The zero-free disk conjecture for bipartite matching at k=4: an effective Janson comparison and a finite certificate table
Abstract
Let the mn edges of K_(m,n) carry independent mean-one exponential costs and let C_(k,m,n) be the minimum cost of a k-matching. Wästlund showed that the moment generating function F_(k,m,n)(t)=E e^(tC_(k,m,n)) is a rational function of t whose first pole sits at t=mn/k, and conjectured that it has no complex zero in the open disk |t|<mn/k; the conjecture would give a Gaussian scaling limit for the random assignment problem. He proved it for k ≤ 3 by comparison with a real-rooted function of Janson, remarked that there "seems to be no hope of generalizing this argument to higher values of k", and proved — non-effectively, with no bound on the exceptions — that for each k only finitely many pairs (m,n) can fail. We settle the first open case, k=4, for the explicit numerator: for all integers m,n ≥ 4 the degree-six polynomial widehat P_(4,m,n) has no zero in the closed disk |t| ≤ mn/4. Modulo Wästlund's identification of widehat P_(4,m,n) with the numerator of F_(4,m,n), which we quote from his paper and do not reprove, this is his conjecture at k=4. The proof makes his own comparison effective. We compute the discrepancy E=widehat P₄-D₃ between the numerator and Janson's in closed form over ℚ(m,n) — four coefficients, one of them the clean e₅=22/∏_(i+j<3)(m-i)(n-j) — and reduce the comparison to the positivity of an explicit integer polynomial W of bidegree (10,10). We then determine the positivity region of W exactly. On the integer quadrant it is precisely the region the comparison covers, so the comparison fails at every one of the 235 residual pairs and at no other pair; each of those pairs is closed instead by an exactly verified dominance certificate, and the failure region of the comparison and the certificate table coincide. Over the reals the region the certificates cover is a staircase of fourteen closed quadrants, no corner of which can be moved inwards inside the domain m,n ≥ 4, and on it the zero-free disk holds for real parameters — in particular for all real m,n ≥ 11 and all real m ≥ 4, n ≥ 62, real parameters being the generality in which Wästlund states his own k ≤ 3 result. The radius is close to sharp: widehat P_(4,4,4) has a real zero below 1.0776 · mn/4, so the statement has about 7.5 of slack at its tightest pair. The results below are machine-checked in Lean 4; the last section says exactly what that covers and what it does not.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 2 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
7c3dd1d6cbe5e11d9ae074d7720858987794f42bc53aa517693783d576c6b938
Claim ledger
Stated results
WZ1routine2026-09-03
Dominance lemma over the complex numbers: if sumⱼ |bⱼ| Rʲ < |p0| prodᵢ (1 - R/|rhoᵢ|) then p0 prodᵢ (1 - t/rhoᵢ) + B has no zero on the CLOSED disk |t| <= R; the comparison factors are given as rational linear factors and conjugate-pair quadratics 1 - b t + a t² with the side conditions b² <= 4a, a <= u², uR < 1
WZ2candidate2026-09-03
The k = 4 case of Wastlund's zero-free disk conjecture, as a polynomial theorem: for all integers m, n >= 4 the explicit degree-6 numerator Phat_(4,m,n) has no complex zero with |t| <= mn/4 (the closed disk, slightly stronger than the conjecture's open disk)
WZ3candidate2026-09-03
Tail: the integer polynomial W of bidegree (10,10) that expresses Janson dominance at k = 4 satisfies W(m,n) > 0 for all real m, n >= 11 and, for each m in 4..10, for all n >= n0(m) with n0 = (62,32,22,17,14,12,11); each threshold is sharp, W(m, n0(m)-1) < 0
WZ4candidate2026-09-03
Core: dominance certificates for all 235 residual ordered pairs (m,n) not covered by the tail (all with m, n <= 61), together with the control that the Janson comparison alone genuinely fails there – W(4,4) = -260617273344 < 0
WZ5known2026-09-03
Wastlund's P:zeroFree3 re-proved from the same dominance lemma: Phat_(3,m,n) has no zero on the closed disk |t| <= mn/3 for all real m, n >= 3, kernel-clean
WZ6candidate2026-09-03
Sharpness at the worst cell: Phat_(4,4,4) has a real zero strictly between 43/10 and 431/100, while the conjectured radius there is mn/4 = 4, so the closed-disk radius cannot be widened past 1.0776 mn/4 at k = 4; and the (4,4) certificate itself fails when the radius is widened by 10%
WZ7candidate2026-09-03
The E-coefficient closed forms at k = 4, derived by running the source's recursion with m and n both symbolic in exact Q(m,n): E = Phat₄ - D₃ has e0 = e1 = e6 = 0, each Delta*eⱼ is an integer polynomial symmetric in m<->n of bidegree (7,7), (6,6), (5,5), (4,4), and e5 = 22 / prod_(i+j<3) (m-i)(n-j)
WZ8prose2026-09-03
Conjecture C:zeroFree of arXiv:2602.07563v1 holds for k = 4: identifying Phat₄ with the numerator of the moment generating function F_(4,m,n) (the source's T:matchingRecursion and P:polynomialDegrees) turns WZ2 into the conjecture's first open case
This ledger entry is reported in prose and is not bound to a Lean theorem.WZ9prose2026-09-03
Two printing errata in the source's proof of P:zeroFree3: both cubic coefficients are printed +2t³ and should be -2t³, and the printed P/Q equals F divided by mn(m-1)(n-1)(m-2)(n-2); the proposition and its proof are unaffected
This ledger entry is reported in prose and is not bound to a Lean theorem.WZ10measurement2026-09-03
Measured degradation of the Janson comparison for k >= 5: the dominance ratio sumⱼ |eⱼ| Rʲ / Dₖ₋₁(R) at (m,n) = (k,k) is 87.3, 1.013e5, 7.143e8, 3.531e13 for k = 4,5,6,7, decaying like 1/n along a strip, which gives k = 5 a residual box of about 7e4 ordered cells and prices it at >= 10 CPU-h and 85 MB of certificates – parked
This ledger entry is reported in prose and is not bound to a Lean theorem.WZ11candidate2026-09-03
Sharpness of the seven tail thresholds at k = 4: for every m in 4..10 the bidegree-(10,10) integer polynomial W satisfies W(m, n0(m) - 1) < 0 with n0 = (62,32,22,17,14,12,11), and W(m, n0(m)) > 0, so the sign of W(m,.) changes exactly at n0(m); the seven values are -2855815750231550853120, -98233363771313400000, -21837476603522764800, -17076160393799270400, -16952052402251366400, -17245491208654705920, -15025554432000000000, all kernel decide on the integer coefficient table
WZ12candidate2026-09-03
tailOK is exactly the positivity region of W on the integer quadrant: for all integers m, n >= 4, 0 < W(m,n) if and only if tailOK m n. Equivalently the Janson comparison fails at EVERY one of the 235 residual pairs, not only at (4,4); the residual set has exactly 235 members with row profile (58,28,18,13,10,8,7) for m = 4..10
WZ13candidate2026-09-03
The k = 4 tail is a real staircase, not seven integer strips: for each a in 4..10 the two-variable shift W(a + u, n0(a) + v) has all 121 coefficients >= 0 with positive constant term, so W > 0 on the whole real quadrant [a, inf) x [n0(a), inf) and its transpose; the union of the fourteen quadrants contains the entire integer tail region tailOK (the quadrant m, n >= 11 included, as it sits inside [10,inf) x [11,inf)), and each corner is sharp in both coordinates
WZ14known2026-09-03
Wastlund's P:zeroFree3 for real parameters: Phat_(3,m,n) has no zero on the closed disk |t| <= mn/3 for all REAL m, n >= 3, proved from a real-coefficient dominance lemma lemDᵣeal; identified with the rational statement WZ5 by phat3R_qcast, phat3R (m:R) (n:R) z = cev (phat3 m n) z
WZ15candidate2026-09-03
The k = 4 zero-free closed disk for REAL parameters: Phat_(4,m,n) has no complex zero with |t| <= mn/4 for all real (m,n) in the staircase region of WZ13 – in particular for all real m, n >= 11 and for all real m >= 4, n >= 62 – identified with the integer/rational statement WZ2 by phat4R_qcast, phat4R (m:R) (n:R) z = cev (phat4 m n) z
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- K_(m,n) carries mn independent mean-one exponential edge costs. For k ≤ min(m,n), C_(k,m,n) is the minimum total cost of a k-matching (a set of k pairwise vertex-disjoint edges); C_(n,n,n) is the random assignment problem. Wästlund (arXiv:2602.07563v1, math.PR, 7 Feb 2026) studies the moment generating function
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7