Filtered Equivariant Membership and Static Algebraic Proof Degree

1 Static Algebraic Degree

Let \(k\) be a field and let

A finite ordered list

of nonzero polynomials will be called a presentation. It generates the ideal

The chosen generating set matters: two presentations of the same ideal can have different bounded-degree derivations.

Definition 1.1 (Static derivation degree).

For \(h\in R\), define

\[ \delta_{\mathbf F}(h) = \min \left\{ D: h=\sum_{i=1}^m g_i f_i,\quad g_i\in R,\quad \deg(g_i f_i)\le D\ \text{for all }i \right\}. \]

If no such representation exists, set \(\delta_{\mathbf F}(h)=\infty\). For \(h=0\), set \(\delta_{\mathbf F}(0)=0\).

When \(h=1\), this is the minimum static Hilbert--Nullstellensatz refutation degree of the presentation, provided \(1\in I_{\mathbf F}\). This is a degree invariant of static ideal-membership identities. It is not a size measure for dynamic Polynomial Calculus proofs or for algebraic circuits.

2 Homogenized Presentation Ideals

Let

For \(0\ne p\in R\), let \(p^h\in S\) denote its homogenization to total degree \(\deg p\):

Given a presentation \(\mathbf F=(f_1,\ldots,f_m)\), define

This is the ideal generated by the homogenizations of the chosen generators. It is generally smaller than the saturated homogenization of \(I_{\mathbf F}\), and this distinction is exactly what records the degree cost of the chosen presentation.

For a homogeneous ideal \(J\subset S\) and a homogeneous polynomial \(H\in S_r\), define

with value \(\infty\) if no such \(D\) exists. For \(H=1\), write

Theorem 2.1 (Homogenized membership formula).

For every nonzero \(h\in R\),

\[ \delta_{\mathbf F}(h) = \nu_{x_0}(J_{\mathbf F};h^h) = \min\{D\ge \deg h:x_0^{D-\deg h}h^h\in J_{\mathbf F}\}. \]

In particular, if \(1\in I_{\mathbf F}\), then

\[ \delta_{\mathbf F}(1)=\nu_{x_0}(J_{\mathbf F}) = \min\{D:x_0^D\in J_{\mathbf F}\}. \]

3 \texorpdfstring{\(x_0\)}{x0}-Torsion and Saturation Defect

Let \(J=J_{\mathbf F}\). Define

and the saturation-defect module

If \(h\in I_{\mathbf F}\), then \(h^h\in J_{\mathbf F}:x_0^\infty\), because any affine expression for \(h\) homogenizes after multiplying by a sufficiently high power of \(x_0\).

Proposition 3.1 (Torsion order).

For every nonzero \(h\in I_{\mathbf F}\),

\[ \delta_{\mathbf F}(h)-\deg h = \min\{e\ge0:x_0^e h^h\in J_{\mathbf F}\}. \]

Equivalently, \(\delta_{\mathbf F}(h)-\deg h\) is the \(x_0\)-torsion order of the class of \(h^h\) in \(T_{\mathbf F}\).

Thus static degree measures how long a homogeneous consequence survives in the \(x_0\)-torsion defect of the chosen homogenized presentation.

4 Degeneration Bounds

The preceding formulation gives simple monotonicity statements under homogeneous flat specialization.

Proposition 4.1 (Flat specialization).

Let \(A\) be an integral \(k\)-algebra and let

\[ \mathcal J\subset S\otimes_k A \]

be a homogeneous ideal such that \((S\otimes_k A)/\mathcal J\) is flat over \(A\). Let \(J_\eta\) be the generic fiber and \(J_s\) a specialization. Then

\[ \nu_{x_0}(J_\eta)\ge \nu_{x_0}(J_s). \]

Corollary 4.2 (Initial ideals).

For every homogeneous ideal \(J\subset S\) and every homogeneous initial ideal \(\operatorname{in}(J)\),

\[ \nu_{x_0}(J)\ge \nu_{x_0}(\operatorname{in}(J)). \]

Consequently,

\[ \delta_{\mathbf F}(1) \ge \min\{D:x_0^D\in \operatorname{in}(J_{\mathbf F})\}. \]

The affine chart has proof-theoretic meaning, so the homogenizing coordinate should be preserved. Let

If \(g\in P\), then \(g(x_0)=\lambda x_0\) for some \(\lambda\in k^\times\), and therefore

Combining this with the preceding corollary gives the family of lower bounds

5 Finite Domains and Filtered Membership

Let \(X\subset k^n\) be finite, with vanishing ideal \(I_X\subset R\), coordinate algebra

and degree filtration

Definition 5.1 (Degree-compatible domain presentation).

A finite presentation \(\Gamma=(\gamma_1,\ldots,\gamma_s)\) of \(I_X\) is degree-compatible if, for every \(D\ge0\) and every \(p\in I_X\cap R_{\le D}\), there are \(u_\ell\in R\) such that

\[ p=\sum_{\ell=1}^s u_\ell\gamma_\ell,\qquad \deg(u_\ell\gamma_\ell)\le D \]

for every \(\ell\).

Finite grids have degree-compatible presentations. If

and

then \(I_X=(u_1,\ldots,u_n)\), and the presentation is degree-compatible because these univariate polynomials in disjoint variables form a Groebner basis and division does not increase total degree.

Theorem 5.2 (Finite-domain filtered membership).

Let \(X\subset k^n\) be finite with degree-compatible presentation \(\Gamma\). Let \(f_1,\ldots,f_m\in R\), and assume

\[ 1\in (f_1,\ldots,f_m)+I_X. \]

For the combined presentation

\[ \mathbf P=(f_1,\ldots,f_m,\Gamma), \]

one has

\[ \delta_{\mathbf P}(1) = \min \left\{ D: 1\in \sum_{j=1}^m \bar f_j\,A_{X,\le D-\deg f_j} \right\}, \]

where \(\bar f_j\) is the image of \(f_j\) in \(A_X\), and \(A_{X,\le r}=0\) for \(r<0\).

6 Single-Equation Reciprocal Formula

Assume \(X\) has a degree-compatible presentation \(\Gamma\). Let \(f\in R\) have no zeros on \(X\). Then \(\bar f\in A_X\) is invertible. Define

Theorem 6.1 (Reciprocal degree).

For the presentation \(\mathbf P=(f,\Gamma)\),

\[ \delta_{\mathbf P}(1)=\deg f+\deg_X(\bar f^{-1}). \]

This is the central filtered-membership form: for one equation on a finite domain, the multiplier is forced to be the reciprocal function in the finite coordinate algebra, and the exact static degree is its filtered degree plus \(\deg f\).

7 Boolean Reciprocal Degree

Let

Every class in \(A_n\) has a unique multilinear representative

Its Boolean degree is

Corollary 7.1 (Boolean reciprocal formula).

If \(f\in R\) has no zeros on \(\{0,1\}^n\), then

\[ \delta(f,B_n)=\deg f+\deg_{\mathrm{bool}}(f^{-1}), \]

where \(f^{-1}\) is the inverse of \(f\) in \(A_n\).

For a Boolean function \(\phi:\{0,1\}^n\to k\), the coefficient of \(x_1\cdots x_n\) in its multilinear representative is

Thus the top coefficient of \(f^{-1}\) is

Theorem 7.2 (Generic maximum on the Boolean cube).

Assume \(k\) is infinite and \(\charac k=0\) or \(\charac k>n\). Let \(d\ge1\). On a nonempty Zariski-open subset of the space of degree-at-most-\(d\) polynomials with no Boolean zeros,

\[ \deg_{\mathrm{bool}}(f^{-1})=n. \]

Consequently, for generic polynomials of exact degree \(d\) with no Boolean zeros,

\[ \delta(f,B_n)=n+d. \]

8 Cardinality and Knapsack Contradictions

Let

and assume \(a\in k\setminus\{0,\ldots,n\}\). Consider

Theorem 8.1 (Cardinality contradiction).

Assume \(\charac k=0\) or \(\charac k>n\). The static refutation degree of this presentation is exactly

\[ n+1. \]

Proposition 8.2 (Full multilinear support).

Under the same assumptions, the multilinear inverse \(q=(t-a)^{-1}\in A_n\) has every squarefree monomial with nonzero coefficient. Hence

\[ |\Supp(q)|=2^n. \]

Moreover every polynomial representative of \(q\) has at least \(2^n\) standard monomials before reduction modulo \(B_n\).

This support statement is a normal-form size statement. It is compatible with the fact that the same multiplier is a univariate polynomial in \(t\) of degree \(n\).

The same argument applies to weighted knapsack equations. If

has no Boolean zeros, then

and for a nonempty Zariski-open set of coefficients this degree is \(n+1\).

9 Equivariant Macaulay Maps

Let \(G\) be a linearly reductive group over \(k\). Assume \(G\) acts linearly on \(\operatorname{span}_k(x_1,\ldots,x_n)\) and fixes \(x_0\).

A homogeneous \(G\)-equivariant presentation consists of finite-dimensional \(G\)-modules \(E_a\), degrees \(d_a\), and \(G\)-equivariant maps

Let

For \(D\ge0\), define

with \(S_j=0\) for \(j<0\), and the Macaulay map

Then \((J_\alpha)_D=\im\mu_D\), and \(\mu_D\) is \(G\)-equivariant.

Theorem 9.1 (Invariant Macaulay reduction).

Let \(H\in S_D^G\). Then

\[ H\in (J_\alpha)_D \quad\Longleftrightarrow\quad H\in \im\bigl(\mu_D^G:M_D(\alpha)^G\to S_D^G\bigr). \]

In particular,

\[ x_0^D\in J_\alpha \quad\Longleftrightarrow\quad x_0^D\in \im(\mu_D^G). \]

Thus invariant static proof search is compressed exactly to invariant Macaulay maps.

10 Isotypic Obstructions

Let

be the isotypic decompositions. Since \(\mu_D\) is \(G\)-equivariant, it preserves isotypic type.

Theorem 10.1 (Isotypic membership criterion).

If \(H\in S_D[\lambda]\), then

\[ H\in (J_\alpha)_D \quad\Longleftrightarrow\quad H\in \mu_D(M_D(\alpha)[\lambda]). \]

In particular, if \(M_D(\alpha)[\lambda]=0\) and \(H\ne0\), then \(H\notin (J_\alpha)_D\).

First occurrence of representations in the Macaulay source therefore gives degree lower bounds. If all generators are \(G\)-invariant of degrees \(d_i\), a type-\(\lambda\) consequence cannot be derived in degree \(D\) unless \(\lambda\) occurs in some \(S_{\le D-d_i}\).

11 Symmetric Boolean Systems

Assume \(\charac k=0\) or \(\charac k>n\). Let \(S_n\) act on

by permuting variables, and put \(t=x_1+\cdots+x_n\).

Lemma 11.1 (Invariant Boolean quotient).

There is a filtered algebra isomorphism

\[ A_n^{S_n} \cong k[t]/(\chi_n(t)), \qquad \chi_n(t)=\prod_{a=0}^n(t-a), \]

where the degree filtration corresponds to ordinary degree in \(t\), truncated at \(n\).

Theorem 11.2 (Exact univariate reduction).

Let \(f_1,\ldots,f_m\in k[x_1,\ldots,x_n]^{S_n}\), and consider the Boolean presentation

\[ \mathbf P=(f_1,\ldots,f_m,\ x_i^2-x_i\ (1\le i\le n)). \]

Let \(\bar f_j(t)\) be the image of \(f_j\) in \(k[t]/(\chi_n(t))\). Then \(\delta_{\mathbf P}(1)\) is the least \(D\) such that

\[ 1\in \sum_{j=1}^m \bar f_j(t)\,k[t]_{\le D-\deg f_j} \quad\text{inside }k[t]/(\chi_n(t)). \]

12 Block Symmetry and Finite Grids

Let

and let \(G=S_{n_1}\times\cdots\times S_{n_r}\) act by permuting variables inside each block. Define

If \(\charac k=0\) or \(\charac k>\max_\ell n_\ell\), then

with total-degree filtration in the orbit parameters.

Consequently, a block-symmetric Boolean system

has static refutation degree equal to the least \(D\) such that

inside the finite-grid coordinate algebra above. For one equation \(F=0\) with no zeros on the grid,

Let \(N=n_1+\cdots+n_r\). On coefficient spaces where a top grid coefficient of \(F^{-1}\) is not identically zero, generic degree-\(d\) block-symmetric contradictions have degree

For affine-linear \(F\), nonvanishing is witnessed by \(F=t_1+\cdots+t_r-a\), with \(a\notin\{0,\ldots,N\}\), using iterated finite differences of \(1/(z-a)\).

13 Dual Linear Functionals

Let

Then \(\delta_{\mathbf F}(1)>D\) if and only if \(1\notin V_D\), equivalently there exists a linear functional

such that

for every \(i\) and every \(q\in R_{\le D-\deg f_i}\).

Over a finite domain, this dual functional may be taken on the filtered coordinate algebra.

Proposition 13.1 (Reciprocal dual form).

Let \(X\) be a finite grid and let \(f\) be nonzero on \(X\). If

\[ \deg_X(f^{-1})>r, \]

then there exists a linear functional

\[ \Lambda:A_{X,\le r+\deg f}\to k \]

such that

\[ \Lambda(1)\ne0,\qquad \Lambda(\bar f\,A_{X,\le r})=0. \]

If a linearly reductive group acts and all data are invariant, such functionals may be averaged to invariant functionals.

14 First Occurrence for Symmetric Groups

Assume \(\charac k=0\). Let \(S_n\) act on \(R=k[x_1,\ldots,x_n]\). For a partition \(\lambda\vdash n\), let \(S^\lambda\) be the Specht module. The first total degree in which \(S^\lambda\) occurs in \(R\) is

the lowest degree appearing in the fake-degree polynomial.

Proposition 14.1 (First-occurrence bound).

Let \(f_1,\ldots,f_m\in R^{S_n}\) be invariant generators of degrees \(d_1,\ldots,d_m\). If a homogeneous component of a consequence has type \(\lambda\), then no static derivation of that component in degree \(D\) can occur unless

\[ D\ge \min_i(d_i+b(\lambda)). \]

For the sign representation \(\lambda=(1^n)\),

Thus invariant generators of minimum degree \(d_{\min}\) cannot produce an alternating component before degree

15 Position Among Algebraic Proof Measures

The results above concern static algebraic derivation degree:

They apply directly to Hilbert--Nullstellensatz degree and bounded static ideal membership. They give exact filtered-degree and equivariant reductions for such identities.

They also explain a precise bridge to functional lower-bound methods. For a single equation \(f=0\) over a finite domain, the multiplier is the reciprocal function \(1/f\) in the coordinate algebra. Lower bounds for static degree are exactly lower bounds on the filtered degree of this reciprocal. Stronger proof systems, such as IPS fragments or dynamic Polynomial Calculus size measures, require additional circuit-complexity or derivational arguments, but the finite-domain reciprocal identity is the static-degree core of that phenomenon.

16 Summary

The main conclusions are:

1. for a chosen presentation,

   \[ \delta_{\mathbf F}(h)=\min\{D:x_0^{D-\deg h}h^h\in J_{\mathbf F}\}; \]

2. the excess degree is the \(x_0\)-torsion order in \((J_{\mathbf F}:x_0^\infty)/J_{\mathbf F}\);

3. over degree-compatible finite domains,

   \[ \delta(1)= \min\left\{D: 1\in\sum_j \bar f_j A_{X,\le D-\deg f_j} \right\}; \]

4. for one equation with no finite-domain zeros,

   \[ \delta=\deg f+\deg_X(f^{-1}); \]

5. generic degree-\(d\) Boolean contradictions have degree \(n+d\);

6. the cardinality contradiction has exact degree \(n+1\) and a full-support multilinear reciprocal multiplier;

7. invariant static proof search under a linearly reductive group is exactly compressed by invariant Macaulay maps;

8. symmetric Boolean systems reduce exactly to univariate filtered membership in

   \[ k[t]/\prod_{a=0}^n(t-a); \]

9. non-invariant consequences admit first-occurrence lower bounds from isotypic representation theory.

In the language of access systems, \(\delta_{\mathbf F}(h)\) is the certification cost associated with the chosen polynomial presentation. The homogenized ideal \(J_{\mathbf F}\) records which consequences are visible at each degree level, while the \(x_0\)-torsion quotient records the delay before a true affine consequence becomes visible in the filtered presentation. Thus static proof degree is filtered membership: a bounded certificate exists exactly when the homogenized consequence appears in the corresponding finite degree slice.