Finding a solution to the Erdős-Ginzburg-Ziv theorem in $O(n\log\log\log n)$ time
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909684013727744 |
|---|---|
| author | Leung, Yui Hin Arvin |
| author_facet | Leung, Yui Hin Arvin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_08139 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Finding a solution to the Erdős-Ginzburg-Ziv theorem in $O(n\log\log\log n)$ time Leung, Yui Hin Arvin Combinatorics Data Structures and Algorithms 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. |
| title | Finding a solution to the Erdős-Ginzburg-Ziv theorem in $O(n\log\log\log n)$ time |
| topic | Combinatorics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.08139 |