zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A probabilistic technique for finding almost-periods of convolutions. (English) Zbl 1234.11013

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<ϵ<1 be some parameter, and suppose B has density β. Then there is a subset T of G of size at least (β/2) 9/ε 2 |G| such that for each tTT -1 one has

1 A *1 B (xt)-1 A *1 B (x) 2 2 ε 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|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 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 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)].


MSC:
11B30Arithmetic combinatorics; higher degree uniformity
05D40Probabilistic methods in combinatorics
References:
[1]N. Alon, J.H. Spencer, The Probabilistic Method, 3rd ed. John Wiley & Sons, 2008.
[2]Bogolioùboff N. (1939) Sur quelques propriétés arithmétiques des presque-périodes. Ann. Chaire Phys. Math. Kiev 4: 185–205
[3]B. Bollobás, Random Graphs, 2nd ed., CUP, 2001.
[4]J. Bourgain, On arithmetic progressions in sums of sets of integers, A tribute to Paul Erdos, CUP (1990), 105–109.
[5]Bourgain J. (2008) Roth’s theorem on progressions revisited. J. Anal. Math. 104: 155–192 · Zbl 1155.11011 · doi:10.1007/s11854-008-0020-x
[6]E. Breuillard, B. Green, Approximate groups, I: the torsion-free nilpotent case, Journal of the Inst. of Math. Jussieu, available on CJO 02 Jun 2010, doi: 10.1017/S1474748010000150
[7]Breuillard E., Green B. (2010) Approximate groups, II: the solvable linear case. Quart. J. Math. 00: 1–9
[8]E. Breuillard, B. Green, T. Tao, Linear approximate groups, preprint (2010); arXiv:1001.4570
[9]Bukh B. (2008) Sums of dilates. Combin. Probab. Comput. 17(5): 627–639 · Zbl 1191.11007 · doi:10.1017/S096354830800919X
[10]Chang M.-C. (2002) A polynomial bound in Freiman’s theorem. Duke Math. J. 113(3): 399–419 · Zbl 1035.11048 · doi:10.1215/S0012-7094-02-11331-3
[11]Chvátal V. (1979) The tail of the hypergeometric distribution. Discrete Math. 25(3): 285–287 · Zbl 0396.60016 · doi:10.1016/0012-365X(79)90084-0
[12]E. Croot, I.Z. Ruzsa, T. Schoen, Arithmetic progressions in sparse sumsets, Combinatorial Number Theory, de Gruyter, Berlin (2007), 157–164.
[13]Croot E., Sisask O. (2009) A new proof of Roth’s theorem on arithmetic progressions. Proc. Amer. Math. Soc. 137(3): 805–809 · Zbl 1202.11011 · doi:10.1090/S0002-9939-08-09594-4
[14]E. Croot, O. Sisask, A note on proving Roth’s theorem using Bogolyubov’s method, note available at http://people.math.gatech.edu/ecroot/expository.html
[15]D. Fisher, N.H. Katz, I. Peng, On Freiman’s theorem in nilpotent groups, preprint (2009); arXiv:0901.1409
[16]G.A. Freiman, Foundations of a Structural Theory of Set Addition, Translations of Mathematical Monographs 37, AMS (1973).
[17]Freiman G.A., Halberstam H., Ruzsa I.Z. (1992) Integer sum sets containing long arithmetic progressions. J. London Math. Soc. (2) 46(2): 193–201 · Zbl 0768.11005 · doi:10.1112/jlms/s2-46.2.193
[18]Green B. (2002) Arithmetic progressions in sumsets. Geom. Funct. Anal. 12(3): 584–597 · Zbl 1020.11009 · doi:10.1007/s00039-002-8258-4
[19]B. Green, Review MR2429639 (2009k:11023) of [ŁuS], Mathematical Reviews, available at http://www.ams.org/mathscinet-getitem?mr=2429639
[20]Green B., Ruzsa I.Z. (2007) Freiman’s theorem in an arbitrary abelian group. J. Lond. Math. Soc. (2) 75(1): 163–175 · Zbl 1133.11058 · doi:10.1112/jlms/jdl021
[21]Green B., Ruzsa I.Z. (2006) Sets with small sumset and rectification. Bull. London Math. Soc. 38(1): 43–52 · Zbl 1155.11307 · doi:10.1112/S0024609305018102
[22]B. Green, T. Sanders, T. Tao, Personal communication.
[23]Hoeffding W. (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58: 13–30 · Zbl 0127.10602 · doi:10.2307/2282952
[24]E. Hrushovski, Stable group theory and approximate subgroups, preprint (2009); arXiv:0909.2190
[25]S. Janson, Large deviation inequalities for sums of indicator variables, Tech. Report 1994:34, Uppsala; available at http://www.math.uu.se/svante/papers/index.html
[26]V.F. Lev, Character-free approach to progression-free sets, preprint (2009); arXiv:0911.0513
[27]V.F. Lev, Reconstructing integer sets from their representation functions, Electron. J. Combin. 11:1 (2004), Research Paper 78, 6 pp. (electronic).
[28]Łuczak T., Schoen T. (2008) On a problem of Konyagin. Acta Arith. 134(2): 101–109 · Zbl 1167.11008 · doi:10.4064/aa134-2-1
[29]Meshulam R. (1995) On subsets of finite abelian groups with no 3-term arithmetic progressions. J. Combin. Theory Ser. A 71(1): 168–172 · Zbl 0832.11006 · doi:10.1016/0097-3165(95)90024-1
[30]D.H.J. Polymath, A new proof of the density Hales–Jewett theorem, preprint (2009); arXiv:0910.3926
[31]L. Pyber, E. Szabó, Growth in finite simple groups of Lie type, preprint (2010); arXiv:1001.4556
[32]Roth K.F. (1953) On certain sets of integers. J. London Math. Soc. 28: 104–109 · Zbl 0050.04002 · doi:10.1112/jlms/s1-28.1.104
[33]Ruzsa I.Z. (1991) Arithmetic progressions in sumsets. Acta Arith. 60(2): 191–202
[34]Ruzsa I.Z. (1994) Generalized arithmetical progressions and sumsets. Acta Math. Hungar. 65(4): 379–388 · Zbl 0816.11008 · doi:10.1007/BF01876039
[35]I.Z. Ruzsa, E. Szemerédi, Triple systems with no six points carrying three triangles, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. János Bolyai 18, North-Holland, Amsterdam-New York (1978). 939–945,
[36]Sanders T. (2008) Additive structures in sumsets. Math. Proc. Cambridge Philos. Soc. 144(2): 289–316 · Zbl 1241.11010 · doi:10.1017/S030500410700093X
[37]Sanders T. (2010) On a non-abelian Balog–Szemerédi-type lemma. J. Aust. Math. Soc. 89: 127–132 · Zbl 1223.11014 · doi:10.1017/S1446788710000236
[38]Sanders T. (2009) Three-term arithmetic progressions and sumsets. Proc. Edinb. Math. Soc. (2) 52(1): 211–233 · Zbl 1221.11029 · doi:10.1017/S0013091506001398
[39]O. Sisask, Bourgain’s proof of the existence of long arithmetic progressions in A + B, note (2009); available at http://www.maths.qmul.ac.uk/olof/
[40]E. Szemerédi, An old new proof of Roth’s theorem, Additive combinatorics, CRM Proc. Lecture Notes 43, Amer. Math. Soc., Providence, RI (2007), 51–54.
[41]T. Tao, Finite subsets of groups with no finite models, blog post available at http://terrytao.wordpress.com/2008/10/06/finite-subsets-of-groupswith-no-finite-models/+ (2008).
[42]Tao T. (2010) Freiman’s theorem for solvable groups. Contrib.. Discrete Math. 5(2): 137–184
[43]Tao T. (2008) Product set estimates for non-commutative groups. Combinatorica 28(5): 547–594 · Zbl 1254.11017 · doi:10.1007/s00493-008-2271-7
[44]T. Tao, V.H. Vu, Additive combinatorics, CUP (2006).
[45]Varnavides P. (1959) On certain sets of positive density. J. London Math. Soc. 34: 358–360 · Zbl 0088.25702 · doi:10.1112/jlms/s1-34.3.358