A conservation law for the first moment in Graham's rearrangement problem
Let $G$ be a finite abelian group of order $n$ and $A \subseteq G \setminus \{0\}$ with $|A| = t$. For $g \in G$ let $U_g(A)$ be the expected number of pairs of partial sums of a random ordering of $A$ differing by $-g$; $g = 0$ gives the first moment for Graham's rearrangement problem, and $U_0(A) < 1$ certifies a valid ordering. We prove the total first moment is an invariant: $\sum_{g \in G} U_g(A) = \binom{t-1}{2}$ for every $A$ and $G$, independently of $n$ and of $A$. At least $n - \binom{t-1}{2}$ targets are certified, recovering the observed $\sqrt{2p}$ threshold as an identity. Feeding Pham and Sauermann's fixed-size anticoncentration theorem into the identity shows the first moment is equidistributed over $\mathbb{Z}_p$, $\max_g U_g(A) = \frac{1}{p}\binom{t-1}{2} + O(\sqrt{t \log t})$, so $O(\sqrt{t \log t})$ when $t = o(\sqrt p)$; the Kneserized estimate of Costa, Della Fiore, Feng and Liu extends this to composite cyclic moduli, subject to their dichotomy. Two upgrades are incorporated: Nguyen, Tran and Vu's announced two-sided estimate improves the error to $O(\sqrt t)$ (proof deferred), and Berger, Berkowitz, Devlin and Vu's fixed-size estimate over the reals settles the order of magnitude in our open slice-anticoncentration question, leaving the sharp constant and extremiser open. Combining $z N_z(A,g) \le \binom{t}{z-1}$ with complementation gives $U_0(A) \le B(t) = (\log 2 + o(1))t$, improving the recorded worst case $t - 1 - H_{t-1}$, trapping the extremal constant in $[1/2, \log 2]$; we ask whether it is $1/2$. Each inequality behind $B(t)$ is sharp, attained at $z = 3$, $A = \mathbb{F}_2^m \setminus \{0\}$. Two corrections: the method fails at $t = 5$ over general abelian groups by strict excess ($\mathbb{Z}_6 \setminus \{0\}$ gives $U_0 = 6/5$), and $\{\pm 1, \dots, \pm k\}$ is extremal only in its minimal ambient group: the obstruction is density, not symmetry.
Authors
- Zeno Lee
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-05
- DOI
- https://doi.org/10.5281/zenodo.23976156
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint