I am interested in techniques that you might be able to use to compute the minimal polynomial of basic functions of a root of a minimal polynomial you know. For example $\alpha^2 + \alpha,\; 1 + \alpha+ \alpha^2, \;\frac{\alpha^2 + \alpha}{2},$ etc

The specific purpose of this is I am asked to calculate an integral basis for $\mathcal O_K$ where $K = \mathbb Q(\alpha)$ where $\alpha$ is a root of $x^3 - x - 4$.

I know that $1, \alpha, \alpha^2$ is not an integral basis because the discriminant is divisible by 4, a square. I am also aware of a result that now says that for some non-zero linear combination of $\frac{1}{2}, \frac{\alpha}{2}, \frac{\alpha^2}{2}$, is in $\mathcal O_K$ and replaces one of the terms $1, \alpha, \alpha^2$ to give an integral basis.

However, I do not know how to check if, say, $\frac{\alpha+\alpha^2}{2} \in \mathcal O_K$.

I know that $\alpha$ is a root of $x^3 - x - 4 \Rightarrow \alpha^3 - \alpha = 4$ and squaring both sides we see that $\alpha$ is a root of $x^6 - 2x^4 + x^2 - 16$, and hence $\alpha^2$ is a root of $x^3 - 2x^2 + x - 16$.

But now how can I compute a polynomial for which $\frac{\alpha+\alpha^2}{2}$ is a root? Is there anything faster than just brute force trying polynomials until one works?

  • $\begingroup$ You can use a multivariate resultant and take one of its irreducible factors (but this isn't a general formula). $\endgroup$ – Michael Burr May 12 '18 at 11:01
  • 1
    $\begingroup$ WA can help. $\endgroup$ – lhf May 12 '18 at 11:16
  • $\begingroup$ @lhf I am much more interested in being able to do this by hand, without the assistance of computers. Do you happen to know how WA does this? $\endgroup$ – user366818 May 12 '18 at 11:23
  • $\begingroup$ @user366818, most probably with resultants, which are large determinants. $\endgroup$ – lhf May 12 '18 at 11:39
  • $\begingroup$ See also en.wikipedia.org/wiki/Resultant#Number_theory $\endgroup$ – lhf May 12 '18 at 13:15

Here is another way, which does not depend on resultants and elimination, and which can be done by hand without too much work.

Take $\beta \in \mathbb Q(\alpha)$ and consider the linear map $T: x \mapsto \beta x$. If $f \in \mathbb Q[x]$, then $f(T)=0$ iff $f(\beta)=0$. In particular, $T$ and $\beta$ have the same minimal polynomial. Finding the minimal polynomial of $T$ is not always easy but it shares irreducible factors with the characteristic polynomial, which is easy to compute from a matrix of $T$.

Bottom line: If $\alpha$ has degree $n$, then $\beta$ is a root of a polynomial of degree $n$, the characteristic polynomial of $T$. Just write the matrix $A$ of $T$ with respect to the basis $1,\alpha,\dots,\alpha^{n-1}$ and compute $\det (A-xI)$. Use the equation for $\alpha$ to reduce powers of $\alpha$ in $\beta\alpha^k$.

For $\beta=\frac{\alpha+\alpha^2}{2}$, we have $$ \beta 1 = \frac{\alpha+\alpha^2}{2}, \quad \beta \alpha = \frac{4+\alpha^2+\alpha^3}{2}, \quad \beta \alpha^2 = \frac{4+5\alpha+\alpha^2}{2} \quad $$ and so the matrix is $$ \begin{pmatrix} 0 & 2 & 2 \\ \frac12 & \frac12 & \frac52 \\ \frac12 & \frac12 & \frac12 \\ \end{pmatrix} $$ Its characteristic polynomial is $-x^3 + x^2 + 3 x + 2$.

Thus, the degree of $\beta$ is $1$ or $3$. It cannot be $1$ because this would imply that the degree of $\alpha$ is at most $2$, not $3$. Therefore, this is the minimal polynomial of $\beta$.


Eliminate $\alpha$ from the system of equations $$\alpha^3-\alpha-4=0 \\ 2 \beta - \alpha - \alpha^2 = 0 $$ and get $$\beta^3 - \beta^2 - 3 \beta - 2=0$$ (with Groebner bases on WA)

By hand: take a matrix $A$ with characteristic polynomial $X^3-X-4$, for instance a companion matrix. $\alpha$ is an eigenvalue of $A$, so $\beta= (\alpha^2 + \alpha)/2$ is an eigenvalue of $B=(A^2+A)/2$, so a root of its characteristic polynomial.

In general, once we have an equation for $\beta= f(\alpha)$, $Q(\beta)=0$, and $Q$ has irreducible factors $Q_i$, the minimal polynomial for $\beta$ will be that $Q_i$ for which $Q_i(f(X))$ is divisible by $P(X)$.



  • Suppose that $f(x)$ is the minimal polynomial for $\alpha$ (in your case, $f(x)=x^3-x-4$).

  • Suppose that $g(x)$ is the minimal polynomial for $\alpha^2$ (in your case, $g(x)=x^3-2x^2+x-16$).

  • Consider the multivariate polynomial $h(x,y)=g(y-x)$. The solutions to the system of equations $f(x)=0$ and $h(x,y)=0$ are pairs $(x,y)$ where $x$ is a root of $f(x)$ and $y$ is a sum of two roots of $f$. In your case, $$ h(x,y)=-x^3+3x^2y-3xy^2+y^3-2x^2+4xy-2y^2-x+y-16. $$

  • You now want to eliminate $x$ from the system of equations $f(x)=0$ and $h(x,y)=0$. This can be done either using a multivariate resultant or Groebner bases with a lex order $x>y$. Using a multivariate resultant in your case gives, \begin{align} \operatorname{Res}(f(x)&,h(x,y);x)\\ &=y^9-6y^8+12y^7-66y^6+231y^5-384y^4-188y^3+864y^2+880y-8768. \end{align} Through direct calculation, you can find that $\alpha^2+\alpha$ is a root of this polynomial.

  • The resultant polynomial is not the minimal polynomial, in most cases, so we need to factor it. In your case, the resultant factors as $$ (y^3-2y^2-12y-16)(y^6-4y^5+16y^4-66y^3+227y^2-466y+548). $$ We can directly check that the cubic term is the minimal polynomial for $\alpha^2+\alpha$.

  • For $\frac{\alpha^2+\alpha}{2}$, one only needs to compute a homothety (a scaling).

Most of this can be done by hand, but it can be quite tedious. The most annoying part to do by hand is the factoring (note that resultants can be computed by determinants of Sylvester matrices).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.