Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-25T18:52:23.580Z Has data issue: false hasContentIssue false

On the Set of Common Differences in van der Waerden’s Theorem on Arithmetic Progressions

Published online by Cambridge University Press:  20 November 2018

Tom C. Brown
Affiliation:
Department of Mathematics and Statistics Simon Fraser University Burnaby, BC V5A 1S6
Ronald L. Graham
Affiliation:
AT&T Labs 180 Park Avenue Florham Park, NJ 07932 USA
Bruce M. Landman
Affiliation:
Department of Mathematical Sciences University of North Carolina at Greensboro Greensboro, NC 27412 USA
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Analogues of van der Waerden’s theorem on arithmetic progressions are considered where the family of all arithmetic progressions, $\text{AP}$, is replaced by some subfamily of $\text{AP}$. Specifically, we want to know for which sets $A$, of positive integers, the following statement holds: for all positive integers $r$ and $k$, there exists a positive integer $n={w}'\text{(}k,r)$ such that for every $r$-coloring of $[1,\,n]$ there exists a monochromatic $k$-term arithmetic progression whose common difference belongs to $A$. We will call any subset of the positive integers that has the above property large. A set having this property for a specific fixed $r$ will be called $r$-large. We give some necessary conditions for a set to be large, including the fact that every large set must contain an infinite number of multiples of each positive integer. Also, no large set $\{{{a}_{n}}\,:\,n\,=\,1,\,2,\ldots \}$ can have $\underset{n\to \infty }{\mathop{\lim \,\inf }}\,\,\frac{{{a}_{n+1}}}{{{a}_{n}}}\,>\,1$. Sufficient conditions for a set to be large are also given. We show that any set containing $n$-cubes for arbitrarily large $n$, is a large set. Results involving the connection between the notions of “large” and “2-large” are given. Several open questions and a conjecture are presented.

Keywords

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1999

References

[1] Bergelson, V., Ergodic Ramsey theory—an update. In: Ergodic theory of Zd-actions (Eds. Pollicott and Schmidt), LondonMath. Soc. Lecture Note Ser. 228 (1996), 161.Google Scholar
[2] Bergelson, V. and Leibman, A., Polynomial extensions of van der Waerden's and Szemerédi's theorems. J. Amer. Math. Soc. 9 (1996), 725753.Google Scholar
[3] Brown, T. C., On van der Waerden's theorem and a theorem of Paris and Harrington. J. Combin. Theory Ser. A 30 (1981), 108111.Google Scholar
[4] Brown, T. C., Erdős, P. and Freedman, A. R., Quasi-progressions and descending waves. J. Combin. Theory Ser. A 53 (1990), 8195.Google Scholar
[5] Furstenberg, H., Recurrence in Ergodic Theory and Combinatorial Number Theory. Princeton University Press, Princeton, 1981.Google Scholar
[6] Furstenberg, H., Poincaré Recurrence and Number Theory. Bull. American Math. Soc. 5 (1981), 211234.Google Scholar
[7] Furstenberg, H., A Polynomial Szemerédi Theorem. In: Combinatorics, Paul Erdős is Eighty, Janos Bolyai Mathematical Society, Budapest, 1996.Google Scholar
[8] Greenwell, R. N. and Landman, B. M., On the existence of a reasonable upper bound for the van der Waerden numbers. J. Combin. Theory Ser. A 50 (1989), 8286.Google Scholar
[9] Hales, A. W. and Jewett, R. I., Regularity and positional games. Trans. Amer. Math. Soc. 106 (1963), 222229.Google Scholar
[10] Landman, B. M., Ramsey functions for quasi-progressions. Graphs and Combinatorics, to appear.Google Scholar
[11] Landman, B. M., Avoiding arithmetic progressions (mod m) and arithmetic progressions. Utilitas Math., to appear.Google Scholar
[12] Landman, B. M. and B. Wysocka, Collections of sequences having the Ramsey property only for few colors. Bull. Australian Math. Soc. 55 (1997), 1928.Google Scholar
[13] van der Waerden, B. L., Beweis einer Baudetschen Vermutung. Nieuw Arch.Wisk. 15 (1927), 212216.Google Scholar