Algorithm to find representation of an element of field extension $\mathbb{Q}(q)$ in the form $\sum a_i q^i$

Question

Let $\mathbb{Q}(q)$ be a field extension of $\mathbb{Q}$, where $q$ is a real root of some monic irreducible polynomial $p(x) \in \mathbb{Z}[x]$ of degree $d=3$.

Given $x \in \mathbb{R}$, (or $\mathbb{Q}(q)$), is there an algorithm to find some good approximation (or expression) of $x$ in the form $x=aq^2+bq+c$, $a,b,c \in \mathbb{Q}$?

I know that I can use continued fractions for field extensions that are generated by second degree polynomials. There, convergents give me "good" approximations of $x$ (the "good aproximation" above is meant in this sense). Is there similar notion for higher values of $d$? Do you know of any books concerning this topic?

Answer 1

You could use the LLL algorithm to find a small vector in a lattice, consider the following $5 \times 4 $ matrix for some relatively large $T$: $$M=\begin{pmatrix} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&1&0\\0&0&0&1\\xT&qT&q^2T&T \end{pmatrix} $$ The columns represents the basis of a lattice in $\mathbb R^5$. You can apply the LLL algorithm (or another lattice reduction algorithm) to get a LLL-reduced basis. Let $N$ be the unimodular transformation carrying $M$ to the LLL-reduced basis then the columns of this matrix give small linear combinations of $x,1,q$ and $q^2$.

For instance if you use Pari-Gp you could do something like

x = Pi;
q = 2^(1/3);
T = 1000;
M = [1,0,0,0; 0,1,0,0; 0,0,1,0; 0,0,0,1; T*x,T*q,T*q^2,T];
N = qflll(M)

This gives the output

[ 2 -1  1 -3]
[-2 -4 -8  1]
[-3  2  5  2]
[ 1  5 -1  5]

which gives (using the first column): $$ \pi - \frac{1}{2}( 2\sqrt[3]{2} + 3\sqrt[3]{4} -1) = 0.0057\dots$$ if you want to find other approximation you can increase the value of $T$ and possible the precision, ie changing $T = 10^5$ gives $$ \pi - \frac{1}{10}( 3\sqrt[3]{2} + 13\sqrt[3]{4} +7) = -5.02\dots 10^{-6} $$

I recommend you to take a look at the section 2.7.2 in Cohen's A course in computational algebraic number theory, to get further advice.

Edit: I forgot to point out that if $x \in \mathbb Q(q)$ then this method will give you very often an exact solution.