betaFeedback

WorksMathematics

Equilateral-triangle-free sets in finite planes

Abstract

For a prime p>3p>3, let F(p)F(p) be the largest cardinality of a subset of Fp2\mathbb F_p^2 containing no equilateral triangle with nonzero squared side length. Alex Iosevich asked for the exact value of F(p)F(p). By constructing such subsets of Fp2\mathbb F_p^2 from cap sets in F3n\mathbb F_3^n, we obtain the uniform lower bounds F(p)≫{p2γ,p≡11(mod12),p1+γ,p≡1(mod12). F(p)\gg \begin{cases} p^{2γ}, & p\equiv 11\pmod{12},\\ p^{1+γ}, & p\equiv 1\pmod{12}. \end{cases} Here γ=log⁡3(2.2202)γ=\log_3(2.2202), so the two exponents are 1.452008666…1.452008666\ldots and 1.726004333…1.726004333\ldots, respectively. We also apply a quantitative corners theorem to show that F(p)=o(p2)F(p)=o(p^2) as p→∞p\to\infty through either congruence class.

Introduction

For a prime p>3p > 3, let Fp\mathbb{F}_p denote the field with pp elements, and let F(p)F(p) be the largest cardinality of a subset of Fp2\mathbb{F}_p^2 containing no equilateral triangle with nonzero squared side length. For w=(a,b)∈Fp2w = (a,b) \in\mathbb{F}_p^2, write ∥w∥2=a2+b2\lVert w\rVert^2 = a^2 + b^2. The squared distance between w=(a,b)w = (a,b) and w′=(a′,b′)w' = (a',b') is

∥w−w′∥2=(a−a′)2+(b−b′)2,\lVert w-w'\rVert^2 = (a-a')^2 + (b-b')^2,

and an equilateral triangle consists of three distinct points X,Y,ZX,Y,Z satisfying

∥X−Y∥2=∥Y−Z∥2=∥Z−X∥2≠0.(1)\lVert X-Y\rVert^2 = \lVert Y-Z\rVert^2 = \lVert Z-X\rVert^2 \ne0. \tag*{(1)}

The problem of determining F(p)F(p) was raised by Alex Iosevich.

One of the motivations behind this question comes from the finite-field simplex problem.

The finite-field simplex problem asks how large a subset of a finite vector space must be to determine many, or all, congruence classes of simplices. Two configurations are congruent if a translation followed by an orthogonal linear map takes one to the other. This problem has been studied by Fourier analysis, incidence estimates, group actions, and spectral graph methods [1, 2, 11, 12].

Bennett, Iosevich, and Pakianathan [2] used the Elekes–Sharir method to show that, for every prime p≡3(mod4)p \equiv3 \pmod4, any set E⊆Fp2E \subseteq\mathbb{F}_p^2 with ∣E∣≫p7/4|E| \gg p^{7/4} determines ≫p3\gg p^3 congruence classes of triangles, a positive proportion of all such classes. Bennett, Hart, Iosevich, Pakianathan, and Rudnev [1 Theorem 1.6] showed that, for every prime p>3p > 3, the same conclusion holds whenever ∣E∣≫p8/5|E| \gg p^{8/5}. For p≡3(mod4)p \equiv3 \pmod4, Pham [8 Theorem 1.2] proved a stronger conclusion under the same size condition, namely, EE determines ≫p2\gg p^2 triangle congruence classes with any prescribed nonzero squared side length.

A set may determine many triangle congruence classes and still miss a particular one. Suppose that t1,t2,t3t_1,t_2,t_3 are the squared side lengths of a noncollinear triangle Δ\Delta in Fp2\mathbb{F}_p^2, and that all three are nonzero. How large must E⊆Fp2E \subseteq\mathbb{F}_p^2 be to contain a triangle with these three squared side lengths?

This question is better understood in higher dimensions. View Δ\Delta in Fpd\mathbb{F}_p^d by appending zero coordinates. For d≥4d \ge4, results of Vinh [11] and Iosevich and Parshall [4] show that every set E⊆FpdE \subseteq\mathbb{F}_p^d with ∣E∣≥Cp(d+3)/2|E| \ge Cp^{(d+3)/2} contains a congruent copy of Δ\Delta. Parshall’s simplex theorem [7] gives the same conclusion for d≥3d \ge3 under the hypothesis ∣E∣≥Cp2(d+1)/3|E| \ge Cp^{2(d+1)/3}. This last exponent equals 22 at d=2d=2, although the theorem requires d≥3d \ge3. In the plane, we know of no ε>0\varepsilon> 0 for which ∣E∣≥Cp2−ε|E| \ge Cp^{2-\varepsilon} suffices for every such choice of t1,t2,t3t_1,t_2,t_3.

Consider first the case t1=t2=t3=1t_1=t_2=t_3=1. How large can EE be if it contains no unit equilateral triangle? We can also allow the common squared side length to vary and ask how large EE can be if it contains no equilateral triangle of any nonzero squared side length. This is Iosevich’s question about F(p)F(p).

Bennett, Iosevich, and Pakianathan [2, Theorem 1.4 and Corollary 4.2] showed that an equilateral triangle with nonzero squared side length exists in Fp2\mathbb{F}_p^2 if and only if 33 is a square in Fp\mathbb{F}_p. For p>3p>3, this is equivalent to p≡1,11(mod12)p \equiv1,11 \pmod{12}. Thus, F(p)=p2F(p)=p^2 when p≡5,7(mod12)p \equiv5,7 \pmod{12}. We therefore focus on p≡1,11(mod12)p \equiv1,11 \pmod{12}.

The restriction to nonzero squared side length matters when −1-1 is a square. In that case, the plane is partitioned into pp parallel isotropic lines, on each of which all squared distances are zero. If triples of distinct points with all three squared distances zero were also forbidden, each isotropic line would contain at most two points of the set. The set would then have at most 2p2p points.

Main results

Polansky [9, Sections 3–4], in his honors thesis, constructed twelve points modulo seven in triangular-lattice coordinates and combined copies by base-seven expansions. His lattice construction gives

F(p)≫plog⁡712,log⁡712=1.276989…,F(p) \gg p^{\log_7 12}, \qquad\log_7 12 = 1.276989\ldots,

for the problem with nonzero squared side length considered here.

Using cap sets in F3n\mathbb{F}_3^n, we improve this lower bound in both residue classes.1

Theorem 1.1. Set γ=log⁡3(2.2202)\gamma=\log_3(2.2202). There is an absolute constant c>0c>0 such that, for every prime p≡1,11(mod12)p \equiv1,11 \pmod{12},

F(p)≥c{p2γ,p≡11(mod12),p1+γ,p≡1(mod12).F(p) \ge c \begin{cases} p^{2\gamma}, & p \equiv11 \pmod{12},\\ p^{1+\gamma}, & p \equiv1 \pmod{12}. \end{cases}

Recall that a cap set in F3n\mathbb{F}_3^n is a set C⊆F3nC \subseteq\mathbb{F}_3^n for which

ξ+η+ζ=0,ξ,η,ζ∈C⟹ξ=η=ζ.\xi+\eta+\zeta=0,\qquad\xi,\eta,\zeta\in C \quad\Longrightarrow\quad\xi=\eta=\zeta.

Equivalently, CC contains no nonconstant three-term arithmetic progression. The following proposition gives a lower bound for F(p)F(p) in terms of nn and ∣C∣|C|, which is the key tool in proving Theorem 1.1.

Proposition 1.2. Let n≥1n \ge1, and let C⊆F3nC \subseteq\mathbb{F}_3^n be a nonempty cap set. For every prime p≡1,11(mod12)p \equiv1,11 \pmod{12},

F(p)≥6−2log⁡3∣C∣{p2log⁡3∣C∣/n,p≡11(mod12),p1+log⁡3∣C∣/n,p≡1(mod12).F(p) \ge6^{-2\log_3 |C|} \begin{cases} p^{2\log_3 |C|/n}, & p \equiv11 \pmod{12},\\ p^{1+\log_3 |C|/n}, & p \equiv1 \pmod{12}. \end{cases}

The exponents in Theorem 1.1 are 2γ=1.452008666…2\gamma= 1.452008666\ldots and 1+γ=1.726004333…1+\gamma= 1.726004333\ldots, respectively. Since 1+γ>8/51+\gamma> 8/5, our construction gives, for every sufficiently large prime p≡1(mod12)p \equiv1 \pmod{12}, a set that determines ≫p3\gg p^3 triangle congruence classes by [1 Theorem 1.6] yet contains no equilateral triangle of nonzero squared side length.

For the upper bound, we use a linear change of coordinates that sends each corner with nonzero step to an equilateral triangle with nonzero squared side length. Recall that a corner in Fp2\mathbb{F}_p^2 is a triple (s,t),(s+h,t),(s,t+h)(s,t),(s+h,t),(s,t+h) with h≠0h \ne0. The quantitative corners theorem of Jaber, Liu, Lovett, Ostuni, and Sawhney [5] then gives the following bound. In particular, F(p)=o(p2)F(p)=o(p^2) as p→∞p\to\infty through primes p≡1,11(mod12)p\equiv1,11\pmod{12}.

Theorem 1.3. There is an absolute constant c>0c>0 such that, for every prime p>3p>3 with p≡1,11(mod12)p\equiv1,11\pmod{12},

F(p)≤p2exp⁡[−c(log⁡p)1/600].F(p) \le p^2\exp\left[-c(\log p)^{1/600}\right].

Corollary 1.4. Let c>0c>0 be as in Theorem 1.3, and let p>3p>3 be a prime with p≡1,11(mod12)p\equiv1,11\pmod{12}. Every set E⊆Fp2E\subseteq\mathbb{F}_p^2 satisfying

∣E∣>p2exp⁡[−c(log⁡p)1/600]|E|>p^2\exp\left[-c(\log p)^{1/600}\right]

contains an equilateral triangle with nonzero squared side length.

In the continuous setting, Maga [6] constructed a compact set E⊆R2E\subseteq\mathbb{R}^2 with dim⁡H(E)=2\dim_{\mathrm{H}}(E)=2 containing no equilateral triangle. For d≥4d\ge4, Iosevich and Liu [3] proved that compact subsets of Rd\mathbb{R}^d satisfying a Frostman bound with exponent sufficiently close to dd contain an equilateral triangle.

Notation. We write f≪gf\ll g or g≫fg\gg f when f≤c0gf\le c_0g for a constant c0>0c_0>0. The implied constants are independent of the field size. We indicate any other dependence explicitly. We use log for the natural logarithm.

Proof of the key proposition

To prove Proposition 1.2, we first describe the coordinate change and linear form used to construct equilateral-triangle-free sets. We then construct integer point sets from cap sets and transfer them to Fp2\mathbb{F}_p^2.

Finite-field geometry

Let p>3p>3 be a prime. Let S={e1=(1,0),e2=(0,1)}S=\{e_1=(1,0),e_2=(0,1)\} be the standard basis of Fp2\mathbb{F}_p^2, and write (a,b)(a,b) for the coordinates of a point with respect to SS. These are the coordinates used in Section 1, so the squared length of a point is ∥(a,b)∥2=a2+b2\|(a,b)\|^2=a^2+b^2, and the dot product is (a,b)⋅(a′,b′)=aa′+bb′(a,b)\cdot(a',b')=aa'+bb'.

For the rest of this section, we assume that p≡1,11(mod12)p \equiv1,11 \pmod{12}. By quadratic reciprocity, this is exactly the condition that 33 is a square in Fp\mathbb{F}_p, and we fix r∈Fpr \in\mathbb{F}_p with r2=3r^2=3. Let

B={v1=(1,0), v2=(12,r2)}.\mathcal{B}=\left\{v_1=(1,0),\ v_2=\left(\frac{1}{2},\frac{r}{2}\right)\right\}.

be a second ordered basis of Fp2\mathbb{F}_p^2, written in the coordinates (a,b)(a,b), and write (s,t)(s,t) for the coordinates of a point with respect to B\mathcal{B}. The map

Φ:Fp2⟶Fp2,Φ(s,t)=(s+t2,rt2),\Phi:\mathbb{F}_p^2\longrightarrow\mathbb{F}_p^2,\qquad\Phi(s,t)=\left(s+\frac{t}{2},\frac{rt}{2}\right),

converts (s,t)(s,t)-coordinates into (a,b)(a,b)-coordinates:

(a,b)=Φ(s,t)=sv1+tv2.(a,b)=\Phi(s,t)=sv_1+tv_2.

It is invertible, since its determinant is r/2≠0r/2\ne0. To distinguish the two coordinate systems, we write

Fp2=(Fp2,(s,t)),(Fp2)′=(Fp2,(a,b)),\mathbb{F}_p^2=(\mathbb{F}_p^2,(s,t)),\qquad(\mathbb{F}_p^2)'=(\mathbb{F}_p^2,(a,b)),

so that Φ:Fp2→(Fp2)′\Phi:\mathbb{F}_p^2\to(\mathbb{F}_p^2)', and (Fp2)′(\mathbb{F}_p^2)' is the plane of Section 1 in which F(p)F(p) is defined.

We recall the criterion for equilateral triangles from [2] and verify the identities needed below. Define

R:Fp2⟶Fp2,R(s,t)=(−t,s+t),Q:Fp2⟶Fp,Q(s,t)=s2+st+t2,T:(Fp2)′⟶(Fp2)′,T(a,b)=(a−rb2,ra+b2).\begin{aligned} R:\mathbb{F}_p^2&\longrightarrow\mathbb{F}_p^2, & R(s,t)&=(-t,s+t),\\ Q:\mathbb{F}_p^2&\longrightarrow\mathbb{F}_p, & Q(s,t)&=s^2+st+t^2,\\ T:(\mathbb{F}_p^2)'&\longrightarrow(\mathbb{F}_p^2)', & T(a,b)&=\left(\frac{a-rb}{2},\frac{ra+b}{2}\right). \end{aligned}

Direct computations show that for every (s,t)∈Fp2(s,t)\in\mathbb{F}_p^2,

Φ(R(s,t))=T(Φ(s,t)),∥Φ(s,t)∥2=Q(s,t),Q(R(s,t))=Q(s,t).\Phi(R(s,t))=T(\Phi(s,t)),\qquad\lVert\Phi(s,t)\rVert^2=Q(s,t),\qquad Q(R(s,t))=Q(s,t).

The formulas for RR and QQ have integer coefficients. We use the same formulas to define R:Z2→Z2R:\mathbb{Z}^2\to\mathbb{Z}^2 and Q:Z2→ZQ:\mathbb{Z}^2\to\mathbb{Z}, and also over R\mathbb{R}. Over R\mathbb{R}, the form QQ is positive definite because Q(s,t)=(s+t/2)2+3t2/4Q(s,t)=(s+t/2)^2+3t^2/4.

Notations. Throughout, for a prime pp, we identify Fp={0ˉ,…,p−1}\mathbb{F}_p=\{\bar{0},\ldots,p-1\}. For m≥1m\ge1 and the rings F=Fp,Z\mathbb{F}=\mathbb{F}_p,\mathbb{Z}, the map Im:Fm→FmI_m:\mathbb{F}^m\to\mathbb{F}^m denotes the identity map. The map π:Zm→Fpm\pi:\mathbb{Z}^m\to\mathbb{F}_p^m denotes the natural projection; and θ:Fpm→Zm\theta:\mathbb{F}_p^m\to\mathbb{Z}^m denotes a set-theoretic section of π\pi, i.e., π∘θ=Im\pi\circ\theta=I_m on Fpm\mathbb{F}_p^m, such that Im⁡(θ)={0,…,p−1}m\operatorname{Im}(\theta)=\{0,\ldots,p-1\}^m. For a subset BB of Fpm\mathbb{F}_p^m, let B~:=θ(B)\widetilde{B}:=\theta(B), which is referred to as a lift of BB (along π\pi). For v∈Zmv\in\mathbb{Z}^m, we denote vˉ=π(v)\bar{v}=\pi(v).

Conventions. The letters X,Y,ZX,Y,Z denote points of (Fp2)′(\mathbb{F}_p^2)', and the letters x,y,zx,y,z denote points of Fp2\mathbb{F}_p^2. The letters ξ,η,ζ\xi,\eta,\zeta denote points of Fpn\mathbb{F}_p^n, (Fp2)n(\mathbb{F}_p^2)^n, or Z2n\mathbb{Z}^{2n}, including integer points of Z2\mathbb{Z}^2. Scalars in Fp\mathbb{F}_p obtained from the linear form ℓ\ell of Lemma 2.1(iv) are denoted u,u1,u2,u3u,u_1,u_2,u_3.

Lemma 2.1. Let p>3p>3 be a prime. Then the following hold.

(i) An equilateral triangle with nonzero squared side length exists in (Fp2)′(\mathbb{F}_p^2)' if and only if p≡1,11(mod12)p\equiv1,11 \pmod{12}.

Suppose that p≡1,11(mod12)p \equiv1,11 \pmod{12}, and let rr, Φ\Phi, RR, QQ, and TT be as above.

(ii) Three points X,Y,Z∈(Fp2)′X,Y,Z \in(\mathbb{F}_p^2)' form an equilateral triangle with nonzero squared side length if and only if, after possibly interchanging XX and YY,

Z−X=T(Y−X)and∥Y−X∥2≠0.Z-X=T(Y-X) \qquad\text{and} \qquad\lVert Y-X\rVert^2 \ne0.

(iii) For x,y,z∈Fp2x,y,z \in\mathbb{F}_p^2, the points Φ(x),Φ(y),Φ(z)∈(Fp2)′\Phi(x),\Phi(y),\Phi(z) \in(\mathbb{F}_p^2)' form an equilateral triangle with nonzero squared side length if and only if, after possibly interchanging xx and yy,

z−x=R(y−x)andQ(y−x)≠0.(2)z-x=R(y-x) \qquad\text{and} \qquad Q(y-x)\ne0. \tag*{(2)}

(iv) Suppose additionally that p≡1(mod12)p\equiv1\pmod{12}. There exists λ∈Fp\lambda\in\mathbb{F}_p satisfying λ2−λ+1=0\lambda^2-\lambda+1=0. The linear form

ℓ:Fp2⟶Fp,ℓ(s,t)=s+λt,\ell:\mathbb{F}_p^2\longrightarrow\mathbb{F}_p,\qquad\ell(s,t)=s+\lambda t,

satisfies

ℓ(R(s,t))=λℓ(s,t),Q(s,t)=ℓ(s,t)(s+λ−1t)(3)\begin{aligned} \ell(R(s,t))&=\lambda\ell(s,t),\\ Q(s,t)&=\ell(s,t)(s+\lambda^{-1}t) \tag*{(3)} \end{aligned}

for every (s,t)∈Fp2(s,t)\in\mathbb{F}_p^2.

Parts (ii) and (iii) characterize equilateral triangles with nonzero squared side length by linear equations. The map TT preserves squared lengths and has determinant 11, so we call it a rotation; over R\mathbb{R}, taking r=3r=\sqrt{3} gives rotation through 60∘60^\circ. We call (2) the rotation equation, which is a main tool in our argument.

Part (iv) provides a linear form whose fibers ℓ−1(u)\ell^{-1}(u), with u∈Fpu\in\mathbb{F}_p, are parallel affine lines in Fp2\mathbb{F}_p^2. If x,y∈Fp2x,y\in\mathbb{F}_p^2 satisfy ℓ(x)=ℓ(y)\ell(x)=\ell(y), then (3) gives

Q(y−x)=0,∥Φ(y)−Φ(x)∥2=0.Q(y-x)=0,\qquad\lVert\Phi(y)-\Phi(x)\rVert^2=0.

Thus, Φ\Phi sends these fibers to parallel isotropic lines in (Fp2)′(\mathbb{F}_p^2)'. Note that the map ℓ\ell is defined only in the case p≡1(mod12)p\equiv1\pmod{12}. Using this map, we will obtain a better bound in Proposition 1.2 in this case

Proof. Define J(a,b)=(−b,a)J(a,b)=(-b,a). Suppose that X,Y,ZX,Y,Z form an equilateral triangle with nonzero squared side length τ\tau. Put W=Y−XW=Y-X and W′=Z−XW'=Z-X. Then

∥W∥2=∥W′∥2=τ,W⋅W′=τ/2.\lVert W\rVert^2=\lVert W'\rVert^2=\tau,\qquad W\cdot W'=\tau/2.

Since det⁡(W,JW)=τ≠0\det(W,JW)=\tau\ne0, the vectors W,JWW,JW form a basis. Using W⋅JW=0W\cdot JW=0, we can write

W′=12W+ρ2JWW'=\frac{1}{2}W+\frac{\rho}{2}JW

for some ρ∈Fp\rho\in\mathbb{F}_p. Direct computation show that

∥W′∥2=1+ρ24∥W∥2.\lVert W'\rVert^2=\frac{1+\rho^2}{4}\lVert W\rVert^2.

Thus we have

ρ=1+ρ24ρ.\rho= \frac{1+\rho^2}{4}\rho.

so ρ2=3\rho^2=3. By quadratic reciprocity, this implies p≡1,11(mod12)p\equiv1,11\pmod{12}. Conversely, if r2=3r^2=3, then (0,0),(2,0),(1,r)(0,0),(2,0),(1,r) form an equilateral triangle of nonzero squared side length. This proves (i).

For (ii), direct computation gives

T=12I2+r2J,T−1=I2−T,∥Tw∥2=∣w∣2,∥(T−I2)w∥2=∥w∥2.(4)T=\frac{1}{2}I_2+\frac{r}{2}J,\qquad T^{-1}=I_2-T,\qquad\lVert T w\rVert^2=|w|^2,\qquad\lVert(T-I_2)w\rVert^2=\lVert w\rVert^2. \tag*{(4)}

Since ρ=±r\rho=\pm r, the calculation in (i) shows that either Z−X=T(Y−X)Z-X=T(Y-X) or Z−X=T−1(Y−X)Z-X=T^{-1}(Y-X). In the latter case, T−1=I2−TT^{-1}=I_2-T gives

Z−Y=T(X−Y).Z-Y=T(X-Y).

Thus, after possibly interchanging XX and YY, we obtain the required equation. Conversely, if Z−X=T(Y−X)Z-X=T(Y-X) and ∥Y−X∥2≠0\lVert Y-X\rVert^2\ne0, then using (4) with w=Y−Xw=Y-X, we can show that X,Y,ZX,Y,Z form an equilateral triangle with nonzero squared side length. This proves (ii).

For (iii), apply (ii) to Φ(x),Φ(y),Φ(z)\Phi(x),\Phi(y),\Phi(z). Since Φ\Phi is a linear bijection satisfying ΦR=TΦ\Phi R=T\Phi and ∥Φ(w)∥2=Q(w)\lVert\Phi(w)\rVert^2=Q(w), the conditions in (ii) are equivalent to

z−x=R(y−x),Q(y−x)≠0,z-x=R(y-x),\qquad Q(y-x)\ne0,

after possibly interchanging xx and yy. This proves (iii).

Finally, suppose that p≡1(mod12)p\equiv1\pmod{12}. Choose ι∈Fp\iota\in\mathbb{F}_p with ι2=−1\iota^2=-1, and set λ=(1+ιr)/2\lambda=(1+\iota r)/2. Then

λ(1−λ)=1+r24=1,\lambda(1-\lambda)=\frac{1+r^2}{4}=1,

so λ2−λ+1=0\lambda^2-\lambda+1=0 and λ−1=1−λ\lambda^{-1}=1-\lambda. For ℓ(s,t)=s+λt\ell(s,t)=s+\lambda t, we obtain

ℓ(R(s,t))=−t+λ(s+t)=λ(s+λt)=λℓ(s,t),\ell(R(s,t))=-t+\lambda(s+t)=\lambda(s+\lambda t)=\lambda\ell(s,t),

and

(s+λt)(s+λ−1t)=s2+st+t2=Q(s,t).(s+\lambda t)(s+\lambda^{-1}t)=s^2+st+t^2=Q(s,t).

This proves (iv), completing the proof.

Encoding a cap set by integer points

We construct integer point sets for which the rotation equation forces the three points to coincide. The construction has three steps, and we state each as a separate lemma.

For n≥1n\ge1, let RR act on (F32)n(\mathbb{F}_3^2)^n and on Z2n\mathbb{Z}^{2n} by applying the formula for RR to each coordinate pair:

R((sj,tj)j=0n−1)=((−tj,sj+tj))j=0n−1.R\left((s_j,t_j)_{j=0}^{n-1}\right)=\left((-t_j,s_j+t_j)\right)_{j=0}^{n-1}.

For n=1n=1, this is the map RR itself. We say that a subset SS of (F32)n(\mathbb{F}_3^2)^n or of Z2n\mathbb{Z}^{2n} is rotation-free if

ζ=(I2n−R)ξ+Rη,ξ,η,ζ∈S⟹ξ=η=ζ.\zeta=(I_{2n}-R)\xi+R\eta,\qquad\xi,\eta,\zeta\in S\Longrightarrow\xi=\eta=\zeta.

with arithmetic in F3\mathbb{F}_3 or in Z\mathbb{Z}, respectively. Lemma 2.2 produces a rotation-free subset of (F32)n(\mathbb{F}_3^2)^n from a cap set. Lemma 2.3 lifts it to integer vectors by base-three expansions, and Lemma 2.4 packs the integer vectors into the plane by expansions in a larger base. Proposition 2.5 combines the three steps.

Lemma 2.2. Let n≥1n \ge1, and let C⊆F3nC \subseteq\mathbb{F}_3^n be a cap set. Define

D={((sj,tj))j=0n−1∈(F32)n:(sj−tj)j=0n−1∈C, (sj)j=0n−1∈C}.D = \left\{ ((s_j,t_j))_{j=0}^{n-1} \in(\mathbb{F}_3^2)^n : (s_j-t_j)_{j=0}^{n-1} \in C,\ (s_j)_{j=0}^{n-1} \in C \right\}.

Then DD is rotation-free and ∣D∣=∣C∣2|D| = |C|^2.

Proof. We take a change of coordinates for which RR is triangular over F3\mathbb{F}_3. For

ξ=((sj,tj))j=0n−1∈(F32)n,\xi= ((s_j,t_j))_{j=0}^{n-1} \in(\mathbb{F}_3^2)^n,

define

αξ=(sj−tj)j=0n−1∈F3n,βξ=(sj)j=0n−1∈F3n.\alpha_\xi= (s_j-t_j)_{j=0}^{n-1} \in\mathbb{F}_3^n,\qquad\beta_\xi= (s_j)_{j=0}^{n-1} \in\mathbb{F}_3^n.

Define

σ:F32n=(F32)n⟶F3n×F3n=F32n,σ(ξ)=(αξ,βξ).\sigma: \mathbb{F}_3^{2n} = (\mathbb{F}_3^2)^n \longrightarrow\mathbb{F}_3^n \times\mathbb{F}_3^n = \mathbb{F}_3^{2n},\qquad\sigma(\xi) = (\alpha_\xi,\beta_\xi).

Then σ\sigma is a linear isomorphism with inverse

σ−1(α,β)=((βj,βj−αj))j=0n−1,α=(αj)j=0n−1, β=(βj)j=0n−1∈F3n.\sigma^{-1}(\alpha,\beta) = ((\beta_j,\beta_j-\alpha_j))_{j=0}^{n-1},\qquad\alpha=(\alpha_j)_{j=0}^{n-1},\ \beta=(\beta_j)_{j=0}^{n-1} \in\mathbb{F}_3^n.

Identifying (F32)n=F32n(\mathbb{F}_3^2)^n = \mathbb{F}_3^{2n} and (F3n)2=F32n(\mathbb{F}_3^n)^2 = \mathbb{F}_3^{2n}, σ\sigma makes a change of coordinates. Let R′=σ∘R∘σ−1R' = \sigma\circ R \circ\sigma^{-1}, so that the diagram

(F32)n→σ(F3n)2R↓↓R′(F32)n→σ(F3n)2\begin{CD} (\mathbb{F}_3^2)^n @>\sigma>> (\mathbb{F}_3^n)^2 \\ @V R VV @VV R' V \\ (\mathbb{F}_3^2)^n @>\sigma>> (\mathbb{F}_3^n)^2 \end{CD}

commutes. A direct computation using 3=03=0 in F3\mathbb{F}_3 shows

R′(α,β)=(−α,α−β),(α,β)∈(F3n)2.R'(\alpha,\beta)=(-\alpha,\alpha-\beta),\qquad(\alpha,\beta)\in(\mathbb{F}_3^n)^2.

The set DD is the inverse image of C×CC \times C under σ\sigma:

D=σ−1(C×C)={ξ∈(F32)n:αξ∈C, βξ∈C}={((βj,βj−αj))j=0n−1:α,β∈C}.D = \sigma^{-1}(C \times C) = \left\{ \xi\in(\mathbb{F}_3^2)^n : \alpha_\xi\in C,\ \beta_\xi\in C \right\} = \left\{ ((\beta_j,\beta_j-\alpha_j))_{j=0}^{n-1} : \alpha,\beta\in C \right\}.

Hence, ∣D∣=∣C∣2|D|=|C|^2.

If ζ=(I2n−R)ξ+Rη\zeta= (I_{2n}-R)\xi+R\eta with ξ,η,ζ∈D\xi,\eta,\zeta\in D, then applying σ\sigma and the formula for R′R' gives

αζ=αξ−(−αξ)+(−αη)=2αξ−αη,βζ=βξ−(αξ−βξ)+(αη−βη)=2βξ−αξ+αη−βη.\alpha_\zeta= \alpha_\xi- (-\alpha_\xi) + (-\alpha_\eta) = 2\alpha_\xi-\alpha_\eta,\qquad\beta_\zeta= \beta_\xi- (\alpha_\xi-\beta_\xi) + (\alpha_\eta-\beta_\eta) = 2\beta_\xi-\alpha_\xi+\alpha_\eta-\beta_\eta.

Since 2=−12=-1 in F3\mathbb{F}_3, rearranging gives

αξ+αη+αζ=0,βξ+βη+βζ=αη−αξ.\alpha_\xi+\alpha_\eta+\alpha_\zeta=0,\qquad\beta_\xi+\beta_\eta+\beta_\zeta=\alpha_\eta-\alpha_\xi.

By the definition of a cap set, we have αξ=αη=αζ\alpha_\xi=\alpha_\eta=\alpha_\zeta, and hence βξ=βη=βζ\beta_\xi=\beta_\eta=\beta_\zeta. Since σ\sigma is injective, ξ=η=ζ\xi=\eta=\zeta. Thus, DD is rotation-free, as desired.

Let BB be any subset of (F3)n(\mathbb{F}_3)^n, so that B~\widetilde{B} is a subset of (Z2)n(\mathbb{Z}^2)^n. For each k≥1k \ge1, define Γ:(B~)k→Z2n\Gamma: \left(\widetilde{B}\right)^k \to\mathbb{Z}^{2n} by

Γ(δ0,…,δk−1)=∑i=0k−13iδi.\Gamma(\delta_0,\ldots,\delta_{k-1})=\sum_{i=0}^{k-1}3^i\delta_i.

Let EkE_k be the image of Γ\Gamma. Then, for each component νj\nu_j of an element ν\nu of EkE_k, we have 0≤νj≤3k−10 \le\nu_j \le3^k-1. Thus, Ek⊆{0,…,3k−1}2nE_k \subseteq\{0,\ldots,3^k-1\}^{2n}.

For ξ∈Ek\xi\in E_k, δξ,j\delta_{\xi,j} denotes δj∈B~\delta_j \in\widetilde{B} for j=0,…,k−1j=0,\ldots,k-1, where ξ=Γ(δ0,…,δk−1)\xi=\Gamma(\delta_0,\ldots,\delta_{k-1}). Note that ξ≡δξ,0\xi\equiv\delta_{\xi,0} (mod 3) by the definition of ξ\xi.

Lemma 2.3. Let n≥1n \ge1, let BB be a subset of (F3)n(\mathbb{F}_3)^n and let EkE_k be as above for k≥1k \ge1. Then the following hold.

(i) For each k≥1k \ge1, Γ\Gamma is injective, and so ∣Ek∣=∣B∣k|E_k|=|B|^k.

(ii) If BB is rotation-free, then so is EkE_k in Z2n\mathbb{Z}^{2n} for every k≥1k \ge1.

Proof. (i): Injectivity of Γ\Gamma follows from uniqueness of base-three expansions. Since Γ\Gamma is injective, we have ∣Ek∣=∣B∣k|E_k|=|B|^k.

(ii): We proceed by induction on kk. Suppose that ξ,η,ζ∈Ek\xi,\eta,\zeta\in E_k satisfy

ζ=(I2n−R)ξ+Rη.(5)\zeta=(I_{2n}-\mathcal{R})\xi+\mathcal{R}\eta. \tag*{(5)}

Since ξ≡δξ,0\xi\equiv\delta_{\xi,0}, η≡δη,0\eta\equiv\delta_{\eta,0}, ζ≡δζ,0\zeta\equiv\delta_{\zeta,0} (mod 3), the equation (5) reduces to

δζ,0≡(I2n−R)δξ,0+Rδη,0(mod3).(6)\delta_{\zeta,0}\equiv(I_{2n}-\mathcal{R})\delta_{\xi,0}+\mathcal{R}\delta_{\eta,0}\pmod{3}. \tag*{(6)}

Let δ‾ξ,0,δ‾η,0,δ‾ζ,0∈B\overline{\delta}_{\xi,0},\overline{\delta}_{\eta,0},\overline{\delta}_{\zeta,0}\in B be images under π\pi of the elements δξ,0,δη,0,δζ,0∈B~\delta_{\xi,0},\delta_{\eta,0},\delta_{\zeta,0}\in\widetilde{B}. By (6), we have, over F3\mathbb{F}_3,

δ‾ζ,0=(I2n−R)δ‾ξ,0+Rδ‾η,0.(7)\overline{\delta}_{\zeta,0}=(I_{2n}-\mathcal{R})\overline{\delta}_{\xi,0}+\mathcal{R}\overline{\delta}_{\eta,0}. \tag*{(7)}

Since BB is rotation-free, we have

δ‾ξ,0=δ‾η,0=δ‾ζ,0.\overline{\delta}_{\xi,0}=\overline{\delta}_{\eta,0}=\overline{\delta}_{\zeta,0}.

Applying θ\theta to this equality, we obtain

δξ,0=δη,0=δζ,0,\delta_{\xi,0}=\delta_{\eta,0}=\delta_{\zeta,0},

since θ(π(δ))=δ\theta(\pi(\delta))=\delta for every δ∈B~\delta\in\widetilde{B}. If k=1k=1, which is the base case for the induction, then E1=B~E_1=\widetilde{B} and

δξ,0=ξ,δη,0=η,δζ,0=ζ.\delta_{\xi,0}=\xi,\qquad\delta_{\eta,0}=\eta,\qquad\delta_{\zeta,0}=\zeta.

Thus, ξ=η=ζ\xi=\eta=\zeta, and so E1E_1 is rotation-free.

Now assume k≥2k \ge2. Write δ0:=δξ,0=δη,0=δζ,0\delta_0:=\delta_{\xi,0}=\delta_{\eta,0}=\delta_{\zeta,0}. Define ξ′,η′,ζ′\xi',\eta',\zeta' by

ξ=δ0+3ξ′,η=δ0+3η′,ζ=δ0+3ζ′.\xi=\delta_0+3\xi',\qquad\eta=\delta_0+3\eta',\qquad\zeta=\delta_0+3\zeta'.

Substitute these into (5):

δ0+3ζ′=(I2n−R)(δ0+3ξ′)+R(δ0+3η′).\delta_0+3\zeta'=(I_{2n}-\mathcal{R})(\delta_0+3\xi')+\mathcal{R}(\delta_0+3\eta').

Then since (I2n−R)+R=I2n(I_{2n}-R)+R=I_{2n}, we obtain

ζ′=(I2n−R)ξ′+Rη′.\zeta'=(I_{2n}-R)\xi'+R\eta'.

Note that ξ′,η′,ζ′\xi',\eta',\zeta' are elements of Ek−1E_{k-1}. By the induction hypothesis that Ek−1E_{k-1} is rotation-free, we obtain ξ′=η′=ζ′\xi'=\eta'=\zeta'. Thus, ξ=η=ζ\xi=\eta=\zeta, and so EkE_k is rotation-free.

Let N≥1N\ge1 be an integer. Define Ψ:(Z2)n→Z2\Psi:(\mathbb{Z}^{2})^n\to\mathbb{Z}^{2} by

Ψ(ξ):=(∑j=0n−1Njsj,∑j=0n−1Njtj)=∑j=0n−1Nj(sj,tj),\Psi(\xi):=\left(\sum_{j=0}^{n-1}N^j s_j,\sum_{j=0}^{n-1}N^j t_j\right)=\sum_{j=0}^{n-1}N^j(s_j,t_j),

where ξ=((sj,tj))j=0n−1∈(Z2)n\xi=((s_j,t_j))_{j=0}^{n-1}\in(\mathbb{Z}^{2})^n.

For ξ=((sj,tj))j=0n−1\xi=((s_j,t_j))_{j=0}^{n-1}, let ξ(j)\xi^{(j)} be the jj-th coordinate pair, i.e., ξ(j)=(sj,tj)\xi^{(j)}=(s_j,t_j).

Lemma 2.4. Let n≥1n\ge1 and fix an integer M≥0M\ge0. Let GG be a subset of Z2n\mathbb{Z}^{2n} with G⊆{0,…,M}2nG\subseteq\{0,\ldots,M\}^{2n}.

(i) If N≥max⁡{2,2M+1}N\ge\max\{2,2M+1\}, then Ψ\Psi is injective on GG, and

Ψ(G)⊆{0,…,MNn−1N−1}2.\Psi(G)\subseteq\left\{0,\ldots,M\frac{N^n-1}{N-1}\right\}^{2}.

(ii) If N≥max⁡{2,2M+1}N\ge\max\{2,2M+1\} and GG is rotation-free, then so is Ψ(G)\Psi(G) in Z2\mathbb{Z}^{2}.

Proof. (i): Since 0≤sj,tj≤M<N0\le s_j,t_j\le M<N for ξ∈G\xi\in G, injectivity of Ψ\Psi on GG follows from uniqueness of base-NN expansions. Both coordinates of Ψ(ξ)\Psi(\xi) lie between 00 and

M∑j=0n−1Nj=MNn−1N−1.M\sum_{j=0}^{n-1}N^j=M\frac{N^n-1}{N-1}.

(ii): To prove (ii), assume that for ξ,η,ζ∈G\xi,\eta,\zeta\in G

Ψ(ζ)=(I2−R)Ψ(ξ)+RΨ(η).(8)\Psi(\zeta)=(I_2-R)\Psi(\xi)+R\Psi(\eta). \tag*{(8)}

Let us show that Ψ(ξ)=Ψ(η)=Ψ(ζ)\Psi(\xi)=\Psi(\eta)=\Psi(\zeta). For each j=0,…,n−1j=0,\ldots,n-1, let e(j)∈Z2e^{(j)}\in\mathbb{Z}^{2} be the jj-th error term defined by

e(j)=ζ(j)−(I2−R)ξ(j)−Rη(j).e^{(j)}=\zeta^{(j)}-(I_2-R)\xi^{(j)}-R\eta^{(j)}.

Using the fact that Ψ∘R=R∘Ψ\Psi\circ R=R\circ\Psi, and R,RR,\mathcal{R} are linear, from (8) we can derive

∑j=0n−1Nje(j)=0.(9)\sum_{j=0}^{n-1}N^j e^{(j)}=0. \tag*{(9)}

By rewriting the equality (9) as

e(0)=(e1(0),e2(0))=−N∑j=1n−1Nj−1e(j),e^{(0)}=(e_1^{(0)},e_2^{(0)})=-N\sum_{j=1}^{n-1}N^{j-1}e^{(j)},

we can easily see that each component ei(0)e_i^{(0)} of e(0)e^{(0)} (i=1,2i=1,2) is divisible by NN in Z\mathbb{Z}.

On the other hand, each component ei(j)e_i^{(j)} of e(j)e^{(j)} is, by definition, a sum of two entries minus two entries for i=1,2i=1,2, and each entry lies between 00 and MM, so for every j=0,…,n−1j=0,\ldots,n-1,

∣e1(j)∣,∣e2(j)∣≤2M≤N−1.\lvert e_1^{(j)}\rvert,\lvert e_2^{(j)}\rvert\le2M \le N-1.

For j=0j=0, since ei(0)e_i^{(0)} is a multiple of NN and ∣ei(0)∣≤N−1\lvert e_i^{(0)}\rvert\le N-1 for i=1,2i=1,2 we have ei(0)=0e_i^{(0)}=0, so e(0)=(0,0)e^{(0)}=(0,0).

Removing this zero term from (9) gives ∑j=1n−1Nje(j)=0\sum_{j=1}^{n-1}N^j e^{(j)}=0. After dividing by NN, the same argument gives e(1)=(0,0)e^{(1)}=(0,0) if n≥2n\ge2. Continuing this process, we obtain

e(0)=e(1)=⋯=e(n−1)=(0,0).e^{(0)}=e^{(1)}=\cdots=e^{(n-1)}=(0,0).

Thus, ξ,η,ζ∈G\xi,\eta,\zeta\in G satisfy

ζ=(I2n−R)ξ+Rη.\zeta=(I_{2n}-R)\xi+R\eta.

Since GG is rotation-free, we have ξ=η=ζ\xi=\eta=\zeta. Therefore Ψ(ξ)=Ψ(η)=Ψ(ζ)\Psi(\xi)=\Psi(\eta)=\Psi(\zeta). Thus, the subset Ψ(G)⊂Z2\Psi(G)\subset\mathbb{Z}^2 is rotation-free.

We now combine the three lemmas.

Proposition 2.5. Let n≥1n\ge1 and C⊆F3nC\subseteq\mathbb{F}_3^n be a nonempty cap set. For every integer k≥0k\ge0, define

Nk=2⋅3k−1.N_k=2\cdot3^k-1.

There is an explicit set

Sk⊂{0,…,Nkn−12}2,∣Sk∣=∣C∣2k,S_k\subset\left\{0,\ldots,\frac{N_k^n-1}{2}\right\}^2,\qquad\lvert S_k\rvert=\lvert C\rvert^{2k},

such that

ζ=(I2−R)ξ+Rη,ξ,η,ζ∈Sk⟹ξ=η=ζ.\zeta=(I_2-R)\xi+R\eta,\qquad\xi,\eta,\zeta\in S_k\quad\Longrightarrow\quad\xi=\eta=\zeta.

Proof. For k=0k=0, take S0={(0,0)}S_0=\{(0,0)\}. Assume henceforth that k≥1k\ge1. Let DD be the rotation-free set of Lemma 2.2, so that ∣D∣=∣C∣2\lvert D\rvert=\lvert C\rvert^2. Next, we apply Lemma 2.3 to B=DB=D. Then we obtain the rotation-free subset Ek⊆{0,…,3k−1}2nE_k\subseteq\{0,\ldots,3^k-1\}^{2n} such that ∣Ek∣=∣D∣k=∣C∣2k\lvert E_k\rvert=\lvert D\rvert^k=\lvert C\rvert^{2k}. Lastly, apply Lemma 2.4 with M=3k−1M=3^k-1 and N=Nk=2M+1N=N_k=2M+1, and set Sk=Ψ(Ek)S_k=\Psi(E_k). Then ∣Sk∣=∣Ek∣=∣C∣2k\lvert S_k\rvert=\lvert E_k\rvert=\lvert C\rvert^{2k}, the set SkS_k is rotation-free in Z2\mathbb{Z}^2, and its coordinates lie between 00 and

MNkn−1Nk−1=Nkn−12,M\frac{N_k^n-1}{N_k-1}=\frac{N_k^n-1}{2},

since Nk−1=2MN_k-1=2M. This proves the proposition.

From integer points to the finite plane

We now use the integer sets from Proposition 2.5 to construct equilateral-triangle-free subsets of Fp2\mathbb{F}_p^2.

Proof of Proposition 1.2. We use direct reduction modulo pp when p≡11(mod12)p\equiv11\pmod{12}. When p≡1(mod12)p\equiv1\pmod{12}, we first construct a scalar set and then use parallel isotropic lines to gain a factor of pp. We finish by choosing the largest admissible scale in each case.

Let SkS_k be the set from Proposition 2.5, with Nk=2⋅3k−1N_k = 2 \cdot3^k - 1. Thus, ∣Sk∣=∣C∣2k|S_k| = |C|^{2k}, and

ζ=(I2−R)ξ+Rη in Z2,ξ,η,ζ∈Sk⟹ξ=η=ζ.\zeta= (I_2 - R)\xi+ R\eta\text{ in } \mathbb{Z}^2,\qquad\xi,\eta,\zeta\in S_k \Longrightarrow\xi= \eta= \zeta.

Let π:Z2→Fp2\pi: \mathbb{Z}^2 \to\mathbb{F}_p^2 be reduction modulo pp, and write ξˉ=π(ξ)\bar{\xi} = \pi(\xi) for ξ∈Z2\xi\in\mathbb{Z}^2. Since RR has integer coefficients, π(Rξ)=Rξˉ\pi(R\xi) = R\bar{\xi}. We will obtain equations modulo pp and use the coordinate bounds to recover the exact integer equation above. For ξ,η,ζ∈Sk\xi,\eta,\zeta\in S_k, define the integer vector e=ζ−(I2−R)ξ−Rηe = \zeta- (I_2 - R)\xi- R\eta. Then

e1=ζ1−ξ1−ξ2+η2,e2=ζ2+ξ1−η1−η2,e1+e2=ζ1+ζ2−ξ2−η1.\begin{aligned} e_1 &= \zeta_1 - \xi_1 - \xi_2 + \eta_2,\\ e_2 &= \zeta_2 + \xi_1 - \eta_1 - \eta_2,\\ e_1 + e_2 &= \zeta_1 + \zeta_2 - \xi_2 - \eta_1. \end{aligned}

Note that each of e1e_1, e2e_2, e1+e2e_1 + e_2 is expressed as a sum of two entries minus two entries. Since every entry lies between 00 and (Nkn−1)/2(N_k^n - 1)/2, we obtain

∣e1∣, ∣e2∣, ∣e1+e2∣≤Nkn−1.(10)|e_1|,\ |e_2|,\ |e_1 + e_2| \le N_k^n - 1. \tag*{(10)}

The case p≡11(mod12)p \equiv11 \pmod{12}. Choose kk with Nkn≤pN_k^n \le p. Define

E=Φ(π(Sk))⊆(Fp2)′.E = \Phi(\pi(S_k)) \subseteq(\mathbb{F}_p^2)'.

Reduction modulo pp is injective on SkS_k, since its coordinates lie between 00 and (p−1)/2(p - 1)/2. As Φ\Phi is also invertible, ∣E∣=∣Sk∣=∣C∣2k|E| = |S_k| = |C|^{2k}.

Suppose that X,Y,Z∈EX,Y,Z \in E form an equilateral triangle with nonzero squared side length. Choose the unique ξ,η,ζ∈Sk\xi,\eta,\zeta\in S_k such that

X=Φ(ξˉ),Y=Φ(ηˉ),Z=Φ(ζˉ).X = \Phi(\bar{\xi}),\qquad Y = \Phi(\bar{\eta}),\qquad Z = \Phi(\bar{\zeta}).

By (2), after possibly interchanging X,YX,Y and the corresponding ξ,η\xi,\eta, we have

ζˉ=(I2−R)ξˉ+Rηˉin Fp2.\bar{\zeta} = (I_2 - R)\bar{\xi} + R\bar{\eta}\quad\text{in }\mathbb{F}_p^2.

Thus, the integer error e=ζ−(I2−R)ξ−Rηe = \zeta- (I_2 - R)\xi- R\eta satisfies π(e)=0\pi(e) = 0, so p∣e1,e2p \mid e_1,e_2. On the other hand, (10) gives

∣e1∣,∣e2∣≤Nkn−1<p.|e_1|,|e_2| \le N_k^n - 1 < p.

Hence, e=0e = 0, and we have the exact equality

ζ=(I2−R)ξ+Rηin Z2.\zeta= (I_2 - R)\xi+ R\eta\quad\text{in }\mathbb{Z}^2.

Proposition 2.5 now gives ξ=η=ζ\xi= \eta= \zeta, so X=Y=ZX = Y = Z, a contradiction. Therefore,

F(p)≥∣C∣2kwhenever Nkn≤p.(11)F(p) \ge|C|^{2k}\qquad\text{whenever }N_k^n \le p. \tag*{(11)}

The case p≡1(mod12)p \equiv1 \pmod{12}. The argument made so far in the case p≡11(mod12)p \equiv11 \pmod{12} applies verbatim when p≡1(mod12)p \equiv1 \pmod{12}. However, the case p≡1(mod12)p \equiv1 \pmod{12} is more favorable since there are isotropic lines in (Fp2)′(\mathbb{F}_p^2)'. Using this advantage we shall find a better bound in this case.

Choose kk with Nkn≤pN_k^n \le\sqrt{p}. Let λ\lambda and ℓ\ell be as in Lemma 2.1(iv). We first show that

ℓ(ζˉ)=(1−λ)ℓ(ξˉ)+λℓ(ηˉ),ξ,η,ζ∈Sk⟹ξ=η=ζ.(12)\ell(\bar{\zeta})=(1-\lambda)\ell(\bar{\xi})+\lambda\ell(\bar{\eta}),\qquad\xi,\eta,\zeta\in S_k \quad\Longrightarrow\quad\xi=\eta=\zeta. \tag*{(12)}

Suppose that the scalar equation holds, and set e=ζ−(I2−R)ξ−Rη∈Z2e=\zeta-(I_2-R)\xi-R\eta\in\mathbb{Z}^2. The first identity in (3) gives

ℓ(eˉ)=ℓ(ζˉ)−(1−λ)ℓ(ξˉ)−λℓ(ηˉ)=0.\ell(\bar{e})=\ell(\bar{\zeta})-(1-\lambda)\ell(\bar{\xi})-\lambda\ell(\bar{\eta})=0.

The second identity then yields Q(eˉ)=0Q(\bar{e})=0 in Fp\mathbb{F}_p. Equivalently, the integer Q(e)Q(e) is divisible by pp. We will show that 0≤Q(e)<p0\le Q(e)<p, which forces Q(e)=0Q(e)=0 over the integers.

For real s,ts,t,

Q(s,t)≤max⁡{s2,t2,(s+t)2}.(13)Q(s,t)\le\max\{s^2,t^2,(s+t)^2\}. \tag*{(13)}

Indeed, if st≥0st\ge0, then Q(s,t)=(s+t)2−st≤(s+t)2Q(s,t)=(s+t)^2-st\le(s+t)^2. If st<0st<0 and ∣s∣≥∣t∣|s|\ge|t|, then st+t2≤0st+t^2\le0, so Q(s,t)≤s2Q(s,t)\le s^2; the other case is symmetric. Combining (10) and (13), we obtain

0≤Q(e)≤(Nkn−1)2<p.0\le Q(e)\le(N_k^n-1)^2<p.

Since p∣Q(e)p\mid Q(e), we have Q(e)=0Q(e)=0 in Z\mathbb{Z}. Positive definiteness of QQ over the integers gives e=0e=0. Thus, ζ=(I2−R)ξ+Rη\zeta=(I_2-R)\xi+R\eta in Z2\mathbb{Z}^2, and Proposition 2.5 yields ξ=η=ζ\xi=\eta=\zeta. This proves (12).

The map ξ↦ℓ(ξˉ)\xi\mapsto\ell(\bar{\xi}) is also injective on SkS_k. Indeed, if ℓ(ξˉ)=ℓ(ηˉ)\ell(\bar{\xi})=\ell(\bar{\eta}), then

ℓ(ηˉ)=(1−λ)ℓ(ξˉ)+λℓ(ξˉ).\ell(\bar{\eta})=(1-\lambda)\ell(\bar{\xi})+\lambda\ell(\bar{\xi}).

Then (12) applied to (ξ,ξ,η)(\xi,\xi,\eta) gives ξ=η\xi=\eta. This proves the injectivity. Consequently, the set

U={ℓ(ξˉ):ξ∈Sk}⊆FpU=\{\ell(\bar{\xi}):\xi\in S_k\}\subseteq\mathbb{F}_p

has cardinality ∣U∣=∣Sk∣=∣C∣2k|U|=|S_k|=|C|^{2k}. Moreover, we claim that for u1,u2,u3∈Uu_1,u_2,u_3\in U

u3=(1−λ)u1+λu2u1,u2,u3∈U⟹u1=u2=u3.(14)u_3=(1-\lambda)u_1+\lambda u_2\qquad u_1,u_2,u_3\in U\quad\Longrightarrow\quad u_1=u_2=u_3. \tag*{(14)}

Indeed, choosing representatives ξ,η,ζ∈Sk\xi,\eta,\zeta\in S_k so that ℓ(ξˉ)=u1,ℓ(ηˉ)=u2,ℓ(ζˉ)=u3\ell(\bar{\xi})=u_1,\ell(\bar{\eta})=u_2,\ell(\bar{\zeta})=u_3, and again applying (12), we obtain u1=u2=u3u_1=u_2=u_3. Define

A=ℓ−1(U)={x∈Fp2:ℓ(x)∈U},E=Φ(A)⊆(Fp2)′.A=\ell^{-1}(U)=\{x\in\mathbb{F}_p^2:\ell(x)\in U\},\qquad E=\Phi(A)\subseteq(\mathbb{F}_p^2)'.

For each u∈Uu\in U, the fiber ℓ−1(u)\ell^{-1}(u) is the line {(s,t)∈Fp2:s+λt=u}\{(s,t)\in\mathbb{F}_p^2:s+\lambda t=u\}, which contains exactly pp points. The fibers are disjoint, and Φ\Phi is invertible, so ∣E∣=∣A∣=p∣U∣=p∣Sk∣=p∣C∣2k|E|=|A|=p|U|=p|S_k|=p|C|^{2k}.

Suppose that E⊆(Fp2)′E\subseteq(\mathbb{F}_p^2)' contains an equilateral triangle X,Y,ZX,Y,Z with nonzero squared side length. Assume that Φ(x)=X,Φ(y)=Y,Φ(z)=Z\Phi(x)=X,\Phi(y)=Y,\Phi(z)=Z for x,y,z∈A⊆Fp2x,y,z\in A\subseteq\mathbb{F}_p^2. (Note that x,y,zx,y,z are already points of Fp2\mathbb{F}_p^2, not elements of Sk⊆Z2S_k\subseteq\mathbb{Z}^2.) Reordering X,Y,ZX,Y,Z, if necessary, by (2) we obtain

z=(I2−R)x+Ry,Q(y−x)≠0.z=(I_2-R)x+Ry,\qquad Q(y-x)\ne0.

Applying ℓ\ell gives

ℓ(z)=(1−λ)ℓ(x)+λℓ(y).\ell(z)=(1-\lambda)\ell(x)+\lambda\ell(y).

Since ℓ(x),ℓ(y),ℓ(z)∈U\ell(x),\ell(y),\ell(z)\in U, by (14) we obtain

ℓ(x)=ℓ(y)=ℓ(z).\ell(x)=\ell(y)=\ell(z).

In particular, ℓ(y−x)=0\ell(y-x)=0, so (3) gives Q(y−x)=0Q(y-x)=0, a contradiction. Therefore,

F(p)≥p∣C∣2kwhenever Nkn≤p.(15)F(p) \ge p|C|^{2^k}\qquad\text{whenever }N_k^n \le\sqrt{p}. \tag*{(15)}

Let L=pL=p in (11) and L=pL=\sqrt{p} in (15). Choose the largest k≥0k\ge0 with Nkn≤LN_k^n\le L. Such a kk exists because N0=1N_0=1. Since Nk=2⋅3k−1N_k=2\cdot3^k-1, the maximal choice of kk gives

L<(2⋅3k+1−1)n<6n3kn,3k>L1/n/6.L < (2\cdot3^{k+1}-1)^n < 6^n3^{kn},\qquad3^k>L^{1/n}/6.

If ∣C∣>1|C|>1, raising the latter inequality to the power 2log⁡3∣C∣2\log_3|C| gives

∣C∣2k≥6−2log⁡3∣C∣L2log⁡3∣C∣/n.(16)|C|^{2^k}\ge6^{-2\log_3|C|}L^{2\log_3|C|/n}. \tag*{(16)}

If ∣C∣=1|C|=1, then both sides of (16) equal 1, so it trivially holds. Substituting (16) into (11) and (15), we obtain both bounds in the proposition.

Proofs of Theorems 1.1 and 1.3

We combine Proposition 1.2 with the cap set construction of Romera-Paredes et al. [10] to obtain the exponents in Theorem 1.1.

Proof of Theorem 1.1. The construction of Romera-Paredes et al. [10 p. 472 and Supplementary Information, Figure C.9] gives an integer n≥1n\ge1 and a cap set C⊆F3nC\subseteq\mathbb{F}_3^n with ∣C∣≥2.2202n=3nγ|C|\ge2.2202^n=3^{n\gamma}. Fix such nn and CC. Since log⁡3∣C∣/n≥γ\log_3|C|/n\ge\gamma, Proposition 1.2 gives the required bounds with c=6−2log⁡3∣C∣>0c=6^{-2\log_3|C|}>0. Since nn and CC are fixed independently of pp, the constant cc is absolute. This proves Theorem 1.1.

We use Φ\Phi to map each corner to an equilateral triangle with nonzero squared side length. The quantitative corners theorem then bounds the size of an equilateral-triangle-free set.

Proof of Theorem 1.3. Let E⊆(Fp2)′E\subseteq(\mathbb{F}_p^2)' contain no equilateral triangle with nonzero squared side length. Let rr and Φ\Phi be as in § 2, so that Φ−1(E)⊆Fp2\Phi^{-1}(E)\subseteq\mathbb{F}_p^2 is the same set in the coordinates (s,t)(s,t). We claim that Φ−1(E)\Phi^{-1}(E) doesn’t contain any corners. Suppose, to the contrary, that Φ−1(E)\Phi^{-1}(E) contains a corner

(s,t),(s+h,t),(s,t+h),h≠0.(s,t),\qquad(s+h,t),\qquad(s,t+h),\qquad h\ne0.

By linearity and the definition of Φ\Phi, the differences between these image points are

Φ(s+h,t)−Φ(s,t)=Φ(h,0)=(h,0),\Phi(s+h,t)-\Phi(s,t)=\Phi(h,0)=(h,0),
Φ(s,t+h)−Φ(s,t)=Φ(0,h)=(h2,rh2),\Phi(s,t+h)-\Phi(s,t)=\Phi(0,h)=\left(\frac{h}{2},\frac{rh}{2}\right),
Φ(s,t+h)−Φ(s+h,t)=Φ(−h,h)=(−h2,rh2).\Phi(s,t+h)-\Phi(s+h,t)=\Phi(-h,h)=\left(-\frac{h}{2},\frac{rh}{2}\right).

The first vector has squared length h2h^2. Since r2=3r^2=3, the other two vectors have squared lengths

(h2)2+(rh2)2=(−h2)2+(rh2)2=1+r24h2=h2.\left(\frac{h}{2}\right)^2+\left(\frac{rh}{2}\right)^2=\left(-\frac{h}{2}\right)^2+\left(\frac{rh}{2}\right)^2=\frac{1+r^2}{4}h^2=h^2.

Since h≠0h \ne0, the image points Φ(s,t),Φ(s+h,t),Φ(s,t+h)\Phi(s,t), \Phi(s+h,t), \Phi(s,t+h) in (Fp2)′(\mathbb{F}_p^2)' form an equilateral triangle with nonzero squared side length, contrary to the choice of EE. Thus, Φ−1(E)\Phi^{-1}(E) doesn’t contain any corner. Applying the corners theorem of Jaber, Liu, Lovett, Ostuni, and Sawhney [5 Theorem 1.1, full version] to the additive group Fp\mathbb{F}_p gives

∣E∣=∣Φ−1(E)∣≤p2exp⁡[−c(log⁡p)1/600].|E| = |\Phi^{-1}(E)| \le p^2 \exp\left[-c(\log p)^{1/600}\right].

This proves Theorem 1.3.

References

  1. [1]M. Bennett, D. Hart, A. Iosevich, J. Pakianathan, and M. Rudnev, Group actions and geometric combinatorics in F_q^d, Forum Mathematicum, 29(1) (2017), 91–110.
  2. [2]M. Bennett, A. Iosevich, and J. Pakianathan, Three-point configurations determined by subsets of F_q^2 via the Elekes–Sharir paradigm, Combinatorica, 34(6) (2014), 689–706.arxiv.org/abs/1201.5039
  3. [3]A. Iosevich and B. Liu, Equilateral triangles in subsets of R^d of large Hausdorff dimension, Israel Journal of Mathematics, 231(1) (2019), 123–137.
  4. [4]A. Iosevich and H. Parshall, Embedding distance graphs in finite field vector spaces, Journal of the Korean Mathematical Society, 56(6) (2019), 1515–1528.arxiv.org/abs/1802.06460
  5. [5]M. Jaber, Y. P. Liu, S. Lovett, A. Ostuni, and M. Sawhney, Quasipolynomial bounds for the corners theorem, in Proceedings of the 2025 IEEE 66th Annual Symposium on Foundations of Computer Science, IEEE, 2025, 2027–2036; full version, arXiv:2504.07006.arxiv.org/abs/2504.07006
  6. [6]P. Maga, Full dimensional sets without given patterns, Real Analysis Exchange, 36(1) (2010/11), 79–90.DOI
  7. [7]H. Parshall, Simplices over finite fields, Proceedings of the American Mathematical Society, 145(6) (2017), 2323–2334.arxiv.org/abs/1606.04040
  8. [8]T. Pham, Triangles with one fixed side-length, a Furstenberg-type problem, and incidences in finite vector spaces, Forum Mathematicum, 37(2) (2025), 359–372.arxiv.org/abs/2304.10897
  9. [10]B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. P. Kumar, E. Dupont, F. J. R. Ruiz, J. S. Ellenberg, P. Wang, O. Fawzi, P. Kohli, and A. Fawzi, Mathematical discoveries from program search with large language models, Nature, 625(7995) (2024), 468–475.
  10. [11]L. A. Vinh, On kaleidoscopic pseudo-randomness of finite Euclidean graphs, Discussiones Mathematicae Graph Theory, 32(2) (2012), 279–287.arxiv.org/abs/0807.2689
  11. [12]L. A. Vinh, The solvability of norm, bilinear and quadratic equations over finite fields via spectra of graphs, Forum Mathematicum, 26(1) (2014), 141–175.

Paper details

vlnc:W_ja5ftbb9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents