{'fraction_non_alphanumeric': 0.05172667968893967, 'fraction_numerical': 0.01652968709689308, 'mean_word_length': 3.7531750897784004, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A probabilistic technique for finding almost-periods of convolutions

We introduce a new probabilistic technique for finding 'almost-periods' of convolutions of subsets of groups. This gives results similar to the Bogolyubov-type estimates established by Fourier analysis on abelian groups but without the need for a nice Fourier transform to exist. We also present applications, some of which are new even in the abelian setting. These include a probabilistic proof of Roth's theorem on three-term arithmetic progressions and a proof of a variant of the Bourgain-Green theorem on the existence of long arithmetic progressions in sumsets A+B that works with sparser subsets of {1, ..., N} than previously possible. In the non-abelian setting we exhibit analogues of the Bogolyubov-Freiman-Halberstam-Ruzsa-type results of additive combinatorics, showing that product sets A B C and A^2 A^{-2} are rather structured, in the sense that they contain very large iterated product sets. This is particularly so when the sets in question satisfy small-doubling conditions or high multiplicative energy conditions. We also present results on structures in product sets A B. Our results are 'local' in nature, meaning that it is not necessary for the sets under consideration to be dense in the ambient group. In particular, our results apply to finite subsets of infinite groups provided they 'interact nicely' with some other set.


Introduction and statements of results
There are many interesting problems that are concerned with counting various structures in subsets of groups. Many of these can be expressed in terms of the operation of convolution, defined for two functions f, g : G → C on a group G to be the function f * g given by f * g(x) := y∈G f (y)g(y −1 x), provided this exists for all x ∈ G. For example, many of the central objects of additive combinatorics can be expressed directly in terms of convolutions: the product set A·B = {ab : a ∈ A, b ∈ B} of two subsets of a group is precisely the support of the function 1 A * 1 B , where 1 X denotes the indicator function of a set X, and the number of threeterm arithmetic progressions in an additive set A, i.e., tuples (a 1 , a 2 , a 3 ) ∈ A × A × A with a 1 + a 3 = 2a 2 , is 1 A * 1 −2·A * 1 A (0). One may think of a convolution as being a sum of a function weighted by translates of another function and, as such, one may hope that convolutions are somewhat 'smooth'. Indeed there are various senses in which this is true, and having precise notions of what it means can lead to interesting combinatorial consequences. Such results are often proved for abelian groups using the beautiful theory of Fourier analysis, where one uses the fact that convolutions and Fourier transforms interact in a very nice way. In this paper our aim is to demonstrate a new technique for establishing results about convolutions that are similar to those of Fourier analysis but that work on arbitrary groups, as well as to present applications.
1.1. Notation. Before we state our results let us introduce some notation-most of which is standard-directing the reader to the book [44] of Tao and Vu or the paper [43] of Tao for more details and interesting information about the concepts we use. Throughout the paper G will denote a group (which may potentially be infinite). For two subsets A and B of G we write A · B := {ab : a ∈ A, b ∈ B} for the product set of A and B, and A −1 for the collection of inverses of elements of A. Sometimes we shall omit the · and just juxtapose two sets to indicate the multiplication. For an element t of G we write tA := {ta : a ∈ A} for the left-translate of A by t and similarly for the right-translate At. If k is a positive integer then we write A k := A · A · · · A for the k-fold product set of A, and A −k for the k-fold product set of A −1 . For abelian groups we write the group operation additively and we give the corresponding definitions to A + B, A − B, t + A, kA, etc. The multiplicative energy between two sets A and B is defined to be the quantity for abelian groups this is known as the additive energy. For a function f : G → C and a real number p 1 we write f p p = f (x) p p := x∈G |f (x)| p for (the pth power of) the L p norm of f provided this is finite. Thus E(A, B) = 1 A * 1 B 2 2 . A final piece of terminology: for finite groups G we say that the density of a set A ⊆ G is |A|/|G|.

1.2.
The almost-periodicity results. Our first result, then, is the following almostperiodicity-type theorem. Proposition 1.1 (L 2 -almost-periodicity, local version). Let G be a group, let A, B ⊆ G be finite subsets, and let ǫ ∈ (0, 1) be a parameter. Suppose S ⊆ G is such that |B · S| K|B|. Then there is a set T ⊆ S of size |T | |S| (2K) 9/ǫ 2 such that, for each t ∈ T T −1 , The condition that there should be a set S such that |B · S| K|B| is what justifies the terminology 'local': one does not need B to be dense in its ambient group in order to apply the proposition effectively. All one needs is for B to interact nicely with some large set S, a condition that we say more about in §2. If one knows little about the structure of B one can still obtain useful conclusions from the proposition provided B is dense in some structured set. For example, if G = Z and B ⊆ [N] := {1, . . . , N} with |B| βN (a case of interest in many problems) then one may take S = [N] and K = 2/β. Similarly, if G is finite then one can always take S = G, regardless of B, which immediately gives the following corollary. Corollary 1.2 (L 2 -almost-periodicity, global version). Let G be a finite group, let A, B ⊆ G, and let ǫ ∈ (0, 1) be a parameter. Suppose B has density β. Then there is a set T ⊆ G of size at least (β/2) 9/ǫ 2 |G| such that, for each t ∈ T T −1 , On an informal level these results say that convolutions are somewhat continuous: one may find a large number of translates t such that the function 1 A * 1 B does not change by much-in an L 2 sense-when translated by t. Having L 2 -almost-periods provides one with good control in many applications, particularly those involving three-fold or higher convolutions, such as when dealing with the number of three-term progressions in a set or with a triple-fold product set A · B · C. But for certain applications involving only a single convolution it turns out that having L p -almost-periods for a somewhat large p is more useful. Proposition 1.3 (L p -almost-periodicity, local version). Let G be a group, let A, B ⊆ G be finite subsets, and let ǫ ∈ (0, 1) and m 1 be parameters. Suppose S ⊆ G is such that |B · S| K|B|. Then there is a set T ⊆ S of size As before, this has the following 'global' corollary. Corollary 1.4 (L p -almost-periodicity, global version). Let G be a finite group, let A, B ⊆ G be subsets, and let ǫ ∈ (0, 1) and m 1 be parameters. Suppose B has density β. Then there is a set T ⊆ G of size at least (β/2) 50m/ǫ |G| such that We give some further variants of the above propositions in §3. In particular one can with a slight change to the hypotheses find left-translates instead of right-translates, which may be more useful depending on the application.
Our proofs of the above propositions are of a probabilistic nature, involving a 'random sampling' procedure that finds small subsets of one of the sets that behave similarly to the set itself (in a precise sense). This procedure is the same regardless of whether the group is commutative or not, which places our method in stark contrast to the Fourieranalytic methods that are typically the port of call for dealing with almost-periodicity in abelian groups. We say more about the abelian versions of the above results and the Fourier-analytic methods that lead to them in §9, turning now instead to applications of our results.
1.3. Applications. We shall apply the almost-periodicity results in four directions in this paper, namely towards (i) non-commutative analogues of the Bogolyubov-Freiman-Halberstam-Ruzsa theory that shows that sumsets are structured, (ii) a low-density version of the Bourgain-Green theorem on long arithmetic progressions in sumsets A + B, (iii) a probabilistic proof of Roth's theorem on arithmetic progressions and (iv) a new result on the approximate translation-invariance of products of so-called strong K-approximate groups.
We discuss each of these in turn.
Structures in product sets. A general objective in additive combinatorics is to show that sumsets in abelian groups are rather structured objects. A rather useful such result due to Bogolyubov [2] that was highlighted by Ruzsa [34] in the additive-combinatorial context shows that sets 2A − 2A are highly structured, particularly if A has small doubling. For non-abelian groups an analogue of this was recently proved by Sanders [37]: Theorem 1.5. Suppose G is a group, A ⊆ G is a finite set such that |A 2 | K|A| and k ∈ N is a parameter. Then there is a symmetric set S containing the identity such that As noted in [37], this is a variant of a result used in Tao's proof [42] of a Freiman-type theorem on the structure of sets with small doubling in solvable groups. Freiman-type results are ones that characterize subsets of groups that are group-like-more precisely subsets A of a group G that satisfy a small-doubling condition |A 2 | K|A| or a smalltripling condition |A 3 | K|A| for some fixed K-and there has been a concerted effort in recent years to try to establish such results in various classes of groups. In the commutative setting a rather precise and useful such characterization is provided by a theorem of Green and Ruzsa [20] that generalizes a fundamental theorem of Freiman [16]. In the non-commutative setting a number of interesting results have appeared recently [6,7,8,15,24,31,42], though there is not yet a unified theory. Let us remark in the context of this paper, however, that results of the form of Theorem 1.5 can be useful in proving such results: abelian results that find large Bohr sets in 2A−2A form a key step in many proofs of Freiman's theorem, and Theorem 1.5 itself was recently used by Green, Sanders and Tao [22] to provide combinatorial proofs of some Freiman-type results of Hrushovski [24].
The almost-periodicity results of this paper are particularly well-suited to proving results of the form of Theorem 1.5, and doing so with reasonable bounds. Indeed, the following is a virtually immediate consequence of Proposition 1.1.
Furthermore, each element of S k has at least |A| 3 /2K representations as a 1 a 2 a −1 Four-fold product sets of the above form are particularly pleasant to analyze, but it is not much harder to obtain a result that works with only triple product sets. To state this concisely it is convenient to introduce a small piece of non-standard terminology: for a triple (A, B, C) of finite subsets of G and an element x ∈ G we shall say that That is, x is γ-popular if it can be written as a product abc with a ∈ A, b ∈ B and c ∈ C in at least γ(|A||B|) 1/2 |C| different ways. If |A · B · C| is small then certainly there is a popular element, since , but there are also much weaker conditions ensuring this. Theorem 1.7. Let G be a group, let A 1 , A 2 , A 3 ⊆ G be finite, non-empty sets and let k ∈ N be a parameter. Suppose x is a (1/K)-popular element for (A 1 , A 2 , A 3 ) and that there is a set D ⊆ G such that |A 3 · D| K ′ |A 3 |. Then there is a symmetric set S ⊆ DD −1 containing the identity such that In the abelian setting the non-local version of this result is in the same vein as a result of Freiman, Halberstam and Ruzsa [17] that finds long arithmetic progressions or Bohr sets in A + A + A (see also [44,Theorem 4.43]); the best bounds currently known in this direction are due to Sanders [36].
For the product of two sets the situation looks rather different, a phenomenon that has been observed in many different contexts. Whereas we cannot ensure that we can find a translate of a large iterated product set in A · B, it turns out that we can always find a translate of any small subset of a large iterated product set. Theorem 1.8. Let G be a group, let A, B ⊆ G be finite, non-empty subsets and let k, n ∈ N be parameters. Suppose |A · B| K|A| and |B · D| K ′ |B|. Then there is a symmetric set S ⊆ DD −1 of size |S| exp −150k 2 K log 2K ′ log 2n |D| such that the product set A · B contains a left-translate of any set P ⊆ S k of size at most n.
This theorem is a straightforward consequence of the L p -almost-periodicity of 1 A * 1 B given by Proposition 1.3. Our next application restricts this result to subsets of {1, . . . , N}.
Arithmetic progressions in sumsets A+B. Coupled with a 'structure-generation' lemma that finds arithmetic progressions in iterated sumsets kS, Theorem 1.8 quickly yields the following. for some absolute constant c > 0. This bound was improved by Green [18] using a different Fourier-analytic argument to the best bound that is currently known for highdensity sets, increasing the exponent 1/3 above to 1/2; a similar bound has since also been established by Sanders [36] using another Fourier-analytic technique. By contrast, our result yields somewhat shorter arithmetic progressions for high-density sets (where α and β are thought of as not depending on N) but is also able to deal with sets that are much smaller than previously possible. Whereas the previous bounds for the length of the arithmetic progressions one can find in A + B are only non-trivial provided αβ C(log log N) 2 / log N for some absolute constant C, Theorem 1.9 requires only α(log 4/β) −1 C/ log N. Thus, whereas at least one of the sets had to have density at least C log log N/(log N) 1/2 with previous bounds, the above theorem allows us to deal with pairs of sets each of which may have density as low as C log log N/ log N. In fact, one of the sets may have density as low as exp (−(log N) c ), which illustrates a significant difference between our results and the Fourier-analytic ones. Our proof also adds another novelty: we are able to work directly in the group Z, never needing to embed the sets in a group Z p (as is typical). We are also able to give a local version of the result; we present this and the proofs in §6.
Roth's theorem. Our next application concerns the quantity r 3 (N), the largest size of a subset of the integers {1, . . . , N} that is free from non-trivial three-term arithmetic progressions-that is, triples (x, x + d, x + 2d) with d = 0. As a consequence of our probabilistic proof of Proposition 1.1 we are able to establish the following version of Roth's theorem [32] by completely combinatorial means. This bound for r 3 is marginally stronger than Roth's original r 3 (N) ≪ N/ log log N, the beautiful Fourier-analytic proof of which has become a model argument in additive combinatorics. Subsequent Fourier-analytic arguments have demonstrated better bounds for r 3 : the best bound currently known is due to Bourgain, who in [5] established that Roth's theorem has enjoyed many different proofs, including non-Fourier-analytic ones, and each new proof has typically offered a slightly different perspective on the problem. However, only the Fourier-analytic proofs seem to have given decent bounds: the methods that have not used Fourier analysis have generally been accompanied by tower-type bounds, establishing only that see [44,Chapter 10] for references, as well as the more recent work [30]. (The iterated logarithm of N, log * N, is defined to be the number of times it is necessary to take the logarithm of N in order to get a number less than or equal to 1, and thus grows extremely slowly.) It is therefore perhaps of interest that our method manages to give bounds of a similar quality to the Fourier-analytic proofs despite not using Fourier analysis. We give the proof of Theorem 1.10 in §7.
Strong approximate groups. We present one final application of the probabilistic technique: the following result says that products of certain 'group-like' sets must have strong almost-periodicity properties. Proposition 1.11. Let A be a finite subset of a group and let ǫ ∈ (0, 1). Suppose A has the property that every x ∈ A 2 has at least |A|/K representations as ab with a, b ∈ A. Then there is symmetric set Green [19] has suggested that one might call sets A that satisfy the hypothesis of this proposition strong K-approximate groups; that is, A is a strong K-approximate Clearly any subgroup of a group is a strong K-approximate group with K = 1, but there are more complex examples. For example, if p > 3 is a prime congruent to 3 mod 4 then the set A ⊆ Z p consisting of non-zero squares is a strong ( We make some further remarks about strong approximate groups in §8.
The remainder of this paper is laid out as follows. In the next section we describe some standard background material from the subject of arithmetic combinatorics. In §3 we outline the basic idea behind our method and present the proofs of our almostperiodicity results. The proofs of the results on structures in product sets are very short and we give them immediately afterwards in §4. In §5 we establish a structuregeneration lemma that allows us to pass from arbitrary sets of translates in abelian groups to structured sets of translates. In §6 we give the proof of Theorem 1.9 on arithmetic progressions in sumsets, and in §7 we present our proof of Roth's theorem. We present the proof of Proposition 1.11 on strong approximate groups in §8, and we close in §9 with some further remarks, including a comparison with Fourier-analytic results.
1.4. Acknowledgements. We would like to thank Tom Sanders for many interesting and helpful conversations relating to several of the results of this paper. The secondnamed author is grateful for the support of an EPSRC Postdoctoral Fellowship, enjoyed while part of this work was carried out.

Preliminaries on convolutions and product sets
In this section we record some useful standard results about convolutions and product sets; it may be largely skipped by those familiar with additive combinatorics. We follow Tao [43].
For functions on abelian groups the operation of convolution is commutative; this is not true in general for non-abelian groups. Convolution is, however, always bilinear and associative. A crucial link between convolutions and products is that the support of 1 A 1 * · · · * 1 A k is the product set A 1 · · · A k . More precisely, convolutions thus count how many representations an element of a product of k sets has a product of elements of the k sets. For pairs of sets one also has the interpretation For functions this change between left-translates and right-translates is illustrated by the reflection property Since convolutions are counts, sums of convolutions are also counts, and a full sum counts a particularly simple quantity: Many results in this paper involve conditions on the cardinalities of product sets. For two finite sets A and B in a group G, one always has the inequalities max(|A|, |B|) |A · B| |A||B| with equality possible in various scenarios. Of course |A· B| |G| as well. Of particular importance to this paper are the cases when the product set A · B is small, though precisely what this means will depend on the context. Generally we shall say that |A · B| is small if it is at most K|A| or K|B| for some fixed number K, i.e., if it is within a constant factor of being as small as it could be. One generally thinks of a condition |A · B| K|B| as showing that A and B share some structure, particularly if A and B are close in size. In particular this implies that A and B must themselves be somewhat structured, as follows from [43, Lemma 3.2].
Lemma 2.1 (Ruzsa triangle inequality). Let A, B, C ⊆ G be finite, non-empty subsets of a group. Then Our almost-periodicity theorems are thus particularly effective when one of the sets A and B is structured in the sense of having small doubling |A 2 | K|A| or |B 2 | K|B|, or small differencing |A · A −1 | K|A| or |B · B −1 | K|B|, for some small, fixed K. In abelian groups the following result is particularly useful for bounding sizes of sumsets; see [44,Chapter 6] for references and a proof.
Theorem 2.2 (Plünnecke-Ruzsa inequality). Let A and B be finite subsets of an abelian group, and suppose |A + B| K|A|. Then for all integers m, n 1.
As previously noted, however, one can substitute the above notion of structure for a much weaker one: that of being dense in a structured set (such as the ambient group).
There are other ways in which one can weaken the notion of structure used; recall our definition of the multiplicative energy between two sets: If the product set A · B is small compared to either A or B, in the sense that it has size at most K|A| or K|B|, then E(A, B) is large: where the inequality follows from the Cauchy-Schwarz inequality. On the other hand, the condition E(A, A) |A| 3 /K need not imply that |A 2 | is small, even in the abelian setting. We mention that there is a partial converse, however, that could be used in certain applications to keep the effectiveness of the bounds of this paper in the case when the sets in question have high multiplicative energy instead of small doubling: this is known as the Balog-Szemerédi-Gowers theorem. We point the interested reader to [44,Chapter 2] and [43, Section 5] for more information on this.
Many of the above properties have analogues for functions more general than indicator functions, of course. The distinction between indicator functions and more general functions tends not to be particularly important in practice; see the comments in §9.

Proofs of the main propositions
Each of our propositions on almost-periodicity has to do with finding translates by which the convolution 1 A * 1 B is approximately invariant in some norm. There are two basic ideas behind the proofs of these propositions. The first is that if one selects a small random subset C ⊆ A, then with high probability the convolution 1 C * 1 B will approximate the function |C| |A| 1 A * 1 B . This means that the approximation will hold for many subsets C of A; so many, in fact, that there must be some relations amongst the sets: lots of them must in fact be translates of one another, which is the second idea. The translates so obtained correspond to translates that leave 1 A * 1 B approximately invariant (in the appropriate norm).
Surprisingly little background is needed to prove Proposition 1.1; all we shall assume is some basic familiarity with the probabilistic method-see for example [1] or [44] for more details on this. We shall prove the following equivalent version of Proposition 1.1; the equivalence follows immediately from the reflection identity (2.2). Proposition 3.1 (L 2 -almost-periodicity, left-translates). Let G be a group, let A, B ⊆ G be finite subsets, and let ǫ ∈ (0, 1) be a parameter. Suppose S ⊆ G is such that |S · A| K|A|. Then there is a set T ⊆ S −1 of size Proof. Let k be an integer between 1 and |A|/2 that we shall fix later and let C be a random subset of A of size k, chosen uniformly out of all such sets. Let us write µ C := 1 C · |A|/k for a normalized version of the indicator function of C. It is easy to see that Eµ C * 1 B (x) = 1 A * 1 B (x) for each x ∈ G and that the variance Summing this inequality over all x ∈ A · B, the support of 1 A * 1 B , we obtain holds. By (3.1) and Markov's inequality we thus have that where P C∈( X k ) refers to the uniform distribution on k-sets in a set X. We now consider k-sets C chosen uniformly at random from Y : 2) and the hypothesis that |S · A| K|A|, then, we have that Summing this inequality over all t ∈ S −1 thus gives In particular there exists a set C for which the set T := {t ∈ S −1 : tC approximates A} has size at least |S|/(2K) k . For this set C we have for each t ∈ T T −1 by the triangle inequality. The proposition now follows upon choosing k := ⌈8/ǫ 2 ⌉. (Note that the conclusion of the proposition is trivial if k > |A|/2.) We need to argue only a little more subtly in order to establish the analogous estimate for higher L p norms: we just make use of higher moments than the variance. In order to do this we shall need some more information about random variables of the type 1 C * 1 B (x) considered above. Since 1 C * 1 B (x) = |C ∩ xB −1 |, a moment's thought reveals that this random variable follows a hypergeometric distribution: a random variable X is said to follow a hypergeometric distribution with parameters N, M and k if for each integer j 0. Thus one may think of X as counting the number of marked objects one obtains when selecting k objects randomly and without replacement from a population of N objects, a total M of which are marked. The proof of the following bounds on the moments of hypergeometrically distributed random variables is elementary, though somewhat tangential to our main arguments, so we postpone it till Appendix A.
Lemma 3.2. Let m 1 and suppose that X follows a hypergeometric distribution with parameters N, M and k as above. Then With these estimates in hand the proof of Proposition 1.3 is straightforward. Again we prove the following trivially equivalent version.
Proof. We follow the proof of Proposition 3.1, letting C be a random subset of A of size k for some k that is to be fixed. Fix an element x ∈ G. As alluded to above, the random variable 1 C * 1 B (x) follows a hypergeometric distribution: where M := 1 A * 1 B (x) = |A ∩ xB −1 |, the probability being nothing but the proportion of k-sets C in A that contain precisely j elements from A ∩ xB −1 . Lemma 3.2 therefore tells us that or, using the notation µ C := |A| k 1 C , Summing over all x ∈ A · B then yields the right-hand side of which we denote by λ. From this it follows by Markov's inequality that We may now argue exactly as in the proof of Proposition 3.1, replacing the L 2 -version of approximation there with this L 2m -version. We thus obtain a set C ⊆ S · A of size k such that the set 2λ} has size at least |S|/(2K) k . The result now follows from the triangle inequality upon noting the bound and choosing k := ⌈49m/ǫ⌉.
Remark 3.4. We have not attempted to optimize the constant 50 that appears in the exponent of the density of the set T in this proposition; one can certainly reduce it, though any such reduction would be largely irrelevant for our applications.

Structures in product sets
In this section we provide proofs of the applications discussed in the first part of §1.3.
These results were all versions of the statement that product sets are structured objects, with various meanings. Theorem 1.6 said that sets A 2 · A −2 are structured in the sense that they contain large iterated product sets; this is perhaps the most straightforward consequence of Proposition 3.1: Proof of Theorem 1.6. Set ǫ := 1/k √ K and apply Proposition 3.1 to A with B = S = A to obtain a set T ⊆ A −1 of size at least |A|/(2K) 9k 2 K such that for each t ∈ T T −1 . Write S := T T −1 . By the triangle inequality we then have for each t ∈ S k . The left-hand side of this inequality can be expanded as Since A has small doubling, it also has large multiplicative energy by (2.4): E(A, A) |A| 3 /K. Hence we thus have that S k ⊆ A 2 · A −2 as desired. Furthermore, each element t ∈ S k has many representations as products in the way claimed, as follows from (2.1).
We record the following more general version of Theorem 1.6; the proof is the same except we do not specialize all the parameters when applying Proposition 3.1.
Theorem 4.1. Let G be a group, let A, B ⊆ G be finite, non-empty subsets and let k ∈ N be a parameter. Suppose E(A, B) |A| 2 |B|/K and that |D · A| K ′ |A| for some set D ⊆ G. Then there is a symmetric set S ⊆ D −1 D containing the identity such that Furthermore, each element of S k has at least |A| 2 |B|/2K representations as Note that this really does generalize Theorem 1.6 by (2.4). Proof of Theorem 1.7. Recall that we are given three finite sets A 1 , A 2 and A 3 , a 'popular' element x such that and a set D such that |A 3 · D| K ′ |A 3 |. Apply Proposition 1.1 to the sets A = A 2 and B = A 3 with ǫ := 1/2kK to obtain a set T ⊆ D of size at least |D|/(2K ′ ) 36k 2 K 2 such that for each t ∈ S := T T −1 . Thus for each t ∈ S k we have Let t ∈ S k . Then the inequality being an application of the Cauchy-Schwarz inequality. Thus Since x is a (1/K)-popular element and t ∈ S k was arbitrary, this completes the proof.
We turn now to the case of two sets. Theorem 1.8 is a special case of the following result, which has the advantage of giving stronger results in the situation when |A · B| is not small but the multiplicative energy E(A, B) is still large.
Theorem 4.2. Let G be a group, let A, B ⊆ G be finite, non-empty subsets and let k, n ∈ N be parameters. Suppose that Then there is a set T ⊆ S of size such that the product set A · B contains a left-translate of any set P ⊆ (T T −1 ) k of size at most n.
Proof. We may assume that n 2. Set m := log 2n, define γ by requiring 1 A * 1 B m m = γ m |AB||B| m and set ǫ := γ/ek 2 . Applying Proposition 1.3 to A and B with these parameters gives us a set T ⊆ S with for each t ∈ T T −1 . Let P ⊆ (T T −1 ) k be a set of size at most n. Suppose for a contradiction that A · B does not contain a left-translate of P . Then for every x ∈ G there must be an element t ∈ P for which xt / ∈ A · B, i.e., for which 1 A * 1 B (xt) = 0. Hence By the Cauchy-Schwarz inequality this is at least 1 A * 1 B 2m m /|AB|. Recalling the definition of ǫ and m then gives the desired contradiction; hence there must be some element x for which xP ⊆ A · B. The result now follows upon noting that γ 1/(K 1 K 2 ) 1/2 ; this follows from Hölder's inequality and (2.3).  If |A · B| is not small compared to |A| then the conclusion of the theorem becomes much less effective. If one still has the energy condition E(A, B) |A||B| 2 /K and A and B are of a similar size then one can use the Balog-Szemerédi-Gowers theorem [43,Theorem 5.2] to obtain large subsets A ′ ⊆ A and B ′ ⊆ B that one can then apply the theorem to effectively; this would yield better bounds than using a large value of K 2 directly. We omit the details.

Obtaining structured sets of translates
While Propositions 1.1 and 1.3 yield very large sets of translates for which 1 A * 1 B is approximately translation-invariant, one often needs these sets to be structured as well. Indeed, for the abelian applications in this paper we shall need to find arithmetic progressions of such translates. With Fourier-analytic methods the existence of an arithmetic progression of almost-periods is usually easy to obtain since one usually gets a Bohr set of translates, but we do not have this convenience. Instead we shall generate the structure by repeated set-addition.
We say that an arithmetic progression P in an abelian group has length k if it can be written as P = {a, a + d, . . . , a + (k − 1)d} for some non-zero element d. Note that this notion may be somewhat degenerate in some groups.
Lemma 5.1. Let G be an abelian group, let S ⊆ G be a finite subset that satisfies |S + S| K|S| or |S − S| K|S| and let k ∈ N. Suppose A ⊆ S satisfies |A| δ|S| where δ > K 3k/2 /|S| 1/(k+1) . Then the set kA − kA contains a symmetric arithmetic progression of length at least 2 k+1 passing through 0, with non-zero step d ∈ A − A.
To prove this we require a simple preliminary result. (This is not required if K = 1, as would be the case if X is a group.) Lemma 5.2. Let G be an abelian group and let A ⊆ G be a finite subset satisfying |A + A| K|A| or |A − A| K|A|. Let k ∈ N. Then |A − 2 k · A| K 3k |A|.
Here we write λ · A for the dilate {λa : a ∈ A}. This result is Theorem 15 of Bukh [9] specialized to the case λ = −2. We include the short proof for completeness.
Proof. By the Ruzsa triangle inequality, Lemma 2.1, we have that The lemma then follows from the instance |A − 2 · A| K 3 |A| of the Plünnecke-Ruzsa inequality, Theorem 2.2.
Proof of Lemma 5.1. It suffices to show that there are distinct elements a, b ∈ A for which 2 j (a − b) ∈ A − A for each j = 1, . . . , k, for then [−2 k , 2 k ] · (a − b) ⊆ kA − kA by binary expansion. Upon rearranging, this is equivalent to there being distinct a, b ∈ A and elements x j , y j ∈ A for which We claim that this system of equations must have a solution with a = b. Indeed, for each (k + 1)-tuple of elements (a, The image of this function is a subset of (S − 2 · S) × · · · × (S − 2 k · S), which by Lemma 5.2 has size at most K 3k(k+1)/2 |S| k . So if |A| k+1 > K 3k(k+1)/2 |S| k , which is the case given our bound on δ, then there must be two distinct tuples a = (a, x 1 , . . . , x k ) and b = (b, y 1 , . . . , y k ) in A k+1 for which f (a) = f (b). Clearly such tuples must have a = b and so provide a non-trivial solution to our system. Remark 5.3. One may wish to generate different types of structure depending on the group; for example, for problems in F n 3 it is more natural to generate subspaces instead of arithmetic progressions. Establishing such a result in F n 3 is relatively straightforward: it is easy to see that adding a symmetric subset of F n 3 to itself generates a subspace of dimension equal to the number of summands provided the set has enough linearly independent vectors.
The proof of Lemma 5.1 should be compared with an argument of the first-named author, Ruzsa and Schoen [12] that finds arithmetic progressions in single sumsets A + B, even when A and B are very sparse (much sparser than the sets considered in this paper).
Next we record a combination of Lemma 5.1 and Proposition 1.1 that will be useful to us in our proof of Roth's theorem. Recall that [N] := {1, . . . , N}. such that 0 ∈ P and, for each t ∈ P , for each t ∈ T − T . Now apply Lemma 5.1 to the set T to get a symmetric arithmetic progression P ⊆ kT − kT of length at least 2 k+1 + 1. By the triangle inequality we then have that any t ∈ P gives this progression would thus satisfy the conclusion of the corollary were it not for the fact that it may not be contained in [−N/2, N/2]. It is however contained in [−kN, kN], and so we may simply select a symmetric subprogression P ′ ⊆ [−N/2, N/2] of P of length at least 2⌊2 k−1 /k⌋ + 1; this progression will then do. Note that the condition on α comes from the requirement that k be at least 1.

Arithmetic progressions in sumsets
In this section we shall prove Theorem 1.9. Our task is thus to exhibit, for two sets A and we may certainly take K 2 = 2/α and K 3 = 2/β, and we may take K 1 = K 2 by (2.4). This gives us a set T ⊆ [N] of size δN, where δ exp −300k 2 (log 4/β)(log 2n)/α , such that A + B contains a translate of any subset P of kT − kT of size at most n. By Lemma 5.1 we can find an arithmetic progression P of length n in kT − kT provided a condition that may be seen to hold by a short calculation. Remark 6.1. In contrast to previous proofs of results of the form of Theorem 1.9, there was no need for us to embed the sets A and B in a finite group Z p for some prime p larger than N in order for us to carry out our analysis. Had we performed this embedding into Z p , however, we would have been able to use a slight simplification of Lemma 5.1, since we would only need to use it for K = 1. Remark 6.2. By a minor modification of the proof of Proposition 3.3-using the triangle inequality to get rid of the terms 1 A * 1 B (x) instead of µ C * 1 B (x)-one can deduce that P ⊆ A + C for a very small set C ⊆ B. One thus needs to translate A by very few elements of B in order to generate long arithmetic progressions.
We similarly get the following local version of Theorem 1.9. and n := 2 k+1 . As before we apply Theorem 4.2 to A and B with these parameters, but this time with S = A. Thus we get a set T ⊆ A of size |T | exp −150k 2 K 1 (log 2K 2 )(log 2n) |A| such that A + B contains any subset of kT − kT of size at most n. By the Plünnecke-Ruzsa inequality, Theorem 2.2, we have that |A + A| K 1 K 2 2 |A|. Another routine calculation now shows that we can apply Lemma 5.1 to T ⊆ A to find an arithmetic progression of length n in kT −kT , which yields the result. (Note again that the theorem is trivial if k < 1.) Remark 6.4. Recall that arithmetic progressions may be degenerate in some groups; consider for example the group F n 2 . Remark 6.5. Other local versions of this result are possible: we could for example work relative to a set S of small doubling such that |B + S| K|B|; this would yield slightly better bounds.
We cannot mention this topic without drawing the reader's attention to a remarkable construction [33] of Ruzsa that places a limit on the potential strength of results of the above form: Theorem 6.6. Let ǫ > 0. For every prime p > p 0 (ǫ) there is a symmetric set A ⊆ Z p of size at least (1/2 − ǫ)p such that A + A contains no arithmetic progression of length exp (log p) 2/3+ǫ .
Let us also mention that if one only wishes to find arithmetic progressions of length about log N in A + B then better results are available: one can work with much sparser sets than those considered in this paper by using the results in [12].

Roth's theorem
In this section we give our proof of Theorem 1.10. We shall employ a density-increment strategy, showing that if A ⊆ {1, . . . , N} is large and contains no three-term progressions then we can find a long arithmetic progression on which A has significantly increased density. We can then iterate this argument in order to obtain a contradiction. Let us introduce some notation before we begin. We denote the sum of a function f : Z → R with finite support over the three-term progressions in Z by T 3 (f ); thus Note that we may drop parts of subscripts when the meaning is clear. If f = 1 A is the indicator function of a set then T 3 (f ) is simply the number of three-term progressions in A. Note that this includes trivial (constant) three-term progressions and that it counts (x, x + d, x + 2d) separately from (x + 2d, x + d, x). We shall use the notation µ X to denote the normalized indicator function 1 X /|X| of a finite set X. For a subset A of X we shall say that A has density α relative to X if |A| = α|X|; when X is clear from the context we shall refer to α simply as the density of A. Finally, we write for the average of f over X.
The core of our proof of Roth's theorem lies in the following proposition. , where c > 0 is an absolute constant, such that Proof. Let Q be the arithmetic progression obtained from Corollary 5.4 applied to A with parameter ǫ 2 ; thus Q is large, Q = −Q and Q ⊆ [−N/2, N/2]. Let P be a symmetric subprogression of Q of length at least |Q|/8 such that 4P ⊆ Q; thus P ⊆ [−N/8, N/8]. We claim that this P satisfies the conclusion of the proposition. Indeed, and so these inequalities being instances of the triangle and Cauchy-Schwarz inequalities and the fact that P + P + 2 · P ⊆ Q.
We also require a preliminary lemma about T 3 . The following lemma gives a lower bound for the minimal number of three-term progressions that a set (or a function) can contain given upper bounds on the function r 3 ; it is a quantitative version of an averaging argument of Varnavides [45].
Lemma 7.2 (Varnavides' theorem). Let N be a positive integer and suppose that f : Then, for any positive integer M N 1/10 /2, The proof of this lemma proceeds via a double-counting argument and can be found in [13] for the case when f is the indicator function of a set. In order to pass from a result about sets, like the lemma stated in [13], to a result about a function f one can employ a standard probabilistic trick of defining a random set A in [N] by letting x ∈ A with probability f (x) independently for each x. See [44, Exercise 10.1.7] for more details.
We are now ready to proceed with the main body of the proof. We shall prove Theorem 1.10 in the following equivalent form. Proof. We begin by establishing the theorem for some c > 0; we shall then be able to bootstrap this to establish the full result. Various inequalities in the argument will hold by the assumption that N is large enough; we shall not state this assumption explicitly each time it is used.
Let A be a subset of {1, . . . , N} of size αN = r 3 (N) that does not contain any nontrivial three-term progressions, and let ǫ > 0 be a parameter that is to be fixed later. Applying Proposition 7.1 to A we obtain a long arithmetic progression P such that Our argument will be centred around the function we shall show that if 0 < δ < 1 is chosen appropriately then there must be an x for which |A ∩ (x − P )| > δ −1 α|P |. This will form the base of our density increment argument.
Suppose, then, that 1 A * µ P (x) δ −1 α for all x ∈ Z. Let f (x) := (δ/α)1 A * µ P (x), so that 0 f (x) 1 for all x, x f (x) = δN, and Note also that f is supported on A + P ⊆ [1 − N/8, 9N/8] ∩ Z, an interval of size at most 5N/4. Now, A contains only trivial three-term progressions and so T 3 (1 A ) = |A|. Thus (7.1) implies that provided ǫ 1/|A|. On the other hand, Lemma 7.2 tells us that Let us initially pick δ = 9/10. One may check by hand that r 3 (10) = 5; by picking M = 10 we therefore see that T 3 (f ) c 0 N 2 for some positive absolute constant c 0 . Comparing this to (7.2) we see that we obtain a contradiction provided we pick ǫ = c 1 α for some small constant c 1 > 0. (This is permissible provided α 1/ √ c 1 N , which we assume.) Hence we must have that |A ∩ (x − P )| 10 9 α|P | for some integer x, where P is a rather long progression. Let us assume that α (log N) −1/6 . Then |P | exp (log N) 1/8 ; we have thus shown that A has density at least 10 9 r 3 (N ) N on an arithmetic progression of length N 1 := |P |. We may thus rescale to obtain a set A 1 ⊆ {1, . . . , N 1 } that is also free of arithmetic progressions, but that is now much denser than the original set A.
We may now iterate this argument, obtaining a sequence of integers N j with N j exp (log N j−1 ) 1/8 and a sequence of densities δ j such that δ j 10 9 j r 3 (N ) N , the only requirements for proceeding to the next stage of the iteration being that δ j (log N j ) −1/6 and N j C for some absolute constant C. Since no δ j can exceed 1, this iteration must stop at some stage K with K log(N/r 3 (N )) log 10/9 , at which point one of these requirements must fail. From this we may deduce that This proves the theorem for a fixed exponent c of log log N. We may now use this to run the argument again, except that we do not now need to rely on numerical data in order to apply Lemma 7.2 effectively. That is, we may now pick δ arbitrarily small and then find a fixed value M for which 4 5 δ − r 3 (M )+2 M δ/2. This means that, instead of obtaining a density increment of a factor of 10 9 , we may obtain an increment of an arbitrarily large factor δ −1 , still on a progression of length at least exp (log N) 1/8 (though we now need N to be large enough in terms of δ). Following the above argument through again, this shows that for N N 0 (δ) and some constant C depending on δ.

Strong approximate groups
Finally we prove Proposition 1.11, the result about strong approximate groups; recall that we say that A is a strong K-approximate group if 1 A * 1 A (x) |A|/K for each x ∈ A 2 . This proposition does not follow directly from the almost-periodicity results; instead it uses the ideas in the proofs of those results in a slightly different way.
Proof of Proposition 1.11. We shall show that if C ⊆ A is chosen at random then CA ≈ A 2 with good probability. Indeed, let us start by picking a random set C ⊆ A of size k. By the hypothesis on A, any x ∈ A 2 that satisfies |µ the latter inequality being a standard distributional inequality for hypergeometric distributions; see, for example, [11] (and cf. Proposition A.3). Summing this over all x ∈ A 2 we obtain the estimate Markov's inequality therefore yields let us pick λ := 4e −2k/K 2 to make this probability be at least 1/2. Now note that |A 2 | K|A|; this follows from the inequality 1 A * 1 A (x) |A|1 A 2 (x)/K holding for all x. As in the proof of Proposition 3.1, this means that there is a set C and a set T ⊆ A −1 of size at least |A|/(2K) k such that for any t ∈ T . For any two elements t 1 , t 2 ∈ T we therefore have |t 2 t −1 1 A 2 △ A 2 | 2λ|A 2 | by the triangle inequality. Thus we may take S := T T −1 after choosing k := ⌈(K 2 log 8/ǫ)/2⌉. Remark 8.1. It is easy to see that a strong K-approximate group must have small doubling, |A 2 | K|A|, but unlike with sets of small doubling it is not clear how abundant strong K-approximate groups of different sizes are, even in the group Z p for a prime p. Konyagin [27,Problem 5] raised the basic question of whether it is the case that for any set A ⊆ Z p of size at most √ p there exists some element x ∈ A + A such where C, c > 0 are absolute constants. Partial progress was made on this question by Luczak and Schoen [28], who also noted that work of Green and Ruzsa [21] implies that one can always find an x ∈ A + A with 1 A * 1 A (x) max(1, |A|/(log 2 p) 1/2+o (1) ). The results of this paper can be used to derive a bound similar to this, if perhaps slightly stronger, but we do not pursue this here.

Further remarks
We conclude with some remarks. 9.1. Convolutions of functions. Although we have focused on convolutions of sets in this paper, it is relatively easy to deduce results for convolutions of functions. Indeed, let f, g : G → [0, 1] be two functions with finite supports S f and S g . Define random sets A, B ⊆ G by stipulating that x ∈ A with probability f (x) and x ∈ B with probability g(x), all independently. One may then use a concentration inequality such as Chernoff's inequality [44,Theorem 1.8] to deduce that there is a choice of sets A ⊆ S f and B ⊆ S g such that A has size very close to f , B has size very close to g and |1 A * 1 B (x) − f * g(x)| is small for every x ∈ S 1 + S 2 . An almost-periodicity result saying that ǫ 2 ( f ) ( g) 2 for every t ∈ T T −1 for a large set T then follows from the corresponding result for sets, and similarly for L p -almost-periodicity. One may then deal with arbitrary realvalued functions with finite support by rescaling. It is also likely that one can prove the almost-periodicity results directly for functions, though the statements will look slightly different; we do not pursue this here.

9.2.
Comparisons with Fourier-analytic results. Our proofs of the almost-periodicity results in this paper have been combinatorial, which meant that there was no need for us to distinguish between abelian and non-abelian groups. When dealing with finite abelian groups, however, it is possible to derive results similar to Corollaries 1.2 and 1.4 using Fourier analysis. Indeed, in the abelian setting Corollary 1.2 is essentially a result of Bogolyubov [2] coupled with a result of Chang [10] on the large spectra of subsets of abelian groups; see Lemma 4.36 and (the proof of) Proposition 4.39 in [44]. An important difference between the two approaches is that Fourier analysis provides one with more information about the set T : one may take it to be a so-called Bohr set (an approximate annihilator of a set of characters in the Pontryagin dual of G), and it is well known that Bohr sets are arithmetically structured sets. For instance, Bohr sets contain long arithmetic progressions, which means that one does not need to appeal to structure-generation results like Lemma 5.1. If one uses this as the base for the arguments of §7 (set in Z N rather than [N]) then one can obtain a bound for r 3 (N) similar to that of an old but recently published proof of Roth's theorem due to Szemerédi [40]; indeed, our argument is in some ways quite similar to Szemerédi's. We present further details of this argument in the note [14].
It is much less clear that one can obtain an L p -almost-periodicity result of a type similar to Corollary 1.4 for abelian groups using Fourier analysis. One may extract such a result from the paper [4] of Bourgain that exhibits the existence of long arithmetic progressions in A + B; indeed, the main thrust of the paper is to establish the estimates required to prove such an almost-periodicity result. Specifically one can obtain a result of the following type.
By a Bohr set B(Γ, ρ) here we mean a set of the form where Γ ⊆ G is a collection of characters.
Bourgain's argument is very elegant though also somewhat complex, relying on some quite sophisticated manipulations of sets of Fourier coefficients. We shall not say more about this here, save for making two comments. First, the set B produced by the above proposition will in general be somewhat smaller than the set T given by Corollary 1.4, but is also guaranteed to contain more structure, which is ultimately what yields Bourgain's superior exponent of 1/3 in place of our 1/4 in the length of the arithmetic progressions one finds in A + B. Second, if one wishes to compare the L p norm to αβ, say, then Corollary 1.4 is useful even if one of the sets A and B is rather sparse whereas Proposition 9.1 requires both sets to be quite large. More details about Proposition 9.1 may be found in the note [39].
Obtaining the local versions of our results using Fourier analysis seems harder. We note that there are tools that get around this to some extent; notably there is the 'modelling' lemma of Green and Ruzsa [20] that allows one to 'isomorphically embed' a set A ⊆ G with small doubling |A + A| K|A| as a dense set A ′ ⊆ G ′ , where |A ′ | f (K)|G ′ |. See for example the paper [38] of Sanders for an efficient proof of a local version of Roth's theorem that makes use of this lemma. Interestingly, modelling results of the same kind cannot exist for non-abelian groups [41]. 9.3. Roth's theorem in other settings. In this paper we proved Roth's theorem in the setting of the integers {1, . . . , N}. The Fourier-analytic proofs of Roth's theorem generally become simpler when studied in the vector space F n 3 over the finite field F 3 (or F n p for a fixed prime p), and this holds true for our argument as well. There are two main reasons for this. One is that it is very easy to establish a result similar to Lemma 5.1 in F n 3 , as remarked in §5. The other is that it becomes easier to run through the density increment strategy itself, since one can induct on subspaces rather than on arithmetic progressions. In particular one does not really need a result corresponding to Lemma 7.2 (Varnavides' theorem). The bounds one obtains for r 3 (F n 3 ) are not significantly better than the corresponding ones for r 3 (N) with N ≈ 3 n , however.
We should mention in this context that Seva Lev has recently produced a proof [26] of the F n p -version of Roth's theorem that removes the use of characters from the general framework of Meshulam's proof [29]. Lev's proof involves very different ideas to those of this paper, however. 9.4. Extensions. There are many possible potential extensions of the methods presented in this paper. It seems likely that the ideas used could also be used to tackle locally compact groups, this being a natural setting for many of the results considered here (where we have only dealt with discrete groups). An area of application that we have not discussed in detail in the current paper is that of Freiman-type results; let us for now remark that it is easy to obtain a number of rudimentary Freiman-type theorems by coupling our almost-periodicity results with so-called covering lemmas. This will be followed up elsewhere.
Appendix A. The moments of the binomial and hypergeometric distributions As noted in the proof of Proposition 3.3, if one selects a random k-element subset C from a set A in an ambient group G then, for any fixed element x ∈ G, the random variable 1 C * 1 B (x) follows a hypergeometric distribution. In this appendix we prove the bounds of Lemma 3.2 on the moments of such a distribution.
Recall that X follows a hypergeometric distribution with parameters N, M and k if so that X can be thought of as counting the number of marked objects selected when k objects are picked without replacement from a population of N objects, M of which are marked. If the k objects are selected with replacement then the number of marked objects selected follows a binomial distribution with parameters n = k and p = M/N, and the two distributions are closely related. We have found certain estimates for the binomial distribution to be more readily available in print than the corresponding estimates for the hypergeometric distribution; the following corollary of a result of Hoeffding [23,Theorem 4] allows us to make use of these results.
Proposition A.1. Let X follow a hypergeometric distribution as above and let Y follow a binomial distribution with parameters n = k and p = M/N. Then for any convex, continuous function f we have Ef (X) Ef (Y ).
Lemma 3.2 therefore follows immediately from the following proposition.
Proposition A.2. Let m 1 and suppose that X follows a binomial distribution with parameters n and p. Then E|X − np| 2m 2(3mnp + m 2 ) m . (A.1) In order to prove this we shall make use of the following deviation estimates, the type of which is often associated with the names of Bennett, Bernstein, Chernoff and Hoeffding.
Proposition A.3. Let X follow a binomial distribution with parameters n and p. Then and P(X np + t) exp − t 2 2(np + t/3) (A.3) for any t 0.
Proofs of these estimates may be found in [25]; see also [3] and [1]. They can be derived from an application of Markov's inequality to the random variable e λ(X−np) using the fact that the moment generating function Ee λ(X−np) is e −λpn (pe λ + 1 − p) n .
Remark A.4. By being a bit more careful in the above proof one could obtain somewhat smaller values for the constants appearing in the proposition, though this is not particularly important for our applications. We should also remark that, although we only required it for binomial random variables, Proposition A.2 holds even when X is a sum of independent Bernoulli random variables that are not necessarily identically distributed. In that setting n is the number of summands and p is EX/n, and one may prove the result exactly as above since Proposition A.3 holds for such random variables. (Let us also note that Proposition A.2 holds with different constants for sums of more general random variables.)