Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Van der Waerden theorem states that sufficiently long initial segment of the natural numbers when divided into $r$ parts contains an arithmetic progression of length $k$. The length of the initial segment is denoted as $W(k,r)$ which is called as the van der Waerden number.

I am looking for papers and research articles on a version of the same theorem where instead of arithmetic progressions we are guaranteed geometric progressions. The geometric van der Waerden theorem is a corollary to van der Waerden's theorem. In particular has any work been done on geometric van der Waerden numbers?

share|improve this question
    
I have seen it as an exercise at several places but what is your question? –  domotorp Sep 21 '13 at 8:57
1  
They are just equal to $G(k,r)=2^{W(k,r)-1}$. One inequality is obvious. For the other one, color $\prod_p p^{m_p}< G(k,r)$ by the color $c(1+\sum_p m_p)$. The general moral is that no literature search beats good old thinking process. –  fedja Sep 21 '13 at 8:58
    
@fedja: Is it possible to just use logarithms and reduce the multiplicative version to the additive version? –  Mark Sapir Sep 21 '13 at 10:49
    
@fedja: In your lower bound what is the coloring? What is $c$? –  Shahab Sep 21 '13 at 11:14
1  
@fedja: In your colouring, geometric progressions such as $\{ 3^n, 2 \times 3^{n-1}, 2^2 \times 3^{n-2}, \dots, 2^{n-1} \times 3, 2^n \}$ are monochromatic. Your answer works if we insist that the common ratio is an integer, though. –  Adam P. Goucher Sep 21 '13 at 11:24

1 Answer 1

Fedja has already answered one possible interpretation of your question in a comment, where the common ratio is required to be an integer. Here's further explanation, together with a multiplicative analogue of van der Waerden's theorem which is equivalent to Gallai-Witt. In what follows, I'm taking $\mathbb{N} = \{ 1, 2, 3, \dots \}$.

There's a straightforward isomorphism between the monoid $\mathbb{N}$ under multiplication and the direct sum $\mathbb{N} \oplus \mathbb{N} \oplus \cdots \oplus \mathbb{N}$ (with countably many copies of $\mathbb{N}$) under addition; the explicit bijection is $2^{a_1} 3^{a_2} 5^{a_3} \dots \rightarrow (a_1 + 1, a_2 + 1, a_3 + 1, \dots)$. Geometric progressions in $\mathbb{N}$ correspond to arithmetic progressions in the direct sum (henceforth abbreviated to $\mathbb{N}^{\omega}$, in a slight abuse of notation).

Fedja's answer involves colouring the points of $\mathbb{N}^{\omega}$ according to their sum (so hyperplanes perpendicular to $(1, 1, 1, \dots)$ have constant colour). Any geometric progression in $\mathbb{N}$ would correspond to an arithmetic progression in $\mathbb{N}^{\omega}$, which is then mapped to an arithmetic progression in $\mathbb{N}$. If the common ratio of the geometric progression is required to be an integer greater than $1$, then all the terms of the resulting arithmetic progression are distinct (otherwise, rational ratios such as $r = \frac{3}{2}$ give a non-injective map).

Anyway, even allowing rational ratios, I can still establish a weak bound in the opposite direction to the trivial bound. Given $G = G(k,r)$, the isomorphism gives a subset of $[\lceil \log_2{G} \rceil]^{\pi(G)}$, where $\pi$ is the prime-counting function. Now, we colour a point $(a_1 + 1, a_2 + 1, a_3 + 1, \dots)$ by $c(1 + a_1 \lceil \log_2{G} \rceil + a_2 (\lceil \log_2{G} \rceil)^2 + \dots)$, where (as in Fedja's answer) $c(n)$ is the colour of $n$ in the worst-case colouring for van der Waerden's theorem, establishing the following very weak bounds:

$$\lceil \log_2{G(k,r)} \rceil \leq W(k,r) \leq (\lceil \log_2{G(k,r)} \rceil)^{\pi(G(k,r))}$$

A refinement of this argument gives $W(k,r) \leq \prod_{p < \pi(G)} (\lceil \log_p{G(k,r)} \rceil)$.


On a related topic, the Gallai-Witt theorem states that, given a finite set $S \subset \mathbb{N}^n$ and a $k$-colouring of $\mathbb{N}^n$, we can find some scaled and translated copy of $S$ that is monochromatic. Using our isomorphism, this can be pulled back to a multiplicative statement in $\mathbb{N}$. Indeed, this multiplicative theorem seems to be shorter than the original Gallai-Witt theorem:

Given a finite set of naturals $\{ b_1, b_2, b_3, \dots, b_n \} \subset \mathbb{N}$ and a $k$-colouring of $\mathbb{N}$, we can find constants $A, B$ such that $\{ A b_1^B, A b_2^B, \dots, Ab_n^B \}$ is a monochromatic set.

The additive version of this statement is trivially equivalent to van der Waerden's theorem.

share|improve this answer
    
Could you explain the definition of $c(n)$? –  Shahab Sep 22 '13 at 4:29
    
"where (as in Fedja's answer) c(n) is the colour of n in the worst-case colouring for van der Waerden's theorem" –  Adam P. Goucher Sep 22 '13 at 8:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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