Binary Exponents and Polynomial Coordinates

Status: Established

This chapter introduces the binary notation used throughout the book. It provides the coordinate system connecting Boolean vectors, integer exponents, and polynomials of degree less than a power of two.

1.1 Basic setting

Let $\mathbb{F}$ be a field and let $m\ge 1$. Define

$$N=2^m$$

and

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

An element of ${\mathbb{B}}_m$ is written

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

The coordinates are ordered from the least significant bit to the most significant bit. Thus $a_0$ has weight $1$, $a_1$ has weight $2$, and $a_{m-1}$ has weight $2^{m-1}$.

1.2 Binary value of a Boolean vector

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

$$|a{|}_2=\sum _{i=0}^{m-1}{a}_i{2}^i.$$

The map

$$a⟼|a{|}_2$$

is a bijection from ${\mathbb{B}}_m$ to

$$\{0,\dots ,2^m-1\}.$$

Consequently, every exponent $j$ satisfying $0\le j<N$ has a unique binary representation $j=|a{|}_2$ for some $a\in {\mathbb{B}}_m$.

1.3 Boolean indexing of polynomial coefficients

Let

$$\mathbb{F}[X{]}_{<N}=\{U(X)\in \mathbb{F}[X]:\mathrm{deg}U<N\}.$$

Every polynomial $U\in \mathbb{F}[X{]}_{<N}$ has a unique monomial expansion

$$U(X)=\sum _{j=0}^{N-1}{u}_j{X}^j.$$

Using binary exponent coordinates, the same polynomial can be written as

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

where $u_a$ denotes the coefficient of $X^{|a{|}_2}$. This is a reindexing of the ordinary monomial basis, not a new polynomial representation.

1.4 Example with three bits

Let $m=3$. Then $N=8$, and the Boolean vectors correspond to exponents as follows:

Therefore, a polynomial of degree less than $8$ can be written as

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

1.5 Low and high coordinates

Fix an integer $k$ satisfying

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

Every $a\in {\mathbb{B}}_m$ can be decomposed uniquely as

$$a=(r,s),$$

where

$$r=(a_0,\dots ,a_{k-1})\in {\mathbb{B}}_k$$

contains the low coordinates and

$$s=(a_k,\dots ,a_{m-1})\in {\mathbb{B}}_{m-k}$$

contains the high coordinates. The binary value satisfies

$$|a{|}_2=|r{|}_2+2^k|s{|}_2.$$

1.6 Degree and high-coordinate support

Proposition 1.1 — Monomial low-degree condition

Let

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

Then

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

if and only if

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

for every $r\in {\mathbb{B}}_k$ and every nonzero $s\in {\mathbb{B}}_{m-k}$.

Proof

Suppose first that $\mathrm{deg}U<2^k$. If $s\ne 0$, then $|s{|}_2\ge 1$ and

$$|r{|}_2+2^k|s{|}_2\ge 2^k.$$

The corresponding monomial cannot occur in $U$, so $u_{(r,s)}=0$.

Conversely, suppose that $u_{(r,s)}=0$ whenever $s\ne 0$. Then

$$U(X)=\sum _{r\in {\mathbb{B}}_k}{u}_{(r,0)}{X}^{|r{|}_2}.$$

For every $r\in {\mathbb{B}}_k$, we have $|r{|}_2\le 2^k-1$. It follows that $\mathrm{deg}U<2^k$.

This proves both directions.

1.7 Why this coordinate system matters

Binary exponent coordinates expose the recursive structure of $\mathbb{F}[X{]}_{<2^m}$. They will allow us to:

• define kernel polynomials indexed by Boolean vectors;
• describe their coefficients through Boolean relations;
• separate low-degree and high-degree components;
• express polynomial folding coordinate by coordinate;
• connect univariate polynomials with multilinear evaluation.

The next chapter introduces the kernel polynomials

$$K_y(X)=\prod _{i=0}^{m-1}\left(X^{2^i}+y_i\right),y\in {\mathbb{B}}_m.$$