Densities of the reciprocals of polynomials in binary power series

Question

Define the density $[f(z)]$ of a power series $f(z) = f_0+f_1z+f_2z^2+\cdots$ in the binary power series ring $F_2[[z]]$ as the natural density of the set $E_f := \{i : f_i = 1\}.$

$D := \{[f^{-1}] : 0 \in E_f\}$ is the set of densities of the reciprocals of the polynomials with non-zero constant term.

I think every arithmetic sequence has the form $E_{f^{-1}}$ where $f(z)$ is a polynomial with $f(0)=1$

1) Any insight into whether $D$ is nowhere dense or not ? What are the accumulation points of $D$ ?

2) Any insight into upper bounds for $D$ ? $\inf(D)=0$, $\sup(D)=1$

I remember some of this brought up in Cooper & Bryant's "Reciprocals Of Binary Power Series" lead by questions on the parity of the partition function and among other things the densities of the reciprocals of polynomials.

Answer 1

I claim that all the fractions $\frac{1}{2t}$ are accumulation points of densities.

This follows from $2$ claims. Recall that $a(x)$ of degree $m$ over $F_2$ is primitive if $a(x)$ is a factor of $x^{2^m-1}+1$ but not $x^N+1$ for any smaller $N.$

• If $a(x)$ is a primitive polynomial of degree $m$ over $F_2$ then $\frac{1}{a(x)}$ has density $\frac{2^{m-1}}{2^m-1}.$

• The density of $\frac1{a(x^t)}$ is $\frac1t$ times the density of $\frac1{a(x)}.$

It will help to consider all proper ratios of polynomials $\frac{n(x)}{a(x)}$ over $F_2$ where $a(x)$ should have constant term $1$ and greater degree than $n(x).$ We do not insist that the ratio be in reduced form. Every such ratio, expressed as a series, is periodic, so the densities are rational numbers.

---

OPTIONAL COMPUTATIONAL DIGRESSION This computation wasn't as helpful as I expected. But I preserve it for what it is worth

There are $2047$ monic polynomials of positive degree $11$ or less with constant term $1.$ Their reciprocal power series enjoy $149$ distinct densities :

There is an accumulation point at $0$ at also one at $\frac12.$ I don't visually see any other strong candidates from that data.

Of the $149$ densities, $99$ are in the interval $[\frac37,\frac6{11}].$ Here is a graph:

Curious fact: At least up to $k=6$, the density of$\frac1{1+x+x^{2^k}}$ is $\frac{3^k-1}{4^k-1}.$

END OF DIGRESSION

---

Let $$g_{\infty}(x)=\frac1{1+x}=1+x+x^2+\cdots$$ Then

$$\frac1{1+x^N}=g_{\infty}(x^N)$$ has density $\frac1{N}.$

This is the unique way to get the largest possible density, $1.$ It also shows that $0$ is an accumulation point of densities.

Define $g_N(x)=\frac{1+x^N}{1+x}=1+x+x^2+\cdots+x^{N-1}.$ then $$\frac1{g_N(x)}=(1+x)(1+x^N+x^{2N}+\cdots)$$ has density $\frac2{N}.$

This gives the second highest density in the small computation above, $\frac1{1+x+x^2}$ has density $\frac23.$ I'd wildly conjecture that these are the only reciprocal polynomials giving densities in $[\frac23,1].$

Also, $$\frac1{g_N(x^j)}=(1+x^j)(1+x^{Nj}+x^{2Nj}+\cdots)$$ has density $\frac{2}{Nj}.$

This provides the only occurrences of the smallest densities in the modest computation above $1/11, 1/10, 1/9, 1/8, 2/15, 1/7, 1/6, 2/11.$

---

To justify the two claims above I will first give two examples and then discuss the general situation.

Let $a(x)$ be a polynomial of degree $4$ with constant term $1.$ There are $2^4-1=15$ proper rational functions $\frac{n(x)}{a(x)}.$ Of them, $8$ have numerator of degree $3$, call them tails. Also, $8$ have constant term $1$, call them heads. There are 4 that are both heads and tails. Here are paths from each tail to its matching head. The rule is that $$\frac{xn(x)}{a(x)}\rightarrow \frac{n(x)}{a(x)}.$$ The strings on the left will be used later.

$$0001 \hspace{1in} {\frac {{x}^{3}}{a(x)}}\rightarrow{\frac {{x}^{2}}{a(x)}}\rightarrow{\frac {x}{a(x)}}\rightarrow\frac1{a(x)} \tag{A}$$

$$001 \hspace{1in}{\frac {{x}^{2}+{x}^{3}}{a(x)}}\rightarrow{\frac {{x}+x^2}{a(x)}}\rightarrow{ \frac {1+x}{a(x)}}\tag{B}$$

$$01 \hspace{2in}{\frac {x+{x}^{3}}{a(x)}}\rightarrow{\frac {1+{x}^{2}}{a(x)}}\tag{C}$$

$$01 \hspace{1in}{\frac {x+{x}^{2}+x^3}{a(x)}}\rightarrow{\frac {1+x+{x}^{2}}{a(x)}}\tag{D}$$

$$1 \hspace{3in}{\frac {1+{x}^{3}}{a(x)}}\tag{E}$$

$$1 \hspace{3in}{\frac {1+x+{x}^{3}}{a(x)}}\tag{F}$$

$$1 \hspace{3in}{\frac {1+x^2+{x}^{3}}{a(x)}}\tag{G}$$

$$1 \hspace{3in}{\frac {1+x+x^2+{x}^{3}}{a(x)}}\tag{H}$$

These paths are independent of $a(x).$ Then each head is connected to a tail according to a rule which does depend on $a(x).$ The result will be one or more cycles, some perhaps of length $1.$ To find the successor of $\frac{n(x)}{a{x}}$ take $n(x)+a(x)$, which will have degree $4$ and constant term $0,$ say $n(x)+a(x)=xn'(x).$ Then $$\frac{n(x)}{a(x)}\rightarrow \frac{n'(x)}{a(x)}.$$

Here is the results for $a(x)=1+x+x^3+x^4$ (on the left) and for $a(x)=1+x+x^4$ (on the right)

Starting on the left, the cycle $AGF$ (started at the head of $A$) with corresponding string $1\, 1\, 1\, 000$ (spaces for clarity but optional) tells us that $(1+x+x^2)(1+x+x^3+x^4)=1+x^6$ so $$\frac{1}{1+x+x^3+x^4}=\frac{1+x+x^2}{1+x^6} $$ with density $\frac36.$

The cycle $HD$ with string $101$ tells us that $(1+x^2)(1+x+x^3+x^4)=(1+x+x^2)(1+x^4)$ so $$\frac{1+x+x^2}{1+x+x^3+x^4}=\frac{1+x^2}{1+x^4}$$ with density $\frac24.$

Moving to the right, the polynomial $1+x+x^4$ is seen to create one big cycle with string $1\,1\,1\,1\,01\,01\,1\,001\,000$ this tells us that $(1+x+x^2+x^3+x^5+x^7+x^8+x^{11} )(1+x+x^4 )=1+x^{15}$ so $$\frac1{1+x+x^4}=\frac{1+x+x^2+x^3+x^5+x^7+x^8+x^{11}}{1+x^{15}}$$ with density $\frac8{15}.$

Because $1+x+x^4$ is primitive, it doesn't divide $1+x^N$ for any positive $N \lt 15.$ Accordingly the cycle, whatever it is, uses all eight strings and has density $\frac8{15}$.

Note that we can discover $a(x)$ as soon as we see one link so $C \rightarrow B$ means $(1+x^2)+a(x)=x(x^2+x^3)=x^3+x^4$ meaning $a(x)=1+x^2+x^3+x^4.$ That might or might not make a single cycle so not every way to link the strings into a single cycle comes from a polynomial.

---

In general, for a primitive polynomial $a(x)$ of degree $m,$ the density of the reciprocal is $$\frac{2^{m-1}}{2^m-1}$$ because in computing $\frac1{a(x)}$ every non-zero proper ratio $\frac{n(x)}{a(x)}$ is seen as a remainder before the period is done.

Answer 2

I felt this synopsis of Aaron Meyerowitz's post with Pietro Majer's comment and my own might be useful, possibly even insightful, in characterizing $D$ even further.

$A(z)=\sum_{0}^{\infty} a_iz^i\in \Bbb F_2[[z]]$ is called periodic by any of the following equivalent definitions :

1. For some $n\in\Bbb N,B(z)\in\Bbb F_2[z]$ with $deg(B(z))<n$ we have $$A(z)*(1+z^n)=B(z)$$ (The period $d$ of $A(z)$ is the smallest possible value for $n$ while $k$ is the exact number of terms in $B(z)$)

2. $E_A$ is the union of $k$ distinct arithmetic sequences of the same common difference $n$.

3. $(a_i)_i^\infty$ is a periodic sequence of period $d$, which divides $n$, and has exactly $k$ 1s up to its first $n$ coefficients.

   • Therefore, there are exactly $2^n$ periodic power series whose period divides $n$. Each periodic power series whose period divides $n$ has the form $\frac{B(z)}{1+z^n}$ and has density $\frac{k}{n}$ where $k$ is the number of nonzero coefficients in $B(z)$. Of these the polynomial reciprocals are the reciprocals of the non-constant factors of $1+z^n$ and thus each of the form $\frac{b(z)}{1+z^n}$ where $b(z)$ is a proper divisor of $1+z^n$.

   • Therefore $D=${$\frac{k}{n}:$ $n\in\Bbb N,$ $b(z)$ has exactly $k$ terms and properly divides $1+z^n$} as each invertible polynomial $f(z)$ divides the characteristic polynomial $\psi_m(z)=z+z^{2^m}$ of its splitting field $\Bbb F_{2^m}$ where $m = deg(f(z))$ when $f$ is irreducible over $\Bbb F_2$.

Claim (Meyerowitz) : Given $m\in\Bbb N$ there exists a $2^{m-1}$ term polynomial $b(z)$ that divides $1+z^{2^m-1}$.

Assuming this claim then $\frac{2^j}{c(2^k-1)}\in D$ for all $c,j,k\in\Bbb N$ with $j<k$ because the $\Bbb F_2[[z]]$ ring endomorphism $\phi_n : f(z)\rightarrow f(z^n)$ has the obvious property $$[\phi_n(f(z))]=\frac{1}{n}*[f(z)]$$ for all binary power series $f(z)$.