Number of Terms in Polynomial 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)

 A: 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$.
A: 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.

