The structure of popular difference sets. (English) Zbl 1246.05026
Summary: We show that the set of popular differences of a large subset of \(\mathbb Z_N\) does not always contain the complete difference set of another large set. For this purpose we construct a so-called niveau set, which was first introduced by I. Z. Ruzsa in [Proc. Lond. Math. Soc., III. Ser. 54, 38–56 (1987; Zbl 0609.10042)] and later used in [I. Z. Ruzsa, Acta Arith. 60, No. 2, 191–202 (1991; Zbl 0728.11009)] to show that there exists a large subset of \(\mathbb Z_N\) whose sumset does not contain any long arithmetic progressions. In this paper we make substantial use of measure concentration results on the multidimensional torus and Esseen’s inequality.
MathOverflow Questions:
Situations where “naturally occurring” mathematical objects behave very differently from “typical” onesMSC:
| 05B10 | Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.) |
| 11B25 | Arithmetic progressions |
References:
| [1] | W. Albers and W. C. M. Kallenberg, A simple approximation to the bivariate normal distribution with large correlation coefficient, Journal of Multivariate Analysis 49 (1994), 87–96. · Zbl 0796.62013 · doi:10.1006/jmva.1994.1015 |
| [2] | N. Alon and J. Spencer, The Probabilistic Method, Wiley-Interscience [John Wiley & Sons], New York, 2000. · Zbl 0996.05001 |
| [3] | A. C. Berry, The accuracy of the Gaussian approximation to the sum of independent variates, Transactions of the American Mathematical Society 49 (1941), 122–136. · JFM 67.0461.01 · doi:10.1090/S0002-9947-1941-0003498-3 |
| [4] | H. Bergstrom, On the central limit theorem in the case \(\mathbb{R}\)k, k > 1, Skand. Aktuarietidskr. 2 (1945), 106–127. |
| [5] | M. Drmota and R. F. Tichy, Sequences, Discrepancies and Applications, Springer-Verlag, Berlin, 1997. · Zbl 0877.11043 |
| [6] | C-G. Esseen, Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law, Acta Mathematica 77 (1945), 1–125. · Zbl 0060.28705 · doi:10.1007/BF02392223 |
| [7] | B. J. Green, Some constructions in the inverse spectral theory of cyclic groups, Combinatorics, Probability and Computing 12 (2003), 127–138. · Zbl 1097.11051 · doi:10.1017/S0963548302005436 |
| [8] | B. J. Green, Finite field models in additive combinatorics, in Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge University Press, Cambridge, 2005, pp. 1–27. · Zbl 1155.11306 |
| [9] | B. J. Green and I. Ruzsa, Sum-free sets in abelian groups, Israel Journal of Mathematics 147 (2005), 157–189. · Zbl 1158.11311 · doi:10.1007/BF02785363 |
| [10] | L. H. Harper, Optimal numberings and isoperimetric problems on graphs, Journal of Combinatorial Theory 1 (1966), 385–393. · Zbl 0158.20802 · doi:10.1016/S0021-9800(66)80059-5 |
| [11] | S. Janson, T. Łuczak and A. Rucinski, Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience [John Wiley & Sons], New York, 2000. |
| [12] | D. Kleitman, On a combinatorial conjecture by Erdös, Journal of Combinatorial Theory 1 (1966), 209–214. · Zbl 0148.01105 · doi:10.1016/S0021-9800(66)80027-3 |
| [13] | M. Ledoux, The concentration of measure phenomenon, AMS Mathematical Surveys and Monographs, vol. 89, American Mathematical Society, Providence, RI, 2001. · Zbl 0995.60002 |
| [14] | V. Lev, T. Łuczak and T. Schoen, Sum-free sets in abelian groups, Israel Journal of Mathematics 125 (2001), 347–367. · Zbl 1055.20043 · doi:10.1007/BF02773386 |
| [15] | C. McDiarmid, On the method of bounded differences, in Surveys in combinatorics, 1989 (Norwich, 1989), London Math. Soc. Lecture Note Ser., vol. 141, Cambridge University Press, Cambridge, 1989, pp. 148–188. · Zbl 0712.05012 |
| [16] | H. Niederreiter and W. Philipp, Berry-Esseen bounds and a theorem of Erdös and Turán on uniform distribution mod 1, Duke Mathematical Journal 40 (1973), 633–649. · Zbl 0273.10043 · doi:10.1215/S0012-7094-73-04055-6 |
| [17] | I. Z. Ruzsa, Essential components, Proceedings of the London Mathematical Society. Third Series 54 (1987), 38–56. · Zbl 0609.10042 · doi:10.1112/plms/s3-54.1.38 |
| [18] | I. Z. Ruzsa, Arithmetic progressions in sumsets, Acta Arithmetica 2 (1991), 191–202. · Zbl 0728.11009 |
| [19] | S. M. Sadikova, Two-dimensional analogues of an inequality of Esseen with applications to the Central Limit Theorem, Theory of Probability and Its Applications 11 (1966), 325–335. · Zbl 0202.48503 · doi:10.1137/1111035 |
| [20] | T. Sanders, Popular difference sets, Available at http://arxiv.org/abs/0807.5106 , 2008. · Zbl 1244.05037 |
| [21] | A. N. Shiryayev, Probability, Graduate Texts in Mathematics, vol. 95, Springer-Verlag, New York, 1984. |
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.
