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

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.