arxiv: 2603.26303 · v2 · submitted 2026-03-27 · 🧮 math.PR · math.CO

Recognition: 2 theorem links

· Lean Theorem

Spectral gap of biased adjacent-transposition chains

Gary R.W. Greaves, Haoran Zhu

Authors on Pith no claims yet

Pith reviewed 2026-05-14 22:41 UTC · model grok-4.3

classification 🧮 math.PR math.CO

keywords spectral gapadjacent transpositionsMarkov chainsymmetric groupprobability vectororthogonal projectionsmixing rate

0 comments

The pith

The uniform probability vector attains the minimum spectral gap among regular vectors for biased adjacent-transposition chains on the symmetric group.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes a sharp lower bound on the spectral gap of the biased adjacent-transposition Markov chain acting on all permutations. The bound implies that the uniform distribution on the symmetric group achieves the smallest gap, thereby resolving Fill's long-standing conjecture that the uniform vector minimizes the gap among regular probability vectors. The authors also identify exactly which regular vectors achieve this minimum gap and compute the multiplicity of the corresponding eigenvalue. Their approach rests on decomposing the transition matrix algebraically into a sum of elementary orthogonal projections whose eigenvalues are easy to analyze.

Core claim

We establish a sharp lower bound on the spectral gap of the biased adjacent-transposition Markov chain on the symmetric group. As a consequence, we resolve a longstanding conjecture of Fill, proving that among all regular probability vectors, the minimum spectral gap of the transition matrix is attained by the uniform probability vector. We also characterise the regular probability vectors attaining the minimum spectral gap and determine the exact multiplicity of the corresponding second-largest eigenvalue. Our proof relies on a novel algebraic decomposition of the transition matrix into elementary orthogonal projections.

What carries the argument

Algebraic decomposition of the transition matrix into elementary orthogonal projections whose spectrum determines the second-largest eigenvalue.

Load-bearing premise

The transition matrix admits an algebraic decomposition into elementary orthogonal projections whose spectrum fully determines the second-largest eigenvalue, and regularity of the probability vector preserves the symmetries needed for the bound.

What would settle it

Direct numerical computation of the eigenvalues of the transition matrix for S_4 with a specific non-uniform regular probability vector, checking whether its second-largest eigenvalue is smaller than the uniform-case lower bound.

read the original abstract

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper settles Fill's conjecture with a sharp spectral gap bound for biased adjacent-transposition chains, using an algebraic decomposition into orthogonal projections that also gives the exact multiplicity.

read the letter

The main result is a sharp lower bound on the spectral gap of the biased adjacent-transposition chain on the symmetric group. Among regular probability vectors, the minimum is achieved exactly at the uniform distribution, which resolves Fill's conjecture. The authors also characterize the minimizers and compute the multiplicity of the second-largest eigenvalue directly from the decomposition of the transition matrix into elementary orthogonal projections. This approach is new; prior work had asymptotic or non-sharp bounds but not this level of precision for the biased case. The decomposition lets them read off the spectrum without comparison theorems or coupling, and the regularity condition appears sufficient to keep the projections orthogonal and commuting with respect to the stationary inner product. That handles the potential commutation issue for non-uniform vectors. The argument stays algebraic and avoids fitted parameters or self-referential quantities. One limitation is the restriction to regular vectors, which matches the conjecture but leaves general stationary distributions for later work. Within the stated setting the claims look solid. This is for people working on mixing times of walks on the symmetric group or on spectral methods for sampling. The math is clean enough to deserve a serious referee.

Referee Report

0 major / 2 minor

Summary. The manuscript establishes a sharp lower bound on the spectral gap of the biased adjacent-transposition Markov chain on the symmetric group. As a consequence, it resolves Fill's conjecture by proving that the uniform probability vector attains the minimum spectral gap among all regular probability vectors. The proof is based on a novel algebraic decomposition of the transition matrix into elementary orthogonal projections, and the authors also characterize the attaining vectors and the multiplicity of the second-largest eigenvalue.

Significance. If the result holds, it provides a definitive resolution to a longstanding open problem in the mixing times of Markov chains on the symmetric group, with potential implications for the analysis of biased shuffles and random permutations. The algebraic approach is a notable strength, offering an exact characterization without reliance on fitted parameters or asymptotic approximations.

minor comments (2)

[Theorem 1.1] In the statement of the main theorem, the precise definition of 'regular probability vector' should be recalled explicitly rather than referenced only to an earlier section.
[§3] The inner product notation induced by the stationary measure is introduced without an explicit formula; adding it would improve readability for the decomposition argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The referee's summary correctly identifies the main results, including the resolution of Fill's conjecture and the algebraic decomposition used in the proof.

Circularity Check

0 steps flagged

Novel algebraic decomposition yields independent spectral gap bound with no reduction to inputs

full rationale

The paper derives the sharp lower bound on the spectral gap via a new algebraic factorization of the transition matrix into elementary orthogonal projections, whose spectra are then used to identify the second-largest eigenvalue. This construction is presented as original and does not reduce to any fitted parameter, self-citation chain, or definitional equivalence with the target quantity. Regularity of the probability vector is invoked only to maintain reversibility and symmetry properties needed for the decomposition to apply, but the bound itself is obtained directly from the projection spectra rather than by construction from the conjecture or prior results. No load-bearing step collapses to a self-referential input, and the resolution of Fill's conjecture follows as a consequence of the independent derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based on the abstract alone, the central claim rests on standard algebraic structures of the symmetric group and the definition of regular probability vectors; no new free parameters or invented entities are introduced.

axioms (2)

standard math The symmetric group is generated by adjacent transpositions and carries the standard representation theory needed for orthogonal projections.
Invoked implicitly when the transition matrix is decomposed into projections on group representations.
domain assumption Regularity of the probability vector preserves the necessary commutation relations with the group action.
Required for the minimum to be attained at the uniform vector and for the multiplicity statement.

pith-pipeline@v0.9.0 · 5366 in / 1445 out tokens · 60715 ms · 2026-05-14T22:41:51.842343+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith.Foundation.RealityFromDistinction reality_from_one_distinction unclear
We decompose the transition matrix as K = 1/(n-1) ∑ E_r where each E_r is an elementary transition matrix... each E_r acts as an orthogonal projection... smallest positive eigenvalue of E_r + E_{r+1} is 1-m_p
IndisputableMonolith.Cost.FunctionalEquation washburn_uniqueness_aczel unclear
Lemma 2.3: E_r is the orthogonal projection onto V_r... Lemma 2.4 on pairs of orthogonal projections... Lemma 3.1: x f, K² f y ≥ (1-2 m_p cos(π/n)/(n-1)) x f, K f y

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

[1]

Aldous and P

D. Aldous and P. Diaconis,Shuffling cards and stopping times, Amer. Math. Monthly 93(1986), no. 5, 333–348

work page 1986
[2]

Aldous and J.A

D. Aldous and J.A. Fill,Reversible Markov Chains and Random Walks on Graphs, unfinished monograph, 2002 (recompiled version, 2014), available athttps://www. stat.berkeley.edu/users/aldous/RWG/book.html

work page 2002
[3]

Bacher,Minimal eigenvalue of the Coxeter Laplacian for the symmetrical group, J

R. Bacher,Minimal eigenvalue of the Coxeter Laplacian for the symmetrical group, J. Algebra167(1994), no. 2, 460–472

work page 1994
[4]

Benjamini, N

I. Benjamini, N. Berger, C. Hoffman, and E. Mossel,Mixing times of the biased card shuffling and the asymmetric exclusion process, Trans. Amer. Math. Soc.357(2005), no. 8, 3013–3029

work page 2005
[5]

Bez´ akov´ a, D.ˇStefankoviˇ c, V.V

I. Bez´ akov´ a, D.ˇStefankoviˇ c, V.V. Vazirani, and E. Vigoda,Accelerating simulated annealing for the permanent and combinatorial counting problems, inProceedings of the Seventeenth Annual ACM–SIAM Symposium on Discrete Algorithms (SODA 2006), Society for Industrial and Applied Mathematics, Philadelphia, PA, 2006, 900– 907

work page 2006
[6]

Bhakta, S

P. Bhakta, S. Miracle, D. Randall, and A.P. Streib,Mixing times of Markov chains for self-organizing lists and biased permutations, Random Struct. Algorithms61(2022), no. 4, 638–665

work page 2022
[7]

Bradley and M.E

R.A. Bradley and M.E. Terry,Rank analysis of incomplete block designs: I. The method of paired comparisons, Biometrika39(1952), no. 3/4, 324–345

work page 1952
[8]

Brouwer and W.H

A.E. Brouwer and W.H. Haemers,Spectra of Graphs, Universitext, Springer, New York, 2012

work page 2012
[9]

Caputo, T.M

P. Caputo, T.M. Liggett, and T. Richthammer,Proof of Aldous’ spectral gap conjec- ture, J. Amer. Math. Soc.23(2010), no. 3, 831–851

work page 2010
[10]

Coester,Transposition is nearly optimal for IID list update, preprint, arXiv:2603.10244 (2026)

C. Coester,Transposition is nearly optimal for IID list update, preprint, arXiv:2603.10244 (2026). SPECTRAL GAP OF BIASED ADJACENT-TRANSPOSITION CHAINS 19

work page arXiv 2026
[11]

Diaconis,Group Representations in Probability and Statistics, IMS Lecture Notes– Monograph Series, vol

P. Diaconis,Group Representations in Probability and Statistics, IMS Lecture Notes– Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988

work page 1988
[12]

Diaconis,From shuffling cards to walking around the building: an introduction to modern Markov chain theory, inProceedings of the International Congress of Math- ematicians, Vol

P. Diaconis,From shuffling cards to walking around the building: an introduction to modern Markov chain theory, inProceedings of the International Congress of Math- ematicians, Vol. I (Berlin, 1998), Doc. Math. 1998, Extra Vol. I, 187–204

work page 1998
[13]

Diaconis and L

P. Diaconis and L. Saloff-Coste,Comparison techniques for random walk on finite groups, Ann. Probab.21(1993), no. 4, 2131–2156

work page 1993
[14]

J. A. Fill,An interesting spectral gap problem, from Jim Fill, unpublished manuscript, 2003; reissued as arXiv:2508.12557 (2025)

work page arXiv 2003
[15]

Gheissari, H

R. Gheissari, H. Lee, and E. Vigoda,Mixing of general biased adjacent transposition chains, preprint, arXiv:2511.02725 (2025). Extended abstract to appear inProceedings of the 58th ACM Symposium on Theory of Computing (STOC 2026)

work page arXiv 2025
[16]

Haddadan and P

S. Haddadan and P. Winkler,Mixing of permutations by biased transpositions, Theory Comput. Syst.63(2019), no. 5, 1068–1088

work page 2019
[17]

Hendricks,Self-organizing Markov Chains, MITRE Corporation, McLean, VA, 1989

W.J. Hendricks,Self-organizing Markov Chains, MITRE Corporation, McLean, VA, 1989

work page 1989
[18]

Hester and D.S

J.H. Hester and D.S. Hirschberg,Self-organizing linear search, ACM Comput. Surv. 17(1985), no. 3, 295–311

work page 1985
[19]

Labb´ e and H

C. Labb´ e and H. Lacoin,Cutoff phenomenon for the asymmetric simple exclusion process and the biased card shuffling, Ann. Probab.47(2019), no. 3, 1541–1586

work page 2019
[20]

Y. Li, B. Xia, and S. Zhou,The second largest eigenvalue of some nonnormal Cayley graphs on symmetric groups, J. Combin. Theory Ser. A,218(2026)

work page 2026
[21]

Miracle and A.P

S. Miracle and A.P. Streib,Rapid mixing ofk-class biased permutations, SIAM J. Discrete Math.38(2024), no. 1, 702–725

work page 2024
[22]

Miracle, A.P

S. Miracle, A.P. Streib, and N. Streib,Iterated decomposition of biased permutations via new bounds on the spectral gap of Markov chains, Theory Comput.21(2025), Art. 3, 1–41

work page 2025
[23]

Wilson,Mixing times of lozenge tiling and card shuffling Markov chains, Ann

D.B. Wilson,Mixing times of lozenge tiling and card shuffling Markov chains, Ann. Appl. Probab.14(2004), no. 1, 274–325. Division of Mathematical Sciences, Nanyang Technological University, 21 Nanyang Link, Singapore 637371 Email address:gary@ntu.edu.sg Division of Mathematical Sciences, Nanyang Technological University, 21 Nanyang Link, Singapore 637371 ...

work page 2004