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.
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^1.365.
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.
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)
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