Products of Differences over Arbitrary Finite Fields

Products of Differences over Arbitrary Finite Fields, Discrete Analysis 2018:18, 42 pp.

A central problem in arithmetic combinatorics is the Erdős-Szemerédi sum-product problem, which asks whether it is true that if $A$ is a finite set of integers, then either the sumset $A+A$ or the product set $A.A$ must have size at least $|A|^{2-o(1)}$. Erdős and Szemerédi obtained a lower bound (for the size of the larger of the sumset and the product set) of $|A|^{1+c}$ for a small positive constant $c$. For a long time, the record was held by Solymosi, who obtained a bound of $n^{4/3-o(1)}$ with a beautifully simple argument. The 4/3 barrier was finally broken by Konyagin and Shkredov in 2015, and the current record, which stands at 4/3+5/5277, is held by George Shakan. In general, the notion that it is not easy for a set to have both a small sumset and a small product set is referred to as the sum-product phenomenon.

A solution to the Erdős-Szemerédi problem still appears to require a major new idea, but there are a number of related questions for which progress is being made. An interesting variant of the problem, with many applications, concerns the sum-product phenomenon for subsets of finite fields. Here one must be careful with formulating conjectures, since a finite field can have proper subfields, and for those the sum-product phenomenon clearly does not occur. However, important results have been proved under the assumptions on the cardinality of the subset that rule out these obvious counterexamples.

A general class of questions, intimately connected with the sum-product phenomenon in finite fields, is the following. Given a fixed multivariable polynomial $P$ in $k$ variables and a subset $A$ of a finite field $\mathbb F_q$, define the image $P(A)$ of $A$ to be the set of all $P(a_1,\dots,a_k)$ such that the $a_i$ belong to $A$. Then if $A$ has cardinality $m$, what can be said about the size of $P(A)$? For example, if $P$ is the polynomial $xy+zw$, then this is asking for the size of the set $A.A+A.A$, which consists of all $xy+zw$ such that $x,y,z,w\in A$. The relationship with the sum-product phenomenon is obvious.

Of particular interest is to determine how large $A$ has to be in order to guarantee that $P(A)$ to have size at least $cq$ for some absolute constant $q$. (One might consider asking for even more – that $P(A)$ is almost all of $\mathbb F_q$, but as the authors show with an example, this significantly increases the size of the bound one can hope for.) The authors concentrate in particular on the polynomial $(x-y)(z-w)$, so they are studying the product set of the difference set.

Since $\mathbb F_q$ does not have a subfield of cardinality greater than $q^{1/2}$, a natural condition to place on $m$ is that it should be safely larger than $q^{1/2}$. However, except when $q$ is a prime, the exponent $2/3$ has proved to be a rather stubborn barrier. The main result of this paper is to get past it: the authors show that the condition $m\geq q^{2/3-1/13542+o(1)}$ suffices. The main novelty of the proof is a precise description of pairs of sets $A,X\subset\mathbb F_q$ with the property that $|A+XA|$ is almost as small as possible, which constitutes the “structure part” of an argument that works via a structure/randomness dichotomy.

When $q$ is prime, the best known exponent is 3/5: another result of the paper is that this bound suffices even for the off-diagonal case of sets of the form $(A-B).(C-D)$.