VizualBusiness: Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets

Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets:
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.)

Filed under: math.AG, math.CO, paper Tagged: algebraic regularity lemma, definability, etale fundamental group, expanders, polynomials, regularity lemma, van Kampen's theorem

DIGITAL JUICE

VizualBusiness

Friday, November 16, 2012

Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets

No comments:

Post a Comment

Digital Juice for Primary Education

About Me

Translate

Total Pageviews