You are currently browsing the category archive for the ‘paper’ category.

I’ve just uploaded to the arXiv my paper “Mixing for progressions in non-abelian groups“, submitted to Forum of Mathematics, Sigma (which, along with sister publication Forum of Mathematics, Pi, has just opened up its online submission system). This paper is loosely related in subject topic to my two previous papers on polynomial expansion and on recurrence in quasirandom groups (with Vitaly Bergelson), although the methods here are rather different from those in those two papers. The starting motivation for this paper was a question posed in this foundational paper of Tim Gowers on quasirandom groups. In that paper, Gowers showed (among other things) that if ${G}$ was a quasirandom group, patterns such as ${(x,xg,xh, xgh)}$ were mixing in the sense that, for any four sets ${A,B,C,D \subset G}$, the number of such quadruples ${(x,xg,xh, xgh)}$ in ${A \times B \times C \times D}$ was equal to ${(\mu(A) \mu(B) \mu(C) \mu(D) + o(1)) |G|^3}$, where ${\mu(A) := |A| / |G|}$, and ${o(1)}$ denotes a quantity that goes to zero as the quasirandomness of the group goes to infinity. In my recent paper with Vitaly, we also considered mixing properties of some other patterns, namely ${(x,xg,gx)}$ and ${(g,x,xg,gx)}$. This paper is concerned instead with the pattern ${(x,xg,xg^2)}$, that is to say a geometric progression of length three. As observed by Gowers, by applying (a suitably quantitative version of) Roth’s theorem in (cosets of) a cyclic group, one can obtain a recurrence theorem for this pattern without much effort: if ${G}$ is an arbitrary finite group, and ${A}$ is a subset of ${G}$ with ${\mu(A) \geq \delta}$, then there are at least ${c(\delta) |G|^2}$ pairs ${(x,g) \in G}$ such that ${x, xg, xg^2 \in A}$, where ${c(\delta)>0}$ is a quantity depending only on ${\delta}$. However, this argument does not settle the question of whether there is a stronger mixing property, in that the number of pairs ${(x,g) \in G^2}$ such that ${(x,xg,xg^2) \in A \times B \times C}$ should be ${(\mu(A)\mu(B)\mu(C)+o(1)) |G|^2}$ for any ${A,B,C \subset G}$. Informally, this would assert that for ${x, g}$ chosen uniformly at random from ${G}$, the triplet ${(x, xg, xg^2)}$ should resemble a uniformly selected element of ${G^3}$ in some weak sense.

For non-quasirandom groups, such mixing properties can certainly fail. For instance, if ${G}$ is the cyclic group ${G = ({\bf Z}/N{\bf Z},+)}$ (which is abelian and thus highly non-quasirandom) with the additive group operation, and ${A = \{1,\ldots,\lfloor \delta N\rfloor\}}$ for some small but fixed ${\delta > 0}$, then ${\mu(A) = \delta + o(1)}$ in the limit ${N \rightarrow \infty}$, but the number of pairs ${(x,g) \in G^2}$ with ${x, x+g, x+2g \in A}$ is ${(\delta^2/2 + o(1)) |G|^2}$ rather than ${(\delta^3+o(1)) |G|^2}$. The problem here is that the identity ${(x+2g) = 2(x+g) - x}$ ensures that if ${x}$ and ${x+g}$ both lie in ${A}$, then ${x+2g}$ has a highly elevated likelihood of also falling in ${A}$. One can view ${A}$ as the preimage of a small ball under the one-dimensional representation ${\rho: G \rightarrow U(1)}$ defined by ${\rho(n) := e^{2\pi i n/N}}$; similar obstructions to mixing can also be constructed from other low-dimensional representations.

However, by definition, quasirandom groups do not have low-dimensional representations, and Gowers asked whether mixing for ${(x,xg,xg^2)}$ could hold for quasirandom groups. I do not know if this is the case for arbitrary quasirandom groups, but I was able to settle the question for a specific class of quasirandom groups, namely the special linear groups ${G := SL_d(F)}$ over a finite field ${F}$ in the regime where the dimension ${d}$ is bounded (but is at least two) and ${F}$ is large. Indeed, for such groups I can obtain a count of ${(\mu(A) \mu(B) \mu(C) + O( |F|^{-\min(d-1,2)/8} )) |G|^2}$ for the number of pairs ${(x,g) \in G^2}$ with ${(x, xg, xg^2) \in A \times B \times C}$. In fact, I have the somewhat stronger statement that there are ${(\mu(A) \mu(B) \mu(C) \mu(D) + O( |F|^{-\min(d-1,2)/8} )) |G|^2}$ pairs ${(x,g) \in G^2}$ with ${(x,xg,xg^2,g) \in A \times B \times C \times D}$ for any ${A,B,C,D \subset G}$.

I was also able to obtain a partial result for the length four progression ${(x,xg,xg^2, xg^3)}$ in the simpler two-dimensional case ${G = SL_2(F)}$, but I had to make the unusual restriction that the group element ${g \in G}$ was hyperbolic in the sense that it was diagonalisable over the finite field ${F}$ (as opposed to diagonalisable over the algebraic closure ${\overline{F}}$ of that field); this amounts to the discriminant of the matrix being a quadratic residue, and this holds for approximately half of the elements of ${G}$. The result is then that for any ${A,B,C,D \subset G}$, one has ${(\frac{1}{2} \mu(A) \mu(B) \mu(C) \mu(D) + o(1)) |G|^2}$ pairs ${(x,g) \in G}$ with ${g}$ hyperbolic and ${(x,xg,xg^2,xg^3) \subset A \times B \times C \times D}$. (Again, I actually show a slightly stronger statement in which ${g}$ is restricted to an arbitrary subset ${E}$ of hyperbolic elements.)

For the length three argument, the main tools used are the Cauchy-Schwarz inequality, the quasirandomness of ${G}$, and some algebraic geometry to ensure that a certain family of probability measures on ${G}$ that are defined algebraically are approximately uniformly distributed. The length four argument is significantly more difficult and relies on a rather ad hoc argument involving, among other things, expander properties related to the work of Bourgain and Gamburd, and also a “twisted” version of an argument of Gowers that is used (among other things) to establish an inverse theorem for the ${U^3}$ norm.

I give some details of these arguments below the fold.

I’ve just uploaded to the arXiv my joint paper with Vitaly Bergelson, “Multiple recurrence in quasirandom groups“, which is submitted to Geom. Func. Anal.. This paper builds upon a paper of Gowers in which he introduced the concept of a quasirandom group, and established some mixing (or recurrence) properties of such groups. A ${D}$-quasirandom group is a finite group with no non-trivial unitary representations of dimension at most ${D}$. We will informally refer to a “quasirandom group” as a ${D}$-quasirandom group with the quasirandomness parameter ${D}$ large (more formally, one can work with a sequence of ${D_n}$-quasirandom groups with ${D_n}$ going to infinity). A typical example of a quasirandom group is ${SL_2(F_p)}$ where ${p}$ is a large prime. Quasirandom groups are discussed in depth in this blog post. One of the key properties of quasirandom groups established in Gowers’ paper is the following “weak mixing” property: if ${A, B}$ are subsets of ${G}$, then for “almost all” ${g \in G}$, one has

$\displaystyle \mu( A \cap gB ) \approx \mu(A) \mu(B) \ \ \ \ \ (1)$

where ${\mu(A) := |A|/|G|}$ denotes the density of ${A}$ in ${G}$. Here, we use ${x \approx y}$ to informally represent an estimate of the form ${x=y+o(1)}$ (where ${o(1)}$ is a quantity that goes to zero when the quasirandomness parameter ${D}$ goes to infinity), and “almost all ${g \in G}$” denotes “for all ${g}$ in a subset of ${G}$ of density ${1-o(1)}$“. As a corollary, if ${A,B,C}$ have positive density in ${G}$ (by which we mean that ${\mu(A)}$ is bounded away from zero, uniformly in the quasirandomness parameter ${D}$, and similarly for ${B,C}$), then (if the quasirandomness parameter ${D}$ is sufficiently large) we can find elements ${g, x \in G}$ such that ${g \in A}$, ${x \in B}$, ${gx \in C}$. In fact we can find approximately ${\mu(A)\mu(B)\mu(C) |G|^2}$ such pairs ${(g,x)}$. To put it another way: if we choose ${g,x}$ uniformly and independently at random from ${G}$, then the events ${g \in A}$, ${x \in B}$, ${gx \in C}$ are approximately independent (thus the random variable ${(g,x,gx) \in G^3}$ resembles a uniformly distributed random variable on ${G^3}$ in some weak sense). One can also express this mixing property in integral form as

$\displaystyle \int_G \int_G f_1(g) f_2(x) f_3(gx)\ d\mu(g) d\mu(x) \approx (\int_G f_1\ d\mu) (\int_G f_2\ d\mu) (\int_G f_3\ d\mu)$

for any bounded functions ${f_1,f_2,f_3: G \rightarrow {\bf R}}$. (Of course, with ${G}$ being finite, one could replace the integrals here by finite averages if desired.) Or in probabilistic language, we have

$\displaystyle \mathop{\bf E} f_1(g) f_2(x) f_3(gx) \approx \mathop{\bf E} f_1(x_1) f_2(x_2) f_3(x_3)$

where ${g, x, x_1, x_2, x_3}$ are drawn uniformly and independently at random from ${G}$.

As observed in Gowers’ paper, one can iterate this observation to find “parallelopipeds” of any given dimension in dense subsets of ${G}$. For instance, applying (1) with ${A,B,C}$ replaced by ${A \cap hB}$, ${C \cap hD}$, and ${E \cap hF}$ one can assert (after some relabeling) that for ${g,h,x}$ chosen uniformly and independently at random from ${G}$, the events ${g \in A}$, ${h \in B}$, ${gh \in C}$, ${x \in D}$, ${gx \in E}$, ${hx \in F}$, ${ghx \in H}$ are approximately independent whenever ${A,B,C,D,E,F,H}$ are dense subsets of ${G}$; thus the tuple ${(g,h,gh,x,gh,hx,ghx)}$ resebles a uniformly distributed random variable in ${G^7}$ in some weak sense.

However, there are other tuples for which the above iteration argument does not seem to apply. One of the simplest tuples in this vein is the tuple ${(g, x, xg, gx)}$ in ${G^4}$, when ${g, x}$ are drawn uniformly at random from a quasirandom group ${G}$. Here, one does not expect the tuple to behave as if it were uniformly distributed in ${G^4}$, because there is an obvious constraint connecting the last two components ${gx, xg}$ of this tuple: they must lie in the same conjugacy class! In particular, if ${A}$ is a subset of ${G}$ that is the union of conjugacy classes, then the events ${gx \in A}$, ${xg \in A}$ are perfectly correlated, so that ${\mu( gx \in A, xg \in A)}$ is equal to ${\mu(A)}$ rather than ${\mu(A)^2}$. Our main result, though, is that in a quasirandom group, this is (approximately) the only constraint on the tuple. More precisely, we have

Theorem 1 Let ${G}$ be a ${D}$-quasirandom group, and let ${g, x}$ be drawn uniformly at random from ${G}$. Then for any ${f_1,f_2,f_3,f_4: G \rightarrow [-1,1]}$, we have

$\displaystyle \mathop{\bf E} f_1(g) f_2(x) f_3(gx) f_4(xg) = \mathop{\bf E} f_1(x_1) f_2(x_2) f_3(x_3) f_4(x_4) + o(1)$

where ${o(1)}$ goes to zero as ${D \rightarrow \infty}$, ${x_1,x_2,x_3}$ are drawn uniformly and independently at random from ${G}$, and ${x_4}$ is drawn uniformly at random from the conjugates of ${x_3}$ for each fixed choice of ${x_1,x_2,x_3}$.

This is the probabilistic formulation of the above theorem; one can also phrase the theorem in other formulations (such as an integral formulation), and this is detailed in the paper. This theorem leads to a number of recurrence results; for instance, as a corollary of this result, we have

$\displaystyle \mu(A) \mu(B)^2 - o(1) \leq \mu( A \cap gB \cap Bg ) \leq \mu(A) \mu(B) + o(1)$

for almost all ${g \in G}$, and any dense subsets ${A, B}$ of ${G}$; the lower and upper bounds are sharp, with the lower bound being attained when ${B}$ is randomly distributed, and the upper bound when ${B}$ is conjugation-invariant.

To me, the more interesting thing here is not the result itself, but how it is proven. Vitaly and I were not able to find a purely finitary way to establish this mixing theorem. Instead, we had to first use the machinery of ultraproducts (as discussed in this previous post) to convert the finitary statement about a quasirandom group to an infinitary statement about a type of infinite group which we call an ultra quasirandom group (basically, an ultraproduct of increasingly quasirandom finite groups). This is analogous to how the Furstenberg correspondence principle is used to convert a finitary combinatorial problem into an infinitary ergodic theory problem.

Ultra quasirandom groups come equipped with a finite, countably additive measure known as Loeb measure ${\mu_G}$, which is very analogous to the Haar measure of a compact group, except that in the case of ultra quasirandom groups one does not quite have a topological structure that would give compactness. Instead, one has a slightly weaker structure known as a ${\sigma}$-topology, which is like a topology except that open sets are only closed under countable unions rather than arbitrary ones. There are some interesting measure-theoretic and topological issues regarding the distinction between topologies and ${\sigma}$-topologies (and between Haar measure and Loeb measure), but for this post it is perhaps best to gloss over these issues and pretend that ultra quasirandom groups ${G}$ come with a Haar measure. One can then recast Theorem 1 as a mixing theorem for the left and right actions of the ultra approximate group ${G}$ on itself, which roughly speaking is the assertion that

$\displaystyle \int_G f_1(x) L_g f_2(x) L_g R_g f_3(x)\ d\mu_G(x) \approx 0 \ \ \ \ \ (2)$

for “almost all” ${g \in G}$, if ${f_1, f_2, f_3}$ are bounded measurable functions on ${G}$, with ${f_3}$ having zero mean on all conjugacy classes of ${G}$, where ${L_g, R_g}$ are the left and right translation operators

$\displaystyle L_g f(x) := f(g^{-1} x); \quad R_g f(x) := f(xg).$

To establish this mixing theorem, we use the machinery of idempotent ultrafilters, which is a particularly useful tool for understanding the ergodic theory of actions of countable groups ${G}$ that need not be amenable; in the non-amenable setting the classical ergodic averages do not make much sense, but ultrafilter-based averages are still available. To oversimplify substantially, the idempotent ultrafilter arguments let one establish mixing estimates of the form (2) for “many” elements ${g}$ of an infinite-dimensional parallelopiped known as an IP system (provided that the actions ${L_g,R_g}$ of this IP system obey some technical mixing hypotheses, but let’s ignore that for sake of this discussion). The claim then follows by using the quasirandomness hypothesis to show that if the estimate (2) failed for a large set of ${g \in G}$, then this large set would then contain an IP system, contradicting the previous claim.

Idempotent ultrafilters are an extremely infinitary type of mathematical object (one has to use Zorn’s lemma no fewer than three times just to construct one of these objects!). So it is quite remarkable that they can be used to establish a finitary theorem such as Theorem 1, though as is often the case with such infinitary arguments, one gets absolutely no quantitative control whatsoever on the error terms ${o(1)}$ appearing in that theorem. (It is also mildly amusing to note that our arguments involve the use of ultrafilters in two completely different ways: firstly in order to set up the ultraproduct that converts the finitary mixing problem to an infinitary one, and secondly to solve the infinitary mixing problem. Despite some superficial similarities, there appear to be no substantial commonalities between these two usages of ultrafilters.) There is already a fair amount of literature on using idempotent ultrafilter methods in infinitary ergodic theory, and perhaps by further development of ultraproduct correspondence principles, one can use such methods to obtain further finitary consequences (although the state of the art for idempotent ultrafilter ergodic theory has not advanced much beyond the analysis of two commuting shifts ${L_g, R_g}$ currently, which is the main reason why our arguments only handle the pattern ${(g,x,xg,gx)}$ and not more sophisticated patterns).

We also have some miscellaneous other results in the paper. It turns out that by using the triangle removal lemma from graph theory, one can obtain a recurrence result that asserts that whenever ${A}$ is a dense subset of a finite group ${G}$ (not necessarily quasirandom), then there are ${\gg |G|^2}$ pairs ${(x,g)}$ such that ${x, gx, xg}$ all lie in ${A}$. Using a hypergraph generalisation of the triangle removal lemma known as the hypergraph removal lemma, one can obtain more complicated versions of this statement; for instance, if ${A}$ is a dense subset of ${G^2}$, then one can find ${\gg |G|^2}$ triples ${(x,y,g)}$ such that ${(x,y), (gx, y), (gx, gy), (gxg^{-1}, gyg^{-1})}$ all lie in ${A}$. But the method is tailored to the specific types of patterns given here, and we do not have a general method for obtaining recurrence or mixing properties for arbitrary patterns of words in some finite alphabet such as ${g,x,y}$.

We also give some properties of a model example of an ultra quasirandom group, namely the ultraproduct ${SL_2(F)}$ of ${SL_2(F_{p_n})}$ where ${p_n}$ is a sequence of primes going off to infinity. Thanks to the substantial recent progress (by Helfgott, Bourgain, Gamburd, Breuillard, and others) on understanding the expansion properties of the finite groups ${SL_2(F_{p_n})}$, we have a fair amount of knowledge on the ultraproduct ${SL_2(F)}$ as well; for instance any two elements of ${SL_2(F)}$ will almost surely generate a spectral gap. We don’t have any direct application of this particular ultra quasirandom group, but it might be interesting to study it further.

I recently finished the first draft of the last of my books based on my 2011 blog posts (and also my Google buzzes and Google+ posts from that year), entitled “Spending symmetry“.    The PDF of this draft is available here.  This is again a rather  assorted (and lightly edited) collection of posts (and buzzes, and Google+ posts), though concentrating in the areas of analysis (both standard and nonstandard), logic, and geometry.   As always, comments and corrections are welcome.

I’ve just uploaded to the arXiv my paper “Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets“, submitted to Contrib. Disc. Math. The motivation of this paper is to understand a certain polynomial variant of the sum-product phenomenon in finite fields. This phenomenon asserts that if ${A}$ is a non-empty subset of a finite field ${F}$, then either the sumset ${A+A := \{a+b: a,b \in A\}}$ or product set ${A \cdot A := \{ab: a,b \in A \}}$ will be significantly larger than ${A}$, unless ${A}$ is close to a subfield of ${F}$ (or to ${\{1\}}$). In particular, in the regime when ${A}$ is large, say ${|F|^{1-c} < |A| \leq |F|}$, one expects an expansion bound of the form

$\displaystyle |A+A| + |A \cdot A| \gg (|F|/|A|)^{c'} |A| \ \ \ \ \ (1)$

for some absolute constants ${c, c' > 0}$. Results of this type are known; for instance, Hart, Iosevich, and Solymosi obtained precisely this bound for ${(c,c')=(3/10,1/3)}$ (in the case when ${|F|}$ is prime), which was then improved by Garaev to ${(c,c')=(1/3,1/2)}$.

We have focused here on the case when ${A}$ is a large subset of ${F}$, but sum-product estimates are also extremely interesting in the opposite regime in which ${A}$ is allowed to be small (see for instance the papers of Katz-Shen and Li and of Garaev for some recent work in this case, building on some older papers of Bourgain, Katz and myself and of Bourgain, Glibichuk, and Konyagin). However, the techniques used in these two regimes are rather different. For large subsets of ${F}$, it is often profitable to use techniques such as the Fourier transform or the Cauchy-Schwarz inequality to “complete” a sum over a large set (such as ${A}$) into a set over the entire field ${F}$, and then to use identities concerning complete sums (such as the Weil bound on complete exponential sums over a finite field). For small subsets of ${F}$, such techniques are usually quite inefficient, and one has to proceed by somewhat different combinatorial methods which do not try to exploit the ambient field ${F}$. But my paper focuses exclusively on the large ${A}$ regime, and unfortunately does not directly say much (except through reasoning by analogy) about the small ${A}$ case.

Note that it is necessary to have both ${A+A}$ and ${A \cdot A}$ appear on the left-hand side of (1). Indeed, if one just has the sumset ${A+A}$, then one can set ${A}$ to be a long arithmetic progression to give counterexamples to (1). Similarly, if one just has a product set ${A \cdot A}$, then one can set ${A}$ to be a long geometric progression. The sum-product phenomenon can then be viewed that it is not possible to simultaneously behave like a long arithmetic progression and a long geometric progression, unless one is already very close to behaving like a subfield.

Now we consider a polynomial variant of the sum-product phenomenon, where we consider a polynomial image

$\displaystyle P(A,A) := \{ P(a,b): a,b \in A \}$

of a set ${A \subset F}$ with respect to a polynomial ${P: F \times F \rightarrow F}$; we can also consider the asymmetric setting of the image

$\displaystyle P(A,B) := \{ P(a,b): a \in A,b \in B \}$

of two subsets ${A,B \subset F}$. The regime we will be interested is the one where the field ${F}$ is large, and the subsets ${A, B}$ of ${F}$ are also large, but the polynomial ${P}$ has bounded degree. Actually, for technical reasons it will not be enough for us to assume that ${F}$ has large cardinality; we will also need to assume that ${F}$ has large characteristic. (The two concepts are synonymous for fields of prime order, but not in general; for instance, the field with ${2^n}$ elements becomes large as ${n \rightarrow \infty}$ while the characteristic remains fixed at ${2}$, and is thus not going to be covered by the results in this paper.)

In this paper of Vu, it was shown that one could replace ${A \cdot A}$ with ${P(A,A)}$ in (1), thus obtaining a bound of the form

$\displaystyle |A+A| + |P(A,A)| \gg (|F|/|A|)^{c'} |A|$

whenever ${|A| \geq |F|^{1-c}}$ for some absolute constants ${c, c' > 0}$, unless the polynomial ${P}$ had the degenerate form ${P(x,y) = Q(L(x,y))}$ for some linear function ${L: F \times F \rightarrow F}$ and polynomial ${Q: F \rightarrow F}$, in which ${P(A,A)}$ behaves too much like ${A+A}$ to get reasonable expansion. In this paper, we focus instead on the question of bounding ${P(A,A)}$ alone. In particular, one can ask to classify the polynomials ${P}$ for which one has the weak expansion property

$\displaystyle |P(A,A)| \gg (|F|/|A|)^{c'} |A|$

whenever ${|A| \geq |F|^{1-c}}$ for some absolute constants ${c, c' > 0}$. One can also ask for stronger versions of this expander property, such as the moderate expansion property

$\displaystyle |P(A,A)| \gg |F|$

whenever ${|A| \geq |F|^{1-c}}$, or the almost strong expansion property

$\displaystyle |P(A,A)| \geq |F| - O( |F|^{1-c'})$

whenever ${|A| \geq |F|^{1-c}}$. (One can consider even stronger expansion properties, such as the strong expansion property ${|P(A,A)| \geq |F|-O(1)}$, but it was shown by Gyarmati and Sarkozy that this property cannot hold for polynomials of two variables of bounded degree when ${|F| \rightarrow \infty}$.) One can also consider asymmetric versions of these properties, in which one obtains lower bounds on ${|P(A,B)|}$ rather than ${|P(A,A)|}$.

The example of a long arithmetic or geometric progression shows that the polynomials ${P(x,y) = x+y}$ or ${P(x,y) = xy}$ cannot be expanders in any of the above senses, and a similar construction also shows that polynomials of the form ${P(x,y) = Q(f(x)+f(y))}$ or ${P(x,y) = Q(f(x) f(y))}$ for some polynomials ${Q, f: F \rightarrow F}$ cannot be expanders. On the other hand, there are a number of results in the literature establishing expansion for various polynomials in two or more variables that are not of this degenerate form (in part because such results are related to incidence geometry questions in finite fields, such as the finite field version of the Erdos distinct distances problem). For instance, Solymosi established weak expansion for polynomials of the form ${P(x,y) = f(x)+y}$ when ${f}$ is a nonlinear polynomial, with generalisations by Hart, Li, and Shen for various polynomials of the form ${P(x,y) = f(x) + g(y)}$ or ${P(x,y) = f(x) g(y)}$. Further examples of expanding polynomials appear in the work of Shkredov, Iosevich-Rudnev, and Bukh-Tsimerman, as well as the previously mentioned paper of Vu and of Hart-Li-Shen, and these papers in turn cite many further results which are in the spirit of the polynomial expansion bounds discussed here (for instance, dealing with the small ${A}$ regime, or working in other fields such as ${{\bf R}}$ instead of in finite fields ${F}$). We will not summarise all these results here; they are summarised briefly in my paper, and in more detail in the papers of Hart-Li-Shen and of Bukh-Tsimerman. But we will single out one of the results of Bukh-Tsimerman, which is one of most recent and general of these results, and closest to the results of my own paper. Roughly speaking, in this paper it is shown that a polynomial ${P(x,y)}$ of two variables and bounded degree will be a moderate expander if it is non-composite (in the sense that it does not take the form ${P(x,y) = Q(R(x,y))}$ for some non-linear polynomial ${Q}$ and some polynomial ${R}$, possibly having coefficients in the algebraic completion of ${F}$) and is monic on both ${x}$ and ${y}$, thus it takes the form ${P(x,y) = x^d + S(x,y)}$ for some ${d \geq 1}$ and some polynomial ${S}$ of degree at most ${d-1}$ in ${x}$, and similarly with the roles of ${x}$ and ${y}$ reversed, unless ${P}$ is of the form ${P(x,y) = f(x) + g(y)}$ or ${P(x,y) = f(x) g(y)}$ (in which case the expansion theory is covered to a large extent by the previous work of Hart, Li, and Shen).

Our first main result improves upon the Bukh-Tsimerman result by strengthening the notion of expansion and removing the non-composite and monic hypotheses, but imposes a condition of large characteristic. I’ll state the result here slightly informally as follows:

Theorem 1 (Criterion for moderate expansion) Let ${P: F \times F \rightarrow F}$ be a polynomial of bounded degree over a finite field ${F}$ of sufficiently large characteristic, and suppose that ${P}$ is not of the form ${P(x,y) = Q(f(x)+g(y))}$ or ${P(x,y) = Q(f(x)g(y))}$ for some polynomials ${Q,f,g: F \rightarrow F}$. Then one has the (asymmetric) moderate expansion property

$\displaystyle |P(A,B)| \gg |F|$

whenever ${|A| |B| \ggg |F|^{2-1/8}}$.

This is basically a sharp necessary and sufficient condition for asymmetric expansion moderate for polynomials of two variables. In the paper, analogous sufficient conditions for weak or almost strong expansion are also given, although these are not quite as satisfactory (particularly the conditions for almost strong expansion, which include a somewhat complicated algebraic condition which is not easy to check, and which I would like to simplify further, but was unable to).

The argument here resembles the Bukh-Tsimerman argument in many ways. One can view the result as an assertion about the expansion properties of the graph ${\{ (a,b,P(a,b)): a,b \in F \}}$, which can essentially be thought of as a somewhat sparse three-uniform hypergraph on ${F}$. Being sparse, it is difficult to directly apply techniques from dense graph or hypergraph theory for this situation; however, after a few applications of the Cauchy-Schwarz inequality, it turns out (as observed by Bukh and Tsimerman) that one can essentially convert the problem to one about the expansion properties of the set

$\displaystyle \{ (P(a,c), P(b,c), P(a,d), P(b,d)): a,b,c,d \in F \} \ \ \ \ \ (2)$

(actually, one should view this as a multiset, but let us ignore this technicality) which one expects to be a dense set in ${F^4}$, except in the case when the associated algebraic variety

$\displaystyle \{ (P(a,c), P(b,c), P(a,d), P(b,d)): a,b,c,d \in \overline{F} \}$

fails to be Zariski dense, but it turns out that in this case one can use some differential geometry and Riemann surface arguments (after first invoking the Lefschetz principle and the high characteristic hypothesis to work over the complex numbers instead over a finite field) to show that ${P}$ is of the form ${Q(f(x)+g(y))}$ or ${Q(f(x)g(y))}$. This reduction is related to the classical fact that the only one-dimensional algebraic groups over the complex numbers are the additive group ${({\bf C},+)}$, the multiplicative group ${({\bf C} \backslash \{0\},\times)}$, or the elliptic curves (but the latter have a group law given by rational functions rather than polynomials, and so ultimately end up being eliminated from consideration, though they would play an important role if one wanted to study the expansion properties of rational functions).

It remains to understand the structure of the set (2) is. To understand dense graphs or hypergraphs, one of the standard tools of choice is the Szemerédi regularity lemma, which carves up such graphs into a bounded number of cells, with the graph behaving pseudorandomly on most pairs of cells. However, the bounds in this lemma are notoriously poor (the regularity obtained is an inverse tower exponential function of the number of cells), and this makes this lemma unsuitable for the type of expansion properties we seek (in which we want to deal with sets ${A}$ which have a polynomial sparsity, e.g. ${|A| \sim |F|^{1-c}}$). Fortunately, in the case of sets such as (2) which are definable over the language of rings, it turns out that a much stronger regularity lemma is available, which I call the “algebraic regularity lemma”. I’ll state it (again, slightly informally) in the context of graphs as follows:

Lemma 2 (Algebraic regularity lemma) Let ${F}$ be a finite field of large characteristic, and let ${V, W}$ be definable sets over ${F}$ of bounded complexity (i.e. ${V, W}$ are subsets of ${F^n}$, ${F^m}$ for some bounded ${n,m}$ that can be described by some first-order predicate in the language of rings of bounded length and involving boundedly many constants). Let ${E}$ be a definable subset of ${V \times W}$, again of bounded complexity (one can view ${E}$ as a bipartite graph connecting ${V}$ and ${W}$). Then one can partition ${V, W}$ into a bounded number of cells ${V_1,\ldots,V_a}$, ${W_1,\ldots,W_b}$, still definable with bounded complexity, such that for all pairs ${i =1,\ldots a}$, ${j=1,\ldots,b}$, one has the regularity property

$\displaystyle |E \cap (A \times B)| = d_{ij} |A| |B| + O( |F|^{-1/4} |V| |W| )$

for all ${A \subset V_i, B \subset W_i}$, where ${d_{ij} := \frac{|E \cap (V_i \times W_j)|}{|V_i| |W_j|}}$ is the density of ${E}$ in ${V_i \times W_j}$.

This lemma resembles the Szemerédi regularity lemma, but regularises all pairs of cells (not just most pairs), and the regularity is of polynomial strength in ${|F|}$, rather than inverse tower exponential in the number of cells. Also, the cells are not arbitrary subsets of ${V,W}$, but are themselves definable with bounded complexity, which turns out to be crucial for applications. I am optimistic that this lemma will be useful not just for studying expanding polynomials, but for many other combinatorial questions involving dense subsets of definable sets over finite fields.

The above lemma is stated for graphs ${E \subset V \times W}$, but one can iterate it to obtain an analogous regularisation of hypergraphs ${E \subset V_1 \times \ldots \times V_k}$ for any bounded ${k}$ (for application to (2), we need ${k=4}$). This hypergraph regularity lemma, by the way, is not analogous to the strong hypergraph regularity lemmas of Rodl et al. and Gowers developed in the last six or so years, but closer in spirit to the older (but weaker) hypergraph regularity lemma of Chung which gives the same “order ${1}$” regularity that the graph regularity lemma gives, rather than higher order regularity.

One feature of the proof of Lemma 2 which I found striking was the need to use some fairly high powered technology from algebraic geometry, and in particular the Lang-Weil bound on counting points in varieties over a finite field (discussed in this previous blog post), and also the theory of the etale fundamental group. Let me try to briefly explain why this is the case. A model example of a definable set of bounded complexity ${E}$ is a set ${E \subset F^n \times F^m}$ of the form

$\displaystyle E = \{ (x,y) \in F^n \times F^m: \exists t \in F; P(x,y,t)=0 \}$

for some polynomial ${P: F^n \times F^m \times F \rightarrow F}$. (Actually, it turns out that one can essentially write all definable sets as an intersection of sets of this form; see this previous blog post for more discussion.) To regularise the set ${E}$, it is convenient to square the adjacency matrix, which soon leads to the study of counting functions such as

$\displaystyle \mu(x,x') := | \{ (y,t,t') \in F^m \times F \times F: P(x,y,t) = P(x',y,t') = 0 \}|.$

If one can show that this function ${\mu}$ is “approximately finite rank” in the sense that (modulo lower order errors, of size ${O(|F|^{-1/2})}$ smaller than the main term), this quantity depends only on a bounded number of bits of information about ${x}$ and a bounded number of bits of information about ${x'}$, then a little bit of linear algebra will then give the required regularity result.

One can recognise ${\mu(x,x')}$ as counting ${F}$-points of a certain algebraic variety

$\displaystyle V_{x,x'} := \{ (y,t,t') \in \overline{F}^m \times \overline{F} \times \overline{F}: P(x,y,t) = P(x',y,t') = 0 \}.$

The Lang-Weil bound (discussed in this previous post) provides a formula for this count, in terms of the number ${c(x,x')}$ of geometrically irreducible components of ${V_{x,x'}}$ that are defined over ${F}$ (or equivalently, are invariant with respect to the Frobenius endomorphism associated to ${F}$). So the problem boils down to ensuring that this quantity ${c(x,x')}$ is “generically bounded rank”, in the sense that for generic ${x,x'}$, its value depends only on a bounded number of bits of ${x}$ and a bounded number of bits of ${x'}$.

Here is where the étale fundamental group comes in. One can view ${V_{x,x'}}$ as a fibre product ${V_x \times_{\overline{F}^m} V_{x'}}$ of the varieties

$\displaystyle V_x := \{ (y,t) \in \overline{F}^m \times \overline{F}: P(x,y,t) = 0 \}$

and

$\displaystyle V_{x'} := \{ (y,t) \in \overline{F}^m \times \overline{F}: P(x',y,t) = 0 \}$

over ${\overline{F}^m}$. If one is in sufficiently high characteristic (or even better, in zero characteristic, which one can reduce to by an ultraproduct (or nonstandard analysis) construction, similar to that discussed in this previous post), the varieties ${V_x,V_{x'}}$ are generically finite étale covers of ${\overline{F}^m}$, and the fibre product ${V_x \times_{\overline{F}^m} V_{x'}}$ is then also generically a finite étale cover. One can count the components of a finite étale cover of a connected variety by counting the number of orbits of the étale fundamental group acting on a fibre of that variety (much as the number of components of a cover of a connected manifold is the number of orbits of the topological fundamental group acting on that fibre). So if one understands the étale fundamental group of a certain generic subset of ${\overline{F}^m}$ (formed by intersecting together an ${x}$-dependent generic subset of ${\overline{F}^m}$ with an ${x'}$-dependent generic subset), this in principle controls ${c(x,x')}$. It turns out that one can decouple the ${x}$ and ${x'}$ dependence of this fundamental group by using an étale version of the van Kampen theorem for the fundamental group, which I discussed in this previous blog post. With this fact (and another deep fact about the étale fundamental group in zero characteristic, namely that it is topologically finitely generated), one can obtain the desired generic bounded rank property of ${c(x,x')}$, which gives the regularity lemma.

In order to expedite the deployment of all this algebraic geometry (as well as some Riemann surface theory), it is convenient to use the formalism of nonstandard analysis (or the ultraproduct construction), which among other things can convert quantitative, finitary problems in large characteristic into equivalent qualitative, infinitary problems in zero characteristic (in the spirit of this blog post). This allows one to use several tools from those fields as “black boxes”; not just the theory of étale fundamental groups (which are considerably simpler and more favorable in characteristic zero than they are in positive characteristic), but also some results limiting the morphisms between compact Riemann surfaces of high genus (such as the de Franchis theorem, the Riemann-Hurwitz formula, or the fact that all morphisms between elliptic curves are essentially group homomorphisms), which would be quite unwieldy to utilise if one did not first pass to the zero characteristic case (and thence to the complex case) via the ultraproduct construction (followed by the Lefschetz principle).

I found this project to be particularly educational for me, as it forced me to wander outside of my usual range by quite a bit in order to pick up the tools from algebraic geometry and Riemann surfaces that I needed (in particular, I read through several chapters of EGA and SGA for the first time). This did however put me in the slightly unnerving position of having to use results (such as the Riemann existence theorem) whose proofs I have not fully verified for myself, but which are easy to find in the literature, and widely accepted in the field. I suppose this type of dependence on results in the literature is more common in the more structured fields of mathematics than it is in analysis, which by its nature has fewer reusable black boxes, and so key tools often need to be rederived and modified for each new application. (This distinction is discussed further in this article of Gowers.)

Ben Green and I have just uploaded to the arXiv our new paper “On sets defining few ordinary lines“, submitted to Discrete and Computational Geometry. This paper asymptotically solves two old questions concerning finite configurations of points ${P}$ in the plane ${{\mathbb R}^2}$. Given a set ${P}$ of ${n}$ points in the plane, define an ordinary line to be a line containing exactly two points of ${P}$. The classical Sylvester-Gallai theorem, first posed as a problem by Sylvester in 1893, asserts that as long as the points of ${P}$ are not all collinear, ${P}$ defines at least one ordinary line:

It is then natural to pose the question of what is the minimal number of ordinary lines that a set of ${n}$ non-collinear points can generate. In 1940, Melchior gave an elegant proof of the Sylvester-Gallai theorem based on projective duality and Euler’s formula ${V-E+F=2}$, showing that at least three ordinary lines must be created; in 1951, Motzkin showed that there must be ${\gg n^{1/2}}$ ordinary lines. Previously to this paper, the best lower bound was by Csima and Sawyer, who in 1993 showed that there are at least ${6n/13}$ ordinary lines. In the converse direction, if ${n}$ is even, then by considering ${n/2}$ equally spaced points on a circle, and ${n/2}$ points on the line at infinity in equally spaced directions, one can find a configuration of ${n}$ points that define just ${n/2}$ ordinary lines.

As first observed by Böröczky, variants of this example also give few ordinary lines for odd ${n}$, though not quite as few as ${n/2}$; more precisely, when ${n=1 \hbox{ mod } 4}$ one can find a configuration with ${3(n-1)/4}$ ordinary lines, and when ${n = 3 \hbox{ mod } 4}$ one can find a configuration with ${3(n-3)/4}$ ordinary lines. Our first main result is that these configurations are best possible for sufficiently large ${n}$:

Theorem 1 (Dirac-Motzkin conjecture) If ${n}$ is sufficiently large, then any set of ${n}$ non-collinear points in the plane will define at least ${\lfloor n/2\rfloor}$ ordinary lines. Furthermore, if ${n}$ is odd, at least ${3\lfloor n/4\rfloor}$ ordinary lines must be created.

The Dirac-Motzkin conjecture asserts that the first part of this theorem in fact holds for all ${n}$, not just for sufficiently large ${n}$; in principle, our theorem reduces that conjecture to a finite verification, although our bound for “sufficiently large” is far too poor to actually make this feasible (it is of double exponential type). (There are two known configurations for which one has ${(n-1)/2}$ ordinary lines, one with ${n=7}$ (discovered by Kelly and Moser), and one with ${n=13}$ (discovered by Crowe and McKee).)

Our second main result concerns not the ordinary lines, but rather the ${3}$-rich lines of an ${n}$-point set – a line that meets exactly three points of that set. A simple double counting argument (counting pairs of distinct points in the set in two different ways) shows that there are at most

$\displaystyle \binom{n}{2} / \binom{3}{2} = \frac{1}{6} n^2 - \frac{1}{6} n$

${3}$-rich lines. On the other hand, on an elliptic curve, three distinct points P,Q,R on that curve are collinear precisely when they sum to zero with respect to the group law on that curve. Thus (as observed first by Sylvester in 1868), any finite subgroup of an elliptic curve (of which one can produce numerous examples, as elliptic curves in ${{\mathbb R}^2}$ have the group structure of either ${{\mathbb R}/{\mathbb Z}}$ or ${{\mathbb R}/{\mathbb Z} \times ({\mathbb Z}/2{\mathbb Z})}$) can provide examples of ${n}$-point sets with a large number of ${3}$-rich lines (${\lfloor \frac{1}{6} n^2 - \frac{1}{2} n + 1\rfloor}$, to be precise). One can also shift such a finite subgroup by a third root of unity and obtain a similar example with only one fewer ${3}$-rich line. Sylvester then formally posed the question of determining whether this was best possible.

This problem was known as the Orchard planting problem, and was given a more poetic formulation as such by Jackson in 1821 (nearly fifty years prior to Sylvester!):

Our second main result answers this problem affirmatively in the large ${n}$ case:

Theorem 2 (Orchard planting problem) If ${n}$ is sufficiently large, then any set of ${n}$ points in the plane will determine at most ${\lfloor \frac{1}{6} n^2 - \frac{1}{2} n + 1\rfloor}$ ${3}$-rich lines.

Again, our threshold for “sufficiently large” for this ${n}$ is extremely large (though slightly less large than in the previous theorem), and so a full solution of the problem, while in principle reduced to a finitary computation, remains infeasible at present.

Our results also classify the extremisers (and near extremisers) for both of these problems; basically, the known examples mentioned previously are (up to projective transformation) the only extremisers when ${n}$ is sufficiently large.

Our proof strategy follows the “inverse theorem method” from additive combinatorics. Namely, rather than try to prove direct theorems such as lower bounds on the number of ordinary lines, or upper bounds on the number of ${3}$-rich lines, we instead try to prove inverse theorems (also known as structure theorems), in which one attempts a structural classification of all configurations with very few ordinary lines (or very many ${3}$-rich lines). In principle, once one has a sufficiently explicit structural description of these sets, one simply has to compute the precise number of ordinary lines or ${3}$-rich lines in each configuration in the list provided by that structural description in order to obtain results such as the two theorems above.

Note from double counting that sets with many ${3}$-rich lines will necessarily have few ordinary lines. Indeed, if we let ${N_k}$ denote the set of lines that meet exactly ${k}$ points of an ${n}$-point configuration, so that ${N_3}$ is the number of ${3}$-rich lines and ${N_2}$ is the number of ordinary lines, then we have the double counting identity

$\displaystyle \sum_{k=2}^n \binom{k}{2} N_k = \binom{n}{2}$

which among other things implies that any counterexample to the orchard problem can have at most ${n+O(1)}$ ordinary lines. In particular, any structural theorem that lets us understand configurations with ${O(n)}$ ordinary lines will, in principle, allow us to obtain results such as the above two theorems.

As it turns out, we do eventually obtain a structure theorem that is strong enough to achieve these aims, but it is difficult to prove this theorem directly. Instead we proceed more iteratively, beginning with a “cheap” structure theorem that is relatively easy to prove but provides only a partial amount of control on the configurations with ${O(n)}$ ordinary lines. One then builds upon that theorem with additional arguments to obtain an “intermediate” structure theorem that gives better control, then a “weak” structure theorem that gives even more control, a “strong” structure theorem that gives yet more control, and then finally a “very strong” structure theorem that gives an almost complete description of the configurations (but only in the asymptotic regime when ${n}$ is very large). It turns out that the “weak” theorem is enough for the orchard planting problem, and the “strong” version is enough for the Dirac-Motzkin conjecture. (So the “very strong” structure theorem ends up being unnecessary for the two applications given, but may be of interest for other applications.) Note that the stronger theorems do not completely supercede the weaker ones, because the quantitative bounds in the theorems get progressively worse as the control gets stronger.

Before we state these structure theorems, note that all the examples mentioned previously of sets with few ordinary lines involved cubic curves: either irreducible examples such as elliptic curves, or reducible examples such as the union of a circle (or more generally, a conic section) and a line. (We also allow singular cubic curves, such as the union of a conic section and a tangent line, or a singular irreducible curve such as ${\{ (x,y): y^2 = x^3 \}}$.) This turns out to be no coincidence; cubic curves happen to be very good at providing many ${3}$-rich lines (and thus, few ordinary lines), and conversely it turns out that they are essentially the only way to produce such lines. This can already be evidenced by our cheap structure theorem:

Theorem 3 (Cheap structure theorem) Let ${P}$ be a configuration of ${n}$ points with at most ${{}Kn}$ ordinary lines for some ${K \geq 1}$. Then ${P}$ can be covered by at most ${500K}$ cubic curves.

This theorem is already a non-trivial amount of control on sets with few ordinary lines, but because the result does not specify the nature of these curves, and how they interact with each other, it does not seem to be directly useful for applications. The intermediate structure theorem given below gives a more precise amount of control on these curves (essentially guaranteeing that all but at most one of the curve components are lines):

Theorem 4 (Intermediate structure theorem) Let ${P}$ be a configuration of ${n}$ points with at most ${{}Kn}$ ordinary lines for some ${K \geq 1}$. Then one of the following is true:

1. ${P}$ lies on the union of an irreducible cubic curve and an additional ${O(K^{O(1)})}$ points.
2. ${P}$ lies on the union of an irreducible conic section and an additional ${O(K^{O(1)})}$ lines, with ${n/2 + O(K^{O(1)})}$ of the points on ${P}$ in either of the two components.
3. ${P}$ lies on the union of ${O(K)}$ lines and an additional ${O(K^{O(1)})}$ points.

By some additional arguments (including a very nice argument supplied to us by Luke Alexander Betts, an undergraduate at Cambridge, which replaces a much more complicated (and weaker) argument we originally had for this paper), one can cut down the number of lines in the above theorem to just one, giving a more useful structure theorem, at least when ${n}$ is large:

Theorem 5 (Weak structure theorem) Let ${P}$ be a configuration of ${n}$ points with at most ${{}Kn}$ ordinary lines for some ${K \geq 1}$. Assume that ${n \geq \exp(\exp(CK^C))}$ for some sufficiently large absolute constant ${C}$. Then one of the following is true:

1. ${P}$ lies on the union of an irreducible cubic curve and an additional ${O(K^{O(1)})}$ points.
2. ${P}$ lies on the union of an irreducible conic section, a line, and an additional ${O(K^{O(1)})}$ points, with ${n/2 + O(K^{O(1)})}$ of the points on ${P}$ in either of the first two components.
3. ${P}$ lies on the union of a single line and an additional ${O(K^{O(1)})}$ points.

As mentioned earlier, this theorem is already strong enough to resolve the orchard planting problem for large ${n}$. The presence of the double exponential here is extremely annoying, and is the main reason why the final thresholds for “sufficiently large” in our results are excessively large, but our methods seem to be unable to eliminate these exponentials from our bounds (though they can fortunately be confined to a lower bound for ${n}$, keeping the other bounds in the theorem polynomial in ${K}$).

For the Dirac-Motzkin conjecture one needs more precise control on the portion of ${P}$ on the various low-degree curves indicated. This is given by the following result:

Theorem 6 (Strong structure theorem) Let ${P}$ be a configuration of ${n}$ points with at most ${{}Kn}$ ordinary lines for some ${K \geq 1}$. Assume that ${n \geq \exp(\exp(CK^C))}$ for some sufficiently large absolute constant ${C}$. Then, after adding or deleting ${O(K^{O(1)})}$ points from ${P}$ if necessary (modifying ${n}$ appropriately), and then applying a projective transformation, one of the following is true:

1. ${P}$ is a finite subgroup of an elliptic curve (EDIT: as pointed out in comments, one also needs to allow for finite subgroups of acnodal singular cubic curves), possibly shifted by a third root of unity.
2. ${P}$ is the Borozcky example mentioned previously (the union of ${n/2}$ equally spaced points on the circle, and ${n/2}$ points on the line at infinity).
3. ${P}$ lies on a single line.

By applying a final “cleanup” we can replace the ${O(K^{O(1)})}$ in the above theorem with the optimal ${O(K)}$, which is our “very strong” structure theorem. But the strong structure theorem is already sufficient to establish the Dirac-Motzkin conjecture for large ${n}$.

There are many tools that go into proving these theorems, some of which are extremely classical (with at least one going back to the ancient Greeks), and others being more recent. I will discuss some (not all) of these tools below the fold, and more specifically:

1. Melchior’s argument, based on projective duality and Euler’s formula, initially used to prove the Sylvester-Gallai theorem;
2. Chasles’ version of the Cayley-Bacharach theorem, which can convert dual triangular grids (produced by Melchior’s argument) into cubic curves that meet many points of the original configuration ${P}$);
3. Menelaus’s theorem, which is useful for producing ordinary lines when the point configuration lies on a few non-concurrent lines, particularly when combined with a sum-product estimate of Elekes, Nathanson, and Ruzsa;
4. Betts’ argument, that produces ordinary lines when the point configuration lies on a few concurrent lines;
5. A result of Poonen and Rubinstein that any point not on the origin or unit circle can lie on at most seven chords connecting roots of unity; this, together with a variant for elliptic curves, gives the very strong structure theorem, and is also (a strong version of) what is needed to finish off the Dirac-Motzkin and orchard planting problems from the structure theorems given above.

There are also a number of more standard tools from arithmetic combinatorics (e.g. a version of the Balog-Szemeredi-Gowers lemma) which are needed to tie things together at various junctures, but I won’t say more about these methods here as they are (by now) relatively routine.

Two quick updates with regards to polymath projects.  Firstly, given the poll on starting the mini-polymath4 project, I will start the project at Thu July 12 2012 UTC 22:00.  As usual, the main research thread on this project will be held at the polymath blog, with the discussion thread hosted separately on this blog.

Second, the Polymath7 project, which seeks to establish the “hot spots conjecture” for acute-angled triangles, has made a fair amount of progress so far; for instance, the first part of the conjecture (asserting that the second Neumann eigenfunction of an acute non-equilateral triangle is simple) is now solved, and the second part (asserting that the “hot spots” (i.e. extrema) of that second eigenfunction lie on the boundary of the triangle) has been solved in a number of special cases (such as the isosceles case).  It’s been quite an active discussion in the last week or so, with almost 200 comments across two threads (and a third thread freshly opened up just now).  While the problem is still not completely solved, I feel optimistic that it should fall within the next few weeks (if nothing else, it seems that the problem is now at least amenable to a brute force numerical attack, though personally I would prefer to see a more conceptual solution).

Van Vu and I have just uploaded to the arXiv our paper “Random matrices: Universality of local spectral statistics of non-Hermitian matrices“. The main result of this paper is a “Four Moment Theorem” that establishes universality for local spectral statistics of non-Hermitian matrices with independent entries, under the additional hypotheses that the entries of the matrix decay exponentially, and match moments with either the real or complex gaussian ensemble to fourth order. This is the non-Hermitian analogue of a long string of recent results establishing universality of local statistics in the Hermitian case (as discussed for instance in this recent survey of Van and myself, and also in several other places).

The complex case is somewhat easier to describe. Given a (non-Hermitian) random matrix ensemble ${M_n}$ of ${n \times n}$ matrices, one can arbitrarily enumerate the (geometric) eigenvalues as ${\lambda_1(M_n),\ldots,\lambda_n(M_n) \in {\bf C}}$, and one can then define the ${k}$-point correlation functions ${\rho^{(k)}_n: {\bf C}^k \rightarrow {\bf R}^+}$ to be the symmetric functions such that

$\displaystyle \int_{{\bf C}^k} F(z_1,\ldots,z_k) \rho^{(k)}_n(z_1,\ldots,z_k)\ dz_1 \ldots dz_k$

$\displaystyle = {\bf E} \sum_{1 \leq i_1 < \ldots < i_k \leq n} F(\lambda_1(M_n),\ldots,\lambda_k(M_n)).$

In the case when ${M_n}$ is drawn from the complex gaussian ensemble, so that all the entries are independent complex gaussians of mean zero and variance one, it is a classical result of Ginibre that the asymptotics of ${\rho^{(k)}_n}$ near some point ${z \sqrt{n}}$ as ${n \rightarrow \infty}$ and ${z \in {\bf C}}$ is fixed are given by the determinantal rule

$\displaystyle \rho^{(k)}_n(z\sqrt{n} + w_1,\ldots,z\sqrt{n}+w_k) \rightarrow \hbox{det}( K(w_i,w_j) )_{1 \leq i,j \leq k} \ \ \ \ \ (1)$

for ${|z| < 1}$ and

$\displaystyle \rho^{(k)}_n(z\sqrt{n} + w_1,\ldots,z\sqrt{n}+w_k) \rightarrow 0$

for ${|z| > 1}$, where ${K}$ is the reproducing kernel

$\displaystyle K(z,w) := \frac{1}{\pi} e^{-|z|^2/2 - |w|^2/2 + z \overline{w}}.$

(There is also an asymptotic for the boundary case ${|z|=1}$, but it is more complicated to state.) In particular, we see that ${\rho^{(k)}_n(z \sqrt{n}) \rightarrow \frac{1}{\pi} 1_{|z| \leq 1}}$ for almost every ${z}$, which is a manifestation of the well-known circular law for these matrices; but the circular law only captures the macroscopic structure of the spectrum, whereas the asymptotic (1) describes the microscopic structure.

Our first main result is that the asymptotic (1) for ${|z|<1}$ also holds (in the sense of vague convergence) when ${M_n}$ is a matrix whose entries are independent with mean zero, variance one, exponentially decaying tails, and which all match moments with the complex gaussian to fourth order. (Actually we prove a stronger result than this which is valid for all bounded ${z}$ and has more uniform bounds, but is a bit more technical to state.) An analogous result is also established for real gaussians (but now one has to separate the correlation function into components depending on how many eigenvalues are real and how many are strictly complex; also, the limiting distribution is more complicated, being described by Pfaffians rather than determinants). Among other things, this allows us to partially extend some known results on complex or real gaussian ensembles to more general ensembles. For instance, there is a central limit theorem of Rider which establishes a central limit theorem for the number of eigenvalues of a complex gaussian matrix in a mesoscopic disk; from our results, we can extend this central limit theorem to matrices that match the complex gaussian ensemble to fourth order, provided that the disk is small enough (for technical reasons, our error bounds are not strong enough to handle large disks). Similarly, extending some results of Edelman-Kostlan-Shub and of Forrester-Nagao, we can show that for a matrix matching the real gaussian ensemble to fourth order, the number of real eigenvalues is ${\sqrt{\frac{2n}{\pi}} + O(n^{1/2-c})}$ with probability ${1-O(n^{-c})}$ for some absolute constant ${c>0}$.

There are several steps involved in the proof. The first step is to apply the Girko Hermitisation trick to replace the problem of understanding the spectrum of a non-Hermitian matrix, with that of understanding the spectrum of various Hermitian matrices. The two identities that realise this trick are, firstly, Jensen’s formula

$\displaystyle \log |\det(M_n-z_0)| = - \sum_{1 \leq i \leq n: \lambda_i(M_n) \in B(z_0,r)} \log \frac{r}{|\lambda_i(M_n)-z_0|}$

$\displaystyle + \frac{1}{2\pi} \int_0^{2\pi} \log |\det(M_n-z_0-re^{i\theta})|\ d\theta$

that relates the local distribution of eigenvalues to the log-determinants ${\log |\det(M_n-z_0)|}$, and secondly the elementary identity

$\displaystyle \log |\det(M_n - z)| = \frac{1}{2} \log|\det W_{n,z}| + \frac{1}{2} n \log n$

that relates the log-determinants of ${M_n-z}$ to the log-determinants of the Hermitian matrices

$\displaystyle W_{n,z} := \frac{1}{\sqrt{n}} \begin{pmatrix} 0 & M_n -z \\ (M_n-z)^* & 0 \end{pmatrix}.$

The main difficulty is then to obtain concentration and universality results for the Hermitian log-determinants ${\log|\det W_{n,z}|}$. This turns out to be a task that is analogous to the task of obtaining concentration for Wigner matrices (as we did in this recent paper), as well as central limit theorems for log-determinants of Wigner matrices (as we did in this other recent paper). In both of these papers, the main idea was to use the Four Moment Theorem for Wigner matrices (which can now be proven relatively easily by a combination of the local semi-circular law and resolvent swapping methods), combined with (in the latter paper) a central limit theorem for the gaussian unitary ensemble (GUE). This latter task was achieved by using the convenient Trotter normal form to tridiagonalise a GUE matrix, which has the effect of revealing the determinant of that matrix as the solution to a certain linear stochastic difference equation, and one can analyse the distribution of that solution via such tools as the martingale central limit theorem.

The matrices ${W_{n,z}}$ are somewhat more complicated than Wigner matrices (for instance, the semi-circular law must be replaced by a distorted Marchenko-Pastur law), but the same general strategy works to obtain concentration and universality for their log-determinants. The main new difficulty that arises is that the analogue of the Trotter norm for gaussian random matrices is not tridiagonal, but rather Hessenberg (i.e. upper-triangular except for the lower diagonal). This ultimately has the effect of expressing the relevant determinant as the solution to a nonlinear stochastic difference equation, which is a bit trickier to solve for. Fortunately, it turns out that one only needs good lower bounds on the solution, as one can use the second moment method to upper bound the determinant and hence the log-determinant (following a classical computation of Turan). This simplifies the analysis on the equation somewhat.

While this result is the first local universality result in the category of random matrices with independent entries, there are still two limitations to the result which one would like to remove. The first is the moment matching hypotheses on the matrix. Very recently, one of the ingredients of our paper, namely the local circular law, was proved without moment matching hypotheses by Bourgade, Yau, and Yin (provided one stays away from the edge of the spectrum); however, as of this time of writing the other main ingredient – the universality of the log-determinant – still requires moment matching. (The standard tool for obtaining universality without moment matching hypotheses is the heat flow method (and more specifically, the local relaxation flow method), but the analogue of Dyson Brownian motion in the non-Hermitian setting appears to be somewhat intractible, being a coupled flow on both the eigenvalues and eigenvectors rather than just on the eigenvalues alone.)

Ben Green and I have just uploaded to the arXiv our paper “New bounds for Szemeredi’s theorem, Ia: Progressions of length 4 in finite field geometries revisited“, submitted to Proc. Lond. Math. Soc.. This is both an erratum to, and a replacement for, our previous paper “New bounds for Szemeredi’s theorem. I. Progressions of length 4 in finite field geometries“. The main objective in both papers is to bound the quantity ${r_4(F^n)}$ for a vector space ${F^n}$ over a finite field ${F}$ of characteristic greater than ${4}$, where ${r_4(F^n)}$ is defined as the cardinality of the largest subset of ${F^n}$ that does not contain an arithmetic progression of length ${4}$. In our earlier paper, we gave two arguments that bounded ${r_4(F^n)}$ in the regime when the field ${F}$ was fixed and ${n}$ was large. The first “cheap” argument gave the bound

$\displaystyle r_4(F^n) \ll |F|^n \exp( - c \sqrt{\log n} )$

and the more complicated “expensive” argument gave the improvement

$\displaystyle r_4(F^n) \ll |F|^n n^{-c} \ \ \ \ \ (1)$

for some constant ${c>0}$ depending only on ${F}$.

Unfortunately, while the cheap argument is correct, we discovered a subtle but serious gap in our expensive argument in the original paper. Roughly speaking, the strategy in that argument is to employ the density increment method: one begins with a large subset ${A}$ of ${F^n}$ that has no arithmetic progressions of length ${4}$, and seeks to locate a subspace on which ${A}$ has a significantly increased density. Then, by using a “Koopman-von Neumann theorem”, ultimately based on an iteration of the inverse ${U^3}$ theorem of Ben and myself (and also independently by Samorodnitsky), one approximates ${A}$ by a “quadratically structured” function ${f}$, which is (locally) a combination of a bounded number of quadratic phase functions, which one can prepare to be in a certain “locally equidistributed” or “locally high rank” form. (It is this reduction to the high rank case that distinguishes the “expensive” argument from the “cheap” one.) Because ${A}$ has no progressions of length ${4}$, the count of progressions of length ${4}$ weighted by ${f}$ will also be small; by combining this with the theory of equidistribution of quadratic phase functions, one can then conclude that there will be a subspace on which ${f}$ has increased density.

The error in the paper was to conclude from this that the original function ${1_A}$ also had increased density on the same subspace; it turns out that the manner in which ${f}$ approximates ${1_A}$ is not strong enough to deduce this latter conclusion from the former. (One can strengthen the nature of approximation until one restores such a conclusion, but only at the price of deteriorating the quantitative bounds on ${r_4(F^n)}$ one gets at the end of the day to be worse than the cheap argument.)

After trying unsuccessfully to repair this error, we eventually found an alternate argument, based on earlier papers of ourselves and of Bergelson-Host-Kra, that avoided the density increment method entirely and ended up giving a simpler proof of a stronger result than (1), and also gives the explicit value of ${c = 2^{-22}}$ for the exponent ${c}$ in (1). In fact, it gives the following stronger result:

Theorem 1 Let ${A}$ be a subset of ${F^n}$ of density at least ${\alpha}$, and let ${\epsilon>0}$. Then there is a subspace ${W}$ of ${F^n}$ of codimension ${O( \epsilon^{-2^{20}})}$ such that the number of (possibly degenerate) progressions ${a, a+r, a+2r, a+3r}$ in ${A \cap W}$ is at least ${(\alpha^4-\epsilon)|W|^2}$.

The bound (1) is an easy consequence of this theorem after choosing ${\epsilon := \alpha^4/2}$ and removing the degenerate progressions from the conclusion of the theorem.

The main new idea is to work with a local Koopman-von Neumann theorem rather than a global one, trading a relatively weak global approximation to ${1_A}$ with a significantly stronger local approximation to ${1_A}$ on a subspace ${W}$. This is somewhat analogous to how sometimes in graph theory it is more efficient (from the point of view of quantative estimates) to work with a local version of the Szemerédi regularity lemma which gives just a single regular pair of cells, rather than attempting to regularise almost all of the cells. This local approach is well adapted to the inverse ${U^3}$ theorem we use (which also has this local aspect), and also makes the reduction to the high rank case much cleaner. At the end of the day, one ends up with a fairly large subspace ${W}$ on which ${A}$ is quite dense (of density ${\alpha-O(\epsilon)}$) and which can be well approximated by a “pure quadratic” object, namely a function of a small number of quadratic phases obeying a high rank condition. One can then exploit a special positivity property of the count of length four progressions weighted by pure quadratic objects, essentially due to Bergelson-Host-Kra, which then gives the required lower bound.

Just a quick update on my previous post on gamifying the problem-solving process in high school algebra. I had a little time to spare (on an airplane flight, of all things), so I decided to rework the mockup version of the algebra game into something a bit more structured, namely as 12 progressively difficult levels of solving a linear equation in one unknown.  (Requires either Java or Flash.)   Somewhat to my surprise, I found that one could create fairly challenging puzzles out of this simple algebra problem by carefully restricting the moves available at each level. Here is a screenshot of a typical level:

After completing each level, an icon appears which one can click on to proceed to the next level.  (There is no particular rationale, by the way, behind my choice of icons; these are basically selected arbitrarily from the default collection of icons (or more precisely, “costumes”) available in Scratch.)

The restriction of moves made the puzzles significantly more artificial in nature, but I think that this may end up ultimately being a good thing, as to solve some of the harder puzzles one is forced to really start thinking about how the process of solving for an unknown actually works. (One could imagine that if one decided to make a fully fledged game out of this, one could have several modes of play, ranging from a puzzle mode in which one solves some carefully constructed, but artificial, puzzles, to a free-form mode in which one can solve arbitrary equations (including ones that you input yourself) using the full set of available algebraic moves.)

One advantage to gamifying linear algebra, as opposed to other types of algebra, is that there is no need for disjunction (i.e. splitting into cases). In contrast, if one has to solve a problem which involves at least one quadratic equation, then at some point one may be forced to divide the analysis into two disjoint cases, depending on which branch of a square root one is taking. I am not sure how to gamify this sort of branching in a civilised manner, and would be interested to hear of any suggestions in this regard. (A similar problem also arises in proving propositions in Euclidean geometry, which I had thought would be another good test case for gamification, because of the need to branch depending on the order of various points on a line, or rays through a point, or whether two lines are parallel or intersect.)

I recently finished the first draft of the the first of my books, entitled “Hilbert’s fifth problem and related topics“, based on the lecture notes for my graduate course of the same name.    The PDF of this draft is available here.  As always, comments and corrections are welcome.