Number of terms in certain polynomials over $\mathbb{F}_2$

Question

I raised this question in my answer to On the rank of a matrix $S$ with coefficients in $\mathbb F_{2^m}$. Let $s_1,s_3,s_5,\dots$ be indeterminates over the field $\mathbb{F}_2$, and recursively set $s_{2n}=s_n^2$, with $s_0=1$. Let \begin{eqnarray*} F(x) & = & \frac{\sum_{n\geq 1} s_{2n-1}x^n}{\sum_{n\geq 0} s_{2n}x^n}\\ & = & \sum_{n\geq 0} p_n(s_1,s_3,\dots)x^n. \end{eqnarray*} Is it true that the number of terms of the polynomial $p_n(s_1,s_3,\dots)$ is equal to the number of ways to write $n$ as a sum of powers of 2, without regard to order? For instance, the number of terms of $p_5$ is four, corresponding to $4+1=2+2+1=2+1+1+1=1+1+1+1+1$. A bijective proof would be especially interesting. Is there a generalization to $\mathbb{F}_p$?

Answer 1

The claim is true. Lets start by simplifying the expression as follows: $$x\left(1+\frac{1}{1+s_1x+s_2x^2+s_3x^3+\cdots}\right)=\frac{\sum_{n\geq 1}s_{2n-1}x^{2n}}{\sum_{n\geq 0} s_{2n} x^{2n}}.$$ This follows because $\sum_{n\geq 0}s_{2n}x^{2n}=\left(\sum_{n\geq 0}s_nx^n\right)^2$, and some basic manipulations over $\mathbb F_2$.

So we are interested in the coefficient of $x^{2n-1}$ in $$1+\frac{1}{1+s_1x+s_2x^2+\cdots}=\left(\sum_{n\geq 0}s_nx^n\right)+\left(\sum_{n\geq 0}s_nx^n\right)^2+\left(\sum_{n\geq 0}s_nx^n\right)^3+\cdots,$$ but by taking binary expansions we see that each term is of the form $$\left(\sum_{n\geq 0}s_{2^{i_1}n}x^{2^{i_1}n}\right)\cdots \left(\sum_{n\geq 0}s_{2^{i_k}n}x^{2^{i_k}n}\right),$$ where $i_1,i_2,\dots,i_k\geq 1$. It follows that the terms in the coefficient of $x^{m}$ correspond exactly to the solutions of $m=j_1+2j_2+\cdots 2^rj_{r+1}$. The ones that appear with a nonzero coefficient in $\mathbb F_2$ are precisely the ones where the $j_1,j_2,\dots$ are all odd. So the number of terms in $p_n$, with your notation, is the number of ways we can write $$2n-1=\sum_{r= 0}^k (2i_r+1)2^{r}$$ for some k. This is the same as $$n=2^k+\sum_{r= 0}^k i_r 2^r$$ which gives exactly the number of ways to partition $n$ as powers of $2$. For example when $n=6$, we can write $11$ as $1+10, 1+6+4, 5+6, 5+2+4, 9+2,11$ each corresponding to the terms in $p_6=s_1s_5^2+s_1s_3^2s_1^4+s_5s_3^2+s_5s_1^2s_1^4+s_9s_1^2+s_{11}$.

Answer 2

This is not really an answer, just a lengthy comment. I worked out some coefficients of this power series; they might be of use to others. (More are available on demand).

• $s_1x$
• $(s_3 + s_1^3)x^2$
• $(s_5 + s_3s_1^2)x^3$
• $(s_7 + s_5s_1^2 + s_3^2s_1 + s_1^7)x^4$
• $(s_9 + s_7s_1^2 + s_3^3 + s_3s_1^6)x^5$
• $(s_{11} + s_9s_1^2 + s_5^2s_1 + s_5s_3^2 + s_5s_1^6 + s_3^2s_1^5)x^6$
• $(s_{13} + s_{11}s_1^2 + s_7s_3^2 + s_7s_1^6 + s_5^2s_3 + s_3^3s_1^4)x^7$
• $(s_{15} + s_{13}s_1^2 + s_9s_3^2 + s_9s_1^6 + s_7^2s_1 + s_5^3 + s_5^2s_1^5 + s_5s_3^2s_1^4 + s_3^4s_1^3 + s_1^{15})x^8$
• $(s_{17} + s_{15}s_1^2 + s_{11}s_3^2 + s_{11}s_1^6 + s_7^2s_3 + s_7s_5^2 + s_7s_3^2s_1^4 + s_5^2s_3s_1^4 + s_3^5s_1^2 + s_3s_1^{14})x^9$
• $(s_{19} + s_{17}s_1^2 + s_{13}s_3^2 + s_{13}s_1^6 + s_9^2s_1 + s_9s_5^2 + s_9s_3^2s_1^4 + s_7^2s_5 + s_7^2s_1^5 + s_5^3s_1^4 + s_5s_3^4s_1^2 + s_5s_1^{14} + s_3^6s_1 + s_3^2s_1^{13})x^{10}$
• $(s_{21} + s_{19}s_1^2 + s_{15}s_3^2 + s_{15}s_1^6 + s_{11}s_5^2 + s_{11}s_3^2s_1^4 + s_9^2s_3 + s_7^3 + s_7^2s_3s_1^4 + s_7s_5^2s_1^4 + s_7s_3^4s_1^2 + s_7s_1^{14} + s_3^7 + s_3^3s_1^{12})x^{11}$
• $(s_{23} + s_{21}s_1^2 + s_{17}s_3^2 + s_{17}s_1^6 + s_{13}s_5^2 + s_{13}s_3^2s_1^4 + s_{11}^2s_1 + s_9^2s_5 + s_9^2s_1^5 + s_9s_7^2 + s_9s_5^2s_1^4 + s_9s_3^4s_1^2 + s_9s_1^{14} + s_7^2s_5s_1^4 + s_5^4s_1^3 + s_5^2s_3^4s_1 + s_5^2s_1^{13} + s_5s_3^6 + s_5s_3^2s_1^{12} + s_3^4s_1^{11})x^{12}$

Answer 3

As an answer to Greg Martins comments;

There is a natural injection from a partition of $n$ with parts that are powers of 2, to partitions of $2n-1$ where all parts are odd.

The mapping $(p_1,p_2,\dotsc,p_l) \mapsto (2p_1-1,2p_2-1,\dotsc,2p_l-1,1,1,\dotsc,1)$, where the number of ones in the end are sufficiently many, is such an injection.

I leave it as an exercise to the reader to prove that this is indeed an injection, but as a hint, the following Mathematica code implements the map above, and the inverse.

TheMapping[part_] := Module[{len},
    len = Length[part];
    Reverse@Sort@Flatten@Append[2*part - 1, ConstantArray[1, len - 1]]
];

TheMappingInverse[part_] := Module[{n, part2, p},
    n = (Total[part] + 1)/2;
    part2 = (part + 1)/2;
    p = First@Flatten@Position[Accumulate[part2], n];
    Return[part2[[;; p]]];
];

Example usage:

TheMapping[{8, 2, 1, 1}] == {15, 3, 1, 1, 1, 1, 1}
TheMappingInverse[{15, 3, 1, 1, 1, 1, 1}] == {8, 2, 1, 1}