Graham's rearrangement conjecture and the repair of random orderings

Overview

Given a set of distinct nonzero residues modulo a prime, can we arrange them so that their successive partial sums never repeat? Graham’s 1971 conjecture asserts that we can. Huy Tuan Pham and Lisa Sauermann prove the missing range of set sizes; together with earlier work, their theorem establishes the conjecture for every sufficiently large prime (Pham & Sauermann, 2026).

Their argument starts with a random ordering and repairs its collisions by swapping nearby entries. The main analytic ingredient bounds the probability that a random subset of a prescribed size has a particular sum. The main combinatorial ingredient makes those bounds survive the dependence between overlapping intervals and the successive repairs.

The primary source is On Graham’s rearrangement conjecture, arXiv:2602.15797v1, posted February 17, 2026. The paper is the final contribution discussed in Quanta’s September 28 article. The theorem numbers below refer to this version.

🏷️ Distinct Partial Sums and Zero-Sum Intervals

Write ${\mathbb{F}}_p=\mathbb{Z}/p\mathbb{Z}$, where $p$ is prime, and let $S\subseteq {\mathbb{F}}_p\setminus \{0\}$ have size $n$. An ordering of $S$ is a sequence $(s_1,\dots ,s_n)$ that uses each element exactly once. Define its partial sums by

$$P_j=\sum _{i=1}^j{s}_i\in {\mathbb{F}}_p,1\le j\le n.$$

The ordering is valid when $P_1,\dots ,P_n$ are pairwise distinct. All sums in this post, except where real or complex quantities are explicitly introduced, are taken modulo $p$.

For $1\le i<j\le n$,

$$P_j-P_i=s_{i+1}+\cdots +s_j.$$

Consequently, validity is equivalent to

$$\sum _{r=a}^b{s}_r\ne 0\text{for every }2\le a\le b\le n.$$

The intervals of length one already have nonzero sums because $0\notin S$. Thus the forbidden configurations are precisely the zero-sum intervals $[a,b]$ with $2\le a<b\le n$.

The initial zero is excluded

The definition compares $P_1,\dots ,P_n$; it does not include $P_0=0$. For example, $(1,2,4)$ modulo $7$ is valid, with partial sums $(1,3,0)$. Requiring $P_0,\dots ,P_n$ to be distinct would be a stronger problem, impossible whenever ${\sum }_{s\in S}s=0$.

The empty set is vacuous, and a singleton is immediate. The difficulty is arranging larger sets whose elements have many additive relations. We cannot remove these relations from $S$; we must keep them from appearing in consecutive positions that produce repeated partial sums.

A local repair modulo seven

Consider the ordering $(1,2,5,3)$ in ${\mathbb{F}}_7$. Its partial sums are $(1,3,1,4)$, so $P_1=P_3$: the interval containing $2,5$ has sum zero. Swapping the last two entries gives $(1,2,3,5)$, whose partial sums $(1,3,6,4)$ are distinct.

The repeated residue is highlighted in the original ordering. Exchanging positions $3$ and $4$ changes only the third partial sum. This small example illustrates the operation; the theorem must also control the other collisions that an arbitrary swap could create.

More generally, exchange the entries at positions $b<y$ and put $\Delta =s_y-s_b$. The new partial sums satisfy the exact identity

$$P_j^{\prime }=\{\begin{array}{ll}{P}_j,& j<b,\\ P_j+\Delta ,& b\le j<y,\\ P_j,& j\ge y.\end{array}$$

Thus a swap translates one consecutive block of partial sums and leaves every other partial sum fixed. This localization is the basis of the proof.

🏷️ The Main Theorem and the Coverage of Set Sizes

Pham–Sauermann, Theorem 1.2

For every $\alpha \in (0,1)$ there is a constant $C_{\alpha }>0$ such that, for every prime $p$ and every $S\subseteq {\mathbb{F}}_p\setminus \{0\}$ satisfying

$$C_{\alpha }\le |S|\le p^{1-\alpha },$$

the set $S$ has a valid ordering (Pham & Sauermann, 2026).

The quantifiers matter: $\alpha$ is fixed first, and the lower threshold may depend on it. The theorem covers every set in the indicated range, regardless of its additive structure.

The preceding results and the new theorem occupy the following ranges. Here $c>0$ is an absolute constant from the large-set theorem; it can be taken smaller than $1$.

Contribution	Range of $n$	Main method
Müyesser–Pokrovskiy, preprint 2022	$n\ge (1-o(1))p$	Random constructions and absorption
Bedert–Kravitz, preprint 2024	$n\le \exp ((\log p{)}^{1/4})$	Additive structure and dissociated sets
Bedert–Bucić–Kravitz–Montgomery–Müyesser, 2025	$n\ge p^{1-c}$	Expansion and absorption
Pham–Sauermann, 2026	$C_{\alpha }\le n\le p^{1-\alpha }$	Anti-concentration and local swaps

The first two preprints subsequently appeared in Inventiones Mathematicae and Israel Journal of Mathematics, respectively (Müyesser & Pokrovskiy, 2025; Bedert & Kravitz, 2026). The 2025 paper also treats other groups, including a much more complete result over ${\mathbb{F}}_2^d$ (Bedert et al., 2025).

To see the coverage explicitly, choose $\alpha =c/2$. The new theorem reaches $p^{1-c/2}$, which exceeds the starting point $p^{1-c}$ of the large-set theorem. For sufficiently large $p$ we also have

$$C_{c/2}\le \exp ((\log p{)}^{1/4}),$$

so the small-set result reaches the lower endpoint of the new theorem. Every possible cardinality is covered.

Scope of the conclusion

The combined result establishes Graham’s conjecture for all sufficiently large primes. It does not establish the original statement for every prime, and the paper does not supply a numerical prime threshold together with a verification of all smaller cases.

🏷️ Anti-Concentration for Sampling Without Replacement

For a random variable $Z$ taking values in ${\mathbb{F}}_p$, its largest point probability is

$$q(Z)=\underset{z\in {\mathbb{F}}_p}{\max }\mathbb{P}(Z=z).$$

An anti-concentration bound is an upper bound on this quantity. A uniform residue has $q(Z)=1/p$. In this problem, $Z$ is a sum of a uniformly chosen subset of fixed size, and its distribution need not be close to uniform.

For $R\subseteq S$, write $\Sigma (R)={\sum }_{x\in R}x$. If $R$ is a uniform $m$-element subset, define $q_m(S)=q(\Sigma (R))$.

Fixed-size subset sums, Theorem 1.3

There is an absolute constant $C>0$ such that, for every prime $p$, every set $S\subseteq {\mathbb{F}}_p$ of size $n\ge 2$, and every integer

$$C\log n\le m\le \frac{10^{-3}n}{\log n},$$

one has

$$q_m(S)\le \frac{1}{p}+\frac{C}{n\sqrt{m}}.$$

Zero is allowed in $S$ for this analytic statement (Pham & Sauermann, 2026).

The scale $n\sqrt{m}$ is natural. For example, if $S$ is an interval of $n$ integers and $m$ is well below $n$, a sample sum has standard deviation of order $n\sqrt{m}$. A local central limit heuristic would therefore predict point probabilities of order $1/(n\sqrt{m})$ before modular wraparound becomes important. This heuristic explains the scale; the theorem proves a uniform bound for arbitrary sets without assuming a limit law.

A useful elementary estimate follows by exposing $m-1$ selected elements first. To achieve a prescribed total, at most one remaining element can be chosen last. Hence

$$q_m(S)\le \frac{1}{n-m+1}.$$

Combining this observation with Theorem 1.3 gives the paper’s Corollary 1.4: for each $\epsilon \in (0,1)$ there is $C_{\epsilon }^{\prime }$ such that

$$q_m(S)\le \frac{1}{p}+\frac{C_{\epsilon }^{\prime }\sqrt{\log n}}{n\sqrt{m}},1\le m\le (1-\epsilon )n.$$

For large $m$, expose most of the sample and leave approximately $\epsilon n/(1000\log n)$ elements to choose. The remaining population still contains at least $\epsilon n$ elements. Conditional on the exposed part, Theorem 1.3 applies to the final sample. For small $m$, the elementary estimate suffices. These two arguments explain both the enlarged range and the logarithmic loss.

The identity $\Sigma (R)=\Sigma (S)-\Sigma (S\setminus R)$ also gives $q_m(S)=q_{n-m}(S)$. In particular, for $1\le m<n$,

$$q_m(S)\le \frac{1}{p}+\frac{C_{1/2}^{\prime }\sqrt{\log n}}{n\sqrt{\min \{m,n-m\}}}.$$

The limitation of a direct union bound

Each fixed interval of length $m$ in a random ordering contains a uniform $m$-element subset. If $N$ counts the forbidden zero-sum intervals, the preceding bound gives

$$\begin{array}{rl}\mathbb{E}N& \le \sum _{m=2}^{n-1}(n-m)\left(\frac{1}{p}+\frac{C_{1/2}^{\prime }\sqrt{\log n}}{n\sqrt{\min \{m,n-m\}}}\right)\\ & =O\left(\frac{n^2}{p}+\sqrt{n\log n}\right).\end{array}$$

This estimate does not force $\mathbb{E}N<1$ in the required range. It therefore cannot certify an ordering with no collisions merely by applying the first-moment method to $N$.

The proof instead controls collisions locally. For a fixed right endpoint, summing the same kind of bounds over possible left endpoints produces a quantity of order

$$\frac{n}{p}+\sqrt{\frac{\log n}{n}},$$

which tends to zero when $n\le p^{1-\alpha }$ and $n\to \infty$. There can be many collisions in total while any particular location is unlikely to need repair.

🏷️ Fourier Analysis of a Random Subset Sum

Throughout this section, $n$ and $m$ satisfy the hypotheses of Theorem 1.3, and logarithms are natural.

The constraint $|R|=m$ makes the membership indicators of $R$ dependent. Pham and Sauermann recover conditional independence by changing the sampling procedure.

Randomly partition $S$ into labeled parts $S_1,\dots ,S_m$ with sizes differing by at most one. Given the partition, choose independent uniform elements $X_i\in S_i$, and set $R=\{X_1,\dots ,X_m\}$.

The resulting $R$ is a uniform $m$-element subset: its distribution is invariant under every permutation of the elements of $S$, and all its outcomes have size $m$. Conditional on the partition, however, the sum $\Sigma (R)=X_1+\cdots +X_m$ is a sum of independent variables.

Character orthogonality and Fourier decay

For $u\in {\mathbb{F}}_p$, put $e_p(u)=\exp (2\pi i\tilde{u}/p)$, where $\tilde{u}$ is any integer representative. Character orthogonality gives

$$1_{\{u=0\}}=\frac{1}{p}\sum _{\xi \in {\mathbb{F}}_p}{e}_p(\xi u).$$

For a fixed partition $\mathcal{S}=(S_1,\dots ,S_m)$, independence therefore yields

$$\begin{array}{rl}\mathbb{P}(\Sigma (R)=z\mid \mathcal{S})& =\frac{1}{p}\sum _{\xi \in {\mathbb{F}}_p}{e}_p(-\xi z)\prod _{i=1}^m\left(\frac{1}{|S_i|}\sum _{x\in S_i}{e}_p(\xi x)\right)\\ & \le \frac{1}{p}\sum _{\xi \in {\mathbb{F}}_p}\prod _{i=1}^m\left|\frac{1}{|S_i|}\sum _{x\in S_i}{e}_p(\xi x)\right|.\end{array}$$

Define the normalized distance of a residue to zero by

$$\Vert u{\Vert }_p=\underset{k\in \mathbb{Z}}{\min }\left|\frac{\tilde{u}}{p}-k\right|.$$

Squaring a Fourier factor turns it into an average over pairs. The elementary inequality $\cos (2\pi t)\le 1-2\Vert t{\Vert }_{\mathbb{Z}}^2$ gives

$${\left|\frac{1}{|S_i|}\sum _{x\in S_i}{e}_p(\xi x)\right|}^2\le 1-\frac{2}{|S_i{|}^2}\sum _{x,x^{\prime }\in S_i}\Vert \xi (x-x^{\prime }){\Vert }_p^2.$$

Using $\sqrt{1-2u}\le e^{-u}$ when $0\le 2u\le 1$, we obtain

$$\mathbb{P}(\Sigma (R)=z\mid \mathcal{S})\le \frac{1}{p}\sum _{\xi \in {\mathbb{F}}_p}{e}^{-{\psi }_{\mathcal{S}}(\xi )},$$

where

$${\psi }_{\mathcal{S}}(\xi )=\sum _{i=1}^m\frac{1}{|S_i{|}^2}\sum _{x,x^{\prime }\in S_i}\Vert \xi (x-x^{\prime }){\Vert }_p^2.$$

A frequency contributes substantially only if the phases within the parts are unusually aligned. The zero frequency always contributes exactly $1/p$.

Comparing random and deterministic phase energies

Introduce the deterministic quantity

$$\Psi (\xi )=\frac{m}{n^2}\sum _{x,x^{\prime }\in S}\Vert \xi (x-x^{\prime }){\Vert }_p^2,F_t=\{\xi \in {\mathbb{F}}_p:\Psi (\xi )\le t\}.$$

Here $F_t$ measures alignment in the entire set, independently of the random partition. For positive integers $t$, the paper proves two complementary facts:

• If $\xi \notin F_{2000t}$ and $\xi \ne 0$, then ${\mathbb{P}}_{\mathcal{S}}({\psi }_{\mathcal{S}}(\xi )<2t)\le n^{-9}$.
• For integers $1\le t\le m/2000$, one has $|F_t|\le 1+200p\sqrt{t}/(n\sqrt{m})$.

The first assertion is a sampling estimate. If no short arc contains most of the phases $\xi S$, a random part contains many pairs with separated phases. If most phases lie in a short arc but $\Psi (\xi )$ is large, the remaining phases contribute substantial squared distance, and random parts pair them with the concentrated majority. Hypergeometric concentration controls both cases. The assumption $m\le 10^{-3}n/\log n$ ensures that every part is large enough for these estimates (Pham & Sauermann, 2026, sec.3).

The second assertion supplies the factor $1/n$ in the theorem. Its proof connects Fourier orthogonality to growth of sumsets.

Proof of the deterministic frequency bound

Fix $t$ and define

$$Q_{\delta }=\left\{x\in {\mathbb{F}}_p:\sum _{\xi \in F_t}\Vert \xi x{\Vert }_p^2<\delta |F_t|\right\}.$$

For independent uniform $Y,Y^{\prime }\in S$, the definition of $F_t$ gives

$$\mathbb{E}\sum _{\xi \in F_t}\Vert \xi (Y-Y^{\prime }){\Vert }_p^2\le |F_t|t/m.$$

Markov’s inequality implies $\mathbb{P}(Y-Y^{\prime }\in Q_{10t/m})\ge 9/10$. Fixing a suitable value of $Y^{\prime }$ then shows

$$|Q_{10t/m}|\ge 9n/10.$$

On the other hand, $F_t=-F_t$, and for $x\in Q_{1/200}$ the inequality $\cos (2\pi u)\ge 1-20\Vert u{\Vert }_{\mathbb{Z}}^2$ implies

$$\sum _{\xi \in F_t}{e}_p(\xi x)\ge \frac{9}{10}|F_t|.$$

Orthogonality gives the exact identity

$$\sum _{x\in {\mathbb{F}}_p}{\left|\sum _{\xi \in F_t}{e}_p(\xi x)\right|}^2=p|F_t|,$$

and hence $|Q_{1/200}|\le 5p/(4|F_t|)$.

The triangle inequality and Cauchy–Schwarz also imply $k{Q}_{\delta }\subseteq Q_{k^2\delta }$, where $kQ$ denotes the sum of $k$ copies of $Q$. Choose

$$k=\lfloor \sqrt{\frac{m}{2000t}}\rfloor .$$

Then $k{Q}_{10t/m}\subseteq Q_{1/200}$. If $|F_t|\ge 2$, the upper bound on $|Q_{1/200}|$ makes this a proper subset of ${\mathbb{F}}_p$. The Cauchy–Davenport theorem, $|A+B|\ge \min \{p,|A|+|B|-1\}$ for nonempty subsets of ${\mathbb{F}}_p$, consequently gives

$$\frac{4}{5}kn\le 1+k(|Q_{10t/m}|-1)\le |k{Q}_{10t/m}|\le \frac{5p}{4|F_t|}.$$

In the range under consideration $n$ is large, and $k\ge 10^{-2}\sqrt{m/t}$. Rearranging yields $|F_t|\le 200p\sqrt{t}/(n\sqrt{m})$. The case $|F_t|=1$ is covered by adding $1$ to the bound.

For integers $1\le t\le m/2000^2$, these two facts imply

$${\mathbb{E}}_{\mathcal{S}}\#\{\xi \ne 0:{\psi }_{\mathcal{S}}(\xi )<2t\}\le \frac{p}{n^9}+\frac{200p\sqrt{2000t}}{n\sqrt{m}}.$$

Divide frequencies into the ranges $\psi <1$ and $2^{\ell }\le \psi <2^{\ell +1}$. The resulting sum contains the convergent numerical series

$$\sum _{\ell \ge 0}{2}^{\ell /2}{e}^{-2^{\ell }}<\infty .$$

The larger-energy tail is exponentially small in $m$, and $m\ge C\log n$ makes it negligible. Averaging the conditional Fourier bound now gives $q_m(S)\le 1/p+C/(n\sqrt{m})$, as asserted.

🏷️ Joint Bounds for Nested Random Subsets

Overlapping intervals are dependent. A bound for one sum cannot simply be multiplied by itself to control several collisions. The paper’s Corollary 4.2 handles the relevant dependence explicitly.

Let $R_1\subset \cdots \subset R_k\subset S$ be a uniform chain with prescribed sizes $1\le m_1<\cdots <m_k<n$. Put $m_0=0$, $m_{k+1}=n$, and

$$h_k(r)=\frac{1}{p}+\frac{C_k\sqrt{\log n}}{n\sqrt{r}},r\ge 1,$$

where $C_k$ depends only on $k$. Then, for any prescribed residues $z_1,\dots ,z_k$,

$$\mathbb{P}(\Sigma (R_i)=z_i\text{ for all }i)\le \sum _{j=0}^k\prod _{\begin{array}{c}0\le i\le k\\ i\ne j\end{array}}{h}_k(m_{i+1}-m_i).$$

To understand the missing factor in each product, choose a largest gap $m_{j+1}-m_j\ge n/(k+1)$. Expose the successive differences up to $R_j$ from the left, then expose $S\setminus R_k$ and the remaining differences from the right. Leave the largest gap unexposed.

At every stage, at least $n/(k+1)$ elements remain as a reserve. Conditional on everything already revealed, the next block is still a uniform subset of the remaining population, and Corollary 1.4 applies with $\epsilon =1/(k+1)$. If the current population has size $N$, then $N\ge n/(k+1)$ and $\log N\le \log n$; thus we may take $C_k=(k+1)C_{1/(k+1)}^{\prime }$ when expressing each bound using the original size $n$. Multiplying these conditional bounds proves the product associated with the chosen gap. Summing over possible gaps gives the displayed symmetric form.

Moreover, Lemma 4.3 shows that the sum of these bounds over all possible sizes is at most

$$\sum _{1\le m_1<\cdots <m_k<n}\sum _{j=0}^k\prod _{\begin{array}{c}0\le i\le k\\ i\ne j\end{array}}{h}_k(m_{i+1}-m_i)\le (k+1){\left(\frac{n}{p}+\frac{2C_k\sqrt{\log n}}{\sqrt{n}}\right)}^k.$$

The calculation uses ${\sum }_{r=1}^n{r}^{-1/2}\le 2\sqrt{n}$, successively summing the gaps on either side of the omitted one. This is why even the union over many possible interval lengths can be controlled: each additional prescribed sum contributes another small factor (Pham & Sauermann, 2026, sec.4).

🏷️ A Deterministic Repair Argument

It suffices to prove the main theorem for $0<\alpha <1/2$: a theorem for a smaller positive $\alpha$ also covers the smaller range belonging to a larger one, after increasing its lower threshold. Set

$$D=\lceil 3/\alpha \rceil .$$

Represent an ordering by a bijection $\sigma :\{1,\dots ,n\}\to S$. Let $B(\sigma )$ be the set of right endpoints of its forbidden zero-sum intervals:

$$B(\sigma )=\left\{b\in \{3,\dots ,n\}:\text{there is }2\le a<b\text{ with }\sum _{r=a}^b\sigma (r)=0\right\}.$$

Call a permutation of the positions admissible if it is a product of transpositions with disjoint supports, each exchanging two positions at distance at most $5D$. The repairs will always have this form.

For an admissible $\pi$, a bad endpoint $b$, and $b<y\le b+5D$, consider exchanging $b$ and $y$ in the ordering $\sigma \circ \pi$. Call $y$ blocked if, after that exchange, some forbidden zero-sum interval $[a,t]$ satisfies

$$a\in \{b+1,\dots ,y\}\text{or}t\in \{b,\dots ,y-1\}.$$

These are precisely the possible boundary locations that the proof needs to exclude. In particular, an interval containing exactly one of the exchanged positions satisfies one of these conditions.

Three properties of a suitable starting ordering

Section 5 of the paper proves that a uniform random $\sigma$ avoids the following events with the indicated probability bounds:

Event	Obstruction	Probability at most
${\mathcal{B}}_1$	Some $b\in B(\sigma )$ lies in $[n-30D,n]$	$1/100$
${\mathcal{B}}_2$	Some $[z-10D,z+10D]$ contains more than $D$ elements of $B(\sigma )$	$3/100$
${\mathcal{B}}_3$	For some $b\in B(\sigma )$ and admissible $\pi$ fixing every position before $b$, at least $2D$ candidate positions $y\in (b,b+5D]$ are blocked	$1/25$

The third property is uniform over all such $\pi$, so it remains applicable after the choices made during earlier repairs. The union bound gives

$$\mathbb{P}({\mathcal{B}}_1\cup {\mathcal{B}}_2\cup {\mathcal{B}}_3)\le \frac{1}{100}+\frac{3}{100}+\frac{1}{25}=\frac{2}{25}.$$

Thus at least $23/25$ of the initial orderings have the required properties, under the theorem’s size assumptions. This is a probability of being repairable by the argument, not a claim that the original ordering already has distinct partial sums.

Processing the bad endpoints from right to left

Fix an ordering outside these three events, and write

$$B(\sigma )=\{b_1,\dots ,b_{\ell }\},b_1>\cdots >b_{\ell }.$$

At stage $j$, exchange $b_j$ with a suitable $y_j\in (b_j,b_j+5D]$. We maintain two conditions: all exchanged positions are distinct, and every zero-sum interval remaining after stage $j$ has right endpoint among $b_{j+1},\dots ,b_{\ell }$.

Because the earlier endpoints were larger, all previous swaps fix every position at or before $b_j$. The third property therefore applies to their composition. There are $5D$ candidates for $y_j$, and at most $2D$ are blocked. At most $D$ are original bad endpoints. At most $D$ are partners used by earlier swaps: any such partner is within $5D$ of its own bad endpoint, which must consequently lie within $10D$ of $b_j$.

There are therefore at least

$$5D-2D-D-D=D>0$$

available choices. The first property ensures that all candidate positions lie inside the ordering. Choose an unused, unblocked candidate that is not an original bad endpoint.

Now consider any zero-sum interval after this exchange. Since $y_j$ was unblocked, its boundaries avoid the two ranges in the definition of blockedness. The interval must therefore contain either both exchanged positions or neither, so its sum has not changed. By the preceding invariant, its right endpoint belonged to $\{b_j,\dots ,b_{\ell }\}$. It cannot end at $b_j$, since that would put its right endpoint in $[b_j,y_j-1]$. Hence it ends at one of the still unprocessed endpoints.

This proves the invariant at the next stage. After all $\ell$ stages, no forbidden zero-sum interval remains, and the ordering is valid.

🏷️ Probability Estimates Behind the Repair Properties

The deterministic argument reduces the theorem to the three probability bounds. Their proofs explain why both the strength and the conditional form of anti-concentration are necessary.

Bad endpoints near the end

The chain estimate with $k=1$, summed over possible left endpoints, gives

$$\mathbb{P}(b\in B(\sigma ))\le \frac{2n}{p}+\frac{4C_1\sqrt{\log n}}{\sqrt{n}}.$$

Since $n\le p^{1-\alpha }$, we have $n/p\le n^{-\alpha }$. Since $\alpha <1/2$, choosing $C_{\alpha }$ sufficiently large also ensures $4C_1\sqrt{\log n}/\sqrt{n}\le n^{-\alpha }$. Thus the preceding probability is at most $3n^{-\alpha }$. Summing over the final $30D+1$ positions proves the bound on ${\mathcal{B}}_1$.

Clusters of nearby bad endpoints

A preliminary estimate gives $\mathbb{P}({\mathcal{B}}_0)\le 1/100$ for the following auxiliary event: near some bad endpoint $b\le n-30D$, two distinct subsets of the positions $[b,b+20D]$ have equal sums.

For fixed distinct subsets, choose a position in their symmetric difference and expose every other position in the local block. Their equality determines at most one value at the unexposed position, among $n-20D$ remaining elements, costing a factor at most $2/n$. Conditional on the completed local block, the probability that $b$ is a bad endpoint is at most $4n^{-\alpha }$. The joint probability is therefore at most $8n^{-1-\alpha }$. There are at most $n{2}^{40D+2}$ choices of the endpoint and the two subsets, so a union bound suffices once $n$ is large in terms of $D$.

Outside ${\mathcal{B}}_0\cup {\mathcal{B}}_1$, a cluster of $D+1$ bad endpoints forces $D$ zero-sum intervals with distinct left endpoints lying before the cluster. Indeed, equal left endpoints would make the segment between two right endpoints sum to zero, contradicting the distinctness of local subset sums. A left endpoint inside the local block would cause the same contradiction.

Expose the local block. The remaining portions of these intervals form nested uniform random subsets, and their required sums are now fixed. The summed chain estimate bounds their probability, for fixed local endpoint data, by

$$(D+1)(2n^{-\alpha }{)}^D\le (D+1)2^D{n}^{-3},$$

because $\alpha D\ge 3$. The remaining choices contribute at most $n(20D{)}^D$. This leaves a quantity tending to zero and, together with the two preliminary exceptions, gives $\mathbb{P}({\mathcal{B}}_2)\le 3/100$.

Uniform control after previous swaps

The event ${\mathcal{B}}_3$ is more delicate: the previous permutation may depend on the ordering. A bound for each fixed permutation would not by itself handle all possible repair histories.

The proof reduces this apparent proliferation of permutations to bounded local data. For any proposed family of $D$ obstructing intervals, discard every previous transposition that exchanges either two positions inside or two positions outside each relevant set. Those transpositions do not change the sums in question.

Every remaining transposition crosses a relevant boundary. Because its length is at most $5D$, its endpoints lie near one of only $O(D)$ boundaries. The number of relevant positions is therefore $O(D^2)$. The paper bounds the number of relevant admissible permutations, for fixed interval endpoints, by $D^{14D^2}$, independently of $n$.

Outside ${\mathcal{B}}_0\cup {\mathcal{B}}_1$, if $2D$ candidates are blocked, at least $D$ obstructions extend to the same side of the local block. The distinctness of local subset sums forces their distant endpoints to be distinct. After fixing a relevant permutation and exposing the local block, these distant parts again form a chain of uniform subsets. Summing the chain estimates and the bounded number of local configurations proves $\mathbb{P}({\mathcal{B}}_3)\le 1/25$ (Pham & Sauermann, 2026, sec.5).

This localization is essential: it is what lets the probabilistic estimate cover the adaptive sequence of swaps used in the deterministic argument.

🏷️ Consequences and Remaining Questions

The method gives an existence proof through a concrete repair procedure. Under its hypotheses, a random starting ordering has probability at least $23/25$ of satisfying conditions that guarantee success. The constants depend strongly on $\alpha$, so this estimate does not by itself provide useful numerical guarantees for small inputs.

The analytic theorem is also a separate contribution. It controls sums drawn without replacement from an arbitrary set and provides enough uniformity to be applied after partial exposure. The largest-gap argument then turns that single-sum statement into estimates for many dependent sums.

Primality enters substantively through Cauchy–Davenport in the frequency bound. In a general finite abelian group, a subset can lie in a proper subgroup and its sum distribution can be supported there, preventing a uniform bound of the same form with $1/|G|$. The paper discusses extensions to other groups as future work; its main theorem is about prime cyclic groups.

For Graham’s original conjecture, the remaining qualification is the restriction to sufficiently large primes in the combined conclusion. The proof shows that every set size is covered once the prime is large enough. It supplies neither a proof for every prime nor an exhaustive computation that removes that qualification.

Links

• on cap sets and the polynomial method studies additive relations in finite fields through polynomial rank bounds. Here additive relations are allowed in the set, while the ordering prevents them from forming forbidden intervals.
• on the lower bound of Ramsey number develops another probabilistic existence argument in which controlling dependent bad events is central. In the rearrangement problem, a deterministic repair procedure is added to the random construction.
• on sum-product in finite fields via entropy gives a complementary use of additive structure and distributional estimates over prime fields.

📚 References

🐻  Bedert, B. & Kravitz, N. 2026. Graham’s rearrangement conjecture beyond the rectification barrier. Israel Journal of Mathematics 273, 471–500.

🐻  Bedert, B., Bucić, M., Kravitz, N., Montgomery, R. & Müyesser, A. 2025. On Graham’s rearrangement conjecture over 𝔽₂ⁿ.

🐻  Müyesser, A. & Pokrovskiy, A. 2025. A random Hall-Paige conjecture. Inventiones Mathematicae 240(3), 779–867.

🐻  Pham, H.T. & Sauermann, L. 2026. On Graham’s rearrangement conjecture.