Number of Terms in Polynomial

Question

The number of terms in a polynomial expansion can be found here

But what about in number of terms for polynomial expansion in Galois Field (or characteristic of 2, where addition is addition mod 2 or Xor)

Answer 1

The "number of terms" of a polynomial $f(X_1,X_2)=\sum c_{i,j}X^i X^j$ is defined to mean $$\left|\{(i,j) | c_{i,j}\not=0\}\right|.$$

So, with $f=(X_1+X_2)^2\in\mathbb{F}_2[X_1,X_2]$ we have $$c_{1,1}=c_{2,2}=1\not=0, c_{1,2}=c_{2,1}=0$$ and the number of terms is $2$.

Answer 2

Sorry I went a bit crazy with this (too) rigorous proof but I thought it could still be nice sharing it :)

We are interessted in the number of terms of $(x_1 + ... + x_m)^n$ modulo $2$.

Lemma 1$$ \left(x_1 + ... + x_m\right)^{2^k}\ (mod\ 2) = \left(x_1^{2^k} + ... + x_m^{2^k}\right)\ \text{for }k \in\mathbb{N} $$

Proof by induction on $k$:

• Base $k=1$ : Clearly $(x_1 + ... + x_m)^2\ (mod\ 2) = (x_1^2 + .. + x_m^2)$.
• Induction assuming true up to $k$, then : $$(x_1 + ... + x_m)^{2^{k+1}}\ (mod\ 2) = \left((x_1 + ... + x_m)^{2^k}\right)^2 \overset{(*)}{=} \left(x_1^{2^k} + ... + x_m^{2^k}\right)^2 \overset{(**)}{=} \left(x_1^{2^{k+1}} + ... + x_m^{2^{k+1}}\right) $$

$(*)$ : Inductive hypothesis

$(**)$ : Renaming $x_i^{2^k} = y_i$ and reapplying the base case.

This means we can decompose $(x_1 + ... + x_m)^n$ into power of two. For example let's say $n=11$ we therefore write : $$ \begin{align} (x_1 + ... + x_m)^{11} &=(x_1 + ... + x_m)(x_1 + ... + x_m)^2(x_1 + ... + x_m)^8 \\ (x_1 + ... + x_m)^{11} \ (mod\ 2) &= (x_1 + ... + x_m)(x_1^2 + ... + x_m^2)(x_1^8 + ... + x_m^8) \end{align} $$

Definition : A term $T_i$ of degree $d$ is the product of 1 or several variables $x_j$ with possibly a coefficient in front: $$ T_i = \lambda \prod_{j=1}^m x_j^{e_{i,j}} \hspace{1cm} \text{where} \hspace{1cm}\sum_{j=1}^m e_{i,j} = d,\ e_{i,j} \geq 0,\ \lambda \in\mathbb{R}^* $$ Moreover we say that two terms $T_i,\ T_j$ are a equivalent if $(e_{i,k})_k = (e_{j,k})_k,\ 1 \leq k \leq m$, otherwise we say that they are distinct. For example $2x_1^2x_2x_4^3$ and $8x_4^3x_1^2x_2$ are two equivalent terms of degree $6$.

Lemma 2: Let $T_i$ be a sequence of $l$ distinct terms of degree strictly less than $b$, then : $$ \left(\sum_{i=1}^l T_i\right) \cdot \left(\sum_{j=1}^m x_j^b \right) $$ Contains exactly $m\cdot l$ distinct terms

Proof by induction on $m$ :

• Base case $m=1$ : $$ \left(\sum_{i=1}^l T_i\right) \cdot x^b = \sum_{i=1}^l T_i\ x^b $$ Which clearly has $1 \cdot l$ distinct terms.
• Induction assuming true up to $m$, then : $$\left(\sum_{i=1}^l T_i\right) \cdot \left(\sum_{j=1}^{m+1} x_j^b \right) = \overbrace{\sum_{j=1}^m\sum_{i=1}^l T_i x_j^b}^{A} + \overbrace{x_{m+1}^b\sum_{i=1}^l T_i}^{B} $$ By induction we know that all the terms in $A$ are distinct and there are $m\cdot l$ of them. Now suppose toward contraction that there is one term in $B$ which is equivalent to one term in $A$, this means that there exist $j (\neq m+1)$ and two distinct $i,\ i'$ such that $T_i x_j^b = x_{m+1}^b T_{i'}$ which then implies that we can decompose $T_i = U x_{m+1}^b$ and $T_{i'} = V x_j^b$. However this shows that $T_i$ and $T_{i'}$ have at least degree $b$ which contradicts the assumption on the sequence $T_i$. Therefore all terms in $A$ and $B$ are distinct and there is a total of $(m+1)l$.

Let $n = b_{d-1}b_{d-2}...b_1b_0$ with $b_i\in \{0,1\}$ be the binary expansion of $n$. Define $D = \sum_{i=0}^{d-1} b_i$ and let the sequence $s_n(i)$ be "the index of the $i$-th '1' bit in $n$" so that $n = \sum_{i=1}^D 2^{s_n(i)}$. For instance : $n=11 = 1011_2,\ s_n(1)=0,\ s_n(2)=1,\ s_n(3) = 3$.

Claim $(x_1 + ... + x_m)^n\ (mod \ 2)$ has $m^D$ disctinct terms.

Proof:

We decompose $(x_1 + ... + x_m)^n\ (mod \ 2)$ according to Lemma 1 : $$ (x_1 + ... + x_m)^n\ (mod \ 2) = \prod_{i=1}^D \left(x_1^{2^{s_n(i)}} + ... + x_m^{2^{s_n(i)}}\right) $$ and now we do an induction on $D$ :

• Base case $D=1$ : Clearly $\left(x_1^{2^{s_n(1)}} + ... + x_m^{2^{s_n(1)}}\right)$ has $m^1$ distinct terms.
• Induction assuming true up to $D$, then : $$ \prod_{i=1}^{D+1} \left(x_1^{2^{s_n(i)}} + ... + x_m^{2^{s_n(i)}}\right) = \overbrace{\prod_{i=1}^D \left(x_1^{2^{s_n(i)}} + ... + x_m^{2^{s_n(i)}}\right)}^{C} \cdot \left(x_1^{2^{s_n(D+1)}} + ... + x_m^{2^{s_n(D+1)}}\right) $$ By assumption we know that $C$ has $m^D$ distinct terms. It is also clear that the degree of all terms is equal to $\sum_{i=1}^D 2^{s_n(i)} < 2^{s_n(D+1)}$. We can therefore apply Lemma 2 and conclude that the expression has exactly $m^D \cdot m = m^{D+1}$ distinct terms.