Some new results in multiplicative and additive Ramsey theory
HTML articles powered by AMS MathViewer
- by Mathias Beiglböck, Vitaly Bergelson, Neil Hindman and Dona Strauss PDF
- Trans. Amer. Math. Soc. 360 (2008), 819-847 Request permission
Abstract:
There are several notions of largeness that make sense in any semigroup, and others such as the various kinds of density that make sense in sufficiently well-behaved semigroups including $(\mathbb {N},+)$ and $(\mathbb {N},\cdot )$. It was recently shown that sets in $\mathbb {N}$ which are multiplicatively large must contain arbitrarily large geoarithmetic progressions, that is, sets of the form $\big \{r^j(a\!+\!id)\!:i,j\in \{0,1,\dotsc ,k\}\big \}$, as well as sets of the form $\big \{b(a+id)^j:i,j\in \{0,1,\dotsc ,k\}\big \}$. Consequently, given a finite partition of $\mathbb {N}$, one cell must contain such configurations. In the partition case we show that we can get substantially stronger conclusions. We establish some combined additive and multiplicative Ramsey theoretic consequences of known algebraic results in the semigroups $(\beta \mathbb {N},+)$ and $(\beta \mathbb {N},\cdot )$, derive some new algebraic results, and derive consequences of them involving geoarithmetic progressions. For example, we show that given any finite partition of $\mathbb {N}$ there must be, for each $k$, sets of the form $\big \{b(a+id)^j:i,j\in \{0,1,\dotsc ,k\}\big \}$ together with $d$, the arithmetic progression $\big \{a+id:i\in \{0,1,\dotsc ,k\}\big \}$, and the geometric progression $\big \{bd^j:j\in \{0,1,\dotsc ,k\}\big \}$ in one cell of the partition. More generally, we show that, if $S$ is a commutative semigroup and ${\mathcal F}$ a partition regular family of finite subsets of $S$, then for any finite partition of $S$ and any $k\in \mathbb {N}$, there exist $b,r\in S$ and $F\in {\mathcal F}$ such that $rF\cup \{b(rx)^j:x \in F,j\in \{0,1,2,\ldots ,k\}\}$ is contained in a cell of the partition. Also, we show that for certain partition regular families ${\mathcal F}$ and ${\mathcal G}$ of subsets of $\mathbb {N}$, given any finite partition of $\mathbb {N}$ some cell contains structures of the form $B \cup C \cup B\cdot C$ for some $B\in {\mathcal F}, C\in {\mathcal G}$.References
- Vitaly Bergelson, Multiplicatively large sets and ergodic Ramsey theory, Israel J. Math. 148 (2005), 23–40. Probability in mathematics. MR 2191223, DOI 10.1007/BF02775431
- Vitaly Bergelson, Andreas Blass, and Neil Hindman, Partition theorems for spaces of variable words, Proc. London Math. Soc. (3) 68 (1994), no. 3, 449–476. MR 1262304, DOI 10.1112/plms/s3-68.3.449
- V. Bergelson and A. Leibman, Polynomial extensions of van der Waerden’s and Szemerédi’s theorems, J. Amer. Math. Soc. 9 (1996), no. 3, 725–753. MR 1325795, DOI 10.1090/S0894-0347-96-00194-4
- Timothy J. Carlson, Neil Hindman, and Dona Strauss, Ramsey theoretic consequences of some new results about algebra in the Stone-Čech compactification, Integers 5 (2005), no. 2, A4, 26. MR 2192082
- Walter Deuber, Partitionen und lineare Gleichungssysteme, Math. Z. 133 (1973), 109–123 (German). MR 325406, DOI 10.1007/BF01237897
- Harry Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Analyse Math. 31 (1977), 204–256. MR 498471, DOI 10.1007/BF02813304
- H. Furstenberg, Recurrence in ergodic theory and combinatorial number theory, Princeton University Press, Princeton, N.J., 1981. M. B. Porter Lectures. MR 603625, DOI 10.1515/9781400855162
- H. Furstenberg and Y. Katznelson, A density version of the Hales-Jewett theorem, J. Anal. Math. 57 (1991), 64–119. MR 1191743, DOI 10.1007/BF03041066
- 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
- W. T. Gowers, A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (2001), no. 3, 465–588. MR 1844079, DOI 10.1007/s00039-001-0332-9
- Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1990. A Wiley-Interscience Publication. MR 1044995
- A. W. Hales and R. I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229. MR 143712, DOI 10.1090/S0002-9947-1963-0143712-1
- Neil Hindman, Partitions and sums and products of integers, Trans. Amer. Math. Soc. 247 (1979), 227–245. MR 517693, DOI 10.1090/S0002-9947-1979-0517693-4
- Neil Hindman, Problems and new results on the algebra of $\beta \Bbb N$ and its application to Ramsey theory, Unsolved problems on mathematics for the 21st century, IOS, Amsterdam, 2001, pp. 295–305. MR 1896684
- Neil Hindman, Imre Leader, and Dona Strauss, Image partition regular matrices—bounded solutions and preservation of largeness, Discrete Math. 242 (2002), no. 1-3, 115–144. MR 1874760, DOI 10.1016/S0012-365X(01)00276-X
- Neil Hindman and Dona Strauss, Algebra in the Stone-Čech compactification, De Gruyter Expositions in Mathematics, vol. 27, Walter de Gruyter & Co., Berlin, 1998. Theory and applications. MR 1642231, DOI 10.1515/9783110809220
- B. de Mathan, Numbers contravening a condition in density modulo $1$, Acta Math. Acad. Sci. Hungar. 36 (1980), no. 3-4, 237–241 (1981). MR 612195, DOI 10.1007/BF01898138
- A. D. Pollington, On the density of sequence $\{n_{k}\xi \}$, Illinois J. Math. 23 (1979), no. 4, 511–515. MR 540398
- R. Rado, Verallgemeinerung Eines Satzes von van der Waerden mit Anwendungen auf ein Problem der Zahlentheorie, Sonderausg. Sitzungsber. Preuss. Akad. Wiss. Phys.-Math. Klasse 17 (1933), 1-10.
- R. Rado, Studien zur Kombinatorik, Math. Zeit. 36 (1933), 242-280.
- 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. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wiskunde 19 (1927), 212-216.
Additional Information
- Mathias Beiglböck
- Affiliation: Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Wiedner Hauptstr. 8-10, 1040 Wien, Austria
- Email: mathias.beiglboeck@tuwien.ac.at
- Vitaly Bergelson
- Affiliation: Department of Mathematics, Ohio State University, Columbus, Ohio 43210
- MR Author ID: 35155
- Email: vitaly@math.ohio-state.edu
- Neil Hindman
- Affiliation: Department of Mathematics, Howard University, Washington, DC 20059
- MR Author ID: 86085
- Email: nhindman@aol.com
- Dona Strauss
- Affiliation: Mathematics Centre, University of Hull, Hull HU6 7RX, United Kingdom
- Email: d.strauss@hull.ac.uk
- Received by editor(s): October 21, 2005
- Published electronically: May 16, 2007
- Additional Notes: The first author thanks the Austrian Science Foundation FWF for its support through Projects nos. S8312 and P17627-N12. He also thanks Ohio State University for its hospitality in the spring of 2004 while much of this research was being conducted.
The second author acknowledges support received from the National Science Foundation via grant DMS-0345350.
The third author acknowledges support received from the National Science Foundation via grants DMS-0243586 and DMS-0554803. - © Copyright 2007 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 360 (2008), 819-847
- MSC (2000): Primary 05D10; Secondary 22A15
- DOI: https://doi.org/10.1090/S0002-9947-07-04370-X
- MathSciNet review: 2346473