Reasonable bounds for Restricted Polynomial Progressions in F n p

arXiv:2610.12831 · math.NT, math.CA, math.CO · Submitted 2026-10-09 · 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: "Reasonable bounds for Restricted Polynomial Progressions in F n p".

Emmy: Here's the gist of the paper. Given an integer k ≥ 2 and a prime p large enough depending on k, we show that if A ⊆ F n p does not contain a restricted polynomial progression of the form x, x + y1, y2..., x + Pk−1(y), where x ∈ F n p and y ∈ Yn without⃗0 for some fixed Mk, then A must have density bounded above by C (log(kO(k)) n) c.

Ada: The main result proves that for k ≥ 4, the bound improves from the previously known Hales–Jewett theorem bound to one involving k O(k) iterated logarithms.

Emmy: How the training signal is built The proof of Theorem 1.1 relies on a density increment argument on coordinate fibers, which proceeds through four main steps.

Ada: These steps involve a counting distribution, showing that if no progression exists, the expected count is far below the random set prediction.

Title and authors: Ada: So we're looking at this paper right now, "Reasonable bounds for Restricted Polynomial Progressions in F n p," and what it’s trying to establish about sets in finite fields. The main idea is that if you don't find a restricted polynomial progression of a certain form inside your set A, then the size of that set A cannot be too large.

Emmy: That's right, Ada, essentially they are looking at these specific sequences like x plus y one and x plus y two and so on up to x plus y k minus one. The paper is focused on getting a reasonable bound for how big those sets can get without containing such a structure.

Kolya: I was reading the summary, and it sounds like they're moving past some older bounds, which is important because earlier bounds were quite weak for higher values of k. What exactly are they saying about the density bound itself?

Ada: The core result, Theorem one point one, states that if n is big enough relative to k, and you have a set A in F n p that avoids these progressions where y is drawn from a specific set Y without zero, then the density of A has to be bounded by something involving iterated logarithms of k times k <ref:2610.12831#pg1>.

Emmy: It seems they are using a density increment argument on coordinate fibers to prove this. They are showing that if no progression exists, the expected count in those fibers is much lower than what you’d expect from a random set prediction, which sets up the initial step for them.

Kolya: That sounds like a standard technique in combinatorics for these kinds of problems, but I'm curious about the machinery they use to make that increment work. What's the key ingredient there?

Ada: The second step relies on ruling out nontrivial abelian embeddings using an inverse theorem from Bhangale, Khot, Liu and Minzer. This theorem connects whether a distribution admits an abelian embedding to a noise stability result.

Emmy: That noise stability result is what gives them the leverage for the density increment on a coordinate fiber. It means if you can rule out those embeddings, the structure of the set A becomes more constrained in terms of how it can be distributed across coordinates.

Kolya: So, if we have this noise stability result from that inverse theorem, what does it tell us about these restricted progressions? Does it help them prove something specific about their setup?

Title and authors: Ada: It allows for the iteration of this process because they include y equals zero in the set Y. That inclusion is what lets them move through several steps until they establish a bound on n that is equivalent to Theorem one point one, which involves k times iterated logarithms <ref:2610.12831#pg1>.

Emmy: And then there’s this part where they rigorously show that the configuration admits no nontrivial abelian embedding into finite fields of different characteristics. They analyze a matrix equation called A sub l M with lambda in characteristic q not equal to p, and they show its rank is full, which forces the embedding to be trivial.

Kolya: That’s a big structural piece of evidence they’re using to rule out those embeddings across different fields. How does that specific rank condition connect back to ruling out the progressions themselves?

Ada: It’s part of showing that if you have these polynomial steps, the underlying distribution cannot support an embedding into something more complex than what they are looking for. This is a key step in their proof strategy for Theorem one point one <ref:2610.12831#pg1>.

Emmy: Moving on to the quantitative bounds, they look at specific cases first so we can see how the general result improves things over what was known before. For example, they mention k equals two and three earlier in the literature.

Kolya: What are those specific bounds for k equals two and three? Are they comparable to what we saw before?

Ada: For k equals two, a density Hales–Jewett argument applies, giving a bound where the size of A is less than p to the power of n minus one half. That's quite strong for that case.

Emmy: And for k equals three, they refer to work by Bhangale, Khot, Liu and Minzer from two years ago, which gave a bound related to log log log n. It shows that even for small k values, the bounds can be very tight.

Kolya: So you have a specific quantitative result for k equals three that is better than what was available then? What does that imply for the general case where k is larger?

Ada: For the general case where k is four or bigger, they improved upon the previous inverse Ackermann type bound by using a bound involving k times iterated logarithms. That's a significant improvement in terms of how fast that bound grows with n.

Emmy: So, the main result is that for any k greater than or equal to four, there exists some constant K equal to k times the iterated logarithm of n such that if n is bigger than e raised to K, and your set A has density at least C times log of K times log of n, then you are guaranteed a nontrivial restricted polynomial progression.

Title and authors: Kolya: I’m trying to wrap my head around what this means for someone who doesn't work in these specific algebraic structures. What is the practical implication of that bound?

Ada: The practical implication is that sets avoiding these complex polynomial patterns are actually much sparser than previously thought, and the bound they provide, C times log of k times log n, is a better description of how sparse they are for larger k.

Emmy: It shows that the structure imposed by those restricted polynomials forces a certain level of complexity on any set trying to avoid them. The fact that they use this noise stability result to get the density increment is where the real structural insight lies in this paper, "Reasonable bounds for Restricted Polynomial Progressions in F n p."

Kolya: I'm just wondering about what the authors themselves flag as a limitation. Does their method only work under certain conditions? What’s not covered by this specific proof?

Ada: One thing they mention is that they use every value y in Y, which means the zero value of y eliminates the f zero term, but they rely on the values y without zero to supply the rows of those matrices A sub l M that appear later. So, their argument hinges on having enough non-zero elements in Y for those matrices.

Emmy: That’s a practical constraint on how you choose your set Y; it can't be too sparse if you want the whole machinery of the proof to work as intended. It keeps the complexity tied to the structure of that set Y itself.

Kolya: So, if we look at this paper, "Reasonable bounds for Restricted Polynomial Progressions in F n p," what does it suggest for future research in this area? What’s next?

Ada: Future work will likely involve refining the density increment argument to see if they can push that bound even further down, maybe closer to what is known for k equals two or three.

Emmy: Or perhaps exploring how the noise stability result applies when you look at these structures over different fields, which we touched on earlier regarding embeddings into different characteristics. That seems like a natural next step for understanding the full scope of these polynomial progressions in finite fields.

Kolya: And from my probabilistic side, I'm interested in whether the constant C they mention survives when you try to apply this to more complex random distributions, not just uniform ones. Does that bound hold up under different statistical assumptions?

Title and authors: Ada: That’s exactly where Kolya’s expertise comes in. The current result is established for a distribution counting restricted polynomial progressions, and extending it requires careful analysis of the probability measure itself.

Emmy: It seems like this paper is really solid because they've tied together algebraic geometry—like the inverse theorem—with probabilistic tools, like the noise stability result, to get these quantitative bounds. It’s a very integrated approach for studying geometric structures in number theory.

Kolya: I agree, it's that integration that makes it compelling for me. The way they use the machinery from Bhangale, Khot, Liu and Minzer to stabilize the distribution is what gives this result its power.

Ada: So to wrap up on this paper, "Reasonable bounds for Restricted Polynomial Progressions in F n p," we’ve seen that they establish a bound involving k times iterated logarithms for k greater than three. They've done this by using noise stability results derived from inverse theorems and density increments on coordinate fibers.

Emmy: It also showed that for smaller values of k, like two and three, there are established bounds related to Hales-Jewett arguments or log log log n, respectively. The paper confirms that these methods yield the best known quantitative results for those specific configurations.

Kolya: And the main point is that the general result gets better as k increases, shifting from an inverse Ackermann type bound to one involving k times iterated logarithms. That’s a concrete improvement in complexity scaling for those sets.

Ada: Exactly, it’s a refinement of what was known before, making the bounds more precise when you look at larger polynomial degrees. We've discussed the main result and how they achieved it using noise stability and embeddings into different characteristics.

Emmy: It really is a great piece of work because it takes these abstract geometric concepts and makes them yield concrete, usable density estimates for sets in finite fields, which is what we need to keep building on.

Kolya: So to summarize for the listener, this paper "Reasonable bounds for Restricted Polynomial Progressions in F n p" shows that if you avoid these specific polynomial patterns in a set A over a large enough field, the set A has a density bounded by something involving k times iterated logarithms.

Ada: That’s right. It's about controlling the size of sets based on what geometric structures they lack. We’ve covered the title, the summary, and how they improved on previous results for k two and three as well as for larger k values using noise stability arguments.

The paper's summary: Ada: So, to recap, this paper is looking at sets A in finite fields F n p that don't contain certain specific polynomial sequences, and they found that if you avoid those sequences for a sufficiently large set size n, then the density of your set A has to be bounded by something involving k times iterated logarithms.

Emmy: That’s right. The whole point is connecting geometric constraints—those restricted polynomial progressions—to density bounds in these finite fields. It shows that even when you only exclude a specific, structured type of pattern, the size of the set A still has to shrink quite fast as n grows.

Kolya: What's interesting about this particular result is how it handles different values of k. They’ve done some specific quantitative work for k two and three earlier on, which are already pretty tight bounds using Hales–Jewett ideas or something similar.

Ada: Exactly. For k two, the bound is related to n minus one half. And for k three, they got a log log log n bound from that earlier work by Bhangale et al., which is quite specific to that case.

Emmy: But the main thrust of this new paper is for larger values of k, specifically four or more. They improved upon the old inverse Ackermann type bounds by using a bound involving k times iterated logarithms. That’s a better description of how fast those sets must be sparse when you look at higher degrees.

Kolya: So, if I just listen to this, what does it mean for me? It means that if you are looking at some random set in a huge finite field and you don't see these complicated polynomial patterns, the set isn't as big as we might have thought before for larger k.

Ada: That’s the probabilistic side of it. The paper shows that the structure imposed by avoiding those progressions forces a certain level of complexity on any set trying to avoid them. It’s about controlling size based on what geometric structures you lack in your data.

Emmy: And the mechanism they use is really clever—they use a noise stability result from an inverse theorem to get a density increment on coordinate fibers, which lets them iterate the process until they hit that bound involving k times iterated logarithms. That’s where the real structural insight is.

Kolya: I wonder if that noise stability part holds up if we try to apply this to distributions that aren't perfectly uniform. The current result is for a distribution counting progressions, so extending it requires looking at the probability measure itself, right?

Ada: That’s a good question Kolya. Extending it would require careful analysis of the probability measure, because the current proof is tied to how that specific count behaves.

Emmy: And they did show something else important—they proved that this configuration admits no nontrivial abelian embedding into finite fields of different characteristics. They used a matrix equation and showed its rank is full, which rules out those embeddings entirely.

Kolya: Ruling out the embeddings across different characteristics sounds like it strengthens the whole argument for why the density must be low. Does that really tighten up the situation?

Ada: It does, because ruling out those embeddings is a key step in showing that you can't support a set A with a density higher than their calculated bound. We’ve seen how they used this machinery to get the general result for k four and up.

Emmy: So, to wrap up on what we’ve heard about "Reasonable bounds for Restricted Polynomial Progressions in F n p," we have the main result involving k times iterated logarithms for larger k, and it’s built on a clever use of noise stability and embedding analysis. Next time we talk about these kinds of geometric constraints, I want to see if they can push those density bounds even closer to the specific results they got for k two and three.

The paper's improvements: Ada: So, we're looking at how they suggest ways to make this paper even better than what they just proved about restricted polynomial progressions in finite fields.

Emmy: They are suggesting an adaptive density increment method for these progressions, which means the system can actively check if a set A contains those patterns by finding smaller subsets and checking their density against a specific threshold.

Kolya: An adaptive approach sounds powerful, but how does that actually change the complexity? Does it just give us a tighter constant, or is it fundamentally different in terms of what it can handle?

Ada: It means the system can determine if a set A contains those progressions by iteratively finding subsets with size at least n squared and then constructing a new subset A sub S that has density at least alpha plus delta over three twenty-two.

Emmy: That delta is derived from the initial density of the set A and that k value we're talking about, so it makes the increment process much more tailored to the specific structure of the set. It’s like having a smarter search strategy for finding patterns in high dimensions.

Kolya: So, if I were to use this adaptive method, would that require me to have a very good initial guess about the density of A? Because if my guess is off by a lot, does the whole process just fail or get way slower?

Ada: It requires an initial estimate for the density of A. The idea is that even with an imperfect start, this adaptive method ensures that each step moves us closer to a conclusion without getting stuck in a loop.

Emmy: And then there's the robustness part—they want to use the inverse theorem from Bhangale et al. to prove those noise stability results, which allows them to rule out specific algebraic configurations across different fields.

Kolya: That’s where it connects back to our earlier discussion on embeddings. So, by using that stability result robustly, they can rule out those embeddings into fields of different characteristics or even the same characteristic if the conditions are right.

Ada: Exactly. It allows them to prove that certain algebraic structures simply don't exist in the distribution they are looking at, which solidifies their density increment argument.

Emmy: It’s about using deep geometric theorems to make sure the probabilistic counting argument doesn't just give us a loose estimate, but one that is tightly constrained by the underlying algebraic geometry.

Kolya: So what does this mean for someone who just wants the practical bound? Does this adaptive method actually lead to a better number for n than the original bound involving k times iterated logarithms?

Ada: It’s still equivalent in terms of the final scaling, but it makes the path to get there more controlled. The new quantitative bounds they are aiming for, like those for k four and above, will be more reliable because the method is more adaptive.

Emmy: They’re essentially taking a solid theoretical result and making it operational—turning an abstract proof into a tool that can actually help you test sets in finite fields.

Kolya: So, the implication for me is that this paper shows how to use these heavy algebraic tools to get concrete, usable bounds on set sizes without needing perfect initial conditions every time. That’s a practical thing.

Conclusion: Ada: So, to wrap up this discussion on "Reasonable bounds for Restricted Polynomial Progressions in F n p," we’ve seen that they established a density bound involving k times iterated logarithms for larger k values.

Emmy: They did it by using noise stability results from an inverse theorem and a clever density increment argument on coordinate fibers. It showed that the structure of avoiding those patterns forces the set A to be sparser than we previously thought for higher degrees.

Kolya: I think what this paper does is show how these deep algebraic constraints translate into concrete, usable bounds for sets in finite fields.

Ada: Exactly. For k two and three, they have solid results that are already quite tight with Hales–Jewett or log log log n bounds, and for all larger k values, they give us a better inverse Ackermann type bound involving those iterated logarithms.

Emmy: It really is about making the machinery of algebraic geometry—like those embeddings into different characteristics—directly serve a probabilistic counting argument. That's the core structure here.

Kolya: What I’m thinking is that this work gives us a way to control the tail behavior of these progressions. The bounds they provide tell us exactly how fast that set size has to grow relative to n.

Ada: It’s a quantitative statement, Kolya, not just an existence proof. The number you get for n is what matters most when you’re trying to build something in a finite field without hitting these patterns.

Emmy: And the fact that they can rule out embeddings across different characteristics means this result holds up across more kinds of mathematical structures than just one specific field. That's quite broad.

Kolya: I agree, it’s solid because they aren't just giving a general statement; they are showing *how* the structure of the progression dictates the sparsity bound.

Ada: So, in short, "Reasonable bounds for Restricted Polynomial Progressions in F n p" gives us better density estimates for avoiding these specific polynomial sequences by combining noise stability with adaptive counting.

Emmy: It’s a great example of how geometric constraints can yield precise quantitative results in number theory.

Kolya: Next time, I want to see if they can push those bounds even further down, maybe closer to what they got for k two and three, or explore how this works with different types of random distributions.

Ada: We certainly will look at that next paper.

math.NT, math.CA, math.CO

Submitted: 2026-10-09

Updated: 2026-11-06

Comments: 35 pages. The paper is formalized, up to twos admit for the inverse Theorem 1.4, and a Theorem of Dimitrov at this URL https://github.com/lacey-gatech/restricted-polynomials-lean

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

Importance score: 90/100

The gist: Given an integer k ≥ 2 and a prime p large enough depending on k, we show that if A ⊆ F n p does not contain a restricted polynomial progression of the form x, x + y1, y2..., x + Pk−1(y)…

Key concepts

Restricted Polynomial Progression
This is a specific sequence structure within a set A, defined as x, x + P1(y), y2..., x + Pk-1(y), where the steps are determined by polynomials of degree up to k-1 in some variable y. The paper studies sets that do not contain such structures.
Density Increment Argument
This is a counting technique used in the proof. If a set A does not contain the forbidden progression, this argument shows that by looking at subsets (coordinate fibers), we can find smaller subsets with higher density than expected, leading to a contradiction unless the set is small.
Noise Stability Result
This is a key theorem from Bhangale et al. It states that if a distribution admits no nontrivial abelian embedding, it guarantees noise stability. This stability allows the researchers to perform the necessary density increment on coordinate fibers effectively.

Terminology

Summary

Given an integer k ≥ 2 and a prime p large enough depending on k, we show that if A ⊆ F n p does not contain a restricted polynomial progression of the form x, x + y1, y2. p. 0

Where the paper says it

REASONABLE BOUNDS FOR RESTRICTED POLYNOMIAL PROGRESSIONS IN F n p ALEX BURGIN, ANASTASIOS FRAGKOS, DAVID KRUZEL, MICHAEL LACEY, AND AMELIA STOKOLOSA Abstract. Given an integer k ≥ 2 and a prime p large enough depending on k, we show that, if A ⊆ F n p does not contain a restricted polynomial progression of the form x, x +   y1 y2 .

.., x + Pk−1(y), where x ∈ F n p and y ∈ Yn without⃗0 for some fixed Mk, then A must have density bounded above by C (log(kO(k)) n) c. p. 0
Where the paper says it

y k−1 n   , where x ∈ F n p and y ∈ {0, 2, 3, . , Mk} n \{⃗0}, for some fixed Mk, then A must have density bounded above by C (log(kO(k)) n) c , where C, c > 0 only depend on k and p.

The main result proves that for k ≥ 4, the bound improves from the previously known Hales–Jewett theorem bound to one involving k O(k) iterated logarithms. p. 3
Where the paper says it

There, to our knowledge, the best previously available bound came from the density Hales–Jewett theorem and was of inverse Ackermann type. 1 replaces it with a bound involving k O(k) iterated logarithms.

How the training signal is built

The proof of Theorem 1.1 relies on a density increment argument on coordinate fibers, which proceeds through four main steps. p. 3

Where the paper says it

Once one knows that µ admits no nontrivial abelian embedding, this theorem yields a density increment on a coordinate fiber. Such fibers preserve the form of the restricted configuration, and therefore allow the argument to be iterated.

These steps involve a counting distribution, showing that if no progression exists, the expected count is far below the random set prediction. p. 5
Where the paper says it

A k-tuple drawn from µ ⊗n is a restricted progression, and it is trivial exactly when every coordinate is diagonal, which has probability 2 −n . So if A has density α and contains no nontrivial progression, then Eµ⊗n Q j A(xj ) = α2 −n , which is far below the value α k predicted for a random set.

The second step involves ruling out nontrivial abelian embeddings using an inverse theorem from Bhangale, Khot, Liu and Minzer [Bha+242]. p. 4
Where the paper says it

Our proof of Theorem 1. 1 relies on an inverse theorem of Bhangale, Khot, Liu and Minzer [Bha+242, Theorem 1].

Where the gains come from

The core of the argument is Theorem 1.4 from Bhangale, Khot, Liu and Minzer [Bha+242], which states that a distribution admitting no nontrivial abelian embedding implies a noise stability result. p. 0

Where the paper says it

The proof uses a recent inverse theorem for noise stability of Bhangale, Khot, Liu and Minzer, which arose in the study of constraint satisfaction problems. The main new ingredient is a proof that the underlying distribution counting restricted polynomial progressions does not admit a nontrivial abelian embedding.

This stability allows for a density increment on a coordinate fiber. p. 4
Where the paper says it

Second, its conclusion concerns noise stability, a notion defined coordinate by coordinate. Noise stability converts directly into a large Efron–Stein weight at low degree, and then, by a random restriction, into a density increment on a coordinate fiber (Lemmas 6.

The iteration of this process, enabled by the inclusion of y = 0 in the set Y, leads to a bound on n that is equivalent to Theorem 1. p. 5
Where the paper says it

Step 4: iteration. Because 0 ∈ Y , a fiber of a set without nontrivial progressions again has none (Lemma 6.

1.

Excluding embeddings into different characteristics

The paper rigorously demonstrates that the configuration admits no nontrivial abelian embedding into finite fields of different characteristics. This is achieved by analyzing the matrix equation Al,M(λ) in characteristic q ≠ p and showing its rank is full, which implies triviality of the embedding. p. 5

Where the paper says it

When q = p, the operator T is unipotent, and a Vandermonde determinant shows that these equations force every fj to be constant. When q ̸= p, we diagonalize T and must show that a matrix Aℓ,M(λ) = (λ y j − 1)y,j has full rank at every root of unity λ of order p in characteristic q.

Quantitative bounds for existing cases

For k = 2, a density Hales–Jewett (DHJ) argument applies, yielding a bound of A p n ≪ n − 1/2. For k = 3, the result follows from work by Bhangale, Khot, Liu and Minzer [Bha+241], giving a bound of A p n ≪ (log log log n) c. p. 6

Where the paper says it

and yields |A| p n ≪ n −1/2 . • For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241].

The general case for k ≥ 4 is improved from the inverse Ackermann type bound to one involving k O(k) iterated logarithms. p. 2
Where the paper says it

were of inverse Ackermann type, |A| pn ≤ O √ 1 log∗ n . The result of [Bha+241] was thus the first reasonable bound for this problem, meaning one involving only a bounded number of iterated logarithms.

p. 2
Where the paper says it

were of inverse Ackermann type, |A| pn ≤ O √ 1 log∗ n . The result of [Bha+241] was thus the first reasonable bound for this problem, meaning one involving only a bounded number of iterated logarithms.

p. 2
Where the paper says it

were of inverse Ackermann type, |A| pn ≤ O √ 1 log∗ n . The result of [Bha+241] was thus the first reasonable bound for this problem, meaning one involving only a bounded number of iterated logarithms.

p. 2
Where the paper says it

were of inverse Ackermann type, |A| pn ≤ O √ 1 log∗ n . The result of [Bha+241] was thus the first reasonable bound for this problem, meaning one involving only a bounded number of iterated logarithms.

p. 2
Where the paper says it

were of inverse Ackermann type, |A| pn ≤ O √ 1 log∗ n . The result of [Bha+241] was thus the first reasonable bound for this problem, meaning one involving only a bounded number of iterated logarithms.

p. 2
Where the paper says it

were of inverse Ackermann type, |A| pn ≤ O √ 1 log∗ n . The result of [Bha+241] was thus the first reasonable bound for this problem, meaning one involving only a bounded number of iterated logarithms.

p. 2
Where the paper says it

were of inverse Ackermann type, |A| pn ≤ O √ 1 log∗ n . The result of [Bha+241] was thus the first reasonable bound for this problem, meaning one involving only a bounded number of iterated logarithms.

p. 2
Where the paper says it

were of inverse Ackermann type, |A| pn ≤ O √ 1 log∗ n . The result of [Bha+241] was thus the first reasonable bound for this problem, meaning one involving only a bounded number of iterated logarithms.

Existing quantitative results for this configuration

The existing quantitative results confirm that for k = 2, a density Hales–Jewett (DHJ) argument applies, yielding A p n ≪ n − 1/2. For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241], giving a bound of A p n ≪ (log log log n) c. p. 6

Where the paper says it

and yields |A| p n ≪ n −1/2 . • For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241].

p. 6
Where the paper says it

and yields |A| p n ≪ n −1/2 . • For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241].

p. 6
Where the paper says it

and yields |A| p n ≪ n −1/2 . • For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241].

p. 6
Where the paper says it

and yields |A| p n ≪ n −1/2 . • For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241].

p. 6
Where the paper says it

and yields |A| p n ≪ n −1/2 . • For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241].

p. 6
Where the paper says it

and yields |A| p n ≪ n −1/2 . • For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241].

p. 6
Where the paper says it

and yields |A| p n ≪ n −1/2 . • For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241].

The general case for k ≥ 4 is improved from the inverse Ackermann type bound to one involving k O(k) iterated logarithms. The paper confirms that for k = 2, DHJ reduces to Sperner’s theorem, which has very good quantitative bounds and yields A p n ≪ n − 1/2. p. 5
Where the paper says it

• For k = 2, a density Hales–Jewett (DHJ) argument, described below for k ≥ 4, applies. For k = 2, DHJ reduces to Sperner’s theorem, which has very good quantitative bounds, 6

p. 5
Where the paper says it

• For k = 2, a density Hales–Jewett (DHJ) argument, described below for k ≥ 4, applies. For k = 2, DHJ reduces to Sperner’s theorem, which has very good quantitative bounds, 6

p. 5
Where the paper says it

• For k = 2, a density Hales–Jewett (DHJ) argument, described below for k ≥ 4, applies. For k = 2, DHJ reduces to Sperner’s theorem, which has very good quantitative bounds, 6

p. 5
Where the paper says it

• For k = 2, a density Hales–Jewett (DHJ) argument, described below for k ≥ 4, applies. For k = 2, DHJ reduces to Sperner’s theorem, which has very good quantitative bounds, 6

p. 5
Where the paper says it

• For k = 2, a density Hales–Jewett (DHJ) argument, described below for k ≥ 4, applies. For k = 2, DHJ reduces to Sperner’s theorem, which has very good quantitative bounds, 6

p. 5
Where the paper says it

• For k = 2, a density Hales–Jewett (DHJ) argument, described below for k ≥ 4, applies. For k = 2, DHJ reduces to Sperner’s theorem, which has very good quantitative bounds, 6

For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241], giving a bound of A p n ≪ (log log log n) c. The general case for k ≥ 4 is improved from the inverse Ackermann type bound to one involving k O(k) iterated logarithms. The paper confirms that for k = 2, DHJ reduces to Sperner’s theorem, which has very good quantitative bounds and yields A p n ≪ n − 1/2. For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241], giving a bound of A p n ≪ (log log log n) c. The general case for k ≥ 4 is improved from the inverse Ackermann type bound to one involving k O(k) iterated logarithms. The paper confirms that for k = 2, DHJ reduces to Sperner’s theorem, which has very good quantitative bounds and yields A p n ≪ n − 1/2. For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241], giving a bound of A p n ≪ (log log log n) c. The general case for k ≥ 4 is improved from the inverse Ackermann type bound to one involving k O(k) iterated logarithms. The paper confirms that for k = 2, DHJ reduces to Sperner’s theorem, which has very good quantitative bounds and yields A p n ≪ n − 1/2. For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241], giving a bound of A p n ≪ (log log log n) c. The general case for k ≥ 4 is improved from the inverse Ackermann type bound to one involving k O(k) iterated logarithms. The paper confirms that for k = 2, DHJ reduces to Sperner’s theorem, which has very good quantitative bounds and yields A p n ≪ n − 1/2. For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241], giving a bound of A p n ≪ (log log log n) c. The general case for k ≥ 4 is improved from the inverse Ackermann type bound to one involving k O(k) iterated logarithms. The paper confirms that for k = 2, DHJ reduces to Sperner’s theorem, which has very good quantitative bounds and yields A p n ≪ n − 1/2. For k = 3, the result follows from work of Bhangale, Khot, Liu and Minzer [Bha+241], giving a bound of A p n ≪ (log log log n) c. The general case for k ≥ 4 is improved from the inverse Ackermann type bound to one involving k O(k) iterated logarithms.

The main result

Theorem 1.1 states that there is K = k O(k) such that if n > exp(K), then for every prime p ≥ Pk, if A p n ≥ C (log(K) n) c, then A contains a nontrivial restricted k-term polynomial progression x, x+P1(y),. p. 2

Where the paper says it

There is K = k O(k) such that for every prime p ≥ Pk there exist C = C(k, p) > 0 and c = c(k, p) > 0 with the following property. If n > exp(K) (1) and A ⊆ F n p satisfies |A| p n ≥ C log(K) n c , then A contains a nontrivial restricted k-term polynomial progression x, x+P1(y), .

.., x+Pk−1(y) with y ∈ Yn without⃗0. p. 3
Where the paper says it

, x + Pk−1(y) in that coordinate shows that they are pairwise distinct. Without this condition a “nontrivial” progression could collapse to fewer than k points.

Remark 3.3

The support of µ cannot be taken smaller by our argument, as the proofs use every value y ∈ Yn: the value y = 0 eliminates f0, and the values y ∈ Yn without⃗0 supply the rows of the matrices Al,M that appear below.

Remark 6.5

Lemma 6.4 is the reason 0 is included in Y: coordinates frozen by a restriction are filled in with the step yi = 0. p. 2

Where the paper says it

The value y = 1 is excluded because it collapses the progression: x + 1j = x + 1 for every j, so a step with coordinates in {0, 1} produces only two distinct points. The value y = 0 is included for two reasons.

Lemma 5.9

Lemma 5.9 shows that if f0,. p. 3

Where the paper says it

Comparing the points x, x + P1(y), . , x + Pk−1(y) in that coordinate shows that they are pairwise distinct.

p. 3
Where the paper says it

Comparing the points x, x + P1(y), . , x + Pk−1(y) in that coordinate shows that they are pairwise distinct.

p. 3
Where the paper says it

Comparing the points x, x + P1(y), . , x + Pk−1(y) in that coordinate shows that they are pairwise distinct.

.., fl satisfy (5. p. 4
Where the paper says it

[Bha+242, Theorem 1] Let k be a positive integer and let µ be a distribution over Σ1 × · · · × Σk that admits no nontrivial abelian embedding, and in which the probability of each atom is at least γ. Then, for every ϵ > 0 there are δ := δ(γ, ϵ) > 0 and N0 = N0(γ, ϵ) such that for every n ≥ N0, if 1-bounded functions fi : Σn i → C satisfy E (x1, .

p. 4
Where the paper says it

[Bha+242, Theorem 1] Let k be a positive integer and let µ be a distribution over Σ1 × · · · × Σk that admits no nontrivial abelian embedding, and in which the probability of each atom is at least γ. Then, for every ϵ > 0 there are δ := δ(γ, ϵ) > 0 and N0 = N0(γ, ϵ) such that for every n ≥ N0, if 1-bounded functions fi : Σn i → C satisfy E (x1, .

p. 4
Where the paper says it

[Bha+242, Theorem 1] Let k be a positive integer and let µ be a distribution over Σ1 × · · · × Σk that admits no nontrivial abelian embedding, and in which the probability of each atom is at least γ. Then, for every ϵ > 0 there are δ := δ(γ, ϵ) > 0 and N0 = N0(γ, ϵ) such that for every n ≥ N0, if 1-bounded functions fi : Σn i → C satisfy E (x1, .

p. 4
Where the paper says it

[Bha+242, Theorem 1] Let k be a positive integer and let µ be a distribution over Σ1 × · · · × Σk that admits no nontrivial abelian embedding, and in which the probability of each atom is at least γ. Then, for every ϵ > 0 there are δ := δ(γ, ϵ) > 0 and N0 = N0(γ, ϵ) such that for every n ≥ N0, if 1-bounded functions fi : Σn i → C satisfy E (x1, .

p. 4
Where the paper says it

[Bha+242, Theorem 1] Let k be a positive integer and let µ be a distribution over Σ1 × · · · × Σk that admits no nontrivial abelian embedding, and in which the probability of each atom is at least γ. Then, for every ϵ > 0 there are δ := δ(γ, ϵ) > 0 and N0 = N0(γ, ϵ) such that for every n ≥ N0, if 1-bounded functions fi : Σn i → C satisfy E (x1, .

p. 4
Where the paper says it

[Bha+242, Theorem 1] Let k be a positive integer and let µ be a distribution over Σ1 × · · · × Σk that admits no nontrivial abelian embedding, and in which the probability of each atom is at least γ. Then, for every ϵ > 0 there are δ := δ(γ, ϵ) > 0 and N0 = N0(γ, ϵ) such that for every n ≥ N0, if 1-bounded functions fi : Σn i → C satisfy E (x1, .

1) and q ≠ p, then fj is constant for every j = 0, 1,. p. 4
Where the paper says it

, ak) ∈ S =⇒ X k i=1 σi(ai) = 0G. The embedding is trivial if every σi is constant, and nontrivial otherwise.

p. 4
Where the paper says it

, ak) ∈ S =⇒ X k i=1 σi(ai) = 0G. The embedding is trivial if every σi is constant, and nontrivial otherwise.

p. 4
Where the paper says it

, ak) ∈ S =⇒ X k i=1 σi(ai) = 0G. The embedding is trivial if every σi is constant, and nontrivial otherwise.

p. 4
Where the paper says it

, ak) ∈ S =⇒ X k i=1 σi(ai) = 0G. The embedding is trivial if every σi is constant, and nontrivial otherwise.

p. 4
Where the paper says it

, ak) ∈ S =⇒ X k i=1 σi(ai) = 0G. The embedding is trivial if every σi is constant, and nontrivial otherwise.

p. 4
Where the paper says it

, ak) ∈ S =⇒ X k i=1 σi(ai) = 0G. The embedding is trivial if every σi is constant, and nontrivial otherwise.

.., l.

Lemma 5.7

Lemma 5.7 shows that the minor ∆(z):= det z y r − 1 1≤r,j≤l is monic of degree Pl r=1 y r r in Z[z]. p. 3

Where the paper says it

Comparing the points x, x + P1(y), . , x + Pk−1(y) in that coordinate shows that they are pairwise distinct.

Lemma 5.8

Lemma 5.8 shows that there is a positive integer cl depending only on l, with the following property: Suppose q N is prime and that λ ∈ F × q is a common root of ∆(MS1),. p. 2

Where the paper says it

1); these depend only on k. There is K = k O(k) such that for every prime p ≥ Pk there exist C = C(k, p) > 0 and c = c(k, p) > 0 with the following property.

.., ∆(MSt), then λ cl = 1.

Lemma 5.5

Lemma 5.5 shows that the matrix Al,M(θ) has rank less than l if and only if Al,∞(θ) has rank less than l. p. 5

Where the paper says it

When q = p, the operator T is unipotent, and a Vandermonde determinant shows that these equations force every fj to be constant. When q ̸= p, we diagonalize T and must show that a matrix Aℓ,M(λ) = (λ y j − 1)y,j has full rank at every root of unity λ of order p in characteristic q.

Proof of Theorem 1. p. 0

Where the paper says it

For k ≥ 4, the best previously known bound came from the density Hales–Jewett theorem and was of inverse Ackermann type. The proof uses a recent inverse theorem for noise stability of Bhangale, Khot, Liu and Minzer, which arose in the study of constraint satisfaction problems.

1

The proof of Theorem 1.1 proceeds by iteration using Lemma 6. p. 5

Where the paper says it

Step 4: iteration. Because 0 ∈ Y , a fiber of a set without nontrivial progressions again has none (Lemma 6.

6 to show that the density can be incremented at each step until it exceeds 1, which implies termination. p. 1
Where the paper says it

A restricted 3-AP in F n p is a three-term arithmetic progression x, x + a, x + 2a with x ∈ F n p and a ∈ {0, 1} n\{⃗0}. They show that if A ⊆ F n p has density |A| pn ≥ Cp (log log log n) cp , then A contains a restricted 3-AP.

The final quantitative bound obtained is n < exp(K+2) α0 Ck − Oµ(k)! p. 1
Where the paper says it

, x + y m+k−1 for various choices of k, m ∈ N. He later built upon a PET induction argument, a degree-lowering method, a quantitative concatenation result for averages of box norms over finite abelian groups, and a box norm smoothing technique to establish a multi-dimensional result in [Kuc241, Kuc242] extending a previously obtained power savings bound for sets lacking the polynomial configuration (x1, x2),(x1 + y, x2),(x1, x2 + y 2 ) in F 2 p by Han, Lacey, and Yang in [HLY21].

, which is equivalent to Theorem 1. p. 5
Where the paper says it

4 before that happens. This bounds n by a tower of height k O(k) in 1/α, which is equivalent to Theorem 1.

1.

Proof of Proposition 5. p. 2

Where the paper says it

Fix k ≥ 2. Let M(·) and P(·) be the functions provided by Proposition 5.

p. 2
Where the paper says it

Fix k ≥ 2. Let M(·) and P(·) be the functions provided by Proposition 5.

p. 2
Where the paper says it

Fix k ≥ 2. Let M(·) and P(·) be the functions provided by Proposition 5.

p. 2
Where the paper says it

Fix k ≥ 2. Let M(·) and P(·) be the functions provided by Proposition 5.

p. 2
Where the paper says it

Fix k ≥ 2. Let M(·) and P(·) be the functions provided by Proposition 5.

2

The proof of Proposition 5. p. 2

Where the paper says it

Fix k ≥ 2. Let M(·) and P(·) be the functions provided by Proposition 5.

p. 2
Where the paper says it

Fix k ≥ 2. Let M(·) and P(·) be the functions provided by Proposition 5.

2 shows that if Al,M(λ) has rank less than l, then λ is a root of unity or zero. p. 5
Where the paper says it

When q ̸= p, we diagonalize T and must show that a matrix Aℓ,M(λ) = (λ y j − 1)y,j has full rank at every root of unity λ of order p in characteristic q. This is done in characteristic zero first, using Kronecker’s theorem.

This is achieved by analyzing the roots of the generating minors D(z) and using Lemma 5. p. 0
Where the paper says it

Following Bergelson and Leibman’s foundational work on the so-called polynomial Szemerédi theorem, considerable effort has been devoted to obtaining quantitative versions of this qualitative result. In the finite field setting, Bourgain and Chang [BC17] first established a quantitative nonlinear Roth theorem using Fourier-analytic techniques and exponential sum estimates.

6 to show that if q ≠ p, then λ m = 1 for some m ∈ El. p. 0
Where the paper says it

REASONABLE BOUNDS FOR RESTRICTED POLYNOMIAL PROGRESSIONS IN F n p ALEX BURGIN, ANASTASIOS FRAGKOS, DAVID KRUZEL, MICHAEL LACEY, AND AMELIA STOKOLOSA Abstract. Given an integer k ≥ 2 and a prime p large enough depending on k, we show that, if A ⊆ F n p does not contain a restricted polynomial progression of the form x, x +   y1 y2 .

Proof of Proposition 3. p. 2

Where the paper says it

Fix k ≥ 2. Let M(·) and P(·) be the functions provided by Proposition 5.

2

The proof of Proposition 3.2 shows that if the distribution admits a nontrivial abelian embedding, it must admit one into (Fp, +) or (Fq, +) for some prime q. p. 9

Where the paper says it

Suppose µ is a probability distribution on a finite set Σ0 × Σ1 × · · · × Σℓ which admits a nontrivial abelian embedding into some abelian group. Then there exists a prime q for which µ admits a nontrivial abelian embedding into the cyclic group (Z/qZ, +).

This is achieved by showing that either Lemma 4. p. 1
Where the paper says it

if A ⊆ [N] contains no non-trivial polynomial progression of the form x, x + y, x + y 2 , then |A| ≪ N (log N) c . Peluse [Pel20] extended the result to longer progressions by showing that given polynomials P1, .

1 or Lemma 5. p. 2
Where the paper says it

, x) in the support of the underlying distribution are what allow us to eliminate one of the functions when ruling out abelian embeddings. Second, freezing a coordinate by taking yi = 0 is what makes the configuration stable under passing to coordinate fibers (Lemma 6.

9 applies to show the embedding is trivial. p. 4
Where the paper says it

The theorem applies to a notably broad class of distributions µ, extending earlier work of Mossel [Mos10] on so-called connected distributions. 1 To state the inverse theorem, we require the concept of an abelian embedding.

Proof of Theorem 5

The proof of Theorem 5 shows that if f0,. p. 6

Where the paper says it

This set is the support of the distribution µ used in our proof. Taking t = 0 shows that R contains the diagonal.

.., fl satisfy (5.1) and q ≠ p, then fj is constant for every j = 0, 1,.., l. This is achieved by analyzing the matrix equation Al,M(λ) in characteristic q ≠ p and showing its rank is full. p. 5
Where the paper says it

When q = p, the operator T is unipotent, and a Vandermonde determinant shows that these equations force every fj to be constant. When q ̸= p, we diagonalize T and must show that a matrix Aℓ,M(λ) = (λ y j − 1)y,j has full rank at every root of unity λ of order p in characteristic q.

p. 5
Where the paper says it

When q = p, the operator T is unipotent, and a Vandermonde determinant shows that these equations force every fj to be constant. When q ̸= p, we diagonalize T and must show that a matrix Aℓ,M(λ) = (λ y j − 1)y,j has full rank at every root of unity λ of order p in characteristic q.

p. 5
Where the paper says it

When q = p, the operator T is unipotent, and a Vandermonde determinant shows that these equations force every fj to be constant. When q ̸= p, we diagonalize T and must show that a matrix Aℓ,M(λ) = (λ y j − 1)y,j has full rank at every root of unity λ of order p in characteristic q.

The proof of Theorem 5 shows that if f0,..., fl satisfy (5.1) and q ≠ p, then fj is constant for every j = 0, 1,.., l.

The proof of Theorem 5 shows that if f0,..., fl satisfy (5.1) and q ≠ p, then fj is constant for every j = 0, 1,.., l. This is achieved by analyzing the matrix equation Al,M(λ) in characteristic q ≠ p and showing its rank is full.

Proof of Proposition 5.3

The proof of Proposition 5.3 shows that if q ≠ N, then H1 V1 +. p. 3

Where the paper says it

Comparing the points x, x + P1(y), . , x + Pk−1(y) in that coordinate shows that they are pairwise distinct.

p. 3
Where the paper says it

Comparing the points x, x + P1(y), . , x + Pk−1(y) in that coordinate shows that they are pairwise distinct.

p. 3
Where the paper says it

Comparing the points x, x + P1(y), . , x + Pk−1(y) in that coordinate shows that they are pairwise distinct.

.. + Ht Vt = N in Fq[z]. This is achieved by analyzing the identity (5.3) and showing that no common root exists, which implies D(λ) = 0. p. 1
Where the paper says it

if A ⊆ [N] contains no non-trivial polynomial progression of the form x, x + y, x + y 2 , then |A| ≪ N (log N) c . Peluse [Pel20] extended the result to longer progressions by showing that given polynomials P1, .

p. 1
Where the paper says it

if A ⊆ [N] contains no non-trivial polynomial progression of the form x, x + y, x + y 2 , then |A| ≪ N (log N) c . Peluse [Pel20] extended the result to longer progressions by showing that given polynomials P1, .

Proof of Proposition 5.9

The proof of Proposition 5.9 shows that if f0,..., fl satisfy (5.1) and q ≠ p, then fj is constant for every j = 0, 1,.., l. This is achieved by analyzing the matrix equation Al,M(λ) in characteristic q ≠ p and showing its rank is full. The proof of Proposition 5.9 shows that if f0,..., fl satisfy (5.1) and q ≠ p, then fj is constant for every j = 0, 1,.., l.

The proof of Proposition 5.3 shows that if q ≠ N, then H1 V1 +... + Ht Vt = N in Fq[z]. This is achieved by analyzing the identity (5.3) and showing that no common root exists, which implies D(λ) = 0. The proof of Proposition 5.3 shows that if q ≠ N, then H1 V1 +... + Ht Vt = N in Fq[z].

**Proof of Proposition 5.

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. Adaptive density increment for restricted polynomial progressions in high-dimensional spaces: The system can determine if a set A in F n p contains a nontrivial restricted k-term polynomial progression by iteratively finding subsets S with size at least n 2d and then constructing a subset AS to have density at least alpha plus delta 32, where delta is derived from the initial density and k.

  2. Robust detection of complex geometric structures via noise stability analysis: The AI can use the inverse theorem of Bhangale, Khot, Liu and Minzer to prove that certain distributions admit no nontrivial abelian embedding into finite fields with different characteristics or the same characteristic, allowing it to rule out specific algebraic configurations in the data.

  3. Quantitative bounds for sparse polynomial progressions: The system can provide explicit bounds on the size of a set A lacking restricted k-term polynomial progressions, such as A pn bounded by C (log(k O(k)) n) c, which is superior to previous inverse Ackermann type bounds for k >= 4.

Abstract

Given an integer k at least 2, there are integers M k and P k so that for all A F n p does not contain a restricted polynomial progression of the form x, x+ y 1 y 2 y n , x+ y 1 squared y 2 squared y n squared ,, x+ y 1 k-1 y 2 k-1 y n k-1 , where x in F n p, with p>P k, and y in 0,2, 3,, M k n 0 vector, for some fixed M k, then A must have density bounded above by C over((k O(k)) n) c, where C, c>0 only depend on k and p. For k at least 4, the best previously known bound came from the density Hales--Jewett theorem and was of inverse Ackermann type. The proof uses a recent inverse theorem for noise stability of Bhangale, Khot, Liu and Minzer, which arose in the study of constraint satisfaction problems. The main new ingredient is a proof that the underlying distribution counting restricted polynomial progressions does not admit a nontrivial abelian embedding, by way of an involved algebraic argument. Reasonable bounds are provided for P k and M k.

Sources

Related papers