Problems in finding an integral basis in a ring of algebraic ntegers I have some problems with this paper.


*

*Firstly, with theorem 3.4: I don't know if this is the original formulation in the literature, but the statement seems rather trivial to me if one considers $0$ to be an algebraic integer. Moreover there are cases where a non trivial integer doesn't even exist as in the classical example of the ring of integers of  $\Bbb Q(\sqrt{d})$ where $d \in  \Bbb Z$ and $d \neq 1 \mod 4$.

*Secondly, in the algorithm that is based on this theorem. As an example I consider the polynomial $x^4+5x+5$. The Galois group of this polynomial over $\Bbb Q$ is the cyclic group of order $4$ abd its splitting field can be represented by its companion matrix $M = \left(\begin{smallmatrix}0 & 0 & 0 & -5\\1 & 0 & 0 & -5\\0 & 1 & 0 & 0\\0 & 0 & 1 & 0\end{smallmatrix}\right)$. Since $M$ is an algebraic integer one can take as a basis of integers for the splitting field the set $B = \{M^0,M,M^2,M^3\}$.The discriminant of this basis using $\Delta = \det(\operatorname{Tr}(B_iB_j))$ equals $5^3\dot 11^2$ (as does the discriminant of the polynomial). If I apply the algorithm I find an algebraic integer with coefficients $\frac{1}{11}\left [ 1, 3, 6,1\right ]$ (the minimal polynomial is $x^4+x^3+6x^2-4x+1$). If I replace in B the second element by this element I obtain a basis whose discriminant now is $5^33^2$, so we are nowhere nearer to an integral basis, on the contrary, one bastard goes out and another comes in. 

*Conclusion: We know that the discriminant of an intergral basis divides that of a basis of integers so in out case it divides both discriminants so also their $\gcd, 5^3$. If only there was a way to calculate the $\gcd$ of two bases of integers.

 A: Here is a formulation which makes more sense. First, recall some terms.


*

*There is the discriminant of the field $K$, given as follows: If $\alpha_i$ denotes an basis of $\mathcal{O}_K$ over $\mathbf{Z}$, then


$$\Delta_K = \Delta(\alpha_i):=\det \mathrm{Tr}(\alpha_i \alpha_j).$$


*If $\beta_i$ are $n = [K:\mathbf{Q}]$ elements of $\mathcal{O}_K$, one can also define:


$$\Delta(\beta_i):= \det \mathrm{Tr}(\alpha_i \alpha_j).$$


*As a special case, if $\beta \in K$ is the root of a polynomial $f(x)$ which generates $K$, and $\beta_1, \ldots, \beta_n$ are the powers $1$, $\beta, \ldots , \beta^{n-1}$, then $\Delta(\beta_i)$ is the discriminant of the polynomial $f$.


The key relation is that:
$$\Delta(\beta_i) = [\mathcal{O}_K:\mathbf{Z}[\beta_1,\ldots,\beta_n]]^2 \cdot \Delta_K.$$ 
From this, one can deduce the following:


*

*If $p$ divides the index of $\mathbf{Z}[\beta_1,\ldots,\beta_n]$ in $\mathcal{O}_K$, then $p^2$ divides $\Delta(\beta_i)$.

*If $p$ divides the index of $\mathbf{Z}[\beta_1,\ldots,\beta_n]$ in $\mathcal{O}_K$, then there is an algebraic integer of the form
$$\gamma = \frac{1}{p} \left(\lambda_1 \beta_1 + \ldots + \lambda_n \beta_n \right)$$
where $0 \le \lambda_i < p$ for all $i$ and not all of them are zero.
(This is the correct formulation of the statement you linked too --- one may insist that not all the $\lambda_i$ are zero, but this only exists if $p$ actually divides the index of the $\beta_i$ in $\mathcal{O}_K$, simply dividing $\Delta(\beta_i)$ is not enough. Of course, in practice, you can try this for all the possible $p$, and if you don't find a $\gamma$ then you have an integral basis.


*In practice, you start with an element $\beta$ and consider the set $\{1,\beta,\ldots,\beta^{n-1}\} = \{\beta_1,\ldots,\beta_n\}$. But the main point is that --- if you find $\gamma$ --- you don't replace the power basis of $\beta$ by the power basis of $\gamma$, but rather take:


$$\{\beta'_1,\ldots,\beta'_n\} = \left\{\beta_1,\ldots,\beta_{n-1},\frac{1}{p} \left(\lambda_1 \beta_1 + \ldots + \lambda_n \beta_n \right)\right\}.$$
This now has smaller index and you repeat. Edit: More carefully, you really want your new lattice to contain the old lattice. So you want the lattice generated by all the $\beta_i$ together with $\gamma$. You can ensure this as follows. At least one of the $\lambda_j$ will be non-zero modulo $p$ by construction. Replacing $\gamma$ by some multiple, one can first assume that $\lambda_j \equiv 1 \mod p$, and then, subtracting a multiple of $\beta_j$, one can assume $\lambda_j = 1$. Then the larger lattice $\{\beta_i,\gamma\}$ is generated by $\gamma$ and $\beta_i$ for $i \ne j$, and so this will have smaller index. End Edit
In your example, let $\beta$ be a root of $x^4 + 5x + 5$. You then discover a new integral element $\gamma$, for example,  your element:
$$\gamma = \frac{1}{11} \gamma^3 + \frac{6}{11} \gamma^2 + \frac{3}{11} \gamma + \frac{1}{11},$$
which does not lie in this basis. The next step is to consider $\{1,\beta,\beta^2,\gamma\}$. That will actually be a basis in this case. In fact, I compute the trace pairing matrix to be:
$$\left( \begin{matrix} 4 & 0 & 0 & -1 \\ 0 & 0 & -15 & -10 \\ 0 & -15 & -20 & -15 \\ -1 & -10 & -15 & -11 \end{matrix} \right),$$
which has discriminant $5^3$. Another computation at $5$ then shows this is an integral basis and one is done.
Warning! Not all fields have an integral basis given by powers of a single element (although this is true in degrees $1$ and $2$). Such fields are called monogenic, and, by certain measures, are rare. Determining if a field is monogenic or not can be quite non-trivial.
Of course, in your particular case, you can easily recognize the field from the fact that it is abelian and has discriminant $5^3$. Namely, it must be the field of fifth roots of unity. After you make this guess, you can compute that
$$\zeta = -\frac{3}{11} \beta^3 + \frac{4}{11} \beta^2 - \frac{9}{11} \beta - \frac{14}{11} = -1 + 0 \cdot \beta + 2 \cdot \beta^2  - 3 \cdot \gamma$$
does indeed satisfy $\zeta^5 = 1$.
