Tag Archives: idle questions

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

X^4 Y^2 + X^2 Y^4 - 3X^2 Y^2 Z^2 + Z^6.

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


P^4 Q^2 + P^2 Q^4 - 3P^2 Q^2 R^2 + R^6

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?”






Tagged , , , , , ,

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

\Lambda_N = \lim_{R \rightarrow \infty} ||P_{R,N} - U_{N}||^{1/R}

(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…..?


Tagged , , , , , ,

Get every new post delivered to your Inbox.

Join 557 other followers

%d bloggers like this: