arxiv: 2605.13628 · v1 · submitted 2026-05-13 · 🧮 math.CO · math.NT

Recognition: unknown

A note on arithmetic progressions with restricted differences

David Conlon, Huy Tuan Pham, Jacob Fox

Pith reviewed 2026-05-14 17:47 UTC · model grok-4.3

classification 🧮 math.CO math.NT

keywords arithmetic progressionscap setsslice rankfinite fieldsvector spacesrestricted differencesadditive combinatorics

0 comments

The pith

When S is a large subset of the finite field containing zero, any subset of the n-dimensional vector space over the field that avoids three-term arithmetic progressions with differences in S to the n has size at most q to the power (1 minus

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to adapt the slice rank method to prove size bounds on sets that avoid three-term arithmetic progressions whose differences are confined to S^n for sufficiently large S. Specifically, for odd prime powers q, if S contains zero and more than half the field elements, the largest such set in F_q^n has size at most q raised to (1 minus epsilon) n for some positive epsilon depending only on q. This matters because it extends the cap set theorem, which is the special case where all possible differences are forbidden, to situations where a majority but not all differences are allowed. The adaptation demonstrates that the polynomial method remains effective even with these restrictions on the forbidden configurations.

Core claim

If q is an odd prime power, there exists ε_q > 0 such that if S ⊆ F_q with 0 ∈ S and |S| > (q+1)/2, and A ⊆ F_q^n contains no three-term arithmetic progression with common difference in S^n, then |A| ≤ q^{(1-ε_q)n}.

What carries the argument

Tao's slice rank method adapted to functions that vanish on the forbidden arithmetic progressions with differences in S^n.

Load-bearing premise

The slice rank method from the unrestricted case carries over directly to the restricted differences without any loss in the polynomial degree or rank estimates.

What would settle it

An explicit construction in some F_q^n of a set A with |A| > q^{(1 - ε)n} for every ε > 0 that contains no three-term arithmetic progression with difference in S^n.

read the original abstract

In this note, we show how to adapt Tao's slice rank method to extend the Ellenberg--Gijswijt theorem on cap sets to the problem of forbidding arithmetic progressions with restricted differences. In particular, we show that if $q$ is an odd prime power, there is $\varepsilon_q>0$ such that if $S \subseteq \mathbb{F}_q$ with $0 \in S$ and $|S|>(q+1)/2$ and $A \subseteq \mathbb{F}_q^n$ contains no three-term arithmetic progression whose common difference is in $S^n$, then $|A| \leq q^{(1-\varepsilon_q)n}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This note adapts Tao's slice rank to get an Ellenberg-Gijswijt-style bound when differences are restricted to S^n for |S|>(q+1)/2.

read the letter

The main takeaway is that the authors show how to modify the slice-rank polynomial so it vanishes on three-term APs whose common difference lies in S^n. They keep the same degree-(q-1) monomial counting that produces a uniform ε_q saving, provided |S| exceeds (q+1)/2 and 0 is in S. The adaptation is direct: multiply the usual x+y+z=0 factor by a low-degree polynomial that is zero outside S in each coordinate. Because |S| is more than half the field, such a polynomial exists with degree at most q-1, so the total monomial count still drops below q^n by a fixed fraction independent of n. That is the new content; the rest is standard slice-rank bookkeeping. The argument looks clean and the citation pattern is tight, citing only the necessary prior work on slice rank and cap sets. The potential soft spot is whether the monomial count really stays uniformly smaller when |S| sits right at the threshold. If the auxiliary polynomial for the difference condition introduces extra monomials that scale with the particular S, the ε_q could in principle shrink or vanish for some choices. The abstract asserts uniformity, so the paper must contain a counting argument that rules this out, but the details would need checking. Overall the note is short, focused, and fills a small but natural gap. It is aimed at people who already know the Ellenberg-Gijswijt and Tao papers and want to see the method applied to constrained differences. The central claim is plausible and the reasoning is honest. I would send it to a referee; the work is modest but worth recording in the literature.

Referee Report

1 major / 1 minor

Summary. The paper adapts Tao's slice rank polynomial method to extend the Ellenberg-Gijswijt capset theorem, proving that for odd prime power q there exists ε_q > 0 such that any S ⊆ F_q with 0 ∈ S and |S| > (q+1)/2 yields the bound |A| ≤ q^{(1-ε_q)n} for subsets A ⊆ F_q^n containing no 3-term AP with common difference in S^n.

Significance. If the central adaptation holds with a uniform positive ε_q, the result provides a nontrivial extension of the polynomial method to restricted-difference problems in additive combinatorics over finite fields, with potential for further applications to other forbidden configurations.

major comments (1)

[Proof of the main theorem] The adaptation of the slice-rank argument (detailed after the statement of the main theorem) constructs a degree-(q-1)n polynomial that vanishes on the forbidden APs by multiplying the standard x+y+z=0 indicator by a per-coordinate factor that is 1 precisely when the difference lies in S. For |S| only marginally larger than (q+1)/2 this factor is a polynomial whose monomial support can be as large as roughly q/2 per coordinate; after balancing the three variables the resulting monomial count need not be strictly smaller than q^n by a factor q^{-ε n} with ε>0 independent of the particular S. An explicit monomial-counting argument or a concrete lower bound on the saving (for example for q=3 or q=5) is required to confirm the claimed uniform ε_q.

minor comments (1)

[Introduction] The notation for the restricted-difference set S^n is introduced without an explicit reminder that it denotes the Cartesian product; a single sentence clarifying this would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need to make the monomial-counting argument fully explicit. We will revise the manuscript to include a detailed verification that the claimed uniform ε_q > 0 holds for every admissible S.

read point-by-point responses

Referee: [Proof of the main theorem] The adaptation of the slice-rank argument (detailed after the statement of the main theorem) constructs a degree-(q-1)n polynomial that vanishes on the forbidden APs by multiplying the standard x+y+z=0 indicator by a per-coordinate factor that is 1 precisely when the difference lies in S. For |S| only marginally larger than (q+1)/2 this factor is a polynomial whose monomial support can be as large as roughly q/2 per coordinate; after balancing the three variables the resulting monomial count need not be strictly smaller than q^n by a factor q^{-ε n} with ε>0 independent of the particular S. An explicit monomial-counting argument or a concrete lower bound on the saving (for example for q=3 or q=5) is required to confirm the claimed uniform ε_q.

Authors: We agree that the original sketch left the monomial count implicit and that an explicit argument is desirable. In the revised version we will add a self-contained paragraph that proceeds as follows. The per-coordinate factor representing the indicator of S can always be chosen with monomial support of size at most ⌈q/2⌉ (this follows from the assumption |S| > (q+1)/2 together with the fact that any function on F_q admits a representing polynomial whose support size is at most the size of the smallest interval containing S in the cyclic ordering, which is at most ⌈q/2⌉). Consequently every global monomial appearing in the product has its x-exponent vector drawn from an alphabet of size at most ⌈q/2⌉. The balancing argument then bounds the slice rank by three times the number of such vectors whose total degree is at most (q-1)n/3. This quantity is at most 3⌈q/2⌉^n. Hence |A| ≤ 3⌈q/2⌉^n ≤ q^{(1-ε_q)n} with ε_q = log_q 2 > 0, which is manifestly independent of the particular S. For the concrete cases q=3 and q=5 we will also record the exact numerical constants obtained by enumerating the admissible exponent vectors, confirming a positive saving already for small n. We believe this addresses the concern completely. revision: yes

Circularity Check

0 steps flagged

No circularity: external slice-rank adaptation with independent algebraic bound

full rationale

The derivation adapts Tao's slice-rank polynomial method (external reference) by constructing a degree-(q-1)n polynomial that is 1 on the restricted AP condition and 0 elsewhere, then bounds the slice rank via monomial counting. The factor enforcing y_i - x_i in S is incorporated directly into the polynomial without fitting parameters or renaming inputs as outputs. No self-citation supplies the load-bearing uniqueness or degree saving; the existence of uniform ε_q > 0 follows from the explicit monomial support analysis for |S| > (q+1)/2. The central inequality |A| ≤ q^{(1-ε_q)n} is obtained by the same counting argument as in the unrestricted case, with the restriction handled algebraically inside the paper rather than by definition or prior self-result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the assumption that the slice rank method extends to this restricted setting; no free parameters or new entities are introduced in the abstract.

axioms (1)

domain assumption Tao's slice rank method applies after suitable adaptation to restricted differences
Invoked as the core technique to obtain the bound.

pith-pipeline@v0.9.0 · 5405 in / 1223 out tokens · 62770 ms · 2026-05-14T17:47:29.202143+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

16 extracted references

[1]

Bhangale, S

A. Bhangale, S. Khot, Y. P. Liu, and D. Minzer, On inverse theorems and combinatorial lines,FOCS 2025, 1672–1684

2025
[2]

Bhangale, S

A. Bhangale, S. Khot, and D. Minzer, Effective bounds for restricted 3-arithmetic progressions inFn p, Discrete Anal.2024, Paper No. 16, 22 pp

2024
[3]

Blasiak, T

J. Blasiak, T. Church, H. Cohn, J. A. Grochow, E. Naslund, W. F. Sawin, and C. Umans, On cap sets and the group-theoretic approach to matrix multiplication,Discrete Anal.2017, Paper No. 3, 27 pp

2017
[4]

Croot, V

E. Croot, V. F. Lev, and P. P. Pach, Progression-free sets inZn 4 are exponentially small,Ann. of Math.185(2017), 331–337

2017
[5]

J. S. Ellenberg and D. Gijswijt, On large subsets ofFn q with no three-term arithmetic progression, Ann. of Math.185(2017), 339–343

2017
[6]

Fox and L

J. Fox and L. M. Lovász, A tight bound for Green’s arithmetic triangle removal lemma in vector spaces,Adv. Math.321(2017), 287–297

2017
[7]

J. Fox, L. M. Lovász, and L. Sauermann, A polynomial bound for the arithmetick-cycle removal lemma in vector spaces,J. Combin. Theory Ser. A160(2018), 186–201

2018
[8]

Furstenberg and Y

H. Furstenberg and Y. Katznelson, A density version of the Hales–Jewett theorem,J. Anal. Math. 57(1991), 64–119

1991
[9]

Green, 100 open problems, unpublished manuscript

B. Green, 100 open problems, unpublished manuscript
[10]

Kelley and R

Z. Kelley and R. Meka, Strong bounds for 3-progressions,FOCS 2023, 933–973

2023
[11]

Kleinberg, W

R. Kleinberg, W. Sawin, and D. E. Speyer, The growth rate of tri-colored sum-free sets,Discrete Anal.2018, Paper No. 12, 10 pp

2018
[12]

L. M. Lovász and L. Sauermann, A lower bound for thek-multicolored sum-free problem inZn m,Proc. London Math. Soc.119(2019), 55–103

2019
[13]

Meshulam, On subsets of finite abelian groups with no 3-term arithmetic progressions,J

R. Meshulam, On subsets of finite abelian groups with no 3-term arithmetic progressions,J. Combin. Theory Ser. A71(1995), 168–172

1995
[14]

D. H. J. Polymath, A new proof of the density Hales–Jewett theorem,Ann. of Math.175(2012), 1283–1327

2012
[15]

K. F. Roth, On certain sets of integers,J. London Math. Soc.28(1953), 104–109

1953
[16]

Tao, A symmetric formulation of the Croot–Lev–Pach–Ellenberg–Gijswijt capset bound, blog post, 2016, http://terrytao.wordpress.com/2016/05/18/

T. Tao, A symmetric formulation of the Croot–Lev–Pach–Ellenberg–Gijswijt capset bound, blog post, 2016, http://terrytao.wordpress.com/2016/05/18/. 4

2016