Skip to main content
deleted 2 characters in body
Source Link
Peter Mueller
  • 22.5k
  • 1
  • 75
  • 107

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

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.

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.

Source Link
Peter Mueller
  • 22.5k
  • 1
  • 75
  • 107

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.