# Polynomials over $\mathbb F_2$ without zeros in $\mathbb F_2$ having an inverse series with support of large density.

Does there exist a sequence $A_n=A_n(x)\in\mathbb F_2[x]$ over the field $\mathbb F_2$ of two elements (represented by $0$ and $1$) such that $A_n(0)=A_n(1)=1$ and the inverse series $1/A_n=\sum_{j=0}^\infty \alpha_{n,j}x^j\in \mathbb F_2[[x]]$ have supports with densities $\delta_n=\lim_{k\rightarrow\infty} \frac{\alpha_{n,0}+\alpha_{n,1}+\dots+\alpha_{n,k-1}}{k}$ converging to $1$?

A positive answer to this question would give a positive answer to question [Sum of densities of support of $A$ and $A^{-1}$ for $A=1+\dots\in \mathbb F_2[[x]]$ by considering $\frac{A_n(x^2)}{1+x}$.

The highest possible density for polynomials of degree $\leq 16$ is $\frac{2}{3}$, achieved by $1+x+x^2$.

• Nice question. How de we know that the density $\delta_n$ exists ?
– Joël
Feb 13, 2013 at 20:01
• @Joel: Because the expansion is periodic. Feb 13, 2013 at 21:30
• I know of one paper where these reciprocals over ${\bf F}_2$ are studied, MR2281861 (2007h:11015) Cooper, Joshua N.; Eichhorn, Dennis; O'Bryant, Kevin; Reciprocals of binary series, Int. J. Number Theory 2 (2006), no. 4, 499–522. Feb 13, 2013 at 22:14
• Here is an empirical observation. I computed the density for the power series $1/P$ where $P$ runs through the irreducible polynomials of degree $n$ over $\mathbf{F}_2$. When $n$ is prime, the maximal density seems to be exactly $2^{n-1}/(2^n-1)$ (up to $n=17$). I don't know how one would go to prove that. Feb 14, 2013 at 14:59
• Further computations show that this observation breaks down for $n=23$. However this is true when we restrict to primitive irreducible polynomials, as explained by Peter Müller in his answer. Feb 14, 2013 at 21:09

This is not an answer, rather a possible suggestion on how to deal with irreducible polynomials $A(x)$: Let $A(x)\in\mathbb F_2[x]$ be irreducible of degree $n$. Then $$A(x)=\prod_{i=0}^{n-1}(1+\lambda^{2^i}x)$$ for some $\lambda\in\mathbb F_{2^n}$. The partial fraction decomposition and geometric series yield $$\frac{1}{A(x)}=\sum_{i=0}^{n-1}\frac{\alpha^{2^i}}{1+\lambda^{2^i}x} = \sum_{m=0}^\infty\sum_{i=0}^{n-1}\alpha^{2^i}(\lambda^{2^i}x)^m = \sum_{m=0}^\infty T(\alpha\lambda^m)x^m,$$ where $\alpha=\lambda/f'(1/\lambda)$ and $T$ is the trace map from $\mathbb F_{2^n}$ to $\mathbb F_2$.

Note that the power series is periodic with period $e$, where $e$ is the multiplicative order of $\lambda$. Thus if $U$ is the subgroup of order $e$ of $\mathbb F_{2^n}^\star$, then the density of $1$'s is the number of $u\in U$ with $T(\alpha u)=1$ divided by $\lvert U\rvert$.

An easy case is when $e=2^n-1$, so $U=\mathbb F_{2^n}^\star$. Half of the elements of $\mathbb F_{2^n}$ have trace $0$, so the density of $1$'s is $2^{n-1}/(2^n-1)$.

So when not only $n$ is prime, but even $2^n-1$ is prime, then we have this case and the density is only slightly bigger than $1/2$.

The general case seems to be more challenging. It is always difficult to relate an additive function like the trace map with subgroups of the multiplicative group of fields.

• The size of the set of $u$ in the group of order $e$ of $\mathbb{F}_{2^n}^*$ with $T(\alpha u) = 1$ is related to the number of points of the curve $y^2+y = \alpha x^d + \beta$, where $T(\beta)=1$ and $d = (2^n-1)/e$, so for large $e$ (i.e. small $d$) the Weil bound should be enough to say that about half of the $u$'s satisfy $T(\alpha u) = 1$. Feb 14, 2013 at 19:30
• Nice! I pushed the computations somewhat further and the empirical observation seems to break down : for $n=23$ and $e=178481$ the density can be $0.506\ldots$ which is $>2^{n-1}/(2^n-1)$... Feb 14, 2013 at 21:01
• Another observation, when $n$ is prime and $2^n-1$ is composite, the density doesn't depend on $e$ alone but really depends on the chosen irreducible polynomial. Feb 14, 2013 at 21:05
• Actually, the upper bound I get is independent of $d$. Sauf erreur, it is $2^{n-1}/(2^n-1) + 1/2^{2+n/2}$. Feb 14, 2013 at 21:33
• @Felipe : for $n=23$ this upper bound would be approximately 0.500086, which would be $<.506$. Anyway, numerically it seems true that the larger $e$, the closer to $1/2$ are the possible densities. This is consistent with the argument using the Weil bound that you suggest in your first comment. Feb 14, 2013 at 21:48

If you do not require, $f(1)=1$, then degree 17 and 18 start to beat 2/3, and there is an asymptote, from the data.

6857 t^17 + t^16 + t^2 + 1
6875 t^17 + t^15 + t + 1
7015 t^18 + t^16 + t + 1
6993 t^18 + t^17 + t^2 + 1


I did not compute, the asymptotic density, only to $10^4$. It indicates, there are 7015 nonzero terms in $1/(t^{18}+t^{16}+t+1)$, when expanding to $10^4$ terms over $F_2[[t]]$.

Going higher, one finds in these forms, here $10^5$ terms

76971 t^34 + t^32 + t + 1
82477 t^66 + t^64 + t + 1
73307 t^98 + t^96 + t + 1


The pattern, should be apparent, I determine here to $10^6$ terms.

428572 t^4 + t^2 + t + 1
523810 t^6 + t^4 + t + 1
616445 t^10 + t^8 + t + 1
699634 t^18 + t^16 + t + 1
769173 t^34 + t^32 + t + 1
824699 t^66 + t^64 + t + 1
867949 t^130 + t^128 + t + 1
901146 t^258 + t^256 + t + 1
929281 t^514 + t^512 + t + 1
951431 t^1026 + t^1024 + t + 1


In the last example, the computation of actual density, should be superior.

• The above answer, is only a comment, but I have no "experience" in the system to allow me. Feb 13, 2013 at 22:07
• Your examples have all 1 as a root. In this case, one can take $1+t$ which has only $1$'s. Feb 14, 2013 at 8:34