betaFeedback

WorksMathematics

Distinct partial products in prime dihedral groups

Abstract

Let D2pD_{2p} be the dihedral group of order 2p2p, where pp is prime. For every fixed 0<α<10<\alpha<1, we prove that every subset A⊆D2p∖{e}A\subseteq D_{2p}\setminus\{e\} with Cα≤∣A∣≤pαC_\alpha\le |A|\le p^\alpha admits an ordering whose nonempty partial products are pairwise distinct. Combined with the known small- and large-set theorems, this covers every subset size for all sufficiently large primes. Pairing reflections reduces the products to partial sums with fixed parity-labelled offsets. Two passes of block rotations remove distant collisions; bounded displacement allows the local condition to exclude the remaining collisions. The existence of suitable rotations follows from Pham–Sauermann's subset-sum anticoncentration theorem, an affine-rank estimate, and a count of clustered collision witnesses.

Introduction

An ordering a1,…,ana_1,\ldots,a_n of a finite subset AA of a group is valid if its nonempty partial products

P1=a1,P2=a1a2,…,Pn=a1⋯anP_1=a_1,\quad P_2=a_1a_2,\quad\ldots,\quad P_n=a_1\cdots a_n

are pairwise distinct. The empty product P0=eP_0=e is excluded from this condition. Graham [7 Problem 10, p. 36] asked whether every subset of Zp∖{0}\mathbb{Z}_p \setminus\{0\} has a valid ordering, for every prime pp; the question was repeated by Erdős and Graham [6 p. 95]. The corresponding nonabelian problem asks for distinct partial products. We consider the dihedral group D2pD_{2p} of order 2p2p.

Theorem 1.1. For every 0<α<10 < \alpha< 1 there is an integer CαC_\alpha such that, for every prime pp, every subset A⊆D2p∖{e}A \subseteq D_{2p} \setminus\{e\} satisfying

Cα≤∣A∣≤pαC_\alpha\leq|A| \leq p^\alpha

has a valid ordering.

Corollary 1.2. For all sufficiently large primes pp, every subset of D2p∖{e}D_{2p} \setminus\{e\} has a valid ordering.

The proof of Corollary 1.2 uses the eventual overlap of three size ranges and leaves a finite set of primes untreated. The assertion for every prime is unresolved. The constants in Theorem 1.1 are not optimised.

The size range in Theorem 1.1 lies between two existing results. The small-set theorem [4 Theorem 1.3] gives a stronger sequencing property for dihedral subsets of size at most exp⁡(cs(log⁡p)1/4)\exp(c_s(\log p)^{1/4}), with an absolute cs>0c_s > 0. It extends the small-set method of Bedert and Kravitz [2] to suitable semidirect products. The general large-set theorem [3 Theorem 1.4] guarantees that, for an absolute c>0c > 0, every subset S⊆G∖{e}S \subseteq G \setminus\{e\} of any finite group GG with ∣S∣≥∣G∣1−c|S| \ge|G|^{1-c} has a valid ordering. These ranges overlap the range of Theorem 1.1 for a suitable fixed α<1\alpha< 1, giving Corollary 1.2.

Ollis [12] studied distinct partial products in dihedral groups. For prime cyclic groups, Pham and Sauermann [13, Theorem 1.2] proved the intermediate range $C_\alpha \le |A| \le p^\alpha$, and hence Graham’s conjecture for sufficiently large primes. Their exponent is written $1-\alpha$; we have reparametrised it. Their proof combines subset-sum anticoncentration with local changes to a random ordering. The dihedral intermediate range is explicitly identified as a further problem after extensions to cyclic groups {citep}[5 Section 7]. {xref}Theorem 1.1` supplies that range by an additive reduction which retains the signs caused by reflections.

There is also a graph formulation. In the directed Cayley graph, give the edge g→gag \to ga colour aa. For nonempty AA, a valid ordering exists if and only if some a∈Aa \in A can be omitted so that the remaining colours form a simple directed rainbow path. Indeed, left multiplication of P1,…,PnP_1,\ldots,P_n by a1−1a_1^{-1} gives the distinct prefixes, including the empty prefix, of a2,…,ana_2,\ldots,a_n. Conversely, prepending the omitted element to such an ordering translates its entire prefix list. This equivalence explains the endpoint convention: a simple path using all colours would impose the additional requirement that P0P_0 be distinct from every PjP_j.

The proof

Write D2p=Fp⋊Z2D_{2p} = \mathbb{F}_p \rtimes\mathbb{Z}_2, with

(x,ϵ)(y,δ)=(x+(−1)ϵy,ϵ+δ).(x,\epsilon)(y,\delta) = (x + (-1)^\epsilon y,\epsilon+\delta).

A reflection reverses every subsequent sign until the next reflection. Pairing reflections into cells of length at most four produces m≥∣A∣/4m \ge|A|/4 variable positions, all with coefficient +1+1. After the other entries have been fixed, the variables x1,…,xmx_1,\ldots,x_m form a uniform permutation of a fixed subset of Fp\mathbb{F}_p. Every partial product in cell jj then belongs to

sj+Dj,sj=∑h≤jxh,Dj⊆Fp×Z2,∣Dj∣≤4.s_j + D_j,\qquad s_j = \sum_{h \le j} x_h,\qquad D_j \subseteq\mathbb{F}_p \times\mathbb{Z}_2,\qquad|D_j| \le4.

where the sets DjD_j remain attached to their positions when variables are permuted. Parity-preserving permutations in semidirect products already appear in [4 Section 2].

For each fixed KK, the permutation local lemma gives a probability cK>0c_K > 0 that every short identity subword is absent, even after arbitrary variable permutations in any window of at most KK cells. The lower bound is uniform in the ratio of the rotation and reflection counts. For a small reflection pool, a pattern count proportional to its size cancels the corresponding probability denominator; see Appendix § 10. Separately, with probability tending to one on every fixed-decoration fibre, each member of a predetermined linear-size family of blocks has a cyclic rotation avoiding all distant target sets. Two staggered passes of these rotations preserve selected cut sums and move every variable by a bounded distance. Any remaining collision can therefore be reproduced by a permutation inside an original bounded window, contradicting the local condition.

The distant-avoidance estimate uses the sharp subset-sum theorem [13 Theorem 1.3]. If all ℓ\ell cyclic rotations of one block fail, one collision per rotation gives an affine system Hx=zHx = z. Suppose its target anchors form qq clusters separated from the source cluster. The affine dimension of the columns of HH is at least (ℓ+q)/2(\ell+ q)/2; long gaps also supply qq independent differences of repeated columns. Conditioning on disjoint position pools then yields

Pr⁡(Hx=z)=O(m−(ℓ+q)/2−ηq),η=min⁡{β,1/6},p≥m1+β.\Pr(Hx = z) = O\left(m^{-(\ell+q)/2-\eta q}\right), \qquad\eta= \min\{\beta, 1/6\}, \qquad p \ge m^{1+\beta}.

With gap scale m1/3m^{1/3}, there are O(mqm(ℓ−q)/3)O(m^q m^{(\ell-q)/3}) anchor tuples, giving a total of O(m−ηℓ)O(m^{-\eta\ell}). Clustered targets have fewer possible locations; separated targets give stronger anticoncentration. This balance permits a union bound over the entire repair family.

The reservoir exposure is related to the chain estimate [13 Corollary 4.2] and to the standard rank-exposure argument [11]; see also [9 Lemma 3.7]. The boundary constraints [2 Section 6] and transposition repairs [13 Section 5] are antecedents of the random-ordering and local-repair approach. The fixed-offset calculation, the repeated-column estimate and the two-pass rotation argument are proved below.

Cells and fixed offsets

For an odd prime pp, use coordinates

D2p=Fp⋊Z2,(x,ϵ)(y,δ)=(x+(−1)ϵy,ϵ+δ).D_{2p} = \mathbb{F}_p \rtimes\mathbb{Z}_2, \qquad(x,\epsilon)(y,\delta) = (x + (-1)^\epsilon y, \epsilon+ \delta).

Let A⊆D2p∖{e}A \subseteq D_{2p} \setminus\{e\} be nonempty. Write R⊆Fp×R \subseteq\mathbb{F}_p^\times and F⊆FpF \subseteq\mathbb{F}_p for its rotation and reflection coordinate sets, and put r=∣R∣r = |R|, f=∣F∣f = |F| and n=r+fn = r + f. Coordinates within either pool are distinct; the two pools may intersect. For s∈Fps \in\mathbb{F}_p and (c,ϵ)∈Fp×Z2(c,\epsilon) \in\mathbb{F}_p \times\mathbb{Z}_2, write s+(c,ϵ)=(s+c,ϵ)s + (c,\epsilon) = (s+c,\epsilon).

Lemma 2.1. There is a random arrangement of AA into mm consecutive cells, each beginning with a variable, such that n/4≤m≤nn/4 \le m \le n and every cell has length at most four. All variables have the same type and distinct coordinates. Conditional on the nonvariable entries and the variable coordinate set XX, their coordinates x1,…,xmx_1,\ldots,x_m form a uniform permutation of XX. There are fixed sets Dj⊆Fp×Z2D_j \subseteq\mathbb{F}_p \times\mathbb{Z}_2, ∣Dj∣≤4|D_j| \le4, such that, for every assignment of XX to the variables, the nonempty prefixes ending in cell jj are exactly

sj+Dj,sj=∑h=1jxh.(1)s_j + D_j, \qquad s_j = \sum_{h=1}^{j} x_h. \tag*{(1)}

The prefixes within each cell are pairwise distinct for every assignment.

Proof. In the rotation-majority case r≥fr \ge f, take m=rm = r cells, each starting with a variable rotation. For f=2tf = 2t, append two reflection slots to each of tt distinct cells. For f=2t+1f = 2t + 1, reserve the last cell for one reflection and append two reflections to each of tt earlier cells. Any such choice of cells is allowed and is fixed before sampling. The reservation is feasible since 2t+1≤m2t + 1 \le m implies t≤m−1t \le m - 1. The types are

(R),(R,F,F),possibly a final (R,F).(R), \qquad(R,F,F), \qquad\text{possibly a final }(R,F).

Choose independent uniform assignments of RR and FF to their slots, with an empty permutation space interpreted as a singleton. Conditioning on the reflections leaves a uniform permutation of X=RX = R. Here m≥n/2m \ge n/2, and each cell has length at most three. In the reflection-majority case f>rf > r, start with ff successive reflection slots. Choose arbitrary distinct reflection slots after which to place the rotations, and fix an arbitrary bijection from these rotation slots to RR before sampling. Only the reflection assignment is random in this case. Assign FF uniformly to its slots, pair successive reflections into cells and retain each following rotation in its reflection’s cell. The types are

(F,[R],F,[R]),(F,[R],F,[R]),

possibly a final (F,[R])(F,[R]), where brackets indicate optional entries and odd reflection slots are variable. Then m=⌈f/2⌉>n/4m = \lceil f/2\rceil> n/4, and cells have length at most four. Conditioning on the even reflection slots leaves a uniform bijection from the odd slots to the remaining set XX.

Every nonfinal cell has even reflection parity, so the prefix preceding each variable has parity zero and its coordinate has coefficient +1+1. Permutations within fixed parity classes that preserve the total product in a semidirect product also occur in [4 Section 2]. Let ϵ∗∈Z2\epsilon_* \in\mathbb{Z}_2 be the common variable type. If cell jj has djd_j fixed entries following its variable, let (uj,h,vj,h)(u_{j,h},v_{j,h}) be the product of their first hh entries, including (uj,0,vj,0)=(0,0)(u_{j,0},v_{j,0})=(0,0). Set

C0=0,Cj=Cj−1+(−1)ϵ∗uj,dj,C_0=0,\qquad C_j=C_{j-1}+(-1)^{\epsilon_*}u_{j,d_j},
Dj={(Cj−1+(−1)ϵ∗uj,h,ϵ∗+vj,h):0≤h≤dj}.D_j=\{(C_{j-1}+(-1)^{\epsilon_*}u_{j,h},\epsilon_*+v_{j,h}):0\le h\le d_j\}.

The product before cell jj is (sj−1+Cj−1,0)(s_{j-1}+C_{j-1},0), proving (1). The possible odd parity of the final cell occurs after its variable and causes no exception.

Subtracting sj+Cj−1s_j+C_{j-1}, a paired rotation cell with reflections y,zy,z has prefixes

(0,0),(y,1),(y−z,0).(0,0),\qquad(y,1),\qquad(y-z,0).

Its equal-parity pair differs by y−z≠0y-z\ne0. A paired reflection cell with second reflection yy and optional rotations a,ba,b has prefixes

(0,1),(−a,1),(−a−y,0),(−a−y+b,0).(0,1),\qquad(-a,1),\qquad(-a-y,0),\qquad(-a-y+b,0).

If aa is absent, set a=0a=0 and omit the second point; if bb is absent, omit the fourth. Every remaining equal-parity pair differs by a present nonzero rotation coordinate. The shorter cells satisfy the same checks.

Robust local separation

Fix an integer K≥1K\ge1 and consider the full probability space of Lemma 2.1. In the rotation-majority case this includes both independent permutation factors; in the reflection-majority case only the reflection assignment is random. Let LKL_K be the event that, in every interval of at most KK cells, every permutation of its variables leaves every nonempty contiguous subword in that interval with nonidentity product. For each realisation, these permutations move only variable coordinates among variable slots in the chosen window. All nonvariable entries, including sampled nonvariable reflections, remain fixed during these permutations.

Lemma 3.1. There are m0(K)m_0(K) and cK>0c_K>0, depending only on KK, such that m≥m0(K)m\ge m_0(K) implies

Pr⁡(LK)≥cK\Pr(L_K)\ge c_K

in either cell construction, uniformly over pp, AA, the permitted placements and the ratio of the two pool sizes.

The proof, given in Appendix § 10, applies the quantitative permutation local lemma to canonical assignments. Its probability is unconditional in the cell construction. In particular, no lower bound on each fixed-decoration fibre is asserted. The condition excludes short identity subwords beginning at the first entry as well as those between two nonempty prefixes; the final conclusion still concerns nonempty prefixes only.

Two-pass repair

Fix k≥2k \ge2, put M=4kM = 4k and suppose m≥km \ge k. Let x1,…,xm∈Fpx_1,\ldots,x_m \in\mathbb{F}_p, set st=∑j≤txjs_t = \sum_{j \le t} x_j, s0=0s_0 = 0, and fix Dj⊆Fp×Z2D_j \subseteq\mathbb{F}_p \times\mathbb{Z}_2 with ∣Dj∣≤B|D_j| \le B. All indices refer to the original ordering, and decorations remain attached to positions. For 0≤t≤m0 \le t \le m, define

Vt={st+∑j∈Jxj+d:J⊆{t+1,…,min⁡(m,t+M)},d∈Dh,h∈[1,m]∩[t,t+M]}.(2)\mathcal{V}_t = \left\{ s_t + \sum_{j \in J} x_j + d : \begin{array}{l} J \subseteq\{t+1,\ldots,\min(m,t+M)\},\\ d \in D_h,\quad h \in[1,m] \cap[t,t+M] \end{array} \right\}. \tag*{(2)}

Then ∣Vt∣≤B(M+1)2M|\mathcal{V}_t| \le B(M+1)2^M and Vm=sm+Dm\mathcal{V}_m = s_m + D_m.

A source consists of a window W={b+1,…,b+w}⊆[m]W = \{b+1,\ldots,b+w\} \subseteq[m] of length w≤Mw \le M, disjoint sets U,Q⊆WU,Q \subseteq W with k≤∣Q∣≤2kk \le|Q| \le2k, and a cyclic order of QQ. A rotation is safe if

sb+∑j∈Uxj+∑j∈Ixj+d∉Vt(3)s_b + \sum_{j \in U} x_j + \sum_{j \in I} x_j + d \notin\mathcal{V}_t \tag*{(3)}

for every nonempty proper prefix II of the rotation, every d∈⋃h∈[1,m]∩[b,b+M]Dhd \in\bigcup_{h \in[1,m] \cap[b,b+M]} D_h and every t∈{0,…,m}t \in\{0,\ldots,m\} with ∣t−b∣>2M|t-b| > 2M. A prefix denotes its set of original labels when used in a sum. The window WW bounds original labels; the rotating list may occupy different positions. Since the safety test includes every decoration in the source interval, it protects the list’s proper prefixes whenever they end at positions in [1,m]∩[b,b+M][1,m] \cap[b,b+M] and the list has starting sum sb+∑j∈Uxjs_b + \sum_{j \in U} x_j.

Partition [m][m] into consecutive intervals Qi={bi+1,…,bi+ni}Q_i = \{b_i+1,\ldots,b_i+n_i\}, k≤ni≤2kk \le n_i \le2k, 1≤i≤a1 \le i \le a. Such a partition exists by using lengths k+u,k,…,kk+u,k,\ldots,k when m=ak+um=ak+u, 0≤u<k0 \le u < k. For c∈Qic \in Q_i, let Ti(c)T_i(c) be the original cyclic order of QiQ_i starting after cc and omitting cc. Before sampling coordinates, list the following sources:

  1. For each ii, use b=bib=b_i, W=QiW=Q_i, U=∅U=\varnothing, Q=QiQ=Q_i and its original cyclic order.

  1. For each i<ai<a and (c,d)∈Qi×Qi+1(c,d) \in Q_i \times Q_{i+1}, use b=bib=b_i, W=Qi∪Qi+1W=Q_i \cup Q_{i+1}, U={c}U=\{c\}, Q=(Qi∖{c})∪{d}Q=(Q_i \setminus\{c\}) \cup\{d\} and cyclic order (Ti(c),d)(T_i(c),d).

Let Rmenu\mathcal{R}_{\mathrm{menu}} assert that every listed source has a safe rotation. The list has at most

a+∑i<anini+1≤(1+4k2)m/k(4)a+\sum_{i<a} n_i n_{i+1} \le(1+4k^2)m/k \tag*{(4)}

items, all satisfying the source restrictions.

Proposition 4.1. If Rmenu\mathcal{R}_{\mathrm{menu}} holds, there is a permutation σ\sigma of [m][m] with ∣σ(j)−j∣≤4k−2<M|\sigma(j)-j| \le4k-2 < M such that, on setting uj=∑h≤jxσ(h)u_j = \sum_{h \le j} x_{\sigma(h)}, equality between a point of ui+Diu_i+D_i and a point of uj+Dju_j+D_j, i<ji<j, implies j−i≤4Mj-i \le4M.

Proof. For each source of the first family, choose a safe rotation, let cic_i be its first label, and write the block as (ci,Ti(ci))(c_i,T_i(c_i)). After this first pass, completed blocks retain their sums, so every proper nonempty prefix inside block ii is sbi+∑h∈Ixhs_{b_i}+\sum_{h\in I}x_h. With its position’s decoration, this lies in VbiV_{b_i} and avoids VtV_t for ∣t−bi∣>2M|t-b_i|>2M. Put a cut at hi=bi+1h_i=b_i+1. Since ni≥2n_i\ge2, its prefix is proper and has sum

sbi+xci.(5)s_{b_i}+x_{c_i}. \tag*{(5)}

The list between cuts hih_i and hi+1h_{i+1} is Pi=(Ti(ci),ci+1)P_i=(T_i(c_i),c_{i+1}), of length nin_i. Rotate it safely using the second-family source indexed by (i,ci,ci+1)(i,c_i,c_{i+1}). These position intervals are disjoint. Their preserved sums, together with the fixed first label c1c_1, preserve every cut sum (5), even if its label moves. Thus sbi+xcis_{b_i}+x_{c_i} remains the starting sum for PiP_i, even though the sum through the original boundary bib_i may change. For hi<j<hi+1h_i<j<h_{i+1}, the final prefix is

uj=sbi+xci+∑h∈Ixh,u_j=s_{b_i}+x_{c_i}+\sum_{h\in I}x_h,

where II is a proper nonempty prefix of the chosen rotation of PiP_i. The labels in {ci}∪I\{c_i\}\cup I lie within MM original positions after bib_i, and j∈[bi,bi+M]j\in[b_i,b_i+M]. Thus (2) and (3) give membership and protection at the original anchor bib_i.

Leave the final tail Ta(ca)T_a(c_a) unchanged. Its preceding cut sum is preserved, so its prefixes retain their first-pass values. The cuts, interiors between cuts and final tail cover every position j<mj<m. For each such jj, the corresponding original boundary aj=bia_j=b_i satisfies

∣j−aj∣≤M,uj+Dj⊆Vaj,|j-a_j|\le M,\qquad u_j+D_j\subseteq V_{a_j},
(uj+Dj)∩Vt=∅if ∣t−aj∣>2M.(6)(u_j+D_j)\cap V_t=\varnothing\quad\text{if }|t-a_j|>2M. \tag*{(6)}

When there is one block, the first pass alone gives these conclusions. At the final position, um=smu_m=s_m and um+Dm=Vmu_m+D_m=V_m; set am=ma_m=m.

Each pass moves labels within intervals of length at most 2k2k, so their composition has displacement at most 4k−24k-2. If decorated points at i<ji<j coincide, protection at i<mi<m and membership at jj force ∣ai−aj∣≤2M|a_i-a_j|\le2M. Hence j−i≤∣i−ai∣+∣ai−aj∣+∣aj−j∣≤4Mj-i\le|i-a_i|+|a_i-a_j|+|a_j-j|\le4M.

Lemma 4.2. Suppose a cell realisation satisfies LK\mathcal{L}_K for K≥6M+1K\ge6M+1. After any variable permutation σ\sigma with ∣σ(h)−h∣≤M|\sigma(h)-h|\le M, no equal nonempty prefixes can end in distinct cells i<ji<j with j−i≤4Mj-i\le4M.

Proof. Equal prefixes give an identity subword by left cancellation. It begins after the selected prefix in cell ii, which already contains that cell’s variable, and ends in cell jj. The subword therefore starts strictly after the variable of cell ii and uses exactly the variable slots i+1,…,ji+1,\ldots,j; its other entries remain fixed. The interval

W=[max⁡(1,i−M),min⁡(m,j+M)]∩ZW=[\max(1,i-M),\min(m,j+M)]\cap\mathbb{Z}

contains the subword’s cells and every original variable label σ(h)\sigma(h) it uses, and ∣W∣≤j−i+2M+1≤6M+1|W|\le j-i+2M+1\le6M+1. The prescriptions h↦σ(h)h\mapsto\sigma(h) for i+1≤h≤ji+1\le h\le j form a partial injection of WW into itself. Extend it to a permutation of WW by matching unused domain and range points. That local permutation reproduces the identity subword in the original realisation, contradicting LK\mathcal{L}_K.

Subset-sum anticoncentration

The analytic input is the following theorem of Pham and Sauermann.

Theorem 5.1 ([13 Theorem 1.3]). There is an absolute constant C≥1C \ge1 such that the following holds. Let pp be prime, let Y⊆FpY \subseteq\mathbb{F}_p have size N≥2N \ge2, and let ZZ be a uniformly random vv-element subset of YY, where

Clog⁡N≤v≤10−3N/log⁡N.C \log N \le v \le10^{-3}N/\log N.

Then

sup⁡z∈FpPr⁡(∑y∈Zy=z)≤1p+CNv.\sup_{z \in\mathbb{F}_p} \Pr\left(\sum_{y \in Z} y = z\right) \le\frac{1}{p}+\frac{C}{N\sqrt{v}}.

Zero is allowed in YY. Fix β>0\beta> 0 and put

L=⌊m1/3⌋,η=min⁡{β,1/6}.(7)L = \lfloor m^{1/3}\rfloor,\qquad\eta= \min\{\beta,1/6\}. \tag*{(7)}

The cube-root scale balances the scalar estimate with the count of clustered collision witnesses.

Lemma 5.2. For each fixed 0<a≤10 < a \le1, there is a threshold mam_a, depending only on aa and CC, with the following property. Suppose m≥mam \ge m_a, p≥m1+βp \ge m^{1+\beta}, and am≤N≤mam \le N \le m. If ZZ is a uniform LL-subset of an arbitrary NN-element set Y⊆FpY \subseteq\mathbb{F}_p, then

sup⁡zPr⁡(∑y∈Zy=z)≤Kam−1−η,Ka=1+2Ca.(8)\sup_{z} \Pr\left(\sum_{y \in Z} y = z\right) \le K_a m^{-1-\eta},\qquad K_a=1+\frac{\sqrt{2}C}{a}. \tag*{(8)}

Proof. Choose mam_a so that, for every m≥mam \ge m_a,

m≥max⁡{8,2/a},2Clog⁡m≤m1/3,1000log⁡m≤am2/3.m \ge\max\{8,2/a\},\qquad2C\log m \le m^{1/3},\qquad1000\log m \le am^{2/3}.

Such a threshold exists and is independent of β\beta. Then N≥2N \ge2, L≥m1/3/2L \ge m^{1/3}/2, and

Clog⁡N≤Clog⁡m≤L≤m1/3≤10−3am/log⁡m≤10−3N/log⁡N.C\log N \le C\log m \le L \le m^{1/3} \le10^{-3}am/\log m \le10^{-3}N/\log N.

The last inequality uses N≥amN \ge am and 0<log⁡N≤log⁡m0 < \log N \le\log m. Theorem 5.1 therefore bounds the largest atom by

m−1−β+2Cam−1−1/6≤Kam−1−η.m^{-1-\beta}+\frac{\sqrt{2}C}{a}m^{-1-1/6}\le K_a m^{-1-\eta}.

Affine systems in a random permutation

For an h×mh \times m matrix HH with columns H1,…,HmH_1,\ldots,H_m, set

S(H)=span⁡{Hj−Hj′:j,j′∈[m]},d=dim⁡S(H).(9)S(H)=\operatorname{span}\{H_j-H_{j'}:j,j'\in[m]\},\qquad d=\dim S(H). \tag*{(9)}

An actual column value is a vector cc that occurs as some HjH_j; its multiplicity is ∣{j∈[m]:Hj=c}∣|\{j\in[m]:H_j=c\}|. When xx is a permutation of XX, replacing every column HjH_j by Hj+cH_j+c translates $H_x by the fixed vector c∑u∈Xuc\sum_{u\in X}u. The affine column dimension is therefore the relevant quantity. The rank-exposure argument is standard; see [11 proof of Proposition 2.2] and [9 Lemma 3.7]. Related exposures retaining a large reservoir occur in the chain estimate [13 Corollary 4.2]. Disjoint position pools recover independent scalar sums inside a permutation.

Lemma 6.1. Fix an integer h≥1h \ge1 and 0<γ≤10 < \gamma\le1. Suppose HH is an h×mh \times m matrix over Fp\mathbb{F}_p with an actual column value c0c_0 of multiplicity at least γm\gamma m. Suppose actual column values c1,…,cqc_1,\ldots,c_q each have multiplicity at least LL and the differences c1−c0,…,cq−c0c_1-c_0,\ldots,c_q-c_0 are independent. If x:[m]→Xx:[m]\to X is a uniform bijection onto an arbitrary mm-element set X⊆FpX\subseteq\mathbb{F}_p, then, for every fixed z∈Fphz\in\mathbb{F}_p^h,

Pr⁡(Hx=z)≤Ph,γm−d−ηq(10)\Pr(Hx=z)\le P_{h,\gamma}m^{-d-\eta q} \tag*{(10)}

provided p≥m1+βp\ge m^{1+\beta} and mm exceeds a threshold depending only on h,γ,Ch,\gamma,C. The constant Ph,γP_{h,\gamma} has the same parameter dependence. The independence assumption implies q≤d≤hq\le d\le h. The cases q=0q=0 and d=0d=0 are allowed.

Proof. If d=0d=0, every column is c0c_0, necessarily q=0q=0, and Hx=c0∑u∈XuHx=c_0\sum_{u\in X}u is deterministic. Assume d≥1d\ge1. Extend the specified differences to a basis

vi=ci−c0,1≤i≤d,v_i=c_i-c_0,\qquad1\le i\le d,

by choosing further actual column values. For i≤qi\le q, select LL positions of column value cic_i; for q<i≤dq<i\le d, select one. Denote these disjoint position sets by EiE_i and their sizes by rir_i. None is a baseline position.

Put

a=γ4h,t=⌊γm2h⌋.a=\frac{\gamma}{4h},\qquad t=\left\lfloor\frac{\gamma m}{2h}\right\rfloor.

For m≥4h/γm\ge4h/\gamma, one has t≥amt\ge am. Choose disjoint sets FiF_i of tt baseline positions, also disjoint from every EiE_i. There are enough baseline positions because dt≤ht≤γm/2dt\le ht\le\gamma m/2. The disjoint pools Ei∪FiE_i\cup F_i have sizes Ni=t+ri∈[am,m]N_i=t+r_i\in[am,m].

Condition on the assignments outside these pools and on the unordered value set YiY_i assigned to each pool. Every nonempty fibre has exactly ∏iNi!\prod_i N_i! assignments, one for each tuple of bijections from the pools to their value sets. The restrictions to the pools are therefore independent uniform bijections. Pool ii contributes

c0∑y∈Yiy+viZi,Zi=∑j∈Eixjc_0\sum_{y\in Y_i}y+v_iZ_i,\qquad Z_i=\sum_{j\in E_i}x_j

to HxHx. The baseline terms and the contribution outside the pools are fixed. Since v1,…,vdv_1,\ldots,v_d are independent, Hx=zHx=z permits at most one tuple (Z1,…,Zd)(Z_1,\ldots,Z_d).

For i≤qi\le q, Lemma 5.2 bounds the largest atom of ZiZ_i by Kam−1−ηK a m^{-1-\eta}. For i>qi>q, the singleton value is uniform on YiY_i and has largest atom Ni−1≤a−1m−1N_i^{-1}\le a^{-1}m^{-1}. Multiplying the bounds on each fibre and averaging proves (10), with

Ph,γ=max⁡{1,Ka,a−1}h.P_{h,\gamma}=\max\{1,K a,a^{-1}\}^{h}.

Increase the threshold to include mam_a and 4h/γ4h/\gamma. This constant also covers d=0.□d=0. \square

The residual right-hand side may vary between fibres, since the bound is uniform in zz. It is fixed on each fibre before the independent pool assignments are exposed.

Collision matrices and circular clusters

The standard incidence-rank formula gives the number of vertices minus the number of components; see [1 Theorem 2.3]. The following extension includes disjoint cluster indicators.

Lemma 7.1. Let g:[ℓ]→[ℓ]g : [\ell] \to[\ell] have no fixed points, and let B0,B1,…,BqB_0, B_1, \ldots, B_q partition [ℓ][\ell], with B0B_0 possibly empty and Ba≠∅B_a \ne\varnothing for a≥1a \ge1. Over a field of characteristic zero or characteristic p>ℓp > \ell, put

Dij=1j=i−1j=g(i),wa=1Ba.D_{ij} = \mathbf{1}_{j=i} - \mathbf{1}_{j=g(i)}, \qquad w_a = \mathbf{1}_{B_a}.

If C1,…,CκC_1, \ldots, C_\kappa are the directed cycles of gg and TT is the κ×q\kappa\times q matrix with Tua=∣Cu∩Ba∣T_{ua} = |C_u \cap B_a|, 1≤a≤q1 \le a \le q, interpreted in the field, then

rank⁡[D∣w1∣⋯∣wq]=ℓ−κ+rank⁡T≥ℓ+q2.(11)\operatorname{rank}[D \mid w_1 \mid\cdots\mid w_q] = \ell- \kappa+ \operatorname{rank} T \ge\frac{\ell+ q}{2}. \tag*{(11)}

Proof. The equations DTy=0D^{\mathsf{T}}y = 0 read

yj=∑i:g(i)=jyi.y_j = \sum_{i:g(i)=j} y_i.

Each functional-graph component consists of a directed cycle with trees feeding into it. Deleting leaves forces yy to vanish off the cycles; on each cycle it is constant. Thus ker⁡DT\ker D^{\mathsf{T}} has basis 1C1,…,1Cκ\mathbf{1}_{C_1}, \ldots, \mathbf{1}_{C_\kappa} and rank⁡D=ℓ−κ\operatorname{rank} D = \ell- \kappa. The map π(y)u=∑i∈Cuyi\pi(y)_u = \sum_{i \in C_u} y_i has kernel im⁡D\operatorname{im} D, by inclusion and dimension. The images π(wa)\pi(w_a) form TT, proving the rank equality.

Write t=rank⁡Tt = \operatorname{rank} T and select tt rows spanning its row space. For every nonzero column aa, choose a vertex of BaB_a on a selected cycle where that column is nonzero. A zero column has no cycle intersection: a positive intersection size is at most ℓ\ell and cannot vanish in the stated characteristic. For such a column choose an off-cycle vertex of BaB_a. These qq distinct representatives avoid all κ−t\kappa- t unselected cycles. Each such cycle has at least two vertices. Hence ℓ≥q+2(κ−t)\ell\ge q + 2(\kappa- t), which proves the inequality.

Let M,L,m,ℓM, L, m, \ell be integers with

2≤ℓ≤M,L≥M,m≥2(ℓ+1)L.(12)2 \le\ell\le M, \qquad L \ge M, \qquad m \ge2(\ell+ 1)L. \tag*{(12)}

Fix 0≤b<m0 \le b < m, disjoint sets U,Q⊆{b+1,…,min⁡(m,b+M)}U, Q \subseteq\{b + 1, \ldots, \min(m, b + M)\} with ∣Q∣=ℓ|Q| = \ell, and a cyclic order (q1,…,qℓ)(q_1, \ldots, q_\ell) of QQ. For each ii, let IiI_i be a nonempty proper cyclic prefix beginning at qiq_i, let ti∈{0,…,m}t_i \in\{0, \ldots, m\} satisfy ∣ti−b∣>2M|t_i - b| > 2M, and choose

Ji⊆{ti+1,…,min⁡(m,ti+M)}.J_i \subseteq\{t_i + 1, \ldots, \min(m, t_i + M)\}.

Define the ℓ×m\ell\times m matrix

(Hj)i=1j≤b−1j≤ti+1j∈U+1j∈Ii−1j∈Ji.(13)(H_j)_i = \mathbf{1}_{j \le b} - \mathbf{1}_{j \le t_i} + \mathbf{1}_{j \in U} + \mathbf{1}_{j \in I_i} - \mathbf{1}_{j \in J_i}. \tag*{(13)}

Mark b,t1,…,tℓb, t_1, \ldots, t_\ell on Z/mZ\mathbb{Z}/m\mathbb{Z}. Join consecutive distinct marks when their clockwise gap is shorter than 2L2L; the connected components are the clusters. Equal residues are in the same cluster. If there is only one distinct mark, its sole gap has length mm. Let qq count the clusters not containing bb, and set Ba={i:ti lies in cluster a}B_a = \{i : t_i \text{ lies in cluster } a\}, with B0B_0 corresponding to the source cluster. The linear anchors 00 and mm remain distinct in (13).

Lemma 7.2. Under (12), in characteristic zero or characteristic p>ℓp > \ell, the affine column dimension dd of HH satisfies d≥(ℓ+q)/2d \ge(\ell+q)/2. There are actual column values c0,…,cqc_0,\ldots,c_q such that c0c_0 occurs at least m/[2(ℓ+1)]m/[2(\ell+1)] times, each other cac_a occurs at least LL times, and c1−c0,…,cq−c0c_1-c_0,\ldots,c_q-c_0 are independent.

Proof. Let g(i)≠ig(i) \ne i be the cyclic position immediately after IiI_i. Neither UU nor JiJ_i meets QQ, and the prefix difference in (13) is constant on QQ. Let DD be the matrix of Lemma 7.1 for this map gg, and write D⋅jD_{\cdot j} for its jj-th column. Taking consecutive cyclic source-column differences gives

Hqj−Hqj−1=D⋅j,q0=qℓ.(14)H_{q_j}-H_{q_{j-1}}=D_{\cdot j},\qquad q_0=q_\ell. \tag*{(14)}

Thus im⁡D⊆S(H)\operatorname{im} D \subseteq S(H).

At least one circular gap has length at least 2L2L, by (12). Every cluster lies in an arc of length less than 2ℓL2\ell L, and there are q+1q+1 intercluster gaps. Write Hj=Aj+EjH_j=A_j+E_j, with (Aj)i=1j≤b−1j≤ti(A_j)_i=1_{j\le b}-1_{j\le t_i}. For an intercluster gap of length GG from aa to the next mark a+Ga+G, the columns AjA_j are constant on the half-open circular arc (a,a+G](a,a+G]. Here a position of residue zero means column mm. Retain the positions at distances M+1,…,GM+1,\ldots,G clockwise from aa, including the next mark itself. The corrections EjE_j are supported at distances 1,…,M1,\ldots,M clockwise after marked anchors. Since no mark lies strictly inside the gap, these corrections vanish at every retained position. There are G−M≥2L−M≥LG-M\ge2L-M\ge L such positions, all with the same column value. The largest gap supplies an actual column value occurring at least

mℓ+1−M≥m2(ℓ+1)\frac{m}{\ell+1}-M\ge\frac{m}{2(\ell+1)}

times.

Extend AjA_j periodically. Its circular jump at residue aa is

Aa+1−Aa=−1a≡b [ℓ]+∑i:ti≡aei.(15)A_{a+1}-A_a=-1_{a\equiv b\ [\ell]}+\sum_{i:t_i\equiv a}e_i. \tag*{(15)}

At residue zero the left side is A1−AmA_1-A_m. Indeed the circular derivative of 1j≤t1_{j\le t} is −1a≡t+1a≡0-1_{a\equiv t}+1_{a\equiv0}, including t=0,mt=0,m. Crossing free cluster aa changes the constant gap value by waw_a; crossing the source cluster changes it by −∑a=1qwa-\sum_{a=1}^{q}w_a. The waw_a are independent because their supports are disjoint and nonempty. The q+1q+1 actual gap values therefore have affine dimension qq and are affinely independent. Choose the largest-gap value as c0c_0. Their differences span all waw_a and supply the required repeated independent directions. Together with (14), Lemma 7.1 gives d≥(ℓ+q)/2d\ge(\ell+q)/2. □

Lemma 7.3. For fixed bb, ℓ\ell, LL, mm satisfying m≥2(ℓ+1)Lm\ge2(\ell+1)L, the number of ordered anchor tuples (t1,…,tℓ)∈{0,…,m}ℓ(t_1,\ldots,t_\ell)\in\{0,\ldots,m\}^{\ell} with qq free clusters is at most

AℓmqLℓ−q,Aℓ=(ℓ+1)ℓ+1(8ℓ+2)ℓ.(16)A_\ell m^qL^{\ell-q},\qquad A_\ell=(\ell+1)^{\ell+1}(8\ell+2)^\ell. \tag*{(16)}

Proof. Partition the labels 0,1,…,ℓ0,1,\ldots,\ell into their clusters, with label zero representing bb. There are at most (ℓ+1)ℓ+1(\ell+1)^{\ell+1} partitions. The least label of each free cluster has at most m+1≤2mm+1\le2m anchor choices. Every other target lies at circular distance less than 2ℓL2\ell L from its representative, which has at most (8ℓ+2)L(8\ell+2)L possible linear anchors, counting both representatives of residue zero. The resulting bound is (16), since 2q(8ℓ+2)ℓ−q≤(8ℓ+2)ℓ2^q(8\ell+2)^{\ell-q}\le(8\ell+2)^\ell. □

The probability of a safe repair menu

We retain the potential target sets (2), the safety condition (3), and the predetermined menu from Section 4. The variable order is sampled uniformly; the decorations remain fixed.

Proposition 8.1. Fix β>0\beta> 0, an integer k≥2k \ge2, and a decoration bound B≥1B \ge1. Put M=4kM = 4k and η=min⁡{β,1/6}\eta= \min\{\beta,1/6\}. There are constants msafe(k)m_{\mathrm{safe}}(k) and Ck,BC_{k,B} such that, whenever m≥msafe(k)m \ge m_{\mathrm{safe}}(k), p≥m1+βp \ge m^{1+\beta}, and xx is a uniform ordering of an arbitrary mm-element set X⊆FpX \subseteq\mathbb{F}_p,

Pr⁡(Rmenuc)≤Ck,Bm1−ηk.(17)\Pr(\mathcal{R}_{\mathrm{menu}}^{c}) \le C_{k,B}m^{1-\eta k}. \tag*{(17)}

The threshold msafe(k)m_{\mathrm{safe}}(k) depends only on kk and the absolute constant CC of Theorem 5.1, and not on β\beta. The bound is uniform over XX and all fixed decorations of size at most BB. In particular the failure probability tends to zero if ηk>1\eta k > 1.

Proof. First fix one source configuration, with cyclic order (q1,…,qℓ)(q_1,\ldots,q_\ell), where k≤ℓ≤2kk \le\ell\le2k. If all its rotations fail, choose one collision for each rotation. For the rotation starting at qiq_i, this specifies a nonempty proper prefix IiI_i, a remote anchor tit_i with ∣ti−b∣>2M\lvert t_i-b\rvert> 2M, a set

Ji⊆{ti+1,…,min⁡(m,ti+M)},J_i \subseteq\{t_i+1,\ldots,\min(m,t_i+M)\},

and source and target decorations of equal parity. Writing ziz_i for target coordinate minus source coordinate, its equation is

sb+∑u∈Uxu+∑j∈Iixj−sti−∑j∈Jixj=zi.(18)s_b+\sum_{u\in U}x_u+\sum_{j\in I_i}x_j-s_{t_i}-\sum_{j\in J_i}x_j=z_i. \tag*{(18)}

After these choices are fixed, the system is Hx=zHx=z with (13). We sum over fixed witness tuples, rather than condition on the failure of other rotations.

Set

h=2k,γ=12(2k+1),P=P2k,γ.h=2k,\qquad\gamma=\frac{1}{2(2k+1)},\qquad P=P_{2k,\gamma}.

Choose mm large enough for Lemma 6.1, for L≥ML \ge M, for m≥2(2k+1)Lm \ge2(2k+1)L, and for m>2km > 2k. These conditions depend only on kk and the absolute scalar constant; they hold eventually. The prime-size condition gives p>2kp > 2k. If the anchors have qq free clusters, Lemma 7.2 gives affine dimension at least (ℓ+q)/2(\ell+q)/2, a baseline of multiplicity at least γm\gamma m, and qq repeated independent directions. Pad HH with zero rows to height 2k2k. Neither its affine dimension nor its column multiplicities change. Lemma 6.1 therefore gives

Pr⁡(Hx=z)≤Pm−(ℓ+q)/2−ηq.(19)\Pr(Hx=z)\le Pm^{-(\ell+q)/2-\eta q}. \tag*{(19)}

For fixed bb, ℓ\ell, qq, Lemma 7.3 bounds the anchor tuples by AℓmqLℓ−qA_\ell m^qL^{\ell-q}. The remoteness restrictions only reduce this count. For each rotation, the prefix has at most 2k2k choices, each decoration has at most B(M+1)B(M+1) choices, and JiJ_i has at most 2M2^M choices. Thus, for fixed anchors, the remaining witness choices number at most Ek,BℓE_{k,B}^{\ell}, where

Ek,B=2k[B(M+1)]222M.E_{k,B}=2k[B(M+1)]^{2}2^{2M}.

Counting pairs of incompatible parities only enlarges this bound. Combining the counts with (19) gives

Pr⁡(the fixed source has no safe rotation)≤PAℓEk,Bℓ∑q=0ℓmqLℓ−qm−(ℓ+q)/2−ηq≤PAℓEk,Bℓ∑q=0ℓm−(ℓ−q)/6−ηq≤Dk,Bm−ηℓ.\begin{aligned} \Pr(\text{the fixed source has no safe rotation}) &\le PA_{\ell}E_{k,B}^{\ell}\sum_{q=0}^{\ell}m^{q}L^{\ell-q}m^{-(\ell+q)/2-\eta q}\\ &\le PA_{\ell}E_{k,B}^{\ell}\sum_{q=0}^{\ell}m^{-(\ell-q)/6-\eta q}\\ &\le D_{k,B}m^{-\eta\ell}. \end{aligned}

where

Dk,B=Pmax⁡k≤ℓ≤2k(ℓ+1)AℓEk,Bℓ.D_{k,B}=P\max_{k\le\ell\le2k}(\ell+1)A_{\ell}E_{k,B}^{\ell}.

The second inequality uses L≤m1/3L\le m^{1/3}; the last uses η≤1/6\eta\le1/6. The case q=0q=0 is included. By (4), the predetermined menu has at most (1+4k2)m/k(1+4k^{2})m/k entries. A union bound proves (17) with

Ck,B=1+4k2kDk,B.C_{k,B}=\frac{1+4k^{2}}{k}D_{k,B}.

All configurations are listed before sampling, so the later selection of rotations introduces no additional conditioning.

The scalar saving 1/61/6 and the clustered-anchor saving 1/61/6 coincide at the cube-root scale. More generally, L=mρL=m^{\rho} gives gains ρ/2\rho/2 and 1/2−ρ1/2-\rho, whose minimum is maximised at ρ=1/3\rho=1/3. The estimate is uniform on every fibre fixing the nonvariable entries and variable coordinate set of the cell construction. The local-separation event is intersected with this event only after averaging the fibre bounds.

Completion of the proofs

Proof of Theorem 1.1. Fix 0<α<10<\alpha<1 and set

β=α−1−1,η=min⁡{β,1/6},k=⌊η−1⌋+1,M=4k,K=6M+1.(20)\beta=\alpha^{-1}-1,\qquad\eta=\min\{\beta,1/6\},\qquad k=\lfloor\eta^{-1}\rfloor+1,\qquad M=4k,\qquad K=6M+1. \tag*{(20)}

Thus ηk>1\eta k>1. Choose m∗m_{*} above the thresholds in Lemma 3.1 and Proposition 8.1 for these fixed parameters and B=4B=4. Increase it, if necessary, so that m∗≥km_{*}\ge k and

Ck,4m1−ηk≤cK/2(m≥m∗),C_{k,4}m^{1-\eta k}\le c_{K}/2\qquad(m\ge m_{*}),

where cKc_{K} is the lower bound in Lemma 3.1 and Ck,4C_{k,4} is the constant in Proposition 8.1. All choices depend only on α\alpha and the absolute constants in the cited theorems. Take an integer Cα≥max⁡{4m∗,4}C_{\alpha}\ge\max\{4m_{*},4\}.

Suppose that Cα≤n=∣A∣≤pαC_{\alpha}\le n=|A|\le p^{\alpha}. In particular pp is odd. The construction of Lemma 2.1 gives m≥n/4≥m∗m\ge n/4\ge m_{*} and

p≥n1/α≥m1/α=m1+β.p\ge n^{1/\alpha}\ge m^{1/\alpha}=m^{1+\beta}.

In the original probability space, Lemma 3.1 gives Pr⁡(LK)≥cK\Pr(\mathcal{L}_{K})\ge c_{K}. Condition on the nonvariable entries and the variable set XX. The decorations are fixed on each such fibre, and the variables remain a uniform permutation of XX. Proposition 8.1 therefore bounds the conditional probability of Rmenuc\mathcal{R}_{\mathrm{menu}}^{c} by Ck,4m1−ηkC_{k,4}m^{1-\eta k} on every nonempty fibre. Averaging gives

Pr⁡(LK∩Rmenu)≥Pr⁡(LK)−Pr⁡(Rmenuc)≥cK/2>0.\begin{aligned} \Pr(\mathcal{L}_K \cap\mathcal{R}_{\mathrm{menu}}) \ge\Pr(\mathcal{L}_K) - \Pr(\mathcal{R}_{\mathrm{menu}}^{c}) \\ &\ge c_K/2 > 0. \end{aligned}

No independence of these events is required. For an outcome in their intersection, apply the variable permutation σ\sigma from Proposition 4.1 to the cell arrangement and read off the resulting word. This is an ordering of AA, since only its variable coordinates have been permuted. Nonempty prefixes ending in the same cell are distinct by Lemma 2.1. If two equal prefixes end in distinct cells, Proposition 4.1 places them at distance at most 4M4M, whereas Lemma 4.2 excludes such a collision because ∣σ(j)−j∣<M|\sigma(j)-j|<M and K=6M+1K=6M+1. Thus the ordering is valid.

Proof of Corollary 1.2. The large-set theorem [3 Theorem 1.4] gives an absolute c>0c>0 such that, for every finite group GG, every S⊆G∖{e}S\subseteq G\setminus\{e\} with ∣S∣≥∣G∣1−c|S|\ge|G|^{1-c} has a valid ordering. Put c0=min⁡{c,1/2}c_0=\min\{c,1/2\} and α=1−c0/2\alpha=1-c_0/2. Then

pα(2p)1−c0=2c0−1pc0/2⟶∞.\frac{p^\alpha}{(2p)^{1-c_0}}=2^{c_0-1}p^{c_0/2}\longrightarrow\infty.

Thus the polynomial range of Theorem 1.1 eventually overlaps the large-set range for D2pD_{2p}. For the small-set range, the semidirect-product theorem [4 Theorem 1.3] applies to Zp⋊H\mathbb{Z}_p\rtimes H when the fixed finite abelian group HH is strongly sequenceable and acts by signs. The group H=Z2H=\mathbb{Z}_2 is strongly sequenceable, since its only nonempty identity-free subset is a singleton. Taking its action by inversion gives an absolute cs>0c_s>0 such that every identity-free dihedral subset of size at most

exp⁡(cs(log⁡p)1/4)\exp\bigl(c_s(\log p)^{1/4}\bigr)

has a sequencing. Their condition also excludes intermediate identity prefixes and hence implies the validity required here. This endpoint eventually exceeds the fixed CαC_\alpha. The small-set, polynomial and large-set intervals therefore cover every integer from 11 to 2p−12p-1 for sufficiently large primes. The empty set is immediate.

Proof of robust local separation

Proof of Lemma 3.1. Put

Λ=4K,νw=2w(4w+1),τK=∑w=1Kw!νw,υK=∑w=1Kw w!νw,\Lambda=4K,\qquad\nu_w=2w(4w+1),\qquad\tau_K=\sum_{w=1}^{K}w!\nu_w,\qquad\upsilon_K=\sum_{w=1}^{K}w\,w!\nu_w,
ωK=2Λ(τK+υK),m0(K)=max⁡{2Λ,8,8ΛωK}.\omega_K=2\Lambda(\tau_K+\upsilon_K),\qquad m_0(K)=\max\{2\Lambda,8,8\Lambda\omega_K\}.

An index pattern consists of a ww-cell window, a permutation of its variables and a nonempty contiguous subword in the resulting window. It has at most 4w4w entries and νw\nu_w subwords. There are at most mτKm^{\tau_K} patterns, and every original random slot belongs to at most υK\upsilon_K patterns. In rotation majority, at most fυKf\upsilon_K patterns meet a reflection slot. Pull the random entries of each subword back to their original slots; this pullback is injective and remains within the window. Discard deterministically nonidentity patterns. In rotation majority, a subword without rotations lies in a run of at most two distinct reflections and is nonidentity. A retained pattern uses a≥1a \ge1 rotations; if a=1a = 1, it uses an even number b≥2b \ge2 of reflections. In reflection majority, a subword without reflections contains at most one rotation, so a retained pattern uses an even number h≥2h \ge2 of reflections. Identity in a retained pattern is one affine equation in the random coordinates, each with coefficient +1+1 or −1-1. The coefficients depend only on the type pattern. A canonical bad event specifies an injective assignment to the used random slots satisfying that equation. Its index includes the pattern, so identical events may occur as different vertices. Their simultaneous avoidance is exactly LK\mathcal{L}_K.

Write (N)a=N(N−1)⋯(N−a+1)(N)_a = N(N-1)\cdots(N-a+1), with (N)0=1(N)_0 = 1. In rotation majority, an assignment using a,ba,b slots has probability [(m)a(f)b]−1[(m)_a(f)_b]^{-1}. Solving the affine equation for one rotation bounds the total event weight of one pattern by

1m−a+1≤2m.(21)\frac{1}{m-a+1} \le\frac{2}{m}. \tag*{(21)}

For a fixed rotation value ρ\rho and a≥2a \ge2, choose its slot and solve for another rotation. There are at most a(m−1)a−2(f)ba(m-1)_{a-2}(f)_b assignments, of weight at most

am(m−a+1)≤2Λm2.\frac{a}{m(m-a+1)} \le\frac{2\Lambda}{m^2}.

If a=1a = 1, solve instead for a reflection after fixing ρ\rho and the other reflections; the weight is at most

1m(f−b+1)≤Λmf,\frac{1}{m(f-b+1)} \le\frac{\Lambda}{mf},

since f/(f−b+1)≤b≤Λf/(f-b+1) \le b \le\Lambda for every feasible f≥bf \ge b. For a fixed reflection value, choose its slot and solve for a rotation, obtaining weight at most

bf(m−a+1)≤2Λfm.\frac{b}{f(m-a+1)} \le\frac{2\Lambda}{fm}.

In reflection majority, solving for one reflection gives pattern weight at most

1f−h+1≤2f≤2m.\frac{1}{f-h+1} \le\frac{2}{f} \le\frac{2}{m}.

If a fixed reflection value must occur, choose its slot and solve for another reflection, giving weight at most

hf(f−h+1)≤2Λf2≤2Λm2.\frac{h}{f(f-h+1)} \le\frac{2\Lambda}{f^2} \le\frac{2\Lambda}{m^2}.

These inequalities use a,h≤Λa,h \le\Lambda, m≥2Λm \ge2\Lambda and f≥mf \ge m in reflection majority. Only feasible patterns contribute denominators.

Let pE=Pr⁡(E)p_E = \Pr(E). Summing pattern weights gives ∑EpE≤2τK\sum_E p_E \le2\tau_K. Every position label has event weight at most 2νK/m2\nu_K/m. In rotation majority, a rotation-value label has weight at most 2ΛτK/m+ΛνK/m2\Lambda\tau_K/m + \Lambda\nu_K/m: use all mτKm\tau_K patterns when a≥2a \ge2 and the at most fνKf\nu_K reflection-using patterns when a=1a = 1. A reflection-value label has weight at most 2ΛνK/m2\Lambda\nu_K/m. In reflection majority its weight is at most 2ΛτK/m2\Lambda\tau_K/m. Thus every position or value label λ\lambda satisfies

∑E:λ used by EpE≤ωK/m.(22)\sum_{E:\lambda\ \mathrm{used\ by}\ E} p_E \le\omega_K/m. \tag*{(22)}

A value label includes its permutation-factor tag, even when rotation and reflection coordinates coincide. For f=0f = 0, reflection cases are absent; for f=1f = 1, retained rotation-majority patterns have no reflections, so the case a=1a = 1 is absent. For every other bounded ff, the number fνKf\nu_K of reflection-using patterns cancels the small-pool denominator.

Join events sharing a position or value label in one permutation factor. This overlap graph is a negative dependency graph, as in the permutation framework of [8 Section 1.1]. For completeness, force the prescribed matches of one event EE successively by swapping each desired value into its prescribed position. Injectivity of the prescribed assignment preserves all previously forced matches. With tt matches already forced in a factor of size NN, each permutation satisfying the next match has exactly N−tN-t preimages satisfying the preceding matches. The resulting law is the product-permutation law conditioned on EE. An occurring non-neighbour survives each swap: its prescribed positions include neither the forced position nor the current position of the desired value. Hence, for avoidance CC of any collection of non-neighbours, Pr⁡(C∣E)≤Pr⁡(C)\Pr(C \mid E) \le\Pr(C). Bayes’ formula gives Pr⁡(E∣C)≤Pr⁡(E)\Pr(E \mid C) \le\Pr(E) whenever Pr⁡(C)>0\Pr(C) > 0. This argument also applies to two independent factors or an empty factor.

The quantitative lopsided local lemma [10 Lemma 3] gives an avoidance probability at least ∏E(1−zE)\prod_E(1-z_E) if

pE≤zE∏E′∼E(1−zE′),0≤zE<1.p_E \le z_E \prod_{E'\sim E}(1-z_{E'}), \qquad0 \le z_E < 1.

Each event uses at most Λ\Lambda matches and 2Λ2\Lambda labels, so (A.2) gives

∑E′∼EpE′≤2ΛωK/m.\sum_{E'\sim E}p_{E'} \le2\Lambda\omega_K/m.

Take zE=2pEz_E = 2p_E. The pattern bound (A.1) and its reflection-majority analogue give zE≤4/m≤1/2z_E \le4/m \le1/2, while m≥8ΛωKm \ge8\Lambda\omega_K gives ∑E′∼EzE′≤1/2\sum_{E'\sim E}z_{E'} \le1/2. Thus ∏E′∼E(1−zE′)≥1−∑E′∼EzE′≥1/2\prod_{E'\sim E}(1-z_{E'}) \ge1-\sum_{E'\sim E}z_{E'} \ge1/2, proving the local-lemma hypothesis. Finally log⁡(1−z)≥−2z\log(1-z) \ge-2z for 0≤z≤1/20 \le z \le1/2 yields

Pr⁡(LK)≥∏E(1−2pE)≥exp⁡(−4∑EpE)≥e−8τK=:cK>0.\begin{aligned} \Pr(\mathcal{L}_K) \ge\prod_E(1-2p_E) \\ &\ge\exp\left(-4\sum_E p_E\right) \\ &\ge e^{-8\tau_K}=:c_K>0. \end{aligned}

References

  1. [1]R. B. Bapat. Graphs and Matrices. Springer London, 2010. ISBN 9781848829817. doi: 10.1007/978-1-84882-981-7.DOI
  2. [2]Benjamin Bedert and Noah Kravitz. Graham’s rearrangement conjecture beyond the rectification barrier. Israel Journal of Mathematics, 273(1):471–500, 2026. doi: 10.1007/s11856-025-2871-6. Published online 30 November 2025.DOI
  3. [3]Benjamin Bedert, Matija Bučić, Noah Kravitz, Richard Montgomery, and Alp Müessner. On Graham’s rearrangement conjecture over ℱ₂, 2025. URL https://arxiv.org/abs/2508.18254v1. Version 1, 25 August 2025.
  4. [4]Simone Costa, Stefano Della Fiore, and Eva R. Engel. Graham’s rearrangement for a class of semidirect products, 2025. URL https://arxiv.org/abs/2503.18101v2. Version 2, 19 August 2025.
  5. [5]Simone Costa, Stefano Della Fiore, Tao Feng, and Hengrui Liu. Kneserized anticoncentration and reverse absorption for Graham’s rearrangement conjecture, 2026. URL https://arxiv.org/abs/2608.10015v2. Version 2, 18 August 2026.
  6. [6]P. Erdős and R. L. Graham. Old and new problems and results in combinatorial number theory. Number 28 in Monographies de L’Enseignement Mathématique. L’Enseignement Mathématique, Université de Genève, Genève, 1980. URL https://mathweb.ucsd.edu/~ronspubs/80_11_number_theory.pdf.
  7. [7]R. L. Graham. On sums of integers taken from a fixed sequence. In Proceedings of the Washington State University Conference on Number Theory, pages 22–40, 1971. URL https://mathweb.ucsd.edu/~ronspubs/71_08_integer_sums.pdf.
  8. [8]David G. Harris and Aravind Srinivasan. A constructive Lovász local lemma for permutations. Theory of Computing, 13(17):1–41, 2017. doi: 10.4086/toc.2017.v013a017.DOI
  9. [9]Matthew Kwan and Lisa Sauermann. Resolution of the quadratic Littlewood–Offord problem. Compositio Mathematica, 161(12):3089–3139, 2025. doi: 10.1112/S0010437X25102789. Lemma 3.7 is cited from arXiv:2312.13826v1.DOI
  10. [10]Linyuan Lu and László Székely. Using Lovász local lemma in the space of random injections. The Electronic Journal of Combinatorics, 14(1):R63, 2007. doi: 10.37236/981. Research Paper R63.DOI
  11. [11]A. M. Odlyzko. On subspaces spanned by random selections of ±1 vectors. Journal of Combinatorial Theory, Series A, 47(1):124–133, 1988. doi: 10.1016/0097-3165(88)90046-5. URL https://www-users.cse.umn.edu/~odlyzko/doc/arch/random.vectors.pdf. Proof of Proposition 2.2 is cited from the author’s manuscript, pp. 5–6.DOI
  12. [12]M. A. Ollis. Sequences in dihedral groups with distinct partial products. Australasian Journal of Combinatorics, 78(1):35–60, 2020. URL https://ajc.maths.uq.edu.au/pdf/78/ajc_v78_p035.pdf.arxiv.org/abs/1904.07646
  13. [13]Huy Tuan Pham and Lisa Sauermann. On Graham’s rearrangement conjecture, 2026. URL https://arxiv.org/abs/2602.15797v1. Version 1, 17 February 2026.

Paper details

vlnc:W_sxxeb2fj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI ChatGPT, Anthropic Claude Fable

View statement
Looking for related papers…
Contents