Greedily partitioning the natural numbers into sets free of arithmetic progressions
HTML articles powered by AMS MathViewer
- by Joseph Gerver, James Propp and Jamie Simpson PDF
- Proc. Amer. Math. Soc. 102 (1988), 765-772 Request permission
Abstract:
We describe a "greedy" algorithm for partitioning the natural numbers into sets free of arithmetic progressions of length 3. A recursive formula governing the resulting partition is proved, and some features of its asymptotic behavior are discussed.References
-
P. Erdös and P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261-264.
- H. Furstenberg, Y. Katznelson, and D. Ornstein, The ergodic theoretical proof of Szemerédi’s theorem, Bull. Amer. Math. Soc. (N.S.) 7 (1982), no. 3, 527–552. MR 670131, DOI 10.1090/S0273-0979-1982-15052-2
- Joseph L. Gerver, Irregular sets of integers generated by the greedy algorithm, Math. Comp. 40 (1983), no. 162, 667–676. MR 689480, DOI 10.1090/S0025-5718-1983-0689480-2
- Joseph L. Gerver and L. Thomas Ramsey, Sets of integers with no long arithmetic progressions generated by the greedy algorithm, Math. Comp. 33 (1979), no. 148, 1353–1359. MR 537982, DOI 10.1090/S0025-5718-1979-0537982-0 Richard K. Guy, Unsolved problems in number theory, Springer-Verlag, 1980.
- D. J. Newman, Sequences without arithmetic progressions, Analytic number theory (Philadelphia, Pa., 1980) Lecture Notes in Math., vol. 899, Springer, Berlin-New York, 1981, pp. 311–314. MR 654536 A.M. Odlyzko and R. P. Stanley, Some curious sequences constructed with the greedy algorithm, unpublished Bell Laboratories report, January 1978.
- R. A. Rankin, Sets of integers containing not more than a given number of terms in arithmetical progression, Proc. Roy. Soc. Edinburgh Sect. A 65 (1960/61), 332–344 (1960/61). MR 142526
- 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
- E. Szemerédi, On sets of integers containing no $k$ elements in arithmetic progression, Acta Arith. 27 (1975), 199–245. MR 369312, DOI 10.4064/aa-27-1-199-245 B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw. Arch. Wisk. 15 (1927), 212-216.
Additional Information
- © Copyright 1988 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 102 (1988), 765-772
- MSC: Primary 11B25; Secondary 05A99
- DOI: https://doi.org/10.1090/S0002-9939-1988-0929018-1
- MathSciNet review: 929018