OctoInformBeta

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

Lemma 3.2: For positive ff with the slot signature property and distinct disjoint pairs avoiding AA, defect totals satisfy 4cprcrp≤z24c_{pr}c_{rp} \le z^2 and cprcrt≤zcptc_{pr}c_{rt} \le z\,c_{pt}

Quadratic inequalities between slot totals and defect totals.

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

Approximate counting of the common bases of two matroids M1M_1 and M2M_2 runs through a multiaffine polynomial with positive coefficients whose variables come in disjoint pairs. Lemma 3.2 is a pair of quadratic inequalities between two kinds of sums of its coefficients, slot totals and defect totals.

The library states the lemma for an arbitrary positive function ff on the subsets of a finite set Γ\Gamma and a list of disjoint pairs of Γ\Gamma; the matroids enter only through the hypothesis that ff has the slot signature property. It also states two inequalities for symmetric bilinear forms with one positive direction, the first a reverse Cauchy-Schwarz inequality.

Slot Totals and Defect Totals

A multiaffine polynomial on a finite set Γ\Gamma is a polynomial in variables xix_i, i∈Γi \in \Gamma, of degree at most one in each variable, f(x)=∑S⊆Γf(S)∏i∈Sxi,f(x) = \sum_{S \subseteq \Gamma} f(S) \prod_{i \in S} x_i,(1) given by its coefficient function S↦f(S)S \mapsto f(S) on the subsets of Γ\Gamma. The directional derivative of ff along a real vector a=(ai)i∈Γa = (a_i)_{i \in \Gamma} is Daf=∑i∈Γai∂f/∂xiD_a f = \sum_{i \in \Gamma} a_i\, \partial f / \partial x_i, and the iterated derivative of ff along a list of vectors a1,…,ama_1, \dots, a_m is Da1Da2⋯DamfD_{a_1} D_{a_2} \cdots D_{a_m} f.✦

The indicator vector 𝟏E\mathbf{1}_E of a finite set E⊆ΓE \subseteq \Gamma has entry 11 at the elements of EE and 00 elsewhere.✦ A pair is an ordered pair p=(p1,p2)p = (p_1, p_2) of elements of Γ\Gamma; its direction is 𝟏p=𝟏{p1,p2}\mathbf{1}_p = \mathbf{1}_{\{p_1, p_2\}}, and A∪pA \cup p stands for A∪{p1,p2}A \cup \{p_1, p_2\}.✦ A list PP of pairs is fresh for a set A⊆ΓA \subseteq \Gamma when the entries of its pairs are pairwise distinct and none of them lies in AA.✦

The slot total zPz_P of ff along a list PP of pairs is the iterated derivative of ff along the directions of the pairs of PP: zP=(∏p∈PD𝟏p)f.z_P = \Big( \prod_{p \in P} D_{\mathbf{1}_p} \Big) f.(2)✦ When PP is fresh for AA, the coefficient of zPz_P at AA is zP(A)=∑Tf(A∪T),z_P(A) = \sum_{T} f(A \cup T),(3) the sum running over the sets TT made of one entry of each pair of PP.

For two pairs pp and rr, the defect total cprc_{pr} of ff along PP at AA is the slot total along the list PP with pp and rr removed, at the set A∪rA \cup r: cpr=zP\{p,r}(A∪r).c_{pr} = z_{P \setminus \{p, r\}}(A \cup r).(4)✦ When PP is fresh for AA and p≠rp \ne r lie in PP, it is the sum of ff over the sets that add to AA both entries of rr, no entry of pp and one entry of each other pair of PP.

One Positive Direction

A bilinear form BB on a real vector space VV has one positive direction if, whenever e∈Ve \in V has B(e,e)>0B(e,e) > 0, every v∈Vv \in V with B(v,e)=0B(v,e) = 0 has B(v,v)≤0B(v,v) \le 0.✦ For a symmetric form this is the condition of at most one positive eigenvalue.

The face Hessian of a multiaffine polynomial ff at a set A⊆ΓA \subseteq \Gamma is the symmetric matrix Hf(A)H_f(A) indexed by Γ\A\Gamma \setminus A, with zero diagonal and Hf(A)ij=f(A∪{i,j})(i≠j);H_f(A)_{ij} = f(A \cup \{i, j\}) \qquad (i \ne j);(5)✦ it is the Hessian at the origin of the derivative of ff in the variables of AA, restricted to the other variables.

A multiaffine polynomial ff on Γ\Gamma has the slot signature property if, for every list PP of pairs of elements of Γ\Gamma and every set A⊆ΓA \subseteq \Gamma, the bilinear form (u,v)↦u⊤HzP(A)v(u, v) \mapsto u^{\top} H_{z_P}(A)\, v of the face Hessian of the slot total zPz_P at AA has one positive direction.✦

The Claim

Theorem 1. Let ff be a multiaffine polynomial on Γ\Gamma with positive coefficients and the slot signature property, let A⊆ΓA \subseteq \Gamma, and let PP be a list of pairs fresh for AA, with slot total z=zP(A)z = z_P(A) and defect totals cprc_{pr} along PP at AA. For distinct pairs pp and rr of PP, 4cprcrp≤z2,4\, c_{pr}\, c_{rp} \le z^2,(6)✦ and for pairwise distinct pairs pp, rr, tt of PP, cprcrt≤zcpt.c_{pr}\, c_{rt} \le z\, c_{pt}.(7)✦ In terms of slot totals alone, for pairs pp, rr, tt and a list QQ of pairs, with (p,r,Q)(p, r, Q) the list that starts with pp and rr and goes on with QQ: if (p,r,Q)(p, r, Q) is fresh for AA, then 4zQ(A∪p)zQ(A∪r)≤z(p,r,Q)(A)2,4\, z_Q(A \cup p)\, z_Q(A \cup r) \le z_{(p, r, Q)}(A)^2,(8)✦ and if (p,r,t,Q)(p, r, t, Q) is fresh for AA, then z(t,Q)(A∪r)z(p,Q)(A∪t)≤z(p,r,t,Q)(A)z(r,Q)(A∪t).z_{(t, Q)}(A \cup r)\, z_{(p, Q)}(A \cup t) \le z_{(p, r, t, Q)}(A)\, z_{(r, Q)}(A \cup t).(9)✦ Let BB be a symmetric bilinear form on a real vector space VV with one positive direction. For u,v∈Vu, v \in V with B(u,u)>0B(u,u) > 0, B(u,u)B(v,v)≤B(u,v)2,B(u,u)\, B(v,v) \le B(u,v)^2,(10)✦ and for u,e,v∈Vu, e, v \in V with B(e,e)>0B(e,e) > 0, B(u,e)>0B(u,e) > 0, B(v,e)>0B(v,e) > 0, B(u,u)≥0B(u,u) \ge 0 and B(v,v)≥0B(v,v) \ge 0, B(u,v)B(e,e)≤2B(u,e)B(v,e).B(u,v)\, B(e,e) \le 2\, B(u,e)\, B(v,e).(11)✦

In the paper, the result reads: for a partial transversal assignment σ\sigma and distinct unassigned indices ii, jj, kk, 4cijσcjiσ≤zσ24c^\sigma_{ij}c^\sigma_{ji} \le z_\sigma^2 and cijσcjkσ≤zσcikσc^\sigma_{ij}c^\sigma_{jk} \le z_\sigma c^\sigma_{ik}, where zσz_\sigma is the slot total zz and cijσc^\sigma_{ij} the defect total cprc_{pr} of the iith pair pp and the jjth pair rr.

What Is Checked

The claim is stated over a multiaffine polynomial ff on a finite set Γ\Gamma with positive coefficients and the slot signature property, a set A⊆ΓA \subseteq \Gamma, a list of pairs fresh for AA with its slot totals and defect totals, and, in (10) and (11), a symmetric bilinear form with one positive direction on a real vector space.