# Dependence of algebraic elements in a finite field

Lets work over the finite field $\mathbb{F}_p$ for a prime $p$. Consider a monic irreducible polynomial $f(X)=X^3+aX^2+bX+c$ in $\mathbb{F}_p[X]$. Let $x$ be a root of $f(x)=0$ (say, in the closure of $\mathbb{F}_p$). Consider another different monic irreducible polynomial $g(Y)=Y^3+AY^2+BY+C$ in $\mathbb{F}_p[Y]$. Let $y$ be a root of $g(Y)=0$ again in the same closure.

How do we explicity relate $x$ and $y$? Can we express $y$ as a polynomial in $x$ with coefficients from $\mathbb{F}_p$?

I know that the field extension $\mathbb{F}_{p^3}$ which can be realized as $\mathbb{F}_p[X]/f$ contains $x$ and $y$ (as it contains every root of every irreducible of degree $3$), so $y$ should be expressible in the form $$y=\alpha x^2+ \beta x +\gamma$$ for some $\alpha, \beta, \gamma \in \mathbb{F}_p$.

But this is what I am trying to establish, without using the uniqueness of $\mathbb{F}_{p^3}$ or it being the splitting field of $X^{p^3}-X$. I would prefer not using any non-trivial facts about finite fields here. My aim is to show that every cubic irreducible has a root in the specific extension $\mathbb{F}_p[X]/f$, and I want to do this by explicitly obtaining a dependence of the form $y=\alpha x^2+ \beta x +\gamma$ whenever $y$ satisfies $y^3+Ay^2+By+C=0$.

Is there some algebraic expression or algorithm to find $\alpha, \beta, \gamma$? Something on the lines of resultants maybe.

I was thinking of considering the ideal $<X^3+aX^2+bX+c, Y^3+AY^2+BY+C>$ in $\mathbb{F}_p[X,Y]$ and show that there exists an element in this ideal with total degree at most $2$. But it doesn't seem to lead me anywhere much, especially since I am not clear how to incorporate the (essential) property that both the polynomials are irreducible. Would a Grobner basis of the ideal help with this? I am not too familiar with that technique, but will explore it if it is relevant here. Thanks.

(This has now been cross-posted to MathOverflow: https://mathoverflow.net/questions/243458/algebraic-dependence-of-irreducibles-in-a-finite-field)

• Have you worked out the simpler case when the degree is 2? – Mohan Jun 30 '16 at 18:17
• @Mohan Yes. In the case of degree $2$, if we construct $\mathbb{F}_{p^2}$ using $f(x)=x^2-c$ where $c$ is a quadratic residue, then the roots of another irreducible $Y^2+BY+C$ are 1/2$(-B \pm \sqrt{B^2-4C})$. But $B^2-4C$ is not a quadratic residue (as $Y^2+BY+C$ is irreducible). So it is of the form $\alpha^2c$ for some $\alpha \in \mathbb{F}_p$. So the roots of $Y^2+BY+C$ can be written in the form $a+bx$ where $a,b \in \mathbb{F}_p$. – BharatRam Jun 30 '16 at 18:32
• As a basic courtesy: whenever you cross-post to other sites, you should always announce that at every site where you have done this, and provide links at each such site to all the other pages where you have cross-posted. I have edited in the link for you. – user43208 Jul 1 '16 at 12:44
• You seem to miss the point: by omitting to mention the cross-post here, you potentially cause users here to waste their time on a question that was already answered there (because they are not tuned in to each of the sites). Please take this under consideration, next time you cross-post. Also, I'd recommend that you give it more time at one site; you've been getting some decent feedback here. Finally, read this: meta.stackexchange.com/questions/64068/… – user43208 Jul 1 '16 at 13:19
• You might not consider it a waste of time, but the potential person who answered the question here, only to discover later that it had already been answered there, might resent having spent their precious time repeating an answer, when they have other ways of using their time. That was my point. – user43208 Jul 1 '16 at 14:38

You are worrying about two irreducible cubics $f$ and $g$ over $k=\Bbb F_p$, and you hope to find any one of the three isomorphisms between $K_1=k[x]/(f$) and $K_2=k[x]/(g)$. (There really is no specific $\Bbb F_{p^3}$, just instantiations like these fields $K_i$.) Deal with one of the fields, say $K_1$, and now you know that $g$ splits completely over $K_1$. If $\lambda=a_0+a_1\bar x+a_2\bar x^2$ is one of the roots of $g$ in $K_1$, where $\bar x$ is the image of $x$ in $K_1$, you can get the corresponding isomorphism from $K_2$ to $K_1$, by sending $\hat x$ (the image of $x\in K_2$) to $\lambda$. But I think you already knew this. In case $p$ was large, it might be relatively hard (I’m thinking of hand computation here) to find your $\lambda$. There’s nothing unsolvable about the problem here, but I can only suggest very specialized tricks, nothing that would be guaranteed to short-cut the problem.
• Thank you sir. I was naively expecting some kind of direct algebraic formulation. I mean, given that $x$ is a root of $x^3+ax^2+bx+c$ and $y$ is a root of $y^3+Ay^2+By+C$, we know that we should be able to express $y$ as $\alpha x^2+ \beta x + \gamma$ for some $\alpha, \beta, \gamma \in \mathbb{F}_p$. I was simply asking if there is some construction which gives us this $(\alpha,\beta,\gamma)$ given $p$ and the two polynomials. The converse procedure (constructing an irreducible whose root is $\alpha x^2+ \beta x + \gamma$) is easily done using elimination (using resultants, say). – BharatRam Jul 2 '16 at 16:13
• I am pretty much sure that it’s nothing but a search, very likely of the same order of difficulty as the discrete logarithm problem. If you have $\alpha\in\Bbb F_{p^3}$, though, its minimal $\Bbb F_p$-polynomial is just $(X-\alpha)(X-\alpha^p)(X-\alpha^{p^2})$. – Lubin Jul 2 '16 at 19:21