On $k$-free sequences of integers
HTML articles powered by AMS MathViewer
- by Samuel S. Wagstaff PDF
- Math. Comp. 26 (1972), 767-771 Request permission
Abstract:
Let ${A^{(k)}}(n)$ denote the cardinality of the largest subsequence of $0,1,2, \cdots ,n - 1$, which contains no $k$ numbers in arithmetical progression. (Such a sequence is called $k$-free.) ${A^{(k)}}(n)$ is computed (on an IBM 360/65) for $3 \leqq k \leqq 8$, and various values of $n$ to about 50. The results support the old conjecture that for all $k$, the limit ${\tau ^{(k)}} = {\lim _{n \to \infty }}({A^{(k)}}(n))/n = 0$. The results ${\tau ^{(5)}} < .649,{\tau ^{(6)}} < .721,{\tau ^{(7)}} < .776$, and ${\tau ^{(8)}} < .8071$ are obtained. Several cases of a (disproved) conjecture of G. Szekeres are verified, including ${A^{(5)}}(94) = 64$.References
-
F. Behrend, âOn sequences of integers containing no arithmetic progression,â Äasopis Mat. Fis. Praha, v. 67, 1938, pp. 235-239.
P. Erdös & P. TurĂĄn, âOn some sequences of integers,â J. London Math. Soc. (2), v. 11, 1936, pp. 261-264.
- A. MÄ kowski, Remark on a paper of ErdĆs and TurĂĄn, J. London Math. Soc. 34 (1959), 480. MR 106866, DOI 10.1112/jlms/s1-34.4.480
- Leo Moser, On non-averaging sets of integers, Canad. J. Math. 5 (1953), 245â252. MR 53140, DOI 10.4153/cjm-1953-027-0
- K. F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104â109. MR 51853, DOI 10.1112/jlms/s1-28.1.104
- Klaus Roth, Sur quelques ensembles dâentiers, C. R. Acad. Sci. Paris 234 (1952), 388â390 (French). MR 46374
- R. Salem and D. C. Spencer, On sets of integers which contain no three terms in arithmetical progression, Proc. Nat. Acad. Sci. U.S.A. 28 (1942), 561â563. MR 7405, DOI 10.1073/pnas.28.12.561
- R. Salem and D. C. Spencer, On sets which do not contain a given number of terms in arithmetical progression, Nieuw Arch. Wiskunde (2) 23 (1950), 133â143. MR 0033294
- E. SzemerĂ©di, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hungar. 20 (1969), 89â104. MR 245555, DOI 10.1007/BF01894569
- S. S. Wagstaff Jr., On sequences of integers with no $4$, or no $5$ numbers in arithmetical progression, Math. Comp. 21 (1967), 695â699. MR 222009, DOI 10.1090/S0025-5718-1967-0222009-2
Additional Information
- © Copyright 1972 American Mathematical Society
- Journal: Math. Comp. 26 (1972), 767-771
- MSC: Primary 10-04; Secondary 10L99
- DOI: https://doi.org/10.1090/S0025-5718-1972-0325500-5
- MathSciNet review: 0325500