Kernel Polynomials

Status: Established

This chapter introduces the Boolean kernel polynomials and determines their monomial coefficients and support exactly.

2.1 Definition

Let $m\ge 1$, let

$$N=2^m,$$

and let

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

For every Boolean vector

$$y=(y_0,\dots ,y_{m-1})\in {\mathbb{B}}_m,$$

we define the associated kernel polynomial by

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

The vector $y$ is called the kernel index.

2.2 Degree and leading coefficient

Every factor $X^{2^i}+y_i$ is monic and has degree $2^i$. Consequently,

$$\mathrm{deg}{K}_y=\sum _{i=0}^{m-1}{2}^i=2^m-1=N-1.$$

Therefore every kernel polynomial is monic of degree $N-1$.

Proposition 2.1 — Degree of a kernel polynomial

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

$$\mathrm{deg}{K}_y=N-1,$$

and the coefficient of $X^{N-1}$ is $1$.

Proof

The leading term of the product is obtained by selecting $X^{2^i}$ from every factor. Hence the leading monomial is

$$\prod _{i=0}^{m-1}{X}^{2^i}=X^{{\sum }_{i=0}^{m-1}{2}^i}=X^{N-1}.$$

Its coefficient is $1$.

2.3 Boolean complement

For

$$a=(a_0,\dots ,a_{m-1})\in {\mathbb{B}}_m,$$

define its Boolean complement by

$$\overline{a}=(1-a_0,\dots ,1-a_{m-1}).$$

For two Boolean vectors $a,y\in {\mathbb{B}}_m$, we write

$$y\ge a$$

when

$$y_i\ge a_i$$

for every $i$.

2.4 Exact coefficient formula

Write

$$K_y(X)=\sum _{a\in {\mathbb{B}}_m}[K_y{]}_a{X}^{|a{|}_2},$$

where $[K_y{]}_a$ denotes the coefficient of $X^{|a{|}_2}$.

Proposition 2.2 — Coefficient formula

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

$$[K_y{]}_a=\prod _{i:a_i=0}{y}_i.$$

Because $y$ is Boolean, this is equivalent to

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

Proof

To obtain the monomial $X^{|a{|}_2}$, we select $X^{2^i}$ from the $i$-th factor when $a_i=1$, and select $y_i$ when $a_i=0$.

The resulting coefficient is therefore

$$\prod _{i:a_i=0}{y}_i.$$

Since every $y_i$ belongs to $\{0,1\}$, this product equals $1$ exactly when

$$y_i=1$$

for every coordinate satisfying $a_i=0$. This condition is precisely

$$y\ge \overline{a}.$$

2.5 Monomial support

Define the monomial support of $K_y$ by

$$\mathrm{Supp}(K_y)=\left\{a\in {\mathbb{B}}_m:[K_y{]}_a\ne 0\right\}.$$

The coefficient formula gives

$$\mathrm{Supp}(K_y)=\left\{a\in {\mathbb{B}}_m:y\ge \overline{a}\right\}.$$

Equivalently, if $y_i=0$, then every exponent index in the support must satisfy $a_i=1$. If $y_i=1$, then $a_i$ is free.

Let

$$\mathrm{wt}(y)=\sum _{i=0}^{m-1}{y}_i$$

denote the Hamming weight of $y$.

Corollary 2.3 — Support size

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

$$\left|\mathrm{Supp}(K_y)\right|=2^{\mathrm{wt}(y)}.$$

Proof

Each coordinate with $y_i=0$ forces $a_i=1$. Each coordinate with $y_i=1$ leaves $a_i$ free. There are $\mathrm{wt}(y)$ free coordinates, giving

$$2^{\mathrm{wt}(y)}$$

possible exponent indices.

2.6 Two extremal kernels

Let

$$0_m=(0,\dots ,0)$$

and

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

For the all-zero index,

$$K_{0_m}(X)=\prod _{i=0}^{m-1}{X}^{2^i}=X^{N-1}.$$

For the all-one index,

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

Using the binary factorization of the geometric sum,

$$K_{1_m}(X)=1+X+\cdots +X^{N-1}.$$

Equivalently,

$$(X-1)K_{1_m}(X)=X^N-1.$$

2.7 Examples for $m=1$

When $m=1$, the two kernels are

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

and

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

2.8 Examples for $m=2$

When $m=2$, we have

$$K_{(0,0)}(X)=X^3,$$

$$K_{(1,0)}(X)=X^3+X^2,$$

$$K_{(0,1)}(X)=X^3+X,$$

and

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

2.9 Examples for $m=3$

When $m=3$, the eight kernel polynomials are

$$K_{(0,0,0)}(X)=X^7,$$

$$K_{(1,0,0)}(X)=X^7+X^6,$$

$$K_{(0,1,0)}(X)=X^7+X^5,$$

$$K_{(1,1,0)}(X)=X^7+X^6+X^5+X^4,$$

$$K_{(0,0,1)}(X)=X^7+X^3,$$

$$K_{(1,0,1)}(X)=X^7+X^6+X^3+X^2,$$

$$K_{(0,1,1)}(X)=X^7+X^5+X^3+X,$$

and

$$K_{(1,1,1)}(X)=X^7+X^6+X^5+X^4+X^3+X^2+X+1.$$

These examples illustrate the exact support formula:

$$[K_y{]}_a=1⟺y\ge \overline{a}.$$

2.10 What comes next

The family

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

contains exactly $N=2^m$ polynomials in the $N$-dimensional space

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

The next chapter proves that these polynomials are linearly independent and therefore form a basis of $\mathbb{F}[X{]}_{<N}$.