Finding a Solution to the Erdős–Ginzburg–Ziv Theorem in Linear Time
Sunghyeon Jo · 2026
Read Finding a Solution to the Erdős–Ginzburg–Ziv Theorem in Linear Time by Sunghyeon Jo (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21753.txt.
Introduction
Sunghyeon Jo gives a deterministic linear-time algorithm for the Erdos-Ginzburg-Ziv problem: from any 2n minus 1 integers, find n whose sum is divisible by n. Earlier methods ran in n log n time, later improved to n log log log n. The core is a prime target subset-sum method built on a compact arithmetic-progression picture of reachable sums. When two progressions meet, a bounded Frobenius interval merges them into a longer one. A standard multiplicative reduction then extends the prime case to arbitrary moduli.
Catalog record
| CREATOR | Sunghyeon Jo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 25604 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.21753
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Finding a Solution to the Erdős–Ginzburg–Ziv Theorem in Linear Time Sunghyeon Jo Abstract The Erdős–Ginzburg–Ziv theorem states that every sequence of 2 n − 1 2n-1 integers contains a subsequence of length n n whose sum is divisible by n n . Choi, Kang, and Lim gave a simple deterministic O ( n log n ) O(n\log n) algorithm for finding such a subsequence, and Leung recently improved this to O ( n log log log n ) 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 p-1 nonzero residues in ℤ p \mathbb{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. 1 Introduction Let A=(a_{1},\ldots,a_{2n-1}) be a sequence of integers. The constructive Erdős–Ginzburg–Ziv problem asks for indices I\subseteq\{1,\ldots,2n-1\} such that |I|=n,\qquad\sum_{i\in I}a_{i}\equiv 0\pmod{n}. The classical multiplicative proof reduces the composite case to smaller moduli, so the algorithmic core is the prime case. For prime p , after sorting the input by residues, either some residue class occurs at least p times, or the problem reduces to the following target subset-sum task. Given nonzero residues d_{1},\ldots,d_{p-1}\in\mathbb{Z}_{p}^{\ast} and a target \tau\in\mathbb{Z}_{p} , find J\subseteq\{1,\ldots,p-1\} such that \sum_{j\in J}d_{j}=\tau. Cauchy–Davenport proves existence, since \{0,d_{1}\}+\cdots+\{0,d_{p-1}\}=\mathbb{Z}_{p}. The question is how to find one representation in linear time without maintaining the full sumset after every insertion. The algorithm of Choi, Kang, and Lim grows a represented sumset by one new residue at a time and uses O(\log p) time per inserted difference. Leung’s later algorithm first transforms the input into a small number of arithmetic progressions and then packs those progressions in linear time; the transformation phase is responsible for the remaining O(n\log\log\log n) factor. Our algorithm removes this preliminary transformation. It maintains arithmetic-progression components online, and every detected intersection is immediately converted into a merge that lengthens the representation. 2 Arithmetic progression components All residues in this section are elements of \mathbb{Z}_{p} , where p is prime. For v\in\mathbb{Z}_{p}^{\ast} and 0\leq\ell\leq p-1 , write \operatorname{AP}(v,\ell)=\{0,v,2v,\ldots,\ell v\}. The covered nonzero residues of this progression are v,2v,\ldots,\ell v . The algorithm processes d_{1},d_{2},\ldots,d_{p-1} from left to right. After some prefix has been processed it maintains active components C_{1},\ldots,C_{r} . Each component C has: v(C)\in\mathbb{Z}_{p}^{\ast},\qquad 0\leq\ell(C)\leq p-1,\qquad\xi(C)\in\mathbb{Z}_{p}. It also has a reconstruction map: for every integer 0\leq t\leq\ell(C) , a subset R_{C}(t) of the processed input indices assigned to C is represented such that \sum_{i\in R_{C}(t)}d_{i}=\xi(C)+t\,v(C)\pmod{p}. The assigned input-index sets of distinct active components are disjoint. Define the global shift X=\sum_{C}\xi(C). Definition 1 . The active family is disjoint if the covered nonzero residues of all active components are pairwise disjoint. Equivalently, no two pairs (C,t) and (D,u) , with 1\leq t\leq\ell(C) and 1\leq u\leq\ell(D) , cover the same nonzero residue. Lemma 2 (reachable set invariant) . If the active components are C_{1},\ldots,C_{r} , then every residue in X+\operatorname{AP}(v(C_{1}),\ell(C_{1}))+\cdots+\operatorname{AP}(v(C_{r}),\ell(C_{r})) is the sum of a subset of the processed input differences. Moreover, such a subset can be recovered from the component reconstruction maps. Proof. Choose coefficients 0\leq t_{j}\leq\ell(C_{j}) . The union of the disjoint subsets R_{C_{j}}(t_{j}) has sum \sum_{j}\bigl(\xi(C_{j})+t_{j}v(C_{j})\bigr)=X+\sum_{j}t_{j}v(C_{j}). This is exactly the desired residue. ∎ 3 The merge lemma The essential operation replaces two colliding progressions by one longer progression. Lemma 3 (bounded Frobenius interval) . Let x,y be coprime positive integers with x,y>1 . Let \ell\geq x and m\geq y , and put F=(x-1)(y-1),\qquad S=\ell y+mx. Then every integer N with F\leq N\leq S-F has a representation N=\alpha y+\beta x,\qquad 0\leq\alpha\leq\ell,\quad 0\leq\beta\leq m. Proof. Fix a residue class modulo x . Since \gcd(x,y)=1 , there is a unique a_{0}\in\{0,\ldots,x-1\} such that a_{0}y belongs to this class. For this class, all representations with coefficient of y congruent to a_{0} modulo x are obtained from the intervals [a_{0}y+kxy,\;a_{0}y+kxy+mx]\qquad(k\geq 0), restricted to integers in the fixed residue class. Consecutive intervals overlap or touch in that residue class: their starting points differ by xy , while the available \beta x term covers 0,x,2x,\ldots,mx , and m\geq y . Let a_{1} be the largest integer at most \ell with a_{1}\equiv a_{0}\pmod{x} . Thus every integer in the fixed residue class between a_{0}y and a_{1}y+mx is represented with 0\leq\alpha\leq\ell and 0\leq\beta\leq m . It remains to check that the interval [F,S-F] has no element of this residue class outside these endpoints. If an integer N in this residue class were smaller than a_{0}y , then N\leq a_{0}y-x\leq(x-1)y-x=F-1 , so N<F . Hence every N\geq F in the class is at least a_{0}y . For the upper endpoint, suppose that N\equiv a_{1}y+mx\pmod{x} and N>a_{1}y+mx . Then N\geq a_{1}y+mx+x . But S-F-(a_{1}y+mx)=(\ell-a_{1})y-(x-1)(y-1)\leq x-1, because 0\leq\ell-a_{1}\leq x-1 . Therefore no integer in the same residue class can be both larger than a_{1}y+mx and at most S-F . This proves that every N\in[F,S-F] is represented. ∎ Lemma 4 (progression merge) . Let two active components have progressions \operatorname{AP}(v,\ell) and \operatorname{AP}(w,m) . Suppose there are positive integers x\leq\ell and y\leq m such that xv=yw\quad\text{in }\mathbb{Z}_{p}, and suppose \gcd(x,y)=1 . Put g=v/y=w/x\quad\text{in }\mathbb{Z}_{p}. Then the two components can be replaced by one component with direction g and length L as follows. If x=1 , set F=0,\qquad L=m+\ell y. Equivalently, for x=1 and v=yg,w=g , \operatorname{AP}(v,\ell)+\operatorname{AP}(w,m)=\operatorname{AP}(g,m+\ell y). If y=1 , set symmetrically F=0 and L=\ell+mx . If x,y>1 , set F=(x-1)(y-1),\qquad L=mx+\ell y-2F. Then Fg+\operatorname{AP}(g,L)\subseteq\operatorname{AP}(v,\ell)+\operatorname{AP}(w,m). If L\geq p-1 , the algorithm may replace this by length p-1 , because \operatorname{AP}(g,p-1)=\mathbb{Z}_{p} . In both cases the replacement is constructive: a coefficient 0\leq t\leq L can be converted into coefficients 0\leq\alpha\leq\ell and 0\leq\beta\leq m satisfying F+t=\alpha y+\beta x. Proof. First suppose x=1 . Then v=yg and w=g , and the collision condition gives y\leq m . For each \alpha=0,\ldots,\ell , the set \alpha yg+\operatorname{AP}(g,m) is the interval \{\alpha yg,\ldots,(\alpha y+m)g\} . Consecutive intervals overlap or touch because m\geq y . Their union is \operatorname{AP}(g,m+\ell y) . The case y=1 is symmetric. Now assume x,y>1 . Since v=yg and w=xg , \operatorname{AP}(v,\ell)+\operatorname{AP}(w,m)=\{(\alpha y+\beta x)g:0\leq\alpha\leq\ell,\;0\leq\beta\leq m\}. By Lemma 3 , every integer N\in[F,\ell y+mx-F] has a bounded representation N=\alpha y+\beta x . Taking N=F+t for 0\leq t\leq\ell y+mx-2F=L gives the desired inclusion. ∎ Remark 5 (computing the bounded coefficients) . For the case x=1 , a coefficient 0\leq t\leq m+\ell y is represented by \alpha=\min\{\ell,\lfloor t/y\rfloor\},\qquad\beta=t-\alpha y. Then 0\leq\beta\leq m : if \alpha<\ell , then \beta<y\leq m , and if \alpha=\ell , this follows from t\leq m+\ell y . The case y=1 is symmetric, using \beta=\min\{m,\lfloor t/x\rfloor\},\qquad\alpha=t-\beta x. For x,y>1 , the proof of Lemma 3 gives an explicit formula once y^{-1}\pmod{x} is known. Let a_{0}\equiv Ny^{-1}\pmod{x},\qquad 0\leq a_{0}<x,\qquad b_{0}=\frac{N-a_{0}y}{x}. The proof above gives b_{0}\geq 0 . Put k=\max\left\{0,\left\lceil\frac{b_{0}-m}{y}\right\rceil\right\},\qquad\alpha=a_{0}+kx,\qquad\beta=b_{0}-ky. Then N=\alpha y+\beta x , and the endpoint argument in Lemma 3 gives 0\leq\alpha\leq\ell and 0\leq\beta\leq