A probabilistic technique for finding almost-periods of convolutions

DOI10.1007/S00039-010-0101-8MaRDI QIDQ616150zbMATH OpenOpenAlexFDO

Publication date 7 January 2011

Published in Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.2978

arithmetic progression Bogolyubov's method convolution Freiman's theorem product-set Roth's theorem sum-set

Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Arithmetic combinatorics; higher degree uniformity (11B30)

Abstract: 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.

Review text

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)].

Recommendations

Cites work

Cited in

(46)

This page was built for publication: A probabilistic technique for finding almost-periods of convolutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616150)