Date: 2026-11-20; revised 2026-11-21 UTC. Status: complete proposed proof of the previously missing threshold direction, including an independent repair of the face reduction, with three independent internal reviews. The source audit found no earlier full threshold proof; priority remains provisional. This is a named subsidiary conjecture discussed under Minc Problems 14 and 15. It does not characterize all cohesive or barycentric supports, and is not a solution of either complete Minc entry.
Statement and prior results
Write J_{r,s} for the all-ones rectangular matrix and define
For a binary support D, let Ω(D) be the doubly stochastic matrices vanishing at its zero positions. A support is cohesive if this face has a permanent minimizer positive on its entire active support. It is barycentric if the average of its supported permutation matrices is a minimizer.
Pula, Song and Wanless, Minimum permanents on two faces of the polytope of doubly stochastic matrices, Linear Algebra Appl. 434 (2011), 232–238, Conjecture 2.1, proposed that for positive m and n>1:
- V_{m,n} is cohesive but not barycentric when n<m+√m.
- V_{m,n} is not cohesive when n≥m+√m, and the barycenter of Ω(U_{m,n}) minimizes the permanent on Ω(V_{m,n}).
The equality sign at the threshold is confirmed in the PDF image and the publisher abstract; text extraction sometimes changes ≥ to >. The cases m<4 or n<4 were already settled by the literature cited in the original introduction and are not new here. In particular m=1 was covered by Brualdi. The original paper states the cohesive direction and the noncohesive direction for n≥2m. Song (2013) identifies a boundary issue in its reduction and proves the m=4 threshold case. Independently, the displayed perturbation of formula (4) in the available 2011 preprint does not follow from the identities used to obtain that formula: some identities hold only at the candidate minimizer. Section 1 below replaces this reduction with a real-rooted-polynomial proof, handling both boundary and interior cases. We do not rely on the original paper's asserted uniqueness on Ω(U_{m,n}).
Cheon–Song (2024) still treats only special cases of the threshold conjecture. Lavi's current Problem 15 page already states non-barycentricity for every m,n≥2. That assertion is credited as prior progress; an independent proof is supplied below to make the combination checkable. We also rederive the known cohesive direction after the repaired reduction.
The proposed new theorem is:
For all positive m and n>1 with n≥m+√m, the permanent on Ω(V_{m,n}) has the unique minimizer
Its permanent is
Together with Sections 4.2 and 5, this settles the stated subsidiary conjecture for all its parameters.
1. An independent repair of the face reduction
Two established ingredients are used here. Minc's repeated-support averaging theorem permits averaging rows or columns with identical allowed support at a permanent minimizer, preserving minimality. Foregger's minimizer lemma says that on a fully indecomposable binary support D, every minimizing matrix Y is fully indecomposable, and its permanental cofactors satisfy
These are the averaging theorem of Minc (1984) and the lemma of Foregger (1980), quoted as Lemma 1.1 in the 2011 paper. The supports V_{m,n} are fully indecomposable for m≥1,n>1.
The averaging step can also be checked directly from (R1) and the Alexandrov–Fenchel inequality for permanents. Hold all but two rows fixed and write the permanent as the symmetric bilinear form F(u,v). Suppose the two rows have the same allowed support S and the current permanent is P. The cofactor inequalities (R1) give F(u,u)≥P and F(v,v)≥P, since each row sums to one. Alexandrov–Fenchel gives F(u,v)²≥F(u,u)F(v,v). Since F(u,v)=P, both diagonal terms equal P. Bilinearity then gives F((u+v)/2,(u+v)/2)=P. Repeated pair averaging and continuity give averaging over any collection of identical-support rows. Columns follow by transposition. This use of averaging is restricted to minimizers.
Start with any minimizer and average its last m rows and then its last m columns. The resulting minimizer Y has entries
Here 0<a_i≤1/m; positivity follows from full indecomposability because a_i=0 would isolate row and column i. The equality of the two cross-block parameters follows from the row and column sum constraints. We prove that every a_i is equal.
1.1 A minor polynomial is log-concave
For diagonal D=diag(D_1,...,D_N) with D_i≥0 and a nonnegative vector b, define
Expanding by the subset of top vertices that use cross-block edges gives the exact differential-operator identity
For a subset of size k, both sides have coefficient times the corresponding product of b_i² and the remaining D_i. Each operator c+e(d/dy), with c,e≥0, preserves real-rootedness of a polynomial whose roots are real and nonpositive, or produces zero. This follows from derivative interlacing for c,e>0, with the derivative and constant cases immediate. Nonnegative coefficients keep all resulting real roots nonpositive. Thus q is zero or has only real nonpositive roots. For every y≥0 it satisfies
For q(y)>0 this is obtained by differentiating the logarithm of its factorization; at zero it follows by continuity. This proof also covers zero D_i directly, with no division or limit in (R2).
1.2 Equalization from cofactor inequalities
Assume m≥2 and suppose two cross parameters differ. Relabel them as u=a_1<v=a_n. Put
The two positive cross-block cofactors in (R1) give, by expansion,
Subtracting and using u<v yields
Also p_1>0: otherwise (R4) gives p_2=0, and the preceding expression would force per Y=0, impossible for a doubly stochastic matrix.
Since u<v≤1/m, the upper diagonal entry 1-mu is positive. If 1-mv is also positive, the two diagonal cofactors equal per Y. If 1-mv=0, its cofactor is at least per Y. In both cases,
so
Now regard the bottom-block entry y of the minor defining p_0 as variable. It has the form in (R2), with the other top diagonal entries D_i=1-ma_i. At the actual y=x,
Using (R3) and (R4),
Together (R5) and (R6) imply
But u,v≤1/m gives 1/u+1/v≥2m. This contradiction proves that all a_i are equal. It treats boundary and interior upper diagonal entries without perturbing identities that hold only at a critical point.
If m=1, the same cross-cofactor equality has no p_2 term. It reads u(1-v)p_1=v(1-u)p_1; the cofactor is positive, so p_1>0 and u=v immediately. Thus equalization also holds for m=1.
1.3 Consequences for the full face
The row and column sums now show that an averaged minimizer has the form
For n≥m the admissible interval is 0≤x≤1/m; for m>n it is (m-n)/m²≤x≤1/m. Averaging preserves the sum of all entries in the lower-right m-by-m block and preserves every upper diagonal entry. Therefore, if A_0 is the only reduced minimizer in the threshold range, every original minimizer has a zero lower-right block and upper diagonal (n-m)I_n/n. This proves noncohesiveness once the scalar theorem is established. Full-face uniqueness will be proved separately by the ordinary van der Waerden theorem in Section 4.1, without importing the original paper's disputed reduction.
2. A polynomial identity
Set d=n-m>0 and t=mx. Define
Here (d+1)_0=1. Counting a permutation according to the number i of its lower-right-block entries gives
For completeness, the coefficient before the matrix weights is , where i'=d+i counts the top diagonal entries; simplification yields . Equivalently choose the top diagonal positions, the lower-right rows and columns, and the three remaining bijections.
Put
Equation (1) becomes, for 0≤t<1,
Every coefficient of F is positive. The ratio of successive coefficients is
It follows by comparing coefficients that
Thus no special-function theorem is needed for the threshold proof. This is also the differential equation of a generalized Laguerre polynomial evaluated at -z.
3. The logarithmic derivative
Define
Equation (3) gives the Riccati identity
Since F(0)=1, μ is analytic near zero. Direct differentiation of z(t) gives
Differentiating (2), the elementary factors combine to
Indeed their contribution is -mtK(t). Hence it remains to prove h(t)>0 for 0<t<1 when d²≥m.
4. A first-zero argument
Suppose h(t)=0 at some interior t, so μ(z(t))=mt. Substituting into (4) yields
Together with (5), this gives at every zero of h:
and therefore
whenever d²≥m and t>0.
We also need the initial sign; h(0)=0 is not enough. The coefficient expansion is
while
Thus
When d²>m, h is positive for sufficiently small positive t. At equality m=d², the next coefficient is
which is again positive for sufficiently small positive t.
If h later became nonpositive, continuity would give a first positive zero reached from positive values. Differentiability at that zero would force h'≤0. This contradicts (8). Hence h>0 on (0,1).
By (6), f is strictly increasing on (0,1), and continuity at both endpoints gives f(t)>f(0) for every 0<t≤1. Equation (2) gives
The repaired averaging argument in Section 1 shows that this is the global minimum on Ω(V_{m,n}), attained by A_0, and that every full-face minimizer has zero lower-right block. In particular V_{m,n} is not cohesive when n≥m+√m, including every equality case m=d², n=d²+d.
4.1 Uniqueness on the entire face
Let Y be any minimizer in this range. Section 1.3 shows that
The n-by-m matrix L has row sums m/n and column sums 1. The m-by-n matrix K has row sums 1 and column sums m/n. Average only the bottom m rows; Minc's theorem preserves the minimum and replaces K by J_{m,n}/n while leaving L unchanged. The permanent of the result is
Complete L to the n-by-n doubly stochastic matrix
Its permanent is
Combining (U1), (U2), and the already proved minimum value forces per B=n!/n^n. Equality in the van der Waerden theorem therefore gives B=J_n/n, so L=J_{n,m}/n. This L was unchanged by the bottom-row averaging. Apply the same expansion to the original Y, now with L uniform, and use the doubly stochastic completion [K^{T}|J_{n,d}/n]. Equality again forces K=J_{m,n}/n. Thus Y=A_0.
4.2 The known cohesive side, after the repaired reduction
We rederive this side to avoid depending implicitly on the original equalization argument. Suppose n<m+√m. If n>m, put d=n-m. The expansions in Section 4 show
At the opposite endpoint, the i=m term of (1) has first derivative f'(1)=2m f(1)>0, and every other term vanishes to order at least two at t=1. Neither endpoint minimizes, so a reduced minimizer is interior and V_{m,n} is cohesive.
If m≥n, put d=m-n and use the upper diagonal parameter a. The reduced family has cross entries (1-a)/m and bottom entries (d+na)/m², with 0≤a≤1. Its permanent is a positive constant times
For d>0 its logarithmic derivative at a=0 is -n/(d+1)<0. For d=0, the F factor is 1+O(a²), giving logarithmic derivative -2n<0. At a=1 the logarithmic derivative is 2n>0, as seen from the leading term. Compactness and the repaired reduction therefore produce a minimizer with 0<a<1, positive at every allowed entry. This proves cohesiveness for all n<m+√m, the already known side of the conjecture.
5. Independent proof of the already stated non-barycentricity
Lavi's current Problem 15 page already asserts this result for every m,n≥2. We do not claim it as new. The following proof verifies that it can be combined with the threshold theorem without an unproved subsidiary assumption.
A variance lemma
For positive integers q and nonnegative integers d, let
This polynomial has q distinct negative roots. A short proof avoids an external zero theorem. Put Q(x)=F_{q,d}(-x). For every integer j with 0≤j<q,
The last sum is the qth finite difference of a polynomial in i of degree j<q. Orthogonality against every polynomial of degree below q, with strictly positive weight on (0,∞), forces Q to have q distinct positive roots: otherwise the polynomial having exactly its sign-changing roots would have degree below q, and its product with Q would have constant nonzero sign, contradicting orthogonality.
Write F(z)=∏_{r=1}^q(1+z/λ_r), λ_r>0 distinct. The distribution
is the sum of q independent Bernoulli variables with distinct success probabilities p_r=1/(1+λ_r). With u=E I and v=Var I, Cauchy–Schwarz gives
At q=1 the displayed strict inequality becomes equality. Also, the Riccati identity at z=1 gives
Case n≥m
Set q=m and d=n-m≥0. Under a uniform supported permutation of V_{m,n}, let I count its lower-right entries. Its distribution is the coefficient distribution of F_{m,d}. Consequently the barycenter B has entries
For m≥2, (11) gives
where the last inequality uses u≤m and n=m+d. Using (12),
At the barycenter t=u/m, the z(t) of Section 2 equals the left side of (13) divided by its right side, so z(t)>1. The function μ(z) is strictly increasing on z>0 because zμ'(z) is the variance of the tilted coefficient distribution. Thus μ(z(t))>μ(1)=u=mt. Equation (6) shows that f is strictly increasing at the barycenter. Decreasing t slightly produces a matrix in the same face with smaller permanent, so B is not a minimizer. The calculation also covers d=0, since t>0 and all logarithms used here are finite.
For m=1 and n>1, the variance inequality is equality but the subsequent comparison is strict because d>0 and u<m. The same conclusion follows, consistently with Brualdi's prior result.
Case m≥n
Set q=n and d=m-n≥0. Now let I count the chosen upper diagonal entries of a uniform supported permutation. Its count distribution is the coefficient distribution of F_{n,d}. The barycenter has
For the one-parameter doubly stochastic family with upper diagonal entry a,
the permanent is a positive constant times
Its logarithmic derivative is
Since n≥2, (11) and (12) imply
Hence z(u/n)>1 and the same increasing-derivative argument shows that the barycenter is not minimizing.
This proves non-barycentricity throughout m≥1, n>1. The excluded case n=1 has V_{m,1}=J_{m+1}, which is barycentric.
6. Scope and sources
This settles the named Pula–Song–Wanless parameter-family conjecture, subject to the limitations of the source audit. The face equalization and uniqueness arguments have been proved independently above; the proof uses the older repeated-support averaging theorem, Foregger's minimizer lemma, and the ordinary van der Waerden theorem. It does not resolve the unrestricted characterization problems on Minc's list. No fixed-order computation is used in the proof.
Primary sources:
- Pula, Song and Wanless (2011), DOI, complete author preprint. Section 2, Theorem 2.1, formula (6), Corollary 2.5, Conjecture 2.1; Section 3, Theorem 3.1.
- Brualdi (1985), An interesting face of the polytope of doubly stochastic matrices, DOI. The m=1 case is explicitly credited to this source by Pula–Song–Wanless.
- Cheon and Song (2024), A conjecture on minimum permanents, DOI, complete primary PDF. This proves special cases including V_{4,5} and V_{4k,7k}, not the general threshold.
- Lavi, Problem 14 and Problem 15, checked 2026-11-20. Both full classification problems remain open. The latter records non-barycentricity for all m,n≥2 as existing progress.
- Song (2013), Minimum permanents on doubly stochastic matrices with prescribed zeros, Honam Math. J. 35, 211–223, DOI, public primary PDF. Full 13-page text inspected. Remarks 2.4 and 4.4 flag the diagonal-positivity issue. Theorems 4.5 and 4.6 settle V_{4,n} for n≥7 and n=6 respectively, not the general threshold.
- Minc (1984), Minimum permanents of doubly stochastic matrices with prescribed zero entries, DOI, Theorem 1 on averaging repeated-support rows and columns.
- Foregger (1980), On the minimum value of the permanent of a nearly decomposable doubly stochastic matrix, DOI, minimizer lemma as quoted in the 2011 and 2013 primary papers.
The separate audit file records searches for later resolutions and the distinction between the flawed published reduction and the replacement proof above.