Structure in Sets with Logarithmic Doubling

Sanders, T.

Canadian mathematical bulletin, Tome 56 (2013) no. 2, pp. 412-423

Résumé

Suppose that $G$ is an abelian group, $A\,\subset \,G$ is finite with $\left| A\,+\,A \right|\,\le \,K\left| A \right|$ and $\eta \,\in \,(0,\,1]$ is a parameter. Our main result is that there is a set $L$ such that $$\left| A\,\cap \,\text{Span}\left( L \right) \right|\ge {{K}^{-{{O}_{n}}\left( 1 \right)}}\left| A \right|\,\,\,\,\text{and}\,\,\,\,\,\left| L \right|=O\left( {{K}^{n}}\log \left| A \right| \right).$$ We include an application of this result to a generalisation of the Roth-Meshulam theorem due to Liuand Spencer

Détail

DOI : 10.4153/CMB-2011-165-0

Mots-clés : 11B25, Fourier analysis, Freiman's theorem, capset problem

Bibliographie

[1] [1] Balog, A. and E. Szemerédi, A statistical theorem of set addition. Combinatorica 14(1994), no. 3, 263–268. Google Scholar | DOI

[2] [2] Chang, M.-C., A polynomial bound in Fre˘ıman's theorem. Duke Math. J. 113(2002), no. 3, 399–419. Google Scholar | DOI

[3] [3] Croot, E. S. and Lev, V. F., Open problems in additive combinatorics. In: Additive Combinatorics. CRM Proc. Lecture Notes 43. American Mathematical Societh, Providence, RI, 2007, pp. 207–233. Google Scholar

[4] [4] Freĭman, G. A., Foundations of a Structural Theory of Set Addition. Translations of Mathematical Monographs 37. American Mathematical Society, Providence, RI, 1973. Google Scholar

[5] [5] Gowers, W. T., A new proof of Szemerédi's theorem for arithmetic progressions of length four. Geom. Funct. Anal. 8(1998), no. 3, 529–551. Google Scholar | DOI

[6] [6] Green, B. J. and Ruzsa, I. Z., Fre˘ıman's theorem in an arbitrary abelian group. J. Lond. Math. Soc. 75(2007), no. 1, 163–175. Google Scholar | DOI

[7] [7] Green, B. J., Finite field models in additive combinatorics. In: Surveys in Combinatorics 2005. London Math. Soc. Lecture Note Ser. 327. Cambridge Univ. Press, Cambridge, 2005, pp. 1–27. Google Scholar

[8] [8] Löpez, J. M. and Ross, K. A., Sidon Sets. Lecture Notes in Pure and Applied Mathematics, 13. Marcel Dekker, New York, 1975. Google Scholar

[9] [9] Liu, Y.-R. and Spencer, C. V., A generalization of Meshulam's theorem on subsets of finite abelian groups with no 3-term arithmetic progression. Des. Codes Cryptogr. 52(2009), no. 1, 83–91. Google Scholar | DOI

[10] [10] Liu, Y.-R., Spencer, C. V., and Zhao, X., A generalization of Meshulam's theorem on subsets of finite abelian groups with no 3-term arithmetic progression. II. European J. Combin. 32(2011), no. 2, 258–264. Google Scholar | DOI

[11] [11] Meshulam, R.. On subsets of finite abelian groups with no 3-term arithmetic progressions. J. Combin. Theory Ser. A 71(1995), no. 1, 168–172. Google Scholar | DOI

[12] [12] Roth, K. F., On certain sets of integers. J. London Math. Soc. 28(1953), 104–109. Google Scholar | DOI

[13] [13] Rudin, W., Fourier Analysis on Groups. Reprint of the 1962 original. JohnWiley & Sons, New York, 1990. Google Scholar

[14] [14] Ruzsa, I. Z., Solving a linear equation in a set of integers. I. Acta Arith. 65(1993), no. 3, 259–282. Google Scholar

[15] [15] Ruzsa, I. Z., Generalized arithmetical progressions and sumsets. Acta Math. Hungar. 65(1994), no. 4, 379–388. Google Scholar | DOI

[16] [16] Sanders, T., On a non-abelian Balog–Szemerédi-type lemma. J. Aust. Math. Soc. 89(2010), no.1, 127–132. Google Scholar

[17] [17] Schoen, T., Near optimal bounds in Freıman's theorem. Preprint, 2010. Google Scholar

[18] [18] Shkredov, I. D., On sets of large trigonometric sums. Izv. Ross. Akad. Nauk Ser. Mat. 72(2008), no. 1, 161–182. Google Scholar

[19] [19] Shkredov, I. D., On sets with small doubling. Mat. Zametki 84(2008), no. 6, 927–947. Google Scholar

[20] [20] Szemerédi, E., Integer sets containing no arithmetic progressions. Acta Math. Hungar. 56(1990), no. 1-2, 155–158. Google Scholar | DOI

[21] [21] Tao, T. C., Structure and Randomness. Pages from Year One of a Mathematical Blog.. American Mathematical Society, Providence, RI, 2008. Google Scholar

[22] [22] Tao, T. C. and Vu, H. V., Additive Combinatorics. Cambridge Studies in Advanced Mathematics 105. Cambridge University Press, Cambridge, 2006. Google Scholar