An Arithmetic Analogue of Fox's Improved Triangle Removal Lemma

Computer Science/Discrete Mathematics Seminar II
Topic:An Arithmetic Analogue of Fox's Improved Triangle Removal Lemma
Speaker:Sushant Sachdeva
Affiliation:Princeton University
Date:Tuesday, April 2
Time/Room:10:30am - 12:30pm/S-101

We give an arithmetic version of the recent proof of the improved triangle removal lemma by Fox [Fox11], for the group F_2^n. A triangle in F_2^n is a tuple (x,y,z) such that x+y+z = 0. The triangle removal lemma for F_2^n states that for every \eps > 0, there is a \delta >0, such that if a subset A of F_2^n requires the removal of at least eps 2^n elements to make it triangle-free, then it must contain at least \delta 2^{2n} triangles. We give a direct proof which gives an improved lower bound for \delta (as a function of \eps), analogous to the one obtained by Fox for triangle removal in graphs. This result was previously known via a reduction from the improved removal lemma for directed cycles [Fox11,Král-Serra-Vena 09]. However, we believe our proof in this simplified setting is more transparent, and defines fourier-analytic notions that may be of independent interest.