4

Let $m$ and $k<2^m$ be nonnegative integers and let $\alpha \in \mathbb{F}_{2^m} - \mathbb{F}_2$ such that $$ \left\{ \begin{array}{l} \alpha = \alpha^k \\ \alpha + 1 = (\alpha + 1)^k \end{array} \right.$$ Does it imply that $k$ is a power of $2$ ?

What lead me to this question is the following problem:

Does the polynomial $X + \alpha Y + (\alpha + 1) Z$ divides $$ \phi_k(X,Y,Z) =\frac{X(Y^k+Z^k)+Y(X^k+Z^k)+Z(X^k+Y^k)}{(X+Y)(Y+Z)(Z+X)} $$ if $k$ is not a power of 2 ?

It is equivalent to ask if $\phi_k(\alpha Y + (\alpha +1)Z, Y, Z)=0$ if and only if $k=2^i$.

Florian Caullery
  • 43

1 Answers1

10

The answer is negative. The smallest counterexample I found (that uses the minimal $k$ for the chosen $\alpha$) is $m=9$, $k=74$.

Consider the polynomial $$ p(x)=x^9+x+1\in\Bbb{F}_2[x]. $$ Let $\alpha$ be a zero of $p(x)$. We see that $$ \alpha^{72}=(\alpha^9)^8=(\alpha+1)^8=\alpha^8+1, $$ so $$ \alpha^{73}=\alpha(\alpha^8+1)=\alpha^9+\alpha=p(\alpha)+1=1. $$ Because $\alpha\neq1$ and $73$ is a prime, we can conclude that $\alpha$ is of order $73$. Then $m=9$ is the smallest integer with the property $73\mid 2^m-1$, so $[\Bbb{F}_2(\alpha):\Bbb{F}_2]=9$. We can thus conclude that $p(x)$ is irreducible.

But we also have that $$ \alpha+1=\alpha+1+p(\alpha)=\alpha^9. $$ Thus we can conclude that $\alpha+1$ is also a $73$rd root of unity.

Therefore both $\alpha$ and $\alpha+1$ satisfy the equation $x=x^{74}$.

How to:

As also observed by Pablo Rotondo a way of finding solutions is the following. A solution $\alpha$ has to be a zero of both $f_k(x)=x^k+x$ and $g_k(x)=(x+1)^k+(x+1)$. This suggests a search strategy (if you have a suitable CAS available): try to find a $k$ such that $\gcd(f_k(x),g_k(x))$ is non-trivial in the sense that it has zeros other than those in the prime field. To eliminate "cheating cases" (where the smallest $k$ that works for a particular $\alpha$ is a power of two) Pablo had the nice idea to make sure that $k-1$ is not a multiple of any $2^n-1, n>1$ (I missed that trick).

I used this method (without the trick of eliminating the unwanted solutions) to find my counterexample. My goal was to keep $m$ as small as possible meaning that for example I skipped $m=5,7$ altogether as those give Mersenne primes forcing $k$ to be a power of two. I used Mathematica. The presented solution is a post-discovery derivation/explanation of that solution. Streamlined as much as I could manage.

Jyrki Lahtonen
  • 133,153