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

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?

• $\mathbb{Q}$ is dense in $\mathbb{R}$, so $\mathbb{Q}(q)$ is as well. So any real number can be written as a limit of points in $\mathbb{Q}(q)$, and then truncating gives an error of arbitrarily small size, I believe. I'm not sure what a good algorithm would be however. – Supersingularity Mar 31 '14 at 18:40
• @Supersingularity I think that could be interesting if there was expression bounding the error in terms of $a,b,c$. Do you know of something like that? – BoZenKhaa Mar 31 '14 at 18:46
• I personally don't know of any off the top of my head, but this sounds like either a number theory or computing theory question. You might actually get a better response from someone who knows how to program, since they always have to approximate arbitrary real numbers using rational ones. I'm sure they have come up with good techniques for doing that. – Supersingularity Mar 31 '14 at 18:54
• I see, thanks, I came across this question in a course on field extensions so I was not sure which way to look for answer. – BoZenKhaa Mar 31 '14 at 18:58

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{2} + 3\sqrt{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{2} + 13\sqrt{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.

• I really like this answer because it is an LLL application I did not know about, but I also find it unsettling as it does not say much about the "quality" of approximation the way that continued fractions do.. – BoZenKhaa Apr 2 '14 at 20:39
• Sorry, I just noticed this, you want the basis to be a 4x4, no? You can remove one row in the matrix by identifying T and 1 in the last column. – BoZenKhaa Apr 4 '14 at 15:47