{'fraction_non_alphanumeric': 0.055593685655456415, 'fraction_numerical': 0.014974730142883884, 'mean_word_length': 3.7155045601647543, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Arithmetic Analogue of Fox's Triangle Removal Argument

We give an arithmetic version of the recent proof of the triangle removal lemma by Fox, 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 \epsilon>0 there is a \delta>0, such that if a subset A of \F_2^n requires the removal of at least \epsilon \cdot 2^n elements to make it triangle-free, then it must contain at least \delta \cdot 2^{2n} triangles. We give a direct proof which gives an improved lower bound for \delta (as a function of \epsilon), analogous to the one obtained by Fox for triangle removal in graphs. The improved lower bound was already known to follow (for triangle-removal in all groups), using Fox's removal lemma for directed cycles and a reduction by Kral, Serra and Vena. The purpose of this note is to provide a direct Fourier-analytic proof for the group \F_2^n.


Introduction
The triangle removal lemma for graphs states that for every ε > 0, there exists a δ > 0 such that for every graph on n vertices with at most δn 3 triangles, one can remove all triangles by deleting at most εn 2 edges. Contrapositively, this means that if a graph is at most ε-far from being triangle-free i.e., one needs to delete more than εn 2 edges to make it triangle free, then it must have at least δn 3 triangles.
The above lemma has a direct application to property testing since for a graph which is ε-far from being triangle-free, a random triple of vertices is guaranteed to form a triangle with probability at least δ. Thus if we test Ω(1/δ) random triples of vertices, we will find a triangle with constant probability. This test can then distinguish such a graph from one which is triangle-free, since, for a triangle-free graph, the probability of the test succeeding is 0. The triangle removal lemma and its generalizations to removal of more general graphs (instead of a triangle) have several interesting applications in mathematics, and we refer the reader to the survey [CF12] for a detailed discussion.
Other than being useful for proving the above result, Green's arithmetic analogue of Szemerédi's regularity lemma has had many other applications in combinatorics [GT10] and computer science [KO09]. In addition to leading to interesting analogues of combinatorial statements, the arithmetic setting has at least one more advantage: the proofs of these statements often proceed by partitioning the underlying spaces, and because of the structure provided by subgroups and cosets, the arguments are often cleaner in the group setting (specially for vector spaces over finite fields). This makes the arithmetic setting a convenient one to study for quantitative improvements to the results.
In this paper, we present an arithmetic analogue of the proof by Fox, for the group F n 2 . The argument can also be extended to other Abelian groups, but we restrict ourselves to F n 2 for simplicity.
We remark that the above result (for all groups) already follows from a version of the removal lemma for directed cycles, using a reduction by Král, Serra and Vena [KSV09]. This was already observed by Fox [Fox11] (see also [CF12]). However, we believe some of the Fourier analytic notions that come up in a direct arithmetic proof might be of independent interest. Also, a direct proof makes it somewhat more transparent how the argument partitions the underlying group, which might be useful for further improvements. We present a sketch of the proof below.
Known lower bounds for triangle removal. The original proof by Ruzsa and Szemerédi used Szemerédi's regularity lemma [Sze75]. However, the known lower bounds for the regularity lemma and its variants (see [Gow97] and [CF12]) imply that this approach necessarily obtains a bound on 1/δ which is at least Tower(poly(1/ε)). Fox's argument [Fox11] manages to avoid using the regularity lemma directly (although his proof still follows the same outline as the proof of the regularity lemma), thus obtaining 1/δ ≤ Tower(O(log(1/ε))).
In terms of lower bounds on 1/δ, it was shown by Alon [Alo02] that one must have 1/δ ≥ 2 Ω(log 2 (1/ε)) for triangle removal in graphs. For the problem of triangle removal in groups, Bhattacharya and Xie [BX10] show that one must have 1/δ ≥ (1/ε) 3.409 . However, both these lower bounds are quite far from the known upper bounds on 1/δ.

Proof Sketch
We will give a proof by contradiction. Let G denote the group F n 2 , and assume, to the contrary, that we have a set A ⊆ G that is ε-far from being triangle-free, and has at most δ|G| 2 triangles. We work with a subset A ′ ⊆ A that is the union of a maximal collection of element disjoint triangles, i.e. no two triples representing triangles share a common element. Since A\A ′ is triangle-free, and A is ε-far from being triangle-free, |A ′ | ≥ ε|G|. Define ε 0 def = |A ′ | /|G|.
In the rest of the sketch, we denote A ′ by A, and ε 0 by ε. The proof is based on a potential argument. At every step in the proof, we have a partition of G into T cosets of a subgroup H G where T def = | G /H| cosets, and hence an induced partition of A according to cosets of H. We measure the mean entropy of the partition, defined as and f (0) def = 0. Observe that the mean entropy is always non-positive, and by convexity it is at least ε log ε. Our main lemma proves that if δ is much smaller than ε 3 · |G| 2 /T 2 , then we can shatter A, i.e., the current partition of A can be refined according to cosets of H ′ H, such that the mean entropy increases by Ω(ε), and | G /H ′ | ≤ 2 T ·O(ε −3 ) . In essence, the size of the partition, and hence the bound on δ, are one exponential larger at every step. Since the mean entropy is always non-positive, this process must stop after O(log ε −1 ) rounds, giving the required bound on δ.
In order to show that we can shatter A if it has too few triangles, it is convenient to equate A with its indicator function A : G → {0, 1}, and the number of triangles with the sum x+y+z=0 A(x)A(y)A(z). Suppose we want to count the number of triangles between two cosets of H, viz. H + g 1 and H + g 2 , and a third coset of H ′ , H ′ + g 3 + z, where g 1 + g 2 + g 3 = 0. Assume A has density ε on all the three cosets. As a thought experiment, if A was the constant function ε on H ′ + g 3 + z, then the "number of triangles" between the three cosets is given by . If this is significantly smaller than ε 3 |H||H ′ |, then a Markov argument implies that if we partition according to cosets of H ′ , on a constant fraction of the cosets, A must have density significantly smaller than ε, i.e. A is shattered. A defect version of Jensen's inequality then implies that the mean entropy of the new partition is larger by Ω(ε).
Of course, A is not necessarily a constant function. However, a very similar argument works if all the non-zero Fourier coefficients of the function A on H ′ + g 3 + z are much smaller than ε in absolute value -we call such functions as superregular, in analogy with the proof from [Fox11]. The last part of the proof is to find a superregular decomposition of A on H + g 3 , i.e. approximating A ∩ (H + g 3 ) by a sum of superregular functions. If A is not superregular on H + g 3 , we pick a large Fourier coefficient η ∈ H, partition x ∈ H according to the value of x, η , and restrict ourselves to the part with greater density. If this part is not superregular, we repeat this procedure. Since the density on any part is at most 1, this process must end with a superregular part. We remove this set from A and repeat the procedure until most of A is covered, to find the required superregular decomposition.
This completes the proof sketch of Theorem 1.2.
Analogies and differences with the proof in [Fox11]. The proof of our main theorem on triangle-removal in groups is analogous to the proof of triangle-removal in graphs from the work of Fox [Fox11]. Nevertheless, we need to give the appropriate arithmetic analogues of the definitions and proofs. Though the proof in this paper is self-contained, for the readers who are familiar with the work of Fox [Fox11], we point out the analogies and the differences between the two proofs.
At every step in our proof, as in [Fox11], we have a partition of the underlying set, the group G in our case. However, our partition is structured, and consists of all the cosets of one fixed subgroup, compared to an arbitrary partition in [Fox11]. Our definitions of the potential function and shattering, are similar, except that we use the densities of the cosets, instead of the edge densities between pairs of subsets used in [Fox11]. Our notion of regularity is quite different from that in [Fox11], and is based on Fourier coefficients, similar to the one used in regularity lemmas for Abelian groups [Gre05]. The superregular decomposition that we find for a given set is analogous to the collection of superregular tuples in a graph, constructed in [Fox11].

Preliminaries
Fix a positive integer n. Throughout the paper, we denote G def = F n 2 and N def = |G| = 2 n . The notation H G denotes that H is a subgroup of G. We use H to denote the dual group of H. Denote by H ⊥ the set of cosets of H in G. In some cases which will be clear from the context, by abuse of notation, we use H ⊥ to denote a set of coset representatives.
Given a set A ⊆ G, three elements x, y, z ∈ A are said to form a triangle if x + y + z = 0. A is said to be ε-far from being triangle-free, if at least εN elements need to be removed from A in order that it contains no triangles.
We abuse notation and use A to denote both the set A, and also its characteristic function A : G → {0, 1}. Given a subgroup H G, and an element g ∈ G, we define A g H : H → {0, 1} as Let E x∈H [·] denote the expectation when x is drawn uniformly from H. For a function f : H → R, we define its Fourier coefficients as follows: where ·, · denotes inner product over F n 2 . Jensen's inequality states that if f is a convex function, ε 1 , . . . , ε s are nonnegative real numbers such that s i=1 ε i = 1, then, for any real numbers x 1 , . . . , x s , Jensen's inequality immediately implies the following simple lemma, which will be useful later.

Entropy
Our proof of the main theorem will be based on a potential argument, where our potential will be the mean entropy of a partition, as defined below.  G, and g ∈ G. Given a set A ⊆ G, if we partition the coset H + g as cosets of H ′ , define the mean entropy of this partition as follows Analogously, the mean entropy of partitioning A on G according to cosets of H G, is defined as Remark 2.4 Assume A ⊆ G has been partitioned according to cosets of a subgroup H G. For a refinement to this partition according to H ′ H we have In order to quantify the increase in the mean entropy because of a shattering, we need the following defect version of Jensen's inequality for the entropy function. We include a proof for completeness.

Proof:
We know that c < 1 since otherwise, a = 1≤i≤s ε i x i = i∈I ε i x i ≤ βa < a, a contradiction. The cases when a or c are equal to 0 follow immediately from Jensen's inequality (Equation (1)), therefore we may assume that a, c = 0.
where the first inequality is from Lemma 2.1, the first equality follows from the definition of the entropy function f , the second inequality follows from the fact that f ( v a ) = f ( 1−uc/a 1−c ) = f (1 + (1−u/a)c 1−c ) > (1−u/a)c 1−c , and the last inequality follows from the fact that u/a ≤ β and that f (x) + 1 − x is a decreasing function on the interval [0, 1].
The following lemma shows how the mean entropy of a partition compares to that of its refinement.
Lemma 2.6 (Entropy -Basic inequalities) Let H ′ H G, and A ⊆ G.

For every g ∈ G, we have F A (H + g, H ′ ) ≥ F A (H + g, H), and therefore F A (G, H ′ ) ≥ F A (G, H).
Proof: Both the parts follow from convexity of f, and Jensen's inequality (Equation (1)).
In Lemma 4.2, we will show how shattering a partition can substantially increase its mean entropy, which will allow us to use the mean entropy as a potential function.

Super-regularity
In this section, we define a notion of regularity, and show how one can approximate any set A as a sum of regular parts.
Given a function f : Similar notions of regularity have been used in the proof of a Szemerédi type regularity lemma for F n 2 [Gre05], and are well-studied as notions of pseudorandomness for subsets of abelian groups (e.g. see [CG92,Gow98]).
Given a set A, the following lemma identifies a subset of A that is superregular.

Lemma 3.2 (Finding Superregular Parts)
Let H be a subgroup of G. Given an element g ∈ G, a desired regularity parameter ρ ∈ (0, 1], a density parameter d > 0, and a set A ⊆ H + g such that |A| ≥ d|H|, we can find a triple (A 1 , H 1 , z 1 ) such that:
4. The indicator function of A 1 restricted to H 1 + z 1 + g is ρ-superregular on H 1 + z 1 + g.

Proof:
We give an iterative procedure to find A 1 , H 1 and z 1 .
If the indicator function of A 1 restricted to H 1 + g + z 1 is ρ-superregular on H 1 + g + z 1 , we are done and we can return (A 1 , H 1 , z 1 ).
Since the density of A 1 , i.e. |A 1 | |H 1 | , is increasing by a factor of (1 + ρ) at every step, and can be at most 1, in log (1+ρ) (1/d) iterations we must find a triple such that the restriction of A 1 to H 1 +z 1 +g is ρ-superregular on H 1 + z 1 + g. Thus, the final triple satisfies property 4. Finally, property 1 also holds since at every step, | H /H 1 | increases by a factor of 2.
Repeatedly applying the above lemma gives us the following corollary, which allows us to decompose a set into superregular parts.

Corollary 3.3 (Superregular Decomposition)
Let H be a subgroup of G. Given an element g ∈ G, a desired regularity parameter ρ ∈ (0, 1], a density parameter d ∈ (0, 1], and a set A ⊆ H + g, we can find a positive integer t, and a collection of t triples are disjoint subsets of A satisfying |A\(A 1 ∪ · · · A t )| ≤ d|H|, and for every i = 1, . . . , t:

The indicator function of
Proof: We build the collection of triples one at a time. At the i th step, let B def = A\(A 1 ∪· · · A i−1 ). If |B| ≤ d|H|, we can return the triples found till step (i − 1).
So we can assume |B| > d|H|, and apply Lemma 3.2 with subgroup H, element g, regularity parameter ρ, density parameter d, and subset B ⊆ H + g, to find (A i , H i , z i ) satisfying the required properties 1-4. Moreover, since We add the triple (A i , H i , z i ) to the collection and iterate.

Shattering
In this section, we prove that if a set A contains few triangles from three cosets, then we can partition at least one of the cosets into parts with significantly varying densities. In order to formally state the concerned lemma, we need to define shattering. The following definition is similar to that used in Fox's proof of the triangle removal lemma [Fox11]. Namely, partitioning H + g according to cosets of H ′ results in significant variation in the density of A.
Once we find a shattering, the defect version of Jensen's inequality allows us to prove that the mean entropy of the partition increases.
Lemma 4.2 (Entropy Increment) Let H ′ H G, and A ⊆ G. Let g ∈ G. If H ′ (α, β, k)shatters A on H + g then Proof: Follows from the definitions of F A and shattering, and applying Lemma 2.5. Now, we can state the main lemma of this section.
We first prove some necessary lemmas, and then give a proof of the above lemma at the end of this section. The following lemma allows us to count the number of triangles between three different sets.
Thus, in order to count the triangles in the three cosets, we count all such triples x 1 , x 2 , x 3 .
No. of triangles = We now give a proof of Lemma 4.6.
Proof: (of Lemma 4.6). We can simplify the above expression as follows: (Since for y 1 uniform over H ′ , y 1 + y 2 is also uniform over H ′ ) Thus, We now claim that either P v f (v) < 3 4 d 1 > 1 20 , or P v g(v) < 3 4 d 2 > 1 20 . This holds because otherwise, since f (v), g(v) ≥ 0, which is a contradiction.