The Affine Butterfly Identity

Status: Established locally; global tower existence is conditional

The classical even–odd butterfly pairs the points $\alpha$ and $-\alpha$ through their common square. The same local reconstruction works when the square is followed by an invertible affine change of coordinate.

This chapter proves that local identity and defines the domain structure needed to iterate it. It does not assert that a tower of every desired size exists over every field.

8.1 Assumptions and notation

Let $\mathbb{F}$ be a field of characteristic different from $2$. Choose $u\in {\mathbb{F}}^{\times }$ and $v\in \mathbb{F}$, and define the affine quadratic map

$${\pi }_{u,v}(x)=\frac{x^2-v}{u}.$$

For every $\alpha \in \mathbb{F}$,

$${\pi }_{u,v}(\alpha )={\pi }_{u,v}(-\alpha ).$$

If $\alpha \ne 0$, the two points $\alpha$ and $-\alpha$ are distinct. This is the local two-to-one structure used by the affine butterfly.

The assumptions $u\ne 0$ and $\mathrm{char}(\mathbb{F})\ne 2$ are essential for the formulas below: the map contains division by $u$, and the reconstruction formulas contain division by $2$.

8.2 Even–odd decomposition

Let

$$f(X)=\sum _{a=0}^d{c}_a{X}^a.$$

Separating its even and odd powers gives unique polynomials $f_{\mathrm{even}}$ and $f_{\mathrm{odd}}$ such that

$$f(X)=f_{\mathrm{even}}(X^2)+X{f}_{\mathrm{odd}}(X^2),$$

where

$$f_{\mathrm{even}}(T)=\sum _j{c}_{2j}{T}^j$$

and

$$f_{\mathrm{odd}}(T)=\sum _j{c}_{2j+1}{T}^j.$$

To express this decomposition in the affine coordinate

$$Y=\frac{X^2-v}{u},$$

define

$$A(Y)=f_{\mathrm{even}}(uY+v)$$

and

$$B(Y)=f_{\mathrm{odd}}(uY+v).$$

Since $X^2=uY+v$, we obtain

$$f(X)=A(Y)+XB(Y).$$

Proposition 8.1 — Affine even–odd decomposition

For every $f\in \mathbb{F}[X]$, there are unique polynomials $A,B\in \mathbb{F}[Y]$ satisfying

$$f(X)=A\left(\frac{X^2-v}{u}\right)+XB\left(\frac{X^2-v}{u}\right).$$

Proof

Existence follows from the construction above. For uniqueness, suppose

$$A\left(\frac{X^2-v}{u}\right)+XB\left(\frac{X^2-v}{u}\right)=0.$$

The first term contains only even powers of $X$, while the second contains only odd powers. Both terms must therefore vanish. The substitution $T\mapsto (X^2-v)/u$ is injective on $\mathbb{F}[T]$, so $A=B=0$. $\square$

8.3 Local evaluation butterfly

Let $\alpha \in {\mathbb{F}}^{\times }$ and set

$$\beta ={\pi }_{u,v}(\alpha )=\frac{{\alpha }^2-v}{u}.$$

Evaluating the affine decomposition at the paired points gives

$$f(\alpha )=A(\beta )+\alpha B(\beta )$$

and

$$f(-\alpha )=A(\beta )-\alpha B(\beta ).$$

Theorem 8.2 — Affine butterfly identity

For every nonzero $\alpha \in \mathbb{F}$,

$$A(\beta )=\frac{f(\alpha )+f(-\alpha )}{2}$$

and

$$B(\beta )=\frac{f(\alpha )-f(-\alpha )}{2\alpha },$$

where $\beta =({\alpha }^2-v)/u$.

Proof

Add the two evaluation identities to obtain

$$f(\alpha )+f(-\alpha )=2A(\beta ).$$

Subtract them to obtain

$$f(\alpha )-f(-\alpha )=2\alpha B(\beta ).$$

Because $2\ne 0$ and $\alpha \ne 0$, both denominators are invertible. $\square$

The reconstruction formula is locally identical to the classical butterfly. The parameters $u$ and $v$ determine which parent point $\beta$ is associated with the pair $\{\alpha ,-\alpha \}$, but they do not change the two-point linear reconstruction.

8.4 Degree reduction

If $f=0$, then $A=B=0$ and every degree-bound statement below is immediate. Assume henceforth that $f\ne 0$ and let $n=\mathrm{deg}f$. From the ordinary even–odd decomposition,

$$\mathrm{deg}{f}_{\mathrm{even}}\le \lfloor \frac{n}{2}\rfloor$$

and

$$\mathrm{deg}{f}_{\mathrm{odd}}\le \lfloor \frac{n-1}{2}\rfloor .$$

Composition with the nonconstant affine polynomial $uY+v$ preserves degree. Therefore

$$\mathrm{deg}A\le \lfloor \frac{n}{2}\rfloor$$

and

$$\mathrm{deg}B\le \lfloor \frac{n-1}{2}\rfloor .$$

In particular, if $\mathrm{deg}f<N$ with even $N$, then

$$\mathrm{deg}A<\frac{N}{2}\text{and}\mathrm{deg}B<\frac{N}{2}.$$

Thus the affine change of coordinate preserves the local degree-halving property of the classical butterfly.

8.5 Affine quadratic domain towers

The local identity can be iterated only when the evaluation domains are compatible across rounds.

Definition 8.3 — Affine quadratic domain tower

An affine quadratic domain tower of depth $m$ over $\mathbb{F}$ consists of finite sets

$$D_0,D_1,\dots ,D_m\subseteq \mathbb{F}$$

and parameters

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

such that:

1. $|D_i|=2^{m-i}$ for every $i$;

2. the map

   $${\pi }_i(x)=\frac{x^2-v_i}{u_i}$$

   sends $D_i$ onto $D_{i+1}$; and

3. every $\beta \in D_{i+1}$ has exactly two preimages in $D_i$.

Since the two solutions of

$$x^2=u_i\beta +v_i$$

are $\alpha$ and $-\alpha$, each valid fiber has the form

$$\{\alpha ,-\alpha \}$$

with $\alpha \ne 0$. Consequently, no valid two-point fiber contains zero.

Proposition 8.4 — One evaluation layer

Suppose $D_i\to D_{i+1}$ is one level of an affine quadratic domain tower. Given the evaluations of $f$ on $D_i$, the butterfly formulas determine the evaluations of both affine components $A$ and $B$ on $D_{i+1}$.

Proof

For each $\beta \in D_{i+1}$, choose either element $\alpha$ of its two-point fiber. Both $f(\alpha )$ and $f(-\alpha )$ are available in the evaluation table on $D_i$. Theorem 8.2 determines $A(\beta )$ and $B(\beta )$. Repeating this for every fiber fills both evaluation tables on $D_{i+1}$. $\square$

The result is independent of which member of the fiber is named $\alpha$: replacing $\alpha$ by $-\alpha$ changes both the numerator and denominator in the formula for $B(\beta )$ by a minus sign.

8.6 Local theorem versus global existence

The affine butterfly identity holds for every choice of $u\ne 0$, $v$, and nonzero paired point $\alpha$ over a field of odd characteristic. This is a local algebraic theorem.

By contrast, constructing a complete tower

$$D_0⟶D_1⟶\cdots ⟶D_m$$

requires simultaneous quadratic-residue and cardinality conditions at every level. The local theorem does not guarantee that such a tower exists for a specified field and depth.

Accordingly, later algorithms using an affine tower must state tower existence as an explicit assumption unless a separate construction theorem has been proved for the field in question.

8.7 What has been established

This chapter establishes:

• the unique affine even–odd decomposition;
• the two-point affine butterfly reconstruction formulas;
• local degree halving;
• the precise definition of an affine quadratic domain tower; and
• one evaluation-layer reduction on any valid tower level.

It does not establish universal or maximal tower existence, an FFT complexity bound, or a protocol-soundness result.