×

Convolutions of sets with bounded VC-dimension are uniformly continuous. (English) Zbl 1498.11043

Summary: We study a notion of VC-dimension for subsets of groups, defining this for a set \(A\) to be the VC-dimension of the family \(\{(xA)\cap A:x\in A\cdot A^{-1}\}\). We show that if a finite subset \(A\) of an abelian group has bounded VC-dimension, then the convolution \(1_A\ast 1_{-A}\) is Bohr uniformly continuous, in a quantitatively strong sense. This generalises and strengthens a version of the stable arithmetic regularity lemma of Terry and Wolf in various ways. In particular, it directly implies that the polynomial Bogolyubov-Ruzsa conjecture – a strong version of the polynomial Freiman-Ruzsa conjecture – holds for sets with bounded VC-dimension. We also prove some results in the non-abelian setting.
In some sense, this gives a structure theorem for translation-closed set systems with bounded (classical) VC-dimension: if a VC-bounded family of subsets of an abelian group is closed under translation, then each member has a simple description in terms of Bohr sets, up to a small error.

MSC:

11B30 Arithmetic combinatorics; higher degree uniformity
43A15 \(L^p\)-spaces and other function spaces on groups, semigroups, etc.
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] N. Alon, J. Fox and Y. Zhao, Efficient arithmetic regularity and removal lemmas for induced bipartite patterns, Discrete Anal. 2019, Paper No. 3, 14 pp. https://arxiv.org/abs/1801.04675. 3, 4, 20, 21 · Zbl 1472.11054
[2] S. Boucheron, G. Lugosi and P. Massart, Concentration inequalities, OUP, 2013. 6 · Zbl 1279.60005
[3] J. Bourgain, On arithmetic progressions in sums of sets of integers, A tribute to Paul Erdős, 105-109 (CUP, 1990). 4 · Zbl 0715.11006
[4] J. Chapman, Private communication. 22
[5] G. Conant and A. Pillay, Approximate subgroups with bounded VC-dimension, preprint available at https://arxiv.org/abs/2004.05666. 19
[6] G. Conant, A. Pillay and C. Terry, A group version of stable regularity, Math. Proc. Cambridge Philos. Soc. 168 (2020), no. 2, 405-413. https://arxiv.org/abs/1710.06309. 3, 18, 19 · Zbl 07167602
[7] G. Conant, A. Pillay and C. Terry, Structure and regularity for subsets of groups with finite VC-dimension, to appear in J. Eur. Math. Soc, https://arxiv.org/abs/1802.04246. 3, 19
[8] E. Croot, I. Łaba and O. Sisask, Arithmetic progressions in sumsets and L p -almost-periodicity, Combin. Probab. Comput. 22 (2013), no. 3, 351-365. https://arxiv.org/abs/1103.6000. 4, 5, 9 · Zbl 1348.11011
[9] E. Croot and O. Sisask, A probabilistic technique for finding almost-periods of convolutions, Geom. Funct. Anal. 20 (2010), no. 6, 1367-1396. https://arxiv.org/abs/1003.2978. 4, 6, 7 · Zbl 1234.11013
[10] W. T. Gowers, Lower bounds of tower type for Szemerédi’s uniformity lemma, Geom. Funct. Anal. 7 (1997), no. 2, 322-337. https://doi.org/10.1007/PL00001621. 2 · Zbl 0876.05053 · doi:10.1007/PL00001621
[11] B. Green, A Szemerédi-type regularity lemma in abelian groups, with applications, Geom. Funct. Anal. 15 (2005), no. 2, 340-376. https://arxiv.org/abs/math/0310476. 2 · Zbl 1160.11314
[12] B. Green, Finite field models in additive combinatorics, Surveys in combinatorics 2005, 1-27, London Math. Soc. Lecture Note Ser. 327, CUP, 2005. https://arxiv.org/abs/math.NT/ 0409420. 5 · Zbl 1155.11306
[13] B. Green, Notes on the Polynomial Freiman-Ruzsa conjecture, available at http://people.maths.ox.ac.uk/greenbj/papers/PFR.pdf. 5
[14] B. Green and I. Z. Ruzsa, Freiman’s theorem in an arbitrary abelian group, J. Lond. Math. Soc. (2) 75 (2007), no. 1, 163-175. https://arxiv.org/abs/math/0505198. 17 · Zbl 1133.11058
[15] D. Haussler, Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension, J. Combin. Theory Ser. A 69 (1995), no. 2, 217-232. https://doi.org/10.1016/0097-3165(95)90052-7. 6, 20, 21 · Zbl 0818.60005 · doi:10.1016/0097-3165(95)90052-7
[16] G. Petridis, New proofs of Plünnecke-type estimates for product sets in groups, Combinatorica 32 (2012), no. 6, 721-733. https://arxiv.org/abs/1101.3507. 18 · Zbl 1291.11127
[17] I. Z. Ruzsa, Arithmetic progressions in sumsets, Acta Arith. 60 (1991), no. 2, 191-202. 5 · Zbl 0728.11009
[18] T. Sanders, Green’s sumset problem at density one half, Acta Arith. 146 (2011), no. 1, 91-101. https://arxiv.org/abs/1003.5649. 5 · Zbl 1225.11015
[19] T. Sanders, On the Bogolyubov-Ruzsa lemma, Anal. PDE 5 (2012), no. 3, 627-655. https://arxiv.org/abs/1011.0107. 5, 9 · Zbl 1320.11009
[20] T. Sanders, The structure theory of set addition revisited, Bull. Amer. Math. Soc. 50 (2013), no. 1, 93-127. https://arxiv.org/abs/1212.0458. 5 · Zbl 1337.11014
[21] T. Schoen and O. Sisask, Roth’s theorem for four variables and additive structures in sums of sparse sets, Forum of Mathematics, Sigma 4 (2016), e5 (28 pages). · Zbl 1333.11014
[22] https://doi.org/10.1017/fms.2016.2. 4, 9 · Zbl 1333.11014 · doi:10.1017/fms.2016.2
[23] P. Simon, VC-sets and generic compact domination, Israel J. Math. 218 (2017), no. 1, 27-41. https://arxiv.org/pdf/1502.04513.pdf. 3, 20 · Zbl 1367.03068
[24] M. Talagrand, Sharper bounds for Gaussian and empirical processes, Ann. Probab. 22 (1994), no. 1, 28-76. https://dx.doi.org/10.1214/aop/1176988847. 6 · Zbl 0798.60051 · doi:10.1214/aop/1176988847
[25] T. Tao and V. H. Vu, Additive Combinatorics, CUP, 2006. 8, 9, 10, 11, 14, 18
[26] C. Terry and J. Wolf, Stable arithmetic regularity in the finite-field model, Bull. Lond. Math. Soc. 51 (2019), no. 1, 70-88. https://arxiv.org/abs/1710.02021. 1, 2, 18, 19 · Zbl 1462.11015
[27] C. Terry and J. Wolf, Quantitative structure of stable sets in finite abelian groups , Trans. Amer. Math. Soc. 373 (2020), no. 6, 3885-3903. https://arxiv.org/abs/1805.06847. 19 · Zbl 1477.11023
[28] V. N. Vapnik and A. Ja.Červonenkis, The uniform convergence of frequencies of the appearance of events to their probabilities, (Russian. English summary), Teor. Verojatnost. i Primenen. 16 (1971), 264-279 · Zbl 0247.60005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.