Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

On $ k$-free sequences of integers


Author: Samuel S. Wagstaff
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] F. Behrend, ``On sequences of integers containing no arithmetic progression,'' Časopis Mat. Fis. Praha, v. 67, 1938, pp. 235-239.
  • [2] P. Erdös & P. Turán, ``On some sequences of integers,'' J. London Math. Soc. (2), v. 11, 1936, pp. 261-264.
  • [3] A. Makowski, ``Remark on a paper of Erdös and Turán,'' J. London Math. Soc., v. 34, 1959, p. 480. MR 21 #5596. MR 0106866 (21:5596)
  • [4] L. Moser, ``On non-averaging sets of integers,'' Canad. J. Math., v. 5, 1953, pp. 245-252. MR 14, 726; 1278. MR 0053140 (14:726d)
  • [5] K. F. Roth, ``On certain sets of integers,'' J. London Math. Soc., v. 28, 1953, pp. 104-109. MR 14, 536; 1278. MR 0051853 (14:536g)
  • [6] K. F. Roth, ``Sur quelques ensembles d'entiers,'' C. R. Acad. Sci. Paris, v. 234, 1952, pp. 388-390. MR 13, 724. MR 0046374 (13:724d)
  • [7] R. Salem & D. C. Spencer, ``On sets of integers which contain no three terms in arithmetic progression,'' Proc. Nat. Acad. Sci. U.S.A., v. 28, 1942, pp. 561-563. MR 4, 131. MR 0007405 (4:131e)
  • [8] R. Salem & D. C. Spencer, ``On sets which do not contain a given number of terms in arithmetic progression,'' Nieuw Arch. Wisk. (2), v. 23, 1950, pp. 133-143. MR 11, 417. MR 0033294 (11:417e)
  • [9] E. Szemerédi, ``On sets of integers containing no four elements in arithmetic progression,'' Acta Math. Acad. Sci. Hungar., v. 20, 1969, pp. 89-104. MR 39 #6861. MR 0245555 (39:6861)
  • [10] S. S. Wagstaff, ``On sequences of integers with no 4, or no 5 numbers in arithmetical progression,'' Math. Comp., v. 21, 1967, pp. 695-699. MR 36 #5061. MR 0222009 (36:5061)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10-04, 10L99

Retrieve articles in all journals with MSC: 10-04, 10L99


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1972-0325500-5
Keywords: $ k$-free sequences, arithmetic progressions in sequences
Article copyright: © Copyright 1972 American Mathematical Society

American Mathematical Society