# Is the primitive element of an extension of a finite field expressible as a linear combination of adjoined elements?

Suppose $F$ is a field, and $\alpha,\beta$ are algebraic, separable elements over $F$.

If $F$ is infinite, the proof of the primitive element theorem gives some $c\in F$ such that $F(\alpha,\beta)=F(\alpha+c\beta)$. The is done by choosing $c$ to be distinct from various ratios of form $(\alpha-\alpha_i)/(\beta-\beta_j)$ where $\alpha_i$ and $\beta_j$ are other roots of the minimal polynomials of $\alpha$ and $\beta$ over $F$.

If $F$ is finite, is it still possible to ensure there is a primitive element for $F(\alpha,\beta)$ of form $\alpha+c\beta$ for some $c\in F$?

Every proof always treats this case by using the result that $F(\alpha,\beta)^\times$ is cyclic.

No. This is false. Here is a counter-example. Let $\alpha$ be a generator of $\mathbf F_{2^6}$ with minimal polynomial $$p=x^6 + x^5 + x^3 + x^2 + 1,$$ and let $\beta$ be a generator of $\mathbf F_{2^{10}}$ with minimal polynomial $$q=x^{10} + x^9 + x^8 + x^3 + x^2 + x + 1$$ over $\mathbf F_2$. Then $\mathbf F_2(\alpha,\beta)=\mathbf F_{2^{30}}$ since the least common multiple of $6$ and $10$ is $30$. However, $\alpha+c\beta$ does not generate this field extension over $\mathbf F_2$ for no value of $c\in\mathbf F_2$. Indeed, $c$ can be $0$ or $1$. Of course, $\alpha=\alpha+0\beta$ does not generate $\mathbf F_{2^{30}}$. The minimal polynomial of $\alpha+\beta$ over $\mathbf F_2$ is $$x^{15} + x^{13} + x^8 + x^5 + x^2 + x + 1.$$ Hence, $\mathbf F_2(\alpha+\beta)=\mathbf F_{2^{15}}$, and $\alpha+\beta$ does not generate $\mathbf F_{2^{30}}$.

Here are some words of justification. It is a straightforward, but tedious, matter to check that the polynomials $p$ and $q$ are indeed irreducible over $\mathbf F_2$, or look for them in the Peterson table. What is interesting about the polynomials $p$ and $q$ is that $p$ divides the polynomial $x^8+x+1$, and $q$ divides $x^{32}+x+1$ (these polynomials came also up in this post as a priori surprising reducible polynomials in $\mathbf F_2[x]$). Indeed, one has $$(x^2+x+1)p=x^8+x+1,$$ and $$(x^{22} + x^{21} + x^{19} + x^{18} + x^{16} + x^{14} + x^{13} + x^{12} + x^{11} + x^6 + x^4 + x^2 + 1)q=x^{32}+x+1$$ It follows that $$\alpha^8=\alpha+1 \quad\text{and}\quad \beta^{32}=\beta+1.$$

Let us now prove that $\alpha+\beta$ does not generate $\mathbf F_{2^{30}}$ over $\mathbf F_2$. Let $\phi$ be the Frobenius morphism $\phi(x)=x^2$ on $\mathbf F_{2^{30}}$. The Galois group of $\mathbf F_{2^{30}}$ over $\mathbf F_2$ is cyclic of order $30$ and generated by $\phi$. In particular, $\phi^{15}$ is not equal to the identity. However, we will show that $$\phi^{15}(\alpha+\beta)=\alpha+\beta.$$ Indeed, $$\phi^{15}(\alpha)=\phi^3(\alpha)=\alpha^{2^3}=\alpha^8$$ since $\phi^6$ is equal to the identity on $\mathbf F_{2^6}$ Similarly, $$\phi^{15}(\beta)=\phi^5(\beta)=\beta^{2^5}=\beta^{32}$$ since $\phi^{10}$ is the identity on $\mathbf F_{2^{10}}$. Therefore, $$\phi^{15}(\alpha+\beta)=\phi^{15}(\alpha)+\phi^{15}(\beta)=\alpha^8+\beta^{32}=\alpha+1+\beta+1=\alpha+\beta,$$ by what we have seen above. Hence, $\alpha+\beta$ belongs to the fixed field of the subgroup $\langle\phi^{15}\rangle$ of the Galois group of $\mathbf F_{2^{30}}$, i.e., $$\alpha+\beta\in \mathbf F_{2^{15}}.$$ This proves that $$\mathbf F_{2}(\alpha+\beta)\subsetneq\mathbf F_2(\alpha,\beta).$$

I found the particular example here using a little sage program:

p=2
d=2*3*5
m=2*3
n=2*5
q=p^d
F=GF(q,'c')
c=F.gen()
a=c^((q-1)/(p^m-1))
b=c^((q-1)/(p^n-1))
exponents_for_nongenerators=[(i,j) for i in range(1,p^m-1) for j in range (1,p^n-1) if (a^i).minimal_polynomial().degree()==m and (b^j).minimal_polynomial().degree()==n and (a^i+b^j).minimal_polynomial().degree()!=d]
(i,j)=exponents_for_nongenerators[0]
print (a^i).minimal_polynomial(), (b^j).minimal_polynomial(), (a^i+b^j).minimal_polynomial()


I do not think that much simpler examples exist, degree-wise speaking.