Affine Coordinates and the Affine Kernel Basis

Status: Established

The affine butterfly replaces repeated squaring by repeated affine quadratic maps. This chapter constructs polynomial coordinates adapted to those maps and proves that the resulting affine kernel family is a basis.

The basis theorem is purely algebraic. It does not require the existence of an evaluation-domain tower, although such a tower is needed for the evaluation algorithms developed later.

9.1 Recursive affine coordinates

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

$$u_i\in {\mathbb{F}}^{\times },v_i\in \mathbb{F},0\le i<m.$$

Define the recursive affine coordinates

$$X_0(X)=X$$

and

$$X_{i+1}(X)=\frac{X_i(X{)}^2-v_i}{u_i}$$

for $0\le i<m$.

These are polynomial identities in the original variable $X$. The notation $X_i$ names the polynomial coordinate at level $i$; it does not introduce an independent variable.

Proposition 9.1 — Degree doubling

For every $i\in \{0,\dots ,m\}$,

$$\mathrm{deg}{X}_i=2^i.$$

Moreover, each $X_i$ has a nonzero leading coefficient.

Proof

The statement holds for $X_0=X$. Suppose $X_i$ has degree $2^i$ and nonzero leading coefficient $c_i$. Then $X_i^2-v_i$ has degree $2^{i+1}$ and leading coefficient $c_i^2$. Division by $u_i\ne 0$ preserves the degree and gives the nonzero leading coefficient

$$c_{i+1}=\frac{c_i^2}{u_i}.$$

The result follows by induction. $\square$

9.2 Affine monomials

For $e=(e_0,\dots ,e_{m-1})\in {\mathbb{B}}_m$, define

$$M_e^{\mathrm{aff}}(X)=\prod _{i=0}^{m-1}{X}_i(X{)}^{e_i}.$$

Because each $e_i$ is Boolean,

$$\mathrm{deg}{M}_e^{\mathrm{aff}}=\sum _{i=0}^{m-1}{e}_i{2}^i=|e{|}_2.$$

As $e$ ranges over ${\mathbb{B}}_m$, these degrees are exactly

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

Theorem 9.2 — Affine monomial basis

The family

$$\left\{M_e^{\mathrm{aff}}:e\in {\mathbb{B}}_m\right\}$$

is a basis of $\mathbb{F}[X{]}_{<2^m}$.

Proof

The affine monomials have pairwise distinct degrees. In a nontrivial linear combination, choose a term of largest degree having a nonzero coefficient. No other term has the same degree, so its leading term cannot be cancelled. Thus the family is linearly independent.

It contains $2^m$ polynomials, equal to the dimension of $\mathbb{F}[X{]}_{<2^m}$. Therefore it is a basis. $\square$

With the affine monomials ordered by $|e{|}_2$, their coefficient matrix in the ordinary monomial basis is triangular with nonzero diagonal.

9.3 Affine kernel polynomials

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

$$K_y^{\mathrm{aff}}(X)=\prod _{i=0}^{m-1}(X_i(X)+y_i).$$

There are exactly $2^m$ affine kernel polynomials. Expanding the product in the affine monomial basis gives

$$K_y^{\mathrm{aff}}(X)=\sum _{e\in {\mathbb{B}}_m}\left(\prod _{i:e_i=0}{y}_i\right)M_e^{\mathrm{aff}}(X).$$

The coefficient of $M_e^{\mathrm{aff}}$ is $1$ exactly when every coordinate with $e_i=0$ also has $y_i=1$; otherwise it is $0$.

This Boolean incidence relation is identical to the relation between the ordinary kernel polynomials and the binary monomials in Chapter 3.

Theorem 9.3 — Affine kernel basis

The family

$$\left\{K_y^{\mathrm{aff}}:y\in {\mathbb{B}}_m\right\}$$

is a basis of $\mathbb{F}[X{]}_{<2^m}$.

Proof

The expansion from affine kernels to affine monomials is the tensor product of the one-coordinate transformation

$$X_i\text{and}{X}_i+1.$$

Relative to the local monomial pair $1,X_i$, its matrix is

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

Its determinant is $-1$, which is nonzero over every field. Therefore its $m$-fold tensor product is invertible. Hence the affine kernel family is obtained from the affine monomial basis by an invertible change of basis.

Theorem 9.2 shows that the affine monomials form a basis, so the affine kernels also form a basis. $\square$

The conclusion depends only on the degree-doubling property and not on the existence of finite sets $D_0,\dots ,D_m$ forming an affine domain tower.

9.4 Small example

Let $m=2$. Then

$$X_0=X$$

and

$$X_1=\frac{X^2-v_0}{u_0}.$$

The four affine monomials are

$$1,X_0,X_1,X_0{X}_1,$$

with respective degrees $0,1,2,3$. The affine kernels are

$$K_{(0,0)}^{\mathrm{aff}}=X_0{X}_1,$$

$$K_{(1,0)}^{\mathrm{aff}}=(X_0+1)X_1,$$

$$K_{(0,1)}^{\mathrm{aff}}=X_0(X_1+1),$$

and

$$K_{(1,1)}^{\mathrm{aff}}=(X_0+1)(X_1+1).$$

Their affine-monomial expansions are

The table is the same Boolean transform seen in the ordinary kernel basis; only the monomial coordinates have changed.

9.5 Exact coefficient conversion

Write a polynomial in affine kernel coordinates as

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

and in affine monomial coordinates as

$$U(X)=\sum _{e\in {\mathbb{B}}_m}{c}_e{M}_e^{\mathrm{aff}}(X).$$

The relation between $\lambda$ and $c$ is exactly the Boolean zeta-type relation from Chapter 3:

$$c_e=\sum _{y_i=1\text{ whenever }{e}_i=0}{\lambda }_y.$$

The same butterfly network therefore converts between the two tables. It uses exactly

$$\frac{m{2}^m}{2}$$

additions for the forward transform and the same number of additions or subtractions for its inverse.

These counts concern conversion between affine kernel coefficients and affine monomial coefficients. They do not include expansion of the recursive coordinates $X_i$ into ordinary monomials.

9.6 Low-degree filtration remains Boolean

The affine monomial $M_e^{\mathrm{aff}}$ has degree $|e{|}_2$, and these degrees are distinct. Consequently,

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

if and only if

$$c_e=0\text{for every }e\text{ with }|e{|}_2\ge 2^k.$$

Since the kernel-to-monomial Boolean transform is unchanged, the proof of Chapter 4 applies verbatim.

Corollary 9.4 — Affine low-degree character condition

Let $0\le k\le m$, let $q=m-k$, and write $y=(x,h)$ with $x\in {\mathbb{B}}_k$ and $h\in {\mathbb{B}}_q$. Then

$$\mathrm{deg}\left(\sum _{y\in {\mathbb{B}}_m}{\lambda }_y{K}_y^{\mathrm{aff}}\right)<2^k$$

if and only if there exists a table $\mu :{\mathbb{B}}_k\to \mathbb{F}$ such that

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

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

Thus the character space ${\mathsf{CH}}_{m,k}$ describes the degree filtration in both the ordinary and affine kernel bases.

9.7 What has been established

This chapter establishes:

• degree doubling for recursive affine coordinates;
• the affine monomial basis theorem;
• the affine kernel basis theorem over any field;
• the exact Boolean coefficient transform and its arithmetic cost; and
• the unchanged low-degree character condition in affine kernel coordinates.

It does not establish the existence of a compatible evaluation-domain tower or the complexity of evaluating this basis on such a tower.