10
$\begingroup$

Consider positive integers $c$, $k$, and $s$. Does there exist some $N = N(c,k,s)$ such that the following holds?

Take any $c$-coloring of the $k$-tuples of integers in $[1,N]$. Then there is an arithmetic progression of length $s$ such that all $k$-tuples of it have the same color. More precisely, there exists a set $S \subseteq [1,N]$ such that $|S| = s$, $S$ is an arithmetic progression, and all tuples in $S^k$ have the same color.


If $k=1$, then this is van der Waerden's theorem. If I don't care for an arithmetic progression (and am happy with just a set), then this is Ramsey's theorem. This is asking for the best of both theorems.

I was unable to find such a statement in my searches. I thought this might be a consequence of the Hales-Jewett Theorem, but could not show this. It seems like a first principles approach combining proofs of van der Waerden and Ramsey's theorem might work. But I was wondering if this is already known.

Thanks!


Update

User Wei Wang has refuted this statement below with a simple counterexample. Exampled added here for clarity. Suppose $N(2,3,4)$ existed. Simply color all three tuples in $[1,N]$ that form an AP blue, and remaining tuples red. Consider any AP $S = (s_1, s_2, s_3, s_4)$. The tuple $\{s_1, s_2, s_3\}$ is blue and $\{s_1, s_3, s_4\}$ is red.

User quid in his answer below has given a reference showing that a variant of my question is true. If I understand correctly, it is the case that there are k APs $S_1, S_2, \ldots, S_k$ such that tuples in $S_1 \times S_2 \times \cdots \times S_k$ have the same color. One can also ensure that these APs have the same minimum difference. (One can get a lot more, as explained in quid's post.) All in all, I think his post gives "more than an answer" to my question.

$\endgroup$
6
  • 2
    $\begingroup$ It is already known to be false. Each 2-tuple is in an essentially unique s-AP. $\endgroup$
    – Boris Bukh
    Mar 22, 2013 at 0:49
  • 6
    $\begingroup$ I guess that Boris means the following counterexample: color a triple (a,b,c) BLUE if it is an AP, or RED otherwise. Then no length 4 AP could be homogeneous. $\endgroup$
    – Wei Wang
    Mar 22, 2013 at 1:28
  • $\begingroup$ But in my opinion the question asks for a s-AP of k-tuples. So one would have to exclude, say, a 4-AP of 3-tuples $\endgroup$
    – user9072
    Mar 22, 2013 at 1:39
  • $\begingroup$ Boris, Wei, I think you misunderstood my question. I have rephrased to make it clear. $\endgroup$
    – Sesh
    Mar 22, 2013 at 2:39
  • 1
    $\begingroup$ Sesh, could you explain why Wei's remark doesn't refute the existence of $N=N(2,3,4)$ for your statement? After all, if $N$ is supposed to work for all 2-colorings of 3-tuples, then Wei's coloring would have to have a homogeneous arithmetic progression $S$ of size $4$, but the first three elements of $S$ are colored blue, and the first with the last two are colored red, violating homogeneity. Have I misunderstood? $\endgroup$ Mar 22, 2013 at 2:54

2 Answers 2

7
$\begingroup$

The way I understand the question is that $k$-tuples of integers are considered so that each coordinate lies in $[1,N]$, so in other words one considers $[1,N]^k$ and colors all the elements of this set, so each poin $(a1,...,ak)$ gets some color.

There is a version of Szemerédi's Theorem for $\mathbb{Z}^k$, due to Furstenberg and Katznelson, that asserts that for every subset $A$ of $\mathbb{Z}^k$ of positive upper Banach density and any finite $F\subset \mathbb{Z}^k$ there is some $u \in \mathbb{Z}^k$ and some $n \in \mathbb{N}$ such that $u+nF \subset A$.

For this result see for example Corollary at the start of the paper by Bergelson and Leibman, establishing a polynomial version of Szemerédi's theorem (I failed to properly locate the original paper, thus this reference by proxy).

This result necessarily also has a 'finitary' analogue (to match the question), however the proof being "ergodic" to get explict constants could be a problem. Also, as usual, on would consider for a given coloring the largest set of the same color, which necessarily has positive upper denisty.

Now, this result implies directly the existence of s-term arithmetic progression in such a set $A$ in the sense I understand this word, namely as a set of the form $a, a+d, ..., a+(s-1)d$ with $a,d$ in the relevant structure so in this case $\mathbb{Z}^k$, by taking $F$ some set of points in arithmetic progression.

However, this appears (after the update) not to be what is meant (yet I have to admit in retrospect that my argument for my, and I think the common, use of AP seems overly complicated).

Yet what OP is looking for is an arithemtic progression $S$ in $\mathbb{Z}$ (or rather $[1,N]$) such that $S^k$ is monochromatic. As noted by OP what the mentioned result gives is a monochromatic set of the form $u+S^k$. And, as mentioned in comments to actually get $S^k$ monochromatic is impossible.

(Sorry for the repeated edits.)

$\endgroup$
6
  • 3
    $\begingroup$ Welcome back to MO. $\endgroup$ Mar 22, 2013 at 1:41
  • $\begingroup$ @Benjamin Steinberg: Thank you! (Yet I am not really back, just visiting, but likely so frequently it will not make that much of a difference.) $\endgroup$
    – user9072
    Mar 22, 2013 at 1:59
  • $\begingroup$ Since there is confusion about the question, it would be better to make the answer explicitly clear, why not state the exact result you have in mind? $\endgroup$ Mar 22, 2013 at 2:42
  • 1
    $\begingroup$ @quid, thank you very much! Yes, you are indeed correct and this is helpful. It is almost the answer. In the Corollary, I could choose F to be some finite sublattice with equal length along each dimension. I will get a $u \in Z^k$ and $n \in Z$ such that $u + nF$ has the same color. Alas, if all coordinates in u are not equal, that does not give me the desired AP. Or am I missing something? $\endgroup$
    – Sesh
    Mar 22, 2013 at 2:45
  • $\begingroup$ @Francois, I have updated the question to clarify. The corollary quid has in mind is (I think): let S \subset Z^k have positive density. Let F be some finite configuration. There exists u \in Z^k and n \in Z such that u + nF \subset S $\endgroup$
    – Sesh
    Mar 22, 2013 at 2:47
2
$\begingroup$

Simple simultaneous generalizations of Ramsey's and van der Waerden's Theorem are available. The first was found by Bergelson and Hindman in their only paper published in Combinatorica. The second, which is similar but incompatible and perhaps cleaner, is available in my paper with Samet, Corollary 3.15. Say that a set of natural numbers is AP if it contains arbitrarily long arithmetic progressions. This corollary asserts that the Baumgartner-Taylor partition relation holds for AP sets: $$ \mathrm{AP}\longrightarrow \lceil \mathrm{AP}\rceil^k_n $$ for all $k$ and $n$.

For $n=2$, this corollary asserts the following: For each AP set $A$ and each finite edge-coloring of the complete graph with set of vertices $A$, there is an AP set $M$ of vertices and a partition of $M$ into finite sets such that all edges among distinct pieces of this partition are of the same color.

Using the compactness theorem, one may obtain a finite version of this theorem.

$\endgroup$
1
  • $\begingroup$ It may be that this theorem, or variations of it, may also be proved elsewhere. I would appreciate any references for other treatments of this result. $\endgroup$ May 12, 2014 at 3:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.