A100719 Size of the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square.

1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 18, 18, 18, 19, 19, 20

Offset: 1

Author

N. J. A. Sloane, Sep 17 2007

Keywords

• nonn

Comments

Prompted by a question about the rate of growth of this sequence asked by Sujith Vijay (sujith(AT)EDEN.RUTGERS.EDU) to the Number Theory List.

The problem can be thought of as finding a maximum independent set in a graph with node set {1, 2, ..., n} and an edge (i, j) if |i - j| is a square. - Rob Pratt

The index of the first occurrence of m is A210570(m). - Glen Whitney, Aug 30 2015

References

• H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions, J. Analyse Math. 31 (1977), 204-256.
• A. Sárközy, On difference sets of sequences of integers II, Annales Univ. Sci. Budapest, Sectio Math.

Links

• Fausto A. C. Cariboni, Table of n, a(n) for n = 1..410 (terms n = 1..100 from Rob Pratt)
• A. Balog, J. Pelikan, J. Pintz and E. Szemeredi, Difference sets without kappa-th powers, Acta Math. Hungar. 65 (1994), no. 2, 165-187.
• Thomas F. Bloom and James Maynard, A new upper bound for sets with no square differences, arXiv:2011.13266 [math.NT], 2020-2021; Compositio Mathematica 158.8 (2022): 1777-1798.
• Fausto A. C. Cariboni, Sets of maximal span that yield a(n) for n = 3..314, Nov 28 2018.
• Ben Green and Mehtaab Sawhney, Improved bounds for the Furstenberg-Sárközy theorem, arXiv preprint arXiv:2411.17448 [math.NT], 2024.
• J. Pintz, W. L. Steiger and E. Szemeredi, On Sets of Natural Numbers Whose Difference Set Contains No Squares, J. London. Math. Soc. 37, 1988, 219-231.
• I. Ruzsa, Difference sets without squares, Period. Math. Hungar. 15 (1984), no. 3, 205-209.
• A. Sárközy, On difference sets of sequences of integers I, Acta Mathematica Academiae Scientiarum Hungarica, March 1978, Volume 31, Issue 1, pp 125-149.
• A. Sárközy, On difference sets of sequences of integers III, Acta Mathematica Academiae Scientiarum Hungarica, September 1978, Volume 31, Issue 3, pp 355-386.

Crossrefs

Cf. A210570.

Cf. A131752, A131753, A131754.

Formula

a(n) >> n^0.733 (I. Ruzsa, Period. Math. Hungar. 15 (1984), no. 3, 205-209). The best upper bound appears to be O(N (log n)^(- c log log log log N)) due to Pintz, Steiger and Szemeredi (J. London. Math. Soc. 37, 1988, 219-231). - Sujith Vijay, Sep 18 2007

A. Sárközy worked on this problem. There is also the following result of A. Balog, J. Pelikan, J. Pintz, E. Szemeredi: the size of largest squarefree difference sets = O(N / (log N)^(log log log log N / 4)). - Tsz Ho Chan (tchan(AT)MEMPHIS.EDU), Sep 19 2007

Green & Sawhney improve the upper bound to a(n) << n exp(-(log n)^c) for any c < 1/4. - Charles R Greathouse IV, Nov 28 2024

Extensions

Computed via integer programming by Rob Pratt, Sep 17 2007