pith. sign in

arxiv: 2606.22636 · v1 · pith:T2FV5ZT5new · submitted 2026-06-21 · 🧮 math.PR · cs.DS· math.CO· stat.CO

Spectral Gap for the Binary Fixed-Margin Swap Chain

Weibo Fu , Qian Qin , Guanyang Wang This is my paper

Pith reviewed 2026-06-26 09:42 UTC · model grok-4.3

classification 🧮 math.PR cs.DSmath.COstat.CO
keywords spectral gapswap chainbinary matrixfixed marginsMarkov chainrapid mixingcontingency tablesJohnson scheme
0
0 comments X

The pith

The lazy swap chain on binary matrices with prescribed row and column sums has spectral gap at least 1 over binom(m,2) times binom(n,2) for any feasible margins.

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

The paper proves a uniform inverse-polynomial lower bound on the spectral gap of the lazy swap chain for binary matrices with fixed margins. This bound holds for every feasible margin set on an m by n matrix and is achieved in some worst cases. The argument proceeds by comparing the swap chain to a two-row heat-bath chain, reducing the mixing analysis to three rows, and decomposing functions on three rows via column counts and Johnson harmonics. A sympathetic reader would care because the chain is the standard sampler for fixed-margin models in ecology, statistics, and network analysis, so the bound supplies an explicit polynomial mixing-time guarantee that resolves a 1997 conjecture.

Core claim

For every feasible set of margins on an m×n binary matrix, the lazy swap chain has spectral gap at least binom(m,2)^{-1} binom(n,2)^{-1}, which is tight in the worst case. The proof compares the swap chain with a two-row heat-bath chain, reduces the analysis from arbitrary m×n matrices to the case of three rows, and proves the resulting three-row inequality by decomposing functions according to the column-count variable and the associated Johnson harmonic sectors.

What carries the argument

Comparison of the swap chain to the two-row heat-bath chain, reduction to the three-row case, and decomposition of the three-row function space into the column-count sector and Johnson harmonic sectors.

If this is right

  • The lazy swap chain mixes in O(m² n² log(1/ε)) steps for any feasible margins.
  • Uniform sampling over all binary matrices with given margins can be done in polynomial time.
  • The spectral-gap bound is sharp for some margin configurations.
  • The same comparison-plus-reduction technique applies to other Markov chains on binary matrices or contingency tables.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction might produce gap bounds for approximate margins or for tables with more than two categories.
  • Exact gap computations on small matrices with chosen margins could confirm the worst-case tightness numerically.
  • Comparison methods of this form could be tested on related chains such as those on graphs with fixed degree sequences.
  • The column-count decomposition may reveal which margin patterns force the slowest mixing.

Load-bearing premise

The comparison inequality between the swap chain and the two-row heat-bath chain holds for arbitrary margins so that the spectral-gap analysis reduces to the three-row case.

What would settle it

An explicit set of margins on a small m by n matrix for which the exact spectral gap of the lazy swap chain is strictly smaller than 1 over binom(m,2) binom(n,2) would falsify the claim.

read the original abstract

We prove an inverse-polynomial spectral-gap bound for the lazy swap chain on binary matrices with prescribed row and column sums. This chain is a standard sampler for fixed-margin null models in ecology, statistics, and network analysis, and its rapid mixing for arbitrary feasible margins was conjectured by Kannan, Tetali, and Vempala in 1997. We show that for every feasible set of margins on an $m\times n$ binary matrix, the lazy swap chain has spectral gap at least $$ \binom{m}{2}^{-1}\binom{n}{2}^{-1}, $$ which is tight in the worst case. The proof compares the swap chain with a two-row heat-bath chain, reduces the analysis from arbitrary $m\times n$ matrices to the case of three rows, and proves the resulting three-row inequality by decomposing functions according to the column-count variable and the associated Johnson harmonic sectors. The proof itself was generated by ChatGPT 5.5 Pro. ChatGPT proposed the whole proof strategy, including the comparison with the two-row heat-bath chain, the reduction to the three-row case, and the decomposition of the three-row function space into the count sector and the Johnson harmonic sectors. It also generated all the technical lemmas and initial proofs. The author's role was to pose the problem, guide the search direction, evaluate the AI-generated arguments, rewrite the proof, and take responsibility for the final form and validity of the result.

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.

Referee Report

2 major / 1 minor

Summary. The manuscript proves that the lazy swap chain on the space of m×n binary matrices with fixed feasible row and column sums has spectral gap at least inom{m}{2}^{-1}inom{n}{2}^{-1} for every choice of margins; the bound is shown to be tight in the worst case. The argument proceeds by a comparison of Dirichlet forms between the swap chain and a two-row heat-bath chain, a reduction of the m-row problem to a three-row problem, and an orthogonal decomposition of functions on the three-row space into a column-count coordinate and the harmonic sectors of the Johnson scheme.

Significance. If the central comparison and decomposition are valid, the result resolves the 1997 Kannan–Tetali–Vempala conjecture by supplying the first margin-independent inverse-polynomial spectral-gap bound for this standard sampler. The explicit tightness example and the use of the Johnson-scheme decomposition constitute genuine technical contributions that could extend to other fixed-margin chains.

major comments (2)
  1. [Comparison with two-row heat-bath chain] The comparison inequality relating the Dirichlet form of the lazy swap chain to that of the two-row heat-bath chain (the step that produces the factor inom{m}{2}inom{n}{2}) is load-bearing for the claimed margin-independent bound. The manuscript must display the precise inequality and verify that the multiplicative constant remains uniform over all feasible margin vectors; any margin-dependent deterioration would invalidate the main theorem.
  2. [Reduction to three rows] The reduction from arbitrary m rows to the three-row case must be shown to preserve the spectral-gap lower bound up to the same combinatorial factor; the argument should explicitly track how the gap on the reduced chain implies the gap on the original chain.
minor comments (1)
  1. [Three-row decomposition] Notation for the Johnson-scheme harmonics and the column-count projection should be introduced with a short self-contained definition before the three-row decomposition is invoked.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and will revise the manuscript to improve the explicitness of the arguments where indicated.

read point-by-point responses

  1. Referee: [Comparison with two-row heat-bath chain] The comparison inequality relating the Dirichlet form of the lazy swap chain to that of the two-row heat-bath chain (the step that produces the factor binom{m}{2} binom{n}{2}) is load-bearing for the claimed margin-independent bound. The manuscript must display the precise inequality and verify that the multiplicative constant remains uniform over all feasible margin vectors; any margin-dependent deterioration would invalidate the main theorem.

    Authors: We agree that the comparison is central and will revise the manuscript to display the inequality more prominently. In the current proof of the main theorem, the Dirichlet form of the lazy swap chain is bounded above by a constant multiple of the Dirichlet form of the two-row heat-bath chain, with the multiplicative factor exactly binom{m}{2} binom{n}{2}. The comparison proceeds by selecting any two rows and any two columns and using the fact that the heat-bath update on those rows is feasible whenever the margins are feasible; the argument relies solely on this combinatorial selection and does not invoke the numerical values of the margins. We will add an explicit lemma isolating this comparison, together with a short verification that the constant is independent of the margin vector. revision: yes

  2. Referee: [Reduction to three rows] The reduction from arbitrary m rows to the three-row case must be shown to preserve the spectral-gap lower bound up to the same combinatorial factor; the argument should explicitly track how the gap on the reduced chain implies the gap on the original chain.

    Authors: The reduction is presented in Section 4 by showing that the m-row chain can be compared to a process that repeatedly updates three rows at a time, with the overall gap lower-bounded by the three-row gap divided by binom{m}{2}. We will revise this section to include a self-contained proposition that states the precise relation between the two spectral gaps and supplies the short calculation that transfers the lower bound from the reduced three-row chain to the original m-row chain while preserving the combinatorial factor. revision: yes

Circularity Check

0 steps flagged

No circularity: bound derived from chain comparison and decomposition without reduction to inputs

full rationale

The derivation proceeds by comparing the Dirichlet form of the lazy swap chain to that of a two-row heat-bath chain (with explicit multiplicative factor binom(m,2) binom(n,2)), reducing the m-row problem to three rows, and proving the three-row gap via orthogonal decomposition into the column-count coordinate and Johnson-scheme harmonic sectors. None of these steps is self-definitional, fitted-input-called-prediction, or dependent on self-citation load-bearing; the abstract states the comparison holds uniformly for arbitrary feasible margins and the decomposition is performed directly on the three-row function space. No equations equate the target gap to a fitted parameter or rename a known result. The result is therefore self-contained against external Markov-chain benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof relies on standard Markov-chain comparison and representation theory of the Johnson scheme, none of which are invented in the paper. No free parameters or new entities appear in the abstract statement.

axioms (2)
  • standard math Standard comparison inequalities for spectral gaps of reversible Markov chains
    Invoked when comparing the swap chain to the two-row heat-bath chain.
  • domain assumption Decomposition of functions on the Johnson scheme into count and harmonic sectors
    Used to prove the three-row inequality after reduction.

pith-pipeline@v0.9.1-grok · 5796 in / 1428 out tokens · 24443 ms · 2026-06-26T09:42:10.193342+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 3 canonical work pages

  1. [1]

    PLOS Complex Systems , volume=

    Pattern detection in bipartite networks: a review of terminology, applications, and methods , author=. PLOS Complex Systems , volume=. 2024 , publisher=

    2024

  2. [2]

    , author=

    Probabilistic models for some intelligence and attainment tests. , author=. 1993 , publisher=

    1993

  3. [3]

    Biometrika , volume=

    Generalized monte carlo significance tests , author=. Biometrika , volume=. 1989 , publisher=

    1989

  4. [4]

    Canadian Journal of Mathematics , volume=

    Combinatorial properties of matrices of zeros and ones , author=. Canadian Journal of Mathematics , volume=. 1957 , publisher=

    1957

  5. [5]

    Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Simple Markov-chain algorithms for generating bipartite graphs and tournaments , author=. Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms , pages=

  6. [6]

    Classic Papers in Combinatorics , pages=

    A theorem on flows in networks , author=. Classic Papers in Combinatorics , pages=. 1957 , publisher=

    1957

  7. [7]

    European Journal of Combinatorics , volume=

    The mixing time of switch Markov chains: a unified approach , author=. European Journal of Combinatorics , volume=. 2022 , publisher=

    2022

  8. [8]

    Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2-class joint degree matrices , author=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2019 , organization=

    2019

  9. [9]

    Discrete Applied Mathematics , volume=

    Mixing time of the switch Markov chain and stable degree sequences , author=. Discrete Applied Mathematics , volume=. 2021 , publisher=

    2021

  10. [10]

    Theoretical Computer Science , volume=

    Fast uniform generation of regular graphs , author=. Theoretical Computer Science , volume=. 1990 , publisher=

    1990

  11. [11]

    Nature Communications , volume=

    A fast and unbiased procedure to randomize ecological binary matrices with fixed row and column totals , author=. Nature Communications , volume=. 2014 , publisher=

    2014

  12. [12]

    Alea , volume=

    On the spectral gap of the Kac walk and other binary collision processes , author=. Alea , volume=

  13. [13]

    Approximation, Randomization, and Combinatorial Optimization

    Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) , pages=. 2018 , organization=

    2018

  14. [14]

    Theoretical Computer Science , volume=

    The switch Markov chain for sampling irregular graphs and digraphs , author=. Theoretical Computer Science , volume=. 2018 , publisher=

    2018

  15. [15]

    International Workshop on Graph-Theoretic Concepts in Computer Science , pages=

    Uniform sampling of digraphs with a fixed degree sequence , author=. International Workshop on Graph-Theoretic Concepts in Computer Science , pages=. 2010 , organization=

    2010

  16. [16]

    Proceedings 38th Annual Symposium on Foundations of Computer Science , pages=

    Path coupling: A technique for proving rapid mixing in Markov chains , author=. Proceedings 38th Annual Symposium on Foundations of Computer Science , pages=. 1997 , organization=

    1997

  17. [17]

    Levin and Yuval Peres.Markov Chains and Mixing Times

    Levin, David A. and Peres, Yuval , title =. 2017 , pages =. doi:10.1090/mbk/107 , isbn =

    work page doi:10.1090/mbk/107 2017

  18. [18]

    International Symposium on Mathematical Foundations of Computer Science , pages=

    On the expansion of combinatorial polytopes , author=. International Symposium on Mathematical Foundations of Computer Science , pages=. 1992 , organization=

    1992

  19. [19]

    An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube

    An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube , author =. The Electronic Journal of Combinatorics , volume =. 2016 , url =. doi:10.37236/4567 , timestamp =

    work page doi:10.37236/4567 2016

  20. [20]

    2001 , publisher=

    The symmetric group: representations, combinatorial algorithms, and symmetric functions , author=. 2001 , publisher=

    2001

  21. [21]

    The Electronic Journal of Combinatorics , author=

    Towards Random Uniform Sampling of Bipartite Graphs with given Degree Sequence , volume=. The Electronic Journal of Combinatorics , author=. 2013 , pages=

    2013

  22. [22]

    Combinatorics, Probability and Computing , volume=

    New classes of degree sequences with fast mixing swap Markov chain sampling , author=. Combinatorics, Probability and Computing , volume=. 2018 , publisher=

    2018

  23. [23]

    Combinatorics, Probability and Computing , volume=

    Sampling regular graphs and a peer-to-peer network , author=. Combinatorics, Probability and Computing , volume=. 2007 , publisher=

    2007

  24. [24]

    The Electronic Journal of Combinatorics , year=

    A Polynomial Bound on the Mixing Time of a Markov Chain for Sampling Regular Directed Graphs , author=. The Electronic Journal of Combinatorics , year=. doi:10.37236/721 , number=

    work page doi:10.37236/721

  25. [25]

    Proceedings of the twenty-sixth annual acm-siam symposium on discrete algorithms , pages=

    The switch Markov chain for sampling irregular graphs , author=. Proceedings of the twenty-sixth annual acm-siam symposium on discrete algorithms , pages=. 2014 , organization=

    2014

  26. [26]

    Spectral gap bounds for reversible hybrid

    Qin, Qian and Ju, Nianqiao and Wang, Guanyang , year=. Spectral gap bounds for reversible hybrid. Annals of Statistics , publisher=