Skip to content

NumberFieldIntegralBasis

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

NumberFieldIntegralBasis[a]

gives an integral basis for the field Q(a) generated by the algebraic number a: a list of algebraic integers that generate the ring of integers O_K of Q(a) as a module over the integers. The equation order Z[a] is enlarged to O_K by Round 2 (Pohst-Zassenhaus) when it is not already maximal, so the basis is correct for non-monogenic fields. a may be a radical, a Root object, or an AlgebraicNumber object; the basis it produces may not be unique. Threads over lists. Requires FLINT. Attributes: Listable, Protected.

Examples (7)

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (5)

Q(2^(1/3)), monogenic

In[1]:= N[NumberFieldIntegralBasis[2^(1/3)]]
Out[1]= {1.0, 1.25992, 1.5874}

Z[theta] not maximal

In[2]:= N[NumberFieldIntegralBasis[Sqrt[2] + Sqrt[3]]]
Out[2]= {1.0, 3.14626, 5.44949, 13.3706}

Z[zeta_8]

In[3]:= N[NumberFieldIntegralBasis[E^(I Pi/4)]]
Out[3]= {1.0, 0.707107 + 0.707107*I, 6.12323e-17 + 1.0*I, -0.707107 + 0.707107*I}

In[4]:= AlgebraicIntegerQ /@ NumberFieldIntegralBasis[E^(I Pi/4)]
Out[4]= {True, True, True, True}

Threads over lists

In[5]:= N[NumberFieldIntegralBasis[{Sqrt[2], Sqrt[5]}]]
Out[5]= {{1.0, 1.41421}, {1.0, 1.61803}}

Applications (2)

Z[Sqrt[2]] is already the maximal order

In[6]:= NumberFieldIntegralBasis[Sqrt[2]]
Out[6]= {1, AlgebraicNumber[Sqrt[2], {0, 1}]}

Disc 5: the ring of integers needs (1 + Sqrt[5])/2

In[7]:= NumberFieldIntegralBasis[Sqrt[5]]
Out[7]= {1, AlgebraicNumber[Sqrt[5], {1/2, 1/2}]}

Algorithm

numberfieldintegralbasis.c — NumberFieldIntegralBasis[a].

See numberfieldintegralbasis.h for the contract. All field / maximal-order computation is delegated to flint_qqbar_integral_basis (which builds the algebraic-integer generator, runs the number-field layer's Dedekind + Round 2 maximal-order engine, and renders each basis row as a canonical AlgebraicNumber). This file only checks the argument shape and reports a decline; the evaluator re-canonicalises each returned element on its next fixed-point step.

Implementation notes

Algorithm. builtin_numberfieldintegralbasis checks arity 1 and delegates to flint_qqbar_integral_basis, which returns a Z-module basis of the ring of integers O_K of K = Q(a):

  1. Build the algebraic-integer generator phi = lc·alpha of Q(a) (algint_generator), monic of degree n. If n ≤ 1, O_K = Z and the basis is {1}.
  2. Hand phi's monic integer defining polynomial to the number-field layer (nf_field_create), which runs Dedekind's criterion at every ramified prime and, where the equation order Z[phi] is not maximal, enlarges it to O_K by Round 2 (Pohst–Zassenhaus). This is what makes the basis correct for non-monogenic fields, not just {1, phi, …, phi^{n−1}}.
  3. Read back the numerator lattice W and common denominator D (O_K = (1/D)·L). The rows of W are arbitrarily ordered; the engine puts them in the standard presentation — the lower-triangular Hermite normal form in the theta-power basis, so omega_0 = 1 and omega_k has degree exactly k. FLINT's fmpz_mat_hnf gives the upper-triangular HNF, so the lower-triangular one is obtained as a 180°-rotation applied to the column-reversed lattice.
  4. Render each basis row omega_i = (1/D) Σ_j H[i][j] phi^j with poly_to_algnum — an AlgebraicNumber[g, {..}], or a plain Integer/Rational when the row is rational (as omega_0 = 1 always is).

A decline routes a NumberFieldIntegralBasis::nintbas message through mth_message.

Data structures. FLINT qqbar_t for phi; the NumberField* maximal-order object (its Round-2 basis W and denominator D as mpz/fmpz); fmpz_mat for the HNF; fmpq_poly per row; and the AlgebraicNumber representation for each returned element.

Complexity / limits. Dominated by the maximal-order computation — factorisation of the field discriminant and the p-radical / Round-2 steps at each ramified prime. Listable (each generator is its own field), Protected; bounded by the degree cap QQBAR_DEGREE_CAP = 120. Declines when O_K cannot be certified (the discriminant will not factor, or a prime exceeds the single-word modulus) or FLINT is compiled out. The basis returned is correct but not unique (any Z-basis of O_K is admissible; this one is the HNF presentation).

Attributes: Listable, Protected.

References

See also: AlgebraicNumber, N, Root

Notes & additional examples

Notes

NumberFieldIntegralBasis[a] gives a Z-module basis of the ring of integers O_K of K = Q(a): a list of algebraic integers generating O_K over the integers. The equation order Z[a] is enlarged to O_K by Round 2 (Pohst–Zassenhaus) when it is not already maximal, so the result is correct even for non-monogenic fields. The Sqrt[5] example shows this: the basis is not {1, Sqrt[5]} but {1, (1 + Sqrt[5])/2} — the half-integer generator — because the discriminant of x^2 - 5 is 20, four times the field discriminant 5.

The basis is presented in Hermite normal form (so the k-th element has degree k), but any Z-basis of O_K is admissible — the choice is not unique. Listable (each generator is its own field) and Protected; requires FLINT.