OctoInformBeta

OpenAI preprint, September 2026 · §3. Quadratic signature inequalities

Theorem 3.1: Every face Hessian of q−r(A)q^{-r(A)} has one positive direction, also after derivatives in nonnegative directions and, after slot derivatives, under linear substitutions

Matroid rank weights with 0<q≤10<q\le 1 have the slot signature property.

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

The problem is to count approximately the common bases of two matroids M1M_1 and M2M_2 on nn elements, both given by one independence oracle. Most of the analysis works over a finite set Γ\Gamma with a list of nn disjoint pairs {xi,yi}\{x_i, y_i\} of its elements and a positive weight ff on the subsets of Γ\Gamma, and the matroids enter only through one spectral hypothesis on ff, the slot signature property.

The weight in question here is the rank weight A↦q−r(A)A \mapsto q^{-r(A)} of a matroid on Γ\Gamma with rank function rr, for 0<q≤10 < q \le 1, and the question is whether it meets that hypothesis.

Derivatives and Face Hessians

A real function ff on the subsets of Γ\Gamma stands for the multiaffine polynomial in the variables zaz_a, a∈Γa \in \Gamma, ∑A⊆Γf(A)∏a∈Aza.\sum_{A \subseteq \Gamma} f(A) \prod_{a \in A} z_a .(1)

The derivative of ff along a vector a∈ℝΓa \in \mathbb{R}^\Gamma is the real function ∂af\partial_a f on the subsets of Γ\Gamma given by (∂af)(A)=∑i∈Γ\Aaif(A∪{i}),(\partial_a f)(A) = \sum_{i \in \Gamma \setminus A} a_i \, f(A \cup \{i\}) ,(2)✦ the coefficient function of the derivative of (1) in the direction aa. The derivative along a list a1,…,aka_1, \dots, a_k of vectors is ∂a1∂a2⋯∂akf\partial_{a_1} \partial_{a_2} \cdots \partial_{a_k} f, which is ff for the empty list.✦

The slot direction of a set E⊆ΓE \subseteq \Gamma is its indicator vector 𝟏E∈ℝΓ\mathbf{1}_E \in \mathbb{R}^\Gamma, with entries 11 on EE and 00 elsewhere.✦ The pair direction of a pair p=(x,y)p = (x, y) of elements of Γ\Gamma is 𝟏p=𝟏{x,y}\mathbf{1}_p = \mathbf{1}_{\{x, y\}}.✦ The slot total of ff along a list P=(p1,…,pn)P = (p_1, \dots, p_n) of pairs of elements of Γ\Gamma is the real function ∂Pf=∂𝟏p1⋯∂𝟏pnf\partial_P f = \partial_{\mathbf{1}_{p_1}} \cdots \partial_{\mathbf{1}_{p_n}} f(3)✦ on the subsets of Γ\Gamma. When the pairs are disjoint and avoid a set AA, the value (∂Pf)(A)(\partial_P f)(A) is the sum of ff over the sets obtained from AA by adding one element of each pair.

The face Hessian of ff at a set A⊆ΓA \subseteq \Gamma is the real symmetric matrix HA(f)H_A(f) indexed by Γ\A\Gamma \setminus A with zero diagonal and off-diagonal entries HA(f)ij=f(A∪{i,j})(i≠j),H_A(f)_{ij} = f(A \cup \{i, j\}) \qquad (i \neq j) ,(4)✦ the Hessian at the origin of the derivative of (1) in the variables of AA, restricted to the remaining variables.

A bilinear form BB on a real vector space VV has one positive direction when, for all e,v∈Ve, v \in V, B(e,e)>0andB(v,e)=0⇒B(v,v)≤0.B(e, e) > 0 \ \text{and} \ B(v, e) = 0 \quad \Longrightarrow \quad B(v, v) \le 0 .(5)✦ For a symmetric form this says that BB has at most one positive eigenvalue. A real square matrix HH has one positive direction when the form (u,v)↦u𝖳Hv(u, v) \mapsto u^{\mathsf{T}} H v does.

A real function ff on the subsets of Γ\Gamma is fully positive of order m∈ℕm \in \mathbb{N} when f(A)>0 if |A|+m≤|Γ|,f(A)=0 if |A|+m>|Γ|.f(A) > 0 \ \text{ if } \ |A| + m \le |\Gamma| , \qquad f(A) = 0 \ \text{ if } \ |A| + m > |\Gamma| .(6)✦

The slot signature property of a real function ff on the subsets of Γ\Gamma is the condition that the face Hessian HA(∂Pf)H_A(\partial_P f) has one positive direction for every list PP of pairs of elements of Γ\Gamma and every set A⊆ΓA \subseteq \Gamma.✦

The Rank Weight

Let MM be a matroid with ground set Γ\Gamma and rank function rr, and let qq be a real number. The rank weight of MM at qq is the real function wqw_q on the subsets of Γ\Gamma given by wq(A)=q−r(A).w_q(A) = q^{-r(A)} .(7)✦ The pair matrix of MM at qq is the real symmetric matrix RqR_q indexed by Γ\Gamma with zero diagonal and off-diagonal entries (Rq)ij=q−r({i,j})(i≠j).(R_q)_{ij} = q^{-r(\{i, j\})} \qquad (i \neq j) .(8)✦

The Claim

Theorem 1. (a) Let MM be a matroid with ground set Γ\Gamma and rank function rr, let 0<q≤10 < q \le 1, and let wqw_q and RqR_q be the rank weight and the pair matrix of MM at qq. Then each of the following matrices has one positive direction: the pair matrix Rq;R_q ;(9)✦ for every set A⊆ΓA \subseteq \Gamma, the face Hessian HA(wq);H_A(w_q) ;(10)✦ for every list a1,…,aka_1, \dots, a_k of vectors in ℝΓ\mathbb{R}^\Gamma with nonnegative entries and every set A⊆ΓA \subseteq \Gamma, the face Hessian HA(∂a1⋯∂akwq);H_A(\partial_{a_1} \cdots \partial_{a_k} w_q) ;(11)✦ for every list E1,…,EkE_1, \dots, E_k of subsets of Γ\Gamma, every set A⊆ΓA \subseteq \Gamma, every finite set KK and every real matrix LL with rows indexed by Γ\A\Gamma \setminus A and columns indexed by KK, the matrix L𝖳HA(∂𝟏E1⋯∂𝟏Ekwq)L.L^{\mathsf{T}} \, H_A(\partial_{\mathbf{1}_{E_1}} \cdots \partial_{\mathbf{1}_{E_k}} w_q) \, L .(12)✦ The rank weight wqw_q(13)✦ has the slot signature property.

(b) Let ff be a real function on the subsets of Γ\Gamma that is fully positive of order mm and whose face Hessians HA(f)H_A(f), A⊆ΓA \subseteq \Gamma, all have one positive direction, and let a∈ℝΓa \in \mathbb{R}^\Gamma have positive entries. Then for every set A⊆ΓA \subseteq \Gamma the face Hessian HA(∂af)H_A(\partial_a f)(14)✦ has one positive direction.

In the paper, the result reads: for a matroid MM on Γ\Gamma and 0<q≤10 < q \le 1, the polynomial Tq,M(z0,z)=∑A⊆Γq−r(A)z0|Γ|−|A|∏a∈AzaT_{q,M}(z_0, z) = \sum_{A \subseteq \Gamma} q^{-r(A)} z_0^{|\Gamma| - |A|} \prod_{a \in A} z_a is Lorentzian, Lorentzian polynomials are closed under partial derivatives and nonnegative linear substitutions, and quadratic ones have at most one positive eigenvalue, so Tq,MT_{q,M} has the quadratic signature property. Here wq(A)w_q(A) is the coefficient of z0|Γ|−|A|∏a∈Azaz_0^{|\Gamma| - |A|} \prod_{a \in A} z_a in Tq,MT_{q,M}.

What Is Checked

The claim is stated over a matroid MM with ground set Γ\Gamma and 0<q≤10 < q \le 1, its rank weight (7) and pair matrix (8), a real function ff on the subsets of Γ\Gamma fully positive of order mm (6), derivatives (2) along vectors and along slot directions, slot totals (3), face Hessians (4), one positive direction (5) and the slot signature property.