A probabilistic technique for finding almost-periods of convolutions (Q616150)

This paper introduces a very interesting and original new method in Additive Combinatorics, and gives several applications. It is a very common technique in Additive Combinatorics to study quantities of interest, such as sum-sets or the three-term arithmetic progressions contained in a set, via considering convolutions of appropriate indicator functions, and related considerations. In particular, it then can be key to assert that these convolutions are `smooth' (in appropriate senses). This was often done using Fourier analysis. Here a different approach is developed. One of its key features is that it is insensitive as to whether the group is abelian or not. Technically, almost periodicity results for the convolutions of indicator functions are established. We state one such result in detail. Let \(G\) be a finite group, written multiplicative and not necessarily abelian, and \(A\) and \(B\) subsets of \(G\). Let \(0<\epsilon <1\) be some parameter, and suppose \(B\) has density \(\beta\). Then there is a subset \(T\) of \(G\) of size at least \((\beta/2)^{9 / \varepsilon^2}|G|\) such that for each \(t \in TT^{-1}\) one has \[ \| 1_A * 1_B(xt) - 1_A * 1_B(x)\|_2^2 \leq \varepsilon^2 |A||B|^2. \] Informally, this means that the convolution is sort of continuous, since there are many translates \(t\) such that the function \(1_A * 1_B\) does not change too much, in an \(L_2\)-sense, when translated by \(t\). In fact, even a local version of this result is established, where one does not require that the group is finite or the set \(B\) is dense in the ambient group, yet it is sufficient that there is an (auxiliary) large set \(S\) with which \(B\) `interacts nicely' in the sense that \(|BS|\leq K|B|\) for some parameter \(K\) (that of course influences the conclusion of the result). Moreover, analog results are obtained for \(L_{2m}\)-norms instead of the \(L_2\)-norm. The proofs are probabilistic. Several applications of these results are given. We give a quick and incomplete overview. A new proof of Roth's theorem on arithmetic progressions is given, which is interesting as it avoids Fourier analysis and still gives a reasonable bound on \(r_3 (N)\). (It is slightly better than Roth's original bound, yet not as good as the then best bound due to Bourgain; however cf.~below.) A variant of results of Bourgain and Green on the existence of long arithmetic progressions in a sumset \(A+B\) is established that it is applicable for sets of smaller density than the other results (while yielding a weaker conclusion in case of high density). A non-commutative analogue of the, in the commutative case, classical result that for \(A\) a set with small doubling the set \(2A-2A\) is highly structured is established, which is similar to a recent result due to \textit{T. Sanders} [J. Aust. Math. Soc. 89, No. 1, 127--132 (2010; Zbl 1223.11014)], yet the present bounds are better. In addition, results on \(K\)-approximate subgroups are obtained. The applicability of this method is not limited to these applications. For example, it was already used in \textit{T. Sanders}'s recent work obtaining the currently best bound on \(r_3(N)\) [On Roth's theorem on progressions, Ann. Math. (2) 174, No. 1, 619--636 (2011; Zbl 1264.11004)].