Finding a Solution to the Erdős-Ginzburg-Ziv Theorem in Linear Time
This provides the first linear-time algorithm for a classic combinatorial number theory problem, benefiting algorithm designers and mathematicians interested in efficient constructive proofs.
The paper presents a deterministic linear-time algorithm for finding a subsequence of length n with sum divisible by n in any sequence of 2n-1 integers, solving the Erdős-Ginzburg-Ziv problem in O(n) time, improving upon previous O(n log log log n) algorithms.
The Erdő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.