OFFSET
1,2
COMMENTS
László Lovász conjectured, and Hillel Furstenberg and András Sárközy (1978) independently showed that a(n) is superlinear. Erdős conjectured that a(n) >> n^2/log^k n for some k. Sárközy proved that a(n) = o(n^2/log^k n) for all k, but still conjectured that a(n) >> n^(2-e) for all e > 0. Ruzsa showed that in fact a(n) << n^1.365.
a(n) is the least m such that A100719(m) = n. - Glen Whitney, Aug 30 2015
REFERENCES
András Sárközy, On difference sets of sequences of integers, II., Annales Universitatis Scientarium Budapestinensis de Rolando Eötvös Nominatae Sectio Mathematica 21 (1978), pp. 45-53.
LINKS
Fausto A. C. Cariboni, Table of n, a(n) for n = 1..74
Fausto A. C. Cariboni, Sets that yield a(n) for n = 2..74, Feb 03 2019
Hillel Furstenberg, Ergodic behaviour of diagonal measures and a theorem of Szemeredi on arithmetic progressions, J. Analyse Math. 31 (1977), pp. 204-256.
Ben Green and Mehtaab Sawhney, Improved bounds for the Furstenberg-Sárközy theorem, arXiv preprint arXiv:2411.17448 [math.NT], 2024.
Janos Pintz, W. L. Steiger and Endre Szemerédi, On sets of natural numbers whose difference set contains no squares, J. London Math. Soc. 37:2 (1988), pp. 219-231.
I. Z. Ruzsa, Difference sets without squares, Periodica Mathematica Hungarica 15:3 (1984), pp. 205-209.
András Sárközy, On difference sets of sequences of integers, I., Acta Mathematica Academiae Scientiarum Hungaricae 31:1-2 (1978), pp. 125-149.
FORMULA
n * (log n)^((1/12) * log log log log n) << a(n) << n^k with k = 2/(1+log(7)/log(65)) = 1.364112553....
Green & Sawhney improve the lower bound to n * exp((log n)^c) for any c < 1/4. - Charles R Greathouse IV, Nov 27 2024
EXAMPLE
There are no nontrivial differences in {1}, so a(1) = 1. {1, 2} contains the square 2-1 as a difference, but {1, 3} is valid so a(2) = 3.
a(3) = 6: {1, 3, 6}
a(4) = 8: {1, 3, 6, 8}
a(5) = 11: {1, 3, 6, 8, 11}
a(6) = 13: {1, 3, 6, 8, 11, 13}
a(7) = 16: {1, 3, 6, 8, 11, 13, 16}
a(8) = 18: {1, 3, 6, 8, 11, 13, 16, 18}
a(9) = 21: {1, 3, 6, 8, 11, 13, 16, 18, 21}
a(10) = 23: {1, 3, 6, 8, 11, 13, 16, 18, 21, 23}
a(11) = 35: {1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35}
a(12) = 38: {1, 4, 6, 9, 11, 14, 16, 21, 28, 33, 35, 38}
a(13) = 43: {1, 3, 6, 9, 11, 14, 16, 21, 33, 35, 38, 40, 43}
PROG
(PARI) ev(v)=my(h=sum(i=1, #v, v[i]), m, u); if(h<2, return(h)); m=#v; while(v[m]==0, m--); u=vector(m-1, i, v[i]); h=ev(u); for(k=1, sqrtint(m-1), u[m-k^2]=0); max(h, 1+ev(u))
a(n)=my(k=(5*n-3)\2, t); while(1, t=ev(vector(k, i, 1)); if(t==n, return(k)); k+=n-t)
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
Charles R Greathouse IV, Apr 02 2012
EXTENSIONS
a(17)-a(31) from Giovanni Resta, Dec 21 2012
a(32)-a(58) from Jon E. Schoenfield, Dec 28 2013
a(59)-a(66) from Fausto A. C. Cariboni, Nov 28 2018
STATUS
approved