← All papers
First page of Spectral Gap for the Binary Fixed-Margin Swap Chain

Spectral Gap for the Binary Fixed-Margin Swap Chain

Weibo Fu, Qian Qin, Guanyang Wang

math.PR Jun 21, 2026 · v2 cs.DS math.CO stat.CO
The full proof of the main spectral-gap theorem for the binary fixed-margin swap chain is formalized in Lean, with a public repository.
We prove an explicit spectral-gap lower 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. Kannan, Tetali, and Vempala (KTV) conjectured that it mixes rapidly for all feasible margins \citep{kannan1997simple}. 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}.$$ The bound is tight in the worst case. Thus, our result proves this KTV conjecture in a stronger quantitative form. The same spectral-gap bound also verifies the Mihail–Vazirani conjecture for fixed-margin 0/1-matrix polytopes. The proof gives a new route to fixed-margin sampling that avoids stability assumptions and canonical-path constructions. We compare the swap chain with a two-row heat-bath chain and use a local-to-global spectral reduction to reduce the analysis from arbitrary $m\times n$ matrices to a three-row problem. The remaining three-row inequality is then proved by separating the scalar column-count sector from the non-scalar Johnson harmonic sectors. The proof itself was generated by ChatGPT 5.5 Pro. 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. The full proof of the main theorem has been formalized in Lean, and the accompanying formalization is available at the anonymous repository https://github.com/guanyangwang/ktv-swap-lean.

Kannan, Tetali, and Vempala conjectured that the swap chain on binary matrices with prescribed row and column sums mixes rapidly for all feasible margins. This chain is a standard sampler for fixed-margin null models.

The lazy swap chain is compared with a two-row heat-bath chain. A local-to-global spectral reduction then reduces the m×n analysis to a three-row problem. The three-row inequality is proved by separating the scalar column-count sector from the non-scalar Johnson harmonic sectors. The proof was generated with ChatGPT 5.5 Pro and rewritten by the author, and the main theorem was formalized in Lean.

For every feasible margin, the spectral gap is at least binom(m,2)^{-1} binom(n,2)^{-1}, and this bound is tight in the worst case. This proves the KTV conjecture in a stronger quantitative form and verifies the Mihail–Vazirani conjecture for fixed-margin 0/1-matrix polytopes.