OctoInformBeta

OpenAI preprint, September 2026 · §3. Selecting a coefficient by a permanent projection

Corollary 3.2: Weighted diagonal perturbations and their affine restrictions

A border size bound for permanent coefficients.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A weighted diagonal perturbation of a matrix introduces two auxiliary variables into its permanent. Selecting their common exponent gives a polynomial in the matrix entries. Its border determinant size is compared with that of a larger permanent.

For a finite variable set σ\sigma, write ℂ[𝒙σ]\mathbb C[\mathbf x_\sigma] for the complex polynomial ring on variables xvx_v, v∈σv\in\sigma.✦ Put Ir={0,…,r−1}I_r=\{0,\ldots,r-1\}, so the variables of an r×rr\times r matrix are indexed by Ir×IrI_r\times I_r, with rows and columns numbered from zero.✦ For the matrix of indeterminates X=(xij)i,j∈ImX=(x_{ij})_{i,j\in I_m}, the permanent polynomial perm⁡m∈ℂ[(xij)i,j∈Im]\operatorname{perm}_m\in\mathbb C[(x_{ij})_{i,j\in I_m}] is the sum in (1), where SmS_m is the symmetric group on ImI_m. perm⁡m(X)=∑π∈Sm∏i∈Imxi,π(i).\operatorname{perm}_m(X) =\sum_{\pi\in S_m}\prod_{i\in I_m}x_{i,\pi(i)}.(1)✦

Let RR be a commutative ring, II a finite set, M∈RI×IM\in R^{I\times I}, θ∈RI\theta\in R^I, and qq a nonnegative integer. The diagonal permanent coefficient δq(M,θ)∈R\delta_q(M,\theta)\in R is the coefficient at bidegree (q,q)(q,q), assigning exponent qq to each of the auxiliary indeterminates s,ts,t, defined in (2): δq(M,θ)=[sqtq]perm⁡(M+diag⁡(s+θit)i∈I).\delta_q(M,\theta) =[s^q t^q]\operatorname{perm} \bigl(M+\operatorname{diag}(s+\theta_i t)_{i\in I}\bigr).(2)✦ The expression inside the coefficient extraction belongs to R[s,t]R[s,t]. For a nonnegative integer kk and complex weights θ∈ℂIk\theta\in\mathbb C^{I_k}, set D=diag⁡(θi)i∈IkD=\operatorname{diag}(\theta_i)_{i\in I_k}. The weighted coefficient polynomial GD∈ℂ[(xij)i,j∈Ik]G_D\in\mathbb C[(x_{ij})_{i,j\in I_k}] is defined by (3), using the matrix of indeterminates and constant weights in (2): GD(X)=δq(X,θ).G_D(X)=\delta_q(X,\theta).(3)✦

For complex n×nn\times n matrices A0A_0 and AvA_v, v∈σv\in\sigma, with A=(Av)v∈σA=(A_v)_{v\in\sigma}, the polynomial FA0,A∈ℂ[𝒙σ]F_{A_0,A}\in\mathbb C[\mathbf x_\sigma] is the determinant of the affine pencil in (4): FA0,A(𝒙)=det⁡(A0+∑v∈σxvAv).F_{A_0,A}(\mathbf x) =\det\left(A_0+\sum_{v\in\sigma}x_vA_v\right).(4) A polynomial p∈ℂ[𝒙σ]p\in\mathbb C[\mathbf x_\sigma] has a border determinantal representation of size nn, written HasBorderDeterminant⁡(n,p)\operatorname{HasBorderDeterminant}(n,p), when n>0n>0 and there exist sequences of such matrices A0(j),Av(j)A_0^{(j)},A_v^{(j)}, with unrestricted complex entries, satisfying (5) for every exponent vector α∈ℕσ\alpha\in\mathbb N^\sigma: limj→∞[𝒙α]FA0(j),A(j)=[𝒙α]p.\lim_{j\to\infty}[\mathbf x^\alpha] F_{A_0^{(j)},A^{(j)}} =[\mathbf x^\alpha]p.(5)✦

For finite sets σ,τ\sigma,\tau, constants b∈ℂσb\in\mathbb C^\sigma, and coefficients B∈ℂσ×τB\in\mathbb C^{\sigma\times\tau}, the affine substitution ϕb,B:ℂ[𝒙σ]→ℂ[𝒚τ]\phi_{b,B}:\mathbb C[\mathbf x_\sigma]\to\mathbb C[\mathbf y_\tau] is the ℂ\mathbb C-algebra homomorphism determined by (6): ϕb,B(xv)=bv+∑w∈τBvwyw(v∈σ).\phi_{b,B}(x_v)=b_v+\sum_{w\in\tau}B_{vw}y_w \qquad(v\in\sigma).(6)✦

The Claim

Theorem 1. Let k,q,m,nk,q,m,n be nonnegative integers and θ∈ℂIk\theta\in\mathbb C^{I_k}. Suppose q≤kq\le k, 11k−2q≤m11k-2q\le m, and HasBorderDeterminant⁡(n,perm⁡m)\operatorname{HasBorderDeterminant}(n,\operatorname{perm}_m). Then the coefficient polynomial in (3) satisfies HasBorderDeterminant⁡(n,GD).\operatorname{HasBorderDeterminant}(n,G_D).(7)✦ For finite variable sets σ,τ\sigma,\tau, let p∈ℂ[𝒙σ]p\in\mathbb C[\mathbf x_\sigma] satisfy HasBorderDeterminant⁡(n,p)\operatorname{HasBorderDeterminant}(n,p), and let ϕb,B\phi_{b,B} be any affine substitution as in (6). Then HasBorderDeterminant⁡(n,ϕb,B(p)).\operatorname{HasBorderDeterminant}\bigl(n,\phi_{b,B}(p)\bigr).(8)✦

In the paper, with bdc\operatorname{bdc} denoting border determinantal complexity, the result reads: under Proposition 3.1’s hypotheses, for every integer d≥1d\ge1 and fixed affine map Λ:ℂd→Mat⁡k(ℂ)\Lambda:\mathbb C^d\to\operatorname{Mat}_k(\mathbb C), bdc⁡(GD∘Λ)≤bdc⁡(perm⁡m)\operatorname{bdc}(G_D\circ\Lambda)\le \operatorname{bdc}(\operatorname{perm}_m), in particular for every fixed linear restriction.

What Is Checked

The coefficient claim (7) is stated for the permanent and weighted diagonal coefficient polynomials over ℂ\mathbb C, with q≤kq\le k and 11k−2q≤m11k-2q\le m; the substitution claim (8) is stated for arbitrary finite variable sets and the sequential coefficient limits in (5).