cp's OEIS Frontend

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

%I A100719 #57 Aug 04 2025 03:38:52
%S A100719 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,
%T A100719 10,10,10,10,11,11,11,12,12,12,12,12,13,13,13,13,13,14,14,14,14,14,15,
%U A100719 15,15,15,15,16,16,16,16,16,16,16,16,17,17,18,18,18,19,19,20
%N A100719 Size of the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square.
%C A100719 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.
%C A100719 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_
%C A100719 The index of the first occurrence of m is A210570(m). - _Glen Whitney_, Aug 30 2015
%D A100719 H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions, J. Analyse Math. 31 (1977), 204-256.
%D A100719 A. Sárközy, On difference sets of sequences of integers II, Annales Univ. Sci. Budapest, Sectio Math.
%H A100719 Fausto A. C. Cariboni, <a href="/A100719/b100719.txt">Table of n, a(n) for n = 1..410</a> (terms n = 1..100 from Rob Pratt)
%H A100719 A. Balog, J. Pelikan, J. Pintz and E. Szemeredi, <a href="http://dx.doi.org/10.1007/BF01874311">Difference sets without kappa-th powers</a>, Acta Math. Hungar. 65 (1994), no. 2, 165-187.
%H A100719 Thomas F. Bloom and James Maynard, <a href="https://arxiv.org/abs/2011.13266">A new upper bound for sets with no square differences</a>, arXiv:2011.13266 [math.NT], 2020-2021; Compositio Mathematica 158.8 (2022): 1777-1798.
%H A100719 Fausto A. C. Cariboni, <a href="/A100719/a100719.txt">Sets of maximal span that yield a(n) for n = 3..314</a>, Nov 28 2018.
%H A100719 Ben Green and Mehtaab Sawhney, <a href="https://arxiv.org/abs/2411.17448">Improved bounds for the Furstenberg-Sárközy theorem</a>, arXiv preprint arXiv:2411.17448 [math.NT], 2024.
%H A100719 J. Pintz, W. L. Steiger and E. Szemeredi, <a href="http://dx.doi.org/10.1112/jlms/s2-37.2.219">On Sets of Natural Numbers Whose Difference Set Contains No Squares</a>, J. London. Math. Soc. 37, 1988, 219-231.
%H A100719 I. Ruzsa, <a href="http://dx.doi.org/10.1007/BF02454169">Difference sets without squares</a>, Period. Math. Hungar. 15 (1984), no. 3, 205-209.
%H A100719 A. Sárközy, <a href="http://dx.doi.org/10.1007/BF01896079">On difference sets of sequences of integers I</a>, Acta Mathematica Academiae Scientiarum Hungarica, March 1978, Volume 31, Issue 1, pp 125-149.
%H A100719 A. Sárközy, <a href="http://dx.doi.org/10.1007/BF01901984">On difference sets of sequences of integers III</a>, Acta Mathematica Academiae Scientiarum Hungarica, September 1978, Volume 31, Issue 3, pp 355-386.
%F A100719 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
%F A100719 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
%F A100719 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
%Y A100719 Cf. A210570.
%Y A100719 Cf. A131752, A131753, A131754.
%K A100719 nonn
%O A100719 1,3
%A A100719 _N. J. A. Sloane_, Sep 17 2007
%E A100719 Computed via integer programming by _Rob Pratt_, Sep 17 2007