A210570 Consider all sequences of n distinct positive integers for which no two different elements have a difference which is a square. This sequence gives the smallest maximal integer in such sequences.
1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35, 38, 43, 48, 53, 58, 66, 68, 71, 73, 81, 86, 92, 97, 102, 107, 112, 118, 120, 125, 131, 133, 138, 144, 146, 151, 157, 159, 164, 189, 199, 203, 206, 208, 219, 223, 236, 242, 248, 253, 258, 263, 266, 269, 283, 285, 288, 293, 311, 314, 323, 328, 331, 334, 343, 346
Offset: 1
Examples
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}
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.
Programs
-
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)
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
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
Comments