2016/06/03 by Jacob Fox, László Lovász, Fox, Jacob +1 · 1 citation
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #FOS: Mathematics #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.1606.01230
openalex publication_date 2016/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let p be a fixed prime. A triangle in \mathbbFpn is an ordered triple (x,y,z) of points satisfying x+y+z=0. Let N=pn=|\mathbbFpn|. Green proved an arithmetic triangle removal lemma which says that for every ε>0 and prime p, there is a δ>0 such that if X,Y,Z ⊂ \mathbbFpn and the number of triangles in X × Y × Z is at most δN2, then we can delete εN elements from X, Y, and Z and remove all triangles. Green posed the problem of improving the quantitative bounds on the arithmetic triangle removal lemma, and, in particular, asked whether a polynomial bound holds. Despite considerable attention, prior to this paper, the best known bound, due to the first author, showed that 1/δ can be taken to be an exponential tower of twos of height logarithmic in 1/ε. We solve Green's problem, proving an essentially tight bound for Green's arithmetic triangle removal lemma in \mathbbFpn. We show that a polynomial bound holds, and further determine the best possible exponent. Namely, there is a computable number Cp such that we may take δ= (ε/3)Cp, and we must have δ≤ εCp-o(1). In particular, C2=1+1/(5/3 - log2 3) ≈ 13.239, and C3=1+1/c3 with c3=1-(log b)/(log 3), b=a-2/3+a1/3+a4/3, and a=(√(33)-1)/(8), which gives C3 ≈ 13.901. The proof uses Kleinberg, Sawin, and Speyer's essentially sharp bound on multicolored sum-free sets, which builds on the recent breakthrough on the cap set problem by Croot-Lev-Pach, and the subsequent work by Ellenberg-Gijswijt, Blasiak-Church-Cohn-Grochow-Naslund-Sawin-Umans, and Alon.