Arithmetic Progression-Free Subset-Sum Sets

Samuel Korsky

arxiv: 2606.24139 · v1 · pith:6O42BJ5Bnew · submitted 2026-06-23 · 🧮 math.CO

Arithmetic Progression-Free Subset-Sum Sets

Samuel Korsky This is my paper

Pith reviewed 2026-06-26 00:09 UTC · model grok-4.3

classification 🧮 math.CO

keywords subset sumsarithmetic progressionsErdős–Sárközy problemcentral trinomial coefficientsternary grid bandwidthcarry-free digit constructionsexponential growth rates

0 comments

The pith

The smallest N for an n-element set whose subset sums avoid 3-term APs equals the bandwidth of the ternary grid and is asymptotically (√3/(2√π)) 3^n / √n.

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

The paper defines g_k(n) as the least N such that some n-element A inside [N] has all its subset sums free of nonconstant k-term arithmetic progressions. For the case k=3 it shows this minimal N is at least the bandwidth of the ternary grid, which is exactly (T_n-1)/2 plus the sum of the first n central trinomial coefficients T_j. This quantity is asymptotically (√3/(2√π) + o(1)) 3^n / √n. For k at least 4 the paper supplies exponential lower bounds with base (k-1)/(k-2) and an upper bound on the exponential growth rate obtained from carry-free digit representations built on nearly-regular graphs.

Core claim

In the three-term case, g_3(n) is at least the exact bandwidth of the ternary grid, which equals (T_n-1)/2 + sum_{j=0}^{n-1} T_j and therefore (√3/(2√π) + o(1)) 3^n / √n. For k ≥ 4, g_k(n) ≫_k ((k-1)/(k-2))^n n^{-log_2((k-1)/(k-2))}. In the opposite direction, lim sup g_k(n)^{1/n} ≤ min_{p prime ≥3} p^{2/(min{p,k}-1)}, so that as k → ∞ the logarithm of the lower exponential rate is at least (1+o(1))/k while the logarithm of the upper exponential rate is at most (2+o(1)) log k / k.

What carries the argument

the exact bandwidth of the ternary grid, which lower-bounds g_3(n) via a subset-sum embedding that preserves the absence of 3-term arithmetic progressions

If this is right

g_3(n) grows exponentially with leading base 3, up to a polynomial factor of order n^{-1/2}.
For each fixed k ≥ 4, g_k(n) is at least exponential in n with base (k-1)/(k-2) times a sub-exponential factor.
The exponential growth rate of g_k(n) is bounded from above by a quantity that tends to zero like (2 log k)/k as k grows.
The gap between the proven lower and upper exponential rates for g_k(n) shrinks to an interval of length roughly (2 log k - 1)/k for large k.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same graph-theoretic construction used for the upper bound may be adaptable to produce explicit sets A achieving the lower bounds for small k.
If the ternary-grid bandwidth is attained by some concrete subset-sum set, then g_3(n) equals the given trinomial expression exactly.
The exponential rates derived here supply a benchmark against which constructions for sumsets avoiding longer progressions in other additive bases can be compared.

Load-bearing premise

The subset-sum embedding into the ternary grid achieves exactly the grid's bandwidth without introducing extra 3-term arithmetic progressions.

What would settle it

An explicit computation of the bandwidth of the n-dimensional ternary grid that yields a number strictly smaller than (T_n-1)/2 + sum_{j=0}^{n-1} T_j for some n.

read the original abstract

For a finite set $A$ of positive integers, let $H(A)$ be its set of subset sums, including the empty sum, and let $g_k(n)$ be the least $N$ for which some $n$-element set $A\subseteq[N]$ has $H(A)$ free of nonconstant $k$-term arithmetic progressions. The problem of determining $g_k(n)$ was posed by Erd\H{o}s and S\'ark\H{o}zy. In the three-term case, we prove a lower bound equal to the exact bandwidth of the ternary grid. If $T_m=[x^m](1+x+x^2)^m$ is the central trinomial coefficient, then \[ g_3(n)\ge \frac{T_n-1}{2}+\sum_{j=0}^{n-1}T_j =\left(\frac{\sqrt{3}}{2\sqrt{\pi}}+o(1)\right)\frac{3^n}{\sqrt{n}}. \] For general $k \ge 4$ we show \[ g_k(n)\gg_k \left(\frac{k-1}{k-2}\right)^n n^{-\log_2((k-1)/(k-2))} \] In the opposite direction, a carry-free digit construction based on nearly-regular graphs gives \[ \limsup_{n\to\infty}g_k(n)^{1/n} \le \min_{p\ \mathrm{prime},\ p\ge3}p^{2/(\min\{p,k\}-1)}. \] Consequently, as $k\to\infty$, the logarithm of the lower exponential rate is at least $(1+o(1))/k$, while the logarithm of the upper exponential rate is at most $(2+o(1))\log k/k$.

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

Korsky gives the first explicit closed-form lower bound for g_3(n) via ternary grid bandwidth plus a carry-free upper bound construction that pins the exponential rate for general k.

read the letter

The punchline is that this paper turns the Erdős–Sárközy question on the minimal N for an n-element A whose subset sums avoid k-term APs into concrete, explicit bounds rather than existence arguments.

What is new is the lower bound for k=3 that equals the bandwidth of the ternary grid, expressed as (T_n-1)/2 plus the partial sum of central trinomial coefficients, which simplifies to the stated asymptotic with leading constant sqrt(3)/(2 sqrt(pi)). The general-k lower bound of order ((k-1)/(k-2))^n n to a negative power is a direct extension. The upper bound on lim sup g_k(n)^{1/n} comes from a carry-free digit construction over primes and nearly-regular graphs, giving the min over p of that p-power expression.

The constructions are parameter-free and combinatorial, which is a strength. The carry-free approach looks clean for producing the exponential upper rate without hidden constants.

The soft spot is the central equality claim for the k=3 lower bound. It requires that the subset-sum embedding into the grid positions really saturates the bandwidth with no losses from non-injective sums or carry issues. The stress-test note flags exactly this; if the full proof shows the map works without extra restrictions, the bound holds. Otherwise the closed form is only a lower bound, not necessarily tight to the bandwidth.

This is for people working in additive combinatorics on subset sums or AP-free sets. The explicit rates and constructions are usable even if later work tightens constants. It deserves serious referee time because the problem is old and the bounds are the first of this explicitness.

Referee Report

2 major / 1 minor

Summary. The paper defines g_k(n) as the minimal N such that some n-element A ⊆ [N] has its subset-sum set H(A) free of non-constant k-term arithmetic progressions. For k=3 it claims the explicit lower bound g_3(n) ≥ (T_n−1)/2 + ∑_{j=0}^{n−1} T_j (T_m the central trinomial coefficient) by identifying this quantity with the exact bandwidth of the ternary grid; for k≥4 it gives the exponential lower bound g_k(n) ≫_k ((k−1)/(k−2))^n n^{−log_2((k−1)/(k−2))}; and via a carry-free digit construction on nearly-regular graphs it proves lim sup g_k(n)^{1/n} ≤ min_{p prime ≥3} p^{2/(min{p,k}−1)}.

Significance. If the grid-bandwidth identification and carry-free embedding hold, the work supplies the first closed-form lower bound for the three-term Erdős–Sárközy problem and concrete exponential rates (both lower and upper) that sharpen the known growth of g_k(n). The explicit trinomial expression and the graph-theoretic upper-bound construction are concrete combinatorial contributions.

major comments (2)

[Abstract] Abstract, paragraph beginning “In the three-term case, we prove a lower bound equal to the exact bandwidth of the ternary grid”: the asserted equality between the displayed trinomial expression and the grid bandwidth rests on an embedding of an n-element subset-sum set into the ternary grid that preserves the AP-free property. The manuscript provides neither the explicit embedding map nor a verification that the map is injective and carry-free; without these the closed-form lower bound does not follow.
[The paragraph stating the lim-sup upper bound] The carry-free digit construction (the paragraph stating the lim-sup upper bound): the argument invokes “nearly-regular graphs” to produce digit representations whose subset sums avoid k-term APs, yet no definition of the graphs, no explicit digit map, and no check that the resulting H(A) is indeed k-AP-free appear in the text. This step is load-bearing for the stated upper bound on the exponential rate.

minor comments (1)

[Abstract] The asymptotic equivalence (√3/(2√π) + o(1)) 3^n / √n for the trinomial sum is stated without a reference or short derivation; a one-line appeal to the known central-trinomial asymptotics would clarify the claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments. We address the two major points below and will revise the manuscript accordingly to supply the requested details.

read point-by-point responses

Referee: [Abstract] Abstract, paragraph beginning “In the three-term case, we prove a lower bound equal to the exact bandwidth of the ternary grid”: the asserted equality between the displayed trinomial expression and the grid bandwidth rests on an embedding of an n-element subset-sum set into the ternary grid that preserves the AP-free property. The manuscript provides neither the explicit embedding map nor a verification that the map is injective and carry-free; without these the closed-form lower bound does not follow.

Authors: We agree that the explicit embedding and its verification are not presented with sufficient detail. In the revision we will insert the concrete map from an n-element subset-sum set into the ternary grid together with proofs of injectivity and carry-freeness; these additions will rigorously justify the identification with the grid bandwidth and the resulting closed-form lower bound. revision: yes
Referee: [The paragraph stating the lim-sup upper bound] The carry-free digit construction (the paragraph stating the lim-sup upper bound): the argument invokes “nearly-regular graphs” to produce digit representations whose subset sums avoid k-term APs, yet no definition of the graphs, no explicit digit map, and no check that the resulting H(A) is indeed k-AP-free appear in the text. This step is load-bearing for the stated upper bound on the exponential rate.

Authors: We acknowledge that the carry-free construction requires a more explicit treatment. The revised manuscript will define the nearly-regular graphs, state the digit map in full, and include a verification that the constructed H(A) contains no k-term arithmetic progression. These additions will substantiate the claimed upper bound on the exponential growth rate. revision: yes

Circularity Check

0 steps flagged

No significant circularity; bounds derived from explicit constructions

full rationale

The paper establishes the g_3(n) lower bound via an explicit n-element subset A whose subset-sum set H(A) is shown to embed into the ternary grid such that the grid bandwidth directly yields an AP-free set of the stated size; the bandwidth formula is computed from the central trinomial coefficients independently of g_k. The k≥4 lower bound uses a direct counting argument on base-(k-1) representations, and the upper bound employs a carry-free digit construction on nearly-regular graphs. None of these steps reduce to a self-definition, a fitted parameter renamed as prediction, or a load-bearing self-citation chain. The derivation chain is self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard combinatorial definitions of subset sums and arithmetic progressions together with generating-function identities for trinomial coefficients; no free parameters are fitted to data and no new entities are postulated.

axioms (2)

standard math The central trinomial coefficient T_m counts the number of ways to obtain sum m with m summands each in {0,1,2}.
Invoked to express the explicit lower bound for g_3(n).
domain assumption Subset sums of an n-element set can be embedded into the ternary grid without creating non-constant 3-term APs precisely when the bandwidth condition holds.
This identification is required for the claimed equality between the trinomial expression and grid bandwidth.

pith-pipeline@v0.9.1-grok · 5852 in / 1666 out tokens · 20239 ms · 2026-06-26T00:09:17.549275+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 9 canonical work pages

[1]

J. Bae. On generalized subset-sum-distinct sequences.International Journal of Pure and Applied Mathematics, 1(3):335–343, 2002. https://www.ijpam.eu/contents/ 2002-1-3/8/8.pdf

2002
[2]

L. J. Billera and S. A. Blanco. Bandwidth of the product of paths of the same length. Discrete Applied Mathematics, 161(18):3080–3086, 2013. https://doi.org/10.1016/ j.dam.2013.05.038

2013
[3]

T. F. Bloom. Erd˝ os Problem #817. 2026.https://www.erdosproblems.com/817

2026
[4]

https://doi.org/10.48550/arXiv.2311

D. Conlon, J. Fox, and H. T. Pham. Homogeneous structures in subset sums and non-averaging sets. arXiv:2311.01416, 2023. https://doi.org/10.48550/arXiv.2311. 01416

work page doi:10.48550/arxiv.2311 2023
[5]

Croot, J

E. Croot, J. Mao, and C. H. Yip. Hilbert cubes in sets with arithmetic properties. arXiv:2603.14654, 2026.https://doi.org/10.48550/arXiv.2603.14654

work page doi:10.48550/arxiv.2603.14654 2026
[6]

Dietmann and C

R. Dietmann and C. Elsholtz. Hilbert cubes in progression-free sets and in the set of squares.Israel Journal of Mathematics, 192(1):59–66, 2012.https://doi.org/10. 1007/s11856-012-0047-7 14

2012
[7]

Dietmann and C

R. Dietmann and C. Elsholtz. Hilbert cubes in arithmetic sets.Revista Matem´ atica Iberoamericana, 31(4):1477–1498, 2015.https://doi.org/10.4171/RMI/877

work page doi:10.4171/rmi/877 2015
[8]

S. Dutta. The greedy algorithm for dissociated sets. arXiv:2601.07068, 2026. https: //doi.org/10.48550/arXiv.2601.07068

work page doi:10.48550/arxiv.2601.07068 2026
[9]

Elsholtz, I

C. Elsholtz, I. Z. Ruzsa, and L. Wurzinger. Sumset growth in progression-free sets. Acta Arithmetica, 220(3):289–303, 2025. https://doi.org/10.4064/aa250115-14-7

work page doi:10.4064/aa250115-14-7 2025
[10]

Erd˝ os and A

P. Erd˝ os and A. S´ ark¨ ozy. Arithmetic progressions in subset sums.Discrete Mathematics, 102(3):249–264, 1992.https://doi.org/10.1016/0012-365X(92)90119-Z

work page doi:10.1016/0012-365x(92)90119-z 1992
[11]

Green and T

B. Green and T. Tao. New bounds for Szemer´ edi’s theorem, III: A polylogarithmic bound for r4(N).Mathematika, 63(3):944–1040, 2017. https://doi.org/10.1112/ S0025579317000316

2017
[12]

L. H. Harper. Optimal numberings and isoperimetric problems on graphs.Jour- nal of Combinatorial Theory, 1(3):385–393, 1966. https://doi.org/10.1016/ S0021-9800(66)80059-5

1966
[13]

J. Leng, A. Sah, and M. Sawhney. Improved bounds for Szemer´ edi’s theorem. arXiv:2402.17995, 2024.https://doi.org/10.48550/arXiv.2402.17995

work page doi:10.48550/arxiv.2402.17995 2024
[14]

H. S. Moghadam. Bandwidth of the product of n paths.Congressus Numerantium, 173:3–15, 2005

2005
[15]

T. Schoen. Arithmetic progressions in sums of subsets of sparse sets.Acta Arithmetica, 147(3):283–289, 2011.https://doi.org/10.4064/aa147-3-7

work page doi:10.4064/aa147-3-7 2011
[16]

Szemer´ edi and V

E. Szemer´ edi and V. H. Vu. Long arithmetic progressions in sumsets: Thresholds and bounds.Journal of the American Mathematical Society, 19(1):119–169, 2006. https://doi.org/10.1090/S0894-0347-05-00502-3 15

work page doi:10.1090/s0894-0347-05-00502-3 2006

[1] [1]

J. Bae. On generalized subset-sum-distinct sequences.International Journal of Pure and Applied Mathematics, 1(3):335–343, 2002. https://www.ijpam.eu/contents/ 2002-1-3/8/8.pdf

2002

[2] [2]

L. J. Billera and S. A. Blanco. Bandwidth of the product of paths of the same length. Discrete Applied Mathematics, 161(18):3080–3086, 2013. https://doi.org/10.1016/ j.dam.2013.05.038

2013

[3] [3]

T. F. Bloom. Erd˝ os Problem #817. 2026.https://www.erdosproblems.com/817

2026

[4] [4]

https://doi.org/10.48550/arXiv.2311

D. Conlon, J. Fox, and H. T. Pham. Homogeneous structures in subset sums and non-averaging sets. arXiv:2311.01416, 2023. https://doi.org/10.48550/arXiv.2311. 01416

work page doi:10.48550/arxiv.2311 2023

[5] [5]

Croot, J

E. Croot, J. Mao, and C. H. Yip. Hilbert cubes in sets with arithmetic properties. arXiv:2603.14654, 2026.https://doi.org/10.48550/arXiv.2603.14654

work page doi:10.48550/arxiv.2603.14654 2026

[6] [6]

Dietmann and C

R. Dietmann and C. Elsholtz. Hilbert cubes in progression-free sets and in the set of squares.Israel Journal of Mathematics, 192(1):59–66, 2012.https://doi.org/10. 1007/s11856-012-0047-7 14

2012

[7] [7]

Dietmann and C

R. Dietmann and C. Elsholtz. Hilbert cubes in arithmetic sets.Revista Matem´ atica Iberoamericana, 31(4):1477–1498, 2015.https://doi.org/10.4171/RMI/877

work page doi:10.4171/rmi/877 2015

[8] [8]

S. Dutta. The greedy algorithm for dissociated sets. arXiv:2601.07068, 2026. https: //doi.org/10.48550/arXiv.2601.07068

work page doi:10.48550/arxiv.2601.07068 2026

[9] [9]

Elsholtz, I

C. Elsholtz, I. Z. Ruzsa, and L. Wurzinger. Sumset growth in progression-free sets. Acta Arithmetica, 220(3):289–303, 2025. https://doi.org/10.4064/aa250115-14-7

work page doi:10.4064/aa250115-14-7 2025

[10] [10]

Erd˝ os and A

P. Erd˝ os and A. S´ ark¨ ozy. Arithmetic progressions in subset sums.Discrete Mathematics, 102(3):249–264, 1992.https://doi.org/10.1016/0012-365X(92)90119-Z

work page doi:10.1016/0012-365x(92)90119-z 1992

[11] [11]

Green and T

B. Green and T. Tao. New bounds for Szemer´ edi’s theorem, III: A polylogarithmic bound for r4(N).Mathematika, 63(3):944–1040, 2017. https://doi.org/10.1112/ S0025579317000316

2017

[12] [12]

L. H. Harper. Optimal numberings and isoperimetric problems on graphs.Jour- nal of Combinatorial Theory, 1(3):385–393, 1966. https://doi.org/10.1016/ S0021-9800(66)80059-5

1966

[13] [13]

J. Leng, A. Sah, and M. Sawhney. Improved bounds for Szemer´ edi’s theorem. arXiv:2402.17995, 2024.https://doi.org/10.48550/arXiv.2402.17995

work page doi:10.48550/arxiv.2402.17995 2024

[14] [14]

H. S. Moghadam. Bandwidth of the product of n paths.Congressus Numerantium, 173:3–15, 2005

2005

[15] [15]

T. Schoen. Arithmetic progressions in sums of subsets of sparse sets.Acta Arithmetica, 147(3):283–289, 2011.https://doi.org/10.4064/aa147-3-7

work page doi:10.4064/aa147-3-7 2011

[16] [16]

Szemer´ edi and V

E. Szemer´ edi and V. H. Vu. Long arithmetic progressions in sumsets: Thresholds and bounds.Journal of the American Mathematical Society, 19(1):119–169, 2006. https://doi.org/10.1090/S0894-0347-05-00502-3 15

work page doi:10.1090/s0894-0347-05-00502-3 2006