{'fraction_non_alphanumeric': 0.06732365700819452, 'fraction_numerical': 0.013711102779711853, 'mean_word_length': 3.4573883981857243, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The structure of critical sets for F_p arithmetic progressions

Fix a prime p and a density 0[0,1], what can one say about those which assign minimal weight to three-term arithmetic progressions -- that is, the sum of f(a)f(a+x)f(a+2x) is minimal as we sum over all a and x -- subject to the density constraint that the expected value of f equals d? In the present paper we show three things about them: 1) Such f are nearly indicator functions; 2) They enjoy a certain ``local minimal'' property; and, 3) They are approximately indicator functions for certain sumsets A+B.

If f were an indicator function for some set S ⊆ F p , this would give a normalized count of the number of three-term progressions in S.
In the present paper we establish a new structure theorem for functions f : F p → [0, 1] that minimize the number of three-term progressions, subject to a density constraint; and, as a consequence of this result, we prove a further structural result, which can also be deduced from the work of Green [3], though only for high densities (Green's result only works for densities exceeding 1/ log * (p), though perhaps his method can be generalized for this particular problem to handle lower densities).
Before stating the theorem, it is worth mentioning that Green and Sisask [5] have shown that sets of high density (density close to 1) that minimize the number of three-term arithmetic progressions, are the complement of the union of two long arithmetic progressions (actually, their result is stated in terms of sets that maximize the number of three-term progressions, but there is a standard trick to relate this to the minimizing sets).
Our main theorem is now given as follows: 1] is an arithmetic progression; and, we let N 3 be the number of such ordered pairs where x, y, n is an arithmetic progression. For n to belong to S, we must have that N 1 + N 2 + N 3 ≤ L.
Since S and R have small symmetric difference, we see that our r can be thought of as enjoying a "local minimal" property: Not only does r minimize Λ(r) up to an error O(1/p), subject to E(r) ≥ θ, but we can easily decide whether n ∈ F p belongs to R or not, simply by checking to see how many progressions pass through the point n, with the other two end-points in R. If this count is small enough, then n likely belongs to R (though it certainly belongs to S); but, if the count is large, n likely does not belong to R.
The most difficult part of this proof that R and S are nearly the same, is handling those n where N 1 + N 2 + N 3 exactly equals L.

Remarks on the third part of the theorem
One reason to believe the third bullet above is that from the second bullet we expect that f is an indicator function for a level set of a "smooth function" (r * r)(2n) + 2(r * g)(−n); and, as is well known, such level sets must be approximately the union of a bunch of translates of a Bohr neighborhood of the function, at least when their density is large enough.
It should be remarked that sumsets are quite special structures, as are smooth functions of the type (r * r)(2n) + 2(r * g)(−n), and only a vanishingly small proportion of the subsets of F p are sumsets or form the support of a smooth function; so, the third bullet is saying something fairly non-trivial about our minimal f . Also, there are loads of other consequences that one can deduce from the third bullet. One of these is that, upon decomposing the Bohr neighborhood B into a union of arithmetic progressions, one can deduce that C is essentially the union of a "small number" of somewhat "long" arithmetic progressions ("small number" can mean a power of p, say p c , where c < 1), all having the same common difference.

Proof of Theorem 1
The proof of this structure theorem depends on a certain function r 3 , which we presently define.
Definition. Given a subset S of a group G, we let r 3 (S) denote the size of the largest subset of S free of solutions to x + y = 2z, x = y. In all the uses of r 3 in the present paper, G = Z and S = [N] := {1, 2, ..., N}, for various different values of N.
Bourgain [2] has recently shown that and from a result of Behrend [1], we know that for N sufficiently large, for a certain constant c > 0.

Proof of the first part of Theorem 1
For this part we will begin by assuming that E(f ) > κp(log p) −2/3 , for as large a κ > 0 as we might happen to need, since this part of the theorem is trivially true otherwise.
Here we will first show that the minimal f is well-approximated by an indicator function; actually, we will prove even more -we will show that if Λ(f ) comes within O(p −1 ) of this smallest value, subject to the density constraint E(f ) > θ, then f must be approximately an indicator function. To do this, we will require the following proposition, proved in subsection 2.4.
We also will require the following quantitative version of Varnavides's theorem [7]. .
Proof of the Lemma. The proof of this lemma is via some easy averaging: We let A N denote the set of all arithmetic progressions A ⊆ F p having length N. These arithmetic progressions are to be identified by ordered pairs (a, d), d = 0, where a is the first term in the progression, and where d is the common difference. Note that this means we "double count" arithmetic progressions in that the progression a, a + d, a + 2d, ..., a + kd is distinct from a + kd, a + (k − 1)d, ..., a.
It is easy to check that each sequence a, a + d, a + 2d, d = 0 is contained in exactly N 2 /2 + O(N) of these A ∈ A N : We have that each three-term progression is contained in the same number of A ∈ A N , and each A ∈ A N contains N 2 /2+O(N) three-term progressions; hence, if P denotes the number of A ∈ A N containing a particular sequence a, a+ d, a+ 2d, we have since there are p(p − 1) non-trivial progressions in F p , that p(p − 1)P = |A N |(N 2 /2 + O(N)), So, if we let T 3 (X) denote the number of sequences a, a + d, a + 2d ∈ X, d = 0, we have that Next, we need a lower bound on how many A ∈ A N satisfy |A ∩ S| ≥ r 3 (N): First, note that for each d ∈ F p , d = 0, there are exactly N arithmetic progressions A ∈ A N having common difference d that contain a particular point a ∈ F p . So, Let Y be the number of A ∈ A N for which |A ∩ S| > r 3 (N). Then, we have For each of these Y progressions A ∈ A N we will have that T 3 (A ∩ S) ≥ 1; and so, we deduce from (3) that Using the easy to see fact that The lemma easily follows on rephrasing this in terms of Λ(S).

Now we let
where ε > 0 will be determined later.
In order for f to be minimal, from Proposition 1 we deduce that we must have that if εβ = p −1/2 log p, then So, since we trivially have that We would like to now apply Lemma 1 to this, but in order to do so, we must solve for N such that To this end, we require the bound (2) of Bourgain, which implies that if we let N = exp(c(p/|A|) 3/2 ) < p, since |A| > κp(log p) −2/3 , then we will have that |A| > p(log N) −2/3 > 2r 3 (N)p/N, as we require. From this it follows from Lemma 1 that It follows now from (4) that So, if we let C be the function f rounded to the nearest integer (which will be either 0 or 1), then for n ∈ A we will have |f (n) − C(n)| ≤ 1, while for all other n we will have |f (n) − C(n)| ≤ ε. It follows that Choosing ε = (log p) −2/3 , we deduce that this sum is O(p(log p) −2/3 ), just as in Bourgain's theorem (2). This completes the proof of the first part of our theorem.

Proof of the second part of Theorem 1
Given a function h : and then we define In order to proceed further, we will require the following proposition.
Proposition 2 Fix A ⊆ F p , and associate to each a ∈ A a real number those which minimize Λ(h) have the property that there exists L > 0 such that The proof of this proposition can be found in subsection 2.5. We will use this proposition to construct a sequence of sets and a sequence of functions such that the following all hold.
• third, given particular fixed values for r i (n) on A i , we have that r i minimizes Λ(r i ), subject to the density constraint E(r i ) = E(f ); • and finally, for each n ∈ Clearly, this process cannot continue past the ⌊p/2⌋th iteration, as the sets A i grow by two elements after each iteration. Furthermore, we will show that whenever the process does terminate (which it will in either case 1 or case 2 below), we will be left with a function r : F p → [0, 1] satisfying the conclusion in the second bullet of Theorem 1.
For the time being, let us suppose that these sequences can be constructed as claimed: Suppose we have constructed A i ; we will now show how to construct A i+1 . To this end, we apply Proposition 2 with A = A i (in the case i = 0 we let A be the empty set), and then we deduce that for some L > 0, r i (n) = 1 (we use r 0 (n) := f (n)) for F r i (n) < L and r i (n) = 0 for F r i (n) > L. We furthermore apply the already-proved first part of Theorem 1 from subsection 2.1, and deduce that since then we just let A i+1 := {x, y}, and r i+1 := r i .
So suppose that there are no such x and y; there are three possibilities to consider.
Note that we include in this case the possibility that there are no n ∈ F p \ A i such that F r i (n) = L.
If we are in this case, then it means that and so, r i (n) is very close to 1 at most places n ∈ F p \ A i where F r i (n) = L. It follows that if we were to let S be the set of all n ∈ F p \ A i with F r i (n) ≤ L, then In order to extend this sum to all n ∈ F p , we will need to show that |A i | cannot be too big. Basically, we will show that if it is, then Λ(f ) could not be minimal.
To see this last point, we apply Proposition 1, using A := A i , h := r i , ε = 1/4, and εβ = p −1/2 log p, and we deduce that there exists We wish to apply Lemma 1: First, let such that from (2) we deduce that as we require. From this it follows now from Lemma 1 that for N sufficiently large.
In order for f to minimize Λ(f ), we must have that It follows from this and (5) that as claimed. It follows that if we extend S to be the set of all n where F r i (n) ≤ L, then Σn |r i (n) − S(n)| ≪ p(log p) −2/3 , and the second bullet of Theorem 1 is proved upon setting r = r i .

Case 2:
If we are in this case, then it means that and so, if we let L ′ = L − δ, for small enough δ > 0, then we will have that We wish to extend this to where S is the set of all n satisfying F r i (n) ≤ L ′ , by showing that |A i | cannot be too big, and we proceed exactly the same way as in Case 1 above. We then deduce that, upon redefining S in this way, that and again this proves the second bullet of Theorem 1 upon setting r = r i .
In order to decide what to do in this case, we will require the following basic fact, which is an immediate consequence of the formula for Λ(h 3 ) in the proof of Proposition 2 in section 2.5 in equation (10): We have that if we let r i+1 (n) := r i (n), if n = x, y; (r i (x) + r i (y))/2, if n = x or y, So, when we are in this case, we just let and so the properties of A i+1 , r i+1 that we require all hold.

Proof of the third part of Theorem 1
We assume for this part of the proof of our theorem that θ > (log log p) −2/3 , since our problem is trivial otherwise.
We now prove the third bullet of Theorem 1. To this end, we let where µ is defined as follows: First, we locate the places b 1 , ..., b t where the Fourier transform where ε 0 > 0 will be decided later, and then we define the Bohr neighborhood B to be all those n ∈ F p where ||b i n/p|| < ε 0 , for all i = 1, ..., t.
Our goal now will be to show that for this will imply the third bullet of Theorem 1 holds: To see this, note that from the already-proved first bullet, we know that if we let C(n) be f (n) rounded to the nearest integer, then which is just what the third bullet claims. Now we show that (6) holds: First note that Parseval gives t ≤ θε −2 0 ; and the following standard lemma tells us that our Bohr neighborhood is "large".
Now let A be all those n ∈ F p for which Then, we have that In order to apply Lemma 1 to this, we let N = exp(c(p/|A|) 3/2 ) < p, so that from (2) we deduce that |A| > p(log N) −2/3 > 2r 3 (N)p/N, as we require. From this it follows now from Lemma 1 that for N sufficiently large.
In order for Λ(f ) to be minimal, we must have that Setting β = 5ε 0 we must have and so, Λ(A) ≤ 80ε 0 ε −5 1 + O(1/p). Combining this with our lower bound for Λ(A) above, we deduce that

It now follows that if C(n) is f 3 (n) rounded to the nearest integer, then
Now we will set ε 0 := θ log log p/ log p, and ε 1 := (log log p) −2/3 , which will give |B| > p 1/2 , and then our sum on |f 3 (n) − C(n)| will be at most which completes the proof of Theorem 1.

Proof of Proposition 1 2.4.1 Technical lemmas needed for the proof of the Proposition
We will need to assemble some lemmas to prove this proposition. We begin with the following standard fact: Lemma 3 Suppose that S ⊆ F p satisfies |S| = αp. Let T denote the complement of S. Then, we have that Proof of the lemma. One way to prove this is via Fourier analysis: We have that SinceŜ(a) = −T (a) for a = 0, we have that all the terms except for a = 0 vanish. So, From this lemma, one can deduce the following corollary, which we state as another lemma: Lemma 4 For α > 2/3 we have that there exists a set S ⊆ F p satisfying |S| = ⌊αp⌋, and Proof of the Lemma. Let β = 1 − α < 1/3, and then let S just be the arithmetic progression {0, 1, ..., ⌊αp⌋ − 1}, and then let T be the complement of S, which is also just an arithmetic progression. It is easy to check that as the solutions to x + y = 2z, x, y, z ∈ T are exactly those ordered pairs (x, z) ∈ T × T of the same parity.
Applying Lemma 3 to this set T , we find that as claimed.

Body of the proof of Proposition 1
We will define the function g : where for n ∈ B, g(n) = f (n), but on the set A, the funciton g will be different from f : Basically, we let S be the set produced by Lemma 4 with α = 1 − ε, then take T to be a random translate and dilate of S, say T := m.S + t = {ms + t : s ∈ S}.
Then, we let for n ∈ A, g(n) Note that this is ≤ 1, because we know f (n) ≤ 1 − ε on A.
We will show that, so long as there are "enough" three-term progressions lying in A, this new function g will have the property that Λ(g) is much smaller than Λ(f ). To this end, we consider three types of arithmetic progressions that give rise to the counts Λ(f ) and Λ(g): Those progressions that pass through both A and B (say one point in A and two in B; or two in A and one in B); those that lie entirely within A; and those that lie entirely within B.
The contribution to Λ(g) of those arithmetic progressions lying entirely within B is the same as the contribution to Λ(f ). So, we don't need to account for these when trying to prove our upper bound on Λ(g); and therefore there are only two non-trivial cases that we need to work out:

Case 1 (all three points in A).
Define the random variable Z 0 := Σa,a+d,a+2d∈A g(a)g(a + d)g(a + 2d), and let W 0 be the analogous sum but with g replaced by f . We note that if we only consider those terms with d = 0, we lose at most O(p) in estimating Z 0 .
We have that To estimate this inner sum, we note that the contribution of those terms with d ′ = 0 is 0; and, when d ′ = 0, we get a contribution of f (a)f (a + d)f (a + 2d) to just the inner sum, because there is only one pair m, t which works. Thus, we deduce from this and Lemma 4 that Also, let W 1 , ..., W 6 be the analogous constants with g replaced by f (note that these are not random variables).
We will now compute the expectations of these random variables; though, we will not do all of these here, and instead will just work it out for Z 1 , as showing it for all the others can be done in exactly the same way, and leads to the same bounds.
To evaluate this last expectation, let us suppose that a + 2d ∈ B and a, a + d ∈ A, where d = 0 (if d = 0 then we would have that a lies both in A and B, which is impossible). Then, given any pair of distinct elements x, y ∈ S, there exists a unique pair (m, t) ∈ F p × F p such that So, the probability that given a + 2d ∈ B, a, a + d ∈ A, is 1/p 2 times the number of ordered pairs (x, y) of distinct elements of S, which is |S|(|S| − 1). Note that if g(a)g(a + d) is not equal to this, then it must take the value 0. It follows that Likewise for the other Z i , we will have that Collecting the two cases together.
Let Z 7 denote the contribution of arithmetic progressions lying entirely in B; that is, Note that in this case W 7 = Z 7 .
Putting together our above estimates, and using the fact that we find that Using Markov's inequality we have Before we "derandomize" and pass to an instantiation of g, we will need to also show that E(g) is close to E(f ) with high probability. This can be accomplished in several different ways, though here we will just use the second moment method: First, let F := Σa∈A f (a), and G := Σa∈A g(a). Now, as is easy to show, F + O(1/p) = E(G); and so, since εβ > p −1/2 log p, we have that It follows from Chebychev's inequality that this last probability is at most To bound this from above we observe that )g(b)).
Now, as a consequence of what we worked out just before (7), we have that g(a) and g(b) are independent whenever a = b. So, and it follows that the probability of the right-most event in (8) is at most O(β −2 /p). It is easy to see that with probability 1 − O(β −2 /p) we will have Conclusion of the proof.
It follows that with probability at least Using our assumption that we have that this probability is positive. So, there exists an instantiation of g such that both hold; henceforth, g will no longer be random, but will instead be one of these instantiations. By reassigning at most 2βp places a ∈ A where g(a) = 0 to the value 1, we can guarantee that E(g) ≥ E(f ), and one easily sees that This completes the proof of our proposition.
There are actually 6 more terms that make up the above "error"; however, all of these give a contribution of 0, which is why they were not listed.
To prove our proposition, all we need to show is that if there is a pair x, y ∈ F p , x, y ∈ A, with F h (x) < F h (y), and h(y) > 0, then in fact h(x) = 1.
Suppose there were such a pair x, y for which h(x) < 1. Then, we will show that h fails to minimize Λ(h) subject to the various constraints: Basically, we let 0 < ε < min(1 − h(x), h(y)) (its exact value will be decided later) and then we consider the function h 3 given by for n ∈ F p , n = x, y, we set h 3 (n) = h(n); and, h 3 (x) = h(x) + ε, h 3 (y) = h(y) − ε.
From our formula (10), we easily deduce that Clearly, if we take ε > 0 small enough, we will get which contradicts the minimality of h. We conclude, therefore, that h(x) = 1, as claimed.