×

An improved lower bound related to the Furstenberg-Sárközy theorem. (English) Zbl 1307.05219

Summary: Let \(D(n)\) denote the cardinality of the largest subset of the set \(\{1,2,\dots,n\}\) such that the difference of no pair of distinct elements is a square. A well-known theorem of Furstenberg and Sárközy states that \(D(n)=o(n)\). In the other direction, I. Z. Ruzsa [Period. Math. Hung. 15, 205–209 (1984; Zbl 0552.10035)] has proven that \(D(n) \gtrsim n^{\gamma}\) for \(\gamma = \frac{1}{2}\left( 1 + \frac{\log 7}{\log 65} \right) \approx 0.733077\). We improve this to \(\gamma = \frac{1}{2}\left( 1 + \frac{\log 12}{\log 205} \right) ~\approx 0.733412\).

MSC:

05D10 Ramsey theory
05B10 Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.)

Citations:

Zbl 0552.10035

Software:

MaxCliqueDyn
PDFBibTeX XMLCite
Full Text: Link

References:

[1] F. A. Behrend, On sets of integers which contain no three terms in arithmetical progression. Proc. Nat. Acad. Sci. U. S. A., 32:331-332, 1946. · Zbl 0060.10302
[2] T. Bloom, A quantitative improvement for Roth’s theorem on arithmetic progressions, Preprint, 2014.arXiv:1405.5800 · Zbl 1364.11024
[3] M. Elkin, An improved construction of progression-free sets. Israel J. Math. 184 (2011), 93-128. · Zbl 1280.11008
[4] J. Fabrykowski, On maximal residue difference sets modulo p. Canad. Math. Bull. 36 (1993), no. 2, 144-146. · Zbl 0797.11003
[5] J. Fabrykowski, On quadratic residues and nonresidues in difference sets modulo m. Proc. Amer. Math. Soc. 122 (1994), no. 2, 325-331. · Zbl 0827.11013
[6] H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemer´edi on arithmetic progressions, J. d’Analyse Math. 31 (1977), 204-256. · Zbl 0347.28016
[7] B. Green and J. Wolf, A note on Elkin’s improvement of Behrend’s construction. Additive number theory, 141-144, Springer, New York, 2010. · Zbl 1261.11013
[8] N. Lyall, A new proof of S´ark¨ozy’s theorem. Proc. Amer. Math. Soc. 141 (2013), no. 7, 2253-2264. · Zbl 1276.11017
[9] J. Konc and D. Janezic, An improved branch and bound algorithm for the maximum clique problem. MATCH Commun. Math. Comput. Chem., 2007, 58, 569-590. the electronic journal of combinatorics 22(1) (2015), #P1.325 · Zbl 1274.05452
[10] J. Konc, Maximum Clique Algorithm.http://www.sicmm.org/ konc/maxclique/ · Zbl 1274.05452
[11] J. Pintz, W. L. Steiger, E. Szemer´edi, On sets of natural numbers whose difference set contains no squares, J. London Math. Soc. 37 (1988), 219-231. · Zbl 0651.10031
[12] I. Ruzsa, Difference sets without squares. Period. Math. Hungar. 15 (1984), no. 3, 205-209. · Zbl 0552.10035
[13] T. Sanders, On Roth’s theorem on progressions. Ann. of Math. (2) 174 (2011), no. 1, 619-636. · Zbl 1264.11004
[14] A. S´ark¨ozy, On difference sets of integers I, Ada Math. Acad. Sci. Hungar. 31 (1978) 125-149. · Zbl 0387.10033
[15] A. S´ark¨ozy, On difference sets of integers II, Ann. Univ. Sci. Budapest. E¨otv¨os Sect. Math. 21 (1978), 45-53. · Zbl 0413.10051
[16] A. S´ark¨ozy, On difference sets of sequences of integers. III. Acta Math. Acad. Sci. Hungar. 31 (1978), no. 3-4, 355-386. · Zbl 0387.10034
[17] T. Tao, A Fourier-free proof of the Furstenberg-Sarkozy theorem. http://terrytao.wordpress.com/2013/02/28/a-fourier-free-proof-ofthe-furstenberg-sarkozy-theorem the electronic journal of combinatorics 22(1) (2015), #P1.326
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.