The Boolean Kernel Basis

Status: Established

This chapter proves that the $2^m$ Boolean kernel polynomials form a basis of

$$\mathbb{F}[X{]}_{<2^m}.$$

It also gives the exact transformation between monomial coefficients and kernel coefficients.

3.1 The kernel family

Let

$$N=2^m$$

and

$${\mathbb{B}}_m=\{0,1{\}}^m.$$

For every $y\in {\mathbb{B}}_m$, recall that

$$K_y(X)=\prod _{i=0}^{m-1}\left(X^{2^i}+y_i\right).$$

There are exactly

$$|{\mathbb{B}}_m|=2^m=N$$

kernel polynomials.

The polynomial space

$$\mathbb{F}[X{]}_{<N}$$

also has dimension $N$. Therefore, it is enough to prove that the kernel polynomials are linearly independent.

3.2 Recursive decomposition

Write a Boolean vector as

$$y=(b,z),$$

where

$$b=y_0\in \{0,1\}$$

and

$$z=(y_1,\dots ,y_{m-1})\in {\mathbb{B}}_{m-1}.$$

Define the smaller kernel polynomial

$$K_z(Y)=\prod _{i=0}^{m-2}\left(Y^{2^i}+z_i\right).$$

Substituting $Y=X^2$, we obtain

$$K_{(0,z)}(X)=X{K}_z(X^2)$$

and

$$K_{(1,z)}(X)=(X+1)K_z(X^2).$$

Therefore,

$$K_{(1,z)}(X)=K_z(X^2)+X{K}_z(X^2).$$

This separates every kernel into an even part and an odd part.

3.3 Linear independence

Theorem 3.1 — Boolean kernel basis

The family

$$\left\{K_y(X):y\in {\mathbb{B}}_m\right\}$$

is a basis of

$$\mathbb{F}[X{]}_{<2^m}.$$

Proof

We proceed by induction on $m$.

For $m=1$, the kernel family is

$$K_{(0)}(X)=X$$

and

$$K_{(1)}(X)=X+1.$$

These two polynomials are linearly independent and therefore form a basis of

$$\mathbb{F}[X{]}_{<2}.$$

Now suppose the result holds for $m-1$. Consider a linear relation

$$\sum _{z\in {\mathbb{B}}_{m-1}}{\alpha }_{0,z}{K}_{(0,z)}(X)+\sum _{z\in {\mathbb{B}}_{m-1}}{\alpha }_{1,z}{K}_{(1,z)}(X)=0.$$

Using the recursive identities, this becomes

$$\sum _z{\alpha }_{1,z}{K}_z(X^2)+X\sum _z\left({\alpha }_{0,z}+{\alpha }_{1,z}\right)K_z(X^2)=0.$$

The first sum contains only even powers of $X$, while the second contains only odd powers. The even and odd parts must therefore vanish separately:

$$\sum _z{\alpha }_{1,z}{K}_z(X^2)=0$$

and

$$\sum _z\left({\alpha }_{0,z}+{\alpha }_{1,z}\right)K_z(X^2)=0.$$

By the induction hypothesis, the polynomials $K_z$ are linearly independent. Hence

$${\alpha }_{1,z}=0$$

for every $z$, and

$${\alpha }_{0,z}+{\alpha }_{1,z}=0.$$

It follows that

$${\alpha }_{0,z}=0$$

for every $z$.

Thus the kernel family is linearly independent. Since it contains $2^m$ elements in a vector space of dimension $2^m$, it is a basis.

3.4 Unique kernel expansion

The basis theorem implies that every polynomial

$$U(X)\in \mathbb{F}[X{]}_{<N}$$

has a unique representation

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

The function

$$\lambda :{\mathbb{B}}_m⟶\mathbb{F}$$

is called the Boolean kernel coefficient table of $U$.

The entries ${\lambda }_y$ are coordinates in a basis. They are not evaluations of $U$.

3.5 From kernel coefficients to monomial coefficients

Write

$$U(X)=\sum _{a\in {\mathbb{B}}_m}{u}_a{X}^{|a{|}_2}$$

and

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

From the coefficient formula of Chapter 2,

$$[K_y{]}_a=\{\begin{array}{ll}1,& y\ge \overline{a},\\ 0,& \text{otherwise}.\end{array}$$

Therefore,

$$\boxed{u_a=\sum _{y\ge \overline{a}}{\lambda }_y.}$$

This is the Boolean zeta transform, followed by the complement permutation.

3.6 Zeta-matrix representation

Define the coefficient matrix $Z_m$ by

$$Z_m(a,y)=[K_y{]}_a.$$

Then

$$Z_m(a,y)=1[y\ge \overline{a}],$$

where $1[P]$ equals $1$ when $P$ is true and $0$ otherwise.

If $u$ and $\lambda$ are written as column vectors, then

$$u=Z_m\lambda .$$

For one coordinate,

$$Z_1=\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right).$$

With the compatible Boolean ordering, the full matrix has a Kronecker structure obtained from $Z_1$, up to the ordering of the Boolean indices.

Since

$$\det Z_1=-1,$$

the one-coordinate matrix is invertible over every field. Its Kronecker powers are also invertible.

This gives a second proof of the Boolean kernel basis theorem.

3.7 Möbius inversion

Define

$$g(b)=u_{\overline{b}}.$$

The coefficient relation becomes

$$g(b)=\sum _{y\ge b}{\lambda }_y.$$

Boolean Möbius inversion gives

$$\boxed{{\lambda }_y=\sum _{b\ge y}(-1{)}^{\mathrm{wt}(b)-\mathrm{wt}(y)}g(b).}$$

Equivalently,

$$\boxed{{\lambda }_y=\sum _{b\ge y}(-1{)}^{\mathrm{wt}(b)-\mathrm{wt}(y)}{u}_{\overline{b}}.}$$

These formulas remain valid in characteristic $2$, where subtraction and addition coincide.

3.8 Exact transformation cost

The Boolean zeta transform can be computed coordinate by coordinate.

For each of the $m$ coordinates, there are

$$2^{m-1}=\frac{N}{2}$$

pair updates. Therefore, conversion from kernel coefficients to monomial coefficients uses exactly

$$\frac{mN}{2}$$

field additions, apart from index permutations.

The inverse Möbius transform uses exactly

$$\frac{mN}{2}$$

field subtractions, apart from index permutations.

Thus both transformations have complexity

$$O(N\log N),$$

with exact arithmetic count

$$\frac{N{\log }_{2}N}{2}.$$

Chapter 9 shows that the affine kernel basis has the same Boolean coefficient transform. The same butterfly network and arithmetic count therefore apply in affine monomial coordinates.

3.9 Summary

We have established the linear isomorphism

$${\mathbb{F}}^{{\mathbb{B}}_m}⟶\mathbb{F}[X{]}_{<2^m},$$

defined by

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

The monomial and kernel coefficient tables are related by an invertible Boolean zeta transform.

The next chapter studies how an ordinary polynomial degree bound appears in the Boolean kernel coefficient table.