HJ numbers revisited

arXiv:2607.14732 · math.CO · Submitted 2026-07-16 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "HJ numbers revisited".

Emmy: Here's the gist of the paper. The paper improves the bounds on density Hales-Jewett numbers to a primitive recursive function, relating this work to theorems like Szemeredi and Van der Waerden theorems.

Ada: The paper aims to prove a primitive recursive bound for a version of the density Hales-Jewett theorem denoted as HJminε(Λ, r) The exposition is self-contained.

Emmy: The history of this problem is well-known, with the original density version proven via ergodic theory by Furstenberg and Katznelson.

Ada: A landmark quantitative elementary combinatorial proof was discovered later by Polymath 1.

Paper summary: Ada: So we're looking at this paper called "HJ numbers revisited". It’s about improving the bounds on density Hales-Jewett numbers to something much more concrete.

Emmy: It claims they can get a primitive recursive bound for a version of the density Hales-Jewett theorem, which they call HJmin epsilon lambda r. The context is that the original density version was proven using ergodic theory by Furstenberg and Katznelson, but earlier elementary combinatorial proofs gave bounds that were way too big, involving things like the Ackermann function.

Kolya: So they’re moving away from those super fast growing functions and aiming for something manageable. What does this mean for the actual density version of Hales-Jewett theorem?

Ada: Well, the paper establishes that this density version is bounded by a tower of exponentiation, which is what we call a tetration bound. More specifically, they prove that HJmin epsilon lambda r is bounded by an E5 function in the Grzegorczyk hierarchy.

Emmy: That’s significant because it shows they can get there from a primitive recursive function, not just some abstract complexity class. It connects this work to other big theorems like Szemeredi and Van der Waerden theorems, which is what the introduction points out as related areas of study.

Kolya: So if the bound is E5, that’s still a pretty high level of complexity for something we're trying to pin down precisely. What exactly are they focusing on in their approach?

Ada: The core idea involves a double induction strategy, first on n which is the cardinality of the alphabet lambda, and then on p which is the number of colors. They use a technique where they fix the number of colors and only perform induction on n initially.

Emmy: And in that inductive step, they choose the size of some set ni and epsilon i by doing a downward induction on i less than r. This choice naturally leads to needing a tetration function as an upper bound for Hales-Jewett numbers, which puts them in E5 territory.

Kolya: So it sounds like they are trying to tame the growth rate of this number by controlling how those subsets grow and how many colors you have available across different levels. What about the actual results they state?

Ada: They establish a few key things. First, HJmin epsilon n one is well-defined and finite for all epsilon greater than zero and n greater than or equal to two. That’s a solid starting point for the density version.

Emmy: And second, they confirm that the density version of Hales-Jewett theorem is bounded by that tower of exponentiation, which we already touched on. But third, they state that HJmin epsilon lambda r is bounded by an E5 function and emphasize that this bound in their proof is primitive recursive.

Kolya: So the main punch here seems to be getting that explicit, primitive recursive bound instead of just a general tower of exponentiation. What are the implications of getting a primitive recursive bound?

Paper summary: Ada: It means we have a very concrete way to calculate how big these numbers can get, rather than just knowing they are bounded by an E5 function abstractly. It’s like moving from saying something is less than some astronomical number to saying it's less than some function that you could actually compute with a computer algorithm.

Emmy: And the paper explicitly claims this bound is primitive recursive, which is a very strong statement in terms of computational complexity. It connects directly back to the original problem by showing a more elementary combinatorial path exists, even if the resulting function is still relatively high up on the complexity ladder.

Kolya: I wonder what that means for probabilistic applications. If we have this bound, does it help us with things like finding specific structures in random graphs or sets? What tails of the distribution are we controlling?

Ada: Kolya’s question is important. The paper focuses on the density version, HJmin epsilon lambda r, which deals with subsets having a density greater than some epsilon. So it governs how dense those subsets need to be to guarantee a line exists.

Emmy: The structure behind this is that they show an "essential equivalence" between two versions of the density Hales-Jewett theorem, HJav epsilon lambda r and HJmin epsilon lambda r, and this equivalence is what lets them build that inductive step in their proof.

Kolya: So for someone who only cares about how this changes things practically, it means we have a more controlled way to say when a dense enough structure must contain a line. But the paper itself admits its limitation by focusing on HJmin epsilon lambda r, which is one version of the density Hales-Jewett theorem.

Ada: Exactly. They state that their bound is E5, and they are working on improving it further to just iteration of exponentiations in section three. So while they have a primitive recursive bound now, the ultimate goal they are aiming for is even lower complexity in terms of how fast that function grows.

Emmy: It shows how deep the combinatorial structure goes when you try to tackle these Ramsey-type problems from a purely set-theoretic or combinatorial standpoint, rather than relying on tools like ergodic theory which Furstenberg and Katznelson used initially.

Kolya: So, to sum up what we’ve heard about "HJ numbers revisited", they improved the bound on density Hales-Jewett numbers to an E5 function that is primitive recursive, connecting it back to the original theorem and showing a more elementary combinatorial path exists.

Ada: Right. And their final point is that they are still working towards refining this bound even further by aiming for just iteration of exponentiations in section three. That’s where the real work on making the function as simple as possible is happening.

Conclusion: Ada: So, we've looked at how they tackled the density Hales-Jewett numbers in this new paper called "HJ numbers revisited."

Emmy: It seems like they're focusing on getting a much tighter bound than what was available before.

Ada: Exactly. They aim to show that the density version of this theorem, which we call HJmin epsilon lambda r, can be bounded by a primitive recursive function.

Kolya: That's interesting because it moves the discussion away from those extremely fast growing functions like the Ackermann function that showed up in earlier proofs.

Emmy: Yes, and they achieve this by using a double induction strategy on both the alphabet size and the number of colors. It’s a very structured way to build up the proof.

Ada: And their main result is that this bound is E5, which means it’s within a specific, relatively well-understood class of functions in complexity theory.

Kolya: But what does E5 actually mean for the real world when we're talking about these density requirements? Does it guarantee something concrete about how dense a set needs to be?

Emmy: It means they have found a way to control that density requirement through this structured combinatorial approach. It’s connecting the geometric structure of Hales-Jewett sets to complexity classes.

Ada: The authors are trying to establish this from a purely elementary combinatorial standpoint, which is a departure from the ergodic theory methods used by Furstenberg and Katznelson initially.

Kolya: So, if we think about probabilistic applications, what does this primitive recursive bound tell us about the tails of distributions? Does it help us figure out when those dense structures are going to appear?

Emmy: It gives us a more concrete scale for how large those necessary sets can be before the theorem guarantees a line exists. It’s moving from an abstract upper limit to something we can actually compute with algorithms.

Ada: And while they hit that primitive recursive bound, the authors admit they are still looking to refine it further, aiming for just iteration of exponentiations in their next steps.

Emmy: So the title itself points to a re-examination of these numbers, suggesting this work is about tightening the screws on these bounds.

Kolya: It makes me wonder how much simpler the structure actually is underneath all that induction when you look at it from a set theory angle.

math.CO

Submitted: 2026-07-16

Updated: 2026-11-05

Comments: proofread and expanded

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 60/100

The gist: The paper improves the bounds on density Hales-Jewett numbers to a primitive recursive function, relating this work to theorems like Szemeredi and Van der Waerden theorems.

Key concepts

Density Hales-Jewett numbers (HJminε(Λ, r))
These numbers relate to the density version of the Hales-Jewett theorem. The paper aims to find a specific bound for these numbers, which quantify how large a structure must be before it guarantees a certain density property.
Primitive recursive function
This is a class of functions in computability theory that can be constructed using basic arithmetic operations like addition, multiplication, exponentiation, and primitive recursion. Proving the bound is primitive recursive means the growth rate of the required number is well-defined within this mathematical framework.
Double induction strategy
The proof uses a two-step inductive process. First, it inducts on 'n' (the size of the alphabet $\Lambda$), and second, it inducts on 'p' (the number of colors). This systematic approach is essential for establishing the complex bounds required by the theorem.
Tetration bound
Tetration is a function that represents repeated exponentiation. The paper notes that the density version of Hales-Jewett is bounded by a tower of exponentiation, which suggests that the complexity of these numbers grows extremely rapidly, necessitating such a high-level bound.

Terminology

Summary

The paper improves the bounds on density Hales-Jewett numbers to a primitive recursive function, relating this work to theorems like Szemeredi and Van der Waerden theorems. p. 0

Where the paper says it

We improve the bounds on the density Hales-Jewett numbers to a primitive recursive function. This relates to Hales-Jewett theorem as Szemeredi theorem relates to Van-der-Waerden theorem.

Introduction and Context

The paper aims to prove a primitive recursive bound for a version of the density Hales-Jewett theorem denoted as HJminε(Λ, r) The exposition is self-contained. The history of this problem is well-known, with the original density version proven via ergodic theory by Furstenberg and Katznelson. p. 2

Where the paper says it

) Here in §1 we get a bound in terms of tetration (power towers). The Density Hales–Jewett Theorem, stating that any dense subset of the grid [ℓ] n contains a combinatorial line, was originally proven via ergodic theory by Furstenberg and Katznelson [FK91].

A landmark quantitative elementary combinatorial proof was discovered later by Polymath 1. p. 2
Where the paper says it

The Density Hales–Jewett Theorem, stating that any dense subset of the grid [ℓ] n contains a combinatorial line, was originally proven via ergodic theory by Furstenberg and Katznelson [FK91]. A landmark quantitative elementary combinatorial proof was discovered (considerably later) by Polymath 1 [Pol12], a massively collaborative project.

The resulting bound there is above the Ackermann function, and so the function was not shown to be primitive recursive. p. 6
Where the paper says it

A purely combinatorial proof appeared twenty years later, as a result of the Polymath 1 project [Pol12]. The resulting bound there is above the Ackermann function, and so the function was not shown to be primitive recursive.

Bounding Techniques

The proof relies on a double induction strategy, first on n (the cardinality of the alphabet Λ) and then on p (the number of colors). The base idea of [She88] is that we fix the number of colors C and perform our induction only on n. p. 4

Where the paper says it

Eventually they get an upper bound in terms of the Ackermann function, which is not primitive recursive. The base idea of [She88] is that we fix the number of colors |C| and perform our induction only on n .

The inductive step involves choosing the cardinality of Ni and εi by downward induction on i < r. p. 4
Where the paper says it

A difference with [She88] is that we choose the middle road — not fixing the number of colors, that is, in the density, but carefully controlling how quickly they are allowed to proliferate. We choose the cardinality of Ni and εi by downward induction on i < r.

This choice naturally requires a tetration function as a bound for HJ, leading to a bound in E5. p. 4
Where the paper says it

This was done such that the coloring does not change if we replace some of the α-s by β-s (or vice versa): we reduce this case of the problem to one with one letter less, hence can use the induction hypothesis, that is, the choice of r gives the desired conclusion. So ki and ℓi were chosen by downward induction on i < r, and naturally we required |Ni | > |C| P j<i |Nj | , so for our lemma we had a tetration function as a bound.

Key Results and Bounds

The paper establishes several key results regarding the density version of Hales-Jewett theorem. Specifically:

  1. HJminε(n, 1) is well-defined and finite for all ε ∈ (0, 1] and n ≥ 2. p. 6

    Where the paper says it

    The function HJε(n, 1) [see Definition 0. 4] is well-defined and finite for all ε ∈ (0, 1] and n ≥ 2.

  2. The density version of Hales-Jewett theorem is bounded by a tower of exponentiation = tetration bound. p. 1

    Where the paper says it

    §3 The E 4 bound p. 20 We prove the density version of Hales-Jewett theorem is bounded by a tower of exponentiation = tetration bound.

  3. HJminε(Λ, r) is bounded by an E5 function, i. p. 1

    Where the paper says it

    §3 The E 4 bound p. 20 We prove the density version of Hales-Jewett theorem is bounded by a tower of exponentiation = tetration bound.

    e., by fΛ+r+⌈1/ε⌉ for some f ∈ E5 The bound in the proof is not only explicit but even primitive recursive. p. 2
    Where the paper says it

    Later and independently, the present author, proved a combinatorial theorem which also implied a Polynomial van der Waerden. The bound in the proof is not only explicit but even primitive recursive.

Advanced Combinatorial Tools

The work employs sophisticated combinatorial tools, including the Corr´adi lemma, (b) A is a finite non-empty set and µ = µA is as in 1.1, and (c). For i 0 < ζ ≤ ε(εn − 1)/n − 1. p. 6

Where the paper says it

(c) For i < n we have Ai ⊆ A with µ(Ai) ≥ ε. (d) 0 < ζ ≤ ε(εn − 1) n − 1 (B) There exist k < ℓ < n such that µ(Ak ∩ Aℓ) ≥ ζ.

These tools are used to establish the inductive step in the proof of HJminε(Λ, r). p. 4
Where the paper says it

Explanation. Here, on the one hand, we give new bounds, and on the other hand we give some bounds to some relatives; usually they are inspired by the main inductive step in the proof of [She88, §1].

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Primitive recursive bound improvement allows for explicit complexity bounds on finding combinatorial lines in dense subsets of grids, specifically bounding HJmin epsilon (Λ, r) by a function in E5 or a tower of height O(Λ).

  2. The system notation and machinery developed allow the AI to perform inductive steps on complex combinatorial structures by relating them to pre-systems and using Claim 1.7 to establish structural equivalences between systems under specific conditions.

  3. The framework enables the AI to transition from density versions of theorems, such as HJ epsilon (Λ, r), to average versions (HJav epsilon (Λ, r)) with established bounds and relationships like HJepsilon(Λ, r) <= HJavepsilon(Λ, r).

  4. The machinery in Section 3 allows the system to derive bounds for the Hales-Jewett theorem in terms of E4 functions by leveraging Claim 3.12 and relating density versions to average versions using sequences of parameters εi.

Abstract

Hales-Jewett theorem is well known. We prove a primitive recursive bound, in fact an 5 one, for the density version. In preparation we deal with what was the main induction step in the old proof of Hales-Jewett as a result in its own right with better bounds. Also in improving our bounds.

Sources

Related papers