Introduction
Throughout the paper, p p p is an odd prime and F p \mathbb{F}_p F p is the field with p p p elements. For d ≥ 1 d \ge1 d ≥ 1 , let
Q d ( z ) = z 1 2 + ⋯ + z d 2 , Δ ( E ) = { Q d ( x − y ) : x , y ∈ E } ( E ⊂ F p d ) . Q_d(z)=z_1^2+\cdots+z_d^2,\qquad\Delta(E)=\{Q_d(x-y):x,y\in E\}\quad(E\subset\mathbb{F}_p^d). Q d ( z ) = z 1 2 + ⋯ + z d 2 , Δ ( E ) = { Q d ( x − y ) : x , y ∈ E } ( E ⊂ F p d ) .
The finite-field Erdős–Falconer problem asks how large a set must be to determine a positive proportion of all possible distances. Bourgain, Katz, and Tao [4 ] connected planar distance estimates with the sum–product problem. Iosevich and Rudnev [10 ] developed a Fourier-analytic approach and proved that, for d ≥ 2 d \ge2 d ≥ 2 , the condition ∣ E ∣ ≥ C p d + 1 2 |E| \ge Cp^{\frac{d+1}{2}} ∣ E ∣ ≥ C p 2 d + 1 implies ∣ Δ ( E ) ∣ ≥ c p |\Delta(E)| \ge cp ∣Δ ( E ) ∣ ≥ c p . Hart, Iosevich, Koh, and Rudnev [7 ] showed that the exponent d + 1 2 \frac{d+1}{2} 2 d + 1 cannot in general be lowered in odd dimensions. In even dimensions, it is conjectured that the sharp exponent is d / 2 d/2 d /2 . This was confirmed recently, up to a log factor, in [15 ] .
In this paper, we ask whether the structure of distance sets allows us to obtain a prescribed configuration, such as an arithmetic or a geometric progression, under weaker size assumptions on E E E than those in the distance estimates above. Previous work has considered square and nonsquare distances [12 ] , and the values that can be represented as ratios of nonzero distances [8 , 9 , 14 ] .
In particular, we take a first step in this direction by studying three-term geometric progressions in distance sets. We start with the following definition.
Definition 1.1. Let D ⊂ F p D \subset\mathbb{F}_p D ⊂ F p . A nondegenerate three-term geometric progression in D D D is a triple
x , x r , x r 2 ∈ D , x , r ∈ F p × , r 2 ≠ 1. x,\ xr,\ xr^2\in D,\qquad x,r\in\mathbb{F}_p^\times,\qquad r^2\ne1. x , x r , x r 2 ∈ D , x , r ∈ F p × , r 2 = 1. The three terms are nonzero and pairwise distinct. Equivalently, they are distinct nonzero values t 1 , t 2 , t 3 t_1,t_2,t_3 t 1 , t 2 , t 3 satisfying t 2 2 = t 1 t 3 t_2^2=t_1t_3 t 2 2 = t 1 t 3 . Multiplication by a nonzero scalar preserves the existence of such a progression. Unless otherwise stated, geometric progressions have three terms.
The main question is formulated formally as follows.
Question 1.2. How large must E ⊂ F p d E \subset\mathbb{F}_p^d E ⊂ F p d be in order that Δ ( E ) \Delta(E) Δ ( E ) contain a nondegenerate geometric progression?
Positive-density results already give partial answers for the existence of such progressions. Szemerédi’s theorem [20 ] states that, for each fixed k ≥ 3 k \ge3 k ≥ 3 and δ > 0 \delta> 0 δ > 0 , every subset of { 1 , … , N } \{1,\ldots,N\} { 1 , … , N } of size at least δ N \delta N δ N contains a k k k -term arithmetic progression when N N N is sufficiently large. Applying this theorem to a short interval of exponents in the cyclic group F p × \mathbb{F}_p^\times F p × gives the corresponding assertion for geometric progressions of every fixed length in sets of fixed positive density. For three terms, Roth’s theorem [18 ] is sufficient. The quantitative bounds of Bloom and Sisask [3 ] and Raghavan [17 ] give more information: for every fixed c , K > 0 c,K>0 c , K > 0 , the condition
∣ D ∣ ≥ c p ( log p ) K |D|\ge\frac{cp}{(\log p)^K} ∣ D ∣ ≥ ( log p ) K c p
forces such a progression in D ⊂ F p D \subset\mathbb{F}_p D ⊂ F p when p p p is sufficiently large in terms of c , K c,K c , K .1 Therefore, combining this conclusion with [15 ] , the condition ∣ E ∣ ≫ p d 2 |E| \gg p^{\frac{d}{2}} ∣ E ∣ ≫ p 2 d is sufficient when d d d even. For d = 2 m d=2m d = 2 m , the exponent m m m is sharp in the split cases, namely when m m m is even or p ≡ 1 ( m o d 4 ) p \equiv1 \pmod{4} p ≡ 1 ( mod 4 ) : there is a totally isotropic subspace of size p m p^m p m whose distance set is { 0 } \{0\} { 0 } . In the nonsplit case, when m m m is odd and p ≡ 3 ( m o d 4 ) p \equiv3 \pmod{4} p ≡ 3 ( mod 4 ) , the optimal exponent remains open; see Section 5.1.
It is worth noting that the arithmetic and geometric properties of the distance set play an important role in the study of Question 1.2. For arbitrary sets of field elements, a lower bound with a fixed exponent below one does not force such a progression. More precisely, for each fixed ε > 0 \varepsilon>0 ε > 0 , a size condition ∣ D ∣ ≥ p 1 − ε |D| \ge p^{1-\varepsilon} ∣ D ∣ ≥ p 1 − ε does not force a nondegenerate three-term geometric progression in D ⊂ F p D \subset\mathbb{F}_p D ⊂ F p . Indeed, applying Behrend’s construction [2 ] to a short interval of exponents gives sets of size at least p e − C log p p e^{-C\sqrt{\log p}} p e − C l o g p with no such progression; see Section 5.
We now turn to odd dimensions. For each d ≥ 1 d \ge1 d ≥ 1 , define
M G P , d ( p ) = max { ∣ E ∣ : E ⊂ F p d , Δ ( E ) contains no nondegenerate geometric progression } . M_{\mathrm{GP},d}(p)=\max\{|E|: E\subset\mathbb{F}_p^d,\ \Delta(E)\text{ contains no nondegenerate geometric progression}\}. M GP , d ( p ) = max { ∣ E ∣ : E ⊂ F p d , Δ ( E ) contains no nondegenerate geometric progression } .
Our main result gives upper and lower bounds for this extremal quantity.
Theorem 1.3. There are absolute constants C ≥ 1 C\ge1 C ≥ 1 and p 0 ≥ 7 p_0\ge7 p 0 ≥ 7 such that, for every prime p ≥ p 0 p\ge p_0 p ≥ p 0 and every integer m ≥ 0 m\ge0 m ≥ 0 ,
p m + 7 26 ≤ M G P , 2 m + 1 ( p ) ≤ C p m + 16 25 . (1) p^{m+\frac{7}{26}} \le M_{\mathrm{GP},2m+1}(p) \le Cp^{m+\frac{16}{25}}. \tag*{(1)} p m + 26 7 ≤ M GP , 2 m + 1 ( p ) ≤ C p m + 25 16 . (1)
The constants are independent of the dimension. For m ≥ 1 m\ge1 m ≥ 1 , the sufficient exponent m + 16 25 m+\frac{16}{25} m + 25 16 is strictly smaller than the exponent m + 1 = d + 1 2 m+1=\frac{d+1}{2} m + 1 = 2 d + 1 for a positive proportion of distances in odd dimensions.
For A ⊂ F p A\subset\mathbb{F}_p A ⊂ F p , we have Δ ( A ) = ( A − A ) 2 \Delta(A)=(A-A)^2 Δ ( A ) = ( A − A ) 2 , where ( A − A ) 2 = { ( a − b ) 2 : a , b ∈ A } (A-A)^2=\{(a-b)^2:a,b\in A\} ( A − A ) 2 = {( a − b ) 2 : a , b ∈ A } .
The main ingredient in the proof is the following one-dimensional result.
Proposition 1.4. The following statements hold.
(i) There is an absolute constant C C C such that, for every prime p ≥ 7 p\ge7 p ≥ 7 and every A ⊂ F p A\subset\mathbb{F}_p A ⊂ F p , the condition
∣ A ∣ ≥ C p 16 25 |A|\ge Cp^{\frac{16}{25}} ∣ A ∣ ≥ C p 25 16 implies that ( A − A ) 2 (A-A)^2 ( A − A ) 2 contains a nondegenerate geometric progression.
(ii) For every sufficiently large prime p p p , there exists a set A ⊂ F p A\subset\mathbb{F}_p A ⊂ F p such that
∣ A ∣ ≥ p 7 26 |A|\ge p^{\frac{7}{26}} ∣ A ∣ ≥ p 26 7 and κ ( A − A ) 2 \kappa(A-A)^2 κ ( A − A ) 2 contains no nondegenerate geometric progression for every κ ∈ F p × \kappa\in\mathbb{F}_p^\times κ ∈ F p × .
Geometric progressions in sumsets provide another relevant comparison. Ahmadi and Shparlinski [1 Theorem 1] proved that A + B A+B A + B contains three distinct nonzero terms in geometric progression whenever A , B ⊂ F p A,B\subset\mathbb{F}_p A , B ⊂ F p and ∣ A ∣ ∣ B ∣ ≥ 20 p 4 3 |A||B|\ge20p^{\frac{4}{3}} ∣ A ∣∣ B ∣ ≥ 20 p 3 4 . Taking B = − A B=-A B = − A gives such a progression in A − A A-A A − A when ∣ A ∣ ≥ 20 p 2 3 |A|\ge\sqrt{20}\,p^{\frac{2}{3}} ∣ A ∣ ≥ 20 p 3 2 . Shparlinski [19 ] strengthened the vector-space result and obtained progressions with a separate ratio in each coordinate.
Proposition 1.4(i) gives the following improvement for difference sets.
Corollary 1.5. There is an absolute constant C C C such that, for every prime p ≥ 7 p \ge7 p ≥ 7 and every A ⊂ F p A \subset\mathbb{F}_p A ⊂ F p with ∣ A ∣ ≥ C p 16 / 25 |A| \ge Cp^{16/25} ∣ A ∣ ≥ C p 16/25 , there exist x , r ∈ F p × x,r \in\mathbb{F}_p^\times x , r ∈ F p × such that
x , x r , x r 2 ∈ A − A , r 4 ≠ 1. x,\ xr,\ xr^2 \in A-A,\qquad r^4 \ne1. x , x r , x r 2 ∈ A − A , r 4 = 1.
Sketch of main ideas of the proofs. We first reduce the problem in odd dimensions to dimension one, using a one-dimensional version of the quotient argument of Pham, Shen, and Xue [16 ] . We choose an m m m -dimensional totally isotropic subspace W W W . More precisely, averaging over its orthogonal-group orbit controls the number of pairs of points of E E E in common affine cosets of W W W . In a suitable affine coset of W ⊥ W^\perp W ⊥ , projection to the one-dimensional space W ⊥ / W W^\perp/W W ⊥ / W then produces a large set A ⊂ F p A \subset\mathbb{F}_p A ⊂ F p with κ ( A − A ) 2 ⊆ Δ ( E ) \kappa(A-A)^2 \subseteq\Delta(E) κ ( A − A ) 2 ⊆ Δ ( E ) for some κ ≠ 0 \kappa\ne0 κ = 0 . For the lower bound, replacing each point of A A A by a translate of W W W multiplies the cardinality by p m p^m p m and changes the distance set only by a nonzero scalar.
To prove Proposition 1.4(i), suppose that ( A − A ) 2 (A-A)^2 ( A − A ) 2 contains no nondegenerate geometric progression. For t ≠ 0 t \ne0 t = 0 with t 4 ≠ 1 t^4 \ne1 t 4 = 1 , the map
( a , b , c ) ⟼ ( b − t a , c − t b ) (a,b,c) \longmapsto(b-ta,c-tb) ( a , b , c ) ⟼ ( b − t a , c − t b )
is injective on A 3 A^3 A 3 . This gives ∣ A ∣ 3 ≤ p 2 |A|^3 \le p^2 ∣ A ∣ 3 ≤ p 2 and bounds the sizes of intersections of translates and dilates of A A A . Combining this injectivity with Plünnecke’s inequality gives ∣ A − A ∣ ≥ ∣ A ∣ 5 / 4 |A-A| \ge|A|^{5/4} ∣ A − A ∣ ≥ ∣ A ∣ 5/4 . We apply these estimates to the variance of the number of representations as a product of two nonzero differences. At every nonzero squared difference this number is small, whereas its mean is large when ∣ A ∣ |A| ∣ A ∣ is large. Comparing the resulting lower and upper bounds for the variance gives ∣ A ∣ ≪ p 16 / 25 |A| \ll p^{16/25} ∣ A ∣ ≪ p 16/25 .
For part (ii), we select vectors in { 0 , 1 , 2 , 3 } L \{0,1,2,3\}^{L} { 0 , 1 , 2 , 3 } L with prescribed digit counts and project them by a random linear map to F p \mathbb{F}_p F p . We delete points to remove relations that would produce nondegenerate geometric progressions among squared differences. The choice of four digits ensures that polynomial identities give only degenerate progressions. Suitable digit weights bound the number of deleted points and leave a set of size at least p 7 / 26 p^{7/26} p 7/26 . The cylinder construction then gives the examples in every odd dimension.
Structure. Section 2 contains the reduction to dimension one and deduces Theorem 1.3 from Proposition 1.4. Sections 3 and 4 prove parts (i) and (ii) of that proposition, respectively. Section 5 discusses even dimensions and the remaining extremal questions.
We write X ≪ Y X \ll Y X ≪ Y if X ≤ C Y X \le CY X ≤ C Y for an absolute constant C > 0 C > 0 C > 0 , X ≫ Y X \gg Y X ≫ Y if Y ≪ X Y \ll X Y ≪ X , and X ≍ Y X \asymp Y X ≍ Y if both inequalities hold. Constants may vary from one occurrence to the next. We use log for the natural logarithm.
Reduction: from 2 m + 1 2m+1 2 m + 1 to 1 1 1
We compare the extremal problem in odd dimensions with the one-dimensional problem. The comparison does not depend on the exponents in Theorem 1.3.
Proposition 2.1. For every prime p ≥ 7 p \ge7 p ≥ 7 and every integer m ≥ 0 m \ge0 m ≥ 0 ,
p m M G P , 1 ( p ) ≤ M G P , 2 m + 1 ( p ) ≤ 4 p m M G P , 1 ( p ) . (2) p^m M_{\mathrm{GP},1}(p) \le M_{\mathrm{GP},2m+1}(p) \le4p^m M_{\mathrm{GP},1}(p). \tag*{(2)} p m M GP , 1 ( p ) ≤ M GP , 2 m + 1 ( p ) ≤ 4 p m M GP , 1 ( p ) . (2)
The constants are independent of the dimension. Thus, every one-dimensional upper bound or construction transfers to all odd dimensions, with the factor p m p^m p m . For the upper bound, we extract a large set in an isotropic quotient. For the lower bound, we replace each point of a one-dimensional set by a translate of a totally isotropic subspace. We first record the quadratic-form and Fourier identities used in these two arguments.
Quadratic forms and isotropic quotients
Let Q Q Q be a nondegenerate quadratic form on F p d \mathbb{F}_p^d F p d . Its associated bilinear form is
B Q ( u , v ) = Q ( u + v ) − Q ( u ) − Q ( v ) 2 . B_Q(u,v)=\frac{Q(u+v)-Q(u)-Q(v)}{2}. B Q ( u , v ) = 2 Q ( u + v ) − Q ( u ) − Q ( v ) .
For a subspace W ⊂ F p d W\subset\mathbb{F}_p^d W ⊂ F p d , we write
W ⊥ = { u ∈ F p d : B Q ( u , w ) = 0 for every w ∈ W } . W^\perp=\{u\in\mathbb{F}_p^d:B_Q(u,w)=0\text{ for every }w\in W\}. W ⊥ = { u ∈ F p d : B Q ( u , w ) = 0 for every w ∈ W } .
For the standard form Q d Q_d Q d , we have B Q d ( u , v ) = u ⋅ v B_{Q_d}(u,v)=u\cdot v B Q d ( u , v ) = u ⋅ v . All orthogonal complements below are taken with respect to the form under consideration.
The subspace W W W is totally isotropic if Q ( w ) = 0 Q(w)=0 Q ( w ) = 0 for every w ∈ W w\in W w ∈ W . Since p p p is odd, this implies B Q ( w , w ′ ) = 0 B_Q(w,w')=0 B Q ( w , w ′ ) = 0 for all w , w ′ ∈ W w,w'\in W w , w ′ ∈ W . Hence, W ⊂ W ⊥ W\subset W^\perp W ⊂ W ⊥ . If u ∈ W ⊥ u\in W^\perp u ∈ W ⊥ and w ∈ W w\in W w ∈ W , then
Q ( u + w ) = Q ( u ) + 2 B Q ( u , w ) + Q ( w ) = Q ( u ) . Q(u+w)=Q(u)+2B_Q(u,w)+Q(w)=Q(u). Q ( u + w ) = Q ( u ) + 2 B Q ( u , w ) + Q ( w ) = Q ( u ) .
Thus, the value of Q ( u ) Q(u) Q ( u ) depends only on the coset u + W u+W u + W , so Q Q Q defines a quadratic form on W ⊥ / W W^\perp/W W ⊥ / W . In particular, passing from an affine coset of W ⊥ W^\perp W ⊥ to this quotient preserves the quadratic values of all differences.
The induced form is nondegenerate. Indeed, if u ∈ W ⊥ u\in W^\perp u ∈ W ⊥ satisfies B Q ( u , v ) = 0 B_Q(u,v)=0 B Q ( u , v ) = 0 for every v ∈ W ⊥ v\in W^\perp v ∈ W ⊥ , then u ∈ ( W ⊥ ) ⊥ = W u\in(W^\perp)^\perp=W u ∈ ( W ⊥ ) ⊥ = W , so its class in the quotient is zero. Since dim W ⊥ = d − dim W \dim W^\perp=d-\dim W dim W ⊥ = d − dim W , we also have
dim ( W ⊥ / W ) = d − 2 dim W . (3) \dim(W^\perp/W)=d-2\dim W. \tag*{(3)} dim ( W ⊥ / W ) = d − 2 dim W . (3)
Witt decomposition shows that every nondegenerate quadratic form on F p 2 m + 1 \mathbb{F}_p^{2m+1} F p 2 m + 1 has a totally isotropic subspace of dimension m m m ; see [9 Lemma 2.1] . For such a subspace W W W , the quotient W ⊥ / W W^\perp/W W ⊥ / W is one-dimensional and nondegenerate. Therefore, the induced quadratic form is κ t 2 \kappa t^2 κ t 2 with κ ∈ F p × \kappa\in\mathbb{F}_p^\times κ ∈ F p × .
Extraction of a one-dimensional set
The next lemma extracts a set A ⊂ F p A\subset\mathbb{F}_p A ⊂ F p whose squared differences, after multiplication by a nonzero scalar, belong to Δ ( E ) \Delta(E) Δ ( E ) .
Lemma 2.2. Let p ≥ 7 p\ge7 p ≥ 7 , let m ≥ 1 m\ge1 m ≥ 1 , and let ∅ ≠ E ⊂ F p 2 m + 1 \varnothing\ne E\subset\mathbb{F}_p^{2m+1} ∅ = E ⊂ F p 2 m + 1 . There are A ⊂ F p A\subset\mathbb{F}_p A ⊂ F p and κ ∈ F p × \kappa\in\mathbb{F}_p^\times κ ∈ F p × such that
∣ A ∣ ≥ ∣ E ∣ p m ( 2 + ∣ E ∣ p m + 1 ) , κ ( A − A ) 2 ⊆ Δ ( E ) . (4) |A|\ge\frac{|E|}{p^m\left(2+\frac{|E|}{p^{m+1}}\right)},\qquad\kappa(A-A)^2\subseteq\Delta(E). \tag*{(4)} ∣ A ∣ ≥ p m ( 2 + p m + 1 ∣ E ∣ ) ∣ E ∣ , κ ( A − A ) 2 ⊆ Δ ( E ) . (4)
When ∣ E ∣ ≤ p m + 1 |E|\le p^{m+1} ∣ E ∣ ≤ p m + 1 , the denominator in parentheses in (4) is at most 3. We retain the full bound so that Proposition 2.1 can be proved without an initial restriction on ∣ E ∣ |E| ∣ E ∣ .
Proof. We seek a totally isotropic m m m -dimensional subspace W W W and an affine coset of W ⊥ W^\perp W ⊥ in which many cosets of W W W meet E E E . After translation, their images in W ⊥ / W W^\perp/W W ⊥ / W will form the required set A A A . To find W W W , we estimate the number of pairs of points of E E E lying in the same coset of W W W .
We first bound the number of pairs at distance zero. Write S 0 = { x ∈ F p 2 m + 1 : Q 2 m + 1 ( x ) = 0 } S_0=\{x\in\mathbb{F}_p^{2m+1}:Q_{2m+1}(x)=0\} S 0 = { x ∈ F p 2 m + 1 : Q 2 m + 1 ( x ) = 0 } . We have ∣ S 0 ∣ = p 2 m |S_0|=p^{2m} ∣ S 0 ∣ = p 2 m and
∣ { ( x , y ) ∈ E 2 : Q 2 m + 1 ( x − y ) = 0 } ∣ ≤ ∣ E ∣ 2 p + p m ∣ E ∣ , (5) \left|\{(x,y)\in E^2:Q_{2m+1}(x-y)=0\}\right|\leq\frac{|E|^2}{p}+p^m|E|, \tag*{(5)} {( x , y ) ∈ E 2 : Q 2 m + 1 ( x − y ) = 0 } ≤ p ∣ E ∣ 2 + p m ∣ E ∣ , (5)
as follows from the sphere Fourier formula in [11 Section 4.1] . We sketch the argument to make the constant explicit. For f : F p 2 m + 1 → C f:\mathbb{F}_p^{2m+1}\to\mathbb{C} f : F p 2 m + 1 → C , write
f ^ ( ξ ) = p − ( 2 m + 1 ) ∑ x ∈ F p 2 m + 1 f ( x ) e − 2 π i x ⋅ ξ / p . \widehat{f}(\xi)=p^{-(2m+1)}\sum_{x\in\mathbb{F}_p^{2m+1}}f(x)e^{-2\pi i x\cdot\xi/p}. f ( ξ ) = p − ( 2 m + 1 ) x ∈ F p 2 m + 1 ∑ f ( x ) e − 2 π i x ⋅ ξ / p .
The sphere formula has a remaining character sum that is either zero or has absolute value p \sqrt{p} p . Together with Plancherel’s identity, this give
1 S 0 ^ ( 0 ) = p − 1 , ∣ 1 S 0 ^ ( ξ ) ∣ ≤ p − m − 1 ( ξ ≠ 0 ) , \widehat{1_{S_0}}(0)=p^{-1},\qquad\left|\widehat{1_{S_0}}(\xi)\right|\leq p^{-m-1}\quad(\xi\ne0), 1 S 0 ( 0 ) = p − 1 , 1 S 0 ( ξ ) ≤ p − m − 1 ( ξ = 0 ) ,
∑ ξ ∈ F p 2 m + 1 ∣ 1 E ^ ( ξ ) ∣ 2 = p − ( 2 m + 1 ) ∣ E ∣ . \sum_{\xi\in\mathbb{F}_p^{2m+1}}\left|\widehat{1_E}(\xi)\right|^2=p^{-(2m+1)}|E|. ξ ∈ F p 2 m + 1 ∑ 1 E ( ξ ) 2 = p − ( 2 m + 1 ) ∣ E ∣.
Fourier inversion therefore yields
∑ x , y ∈ E 1 S 0 ( x − y ) = p 4 m + 2 ∑ ξ ∈ F p 2 m + 1 1 S 0 ^ ( ξ ) ∣ 1 E ^ ( ξ ) ∣ 2 ≤ ∣ E ∣ 2 p + p 4 m + 2 p − m − 1 p − ( 2 m + 1 ) ∣ E ∣ = ∣ E ∣ 2 p + p m ∣ E ∣ , \begin{aligned}
\sum_{x,y\in E}1_{S_0}(x-y)=p^{4m+2}\sum_{\xi\in\mathbb{F}_p^{2m+1}}\widehat{1_{S_0}}(\xi)\left|\widehat{1_E}(\xi)\right|^2 \\
&\leq\frac{|E|^2}{p}+p^{4m+2}p^{-m-1}p^{-(2m+1)}|E| \\
&=\frac{|E|^2}{p}+p^m|E|,
\end{aligned} x , y ∈ E ∑ 1 S 0 ( x − y ) = p 4 m + 2 ξ ∈ F p 2 m + 1 ∑ 1 S 0 ( ξ ) 1 E ( ξ ) 2 ≤ p ∣ E ∣ 2 + p 4 m + 2 p − m − 1 p − ( 2 m + 1 ) ∣ E ∣ = p ∣ E ∣ 2 + p m ∣ E ∣ ,
which proves (2.4).
We now average over isotropic subspaces. Choose one such subspace of dimension m m m , and choose W W W uniformly from its orbit under the orthogonal group. To compute the probability that a fixed vector lies in W W W , we use transitivity on the nonzero isotropic vectors. For Q 2 m + 1 ( u ) ≠ 0 Q_{2m+1}(u)\ne0 Q 2 m + 1 ( u ) = 0 , reflection across u ⊥ u^\perp u ⊥ is the map
x ⟼ x − 2 x ⋅ u Q 2 m + 1 ( u ) u . x\longmapsto x-\frac{2x\cdot u}{Q_{2m+1}(u)}u. x ⟼ x − Q 2 m + 1 ( u ) 2 x ⋅ u u .
For two nonzero isotropic vectors v , v ′ v,v' v , v ′ , reflection across the hyperplane orthogonal to v − v ′ v-v' v − v ′ sends v v v to v ′ v' v ′ if v ⋅ v ′ ≠ 0 v\cdot v'\ne0 v ⋅ v ′ = 0 . Indeed, Q 2 m + 1 ( v − v ′ ) = − 2 v ⋅ v ′ Q_{2m+1}(v-v')=-2v\cdot v' Q 2 m + 1 ( v − v ′ ) = − 2 v ⋅ v ′ and v ⋅ ( v − v ′ ) = − v ⋅ v ′ v\cdot(v-v')=-v\cdot v' v ⋅ ( v − v ′ ) = − v ⋅ v ′ . If v ⋅ v ′ = 0 v\cdot v'=0 v ⋅ v ′ = 0 , choose u u u with Q 2 m + 1 ( u ) ( v ⋅ u ) ( v ′ ⋅ u ) ≠ 0 Q_{2m+1}(u)(v\cdot u)(v'\cdot u)\ne0 Q 2 m + 1 ( u ) ( v ⋅ u ) ( v ′ ⋅ u ) = 0 and first reflect v v v across the hyperplane orthogonal to u u u . Its inner product with v ′ v' v ′ is then nonzero, since
( v − 2 v ⋅ u Q 2 m + 1 ( u ) u ) ⋅ v ′ = − 2 ( v ⋅ u ) ( v ′ ⋅ u ) Q 2 m + 1 ( u ) ≠ 0. \left(v-\frac{2v\cdot u}{Q_{2m+1}(u)}u\right)\cdot v'=-\frac{2(v\cdot u)(v'\cdot u)}{Q_{2m+1}(u)}\ne0. ( v − Q 2 m + 1 ( u ) 2 v ⋅ u u ) ⋅ v ′ = − Q 2 m + 1 ( u ) 2 ( v ⋅ u ) ( v ′ ⋅ u ) = 0.
A second reflection therefore sends this image of v v v to v ′ v' v ′ . Such a u u u exists because the nonzero polynomial u ↦ Q 2 m + 1 ( u ) ( v ⋅ u ) ( v ′ ⋅ u ) u \mapsto Q_{2m+1}(u)(v \cdot u)(v' \cdot u) u ↦ Q 2 m + 1 ( u ) ( v ⋅ u ) ( v ′ ⋅ u ) has degree four, less than p p p , and so cannot vanish at every point of F p 2 m + 1 \mathbb{F}_p^{2m+1} F p 2 m + 1 . It follows by double counting that, for every nonzero isotropic vector v v v ,
Pr ( v ∈ W ) = p m − 1 p 2 m − 1 = 1 p m + 1 < p − m . (6) \Pr(v \in W) = \frac{p^m-1}{p^{2m}-1} = \frac{1}{p^m+1} < p^{-m}. \tag*{(6)} Pr ( v ∈ W ) = p 2 m − 1 p m − 1 = p m + 1 1 < p − m . (6)
The sum ∑ x + W ∣ E ∩ ( x + W ) ∣ 2 \sum_{x+W} |E \cap(x+W)|^2 ∑ x + W ∣ E ∩ ( x + W ) ∣ 2 counts ordered pairs of points whose difference lies in W W W . By (5) and (2.5), its expectation is at most
∣ E ∣ + p − m ( ∣ E ∣ 2 p + p m ∣ E ∣ ) = 2 ∣ E ∣ + ∣ E ∣ 2 p m + 1 . |E| + p^{-m}\left(\frac{|E|^2}{p} + p^m|E|\right) = 2|E| + \frac{|E|^2}{p^{m+1}}. ∣ E ∣ + p − m ( p ∣ E ∣ 2 + p m ∣ E ∣ ) = 2∣ E ∣ + p m + 1 ∣ E ∣ 2 .
Fix W W W for which this bound holds. The Cauchy–Schwarz inequality then shows that at least
∣ E ∣ 2 + ∣ E ∣ p m + 1 \frac{|E|}{2+\frac{|E|}{p^{m+1}}} 2 + p m + 1 ∣ E ∣ ∣ E ∣
affine cosets of W W W meet E E E . Each lies in one affine coset of W ⊥ W^\perp W ⊥ . Since there are p m p^m p m cosets of W ⊥ , W^\perp, W ⊥ , some affine subspace z + W ⊥ z+W^\perp z + W ⊥ contains at least
∣ E ∣ p m ( 2 + ∣ E ∣ p m + 1 ) \frac{|E|}{p^m\left(2+\frac{|E|}{p^{m+1}}\right)} p m ( 2 + p m + 1 ∣ E ∣ ) ∣ E ∣
cosets of W W W that meet E E E .
Translate E ∩ ( z + W ⊥ ) E\cap(z+W^\perp) E ∩ ( z + W ⊥ ) by − z -z − z and take its image in W ⊥ / W W^\perp/W W ⊥ / W . By (3) , the quotient is one-dimensional and nondegenerate, so its form can be written as κ t 2 \kappa t^2 κ t 2 with κ ≠ 0 \kappa\ne0 κ = 0 . Identify the image with a set A ⊂ F p A \subset\mathbb{F}_p A ⊂ F p , and choose one representative x a ∈ E ∩ ( z + W ⊥ ) x_a \in E\cap(z+W^\perp) x a ∈ E ∩ ( z + W ⊥ ) for each a ∈ A a \in A a ∈ A . The quotient form gives
κ ( a − b ) 2 = Q 2 m + 1 ( x a − x b ) ( a , b ∈ A ) . \kappa(a-b)^2 = Q_{2m+1}(x_a-x_b) \qquad(a,b \in A). κ ( a − b ) 2 = Q 2 m + 1 ( x a − x b ) ( a , b ∈ A ) .
This proves both assertions and completes the proof.
The cylinder construction
The reverse construction replaces each element of A A A by a translate of an m m m -dimensional totally isotropic subspace. This multiplies the cardinality by p m p^m p m , while the distances depend only on the corresponding elements of A A A . The following lemma is the coordinate-free form of the construction in [9 Lemma 2.1(ii) and Section 4.2] .
Lemma 2.3. Let m ≥ 0 m \ge0 m ≥ 0 be an integer and let d = 2 m + 1 d=2m+1 d = 2 m + 1 . There exists a totally isotropic m m m -dimensional subspace W ⊂ F p d W \subset\mathbb{F}_p^d W ⊂ F p d and a vector e ∈ W ⊥ ∖ W e \in W^\perp\setminus W e ∈ W ⊥ ∖ W such that κ : = Q d ( e ) ≠ 0 \kappa:= Q_d(e) \ne0 κ := Q d ( e ) = 0 and, for every A ⊂ F p A \subset\mathbb{F}_p A ⊂ F p , the set
E A : = { w + a e : w ∈ W , a ∈ A } E_A := \{w+ae : w \in W,\ a \in A\} E A := { w + a e : w ∈ W , a ∈ A } satisfies
∣ E A ∣ = p m ∣ A ∣ , Δ ( E A ) = κ ( A − A ) 2 . (7) |E_A| = p^m|A|,\qquad\Delta(E_A)=\kappa(A-A)^2. \tag*{(7)} ∣ E A ∣ = p m ∣ A ∣ , Δ ( E A ) = κ ( A − A ) 2 . (7)
Proof. If m = 0 m=0 m = 0 , then the conclusion follows by taking W = { 0 } W=\{0\} W = { 0 } and e = 1 e=1 e = 1 , so that κ = Q 1 ( e ) = 1 \kappa=Q_1(e)=1 κ = Q 1 ( e ) = 1 . Therefore, it remains to prove the result in the case m ≥ 1 m\ge1 m ≥ 1 .
Choose a totally isotropic subspace W ⊂ F p d W\subset\mathbb{F}_p^d W ⊂ F p d of dimension m m m , as in Section 2.1. The quadratic form induced by Q d Q_d Q d on W ⊥ / W W^\perp/W W ⊥ / W is nondegenerate and one-dimensional. Hence, for any e ∈ W ⊥ ∖ W e\in W^\perp\setminus W e ∈ W ⊥ ∖ W ,
κ : = Q d ( e ) ≠ 0. \kappa:=Q_d(e)\ne0. κ := Q d ( e ) = 0.
Since e ∉ W e\notin W e ∈ / W , the representation w + a e w+ae w + a e , with w ∈ W w\in W w ∈ W and a ∈ A a\in A a ∈ A , is unique. Therefore,
∣ E A ∣ = ∣ W ∣ ∣ A ∣ = p m ∣ A ∣ . \lvert E_A\rvert=\lvert W\rvert\lvert A\rvert=p^m\lvert A\rvert. ∣ E A ∣ = ∣ W ∣ ∣ A ∣ = p m ∣ A ∣ .
Moreover, for w , w ′ ∈ W w,w'\in W w , w ′ ∈ W and a , b ∈ A a,b\in A a , b ∈ A , the total isotropy of W W W and the fact that e ∈ W ⊥ e\in W^\perp e ∈ W ⊥ give
Q d ( w − w ′ ) = 0 , ( w − w ′ ) ⋅ e = 0. Q_d(w-w')=0,\qquad(w-w')\cdot e=0. Q d ( w − w ′ ) = 0 , ( w − w ′ ) ⋅ e = 0.
Consequently,
Q d ( ( w + a e ) − ( w ′ + b e ) ) = Q d ( w − w ′ ) + 2 ( a − b ) ( w − w ′ ) ⋅ e + ( a − b ) 2 Q d ( e ) = κ ( a − b ) 2 . \begin{aligned}
Q_d((w+ae)-(w'+be))&=Q_d(w-w')+2(a-b)(w-w')\cdot e\\
&\quad+(a-b)^2Q_d(e)\\
&=\kappa(a-b)^2.
\end{aligned} Q d (( w + a e ) − ( w ′ + b e )) = Q d ( w − w ′ ) + 2 ( a − b ) ( w − w ′ ) ⋅ e + ( a − b ) 2 Q d ( e ) = κ ( a − b ) 2 .
Thus, Δ ( E A ) ⊆ κ ( A − A ) 2 \Delta(E_A)\subseteq\kappa(A-A)^2 Δ ( E A ) ⊆ κ ( A − A ) 2 . The reverse inclusion follows by taking w = w ′ = 0 w=w'=0 w = w ′ = 0 . Hence, Δ ( E A ) = κ ( A − A ) 2 \Delta(E_A)=\kappa(A-A)^2 Δ ( E A ) = κ ( A − A ) 2 . This completes the proof. □
Proof of Proposition 2.1, Theorem 1.3, and Corollary 1.5
We now combine the two lemmas. The estimate M G P , 1 ( p ) ≤ ( p − 1 ) / 2 M_{\mathrm{GP},1}(p)\le(p-1)/2 M GP , 1 ( p ) ≤ ( p − 1 ) /2 allows us to absorb the dependence on ∣ E ∣ \lvert E\rvert ∣ E ∣ in the denominator of (2.3).
Proof of Proposition 2.1. If m = 0 m=0 m = 0 , then (2.1) follows directly from the definition of M G P , 1 ( p ) M_{\mathrm{GP},1}(p) M GP , 1 ( p ) . We henceforth assume that m ≥ 1 m\ge1 m ≥ 1 . We first note that
M G P , 1 ( p ) ≤ p − 1 2 . M_{\mathrm{GP},1}(p)\le\frac{p-1}{2}. M GP , 1 ( p ) ≤ 2 p − 1 .
Indeed, if A ⊂ F p A\subset\mathbb{F}_p A ⊂ F p has more than p / 2 p/2 p /2 elements, then A A A and u + A u+A u + A intersect for every u ∈ F p u\in\mathbb{F}_p u ∈ F p , so A − A = F p A-A=\mathbb{F}_p A − A = F p . Hence, ( A − A ) 2 (A-A)^2 ( A − A ) 2 contains all nonzero squares. The set of nonzero squares is a cyclic multiplicative subgroup of order ( p − 1 ) / 2 ≥ 3 (p-1)/2\ge3 ( p − 1 ) /2 ≥ 3 . Therefore, it contains a nondegenerate geometric progression.
Let E ⊂ F p 2 m + 1 E\subset\mathbb{F}_p^{2m+1} E ⊂ F p 2 m + 1 be nonempty and suppose that its distance set contains no nondegenerate geometric progression. By Lemma 2.2 and the invariance under nonzero scaling noted after Definition 1.1,
M G P , 1 ( p ) ≥ ∣ E ∣ p m ( 2 + ∣ E ∣ p m + 1 ) . M_{\mathrm{GP},1}(p)\ge\frac{\lvert E\rvert}{p^m\left(2+\frac{\lvert E\rvert}{p^{m+1}}\right)}. M GP , 1 ( p ) ≥ p m ( 2 + p m + 1 ∣ E ∣ ) ∣ E ∣ .
Multiplying through by the denominator and collecting the terms containing ∣ E ∣ \lvert E\rvert ∣ E ∣ , we obtain
∣ E ∣ ( 1 − M G P , 1 ( p ) p ) ≤ 2 p m M G P , 1 ( p ) . \lvert E\rvert\left(1-\frac{M_{\mathrm{GP},1}(p)}{p}\right)\le2p^mM_{\mathrm{GP},1}(p). ∣ E ∣ ( 1 − p M GP , 1 ( p ) ) ≤ 2 p m M GP , 1 ( p ) .
Since M G P , 1 ( p ) ≤ p − 1 2 M_{\mathrm{GP},1}(p) \le\frac{p-1}{2} M GP , 1 ( p ) ≤ 2 p − 1 , the factor on the left is greater than 1 2 \frac{1}{2} 2 1 . Hence, ∣ E ∣ ≤ 4 p m M G P , 1 ( p ) |E| \le4p^m M_{\mathrm{GP},1}(p) ∣ E ∣ ≤ 4 p m M GP , 1 ( p ) . This proves the upper bound in (2.1).
For the lower bound, choose A ⊂ F p A \subset\mathbb{F}_p A ⊂ F p with ∣ A ∣ = M G P , 1 ( p ) |A| = M_{\mathrm{GP},1}(p) ∣ A ∣ = M GP , 1 ( p ) such that ( A − A ) 2 (A-A)^2 ( A − A ) 2 contains no nondegenerate geometric progression. Lemma 2.3 constructs a set E A ⊂ F p 2 m + 1 E_A \subset\mathbb{F}_p^{2m+1} E A ⊂ F p 2 m + 1 satisfying ∣ E A ∣ = p m M G P , 1 ( p ) |E_A| = p^m M_{\mathrm{GP},1}(p) ∣ E A ∣ = p m M GP , 1 ( p ) and Δ ( E A ) = κ ( A − A ) 2 \Delta(E_A) = \kappa(A-A)^2 Δ ( E A ) = κ ( A − A ) 2 for some κ ≠ 0 \kappa\ne0 κ = 0 . Since multiplication by κ \kappa κ preserves nondegeneracy, Δ ( E A ) \Delta(E_A) Δ ( E A ) also contains no nondegenerate geometric progression. Consequently, M G P , 2 m + 1 ( p ) ≥ p m M G P , 1 ( p ) M_{\mathrm{GP},2m+1}(p) \ge p^m M_{\mathrm{GP},1}(p) M GP , 2 m + 1 ( p ) ≥ p m M GP , 1 ( p ) . This proves (2.1) and completes the proof.
The main theorem follows by applying the comparison to the two one-dimensional bounds.
Proof of Theorem 1.3. Proposition 1.4(i) gives an absolute constant C 1 C_1 C 1 such that M G P , 1 ( p ) ≤ C 1 p 16 25 M_{\mathrm{GP},1}(p) \le C_1p^{\frac{16}{25}} M GP , 1 ( p ) ≤ C 1 p 25 16 for every prime p ≥ 7 p \ge7 p ≥ 7 . Part (ii) gives an absolute p 0 ≥ 7 p_0 \ge7 p 0 ≥ 7 such that M G P , 1 ( p ) ≥ p 7 26 M_{\mathrm{GP},1}(p) \ge p^{\frac{7}{26}} M GP , 1 ( p ) ≥ p 26 7 for every prime p ≥ p 0 p \ge p_0 p ≥ p 0 . Hence, Proposition 2.1 yields
p m + 7 26 ≤ p m M G P , 1 ( p ) ≤ M G P , 2 m + 1 ( p ) ≤ 4 p m M G P , 1 ( p ) ≤ 4 C 1 p m + 16 25 . p^{m+\frac{7}{26}} \le p^m M_{\mathrm{GP},1}(p) \le M_{\mathrm{GP},2m+1}(p) \le4p^m M_{\mathrm{GP},1}(p) \le4C_1p^{m+\frac{16}{25}}. p m + 26 7 ≤ p m M GP , 1 ( p ) ≤ M GP , 2 m + 1 ( p ) ≤ 4 p m M GP , 1 ( p ) ≤ 4 C 1 p m + 25 16 .
Taking C = max { 1 , 4 C 1 } C = \max\{1,4C_1\} C = max { 1 , 4 C 1 } proves the theorem. Both C C C and p 0 p_0 p 0 are independent of m m m . This completes the proof.
Proof of Corollary 1.5. By Proposition 1.4(i), there exist u , v , w ∈ ( A − A ) ∖ { 0 } u,v,w \in(A-A)\setminus\{0\} u , v , w ∈ ( A − A ) ∖ { 0 } such that u 2 , v 2 , w 2 u^2,v^2,w^2 u 2 , v 2 , w 2 are pairwise distinct and form a geometric progression. Thus,
v 4 = u 2 w 2 , v^4 = u^2w^2, v 4 = u 2 w 2 ,
and hence
( v 2 − u w ) ( v 2 + u w ) = 0. (v^2-uw)(v^2+uw)=0. ( v 2 − u w ) ( v 2 + u w ) = 0.
Therefore, v 2 = u w v^2=uw v 2 = u w or v 2 = − u w v^2=-uw v 2 = − u w . Since A − A A-A A − A is symmetric, replacing w w w by − w -w − w if necessary, we may assume that v 2 = u w v^2=uw v 2 = u w .
Set x = u x=u x = u and r = v / u r=v/u r = v / u . Then x , r ∈ F p × x,r \in\mathbb{F}_p^\times x , r ∈ F p × and
x = u , x r = v , x r 2 = v 2 u = w . x=u,\qquad xr=v,\qquad xr^2=\frac{v^2}{u}=w. x = u , x r = v , x r 2 = u v 2 = w .
Thus, x , x r , x r 2 ∈ A − A x,xr,xr^2 \in A-A x , x r , x r 2 ∈ A − A . Moreover,
r 4 = v 4 u 4 = w 2 u 2 ≠ 1 , r^4=\frac{v^4}{u^4}=\frac{w^2}{u^2}\ne1, r 4 = u 4 v 4 = u 2 w 2 = 1 ,
since u 2 ≠ w 2 u^2\ne w^2 u 2 = w 2 . This completes the proof.
We prove the two parts of Proposition 1.4 in the next two sections.
Proof of Proposition 1.4(i)
The proof compares two bounds for the variance of the number of representations of a nonzero field element as a product of two differences from A A A . The absence of a progression makes this number small at every nonzero squared difference. We first show that there are many such squared differences and establish the injectivity estimate needed for the upper bound on the variance.
Consequences of the absence of a progression
The three conclusions of the next lemma have different roles. The bound for ∣ A ∣ |A| ∣ A ∣ controls the exceptional slopes in the variance estimate, the bound for ∣ A − A ∣ |A-A| ∣ A − A ∣ supplies many squared differences, and the bound for the number of solutions to b − t a = s b-ta=s b − t a = s controls the remaining slopes. All three follow from the injectivity of ( a , b , c ) ↦ ( b − t a , c − t b ) (a,b,c)\mapsto(b-ta,c-tb) ( a , b , c ) ↦ ( b − t a , c − t b ) when t ≠ 0 t\ne0 t = 0 and t 4 ≠ 1 t^4\ne1 t 4 = 1 .
Lemma 3.1. Let p ≥ 7 p\ge7 p ≥ 7 be a prime and let ∅ ≠ A ⊂ F p \varnothing\ne A\subset\mathbb{F}_p ∅ = A ⊂ F p . If ( A − A ) 2 (A-A)^2 ( A − A ) 2 contains no nondegenerate geometric progression, then
∣ A ∣ 3 ≤ p 2 , ∣ A − A ∣ ≥ ∣ A ∣ 5 4 . (8) |A|^3\le p^2,\qquad|A-A|\ge|A|^{\frac{5}{4}}. \tag*{(8)} ∣ A ∣ 3 ≤ p 2 , ∣ A − A ∣ ≥ ∣ A ∣ 4 5 . (8) Moreover, for t ≠ 0 t\ne0 t = 0 with t 4 ≠ 1 t^4\ne1 t 4 = 1 and every s ∈ F p s\in\mathbb{F}_p s ∈ F p ,
∣ { ( a , b ) ∈ A 2 : b − t a = s } ∣ ≤ p ∣ A ∣ . (9) \left|\{(a,b)\in A^2:b-ta=s\}\right|\le\frac{p}{|A|}. \tag*{(9)} {( a , b ) ∈ A 2 : b − t a = s } ≤ ∣ A ∣ p . (9)
Proof. Fix t ∈ F p × t\in\mathbb{F}_p^\times t ∈ F p × with t 4 ≠ 1 t^4\ne1 t 4 = 1 and consider the map
Φ t : A 3 ⟶ F p 2 , Φ t ( a , b , c ) = ( b − t a , c − t b ) . \Phi_t:A^3\longrightarrow\mathbb{F}_p^2,\qquad\Phi_t(a,b,c)=(b-ta,c-tb). Φ t : A 3 ⟶ F p 2 , Φ t ( a , b , c ) = ( b − t a , c − t b ) .
If two triples ( a , b , c ) (a,b,c) ( a , b , c ) and ( a ′ , b ′ , c ′ ) (a',b',c') ( a ′ , b ′ , c ′ ) have the same image, then
b − b ′ = t ( a − a ′ ) , c − c ′ = t ( b − b ′ ) . b-b'=t(a-a'),\qquad c-c'=t(b-b'). b − b ′ = t ( a − a ′ ) , c − c ′ = t ( b − b ′ ) .
If the triples are distinct, then a − a ′ ≠ 0 a-a'\ne0 a − a ′ = 0 , and these three differences are nonzero and have common ratio t t t . Their squares would form a nondegenerate geometric progression in ( A − A ) 2 (A-A)^2 ( A − A ) 2 , since t 4 ≠ 1 t^4\ne1 t 4 = 1 . Thus, Φ t \Phi_t Φ t is injective. Since 2 4 ≠ 1 2^4\ne1 2 4 = 1 for p ≥ 7 p\ge7 p ≥ 7 , taking t = 2 t=2 t = 2 yields ∣ A ∣ 3 ≤ p 2 |A|^3\le p^2 ∣ A ∣ 3 ≤ p 2 .
To obtain the lower bound for ∣ A − A ∣ |A-A| ∣ A − A ∣ , apply Plünnecke’s inequality [13 Theorem 1.1] to A A A and − A -A − A . This gives a nonempty set X ⊂ A X\subset A X ⊂ A such that
∣ X − A − A ∣ ≤ ( ∣ A − A ∣ ∣ A ∣ ) 2 ∣ X ∣ . |X-A-A|\le\left(\frac{|A-A|}{|A|}\right)^2|X|. ∣ X − A − A ∣ ≤ ( ∣ A ∣ ∣ A − A ∣ ) 2 ∣ X ∣.
For every ( a , b , c ) ∈ A × X × X (a,b,c)\in A\times X\times X ( a , b , c ) ∈ A × X × X , we have
b − 2 a = b − a − a ∈ X − A − A , c − 2 b = c − b − b ∈ X − A − A . b-2a=b-a-a\in X-A-A,\qquad c-2b=c-b-b\in X-A-A. b − 2 a = b − a − a ∈ X − A − A , c − 2 b = c − b − b ∈ X − A − A .
Since Φ 2 \Phi_2 Φ 2 is injective,
∣ A ∣ ∣ X ∣ 2 ≤ ∣ X − A − A ∣ 2 ≤ ( ∣ A − A ∣ ∣ A ∣ ) 4 ∣ X ∣ 2 . |A||X|^2\le|X-A-A|^2\le\left(\frac{|A-A|}{|A|}\right)^4|X|^2. ∣ A ∣∣ X ∣ 2 ≤ ∣ X − A − A ∣ 2 ≤ ( ∣ A ∣ ∣ A − A ∣ ) 4 ∣ X ∣ 2 .
Since X ≠ ∅ X\ne\varnothing X = ∅ , it follows that ∣ A − A ∣ ≥ ∣ A ∣ 5 4 |A-A|\ge|A|^{\frac{5}{4}} ∣ A − A ∣ ≥ ∣ A ∣ 4 5 .
Finally, for each s ∈ F p s\in\mathbb{F}_p s ∈ F p , the map Φ t \Phi_t Φ t sends { ( a , b , c ) ∈ A 3 : b − t a = s } \{(a,b,c)\in A^3:b-ta=s\} {( a , b , c ) ∈ A 3 : b − t a = s } injectively into { s } × F p \{s\}\times\mathbb{F}_p { s } × F p . Comparing cardinalities gives
∣ A ∣ ∣ { ( a , b ) ∈ A 2 : b − t a = s } ∣ ≤ p , |A|\left|\{(a,b)\in A^2:b-ta=s\}\right|\le p, ∣ A ∣ {( a , b ) ∈ A 2 : b − t a = s } ≤ p ,
which proves (3.2). This completes the proof.
The variance argument
For a nonempty set A ⊂ F p A \subset\mathbb{F}_p A ⊂ F p , let r A − A ( h ) = ∣ { ( a , b ) ∈ A 2 : a − b = h } ∣ r_{A-A}(h)=|\{(a,b)\in A^2:a-b=h\}| r A − A ( h ) = ∣ {( a , b ) ∈ A 2 : a − b = h } ∣ for h ∈ F p h\in\mathbb{F}_p h ∈ F p . Thus, r A − A ( h ) > 0 r_{A-A}(h)>0 r A − A ( h ) > 0 if and only if h ∈ A − A h\in A-A h ∈ A − A . To count products of nonzero differences with their multiplicities, define
F ( z ) : = ∑ x , y ∈ F p × x y = z r A − A ( x ) r A − A ( y ) ( z ∈ F p × ) . F(z):=\sum_{\substack{x,y\in\mathbb{F}_p^\times\\xy=z}}r_{A-A}(x)r_{A-A}(y)\quad(z\in\mathbb{F}_p^\times). F ( z ) := x , y ∈ F p × x y = z ∑ r A − A ( x ) r A − A ( y ) ( z ∈ F p × ) .
Its mean is
F ‾ : = 1 p − 1 ∑ z ∈ F p × F ( z ) = ∣ A ∣ 2 ( ∣ A ∣ − 1 ) 2 p − 1 . \overline{F}:=\frac{1}{p-1}\sum_{z\in\mathbb{F}_p^\times}F(z)=\frac{|A|^2(|A|-1)^2}{p-1}. F := p − 1 1 z ∈ F p × ∑ F ( z ) = p − 1 ∣ A ∣ 2 ( ∣ A ∣ − 1 ) 2 .
The formula for the mean follows from ∑ h ≠ 0 r A − A ( h ) = ∣ A ∣ ( ∣ A ∣ − 1 ) \sum_{h\ne0}r_{A-A}(h)=|A|(|A|-1) ∑ h = 0 r A − A ( h ) = ∣ A ∣ ( ∣ A ∣ − 1 ) .
Let h ∈ ( A − A ) ∖ { 0 } h\in(A-A)\setminus\{0\} h ∈ ( A − A ) ∖ { 0 } . If x , y ∈ F p × x,y\in\mathbb{F}_p^\times x , y ∈ F p × satisfy x y = h 2 xy=h^2 x y = h 2 and r A − A ( x ) r A − A ( y ) > 0 r_{A-A}(x)r_{A-A}(y)>0 r A − A ( x ) r A − A ( y ) > 0 , then x , y ∈ A − A x,y\in A-A x , y ∈ A − A . Consequently, x 2 , h 2 , y 2 ∈ ( A − A ) 2 x^2,h^2,y^2\in(A-A)^2 x 2 , h 2 , y 2 ∈ ( A − A ) 2 and
h 2 x 2 = y x = y 2 h 2 . \frac{h^2}{x^2}=\frac{y}{x}=\frac{y^2}{h^2}. x 2 h 2 = x y = h 2 y 2 .
Thus, these three values form a geometric progression, possibly degenerate. When no nondegenerate progression is present, only a bounded number of pairs ( x , y ) (x,y) ( x , y ) are possible. Thus, F ( h 2 ) F(h^2) F ( h 2 ) is small. For ∣ A ∣ > 6 p |A|>6\sqrt{p} ∣ A ∣ > 6 p , these values lie below half the mean and give the lower bound in the following lemma. The upper bound will follow from Lemma 3.1.
Lemma 3.2. Let p ≥ 7 p\ge7 p ≥ 7 be a prime and let ∅ ≠ A ⊂ F p \varnothing\ne A\subset\mathbb{F}_p ∅ = A ⊂ F p . Suppose that ( A − A ) 2 (A-A)^2 ( A − A ) 2 contains no nondegenerate geometric progression. Then
∑ z ∈ F p × ( F ( z ) − F ‾ ) 2 ≤ 5 p 2 ∣ A ∣ 3 . \sum_{z\in\mathbb{F}_p^\times}\left(F(z)-\overline{F}\right)^2\le5p^2|A|^3. z ∈ F p × ∑ ( F ( z ) − F ) 2 ≤ 5 p 2 ∣ A ∣ 3 . If ∣ A ∣ > 6 p |A|>6\sqrt{p} ∣ A ∣ > 6 p , then also
∑ z ∈ F p × ( F ( z ) − F ‾ ) 2 ≫ ( ∣ A − A ∣ − 1 ) ∣ A ∣ 8 p 2 , \sum_{z\in\mathbb{F}_p^\times}\left(F(z)-\overline{F}\right)^2\gg\frac{(|A-A|-1)|A|^8}{p^2}, z ∈ F p × ∑ ( F ( z ) − F ) 2 ≫ p 2 ( ∣ A − A ∣ − 1 ) ∣ A ∣ 8 , where the implied constant is absolute.
Proof of Lemma 3.2. We first bound the variance from above by counting pairs on lines of a fixed slope. We then obtain the lower bound from the small values of F F F at nonzero squared differences.
The equation x y = u v ≠ 0 xy=uv\ne0 x y = uv = 0 can be written as u = t x u=tx u = t x and y = t v y=tv y = t v for some t ≠ 0 t\ne0 t = 0 . This relates the second moment of F F F to the numbers of solutions of b − b ′ = t ( a − a ′ ) b-b'=t(a-a') b − b ′ = t ( a − a ′ ) . We count these solutions through the fibers of ( a , b ) ↦ b − t a (a,b)\mapsto b-ta ( a , b ) ↦ b − t a . For s , t ∈ F p s,t\in\mathbb{F}_p s , t ∈ F p , let
i t ( s ) = ∣ { ( a , b ) ∈ A 2 : b − t a = s } ∣ , V ( t ) = ∑ s ∈ F p ( i t ( s ) − ∣ A ∣ 2 p ) 2 . i_t(s)=|\{(a,b)\in A^2:b-ta=s\}|,\qquad V(t)=\sum_{s\in\mathbb{F}_p}\left(i_t(s)-\frac{|A|^2}{p}\right)^2. i t ( s ) = ∣ {( a , b ) ∈ A 2 : b − t a = s } ∣ , V ( t ) = s ∈ F p ∑ ( i t ( s ) − p ∣ A ∣ 2 ) 2 .
Since ∑ s ∈ F p i t ( s ) = ∣ A ∣ 2 \sum_{s\in\mathbb{F}_p}i_t(s)=|A|^2 ∑ s ∈ F p i t ( s ) = ∣ A ∣ 2 , expanding the square in V ( t ) V(t) V ( t ) reduces the calculation to counting solutions of b − b ′ = t ( a − a ′ ) b-b'=t(a-a') b − b ′ = t ( a − a ′ ) . When a ≠ a ′ a\ne a' a = a ′ , each choice of a , a ′ , b , b ′ a,a',b,b' a , a ′ , b , b ′ gives one value of t t t ; when a = a ′ a=a' a = a ′ , a solution requires b = b ′ b=b' b = b ′ and then all p p p values of t t t are allowed. Hence,
∑ t ∈ F p ∑ s ∈ F p i t ( s ) 2 = ( ∣ A ∣ 2 − ∣ A ∣ ) ∣ A ∣ 2 + p ∣ A ∣ 2 . \sum_{t\in\mathbb{F}_p}\sum_{s\in\mathbb{F}_p}i_t(s)^2=(|A|^2-|A|)|A|^2+p|A|^2. t ∈ F p ∑ s ∈ F p ∑ i t ( s ) 2 = ( ∣ A ∣ 2 − ∣ A ∣ ) ∣ A ∣ 2 + p ∣ A ∣ 2 .
Subtracting ∣ A ∣ 4 |A|^4 ∣ A ∣ 4 gives
V ( t ) = ∑ s ∈ F p i t ( s ) 2 − ∣ A ∣ 4 p ≥ 0 , ∑ t ∈ F p V ( t ) = p ∣ A ∣ 2 − ∣ A ∣ 3 ≤ p ∣ A ∣ 2 . (10) V(t)=\sum_{s\in\mathbb{F}_p}i_t(s)^2-\frac{|A|^4}{p}\geq0,\qquad\sum_{t\in\mathbb{F}_p}V(t)=p|A|^2-|A|^3\leq p|A|^2. \tag*{(10)} V ( t ) = s ∈ F p ∑ i t ( s ) 2 − p ∣ A ∣ 4 ≥ 0 , t ∈ F p ∑ V ( t ) = p ∣ A ∣ 2 − ∣ A ∣ 3 ≤ p ∣ A ∣ 2 . (10)
For t ≠ 0 t\ne0 t = 0 with t 4 ≠ 1 t^4\ne1 t 4 = 1 , (9) implies V ( t ) ≤ ∑ s ∈ F p i t ( s ) 2 ≤ p ∣ A ∣ V(t)\leq\sum_{s\in\mathbb{F}_p}i_t(s)^2\leq p|A| V ( t ) ≤ ∑ s ∈ F p i t ( s ) 2 ≤ p ∣ A ∣ . For the at most four values of t t t satisfying t 4 = 1 t^4=1 t 4 = 1 , we use V ( t ) ≤ ∑ s ∈ F p i t ( s ) 2 ≤ ∣ A ∣ 3 V(t)\leq\sum_{s\in\mathbb{F}_p}i_t(s)^2\leq|A|^3 V ( t ) ≤ ∑ s ∈ F p i t ( s ) 2 ≤ ∣ A ∣ 3 . For t ≠ 0 t\ne0 t = 0 with t 4 ≠ 1 t^4\ne1 t 4 = 1 , we have V ( t ) 2 ≤ p ∣ A ∣ V ( t ) V(t)^2\leq p|A|V(t) V ( t ) 2 ≤ p ∣ A ∣ V ( t ) . The values satisfying t 4 = 1 t^4=1 t 4 = 1 contribute at most 4 ∣ A ∣ 6 4|A|^6 4∣ A ∣ 6 . Thus, (10) and the bound ∣ A ∣ 3 ≤ p 2 |A|^3\leq p^2 ∣ A ∣ 3 ≤ p 2 from Lemma 3.1 yield
∑ t ∈ F p × V ( t ) 2 ≤ p 2 ∣ A ∣ 3 + 4 ∣ A ∣ 6 ≤ 5 p 2 ∣ A ∣ 3 . (11) \sum_{t\in\mathbb{F}_p^\times}V(t)^2\leq p^2|A|^3+4|A|^6\leq5p^2|A|^3. \tag*{(11)} t ∈ F p × ∑ V ( t ) 2 ≤ p 2 ∣ A ∣ 3 + 4∣ A ∣ 6 ≤ 5 p 2 ∣ A ∣ 3 . (11)
We now transfer this estimate to F F F . Grouping the weighted solutions of x y = u v ≠ 0 xy=uv\ne0 x y = uv = 0 by t = u x = y v t=\frac{u}{x}=\frac{y}{v} t = x u = v y gives
∑ z ∈ F p × F ( z ) 2 = ∑ t ∈ F p × ( ∑ h ∈ F p × r A − A ( h ) r A − A ( t h ) ) 2 . (12) \sum_{z\in\mathbb{F}_p^\times}F(z)^2=\sum_{t\in\mathbb{F}_p^\times}\left(\sum_{h\in\mathbb{F}_p^\times}r_{A-A}(h)r_{A-A}(th)\right)^2. \tag*{(12)} z ∈ F p × ∑ F ( z ) 2 = t ∈ F p × ∑ h ∈ F p × ∑ r A − A ( h ) r A − A ( t h ) 2 . (12)
Moreover, since multiplication by any h ≠ 0 h\ne0 h = 0 permutes F p × \mathbb{F}_p^\times F p × ,
∑ t ∈ F p × ∑ h ∈ F p × r A − A ( h ) r A − A ( t h ) = ( ∑ h ∈ F p × r A − A ( h ) ) 2 = ∣ A ∣ 2 ( ∣ A ∣ − 1 ) 2 = ∑ z ∈ F p × F ( z ) . \sum_{t\in\mathbb{F}_p^\times}\sum_{h\in\mathbb{F}_p^\times}r_{A-A}(h)r_{A-A}(th)=\left(\sum_{h\in\mathbb{F}_p^\times}r_{A-A}(h)\right)^2=|A|^2(|A|-1)^2=\sum_{z\in\mathbb{F}_p^\times}F(z). t ∈ F p × ∑ h ∈ F p × ∑ r A − A ( h ) r A − A ( t h ) = h ∈ F p × ∑ r A − A ( h ) 2 = ∣ A ∣ 2 ( ∣ A ∣ − 1 ) 2 = z ∈ F p × ∑ F ( z ) .
Thus, F F F and the function t ↦ ∑ h ∈ F p × r A − A ( h ) r A − A ( t h ) t\mapsto\sum_{h\in\mathbb{F}_p^\times}r_{A-A}(h)r_{A-A}(th) t ↦ ∑ h ∈ F p × r A − A ( h ) r A − A ( t h ) have the same mean F ‾ \overline{F} F and second moment.
For t ∈ F p × t\in\mathbb{F}_p^\times t ∈ F p × , the sum ∑ s ∈ F p i t ( s ) 2 \sum_{s\in\mathbb{F}_p}i_t(s)^2 ∑ s ∈ F p i t ( s ) 2 counts solutions of b − b ′ = t ( a − a ′ ) b-b'=t(a-a') b − b ′ = t ( a − a ′ ) in A 4 A^4 A 4 . Removing the ∣ A ∣ 2 |A|^2 ∣ A ∣ 2 solutions with a = a ′ a=a' a = a ′ gives
∑ h ∈ F p × r A − A ( h ) r A − A ( t h ) = ∑ s ∈ F p i t ( s ) 2 − ∣ A ∣ 2 = V ( t ) + ∣ A ∣ 4 p − ∣ A ∣ 2 . \sum_{h\in\mathbb{F}_p^\times}r_{A-A}(h)r_{A-A}(th)=\sum_{s\in\mathbb{F}_p}i_t(s)^2-|A|^2=V(t)+\frac{|A|^4}{p}-|A|^2. h ∈ F p × ∑ r A − A ( h ) r A − A ( t h ) = s ∈ F p ∑ i t ( s ) 2 − ∣ A ∣ 2 = V ( t ) + p ∣ A ∣ 4 − ∣ A ∣ 2 .
Combining this identity with (12) and the equality of the means, we obtain
∑ z ∈ F p × ( F ( z ) − F ‾ ) 2 = ∑ t ∈ F p × ( V ( t ) − 1 p − 1 ∑ u ∈ F p × V ( u ) ) 2 ≤ ∑ t ∈ F p × V ( t ) 2 ≤ 5 p 2 ∣ A ∣ 3 . (13) \begin{aligned}
\sum_{z\in\mathbb{F}_p^\times}(F(z)-\overline{F})^2=\sum_{t\in\mathbb{F}_p^\times}\left(V(t)-\frac{1}{p-1}\sum_{u\in\mathbb{F}_p^\times}V(u)\right)^2 \\
&\leq\sum_{t\in\mathbb{F}_p^\times}V(t)^2\leq5p^2|A|^3. \tag*{(13)}
\end{aligned} z ∈ F p × ∑ ( F ( z ) − F ) 2 = t ∈ F p × ∑ V ( t ) − p − 1 1 u ∈ F p × ∑ V ( u ) 2 ≤ t ∈ F p × ∑ V ( t ) 2 ≤ 5 p 2 ∣ A ∣ 3 . (13)
where the last inequality follows from (11) .
We now prove the lower bound. For h ∈ ( A − A ) ∖ { 0 } h\in(A-A)\setminus\{0\} h ∈ ( A − A ) ∖ { 0 } , each nonzero summand in F ( h 2 ) F(h^2) F ( h 2 ) corresponds to nonzero x , y ∈ A − A x,y\in A-A x , y ∈ A − A with x y = h 2 xy=h^2 x y = h 2 . The terms x 2 x^2 x 2 , h 2 h^2 h 2 , y 2 y^2 y 2 form a geometric progression with ratio h 2 x 2 \frac{h^2}{x^2} x 2 h 2 . This progression must be degenerate, so ( h 2 x 2 ) 2 = 1 \left(\frac{h^2}{x^2}\right)^2=1 ( x 2 h 2 ) 2 = 1 , or equivalently x 4 = h 4 x^4=h^4 x 4 = h 4 . There are at most four choices for x x x , each determining y y y . Since r A − A ≤ ∣ A ∣ r_{A-A}\leq|A| r A − A ≤ ∣ A ∣ , we obtain
F ( h 2 ) ≤ 4 ∣ A ∣ 2 . (14) F(h^2)\leq4|A|^2. \tag*{(14)} F ( h 2 ) ≤ 4∣ A ∣ 2 . (14)
Assume now that ∣ A ∣ > 6 p |A| > 6\sqrt{p} ∣ A ∣ > 6 p . Then
F ‾ = ∣ A ∣ 2 ( ∣ A ∣ − 1 ) 2 p − 1 ≥ ∣ A ∣ 4 4 p . \overline{F} = \frac{|A|^2(|A|-1)^2}{p-1} \ge\frac{|A|^4}{4p}. F = p − 1 ∣ A ∣ 2 ( ∣ A ∣ − 1 ) 2 ≥ 4 p ∣ A ∣ 4 .
Since ∣ A ∣ > 6 p |A| > 6\sqrt{p} ∣ A ∣ > 6 p , we also have F ‾ > 8 ∣ A ∣ 2 \overline{F} > 8|A|^2 F > 8∣ A ∣ 2 .
Since A − A A-A A − A is symmetric and p p p is odd, the squaring map is two-to-one on ( A − A ) ∖ { 0 } (A-A) \setminus\{0\} ( A − A ) ∖ { 0 } , so the set D = ( A − A ) 2 ∖ { 0 } D=(A-A)^2\setminus\{0\} D = ( A − A ) 2 ∖ { 0 } has cardinality ∣ D ∣ = ∣ A − A ∣ − 1 2 |D|=\frac{|A-A|-1}{2} ∣ D ∣ = 2 ∣ A − A ∣ − 1 . Moreover, (14) and the bound F ‾ ≥ 8 ∣ A ∣ 2 \overline{F}\ge8|A|^2 F ≥ 8∣ A ∣ 2 give F ( z ) ≤ 4 ∣ A ∣ 2 ≤ F ‾ 2 F(z)\le4|A|^2\le\frac{\overline{F}}{2} F ( z ) ≤ 4∣ A ∣ 2 ≤ 2 F for every z ∈ D z\in D z ∈ D . Therefore,
∑ z ∈ F p × ( F ( z ) − F ‾ ) 2 ≥ ∑ z ∈ D ( F ( z ) − F ‾ ) 2 ≥ ∣ D ∣ 4 F ‾ 2 = ∣ A − A ∣ − 1 8 F ‾ 2 ≫ ( ∣ A − A ∣ − 1 ) ∣ A ∣ 8 p 2 . (15) \sum_{z\in\mathbb{F}_p^\times}(F(z)-\overline{F})^2
\ge\sum_{z\in D}(F(z)-\overline{F})^2
\ge\frac{|D|}{4}\overline{F}^2
= \frac{|A-A|-1}{8}\overline{F}^2
\gg\frac{(|A-A|-1)|A|^8}{p^2}. \tag*{(15)} z ∈ F p × ∑ ( F ( z ) − F ) 2 ≥ z ∈ D ∑ ( F ( z ) − F ) 2 ≥ 4 ∣ D ∣ F 2 = 8 ∣ A − A ∣ − 1 F 2 ≫ p 2 ( ∣ A − A ∣ − 1 ) ∣ A ∣ 8 . (15)
This completes the proof.
We can now prove the upper bound. The next calculation explains the exponent 16 25 \frac{16}{25} 25 16 .
Proof of Proposition 1.4(i). Assume that ( A − A ) 2 (A-A)^2 ( A − A ) 2 contains no nondegenerate geometric progression. If ∣ A ∣ ≤ 6 p |A|\le6\sqrt{p} ∣ A ∣ ≤ 6 p , then the required bound ∣ A ∣ ≪ p 16 / 25 |A|\ll p^{16/25} ∣ A ∣ ≪ p 16/25 is immediate. Hence, we may assume ∣ A ∣ > 6 p |A|>6\sqrt{p} ∣ A ∣ > 6 p . Comparing the two estimates in Lemma 3.2, we obtain
( ∣ A − A ∣ − 1 ) ∣ A ∣ 5 ≪ p 4 . (|A-A|-1)|A|^5\ll p^4. ( ∣ A − A ∣ − 1 ) ∣ A ∣ 5 ≪ p 4 .
Since (8) and ∣ A ∣ > 6 p |A|>6\sqrt{p} ∣ A ∣ > 6 p imply ∣ A − A ∣ − 1 ≫ ∣ A ∣ 5 / 4 |A-A|-1\gg|A|^{5/4} ∣ A − A ∣ − 1 ≫ ∣ A ∣ 5/4 , it follows that
∣ A ∣ 25 / 4 ≪ p 4 , so ∣ A ∣ ≪ p 16 / 25 . |A|^{25/4}\ll p^4,\qquad\text{so}\qquad|A|\ll p^{16/25}. ∣ A ∣ 25/4 ≪ p 4 , so ∣ A ∣ ≪ p 16/25 .
Choosing the constant in Proposition 1.4(i) sufficiently large proves the assertion. This completes the proof.
Proof of Proposition 1.4(ii)
In this section, we construct a large family of integer vectors, project it to F p \mathbb{F}_p F p , and delete points to remove the relations that would produce a nondegenerate geometric progression.
Random projection and deletion
To construct the set in Proposition 1.4(ii), we must control relations among all differences of A A A . The following criterion allows us to work before squaring those differences.
For κ ∈ F p × \kappa\in\mathbb{F}_p^\times κ ∈ F p × , the set κ ( A − A ) 2 \kappa(A-A)^2 κ ( A − A ) 2 contains a nondegenerate geometric progression if and only if there exist u , v , w ∈ ( A − A ) ∖ { 0 } u,v,w\in(A-A)\setminus\{0\} u , v , w ∈ ( A − A ) ∖ { 0 } with
v 2 = u w , u 4 ≠ v 4 . (16) v^2=uw,\qquad u^4\ne v^4. \tag*{(16)} v 2 = u w , u 4 = v 4 . (16)
Indeed, if v 2 = u w v^2=uw v 2 = u w , then v 4 = u 2 w 2 v^4=u^2w^2 v 4 = u 2 w 2 , so κ u 2 \kappa u^2 κ u 2 , κ v 2 \kappa v^2 κ v 2 , κ w 2 \kappa w^2 κ w 2 form a geometric progression with common ratio v 2 / u 2 v^2/u^2 v 2 / u 2 . All three terms are nonzero, and u 4 ≠ v 4 u^4\ne v^4 u 4 = v 4 says exactly that the square of this ratio is not one. Conversely, a nondegenerate progression κ u 2 \kappa u^2 κ u 2 , κ v 2 \kappa v^2 κ v 2 , κ w 2 \kappa w^2 κ w 2 satisfies v 4 = u 2 w 2 v^4=u^2w^2 v 4 = u 2 w 2 and u 4 ≠ v 4 u^4\ne v^4 u 4 = v 4 . Since p p p is odd, v 2 = u w v^2=uw v 2 = u w or v 2 = − u w v^2=-uw v 2 = − u w . In the second case, replace w w w with − w -w − w ; this is allowed because A − A A-A A − A is symmetric, and it leaves w 2 w^2 w 2 unchanged. Thus, (16) holds.
We begin with a family of integer vectors in { 0 , 1 , 2 , 3 } L \{0,1,2,3\}^L { 0 , 1 , 2 , 3 } L and project it linearly to F p \mathbb{F}_p F p . A collision in the projection or an unwanted quadratic relation can be removed by deleting points so that one of its differences no longer occurs.
Lemma 4.1. Let L ≥ 1 L\ge1 L ≥ 1 and C ⊆ { 0 , 1 , 2 , 3 } L C\subseteq\{0,1,2,3\}^L C ⊆ { 0 , 1 , 2 , 3 } L . With differences and intersections taken in Z L \mathbb{Z}^L Z L , let
D : = C − C , r C − C ( u ) : = ∣ C ∩ ( C + u ) ∣ , J ( C ) : = ∑ u ∈ D r C − C ( u ) 1 / 3 . D:=C-C,\qquad r_{C-C}(\mathbf{u}):=\lvert C\cap(C+\mathbf{u})\rvert,\qquad J(C):=\sum_{\mathbf{u}\in D}r_{C-C}(\mathbf{u})^{1/3}. D := C − C , r C − C ( u ) := ∣ C ∩ ( C + u )∣ , J ( C ) := u ∈ D ∑ r C − C ( u ) 1/3 . For every prime p > 18 p>18 p > 18 , there exists A ⊂ F p A\subset\mathbb{F}_p A ⊂ F p such that ( A − A ) 2 (A-A)^2 ( A − A ) 2 contains no nondegenerate geometric progression and
∣ A ∣ ≥ ∣ C ∣ − ∣ C ∣ 2 p − 2 J ( C ) 3 p . (17) \lvert A\rvert\ge\lvert C\rvert-\frac{\lvert C\rvert^2}{p}-\frac{2J(C)^3}{p}. \tag*{(17)} ∣ A ∣ ≥ ∣ C ∣ − p ∣ C ∣ 2 − p 2 J ( C ) 3 . (17)
Proof. We seek a projection that becomes injective after a controlled number of deletions and creates no nondegenerate progression among the squared differences. For α = ( α 1 , … , α L ) ∈ F p L \boldsymbol{\alpha}=(\alpha_1,\ldots,\alpha_L)\in\mathbb{F}_p^L α = ( α 1 , … , α L ) ∈ F p L , define
ϕ α : Z L ⟶ F p , \phi_{\boldsymbol{\alpha}}:\mathbb{Z}^L\longrightarrow\mathbb{F}_p, ϕ α : Z L ⟶ F p ,
c = ( c 1 , … , c L ) ⟼ ∑ i = 1 L c i ‾ α i , \mathbf{c}=(c_1,\ldots,c_L)\longmapsto\sum_{i=1}^{L}\overline{c_i}\alpha_i, c = ( c 1 , … , c L ) ⟼ i = 1 ∑ L c i α i ,
where c i ‾ ∈ F p \overline{c_i}\in\mathbb{F}_p c i ∈ F p is the residue class of the integer c i c_i c i modulo p p p . Thus, we first reduce the coordinates modulo p p p and then take their dot product with α \boldsymbol{\alpha} α in F p L \mathbb{F}_p^L F p L . We use this map on C C C and on its difference set D D D .
It suffices to find a choice of α \boldsymbol{\alpha} α for which we can delete at most
∣ C ∣ 2 p + 2 J ( C ) 3 p \frac{\lvert C\rvert^2}{p}+\frac{2J(C)^3}{p} p ∣ C ∣ 2 + p 2 J ( C ) 3
points from C C C and satisfy two requirements. First, ϕ α \phi_{\boldsymbol{\alpha}} ϕ α must be injective on the remaining set. Second, every three nonzero differences δ 1 , δ 2 , δ 3 \delta_1,\delta_2,\delta_3 δ 1 , δ 2 , δ 3 of its image must satisfy
δ 2 2 = δ 1 δ 3 ⟹ δ 1 4 = δ 2 4 . \delta_2^2=\delta_1\delta_3\quad\Longrightarrow\quad\delta_1^4=\delta_2^4. δ 2 2 = δ 1 δ 3 ⟹ δ 1 4 = δ 2 4 .
By (16) , the the second requirement excludes nondegenerate geometric progressions among the squared differences of that image. Injectivity and the deletion bound give (17) , so the image will be the required set A A A .
We first identify the quadratic relations that can be left untreated by the deletion rule.
Write X = ( X 1 , … , X L ) X=(X_1,\ldots,X_L) X = ( X 1 , … , X L ) for the tuple of indeterminates. For each ordered triple τ = ( u , v , w ) ∈ ( D ∖ { 0 } ) 3 \tau=(\mathbf{u},\mathbf{v},\mathbf{w})\in(D\setminus\{0\})^3 τ = ( u , v , w ) ∈ ( D ∖ { 0 } ) 3 , define
P τ ( X ) = ( v ⋅ X ) 2 − ( u ⋅ X ) ( w ⋅ X ) in F p [ X 1 , … , X L ] . P_\tau(X)=(\mathbf{v}\cdot X)^2-(\mathbf{u}\cdot X)(\mathbf{w}\cdot X)\quad\text{in }\mathbb{F}_p[X_1,\ldots,X_L]. P τ ( X ) = ( v ⋅ X ) 2 − ( u ⋅ X ) ( w ⋅ X ) in F p [ X 1 , … , X L ] .
In this polynomial, integer coordinates are reduced modulo p p p when used as coefficients. We claim that if P τ ≡ 0 P_\tau\equiv0 P τ ≡ 0 , then every projection satisfies
ϕ α ( u ) 2 = ϕ α ( v ) 2 = ϕ α ( w ) 2 . \phi_\alpha(\mathbf{u})^2=\phi_\alpha(\mathbf{v})^2=\phi_\alpha(\mathbf{w})^2. ϕ α ( u ) 2 = ϕ α ( v ) 2 = ϕ α ( w ) 2 .
Such an identity cannot yield the nondegenerate relation in (16) .
Suppose that P τ ≡ 0 P_\tau\equiv0 P τ ≡ 0 . Each of the three linear forms is nonzero: its coefficient vector is a nonzero element of { − 3 , … , 3 } L \{-3,\ldots,3\}^{L} { − 3 , … , 3 } L and p > 18 p>18 p > 18 . The identity ( v ⋅ X ) 2 = ( u ⋅ X ) ( w ⋅ X ) (\mathbf{v}\cdot\mathbf{X})^2=(\mathbf{u}\cdot\mathbf{X})(\mathbf{w}\cdot\mathbf{X}) ( v ⋅ X ) 2 = ( u ⋅ X ) ( w ⋅ X ) and unique factorization in F p [ X 1 , … , X L ] \mathbb{F}_p[X_1,\ldots,X_L] F p [ X 1 , … , X L ] force u ⋅ X \mathbf{u}\cdot\mathbf{X} u ⋅ X and w ⋅ X \mathbf{w}\cdot\mathbf{X} w ⋅ X to be scalar multiples of v ⋅ X \mathbf{v}\cdot\mathbf{X} v ⋅ X . We lift this proportionality to Q \mathbb{Q} Q to use the integer digit bounds. Every 2 × 2 2\times2 2 × 2 minor formed from their coefficient vectors vanishes modulo p p p . For example,
u i v j − u j v i ≡ 0 ( m o d p ) , ∣ u i v j − u j v i ∣ ≤ 3 ⋅ 3 + 3 ⋅ 3 = 18 < p . u_i v_j-u_j v_i\equiv0\pmod{p},\qquad\lvert u_i v_j-u_j v_i\rvert\leq3\cdot3+3\cdot3=18<p. u i v j − u j v i ≡ 0 ( mod p ) , ∣ u i v j − u j v i ∣ ≤ 3 ⋅ 3 + 3 ⋅ 3 = 18 < p .
The same bound holds for the minors formed from any two of the three vectors. Each minor is divisible by p p p and has absolute value less than p p p , so it vanishes over Z \mathbb{Z} Z . Thus, the vectors are proportional over Q \mathbb{Q} Q , so we may write
u = λ 1 h , v = λ 2 h , w = λ 3 h , \mathbf{u}=\lambda_1\mathbf{h},\qquad\mathbf{v}=\lambda_2\mathbf{h},\qquad\mathbf{w}=\lambda_3\mathbf{h}, u = λ 1 h , v = λ 2 h , w = λ 3 h ,
where h \mathbf{h} h is a primitive integer vector and λ 1 , λ 2 , λ 3 \lambda_1,\lambda_2,\lambda_3 λ 1 , λ 2 , λ 3 are nonzero integers. Primitivity means gcd ( h 1 , … , h L ) = 1 \gcd(h_1,\ldots,h_L)=1 g cd( h 1 , … , h L ) = 1 , so every integer vector on the rational line Q h \mathbb{Q}\mathbf{h} Q h is an integer multiple of h \mathbf{h} h . The coordinate bounds give ∣ λ j ∣ ≤ 3 \lvert\lambda_j\rvert\leq3 ∣ λ j ∣ ≤ 3 , since ∣ λ j ∣ ≤ ∣ λ j h i ∣ ≤ 3 \lvert\lambda_j\rvert\leq\lvert\lambda_jh_i\rvert\leq3 ∣ λ j ∣ ≤ ∣ λ j h i ∣ ≤ 3 for any coordinate with h i ≠ 0 h_i\neq0 h i = 0 . Since h \mathbf{h} h is primitive, it is nonzero modulo p p p , so h ⋅ X \mathbf{h}\cdot\mathbf{X} h ⋅ X is a nonzero polynomial. Substitution into P τ ≡ 0 P_\tau\equiv0 P τ ≡ 0 gives
( λ 2 2 − λ 1 λ 3 ) ( h ⋅ X ) 2 ≡ 0 in F p [ X 1 , … , X L ] , (\lambda_2^2-\lambda_1\lambda_3)(\mathbf{h}\cdot\mathbf{X})^2\equiv0\text{ in }\mathbb{F}_p[X_1,\ldots,X_L], ( λ 2 2 − λ 1 λ 3 ) ( h ⋅ X ) 2 ≡ 0 in F p [ X 1 , … , X L ] ,
and hence
λ 2 2 ≡ λ 1 λ 3 ( m o d p ) . \lambda_2^2\equiv\lambda_1\lambda_3\pmod{p}. λ 2 2 ≡ λ 1 λ 3 ( mod p ) .
Together with ∣ λ 2 2 − λ 1 λ 3 ∣ ≤ 18 < p \lvert\lambda_2^2-\lambda_1\lambda_3\rvert\leq18<p ∣ λ 2 2 − λ 1 λ 3 ∣ ≤ 18 < p , this gives the integer equality λ 2 2 = λ 1 λ 3 \lambda_2^2=\lambda_1\lambda_3 λ 2 2 = λ 1 λ 3 . Because λ 2 2 ∈ { 1 , 4 , 9 } \lambda_2^2\in\{1,4,9\} λ 2 2 ∈ { 1 , 4 , 9 } and λ 1 λ 3 = λ 2 2 \lambda_1\lambda_3=\lambda_2^2 λ 1 λ 3 = λ 2 2 , the restrictions 1 ≤ ∣ λ j ∣ ≤ 3 1\leq\lvert\lambda_j\rvert\leq3 1 ≤ ∣ λ j ∣ ≤ 3 force ∣ λ 1 ∣ = ∣ λ 2 ∣ = ∣ λ 3 ∣ \lvert\lambda_1\rvert=\lvert\lambda_2\rvert=\lvert\lambda_3\rvert ∣ λ 1 ∣ = ∣ λ 2 ∣ = ∣ λ 3 ∣ . For any projection, write δ 1 = ϕ α ( u ) \delta_1=\phi_\alpha(\mathbf{u}) δ 1 = ϕ α ( u ) , δ 2 = ϕ α ( v ) \delta_2=\phi_\alpha(\mathbf{v}) δ 2 = ϕ α ( v ) , and δ 3 = ϕ α ( w ) \delta_3=\phi_\alpha(\mathbf{w}) δ 3 = ϕ α ( w ) . Linearity gives
δ j = λ j ϕ α ( h ) in F p ( j = 1 , 2 , 3 ) . \delta_j=\lambda_j\phi_\alpha(\mathbf{h})\text{ in }\mathbb{F}_p\qquad(j=1,2,3). δ j = λ j ϕ α ( h ) in F p ( j = 1 , 2 , 3 ) .
Thus, δ 1 2 = δ 2 2 = δ 3 2 \delta_1^2=\delta_2^2=\delta_3^2 δ 1 2 = δ 2 2 = δ 3 2 , proving the claim.
We now choose α ∈ F p L \alpha\in\mathbb{F}_p^L α ∈ F p L uniformly and define the deletions. For each u ∈ D \mathbf{u}\in\mathcal{D} u ∈ D , set
R u = C ∩ ( C + u ) . R_{\mathbf{u}}=\mathcal{C}\cap(\mathcal{C}+\mathbf{u}). R u = C ∩ ( C + u ) .
We have ∣ R u ∣ = r C − C ( u ) \lvert R_{\mathbf{u}}\rvert=r_{\mathcal{C}-\mathcal{C}}(\mathbf{u}) ∣ R u ∣ = r C − C ( u ) . Whenever x , y ∈ C \mathbf{x},\mathbf{y}\in\mathcal{C} x , y ∈ C satisfy x − y = u \mathbf{x}-\mathbf{y}=\mathbf{u} x − y = u , we have x ∈ R u \mathbf{x}\in R_{\mathbf{u}} x ∈ R u , so deleting R u R_{\mathbf{u}} R u leaves no pair with difference u \mathbf{u} u .
For each τ = ( u , v , w ) ∈ ( D ∖ { 0 } ) 3 \tau=(\mathbf{u},\mathbf{v},\mathbf{w})\in(\mathcal{D}\setminus\{\mathbf{0}\})^3 τ = ( u , v , w ) ∈ ( D ∖ { 0 } ) 3 , let d ( τ ) \mathbf{d}(\tau) d ( τ ) be the first entry of τ \tau τ with the smallest difference multiplicity. For a choice of α \alpha α , define the surviving set C ′ ⊆ C \mathcal{C}'\subseteq\mathcal{C} C ′ ⊆ C by deleting R u R_{\mathbf{u}} R u whenever u ∈ D ∖ { 0 } \mathbf{u}\in\mathcal{D}\setminus\{\mathbf{0}\} u ∈ D ∖ { 0 } and ϕ α ( u ) = 0 \phi_\alpha(\mathbf{u})=0 ϕ α ( u ) = 0 , and deleting R d ( τ ) R_{\mathbf{d}(\tau)} R d ( τ ) whenever P τ ≢ 0 P_\tau\not\equiv0 P τ ≡ 0 and P τ ( α ) = 0 P_\tau(\alpha)=0 P τ ( α ) = 0 .
We next estimate the expected number of deleted points. Every nonzero u ∈ D \mathbf{u}\in\mathcal{D} u ∈ D remains nonzero modulo p p p , since its coordinates have absolute value at most 3 3 3 and p > 18 p>18 p > 18 . Hence, ϕ α ( u ) = 0 \phi_\alpha(\mathbf{u})=0 ϕ α ( u ) = 0 with probability 1 / p 1/p 1/ p . If P τ ≠ 0 P_\tau\ne0 P τ = 0 , the degree bound for polynomial zeros applies with total degree two, giving at most 2 p L − 1 2p^{L-1} 2 p L − 1 zeros in F p L \mathbb{F}_p^L F p L . Thus, P τ ( α ) = 0 P_\tau(\alpha)=0 P τ ( α ) = 0 with probability at most 2 / p 2/p 2/ p . The number of deleted points is at most the sum of the cardinalities of the deleted sets, even when these sets overlap. By linearity of expectation, its expected value is therefore at most
1 p ∑ u ∈ D ∖ { 0 } r C − C ( u ) + 2 p ∑ τ ∈ ( D ∖ { 0 } ) 3 P τ ≠ 0 r C − C ( d ( τ ) ) . \frac{1}{p}\sum_{\mathbf{u}\in D\setminus\{\mathbf{0}\}}r_{C-C}(\mathbf{u})+\frac{2}{p}\sum_{\substack{\tau\in(D\setminus\{\mathbf{0}\})^3\\P_\tau\ne0}}r_{C-C}(\mathbf{d}(\tau)). p 1 u ∈ D ∖ { 0 } ∑ r C − C ( u ) + p 2 τ ∈ ( D ∖ { 0 } ) 3 P τ = 0 ∑ r C − C ( d ( τ )) .
For τ = ( u , v , w ) \tau=(\mathbf{u},\mathbf{v},\mathbf{w}) τ = ( u , v , w ) , we have
r C − C ( d ( τ ) ) = min { r C − C ( u ) , r C − C ( v ) , r C − C ( w ) } ≤ ( r C − C ( u ) r C − C ( v ) r C − C ( w ) ) 1 3 . \begin{aligned}
r_{C-C}(\mathbf{d}(\tau))=\min\{r_{C-C}(\mathbf{u}),r_{C-C}(\mathbf{v}),r_{C-C}(\mathbf{w})\} \\
&\leq\left(r_{C-C}(\mathbf{u})r_{C-C}(\mathbf{v})r_{C-C}(\mathbf{w})\right)^{\frac{1}{3}}.
\end{aligned} r C − C ( d ( τ )) = min { r C − C ( u ) , r C − C ( v ) , r C − C ( w )} ≤ ( r C − C ( u ) r C − C ( v ) r C − C ( w ) ) 3 1 .
The identity ∑ u ∈ D ∖ { 0 } r C − C ( u ) = ∣ C ∣ 2 − ∣ C ∣ \sum_{\mathbf{u}\in D\setminus\{\mathbf{0}\}}r_{C-C}(\mathbf{u})=|C|^2-|C| ∑ u ∈ D ∖ { 0 } r C − C ( u ) = ∣ C ∣ 2 − ∣ C ∣ counts all ordered pairs of distinct points. Using this identity and enlarging the triple sum to D 3 D^3 D 3 , we bound the expected number of deletions by
∣ C ∣ 2 − ∣ C ∣ p + 2 p ( ∑ u ∈ D r C − C ( u ) 1 3 ) 3 = ∣ C ∣ 2 − ∣ C ∣ + 2 J ( C ) 3 p . \frac{|C|^2-|C|}{p}+\frac{2}{p}\left(\sum_{\mathbf{u}\in D}r_{C-C}(\mathbf{u})^{\frac{1}{3}}\right)^3=\frac{|C|^2-|C|+2J(C)^3}{p}. p ∣ C ∣ 2 − ∣ C ∣ + p 2 ( u ∈ D ∑ r C − C ( u ) 3 1 ) 3 = p ∣ C ∣ 2 − ∣ C ∣ + 2 J ( C ) 3 .
Fix a choice of α \alpha α for which the number of deleted points does not exceed this bound, and set A = ϕ α ( C ′ ) A=\phi_\alpha(C') A = ϕ α ( C ′ ) . The restriction of ϕ α \phi_\alpha ϕ α to C ′ C' C ′ is injective: if distinct x , y ∈ C ′ \mathbf{x},\mathbf{y}\in C' x , y ∈ C ′ had the same image, then u = x − y \mathbf{u}=\mathbf{x}-\mathbf{y} u = x − y would satisfy u ≠ 0 \mathbf{u}\ne\mathbf{0} u = 0 and ϕ α ( u ) = 0 \phi_\alpha(\mathbf{u})=0 ϕ α ( u ) = 0 , so x ∈ R u \mathbf{x}\in R_{\mathbf{u}} x ∈ R u would have been deleted. Consequently, ∣ A ∣ = ∣ C ′ ∣ |A|=|C'| ∣ A ∣ = ∣ C ′ ∣ . The deletion bound above is at most ∣ C ∣ 2 + 2 J ( C ) 3 p \frac{|C|^2+2J(C)^3}{p} p ∣ C ∣ 2 + 2 J ( C ) 3 , so it proves (4.2).
It remains to show that ( A − A ) 2 (A-A)^2 ( A − A ) 2 contains no nondegenerate geometric progression. Suppose that nonzero differences δ 1 , δ 2 , δ 3 ∈ A − A \delta_1,\delta_2,\delta_3\in A-A δ 1 , δ 2 , δ 3 ∈ A − A satisfy δ 2 2 = δ 1 δ 3 \delta_2^2=\delta_1\delta_3 δ 2 2 = δ 1 δ 3 . Choose nonzero vectors u , v , w ∈ C ′ − C ′ \mathbf{u},\mathbf{v},\mathbf{w}\in C'-C' u , v , w ∈ C ′ − C ′ whose images under ϕ α \phi_\alpha ϕ α are δ 1 , δ 2 , δ 3 \delta_1,\delta_2,\delta_3 δ 1 , δ 2 , δ 3 , respectively. For τ = ( u , v , w ) \tau=(\mathbf{u},\mathbf{v},\mathbf{w}) τ = ( u , v , w ) , we then have P τ ( α ) = 0 P_\tau(\alpha)=0 P τ ( α ) = 0 . If P τ ≠ 0 P_\tau\ne0 P τ = 0 , the set R d ( τ ) R_{\mathbf{d}(\tau)} R d ( τ ) would have been deleted, contradicting d ( τ ) ∈ C ′ − C ′ \mathbf{d}(\tau)\in C'-C' d ( τ ) ∈ C ′ − C ′ . Therefore, P τ = 0 P_\tau=0 P τ = 0 , and the claim proved above gives δ 1 2 = δ 2 2 = δ 3 2 \delta_1^2=\delta_2^2=\delta_3^2 δ 1 2 = δ 2 2 = δ 3 2 . In particular, δ 1 4 = δ 2 4 \delta_1^4=\delta_2^4 δ 1 4 = δ 2 4 . By (4.1), ( A − A ) 2 (A-A)^2 ( A − A ) 2 contains no nondegenerate geometric progression. This completes the proof. □
The choice of the four digits 0 , 1 , 2 , 3 0,1,2,3 0 , 1 , 2 , 3 ensures that the polynomial identities left untreated by our deletion rule produce only degenerate progressions. This property fails for five consecutive digits. Indeed, the difference set of { 0 , 1 , 2 , 3 , 4 } L \{0,1,2,3,4\}^L { 0 , 1 , 2 , 3 , 4 } L contains h , 2 h , 4 h \mathbf{h},2\mathbf{h},4\mathbf{h} h , 2 h , 4 h , where h \mathbf{h} h is a coordinate vector, and
( 2 h ⋅ X ) 2 − ( h ⋅ X ) ( 4 h ⋅ X ) = 0. (2\mathbf{h}\cdot\mathbf{X})^2-(\mathbf{h}\cdot\mathbf{X})(4\mathbf{h}\cdot\mathbf{X})=0. ( 2 h ⋅ X ) 2 − ( h ⋅ X ) ( 4 h ⋅ X ) = 0.
For any projection with t = ϕ α ( h ) ≠ 0 t=\phi_\alpha(\mathbf{h})\ne0 t = ϕ α ( h ) = 0 , these differences give the squared values t 2 , 4 t 2 , 16 t 2 t^2,4t^2,16t^2 t 2 , 4 t 2 , 16 t 2 , which form a nondegenerate geometric progression when p > 18 p>18 p > 18 . Since the displayed polynomial is identically zero, it vanishes with probability one, and the 2 / p 2/p 2/ p bound for nonzero polynomials does not apply. Thus, extending this construction to five consecutive digits would require an additional argument to handle such identities.
A family with prescribed digit counts
To apply Lemma 4.1, we need a large family C C C for which J ( C ) 3 J(C)^3 J ( C ) 3 is small compared with p ∣ C ∣ p|C| p ∣ C ∣ . We prescribe the digit counts so that the product of the digit weights is constant on the family. We then bound the weighted pair sums by the corresponding sums over the full cube, which factor over the coordinates and give the required estimate for J ( C ) J(C) J ( C ) .
Proof of Proposition 1.4(ii). Let p p p be a sufficiently large prime. To prove the bound ∣ A ∣ ≥ p 7 / 26 |A| \ge p^{7/26} ∣ A ∣ ≥ p 7/26 , we will apply Lemma 4.1. For a family C ⊆ { 0 , 1 , 2 , 3 } L \mathcal{C} \subseteq\{0,1,2,3\}^{L} C ⊆ { 0 , 1 , 2 , 3 } L , this lemma gives a set A ⊆ F p A \subseteq\mathbb{F}_p A ⊆ F p such that ( A − A ) 2 (A-A)^2 ( A − A ) 2 contains no nondegenerate geometric progression and
∣ A ∣ ≥ ∣ C ∣ − ∣ C ∣ 2 p − 2 J ( C ) 3 p . |A| \ge|\mathcal{C}|-\frac{|\mathcal{C}|^2}{p}-\frac{2J(\mathcal{C})^3}{p}. ∣ A ∣ ≥ ∣ C ∣ − p ∣ C ∣ 2 − p 2 J ( C ) 3 .
Let L L L be a positive multiple of 26, to be chosen below. For x ∈ { 0 , 1 , 2 , 3 } L \mathbf{x} \in\{0,1,2,3\}^{L} x ∈ { 0 , 1 , 2 , 3 } L , write N j ( x ) = ∣ { i : x i = j } ∣ N_j(\mathbf{x})=|\{i:x_i=j\}| N j ( x ) = ∣ { i : x i = j } ∣ for j = 0 , 1 , 2 , 3 j=0,1,2,3 j = 0 , 1 , 2 , 3 , and set
C L = { x ∈ { 0 , 1 , 2 , 3 } L : ( N 0 ( x ) , N 1 ( x ) , N 2 ( x ) , N 3 ( x ) ) = L 26 ( 5 , 8 , 8 , 5 ) } . (18) \mathcal{C}_L=\left\{\mathbf{x}\in\{0,1,2,3\}^{L}:(N_0(\mathbf{x}),N_1(\mathbf{x}),N_2(\mathbf{x}),N_3(\mathbf{x}))=\frac{L}{26}(5,8,8,5)\right\}. \tag*{(18)} C L = { x ∈ { 0 , 1 , 2 , 3 } L : ( N 0 ( x ) , N 1 ( x ) , N 2 ( x ) , N 3 ( x )) = 26 L ( 5 , 8 , 8 , 5 ) } . (18)
We will apply the lemma with C = C L \mathcal{C}=\mathcal{C}_L C = C L and choose L L L so that
∣ A ∣ ≥ 1 2 ∣ C L ∣ , 1 2 ∣ C L ∣ ≥ p 7 / 26 . (19) |A|\ge\frac{1}{2}|\mathcal{C}_L|,\qquad\frac{1}{2}|\mathcal{C}_L|\ge p^{7/26}. \tag*{(19)} ∣ A ∣ ≥ 2 1 ∣ C L ∣ , 2 1 ∣ C L ∣ ≥ p 7/26 . (19)
For the first inequality, it suffices to prove
∣ C L ∣ 2 p + 2 J ( C L ) 3 p ≤ 1 2 ∣ C L ∣ . \frac{|\mathcal{C}_L|^2}{p}+\frac{2J(\mathcal{C}_L)^3}{p}\le\frac{1}{2}|\mathcal{C}_L|. p ∣ C L ∣ 2 + p 2 J ( C L ) 3 ≤ 2 1 ∣ C L ∣.
We therefore begin with estimates for ∣ C L ∣ |\mathcal{C}_L| ∣ C L ∣ and J ( C L ) J(\mathcal{C}_L) J ( C L ) .
The prescribed digit counts give
∣ C L ∣ = L ! ( ( 5 L 26 ) ! ) 2 ( ( 8 L 26 ) ! ) 2 . |\mathcal{C}_L|=\frac{L!}{\left(\left(\frac{5L}{26}\right)!\right)^2\left(\left(\frac{8L}{26}\right)!\right)^2}. ∣ C L ∣ = ( ( 26 5 L ) ! ) 2 ( ( 26 8 L ) ! ) 2 L ! .
Applying Stirling’s formula in the form
log ( n ! ) = n log n − n + 1 2 log n + O ( 1 ) , \log(n!)=n\log n-n+\frac{1}{2}\log n+O(1), log ( n !) = n log n − n + 2 1 log n + O ( 1 ) ,
we obtain
log ∣ C L ∣ = h 0 L − 3 2 log L + O ( 1 ) , h 0 = log 26 − 5 13 log 5 − 8 13 log 8. \log|\mathcal{C}_L|=h_0L-\frac{3}{2}\log L+O(1),\qquad h_0=\log26-\frac{5}{13}\log5-\frac{8}{13}\log8. log ∣ C L ∣ = h 0 L − 2 3 log L + O ( 1 ) , h 0 = log 26 − 13 5 log 5 − 13 8 log 8.
In particular,
∣ C L ∣ ≍ L − 3 / 2 e h 0 L , (20) |\mathcal{C}_L|\asymp L^{-3/2}e^{h_0L}, \tag*{(20)} ∣ C L ∣ ≍ L − 3/2 e h 0 L , (20)
with absolute implied constants.
We next estimate J ( C L ) J(\mathcal{C}_L) J ( C L ) . Set ( w 0 , w 1 , w 2 , w 3 ) = ( 1 , 3 , 3 , 1 ) (w_0,w_1,w_2,w_3)=(1,3,3,1) ( w 0 , w 1 , w 2 , w 3 ) = ( 1 , 3 , 3 , 1 ) and define
ω ( x ) = ∏ i = 1 L w x i , x ∈ { 0 , 1 , 2 , 3 } L . \omega(\mathbf{x})=\prod_{i=1}^{L}w_{x_i},\qquad\mathbf{x}\in\{0,1,2,3\}^{L}. ω ( x ) = i = 1 ∏ L w x i , x ∈ { 0 , 1 , 2 , 3 } L .
The prescribed counts make this weight constant on C L \mathcal{C}_L C L :
ω ( x ) = 3 N 1 ( x ) + N 2 ( x ) = 3 8 L / 13 ( x ∈ C L ) . \omega(\mathbf{x})=3^{N_1(\mathbf{x})+N_2(\mathbf{x})}=3^{8L/13}\qquad(\mathbf{x}\in\mathcal{C}_L). ω ( x ) = 3 N 1 ( x ) + N 2 ( x ) = 3 8 L /13 ( x ∈ C L ) .
For j ∈ { − 3 , … , 3 } j\in\{-3,\ldots,3\} j ∈ { − 3 , … , 3 } , let
ρ ( j ) = ∑ a , b ∈ { 0 , 1 , 2 , 3 } a − b = j w a w b . \rho(j)=\sum_{\substack{a,b\in\{0,1,2,3\}\\a-b=j}}w_aw_b. ρ ( j ) = a , b ∈ { 0 , 1 , 2 , 3 } a − b = j ∑ w a w b .
These are the weighted pair counts for one coordinate. Direct summation gives
ρ ( 0 ) = 20 , ρ ( ± 1 ) = 15 , ρ ( ± 2 ) = 6 , ρ ( ± 3 ) = 1. (21) \rho(0)=20,\qquad\rho(\pm1)=15,\qquad\rho(\pm2)=6,\qquad\rho(\pm3)=1. \tag*{(21)} ρ ( 0 ) = 20 , ρ ( ± 1 ) = 15 , ρ ( ± 2 ) = 6 , ρ ( ± 3 ) = 1. (21)
For each u ∈ C L − C L \mathbf{u}\in C_L-C_L u ∈ C L − C L , the difference multiplicity defined in Lemma 4.1 satisfies
3 16 L 13 r C L − C L ( u ) = ∑ x , y ∈ C L x − y = u ω ( x ) ω ( y ) ≤ ∑ x , y ∈ { 0 , 1 , 2 , 3 } L x − y = u ω ( x ) ω ( y ) = ∏ i = 1 L ρ ( u i ) . (22) 3^{\frac{16L}{13}}r_{C_L-C_L}(\mathbf{u})=
\sum_{\substack{\mathbf{x},\mathbf{y}\in C_L\\ \mathbf{x}-\mathbf{y}=\mathbf{u}}}\omega(\mathbf{x})\omega(\mathbf{y})
\leq
\sum_{\substack{\mathbf{x},\mathbf{y}\in\{0,1,2,3\}^{L}\\ \mathbf{x}-\mathbf{y}=\mathbf{u}}}\omega(\mathbf{x})\omega(\mathbf{y})
=\prod_{i=1}^{L}\rho(u_i). \tag*{(22)} 3 13 16 L r C L − C L ( u ) = x , y ∈ C L x − y = u ∑ ω ( x ) ω ( y ) ≤ x , y ∈ { 0 , 1 , 2 , 3 } L x − y = u ∑ ω ( x ) ω ( y ) = i = 1 ∏ L ρ ( u i ) . (22)
The inequality enlarges the sum to the full cube, where the coordinates can be summed independently.
Taking cube roots and enlarging the sum over differences to { − 3 , … , 3 } L \{-3,\ldots,3\}^{L} { − 3 , … , 3 } L , we obtain
J ( C L ) = ∑ u ∈ C L − C L r C L − C L ( u ) 1 3 ≤ 3 − 16 L 39 ∑ u ∈ { − 3 , … , 3 } L ∏ i = 1 L ρ ( u i ) 1 3 = 3 − 16 L 39 ( ∑ j = − 3 3 ρ ( j ) 1 3 ) L = 3 − 16 L 39 s 0 L , J(C_L)=\sum_{\mathbf{u}\in C_L-C_L}r_{C_L-C_L}(\mathbf{u})^{\frac{1}{3}}
\leq3^{-\frac{16L}{39}}\sum_{\mathbf{u}\in\{-3,\ldots,3\}^{L}}\prod_{i=1}^{L}\rho(u_i)^{\frac{1}{3}}
=3^{-\frac{16L}{39}}\left(\sum_{j=-3}^{3}\rho(j)^{\frac{1}{3}}\right)^{L}
=3^{-\frac{16L}{39}}s_0^{L}, J ( C L ) = u ∈ C L − C L ∑ r C L − C L ( u ) 3 1 ≤ 3 − 39 16 L u ∈ { − 3 , … , 3 } L ∑ i = 1 ∏ L ρ ( u i ) 3 1 = 3 − 39 16 L ( j = − 3 ∑ 3 ρ ( j ) 3 1 ) L = 3 − 39 16 L s 0 L ,
where
s 0 : = ∑ j = − 3 3 ρ ( j ) 1 3 = 20 3 + 2 15 3 + 2 6 3 + 2. s_0:=\sum_{j=-3}^{3}\rho(j)^{\frac{1}{3}}=\sqrt[3]{20}+2\sqrt[3]{15}+2\sqrt[3]{6}+2. s 0 := j = − 3 ∑ 3 ρ ( j ) 3 1 = 3 20 + 2 3 15 + 2 3 6 + 2.
Cubing the preceding estimate gives
J ( C L ) 3 ≤ ( 3 − 16 13 s 0 3 ) L = e b 0 L , b 0 : = 3 log s 0 − 16 13 log 3. (23) J(C_L)^3\leq\left(3^{-\frac{16}{13}}s_0^3\right)^L=e^{b_0L},\qquad b_0:=3\log s_0-\frac{16}{13}\log3. \tag*{(23)} J ( C L ) 3 ≤ ( 3 − 13 16 s 0 3 ) L = e b 0 L , b 0 := 3 log s 0 − 13 16 log 3. (23)
Since s 0 > 12 s_0>12 s 0 > 12 and 0 < h 0 ≤ log 4 0<h_0\leq\log4 0 < h 0 ≤ log 4 , we have
b 0 > 3 log 12 − 16 13 log 3 > 2 log 4 ≥ 2 h 0 . b_0>3\log12-\frac{16}{13}\log3>2\log4\geq2h_0. b 0 > 3 log 12 − 13 16 log 3 > 2 log 4 ≥ 2 h 0 .
We now choose L L L to prove the first inequality in (19) . Dividing the two error terms by ∣ C L ∣ \lvert C_L\rvert ∣ C L ∣ and using (20) and (23) , we obtain
∣ C L ∣ p + 2 J ( C L ) 3 p ∣ C L ∣ ≪ e h 0 L p L 3 2 + L 3 2 e ( b 0 − h 0 ) L p ≪ L 3 2 e ( b 0 − h 0 ) L p , \frac{\lvert C_L\rvert}{p}+\frac{2J(C_L)^3}{p\lvert C_L\rvert}
\ll\frac{e^{h_0L}}{pL^{\frac{3}{2}}}+\frac{L^{\frac{3}{2}}e^{(b_0-h_0)L}}{p}
\ll\frac{L^{\frac{3}{2}}e^{(b_0-h_0)L}}{p}, p ∣ C L ∣ + p ∣ C L ∣ 2 J ( C L ) 3 ≪ p L 2 3 e h 0 L + p L 2 3 e ( b 0 − h 0 ) L ≪ p L 2 3 e ( b 0 − h 0 ) L ,
where the last step uses b 0 > 2 h 0 b_0>2h_0 b 0 > 2 h 0 and L ≥ 1 L\geq1 L ≥ 1 .
For L ≤ log p b 0 − h 0 L \le\frac{\log p}{b_0-h_0} L ≤ b 0 − h 0 l o g p , we have L 3 2 ≪ ( log p ) 3 2 L^{\frac{3}{2}} \ll(\log p)^{\frac{3}{2}} L 2 3 ≪ ( log p ) 2 3 . It therefore suffices to require
e ( b 0 − h 0 ) L ≤ e − K p ( log p ) − 3 2 , e^{(b_0-h_0)L} \le e^{-K}p(\log p)^{-\frac{3}{2}}, e ( b 0 − h 0 ) L ≤ e − K p ( log p ) − 2 3 ,
where K > 0 K>0 K > 0 will be fixed sufficiently large. Taking logarithms, we choose the largest multiple of 26 26 26 satisfying this inequality, namely
L = 26 ⌊ log p − 3 2 log log p − K 26 ( b 0 − h 0 ) ⌋ . (24) L=26\left\lfloor\frac{\log p-\frac{3}{2}\log\log p-K}{26(b_0-h_0)}\right\rfloor. \tag*{(24)} L = 26 ⌊ 26 ( b 0 − h 0 ) log p − 2 3 log log p − K ⌋ . (24)
For p p p sufficiently large in terms of K K K , this choice is positive, satisfies L ≤ log p b 0 − h 0 L\le\frac{\log p}{b_0-h_0} L ≤ b 0 − h 0 l o g p , and has L ≍ log p L\asymp\log p L ≍ log p . Consequently,
∣ C L ∣ p + 2 J ( C L ) 3 p ∣ C L ∣ ≪ L 3 2 e ( b 0 − h 0 ) L p ≤ e − K ( b 0 − h 0 ) 3 2 , \frac{|C_L|}{p}+\frac{2J(C_L)^3}{p|C_L|}\ll\frac{L^{\frac{3}{2}}e^{(b_0-h_0)L}}{p}\le\frac{e^{-K}}{(b_0-h_0)^{\frac{3}{2}}}, p ∣ C L ∣ + p ∣ C L ∣ 2 J ( C L ) 3 ≪ p L 2 3 e ( b 0 − h 0 ) L ≤ ( b 0 − h 0 ) 2 3 e − K ,
with an implied constant independent of K K K . We first fix K K K sufficiently large and then take p p p sufficiently large so that the relative error is at most 1 2 \frac{1}{2} 2 1 . Lemma 4.1 then gives
∣ A ∣ ≥ 1 2 ∣ C L ∣ . |A|\ge\frac{1}{2}|C_L|. ∣ A ∣ ≥ 2 1 ∣ C L ∣.
This proves the first inequality in (19) .
To prove the second inequality, put
β 0 : = h 0 b 0 − h 0 ∈ ( 0 , 1 ) . \beta_0:=\frac{h_0}{b_0-h_0}\in(0,1). β 0 := b 0 − h 0 h 0 ∈ ( 0 , 1 ) .
With K K K now fixed, rounding in (24) changes L L L by less than 26 26 26 , and log L = log log p + O ( 1 ) \log L=\log\log p+O(1) log L = log log p + O ( 1 ) . Substituting this choice of L L L into the logarithmic size estimate gives
log ∣ C L ∣ = β 0 log p − 3 2 ( 1 + β 0 ) log log p + O ( 1 ) . \log|C_L|=\beta_0\log p-\frac{3}{2}(1+\beta_0)\log\log p+O(1). log ∣ C L ∣ = β 0 log p − 2 3 ( 1 + β 0 ) log log p + O ( 1 ) .
Hence,
1 2 ∣ C L ∣ ≫ p β 0 ( log p ) 3 2 ( 1 + β 0 ) . (25) \frac{1}{2}|C_L|\gg\frac{p^{\beta_0}}{(\log p)^{\frac{3}{2}(1+\beta_0)}}. \tag*{(25)} 2 1 ∣ C L ∣ ≫ ( log p ) 2 3 ( 1 + β 0 ) p β 0 . (25)
It remains to verify that β 0 > 7 26 \beta_0>\frac{7}{26} β 0 > 26 7 . Since b 0 − h 0 > 0 b_0-h_0>0 b 0 − h 0 > 0 , this is equivalent to 33 h 0 > 7 b 0 33h_0>7b_0 33 h 0 > 7 b 0 . Substituting the definitions yields
13 ( 33 h 0 − 7 b 0 ) = log ( 26 429 ⋅ 3 112 5 165 ⋅ 8 264 ⋅ s 0 273 ) . (26) 13(33h_0-7b_0)=\log\left(\frac{26^{429}\cdot3^{112}}{5^{165}\cdot8^{264}\cdot s_0^{273}}\right). \tag*{(26)} 13 ( 33 h 0 − 7 b 0 ) = log ( 5 165 ⋅ 8 264 ⋅ s 0 273 2 6 429 ⋅ 3 112 ) . (26)
We verify this inequality using rational upper bounds for the cube roots and integer arithmetic. The inequalities
2715 3 > 20 ⋅ 1000 3 , 2467 3 > 15 ⋅ 1000 3 , 1818 3 > 6 ⋅ 1000 3 2715^3>20\cdot1000^3,\qquad2467^3>15\cdot1000^3,\qquad1818^3>6\cdot1000^3 271 5 3 > 20 ⋅ 100 0 3 , 246 7 3 > 15 ⋅ 100 0 3 , 181 8 3 > 6 ⋅ 100 0 3
imply s 0 < 13285 1000 s_0<\frac{13285}{1000} s 0 < 1000 13285 , while direct integer arithmetic gives
26 429 ⋅ 3 112 ⋅ 1000 273 > 5 165 ⋅ 8 264 ⋅ 13285 273 . 26^{429}\cdot3^{112}\cdot1000^{273}>5^{165}\cdot8^{264}\cdot13285^{273}. 2 6 429 ⋅ 3 112 ⋅ 100 0 273 > 5 165 ⋅ 8 264 ⋅ 1328 5 273 .
Thus the ratio in (26) is greater than 1 1 1 , proving β 0 > 7 26 \beta_0>\frac{7}{26} β 0 > 26 7 .
Since
p β 0 − 7 26 ( log p ) 3 2 ( 1 + β 0 ) ⟶ ∞ ( p → ∞ ) , \frac{p^{\beta_0-\frac{7}{26}}}{(\log p)^{\frac{3}{2}(1+\beta_0)}} \longrightarrow\infty\qquad(p\to\infty), ( log p ) 2 3 ( 1 + β 0 ) p β 0 − 26 7 ⟶ ∞ ( p → ∞ ) ,
the estimate (25) implies 1 2 ∣ C L ∣ ≥ p 7 26 \frac{1}{2}|\mathcal{C}_L| \ge p^{\frac{7}{26}} 2 1 ∣ C L ∣ ≥ p 26 7 for all sufficiently large p p p . This proves the second inequality in (19) , and the first now gives ∣ A ∣ ≥ p 7 26 |A| \ge p^{\frac{7}{26}} ∣ A ∣ ≥ p 26 7 .
The same set A A A works for every κ ∈ F p × \kappa\in\mathbb{F}_p^\times κ ∈ F p × : if κ ( A − A ) 2 \kappa(A-A)^2 κ ( A − A ) 2 contained a nondegenerate geometric progression, multiplication by κ − 1 \kappa^{-1} κ − 1 would give one in ( A − A ) 2 (A-A)^2 ( A − A ) 2 . This completes the proof. □ \square □
Numerically, β 0 ≈ 0.2693287509 \beta_0 \approx0.2693287509 β 0 ≈ 0.2693287509 , so 7 26 \frac{7}{26} 26 7 is a convenient rational exponent below β 0 \beta_0 β 0 . We do not claim that these choices or the resulting exponent are optimal.
Further remarks
The preceding sections reduce the odd-dimensional extremal problem to dimension one. We now explain what is known in even dimensions, where the split and nonsplit forms behave differently. We then show why the condition ∣ D ∣ ≥ p 1 − ε |D| \ge p^{1-\varepsilon} ∣ D ∣ ≥ p 1 − ε , for fixed ε > 0 \varepsilon> 0 ε > 0 , does not force a progression in an arbitrary set D ⊂ F p D \subset\mathbb{F}_p D ⊂ F p , and state the remaining questions.
Even dimensions
The distance estimate of Pham, Shen, Tran, and Xue [15 ] , combined with a quantitative form of Roth’s theorem, gives a uniform sufficient threshold in even dimensions. This threshold is sharp for split forms. For the standard nonsplit form, the remaining extremal problem reduces to the plane. We first bound the cardinality of an arbitrary set containing no nondegenerate geometric progression. This will be applied to distance sets in both cases.
Lemma 5.1. There is an absolute constant a > 0 a > 0 a > 0 such that, for every sufficiently large prime p p p , every set D ⊂ F p D \subset\mathbb{F}_p D ⊂ F p containing no nondegenerate geometric progression satisfies
∣ D ∣ ≤ p e − a ( log p log log p ) 1 6 . (27) |D| \le p e^{-a\left(\frac{\log p}{\log\log p}\right)^{\frac{1}{6}}}. \tag*{(27)} ∣ D ∣ ≤ p e − a ( l o g l o g p l o g p ) 6 1 . (27) Consequently, for every c , K > 0 c, K > 0 c , K > 0 , there exists p 0 = p 0 ( c , K ) p_0 = p_0(c,K) p 0 = p 0 ( c , K ) such that
∣ D ∣ ≥ c p ( log p ) K ⟹ D contains a nondegenerate geometric progression |D| \ge\frac{cp}{(\log p)^K} \quad\Longrightarrow\quad D\text{ contains a nondegenerate geometric progression} ∣ D ∣ ≥ ( log p ) K c p ⟹ D contains a nondegenerate geometric progression whenever p ≥ p 0 p \ge p_0 p ≥ p 0 is prime and D ⊂ F p D \subset\mathbb{F}_p D ⊂ F p .
Proof. Let r 3 ( N ) r_3(N) r 3 ( N ) be the largest cardinality of a subset of { 0 , … , N − 1 } \{0,\ldots,N-1\} { 0 , … , N − 1 } containing no three distinct terms in arithmetic progression. By Raghavan [17 Theorem 1.4] , there is an absolute constant b > 0 b > 0 b > 0 such that
r 3 ( N ) ≤ N e − b ( log N log log N ) 1 6 r_3(N) \le N e^{-b\left(\frac{\log N}{\log\log N}\right)^{\frac{1}{6}}} r 3 ( N ) ≤ N e − b ( l o g l o g N l o g N ) 6 1
for all sufficiently large N N N .
Suppose that D D D contains no nondegenerate geometric progression. Choose a primitive root γ ∈ F p × \gamma\in\mathbb{F}_p^\times γ ∈ F p × and let
S = { j ∈ { 0 , … , p − 2 } : γ j ∈ D } . S=\{j\in\{0,\ldots,p-2\}:\gamma^j\in D\}. S = { j ∈ { 0 , … , p − 2 } : γ j ∈ D } .
If S S S contained integers u , u + v , u + 2 v u,u+v,u+2v u , u + v , u + 2 v with v > 0 v>0 v > 0 , then γ u , γ u + v , γ u + 2 v \gamma^u,\gamma^{u+v},\gamma^{u+2v} γ u , γ u + v , γ u + 2 v would be three distinct nonzero elements of D D D in geometric progression. Their distinctness follows because their exponents belong to { 0 , … , p − 2 } \{0,\ldots,p-2\} { 0 , … , p − 2 } . Thus, ∣ S ∣ ≤ r 3 ( p − 1 ) |S|\le r_3(p-1) ∣ S ∣ ≤ r 3 ( p − 1 ) and
∣ D ∣ ≤ 1 + r 3 ( p − 1 ) ≤ p e − a ( log p log log p ) 1 / 6 |D|\le1+r_3(p-1)\le p e^{-a\left(\frac{\log p}{\log\log p}\right)^{1/6}} ∣ D ∣ ≤ 1 + r 3 ( p − 1 ) ≤ p e − a ( l o g l o g p l o g p ) 1/6
for all sufficiently large p p p , with a suitable absolute constant a > 0 a>0 a > 0 . The final assertion follows since
e − a ( log p log log p ) 1 / 6 = o ( ( log p ) − K ) e^{-a\left(\frac{\log p}{\log\log p}\right)^{1/6}}=o((\log p)^{-K}) e − a ( l o g l o g p l o g p ) 1/6 = o (( log p ) − K )
for every fixed K > 0 K>0 K > 0 . This completes the proof.
A uniform sufficient threshold. We apply the preceding lemma to the recent distance estimate. For a quadratic form Q Q Q on F p 2 m \mathbb{F}_p^{2m} F p 2 m , let
Δ Q ( E ) = { Q ( x − y ) : x , y ∈ E } . \Delta_Q(E)=\{Q(x-y):x,y\in E\}. Δ Q ( E ) = { Q ( x − y ) : x , y ∈ E } .
A nondegenerate form on F p 2 m \mathbb{F}_p^{2m} F p 2 m is called split if it has an m m m -dimensional totally isotropic subspace, and nonsplit otherwise. In the nonsplit case, the largest dimension of a totally isotropic subspace is m − 1 m-1 m − 1 . Pham, Shen, Tran, and Xue [15 Theorem 1.1 and Remark 1.2] proved that, for every nondegenerate Q Q Q and every E ⊂ F p 2 m E\subset\mathbb{F}_p^{2m} E ⊂ F p 2 m with ∣ E ∣ > p m |E|>p^m ∣ E ∣ > p m ,
∣ Δ Q ( E ) ∣ ≥ c 0 p log 2 ( 2 p ) , (28) |\Delta_Q(E)|\ge\frac{c_0p}{\log^2(2p)}, \tag*{(28)} ∣ Δ Q ( E ) ∣ ≥ log 2 ( 2 p ) c 0 p , (28)
where c 0 > 0 c_0>0 c 0 > 0 is absolute. If Q Q Q is nonsplit, the same conclusion holds when ∣ E ∣ = p m |E|=p^m ∣ E ∣ = p m ; in fact, their estimate gives ∣ Δ Q ( E ) ∣ ≥ c 0 p log ( 2 p ) |\Delta_Q(E)|\ge\frac{c_0p}{\log(2p)} ∣ Δ Q ( E ) ∣ ≥ l o g ( 2 p ) c 0 p in this case, after decreasing c 0 c_0 c 0 if necessary. The constants are independent of m m m .
Corollary 5.2. There is an absolute constant p 0 p_0 p 0 such that the following holds for every odd prime p ≥ p 0 p\ge p_0 p ≥ p 0 and every integer m ≥ 1 m\ge1 m ≥ 1 . Let Q Q Q be a nondegenerate quadratic form on F p 2 m \mathbb{F}_p^{2m} F p 2 m and let E ⊂ F p 2 m E\subset\mathbb{F}_p^{2m} E ⊂ F p 2 m . If ∣ E ∣ > p m |E|>p^m ∣ E ∣ > p m , then Δ Q ( E ) \Delta_Q(E) Δ Q ( E ) contains a nondegenerate geometric progression. The same conclusion holds if ∣ E ∣ = p m |E|=p^m ∣ E ∣ = p m and Q Q Q is nonsplit.
Proof. For p ≥ 2 p\ge2 p ≥ 2 , we have log ( 2 p ) ≤ 2 log p \log(2p)\le2\log p log ( 2 p ) ≤ 2 log p . Thus, (28) gives
∣ Δ Q ( E ) ∣ ≥ c 0 p 4 ( log p ) 2 . |\Delta_Q(E)|\ge\frac{c_0p}{4(\log p)^2}. ∣ Δ Q ( E ) ∣ ≥ 4 ( log p ) 2 c 0 p .
Lemma 5.1, with c = 1 4 c 0 c=\frac{1}{4}c_0 c = 4 1 c 0 and K = 2 K=2 K = 2 , proves the assertion when ∣ E ∣ > p m |E|>p^m ∣ E ∣ > p m . The quoted estimate for nonsplit forms gives the conclusion at equality as well. Since c 0 c_0 c 0 is absolute, the lower bound on p p p is independent of m m m and Q Q Q . This completes the proof.
Split forms. The strict inequality ∣ E ∣ > p m |E|>p^m ∣ E ∣ > p m is sharp when Q Q Q is split. Indeed, a split form has a totally isotropic subspace W W W of dimension m m m . Taking E = W E=W E = W gives ∣ E ∣ = p m |E|=p^m ∣ E ∣ = p m and Δ Q ( E ) = { 0 } \Delta_Q(E)=\{0\} Δ Q ( E ) = { 0 } . For the standard form Q 2 m Q_{2m} Q 2 m , the split condition is that ( − 1 ) m (-1)^m ( − 1 ) m be a square in F p \mathbb{F}_p F p ; see [16 Lemma 2.7] . Consequently,
M G P , 2 m ( p ) = p m (29) M_{\mathrm{GP},2m}(p)=p^m \tag*{(29)} M GP , 2 m ( p ) = p m (29)
for all sufficiently large primes p p p whenever m m m is even or p ≡ 1 ( m o d 4 ) p\equiv1\pmod{4} p ≡ 1 ( mod 4 ) .
Nonsplit forms. For the standard form, the remaining case is p ≡ 3 ( m o d 4 ) p \equiv3 \pmod{4} p ≡ 3 ( mod 4 ) and m m m odd. A totally isotropic subspace then has dimension at most m − 1 m-1 m − 1 , so the preceding example does not establish sharpness of the exponent m m m . A cylinder over a planar set gives a lower comparison with M G P , 2 ( p ) M_{\mathrm{GP},2}(p) M GP , 2 ( p ) , and the extraction theorem gives the upper comparison. We record both inequalities together with the available planar bounds.
Proposition 5.3. There are absolute constants c > 0 c > 0 c > 0 , C ≥ 1 C \ge1 C ≥ 1 , and p 0 p_0 p 0 such that, for every prime p ≥ p 0 p \ge p_0 p ≥ p 0 with p ≡ 3 ( m o d 4 ) p \equiv3 \pmod{4} p ≡ 3 ( mod 4 ) and every odd integer m ≥ 1 m \ge1 m ≥ 1 ,
p m − 1 M G P , 2 ( p ) ≤ M G P , 2 m ( p ) ≤ C p m − 1 M G P , 2 ( p ) . (30) p^{m-1}M_{\mathrm{GP},2}(p) \le M_{\mathrm{GP},2m}(p) \le Cp^{m-1}M_{\mathrm{GP},2}(p). \tag*{(30)} p m − 1 M GP , 2 ( p ) ≤ M GP , 2 m ( p ) ≤ C p m − 1 M GP , 2 ( p ) . (30) Moreover,
p 7 26 ≤ M G P , 2 ( p ) ≤ C p e − c ( log p log log p ) 1 6 . (31) p^{\frac{7}{26}} \le M_{\mathrm{GP},2}(p) \le Cp e^{-c\left(\frac{\log p}{\log\log p}\right)^{\frac{1}{6}}}. \tag*{(31)} p 26 7 ≤ M GP , 2 ( p ) ≤ C p e − c ( l o g l o g p l o g p ) 6 1 . (31)
Proof. We first prove (30) and then establish the planar bounds in (31) .
By the classification of quadratic forms over F p \mathbb{F}_p F p , a linear change of coordinates identifies Q 2 m Q_{2m} Q 2 m with
u ⋅ v + Q 2 ( z ) , u , v ∈ F p m − 1 , z ∈ F p 2 ; u \cdot v + Q_2(z), \qquad u,v \in\mathbb{F}_p^{m-1}, \quad z \in\mathbb{F}_p^2; u ⋅ v + Q 2 ( z ) , u , v ∈ F p m − 1 , z ∈ F p 2 ;
see [16 Lemma 2.7] . If P ⊂ F p 2 P \subset\mathbb{F}_p^2 P ⊂ F p 2 has no nondegenerate geometric progression in its distance set, then, in these coordinates, the set
F p m − 1 × { 0 } m − 1 × P \mathbb{F}_p^{m-1} \times\{0\}^{m-1} \times P F p m − 1 × { 0 } m − 1 × P
has p m − 1 ∣ P ∣ p^{m-1}|P| p m − 1 ∣ P ∣ elements and distance set Δ ( P ) \Delta(P) Δ ( P ) . This proves the lower bound in (30) .
For the upper bound, let E ⊂ F p 2 m E \subset\mathbb{F}_p^{2m} E ⊂ F p 2 m have no nondegenerate geometric progression in Δ ( E ) \Delta(E) Δ ( E ) . Corollary 5.2 gives ∣ E ∣ < p m |E| < p^m ∣ E ∣ < p m . The extraction theorem of Pham, Shen, and Xue [16 Theorem 1.1] , with the residual binary form identified with Q 2 Q_2 Q 2 , gives a set P ⊂ F p 2 P \subset\mathbb{F}_p^2 P ⊂ F p 2 such that Δ ( P ) ⊆ Δ ( E ) \Delta(P) \subseteq\Delta(E) Δ ( P ) ⊆ Δ ( E ) and
∣ P ∣ ≥ 1 C 0 ∣ E ∣ / p m − 1 1 + ∣ E ∣ / p m + 1 ≥ ∣ E ∣ 2 C 0 p m − 1 , |P| \ge\frac{1}{C_0}\frac{|E|/p^{m-1}}{1+|E|/p^{m+1}} \ge\frac{|E|}{2C_0p^{m-1}}, ∣ P ∣ ≥ C 0 1 1 + ∣ E ∣/ p m + 1 ∣ E ∣/ p m − 1 ≥ 2 C 0 p m − 1 ∣ E ∣ ,
where C 0 C_0 C 0 is absolute. Since ∣ P ∣ ≤ M G P , 2 ( p ) |P| \le M_{\mathrm{GP},2}(p) ∣ P ∣ ≤ M GP , 2 ( p ) , the upper bound follows.
To prove (31) , let A ⊂ F p A \subset\mathbb{F}_p A ⊂ F p be the set from Proposition 1.4(ii). Then Δ ( A × { 0 } ) = ( A − A ) 2 \Delta(A \times\{0\}) = (A-A)^2 Δ ( A × { 0 }) = ( A − A ) 2 , giving M G P , 2 ( p ) ≥ p 7 26 M_{\mathrm{GP},2}(p) \ge p^{\frac{7}{26}} M GP , 2 ( p ) ≥ p 26 7 . Next, let P ⊂ F p 2 P \subset\mathbb{F}_p^2 P ⊂ F p 2 be nonempty and have no nondegenerate geometric progression in Δ ( P ) \Delta(P) Δ ( P ) . Again, Corollary 5.2 gives ∣ P ∣ < p |P| < p ∣ P ∣ < p . Since Q 2 Q_2 Q 2 is anisotropic, the planar estimate of Pham, Shen, Tran, and Xue [15 Theorem 1.3] yields
∣ P ∣ log ( 2 ∣ P ∣ ) ≪ ∣ Δ ( P ) ∣ ≤ p e − a ( log p log log p ) 1 6 , \frac{|P|}{\log(2|P|)} \ll|\Delta(P)| \le p e^{-a\left(\frac{\log p}{\log\log p}\right)^{\frac{1}{6}}}, log ( 2∣ P ∣ ) ∣ P ∣ ≪ ∣Δ ( P ) ∣ ≤ p e − a ( l o g l o g p l o g p ) 6 1 ,
where the last inequality is Lemma 5.1 . Since ∣ P ∣ < p |P| < p ∣ P ∣ < p , we obtain
∣ P ∣ ≪ p log ( 2 p ) e − a ( log p log log p ) 1 6 ≪ p e − c ( log p log log p ) 1 6 |P| \ll p\log(2p)e^{-a\left(\frac{\log p}{\log\log p}\right)^{\frac{1}{6}}} \ll p e^{-c\left(\frac{\log p}{\log\log p}\right)^{\frac{1}{6}}} ∣ P ∣ ≪ p log ( 2 p ) e − a ( l o g l o g p l o g p ) 6 1 ≪ p e − c ( l o g l o g p l o g p ) 6 1
for a suitable absolute constant c > 0 c > 0 c > 0 . This completes the proof.
In particular, for p ≡ 3 ( m o d 4 ) p \equiv3 \pmod{4} p ≡ 3 ( mod 4 ) and odd m m m ,
p m − 1 + 7 26 ≤ M G P , 2 m ( p ) ≪ p m e − c ( log p log log p ) 1 6 . (32) p^{m-1+\frac{7}{26}} \le M_{\mathrm{GP},2m}(p) \ll p^m e^{-c\left(\frac{\log p}{\log\log p}\right)^{\frac{1}{6}}}. \tag*{(32)} p m − 1 + 26 7 ≤ M GP , 2 m ( p ) ≪ p m e − c ( l o g l o g p l o g p ) 6 1 . (32)
Thus, M G P , 2 m ( p ) = o ( p m ) M_{\mathrm{GP},2m}(p) = o(p^m) M GP , 2 m ( p ) = o ( p m ) as p p p tends to infinity through these primes. The upper bound does not give a fixed power improvement below p m p^m p m , and the lower bound does not establish sharpness of the exponent m m m . Determining the optimal exponent in this nonsplit case reduces, by (30) , to determining it for M G P , 2 ( p ) M_{\mathrm{GP},2}(p) M GP , 2 ( p ) when p ≡ 3 ( m o d 4 ) p \equiv3 \pmod{4} p ≡ 3 ( mod 4 ) .
Cardinality alone is not enough
Lemma 5.1 forces a progression at every density c / ( log p ) K c/(\log p)^K c / ( log p ) K . A fixed power bound is different: for every ε > 0 \varepsilon> 0 ε > 0 , the size condition ∣ D ∣ ≥ p 1 − ε |D| \ge p^{1-\varepsilon} ∣ D ∣ ≥ p 1 − ε does not force a nondegenerate geometric progression in an arbitrary set D ⊂ F p D \subset\mathbb{F}_p D ⊂ F p . Indeed, let ℓ 0 = ⌊ p − 1 3 ⌋ \ell_0 = \left\lfloor\frac{p-1}{3}\right\rfloor ℓ 0 = ⌊ 3 p − 1 ⌋ . Behrend’s construction [2 ] gives a set B ⊂ { 0 , … , ℓ 0 − 1 } B \subset\{0,\ldots,\ell_0-1\} B ⊂ { 0 , … , ℓ 0 − 1 } with ∣ B ∣ ≥ ℓ 0 e − C log ℓ 0 |B| \ge\ell_0 e^{-C\sqrt{\log\ell_0}} ∣ B ∣ ≥ ℓ 0 e − C l o g ℓ 0 containing no arithmetic progression of three distinct terms. Choose a generator γ \gamma γ of F p × \mathbb{F}_p^\times F p × and set D = { γ b : b ∈ B } D = \{\gamma^b : b \in B\} D = { γ b : b ∈ B } . A nondegenerate geometric progression in D D D would give distinct b 1 , b 2 , b 3 ∈ B b_1,b_2,b_3 \in B b 1 , b 2 , b 3 ∈ B satisfying b 1 + b 3 ≡ 2 b 2 ( m o d p − 1 ) b_1+b_3 \equiv2b_2 \pmod{p-1} b 1 + b 3 ≡ 2 b 2 ( mod p − 1 ) . Since ∣ b 1 + b 3 − 2 b 2 ∣ ≤ 2 ( ℓ 0 − 1 ) < p − 1 |b_1+b_3-2b_2| \le2(\ell_0-1) < p-1 ∣ b 1 + b 3 − 2 b 2 ∣ ≤ 2 ( ℓ 0 − 1 ) < p − 1 , this congruence would imply b 1 + b 3 = 2 b 2 b_1+b_3=2b_2 b 1 + b 3 = 2 b 2 over the integers, contrary to the choice of B B B .
After increasing the absolute constant C C C if necessary, we obtain
∣ D ∣ = ∣ B ∣ ≥ p e − C log p |D| = |B| \ge p e^{-C\sqrt{\log p}} ∣ D ∣ = ∣ B ∣ ≥ p e − C l o g p
for all sufficiently large p p p . For every fixed ε > 0 \varepsilon> 0 ε > 0 , this lower bound exceeds p 1 − ε p^{1-\varepsilon} p 1 − ε once p p p is sufficiently large, showing that such a size condition alone does not force a nondegenerate geometric progression. The argument in Section 3 uses the additional structure of squared difference sets.
Remarks over arbitrary finite fields
Let q q q be a power of a prime p > 18 p > 18 p > 18 . Define Δ ( E ) \Delta(E) Δ ( E ) and M G P , d ( q ) M_{\mathrm{GP},d}(q) M GP , d ( q ) over F q \mathbb{F}_q F q by the same formulas as over F p \mathbb{F}_p F p . The arguments in Sections 2–4 extend to this setting. More precisely, the quadratic-form counts and the upper-bound argument use q q q in place of p p p , with Fourier analysis defined using a nontrivial additive character of F q \mathbb{F}_q F q . In Lemma 4.1, choosing α \alpha α uniformly from F q L \mathbb{F}_q^L F q L gives the probabilities 1 / q 1/q 1/ q for a collision and at most 2 / q 2/q 2/ q for a nonzero quadratic relation. The two steps that lift congruences to integer equalities still use the characteristic bound p > 18 p > 18 p > 18 . The digit-count estimates are unchanged, with L L L chosen in terms of log q \log q log q . For every integer m ≥ 0 m \ge0 m ≥ 0 ,
q m M G P , 1 ( q ) ≤ M G P , 2 m + 1 ( q ) ≤ 4 q m M G P , 1 ( q ) . q^m M_{\mathrm{GP},1}(q) \le M_{\mathrm{GP},2m+1}(q) \le4q^m M_{\mathrm{GP},1}(q). q m M GP , 1 ( q ) ≤ M GP , 2 m + 1 ( q ) ≤ 4 q m M GP , 1 ( q ) .
Moreover, there are absolute constants C ≥ 1 C \ge1 C ≥ 1 and q 0 q_0 q 0 such that
q m + 7 26 ≤ M G P , 2 m + 1 ( q ) ≤ C q m + 16 25 q^{m+\frac{7}{26}} \le M_{\mathrm{GP},2m+1}(q) \le Cq^{m+\frac{16}{25}} q m + 26 7 ≤ M GP , 2 m + 1 ( q ) ≤ C q m + 25 16
whenever q ≥ q 0 q \ge q_0 q ≥ q 0 . These constants are independent of m m m , p p p , and the degree of the field extension. Questions of sharpness and the construction of extremal examples are more involved over general finite fields. To keep the presentation focused and consistent with recent progress on the distance problem over prime fields, we state and prove the main results only over prime fields.
Open questions
The one-dimensional extremal problem. Proposition 1.4 gives, for all sufficiently large primes p p p ,
p 7 26 ≤ M G P , 1 ( p ) ≪ p 16 25 p^{\frac{7}{26}} \le M_{\mathrm{GP},1}(p) \ll p^{\frac{16}{25}} p 26 7 ≤ M GP , 1 ( p ) ≪ p 25 16
The gap between these bounds leads to the following question.
Question 5.4. What is the order of magnitude of M G P , 1 ( p ) M_{\mathrm{GP},1}(p) M GP , 1 ( p ) as p p p tends to infinity through the primes?
By Proposition 2.1,
M G P , 2 m + 1 ( p ) ≍ p m M G P , 1 ( p ) , M_{\mathrm{GP},2m+1}(p) \asymp p^m M_{\mathrm{GP},1}(p), M GP , 2 m + 1 ( p ) ≍ p m M GP , 1 ( p ) ,
with absolute implied constants, so an answer to Question 5.4 would also determine the extremal order in every odd dimension.
Other arithmetic patterns. A natural next question is how large E E E must be for Δ ( E ) \Delta(E) Δ ( E ) to contain other patterns, such as a nontrivial three-term arithmetic progression or a geometric progression of length at least four.
On ( u , s ) (u,s) ( u , s ) –Salem sets. Fraser introduced ( u , s ) (u,s) ( u , s ) –Salem sets and studied their distance sets in [6 ] ; see also [5 ] for subsequent results. It would be interesting to determine whether suitable ( u , s ) (u,s) ( u , s ) –Salem hypotheses lower the size thresholds for geometric progressions proved in this paper.
Acknowledgement. D. T. Tran would like to thank the Vietnam Institute for Advanced Study in Mathematics (VIASM) for its warm hospitality and excellent research environment.