22
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – James Cranch Jan 20 '14 at 23:17
  • 2
    $\begingroup$ @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. $\endgroup$ – Greg Martin Jan 21 '14 at 7:26
  • 1
    $\begingroup$ Random remark: the partition $(2n-5) + 3 + 1$ never seems to occur. $\endgroup$ – Greg Martin Jan 21 '14 at 7:32
  • 1
    $\begingroup$ 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.... $\endgroup$ – Greg Martin Jan 21 '14 at 7:44
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Will Sawin Jan 21 '14 at 23:06
  • $\begingroup$ @Will, yes, precisely. $\endgroup$ – Gjergji Zaimi Jan 21 '14 at 23:55
  • $\begingroup$ 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}}$. $\endgroup$ – Mark Wildon Jan 24 '14 at 10:45
1
$\begingroup$

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}$
$\endgroup$
  • $\begingroup$ If you have a chance, can you please compute and post the inverse of the series in the denominator? $\endgroup$ – Benjamin Young Jan 21 '14 at 17:23
  • $\begingroup$ I mean, the low order terms of it. I'm just assuming that this is an easy modification of what you've done already. $\endgroup$ – Benjamin Young Jan 21 '14 at 17:24
  • $\begingroup$ 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""" $\endgroup$ – James Cranch Jan 21 '14 at 17:28
1
$\begingroup$

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}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.