{"ID":2896299,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.08139","arxiv_id":"2507.08139","title":"Finding a solution to the Erdős-Ginzburg-Ziv theorem in $O(n\\log\\log\\log n)$ time","abstract":"The Erdős-Ginzburg-Ziv theorem states that for any sequence of $2n-1$ integers, there exists a subsequence of $n$ elements whose sum is divisible by $n$. In this article, we provide a simple, practical $O(n\\log\\log n)$ algorithm and a theoretical $O(n\\log\\log\\log n)$ algorithm, both of which improve upon the best previously known $O(n\\log n)$ approach. This shows that a specific variant of boolean convolution can be implemented in time faster than the usual $O(n\\log n)$ expected from FFT-based methods.","short_abstract":"The Erdős-Ginzburg-Ziv theorem states that for any sequence of $2n-1$ integers, there exists a subsequence of $n$ elements whose sum is divisible by $n$. In this article, we provide a simple, practical $O(n\\log\\log n)$ algorithm and a theoretical $O(n\\log\\log\\log n)$ algorithm, both of which improve upon the best previ...","url_abs":"https://arxiv.org/abs/2507.08139","url_pdf":"https://arxiv.org/pdf/2507.08139v1","authors":"[\"Yui Hin Arvin Leung\"]","published":"2025-07-10T19:56:34Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DS\"]","methods":"[]","has_code":false}