4

My question is: is the following statement true? If so, how might I go about proving it?

Let $m$ be an integer not less than 1, let $F = GF(2^{6m})$, and let $L = GF(2^{2m})$. Let $\gamma$ be a primitive element of $L$, and let $\beta \in F$ be such that $\beta^3 = \gamma$. If $\phi_a(x) = c_0x^{6m}+c_1x^{6m-1}+...+c_{6m-1}x+c_{6m}$ is the minimal polynomial of an element $a \in \beta L$, then $$c_i = 0 \hspace{5mm} \text{if $i \not\equiv 0 \pmod{3}$}$$

727
  • 1,607

1 Answers1

1

The following sketch is the best I can muster right away. It probably isn't the cleanest route to the destination, but it leads to a proof.

Assume that $z=\gamma^j$ is an arbitrary non-zero element of $L$. Then

  • $\beta z=\beta^{1+3j}$, and
  • $(\beta z)^3=\gamma^{1+3j}\in L$.

Let $\phi(x)$ be the minimal polynomial of $\gamma^{1+3j}\in L$. Then

  • $a=\beta z$ is a zero of the polynomial $\phi(x^3)$, and
  • the coefficients of terms of $\phi(x^3)$ of degree $\not\equiv0\pmod3$ are all zero.

This proves your observation, if we can show that $\phi(x^3)$ has the correct degree ($=\deg\phi_a(x)$). Because $\deg\phi(x)$ is always a factor of $2m$, we are done, if we have that extra bit of information that $\deg\phi_a(x)=6m$.

Even if that is not the case we can make the following deductions (leaving them sketchy as per your request):

  • We have $\deg\phi(x)$ is equal to the degree of the extension $GF(2)[a^3]$ over $GF(2)$.
  • Similarly $\deg\phi_a(x)$ is equal to the degree of the extension $GF(2)[a]$ over $GF(2)$.
  • Here $GF(2)[a^3]$ is a subfield of $L$.
  • But $GF(2)[a]$ is not a subfield of $L$. It is a subfield of $F$ though.
  • Clearly $GF(2)[a^3]$ is a subfield of $GF(2)[a]$.
  • Putting these bits together shows that $GF(2)[a]$ is a cubic extension of $GF(2)[a^3]$.
  • Therefore $\deg\phi_a(x)=3\deg\phi(x)$, and the claim follows as above.

The next to last bullet is a bit subtler than the rest. Remember that the cardinality of a subfield of $F$ determines it uniquely.

Jyrki Lahtonen
  • 133,153
  • Unfortunately we cannot assume that $\phi_a(x)$ always has degree $6m$, for example it has happened to me in some of the iterations that the minimal polynomials for $m=1$ and $m=2$ were the same ($x^6+x^3+1$).

    Nevertheless, there is clearly a way around this as you have shown, thanks for the help!

     – 727 May 25 '15 at 20:52
  • 1
    Hi Jyrki,

    sorry, but I can't see why $GF(2)[a]$ is necessarily a cubic extension of $GF(2)[a^3]$. I can see how using the cardinalities of the subfields would work if $L$ was a subfield of $GF(2)[a]$, but that is not necessarily true.

    It's easy to show that $GF(2)[a]$ either quadratic or cubic as an extension of $GF(2)[a^3]$. I thought that perhaps I could arrive at a contradiction by assuming that $a$ satisfies a polynomial of degree 2 with coefficients in $GF(2)[a^3]$, but I've had no luck.

    How can I try to understand this?

     – 727 May 29 '15 at 06:57
  • 1
    @Luc : I thought it would go as follows. Let $k$ be the degree of $a^3$ over $GF(2)$, and $\ell$ the degree of $a$. Because $a^3\in L$ we know that $k\mid 2m$. Because $a^3\in GF(2)[a]$ we have $k\mid\ell$. Because $a\in F\setminus L$ we know that $\ell\nmid 2m$ but also $\ell\mid 6m$. Clearly $\ell\le 3k$, so the only possibilities are $\ell=2k$ and $\ell=3k$. But if $\ell=2k$, then $\ell\mid 4m$. If $\ell$ is a factor of both $4m$ and $6m$ then $\ell$ is also a factor of $2m$, which is a contradiction. – Jyrki Lahtonen May 29 '15 at 07:45