5
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Nice question. How de we know that the density $\delta_n$ exists ? $\endgroup$
    – Joël
    Feb 13, 2013 at 20:01
  • 1
    $\begingroup$ @Joel: Because the expansion is periodic. $\endgroup$ Feb 13, 2013 at 21:30
  • $\begingroup$ 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. $\endgroup$ Feb 13, 2013 at 22:14
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 14, 2013 at 14:59
  • $\begingroup$ 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. $\endgroup$ Feb 14, 2013 at 21:09

2 Answers 2

5
$\begingroup$

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 \begin{equation} A(x)=\prod_{i=0}^{n-1}(1+\lambda^{2^i}x) \end{equation} for some $\lambda\in\mathbb F_{2^n}$. The partial fraction decomposition and geometric series yield \begin{equation} \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, \end{equation} 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.

$\endgroup$
6
  • 3
    $\begingroup$ 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$. $\endgroup$ Feb 14, 2013 at 19:30
  • $\begingroup$ 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)$... $\endgroup$ Feb 14, 2013 at 21:01
  • $\begingroup$ 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. $\endgroup$ Feb 14, 2013 at 21:05
  • $\begingroup$ 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}$. $\endgroup$ Feb 14, 2013 at 21:33
  • $\begingroup$ @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. $\endgroup$ Feb 14, 2013 at 21:48
2
$\begingroup$

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.

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

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.