Dissecting squares into equal-area triangles: idle questions

Love this post from Matt Baker in which he explains the tropical / 2-adic proof (in fact the only proof!) that you can’t dissect a square into an odd number of triangles of equal area.  In fact, his argument proves more, I think — you can’t dissect a square into triangles whose areas are all rational numbers with odd denominator!

• The space of quadrilaterals in R^2, up to the action of affine linear transformations, is basically just R^2, right?  Because you can move three vertices to (0,0), (0,1), (1,0) and then you’re basically out of linear transformations.   And the property “can be decomposed into n triangles of equal area” is invariant under those transformations.  OK, so — for which choices of the “fourth vertex” do you get a quadrilateral that has a decomposition into an odd number of equal-area triangles? (I think once you’re not a parallelogram you lose the easy decomposition into 2 equal area triangles, so I suppose generically maybe there’s NO equal-area decomposition?)  When do you have a decomposition into triangles whose area has odd denominator?
• What if you replace the square with the torus R^2 / Z^2; for which n can you decompose the torus into equal-area triangles?  What about a Riemann surface with constant negative curvature?  (Now a “triangle” is understood to be a geodesic triangle.)  If I have this right, there are plenty of examples of such surfaces with equal-area triangulations — for instance, Voight gives lots of examples of Shimura curves corresponding to cocompact arithmetic subgroups which are finite index in triangle groups; I think that lets you decompose the Riemann surface into a union of fundamental domains each of which are geodesic triangles of the same area.

Metric chromatic numbers

Idle thought.  Let G be a (loopless) graph, let M be a metric space, and let b be a nonnegative real number.  Then let Conf(G,M,b) be the space of maps from the vertices of the graph to M such that no two adjacent vertices are within b of each other.

When b=0 and G is the complete graph K_n, this is the usual ordered configuration space of n points on M.  When G is the empty graph on n vertices, it’s just M^n.  When M is a set of N points with the discrete metric, Conf(G,M,b) is the same thing for every b;  a set of points whose cardinality is χ_G(N), the chromatic polynomial of G evaluated at N.  When M is a box, Conf(G,M,b) is the “discs in a box” space I blogged about here.  If M is (Z/2Z)^k with Hamming distance, you are asking about how many ways you can supply G with k 2-colorings so that no edge is monochromatic in more than k-b-1 of them.

Update:  Ian Agol links in the comments to this paper about Conf(G,M,0) by Eastwood and Huggett; the paper points out that the Euler characteristic of Conf(G,M,0) computes χ_G(N) whenever M has Euler characteristic N; so M being N points works, but so does M = CP^{N-1}, and that’s the case they study.

When b=0 and G is the complex plane, Conf(G,C,0) is the complement of the graphic arrangement of G; its Poincare polynomial is  t^-{|G|} χ_G(-1/t).  Lots of graphs have the same chromatic polynomial (e.g. all trees do) but do they have homeomorphic Conf(G,C,0)?

This is fun to think about!  Is Conf(G,M,0), for various manifolds other than discrete sets of points, an interesting invariant of a graph?

You can think of

vol(Conf(G,M,b)) vol(M)^{-n}

as a sort of analogue of the chromatic polynomial, especially when b is small; when M = C, for instance, Conf(G,M,b) is just the complement of tubular neighborhoods around the hyperplanes in the graphical arrangement, and its volume should be roughly b^|G|χ_G(1/b) I think.  When b gets big, this function deviates from the chromatic polynomial, and in particular you can ask when it hits 0.

In other words:  you could define an M-chromatic number χ(G,M) to be the smallest B such that Conf(G,M,1/B) is nonempty.  When M is a circle S^1 with circumference 1, you can check that χ(G,M) is at least the clique number of G and at most the chromatic number.  If G is a (2n+1)-cycle, the clique number is 2, the chromatic number is 3, and the S^1-chromatic number is 2+1/n, if I did this right.  Does it have anything to do with the Lovasz number, which is also wedged between clique number and chromatic number?  Relevant here:  the vector chromatic number, which is determined by χ(G,S^{v(G)-1}), and which is in fact a lower bound for the Lovasz number.

 

 

 

 

Idle question: are Kakeya sets winning?

Jayadev Athreya was here last week and reminded me about this notion of “winning sets,” which I learned about from Howie Masur — originally, one of the many contributions of Wolfgang Schmidt.

Here’s a paper by Curt McMullen introducing a somewhat stronger notion, “absolute winning.”

Anyway:  a winning set (or an absolute winning set) in R^n is “big” in some sense.  In particular, it has to have full Hausdorff dimension, but it doesn’t have to have positive measure.

Kakeya sets (subsets of R^n containing a unit line segment in every direction) can have measure zero, by the Besicovitch construction, and are conjectured (when n=2, known) to have Hausdorff dimension n.  So should we expect these sets to be winning?  Are Besicovitch sets winning?

I have no reason to need to know.  I just think these refined classifications of sets which are measure 0 yet still “large” are very interesting.  And for all I know, maybe there are sets where the easiest way to prove they have full Hausdorff dimension is to prove they’re winning!

 

 

Squares and Motzkins

Greg Smith gave an awesome colloquium here last week about his paper with Blekherman and Velasco on sums of squares.

Here’s how it goes.  You can ask:  if a homogeneous degree-d polynomial in n variables over R takes only non-negative values, is it necessarily a sum of squares?  Hilbert showed in 1888 that the answer is yes only when d=2 (the case of quadratic forms), n=2 (the case of binary forms) or (n,d) = (3,4) (the case of ternary quartics.)  Beyond that, there are polynomials that take non-negative values but are not sums of squares, like the Motzkin polynomial

.

So Greg points out that you can formulate this question for an arbitrary real projective variety X/R.  We say a global section f of O(2) on X is nonnegative if it takes nonnegative values on X(R); this is well-defined because 2 is even, so dilating a vector x leaves the sign of f(x) alone.

So we can ask:  is every nonnegative f a sum of squares of global sections of O(1)?  And Blekherman, Smith, and Velasco find there’s an unexpectedly clean criterion:  the answer is yes if and only if X is a variety of minimal degree, i.e. its degree is one more than its codimension.  So e.g. X could be P^n, which is the (n+1,2) case of Hilbert.  Or it could be a rational normal scroll, which is the (2,d) case.  But there’s one other nice case:  P^2 in its Veronese embedding in P^5, where it’s degree 4 and codimension 3.  The sections of O(2) are then just the plane quartics, and you get back Hilbert’s third case.  But now it doesn’t look like a weird outlier; it’s an inevitable consequence of a theorem both simpler and more general.  Not every day you get to out-Hilbert Hilbert.

Idle question follows:

One easy way to get nonnegative homogenous forms is by adding up squares, which all arise as pullback by polynomial maps of the ur-nonnegative form x^2.

But we know, by Hilbert, that this isn’t enough to capture all nonnegative forms; for instance, it misses the Motzkin polynomial.

So what if you throw that in?  That is, we say a Motzkin is a degree-6d form

expressible as

 

for degree-d forms P,Q,R.  A Motzkin is obviously nonnegative.

It is possible that every nonnegative form of degree 6d is a sum of squares and Motzkins?  What if instead of just Motzkins we allow ourselves every nonnegative sextic?  Or every nonnegative homogeneous degree-d form in n variables for n and d less than 1,000,000?  Is it possible that the condition of nonnegativity is in this respect “finitely generated?”

 

 

 

 

 

Idle question: cluster algebras over finite fields and spectral gaps

Yet another great talk at the JMM:  Lauren Williams gave an introduction to cluster algebras in the Current Events section which was perfect for people, like me, who didn’t know the definition.  (The talks by Wei Ho, Sam Payne, and Mladen Bestvina were equally good, but I don’t have any idle questions about them!)

This post will be too long if I try to include the definitions myself, and I wouldn’t do as good a job of exposition as Williams did, so it’s good news that she’s arXived a survey paper which covers roughly the same ground as her talk.

Setup for idle question:  you can get a cluster algebra comes from a process called “seed mutation” — given a rational function field K = k(x_1, … x_m), a labelled seed is a pair (Q,f) where Q is a quiver on m vertices and f = (f_1, … f_m) is a labelling of the vertices of Q with rational functions in K.  For each i, there’s a seed mutation mu_i which is an involution on the labelled seeds; see Williams’s paper for the definition.

Now start with a labelled seed (Q,(x_1, … x_m)) and let T be the set of labelled seeds obtainable from the starting seed by repeated application of seed mutations mu_1, …. m_n for some n < m.  (I didn’t think carefully about the meaning of this special subset of n vertices, which are called the mutable vertices.)

It’s called T because it’s a tree, regular of degree n; each vertex is indexed by a word in the n seed mutations with no letter appearing twice in succession.

Anyway, for each vertex of T and each mutable vertex i you have a rational function f_i.  The cluster algebra is the algebra generated by all these rational functions.

The great miracle — rather, one of the great miracles — is that, by a theorem of Fomin and Zelevinsky, the f_i are all Laurent; that is, their denominators are just monomials in the original functions x_i.

We are now ready for the idle question!

Let’s take k to be a finite field F_q, and let U be (F_q^*)^m, the rational points of the m-torus over F_q.  Choose a point u = (u_1, … u_n) in (F_q^*)^m.

Then for any vertex of T, we can (thanks to the Laurent condition!) evaluate the functions (f_1, …. f_m) at u, getting an element of F_q^m.

So a random walk on the tree T, combined with evaluation at u, gives you a random walk on F_q^m.

Idle question:  Is there a spectral gap for this family of walks, independent of q?

Update:  As David Speyer explains in the comments, this finite random walk is not in general well-defined.  Let me try another phrasing which I think makes sense.

Let t be the endpoint of a length-R random walk on T; then evaluation at (1,1,..1) gives a probability distribution P_{R,N} on (Z/NZ)^m.  Let U_N be the uniform distribution on (Z/NZ)^m.  Now for each N we can ask about the limit

(I don’t think it matters what norm we use.)

The idea is that the random walk on the tree should be equidistributing mod N, and the speed of convergence is governed by Λ_N.  Then we can ask

Idle question mark 2:  Is Λ_N bounded away from 1 by a constant independent of N?

This is a question in “spectral gap” style, which, if I did it right, doesn’t a priori have to do with a sequence of finite graphs.

Motivation:  this setup reminds me of a very well-known story in arithmetic groups; you have a discrete group Gamma which comes equipped with an action on an set of objects “over Z” — then reducing mod p for all p gives you a family of actions of Gamma on larger and larger finite sets, and a critical organizing question is:  do the corresponding graphs have a spectral gap?

For that matter, what happens if you, say, keep k = C and then evaluate your f_i at (1,1,… 1)?  Looking at a bigger and bigger ball in the tree you get bigger and bigger sets of elements of C^m; what do these look like?  Do they shoot off to infinity, accumulate, equidistribute…..?