REGRESSIVE RAMSEY NUMBERS ARE ACKERMANNIAN

MENACHEM KOJMAN AND SAHARON SHELAH

Abstract. We give an elementary proof of the fact that regressive Ramsey numbers are Ackermannian. This fact was first proved by Kanamori and McAloon with mathematical logic techniques.

Nous vivons encore sous le règne de la logique, voilà, bien entendu, à quoi je voulais en venir. Mais les procédés logiques, de nos jours, ne s’appliquent plus qu’à la résolution de problèmes d’intérêt secondaire. [1, 1924, p. 13]

1. Introduction

Definition 1. 1. let A be a set of natural numbers. A coloring c : [A]^{e} → ℕ of

unordered e-tuples from A is regressive if c(x) < min x for all x ∈ [A]^{e}.

2. A subset B ⊆ A is min-homogeneous for a coloring c of [A]^{e} if for all x ∈ [A]^{e} the color c(x) depends only on min x.

Theorem 2 (Kanamori and McAloon). 1. For every k and e there exists N such that for every regressive coloring of e-tuples from {1, 2, …, N} there exists a min-homogeneous subset of size k.

2. The statement in (1) cannot be proved from the axioms of Peano Arithmetic (although it can be phrased in the language of PA)

3. Let ν(k) be the least N which satisfies 1 for e = 2. The function ν eventually dominates every primitive recursive function.

Part (3) of Kanamori and McAloon’s result [3] was proved with methods from mathematical logic. We present below an elementary proof of 3.

2. The lower bound

For every function f : ℕ → ℕ and n, f^{(n)} is defined by f^{(0)}(x) = x and f^{(n+1)}(x) = f(f^{(n)}(x)) for all x ∈ ℕ.

Define a sequence of (strictly increasing) integer functions f_{i} : ℕ → ℕ for i ≥ 1 as follows:

f_{1}(n) = n + 1  (1)
f_{i+1}(n) = f_{i}^{(⌊\sqrt{n}/2⌋)}(n)  (2)

Fix an integer k > 2. Define a sequence of semi-metrics ⟨d_{i} : i ∈ ℕ⟩ on {n : n ≥ 4k^{2}} by putting, for m, n ≥ 4k^{2},

The first author was partially supported by NSF grant No. DMS-9622579.

The second author was partially supported by the Binational Science Foundation. Number 649 in list of publications.

d_{i}(m, n) = |{l ∈ ℕ : m < f_{i}^{(l)}(4k^{2}) ≤ n}|  (3)

For n > m ≥ 4k^{2} let I(m, n) be the greatest i for which d_{i}(m, n) is positive, and d(m, n) = d_{I(m,n)}(m, n).

Claim 3. For all n ≥ m ≥ 4k^{2}, d(m, n) ≤ \sqrt{m}/2.

Proof. Let i = I(m, n). Since d_{i+1}(m, n) = 0, there exists t and l such that t = f_{i+1}^{(l)}(4k^{2}) ≤ m ≤ n < f_{i+1}^{(l+1)}(4k^{2}) = f_{i+1}(t). But f_{i+1}(t) = f_{i}^{(⌊\sqrt{t}/2⌋)}(t) and therefore \sqrt{t}/2 ≥ d_{i}(t, f_{i+1}(t)) ≥ d(m, n).

Let us fix the following (standard) pairing function Pr on ℕ^{2}

Pr(m, n) = \binom{m + n + 1}{2} + n

Pr is a bijection between ℕ^{2} and ℕ and is monotone in each variable. Observe that if m, n ≤ l then Pr(m, n) < 4l^{2} for all l > 2.

Define a pair coloring c on {n : n ≥ 4k^{2}} as follows:

c({m, n}) = Pr(I(m, n), d(m, n))  (4)

Claim 4. For every i ∈ ℕ, every sequence x_{0} < x_{1} < ⋯ < x_{i} that satisfies d_{i}(x_{0}, x_{i}) = 0 is not min-homogeneous for c.

Proof. The claim is proved by induction on i. If i = 1 then there are no x_{0} < x_{1} with d_{1}(x_{0}, x_{1}) = 0 at all. Suppose to the contrary that i > 1, that x_{0} < x_{1} < ⋯ < x_{i} form a min-homogeneous sequence with respect to c and that d_{i}(x_{0}, x_{i}) = 0. Necessarily, I(x_{0}, x_{i}) = j < i. By min-homogeneity, I(x_{0}, x_{1}) = j as well, and d_{j}(x_{0}, x_{i}) = d_{j}(x_{0}, x_{1}). Hence, {x_{1}, x_{2}, … x_{i}} is min-homogeneous with d_{j}(x_{1}, x_{i}) = 0 — contrary to the induction hypothesis.

Claim 5. The coloring c is regressive on the interval [4k^{2}, f_{k}(4k^{2})).

Proof. Clearly, d_{k+1}(m, n) = 0 for 4k^{2} ≤ m < n < f_{k}(4k^{2}) and therefore I(m, n) < k ≤ \sqrt{m}/2. From Claim 3 we know that d(m, n) ≤ \sqrt{m}/2. Thus, c(\{m, n\}) ≤ Pr(⌊\sqrt{m}/2⌋, ⌊\sqrt{m}/2⌋), which is < m, since \sqrt{m} > 2.

We show that f_{k}(4k^{2}) grows eventually faster than every primitive recursive function by comparing the functions f_{i} with the usual approximations of Ackermann’s function. It is well known that every primitive recursive function is dominated by some approximation of Ackermann’s function (see, e.g. [2]).

Let A_{i}(n) be defined as follows:

A_{1}(n) = n + 1  (5)
A_{i+1}(n) = A_{i}^{(n)}(n)  (6)

The A_{i}-s are the usual approximations to Ackermann’s function, which is defined by Ack(n) = A_{n}(n).

Claim 6. 1. for all n ≥ 16 and i ≥ 7, (a) 16n^{2} ≤ f_{i}(n);

(b) f_{i}(16n^{2}) ≤ f_{i}^{(2)}(n).

2. A_{i}(n) ≤ f_{i+6}^{(2)}(n) for all i ≥ 1 and n ≥ 16.

Proof. Inequality (a) is verified directly.

Inequality (b) follows from (a) by substituting f_{i}(n) for 16n^{2} in f_{i}(16n^{2}), since f_{i} is increasing.

We prove 2 by induction on i. For i = 1 it holds that n + 1 < f_{7}^{(2)}(n) for all n ≥ 16 by (a).

Suppose the inequality holds for i and all n ≥ 16, and let n ≥ 16 be given. Since A_{i}(n) ≤ f_{i+6}^{(2)}(n) for all n ≥ 16, it follows by monotonicity of A_{i} that A_{i}^{(n)}(n) ≤ f_{i+6}^{(2n)}(n). The latter term is smaller than f_{i+6}^{(2n)}(16n^{2}) by monotonicity, which equals f_{i+7}(16n^{2}) by (2). Inequality (b) implies that A_{i}^{(n)}(n) ≤ f_{i+7}^{(2)}(n). Finally, A_{i}^{(n)}(n) = A_{i+1}(n) by (6).

Claim 7. For all i ≥ 7 and n ≥ 16 it holds that A_{i}(n) ≤ f_{i+7}(n).

Proof. By 2 in the previous claim, A_{i}(n) ≤ f_{i+6}^{(2)}(n) for n ≥ 16. If n ≥ 16, then

\sqrt{n}/2 ≥ 2 and hence, by (2), f_{i+7}(n) =^{def} f_{i+6}^{⌊(\sqrt{n}/2⌋)} ≥ f_{i+6}^{(2)}(n).

Corollary 8. The function ν(k) eventually dominates every primitive recursive function.

3. Discussion

3.1. Other Ramsey numbers. Paris and Harrington [8] published in 1976 the first finite Ramsey-type statement that was shown to be independent over Peano Arithmetic. Soon after the discovery of the Paris-Harrington result, Erdős and Mills studied the Ramsey-Paris-Harrington numbers in [7]. Denoting by R_{c}^{e}(k) the Ramsey-Paris-Harrington number for exponent e and c many colors, Erdős and Mills showed that R_{2}^{2}(k) is double exponential in k and that R_{c}^{2}(k) is Ackermannian as a function of k and c. In the same paper, several small Ramsey-Paris-Harrington numbers were computed. Later Mills tightened the double exponential upper bound for R_{2}^{2}(k) in [5].

Canonical Ramsey numbers for pair colorings were treated in [4] and were also found to be double exponential.

The second author showed that van der Waerden numbers are primitive recursive, refuting the conjecture that they were Ackermannian, in [9] (see also [6]).

We remark that an upper bound for regressive Ramsey numbers for pairs is R_{2}^{3}(k) — the Ramsey-Paris-Harrington number for triples. Let N be large enough and suppose that c is regressive on {1, 2, …, N − 1}. Color a triple x < y < z red if c(x, y) = c(x, z) and blue otherwise. Find a homogeneous set A of size at least k and so that |A| > min A + 1. The homogeneous color on A cannot be blue for k > 5, and therefore A is min-homogeneous for c.

3.2. Problems. The following two problems about regressive Ramsey numbers remain open:

Problem 9. 1. Find a concrete upper bound for regressive Ramsey numbers. 2. Compute small regressive Ramsey numbers

References

[1] André Breton. Manifeste du surréalisme. In Manifestes du Surréalisme, pages 11–66. Gallimard, 1972.

[2] Calude, Cristian. Theories of computational complexity. Annals of Discrete Mathematics, 35. Amsterdam etc.: North-Holland. XII, 487 p., 1988.

[3] Akihiro Kanamori and Kenneth McAloon. On Gödel incompleteness and finite combinatorics. Ann. Pure Appl. Logic, 33(1):23–41, 1987.

[4] Hanno Leffman and Vojtěch Rödl. On canonical Ramsey numbers for complete graphs versus paths. Journal of Combinatorial theory, Series B, 58:1–13, 1993.

[5] George Mills. Ramsey–Paris–Harrington numbers for graphs. Journal of Combinatorial theory, Series A, 38:30–37, 1985.

[6] Alon Nilli. Shelah’s proof of the Hales-Jewett theorem. In Jaroslav Nešetřil and Vojtěch Rödl, editors, Mathematics of Ramsey Theory, volume 5 of Algorithms and Combinatorics, pages 151–152. Springer, Berlin, 1990.

[7] Paul Erdős and George Mills. Some bounds for the Ramsey-Paris-Harrington numbers. Journal of Combinatorial theory, Series A, 30:53–70, 1981.

[8] J. Paris and L. Harrington. A mathematical incompleteness in Peano arithmetic. In J. Barwise, editor, Handbook of Mathematical Logic. North-Holland, 1977.

[9] Saharon Shelah. Primitive recursive bounds for van der Waerden numbers. Journal of the American Mathematical Society, 1:683–697, 1988.

Department of Mathematics and Computer Science, Ben Gurion University of the Negev, Beer Sheva, Israel

Department of Mathematical Sciences, Carnegie-Mellon University, Pittsburgh, PA

   E-mail address: kojman@cs.bgu.ac.il

Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem 91904, Israel

   E-mail address: shelah@math.huji.ac.il