Malek negative-transform constants review

What Lean checks

Complete written all-degree negative-transform proof with all equality cases, two independent internal reviews and exact scalar identity checks. The permanent endpoint is prior work; the named subsidiary is documented in the Minc site's linked survey. No proof-assistant work is claimed.

Research date: 2026-11-20 (America/Chicago).

This independently checks the proposed strengthened subpermanent lower bound and the constants needed to compare it with the negative transform. The proof in this note covers n≥5n\geq5 and 2≤k<n2\leq k<n. The permanent case k=nk=n, the smaller orders, and the historical scope of Malek's conjecture must be supplied separately when stating the full result. No matrix search or finite-order extension is used.

The two source inputs inspected were Yair Lavi's Kopotun paper, especially Sections 3, 5, and 6, and his Marcus–Minc paper, especially Sections 3–5. The former supplies the stable-polynomial slice framework, root-motion estimate, and centered subpermanent bound. The latter supplies the rational upper bound on the full permanent comparison constant. The stronger capacity estimate below is the campaign's proposed improvement; it is not attributed to those papers.

Notation

Let AA be doubly stochastic of order nn, let J=𝟏𝟏𝖳/nJ=\mathbf1\mathbf1^{\mathsf T}/n, and set

X=A−J,Q=I−J,r2=∥X∥F2,Sn,k=(nk)2k!nk,qk(D)=σk(D)Sn,k,αn,k=k(k−1)n(n−1).X=A-J,\quad Q=I-J,\quad r^2=\|X\|_F^2, \quad S_{n,k}=\binom nk^2\frac{k!}{n^k}, \quad q_k(D)=\frac{\sigma_k(D)}{S_{n,k}}, \quad \alpha_{n,k}=\frac{k(k-1)}{n(n-1)}.

The transform is T(A)=(nJ−A)/(n−1)=J−X/(n−1)T(A)=(nJ-A)/(n-1)=J-X/(n-1). It is doubly stochastic because every entry of AA lies in [0,1][0,1].

1. The improved capacity cost

Assume first that AA is positive, put m=n−k≥1m=n-k\geq1, and use the degree-nn stable polynomial

P(z)=Ek(Az)E1(z)m,Ej(z)=ej(z)(nj).P(z)=E_k(Az)E_1(z)^m, \qquad E_j(z)=\frac{e_j(z)}{\binom nj}.

For positive zz, double stochasticity implies Az≺zAz\prec z. The elementary symmetric polynomial is Schur-concave, so Ek(Az)≥Ek(z)E_k(Az)\geq E_k(z). The normalized Newton inequalities make Ej+1/EjE_{j+1}/E_j nonincreasing in jj; hence

En−1(z)≤Ek(z)E1(z)m−1.E_{n-1}(z)\leq E_k(z)E_1(z)^{m-1}.

The direction of this inequality matters. It yields

P(z)∏izi≥E1(z)En−1(z)En(z)=(1n∑izi)(1n∑izi−1).\frac{P(z)}{\prod_i z_i} \geq \frac{E_1(z)E_{n-1}(z)}{E_n(z)} =\left(\frac1n\sum_i z_i\right) \left(\frac1n\sum_i z_i^{-1}\right). \tag{1}

Fix a slice coordinate jj. For the other coordinates xh>0x_h>0, let R=log(maxxh/minxh)R=\log(\max x_h/\min x_h). At the optimizing slice coordinate zj=t*z_j=t_*, set F=log(P(z)/∏zi)F=\log(P(z)/\prod z_i). Choose two of the other coordinates with ratio eRe^R, and scale all coordinates so that these two are e−R/2,eR/2e^{-R/2},e^{R/2}. If the remaining coordinates have sums uu and reciprocal sum vv, then uv≥(n−2)2uv\geq(n-2)^2 and u+v≥2(n−2)u+v\geq2(n-2). Therefore (1) gives

F≥2log(1+2n(cosh(R/2)−1)).F\geq2\log\left(1+\frac{2}{n}\bigl(\cosh(R/2)-1\bigr)\right). \tag{2}

This also covers R=0R=0. The argument uses two distinct other coordinates, available because n≥5n\geq5.

2. The pointwise lower bound

Use the slice probabilities pi=t*/(t*+λi)p_i=t_*/(t_*+\lambda_i), their values pi0p_i^0 when all other coordinates equal one, and

d=∑ipi2−1n,d0=∑i(pi0)2−1n=αn,k∥X:j∥22.d=\sum_i p_i^2-\frac1n,\qquad d_0=\sum_i(p_i^0)^2-\frac1n =\alpha_{n,k}\|X_{:j}\|_2^2.

The inspected root-motion estimate gives

d0≤d+pmaxsinh(R/2),pmax≤1n+n−1nd.\sqrt{d_0}\leq\sqrt d+\sqrt{p_{\max}}\sinh(R/2), \qquad p_{\max}\leq\frac1n+\sqrt{\frac{n-1}{n}d}. \tag{3}

If d0=0d_0=0, then F+d/2≥0F+d/2\geq0 suffices. Otherwise suppose, for contradiction, that

F+d2≤5d04n.F+\frac d2\leq\frac{5d_0}{4n}.

Write s=d/d0s=\sqrt{d/d_0} and w=5/4−ns2/2w=5/4-ns^2/2. Then

0≤s≤52n<1,0≤w≤54,F≤d0wn≤14.0\leq s\leq\sqrt{\frac{5}{2n}}<1, \quad 0\leq w\leq\frac54, \quad F\leq\frac{d_0w}{n}\leq\frac14.

For 0≤F≤1/40\leq F\leq1/4, the factorial bound ℓ!≥2ℓ−1\ell!\geq2^{\ell-1} gives

eF/2−1≤F/21−F/4≤8F15.e^{F/2}-1\leq\frac{F/2}{1-F/4}\leq\frac{8F}{15}.

Equation (2) consequently implies

cosh(R/2)−1≤415d0w,sinh2(R/2)≤2845d0w.\cosh(R/2)-1\leq\frac4{15}d_0w, \qquad \sinh^2(R/2)\leq\frac{28}{45}d_0w. \tag{4}

For the second estimate use d0w≤5/4d_0w\leq5/4 in sinh2u=2(coshu−1)+(coshu−1)2\sinh^2 u=2(\cosh u-1)+(\cosh u-1)^2. Also d0≤(n−1)/nd_0\leq(n-1)/n, so (3) gives npmax≤1+(n−1)snp_{\max}\leq1+(n-1)s. Substitution into (3) now forces

1≤s+2845(1+(n−1)s)(54n−s22).1\leq s+\sqrt{\frac{28}{45} (1+(n-1)s)\left(\frac{5}{4n}-\frac{s^2}{2}\right)}. \tag{5}

For fixed 0≤s<10\leq s<1, the product under the radical before the factor 28/4528/45 decreases with nn: it equals

54s+5(1−s)4n−s2(1−s)2−ns32.\frac54s+\frac{5(1-s)}{4n} -\frac{s^2(1-s)}2-\frac{ns^3}2.

Replacing nn by 5 in (5) is therefore an upper bound. But

45[(1−s)2−2845(1+4s)(14−s22)]=56s3+59s2−118s+38>045\left[(1-s)^2- \frac{28}{45}(1+4s)\left(\frac14-\frac{s^2}{2}\right)\right] =56s^3+59s^2-118s+38>0

for every s≥0s\geq0. An exact certificate is

56s3+59s2−118s+38=59s2−178627s+13702729+56(s−59)2(s+109).56s^3+59s^2-118s+38 =59s^2-\frac{1786}{27}s+\frac{13702}{729} +56\left(s-\frac59\right)^2\left(s+\frac{10}{9}\right).

The quadratic has positive leading coefficient and discriminant −43876/729-43876/729; the last term is nonnegative on s≥0s\geq0. Since s<1s<1, this contradicts (5). Thus the proposed pointwise estimate is valid:

F+d2≥5d04n.F+\frac d2\geq\frac{5d_0}{4n}. \tag{6}

The stable coefficient argument in the inspected Kopotun paper converts (6) into

qk(A)≥exp(5αn,k4n2∥A−J∥F2).q_k(A)\geq \exp\left(\frac{5\alpha_{n,k}}{4n^2}\|A-J\|_F^2\right). \tag{7}

Indeed, take the infimum over the positive slice coordinates, then choose jj with d0≥αn,kr2/nd_0\geq\alpha_{n,k}r^2/n. For an arbitrary doubly stochastic matrix, apply the positive-matrix argument to Aε=(1−ε)A+εJA_\varepsilon=(1-\varepsilon)A+\varepsilon J and let ε↓0\varepsilon\downarrow0. Every quantity in (7) is continuous. This handles all support boundaries.

3. The upper constant increases with kk

For falling factorials (a)j(a)_j, expansion by the entries selected from XX gives

qk(J+tX)=∑j=0k(k)jnj(n)j2tjσj(X).q_k(J+tX)=\sum_{j=0}^k \frac{(k)_j n^j}{(n)_j^2}\,t^j\sigma_j(X). \tag{8}

The centered estimate applies to X=A−JX=A-J: it has zero margins and operator norm at most one. It gives

|σj(X)|≤r2n−1σj(Q),σj(Q)≥0.|\sigma_j(X)|\leq\frac{r^2}{n-1}\sigma_j(Q), \qquad \sigma_j(Q)\geq0.

Use (8), including absolute values for odd jj, and put t=1/(n−1)t=1/(n-1). This gives

qk(T(A))≤1+bn,kαn,kr2,bn,k=qk(J+tQ)−1(n−1)αn,k.q_k(T(A))\leq1+b_{n,k}\alpha_{n,k}r^2, \qquad b_{n,k}=\frac{q_k(J+tQ)-1}{(n-1)\alpha_{n,k}}. \tag{9}

After division by αn,k=(k)2/(n)2\alpha_{n,k}=(k)_2/(n)_2, the jj-th coefficient in qk(J+tQ)−1q_k(J+tQ)-1 is a nonnegative constant independent of kk times (k−2)j−2(k-2)_{j-2}. Increasing kk increases every existing term and introduces only nonnegative terms. Therefore

bn,k≤bn,n−1≤bn,n=βn.b_{n,k}\leq b_{n,n-1}\leq b_{n,n}=\beta_n. \tag{10}

This is the same coefficient monotonicity mechanism as the source's positive-transform upper bound, applied at a different positive value of tt.

The exact diagonal-plus-uniform evaluation is

qk(J+tQ)=∑j=0k(k)j(n)j(nt)j(1−t)k−jj!.q_k(J+tQ)=\sum_{j=0}^k \frac{(k)_j}{(n)_j}\frac{(nt)^j(1-t)^{k-j}}{j!}. \tag{11}

It follows by expanding J+tQ=tI+(1−t)JJ+tQ=tI+(1-t)J; no sign condition on a centered coefficient is substituted for this calculation.

4. Exact separation of the constants

The necessary small scalar calculations are:

nn Constant used Exact value Gap below 5/(4n2)5/(4n^2)
5 b5,4b_{5,4} 3685/737283685/73728 7/3686407/368640
6 b6,5b_{6,5} 4767/1562504767/156250 47401/1125000047401/11250000
7 β7\beta_7 4421129/2015539204421129/201553920 35307079/987614208035307079/9876142080

For n≥8n\geq8, the Marcus–Minc paper proves

βn<n(n−1)(2(n−2)2−n).\beta_n<\frac{n}{(n-1)(2(n-2)^2-n)}.

All denominators are positive. Comparison with 5/(4n2)5/(4n^2) reduces to

6n3−55n2+85n−40>0.6n^3-55n^2+85n-40>0.

Writing n=8+vn=8+v gives the exact positive expression

6v3+89v2+357v+192>0(v≥0).6v^3+89v^2+357v+192>0\qquad(v\geq0).

Thus bn,k<5/(4n2)b_{n,k}<5/(4n^2) for every n≥5n\geq5 and 2≤k<n2\leq k<n. Combining (7) and (9) proves the proposed strict comparison when A≠JA\ne J, and equality at JJ. The upper comparison must retain k<nk<n for the small constants: β5\beta_5 and β6\beta_6 themselves exceed 5/(4n2)5/(4n^2). This does not affect the argument, since (10) permits the sharper bn,n−1b_{n,n-1} at those two orders and the permanent case has a separate theorem.

Verification scope

The accompanying script verifies the scalar evaluations, two independent expansions for them, the cubic decomposition and its discriminant, and the shifted positive polynomial. It does not test a finite collection of matrices or substitute computation for the quantified inequalities. This review found no gap in the stated n≥5,k<nn\geq5,\ k<n argument.

Comparison with the complete draft

The complete draft at proof.md was then read independently. Its displayed scalar values, normalizations, the factor 5/(4n2)5/(4n^2), the cubic certificate, and the final strictness argument agree with this check.

Two details in the expanded draft deserve an explicit check. First, the ordered root bounds uλi0≤λi≤vλi0u\lambda_i^0\leq\lambda_i\leq v\lambda_i^0 imply u≤t*≤vu\leq t_*\leq v by the increasing slice equation. Setting ai=λi/(t*λi0)a_i=\lambda_i/(t_*\lambda_i^0), the likelihood ratio is

pi0pi=1+aiλi01+λi0.\frac{p_i^0}{p_i} =\frac{1+a_i\lambda_i^0}{1+\lambda_i^0}.

It lies between 11 and aia_i, hence between u/t*u/t_* and v/t*v/t_*. This directly gives the needed ratio bound v/uv/u. Sorting the two component root lists does not invalidate their coordinatewise bounds.

Second, the remaining small proper degree is (n,k)=(4,3)(n,k)=(4,3). The zero-margin identities

σ2(X)=12∑xij2,σ3(X)=23∑xij3\sigma_2(X)=\frac12\sum x_{ij}^2,\qquad \sigma_3(X)=\frac23\sum x_{ij}^3

and xij≥−1/nx_{ij}\geq-1/n imply σ3(X)≥−4σ2(X)/(3n)\sigma_3(X)\geq-4\sigma_2(X)/(3n). At n=4n=4, the transform difference is

89σ2(X)+2827σ3(X)≥4481σ2(X).\frac89\sigma_2(X)+\frac{28}{27}\sigma_3(X) \geq\frac{44}{81}\sigma_2(X).

The draft's constant and equality conclusion are correct. Degree two is strict away from JJ for n≥3n\geq3, and degrees zero and one are constant. The full degree and its exceptional order-three equality cases are imported from the cited Marcus–Minc theorem rather than claimed as new work.

This completes the mathematical audit of the written argument. The historical attribution and the search for prior all-degree resolutions remain the root agent's separate source audit.