2
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ I have seen it as an exercise at several places but what is your question? $\endgroup$
    – domotorp
    Commented Sep 21, 2013 at 8:57
  • 2
    $\begingroup$ 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. $\endgroup$
    – fedja
    Commented Sep 21, 2013 at 8:58
  • $\begingroup$ @fedja: Is it possible to just use logarithms and reduce the multiplicative version to the additive version? $\endgroup$
    – user6976
    Commented Sep 21, 2013 at 10:49
  • $\begingroup$ @fedja: In your lower bound what is the coloring? What is $c$? $\endgroup$
    – user14875
    Commented Sep 21, 2013 at 11:14
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Sep 21, 2013 at 11:24

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Could you explain the definition of $c(n)$? $\endgroup$
    – user14875
    Commented Sep 22, 2013 at 4:29
  • $\begingroup$ "where (as in Fedja's answer) c(n) is the colour of n in the worst-case colouring for van der Waerden's theorem" $\endgroup$ Commented Sep 22, 2013 at 8:29

You must log in to answer this question.