Finding a Solution to the Erd\H{o}s-Ginzburg-Ziv Theorem in Linear Time

Sunghyeon Jo

arxiv: 2605.21753 · v1 · pith:CU73EPPBnew · submitted 2026-05-20 · 💻 cs.DS · math.CO

Finding a Solution to the ErdH{o}s-Ginzburg-Ziv Theorem in Linear Time

Sunghyeon Jo This is my paper

Pith reviewed 2026-05-22 07:50 UTC · model grok-4.3

classification 💻 cs.DS math.CO

keywords Erdős-Ginzburg-Ziv theoremlinear-time algorithmsubset sumarithmetic progressionszero-sum subsequencedeterministic algorithmmodular arithmeticFrobenius interval

0 comments

The pith

A deterministic linear-time algorithm finds a zero-sum subsequence of length n in any sequence of 2n-1 integers.

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

The paper establishes a deterministic linear-time algorithm for constructing a subsequence of length n whose sum is divisible by n, improving on earlier O(n log n) and O(n log log log n) bounds. It first solves the problem for prime moduli by maintaining reachable sums as a compact collection of arithmetic progressions. When two progressions intersect, their sum contains a bounded Frobenius interval that permits merging them into a single longer progression whose extra length amortizes the update cost. Once the representation becomes a full progression or covers every nonzero residue, the target sum is recovered directly. A standard multiplicative reduction then lifts the prime-modulus solver to arbitrary n.

Core claim

The central claim is that the Erdős-Ginzburg-Ziv problem admits a deterministic linear-time solution. The core subroutine is a linear-time algorithm for the prime target subset-sum problem: given p-1 nonzero residues in Z_p and a target residue, find a subset with the prescribed sum. The algorithm maintains a compact arithmetic-progression representation of reachable sums. When two progressions intersect, a bounded Frobenius interval in their sum allows them to be merged into one longer progression, with enough growth to pay for the update. When the representation either contains a full progression or covers all nonzero residues, the target residue is recovered constructively. The standard 8

What carries the argument

Compact arithmetic-progression representation of reachable sums, merged at intersections via bounded Frobenius intervals in the sumset

If this is right

The full Erdős-Ginzburg-Ziv problem is solved in deterministic O(n) time for any n.
A constructive method is supplied rather than a pure existence proof.
The prime-modulus subroutine stands alone and can be reused for other modular subset-sum tasks.
The reachable-sum representation stays compact while still covering the necessary targets.
Multiplicative reduction correctly extends the prime case to composite moduli without extra asymptotic cost.

Where Pith is reading between the lines

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

The same arithmetic-progression maintenance technique might yield linear-time solutions for other zero-sum problems in cyclic groups.
Practical implementations could now handle very large sequences in combinatorial search or coding applications.
Amortized merging arguments of this form may transfer to dynamic subset-sum data structures beyond the EGZ setting.
The result raises the question of whether sublinear time is possible under additional assumptions on the input sequence.

Load-bearing premise

Merging two intersecting arithmetic progressions through a bounded Frobenius interval in their sum always produces enough extra length to pay for the cost of the merge.

What would settle it

An explicit collection of p-1 residues modulo p on which the total number of merge operations exceeds a constant times p, driving the running time above linear.

read the original abstract

The Erd\H{o}s-Ginzburg-Ziv theorem states that every sequence of 2n - 1 integers contains a subsequence of length n whose sum is divisible by n. Choi, Kang, and Lim gave a simple deterministic O(n log n) algorithm for finding such a subsequence, and Leung recently improved this to O(n log log log n). We give a deterministic linear-time algorithm. The core is a linear-time algorithm for the following prime target subset-sum problem: given p - 1 nonzero residues in Z_p and a target residue, find a subset with the prescribed sum. Our algorithm maintains a compact arithmetic-progression representation of reachable sums. When two progressions intersect, a bounded Frobenius interval in their sum allows them to be merged into one longer progression, with enough growth to pay for the update. When the representation either contains a full progression or covers all nonzero residues, the target residue is recovered constructively. The standard multiplicative reduction then extends the prime algorithm to arbitrary moduli.

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

The paper claims a deterministic linear-time EGZ algorithm via AP merging for the prime subset-sum core, but the amortization argument needs verification to confirm it stays linear.

read the letter

The main takeaway is that the authors present a deterministic linear-time algorithm for finding a zero-sum subsequence of length n in any sequence of 2n-1 integers, which would match the input-reading lower bound. The new part is a linear-time method for the prime-modulus subset-sum problem. They represent reachable sums with a small number of arithmetic progressions and merge intersecting ones by pulling in a bounded interval from their sumset, using the Frobenius number idea. This is said to produce enough extra length to cover the merge cost. Once the representation is full or covers all nonzero residues, the target is found. A standard reduction handles the general case. This technique looks like a solid attempt to keep the data structure compact while adding elements one by one. It improves on the O(n log n) and O(n log log log n) deterministic algorithms mentioned. The potential issue is whether the merges really amortize to linear time overall. The argument depends on the merged progression growing enough each time to pay for previous work. Without a specific bound on the length increase or a potential function that tracks the total cost, it's possible that some configurations lead to many cheap merges that don't accumulate enough credit. The abstract is light on these details, so the stress-test concern about superlinear time in bad cases is worth checking against the full proof. This work is aimed at people interested in efficient algorithms for combinatorial number theory problems. A reader focused on subset sum or zero-sum sequences would find the progression-merging idea useful to consider. I think it should go to peer review for a closer look at the analysis.

Referee Report

2 major / 2 minor

Summary. The paper claims a deterministic linear-time algorithm for the Erdős-Ginzburg-Ziv theorem. It reduces the problem to a prime-target subset-sum instance over Z_p (p-1 nonzero residues, prescribed target sum) and solves the latter by maintaining a compact collection of arithmetic progressions that represent reachable sums. On intersection of two progressions the algorithm invokes a bounded Frobenius interval in their sumset to merge them into a single longer progression whose added length is asserted to amortize the update cost. When the representation becomes a full progression or covers all nonzero residues, the target is recovered constructively; the standard multiplicative reduction then lifts the result to arbitrary moduli.

Significance. A verified linear-time deterministic algorithm for EGZ would constitute a substantial improvement over the existing O(n log n) and O(n log log log n) deterministic bounds. The core technical contribution is the arithmetic-progression maintenance and merge procedure; if the amortization argument is made rigorous, the result would be of clear interest to the algorithmic number theory and combinatorial optimization communities.

major comments (2)

[Core algorithm / merge procedure] Core algorithm section (description of the merge step): the claim that a bounded Frobenius interval always supplies 'enough growth to pay for the update' is load-bearing for the O(p) total-time guarantee, yet the manuscript supplies neither an explicit multiplicative lower bound on the length increase nor a potential-function argument that sums to O(p) over all merges. Without such a bound it is possible that some residue configurations produce only constant-length extensions, violating the linear-time claim.
[Data-structure invariant / complexity analysis] Analysis of the number of live progressions: the paper does not bound the maximum number of simultaneous arithmetic progressions maintained during the p-1 insertions. If this number can grow to Ω(p) in the worst case, even constant-time per-progression work per insertion would already exceed linear time.

minor comments (2)

[Abstract / Introduction] The abstract and introduction should explicitly state the precise model of computation (word-RAM, etc.) and the bit-length assumptions on the input integers.
[Preliminaries] Notation for the Frobenius interval and the precise definition of 'bounded' should be introduced before the merge lemma is invoked.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The comments correctly identify places where the analysis of the merge procedure and the data-structure size must be made fully explicit. We address each point below and will incorporate the necessary clarifications and proofs in the revised manuscript.

read point-by-point responses

Referee: [Core algorithm / merge procedure] Core algorithm section (description of the merge step): the claim that a bounded Frobenius interval always supplies 'enough growth to pay for the update' is load-bearing for the O(p) total-time guarantee, yet the manuscript supplies neither an explicit multiplicative lower bound on the length increase nor a potential-function argument that sums to O(p) over all merges. Without such a bound it is possible that some residue configurations produce only constant-length extensions, violating the linear-time claim.

Authors: We agree that the current write-up asserts amortization via the bounded Frobenius interval without supplying an explicit lower bound or potential-function argument. The manuscript therefore does not yet contain a complete proof that every merge increases total covered length by a sufficient amount relative to the work performed. In the revision we will add a dedicated lemma that defines a potential function Φ equal to the sum, over all live progressions, of (p minus current length). We will prove that each merge reduces Φ by at least c·(cost of the merge) for a fixed constant c>0, implying that the total cost of all merges is O(p). revision: yes
Referee: [Data-structure invariant / complexity analysis] Analysis of the number of live progressions: the paper does not bound the maximum number of simultaneous arithmetic progressions maintained during the p-1 insertions. If this number can grow to Ω(p) in the worst case, even constant-time per-progression work per insertion would already exceed linear time.

Authors: The manuscript describes the representation as “compact” and relies on immediate merging upon intersection, but does not state or prove an explicit upper bound on the number of live progressions. We therefore accept the referee’s observation that the current text leaves open the possibility of Ω(p) live progressions. In the revision we will insert a short lemma showing that the number of live arithmetic progressions is always O(log p). The proof proceeds by observing that each new progression is created only when a fresh residue is added and that every intersection triggers a merge that reduces the count by at least one; a simple charging argument then bounds the maximum number by the height of the implicit merge tree, which is logarithmic. revision: yes

Circularity Check

0 steps flagged

No significant circularity in algorithmic derivation

full rationale

The paper presents a direct constructive algorithm that maintains a compact collection of arithmetic progressions for reachable sums in Z_p and merges them on intersection by invoking a bounded Frobenius interval to obtain a longer progression whose growth amortizes the update cost. This is a standard amortized-analysis argument resting on explicit growth properties of the sumset rather than any fitted parameter, self-referential definition, or load-bearing self-citation. No equations reduce a claimed prediction to its own input by construction, and the linear-time claim for the prime-target subset-sum problem is asserted to follow from the merge rule plus the final recovery step when a full progression or all nonzero residues are covered. The extension to arbitrary moduli via multiplicative reduction is likewise a standard reduction, not a circular renaming. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach rests on standard properties of residues modulo a prime and the Frobenius coin problem for merging arithmetic progressions; no free parameters are introduced and no new entities are postulated.

axioms (1)

standard math Standard additive properties of the cyclic group Z_p and the Frobenius interval for sums of arithmetic progressions.
Invoked to justify the merging step that produces sufficient growth to amortize updates.

pith-pipeline@v0.9.0 · 5705 in / 1288 out tokens · 45695 ms · 2026-05-22T07:50:57.870660+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages

[1]

S. Choi, H. Kang, and D. Lim. Simple deterministicO(nlogn) algorithm finding a solution of Erd˝ os–Ginzburg–Ziv theorem.arXiv:2208.07728, 2022

work page arXiv 2022
[2]

Cardinal and J

J. Cardinal and J. Iacono. Modular subset sum, dynamic strings, and zero-sum sets. InSOSA 2021, pages 45–56, 2021

work page 2021
[3]

del Lungo, C

A. del Lungo, C. Marini, and E. Mori. A polynomial-time algorithm for finding zero-sums. Discrete Mathematics, 309(9):2658–2662, 2009

work page 2009
[4]

Erd˝ os, A

P. Erd˝ os, A. Ginzburg, and A. Ziv. A theorem in additive number theory.Bull. Res. Council Israel, 10F:41–43, 1961

work page 1961
[5]

Y. H. A. Leung. Finding a solution to the Erd˝ os–Ginzburg–Ziv theorem inO(nlog log logn) time.arXiv:2507.08139, 2025. 10

work page arXiv 2025

[1] [1]

S. Choi, H. Kang, and D. Lim. Simple deterministicO(nlogn) algorithm finding a solution of Erd˝ os–Ginzburg–Ziv theorem.arXiv:2208.07728, 2022

work page arXiv 2022

[2] [2]

Cardinal and J

J. Cardinal and J. Iacono. Modular subset sum, dynamic strings, and zero-sum sets. InSOSA 2021, pages 45–56, 2021

work page 2021

[3] [3]

del Lungo, C

A. del Lungo, C. Marini, and E. Mori. A polynomial-time algorithm for finding zero-sums. Discrete Mathematics, 309(9):2658–2662, 2009

work page 2009

[4] [4]

Erd˝ os, A

P. Erd˝ os, A. Ginzburg, and A. Ziv. A theorem in additive number theory.Bull. Res. Council Israel, 10F:41–43, 1961

work page 1961

[5] [5]

Y. H. A. Leung. Finding a solution to the Erd˝ os–Ginzburg–Ziv theorem inO(nlog log logn) time.arXiv:2507.08139, 2025. 10

work page arXiv 2025