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

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$?

• Interesting! If we define $|s_n| = n$, then the polynomial $p_n$ is homogeneous of degree $2n-1$. In particular, if the conjecture is true, then there is some natural subset of the partitions of $2n-1$ into odd parts which is in bijection with the partitions of $n$ into powers of $2$. – James Cranch Jan 20 '14 at 23:17
• @JamesCranch: emperically, the partitions of $2n-1$ into odd parts that occur all have a number of parts which is one less than a power of $2$. For example, when $n=5$, the corresponding partitions of $9$ are $9$, $7+1+1$, $3+3+3$, and $3+1+1+1+1+1+1$. However, not all such partitions appear: $5+3+1$ is missing, and $7+3+1$ and $5+3+3$ are missing when $n=6$, while $9+3+1$ and $5+3+1+1+1+1+1$ are missing when $n=7$, for example. – Greg Martin Jan 21 '14 at 7:26
• Random remark: the partition $(2n-5) + 3 + 1$ never seems to occur. – Greg Martin Jan 21 '14 at 7:32
• Still considering the "special" partitions of $2n-1$ as given by the $p_n(s_1,\dots)$: let $N_{n,k}$ $(n\ge1,k\ge0)$ denote the number of "special" partitions of $2n-1$ into $2^{k+1}-1$ parts. Then $N_{n,0}=1$ for all $n\ge1$, and $N_{n,k}=0$ when $n<2^k$. Emperically, it seems that $N_{n,k} = \sum_{j=0}^k N_{n-2^k,j}$. If I'm not mistaken, the same recursion/initial values are satisfied by the number of ways to write $n$ as a sum of powers of $2$ where the largest element of the sum equals $2^k$. This might be a clue to the desired bijection.... – Greg Martin Jan 21 '14 at 7:44

## 3 Answers

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}$.

• So the terms that appear are exactly the terms where the exponents of the $s_n$, $n$ odd, add up to $2^k-1$ for some $k$ without cancellation. – Will Sawin Jan 21 '14 at 23:06
• @Will, yes, precisely. – Gjergji Zaimi Jan 21 '14 at 23:55
• Here is an involutive proof of the cancellation. As in the proof, let $(j_1,j_2,\ldots)$ encode a partition with $j_i$ parts of size $2^{i-1}$. If all the non-zero multiplicities are odd, do nothing. Otherwise, the sequence is of the form $(\ldots, 2a, a, \ldots, a, c, \ldots)$ where $2a$ is the first even multiplicity and $c\not =a$. Replace this subsequence with $(\ldots, 2c, c, \ldots, c, a, \ldots)$. If the $c$ in the first sequence is in position $r$ then both subsequences contribute $s_a^{2^{r-1}}s_c^{2^{r-1}}$. – Mark Wildon Jan 24 '14 at 10:45

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}$
• If you have a chance, can you please compute and post the inverse of the series in the denominator? – Benjamin Young Jan 21 '14 at 17:23
• I mean, the low order terms of it. I'm just assuming that this is an easy modification of what you've done already. – Benjamin Young Jan 21 '14 at 17:24
• Sure, up to degree 12, it's """1 + s_1^2*x + (s_3^2 + s_1^6)*x^3 + (s_5^2 + s_3^2*s_1^4)*x^5 + (s_7^2 + s_5^2*s_1^4 + s_3^4*s_1^2 + s_1^14)*x^7 + (s_9^2 + s_7^2*s_1^4 + s_3^6 + s_3^2*s_1^12)*x^9 + (s_11^2 + s_9^2*s_1^4 + s_5^4*s_1^2 + s_5^2*s_3^4 + s_5^2*s_1^12 + s_3^4*s_1^10)*x^11""" – James Cranch Jan 21 '14 at 17:28

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}