Order any subset of $\mathbb{F}_p\setminus\{0\}$ so that all partial sums are distinct (Erdős #475)
Statement
Let $p$ be a prime. Given any finite set $A\subseteq \mathbb{F}_p\setminus\{0\}$, is there always a rearrangement $A=\{a_1,\ldots,a_t\}$ such that the partial sums $\sum_{1\leq k\leq m}a_k$ (computed in $\mathbb{F}_p$) are pairwise distinct for $1\leq m\leq t$? An ordering with this property is called a valid ordering (also 'distinct partial sums' ordering).
Acceptance. FULLY RESOLVES: a complete proof that every finite $A\subseteq\mathbb{F}_p\setminus\{0\}$, for every prime $p$, admits a valid ordering — machine-checkable (Lean/Coq) preferred, else a full written proof; a hybrid proof (effective versions of the known asymptotic results plus a finite computation) is acceptable if the computation ships with code and an exhaustiveness certificate. OR a counterexample: an explicit prime $p$ and set $A$ together with a machine-checkable certificate (exhaustive-search transcript or SAT/UNSAT-style proof) that no ordering of $A$ has all partial sums distinct. ADVANCES: (a) verify the conjecture for ALL subsets of $\mathbb{F}_p\setminus\{0\}$ for every prime $p$ up to a stated bound, strictly beyond what the results in the background already cover, with reproducible code and an exhaustiveness certificate; (b) extend the proven ranges of $t$ (as functions of $p$) strictly beyond the best stated in the background, with proof; (c) make the 'sufficiently large' thresholds in any of the four regimes explicit, with proof. Deliver the proof file, or the search code + verified range + certificate.
Background
A problem of Graham, recorded by Erdős [Er73] and Erdős–Graham [ErGr80]; listed as open on erdosproblems.com/475 (fetched 2026-07-13, status 'decidable', tagged 'number theory | additive combinatorics'). Graham himself proved the case $t=p-1$ (the full set $\mathbb{F}_p\setminus\{0\}$), and Alspach conjectured the analogue for arbitrary abelian groups. The known frontier is substantial: the conjecture holds for all $t\leq 12$ (Costa–Pellegrini [CoPe20] and references therein) and for $p-3\leq t\leq p-1$ (Hicks–Ollis–Schmitt [HOS19] and references therein). Moreover it has been proved for all sufficiently large primes, by combining four regimes: small $A$ — Kravitz [Kr24] handled $t\leq \log p/\log\log p$ (independently observed earlier by Will Sawin on MathOverflow), improved by Bedert–Kravitz [BeKr24] to $t\leq e^{c(\log p)^{1/4}}$ and by Costa–Della Fiore [CoDe26] to $t\leq e^{c(\log p)^{1/3}}$; medium $A$ — Pham–Sauermann [PhSa26] proved it for any fixed $0<\alpha<1$ and all sufficiently large $t\leq p^{1-\alpha}$; large $A$ — Bedert–Bucić–Kravitz–Montgomery–Müyesser [BBKMM25] covered $p^{1-c}\leq t\leq (1-o(1))p$; very large $A$ — Müyesser–Pokrovskiy [MuPo25] covered $t\geq (1-o(1))p$. What remains is the small-prime regime: the asymptotic results have inexplicit/ineffective thresholds, so the full conjecture is 'resolved up to a finite check' that nobody can yet perform. For a given prime $p$ the unverified window is essentially $13\leq t\leq p-4$. The attacker's tool: per-prime exhaustive verification (backtracking or SAT over orderings of each subset, with symmetry reduction via dilation $A\mapsto \lambda A$), pushing the fully-verified prime bound upward; or effectivizing the constants in the asymptotic regimes.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #475 (T. F. Bloom) | website |
| REF-02 | MathOverflow 164300 — ordering subsets of the cyclic group to give distinct partial sums (Sawin's observation) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.