HJ numbers revisited

summary

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.

In short

This paper seeks a primitive recursive bound for density Hales-Jewett numbers, HJminε(Λ, r). It builds upon previous work by using a double induction strategy involving downward induction on colors and an inductive step based on choosing cardinalities. The result establishes that this density version is bounded by an E5 function, which is explicitly shown to be primitive recursive.

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 used across episodes

This episode discusses

The paper

HJ numbers revisited · Read on arXiv

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.

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.

More episodes

← Home