OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

§1 (setting): exact and border determinant representations: Affine determinant representations and the permanent over the complex numbers

Exact and border models at fixed size.

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

Representing the permanent of an m×mm\times m matrix by an n×nn\times n affine determinant compares two independently specified sizes.

The Claim

Definition 1. For a variable set Σ\Sigma, the complex polynomial ring 𝒫Σ\mathcal P_\Sigma is (1). 𝒫Σ:=ℂ[xv∣v∈Σ].\mathcal P_\Sigma := \mathbb C[x_v\mid v\in\Sigma].(1)✦

For a nonnegative integer mm, put Im={i∈ℤ:0≤i<m}I_m=\{i\in\mathbb Z:0\leq i<m\}. The matrix entry index set 𝒱m\mathcal V_m is the Cartesian product in (2). 𝒱m:=Im×Im.\mathcal V_m := I_m\times I_m.(2)✦ With 𝔖(Im)\mathfrak S(I_m) denoting the permutations of ImI_m, the permanent per⁡m∈𝒫𝒱m\operatorname{per}_m\in\mathcal P_{\mathcal V_m} is the polynomial in (3). per⁡m:=∑τ∈𝔖(Im)∏i∈Imxi,τ(i).\operatorname{per}_m := \sum_{\tau\in\mathfrak S(I_m)}\prod_{i\in I_m}x_{i,\tau(i)}.(3)✦

Let Σ\Sigma be finite and nn a nonnegative integer. For complex matrices A0,Av∈Mn(ℂ)A_0,A_v\in M_n(\mathbb C), indexed by v∈Σv\in\Sigma, write A=(Av)v∈ΣA=(A_v)_{v\in\Sigma}. The affine determinant Δn(A0,A)∈𝒫Σ\Delta_n(A_0,A)\in\mathcal P_\Sigma of complex matrices A0,Av∈Mn(ℂ)A_0,A_v\in M_n(\mathbb C) indexed by v∈Σv\in\Sigma is the polynomial in (4). Δn(A0,A):=det⁡(A0+∑v∈ΣxvAv).\Delta_n(A_0,A) := \det\!\left(A_0+\sum_{v\in\Sigma}x_vA_v\right).(4)✦

An exact determinant representation of p∈𝒫Σp\in\mathcal P_\Sigma of positive size nn is a choice of matrices A0,Av∈Mn(ℂ)A_0,A_v\in M_n(\mathbb C) satisfying (5); write HasExactDeterminant⁡(n,p)\operatorname{HasExactDeterminant}(n,p) when such a choice exists. Δn(A0,A)=p.\Delta_n(A_0,A)=p.(5)✦

For α∈ℕΣ\alpha\in\mathbb N^\Sigma and q∈𝒫Σq\in\mathcal P_\Sigma, let [xα]q[x^\alpha]q denote the coefficient of xα=∏v∈Σxvαvx^\alpha=\prod_{v\in\Sigma}x_v^{\alpha_v} in qq. A border determinant representation of p∈𝒫Σp\in\mathcal P_\Sigma of positive size nn is a sequence of complex matrices A0(r),Av(r)∈Mn(ℂ)A_0^{(r)},A_v^{(r)}\in M_n(\mathbb C), for r∈ℕr\in\mathbb N and v∈Σv\in\Sigma, satisfying (6), with A(r)=(Av(r))v∈ΣA^{(r)}=(A_v^{(r)})_{v\in\Sigma}; write HasBorderDeterminant⁡(n,p)\operatorname{HasBorderDeterminant}(n,p) when such a sequence exists. limr→∞[xα]Δn(A0(r),A(r))=[xα]p(α∈ℕΣ).\lim_{r\to\infty}[x^\alpha]\Delta_n(A_0^{(r)},A^{(r)}) =[x^\alpha]p \qquad(\alpha\in\mathbb N^\Sigma).(6)✦

Theorem 1. Let Σ\Sigma be finite and p∈𝒫Σp\in\mathcal P_\Sigma have an exact determinant representation of positive size nn. Then (7) holds. HasBorderDeterminant⁡(n,p).\operatorname{HasBorderDeterminant}(n,p).(7)✦

In the paper, dc⁡(f)\operatorname{dc}(f) for a complex polynomial ff is the least positive nn such that f=det⁡(A0+∑v∈ΣxvAv)f=\det(A_0+\sum_{v\in\Sigma}x_vA_v), its border counterpart bdc⁡(f)\operatorname{bdc}(f) is the least positive nn for which ff belongs to the coefficientwise closure of size-nn affine determinants with unrestricted matrix coefficients in the approximating sequence, and per⁡m=∑τ∈𝔖(Im)∏i∈Imxi,τ(i)\operatorname{per}_m=\sum_{\tau\in\mathfrak S(I_m)}\prod_{i\in I_m}x_{i,\tau(i)}.

What Is Checked

The representations and (7) are stated for polynomials in finitely many variables over ℂ\mathbb C, with arbitrary complex coefficient matrices of the prescribed size.