Low-Degree Filtration

Status: Established

This chapter characterizes ordinary polynomial degree directly in the Boolean kernel coefficient table.

The central result is that a degree bound does not correspond to sparse kernel coefficients. Instead, it imposes an alternating character structure on the high coordinates.

4.1 Setting

Let

$$N=2^m,$$

and write a polynomial $U\in \mathbb{F}[X{]}_{<N}$ in the Boolean kernel basis:

$$U(X)=\sum _{y\in {\mathbb{B}}_m}{\lambda }_y{K}_y(X).$$

Fix an integer $k$ satisfying

$$0\le k\le m.$$

Set

$$q=m-k.$$

We split every kernel index as

$$y=(x,h),$$

where

$$x=(y_0,\dots ,y_{k-1})\in {\mathbb{B}}_k$$

contains the low coordinates, and

$$h=(y_k,\dots ,y_{m-1})\in {\mathbb{B}}_q$$

contains the high coordinates.

The kernel coefficient table is therefore written as

$${\lambda }_{(x,h)}.$$

4.2 The high-coordinate sign character

For $h\in {\mathbb{B}}_q$, define

$${\sigma }_q(h)=(-1{)}^{q-\mathrm{wt}(h)}.$$

Equivalently,

$${\sigma }_q(h)=\prod _{j=0}^{q-1}(-1{)}^{1-h_j}.$$

The value changes sign whenever one high coordinate is flipped.

Up to the constant factor $(-1{)}^q$, this is the Boolean character

$$h⟼(-1{)}^{\mathrm{wt}(h)}.$$

4.3 Main theorem

Theorem 4.1 — Low-degree filtration

Let

$$U(X)=\sum _{(x,h)\in {\mathbb{B}}_k\times {\mathbb{B}}_q}{\lambda }_{(x,h)}{K}_{(x,h)}(X).$$

Then

$$\mathrm{deg}U<2^k$$

if and only if there exists a unique function

$$\mu :{\mathbb{B}}_k⟶\mathbb{F}$$

such that

$$\boxed{{\lambda }_{(x,h)}=(-1{)}^{q-\mathrm{wt}(h)}{\mu }_x}$$

for every $x\in {\mathbb{B}}_k$ and every $h\in {\mathbb{B}}_q$.

The free coefficient is

$${\mu }_x={\lambda }_{(x,1_q)},$$

where

$$1_q=(1,\dots ,1).$$

4.4 Proof: degree implies the character condition

Write the monomial expansion of $U$ as

$$U(X)=\sum _{(r,t)\in {\mathbb{B}}_k\times {\mathbb{B}}_q}{u}_{(r,t)}{X}^{|r{|}_2+2^k|t{|}_2}.$$

By Chapter 1,

$$\mathrm{deg}U<2^k$$

if and only if

$$u_{(r,t)}=0$$

for every $r\in {\mathbb{B}}_k$ and every nonzero $t\in {\mathbb{B}}_q$.

By the coefficient formula from Chapter 3,

$$u_{(r,t)}=\sum _{x\ge \overline{r}}\sum _{h\ge \overline{t}}{\lambda }_{(x,h)}.$$

Fix a nonzero $t$. Since the Boolean zeta transform over the low coordinates is invertible, the identities

$$u_{(r,t)}=0\text{for every }r\in {\mathbb{B}}_k$$

imply

$$\sum _{h\ge \overline{t}}{\lambda }_{(x,h)}=0$$

for every $x\in {\mathbb{B}}_k$.

Because $t\ne 0_q$, its complement satisfies

$$\overline{t}\ne 1_q.$$

For fixed $x$, define

$$G_x(b)=\sum _{h\ge b}{\lambda }_{(x,h)}.$$

We have shown that

$$G_x(b)=0$$

for every $b\ne 1_q$.

At the all-one vector,

$$G_x(1_q)={\lambda }_{(x,1_q)}.$$

Define

$${\mu }_x={\lambda }_{(x,1_q)}.$$

Boolean Möbius inversion gives

$${\lambda }_{(x,h)}=\sum _{b\ge h}(-1{)}^{\mathrm{wt}(b)-\mathrm{wt}(h)}{G}_x(b).$$

Only $b=1_q$ can contribute. Therefore,

$${\lambda }_{(x,h)}=(-1{)}^{q-\mathrm{wt}(h)}{\mu }_x.$$

This proves the first direction.

4.5 Proof: the character condition implies low degree

Assume that

$${\lambda }_{(x,h)}=(-1{)}^{q-\mathrm{wt}(h)}{\mu }_x.$$

Let $t\in {\mathbb{B}}_q$ be nonzero and set

$$b=\overline{t}.$$

Since $t\ne 0_q$, we have

$$b\ne 1_q.$$

For every $x\in {\mathbb{B}}_k$,

$$\sum _{h\ge b}{\lambda }_{(x,h)}={\mu }_x\sum _{h\ge b}(-1{)}^{q-\mathrm{wt}(h)}.$$

There is at least one free coordinate in the sum because $b\ne 1_q$. The alternating Boolean sum therefore vanishes:

$$\sum _{h\ge b}(-1{)}^{q-\mathrm{wt}(h)}=0.$$

Consequently,

$$\sum _{h\ge \overline{t}}{\lambda }_{(x,h)}=0.$$

It follows that

$$u_{(r,t)}=0$$

for every $r\in {\mathbb{B}}_k$ and every nonzero $t\in {\mathbb{B}}_q$.

By the monomial low-degree condition,

$$\mathrm{deg}U<2^k.$$

This proves the converse direction.

4.6 Collapse of the high coordinates

For $x\in {\mathbb{B}}_k$, define the truncated kernel

$$K_x^{[k]}(X)=\prod _{i=0}^{k-1}\left(X^{2^i}+x_i\right).$$

The character condition gives

$$U(X)=\sum _{x\in {\mathbb{B}}_k}{\mu }_x\sum _{h\in {\mathbb{B}}_q}(-1{)}^{q-\mathrm{wt}(h)}{K}_{(x,h)}(X).$$

The high-coordinate sum factors coordinate by coordinate. For every $i\ge k$,

$$(X^{2^i}+1)-X^{2^i}=1.$$

Therefore,

$$\sum _{h\in {\mathbb{B}}_q}(-1{)}^{q-\mathrm{wt}(h)}{K}_{(x,h)}(X)=K_x^{[k]}(X).$$

Hence every polynomial satisfying $\mathrm{deg}U<2^k$ has the reduced expression

$$\boxed{U(X)=\sum _{x\in {\mathbb{B}}_k}{\mu }_x{K}_x^{[k]}(X)}.$$

This formula makes the collapse of the high coordinates explicit.

4.7 The character-side low-degree space

Define

$${\mathsf{CH}}_{m,k}=\left\{\lambda \in {\mathbb{F}}^{{\mathbb{B}}_m}:{\lambda }_{(x,h)}=(-1{)}^{q-\mathrm{wt}(h)}{\mu }_x\text{ for some }\mu :{\mathbb{B}}_k\to \mathbb{F}\right\}.$$

The low-degree theorem gives the exact correspondence

$$\mathrm{deg}U<2^k⟺\lambda \in {\mathsf{CH}}_{m,k}.$$

The table $\mu$ has $2^k$ independent entries. Therefore,

$$\dim {\mathsf{CH}}_{m,k}=2^k.$$

This agrees with

$$\dim \mathbb{F}[X{]}_{<2^k}=2^k.$$

4.8 Example: $m=3$ and $k=1$

Here,

$$q=m-k=2.$$

For each $x\in {\mathbb{B}}_1$, the four coefficients in the high-coordinate fiber are

Thus the full kernel coefficient table has the form

$${\lambda }_{(x,0,0)}={\mu }_x,{\lambda }_{(x,1,0)}=-{\mu }_x,{\lambda }_{(x,0,1)}=-{\mu }_x,{\lambda }_{(x,1,1)}={\mu }_x.$$

The polynomial collapses to

$$U(X)={\mu }_0{K}_{(0)}^{[1]}(X)+{\mu }_1{K}_{(1)}^{[1]}(X).$$

Since

$$K_{(0)}^{[1]}(X)=X$$

and

$$K_{(1)}^{[1]}(X)=X+1,$$

we obtain

$$U(X)={\mu }_{0}X+{\mu }_1(X+1).$$

This polynomial has degree less than $2$, as required.

4.9 Boundary cases

When $k=m$, we have $q=0$. There are no high coordinates, and the character condition imposes no restriction. This agrees with the fact that every polynomial in $\mathbb{F}[X{]}_{<2^m}$ has degree less than $2^m$.

When $k=0$, the table $\mu$ contains one scalar. The kernel coefficients must follow the complete alternating character

$${\lambda }_h=(-1{)}^{m-\mathrm{wt}(h)}\mu .$$

The corresponding polynomial is constant.

4.10 Summary

The Boolean kernel basis converts an ordinary degree condition into an exact character condition:

$$\boxed{\mathrm{deg}U<2^k⟺{\lambda }_{(x,h)}=(-1{)}^{m-k-\mathrm{wt}(h)}{\mu }_x}.$$

The next chapter studies how even–odd polynomial folding acts directly on the kernel coefficient table.