fredrikj.net / blog /
Printing algebraic numbers
March 24, 2021
The Calcium library supports exact computation in the field of algebraic numbers $\overline{\mathbb{Q}}$. A surprisingly subtle problem is to convert algebraic numbers to text or symbolic expressions for serialization or presentation to the user.
Contents
Algebraic numbers in Calcium
There are essentially three different ways to represent algebraic numbers in Calcium: in absolute form, as field elements, and as symbolic expressions.
-
The qqbar_t type represents an algebraic number in a canonical form consisting of the minimal polynomial together with a root enclosure. For example, the third root of unity $e^{2\pi i / 3}$ is represented by $x^2 + x + 1$ together with a complex interval $[-0.500000\ldots \pm \ldots] + [0.866025\ldots \pm \ldots] i$. Strictly speaking, the internal representation is not bitwise canonical since the isolating intervals are subject to numerical noise, but this is an implementation detail which is not normally visible externally; qqbar_t operations refine the roots automatically as needed to ensure exact results for the algebraic numbers being represented.
-
The ca_t type represents numbers as elements of fields $\mathbb{Q}(a_1,\ldots,a_n)$ where $a_1,\ldots,a_n$ are extension numbers which may be algebraic or transcendental. Algebraic extension numbers can be defined either in absolute form (qqbar_t constants) or in relative form (for example, $a_i = \sqrt{a_j}$). The ca_t type is usually far more efficient than qqbar_t for number crunching, for two reasons: field operations do not require computing new minimal polynomials (only reducing by polynomials that are already known), and multivariate fields avoid problems with degree explosion (a famous pathological example is that the minimal polynomial of $\sqrt{2} + \sqrt{3} + \sqrt{5} + \ldots + \sqrt{p_n}$ has degree $2^n$). The downside is that the representation is non-canonical; two structurally different ca_t instances can represent the same algebraic number. For example, the third root of unity can be represented as an element of $\mathbb{Q}(e^{2 \pi i / 3})$, but it can also be represented as an element of $\mathbb{Q}(\sqrt{-3})$ or $\mathbb{Q}(\sqrt{3}, i)$, among other possibilities. It is often useful to convert an algebraic ca_t to an absolute qqbar_t constant for the purpose of simplifying formulas or evaluating predicates (many Calcium functions do so internally).
-
The fexpr_t type allows working with unevaluated symbolic expressions. This is highly versatile: one can construct RootOfUnity(3), Exp(Mul(2, Pi, NumberI) / 3), Div(Add(-1, Sqrt(-3)), 2), Add(Div(-1, 2), Div(Mul(Sqrt(3), NumberI), 2)), etc. By design, symbolic expressions will not perform any simplifications or computations automatically, but they are easily converted to any desired computational type (ca_t, qqbar_t, acb_t, etc.) through a simple expression tree traversal. They can be used as an intermediate format for user input/output (there is builtin support for pretty LaTeX output) or serialization.
This post will discuss how I'm trying to address input and output of qqbar_t numbers in a user-friendly way. On the interface level, this is mainly accomplished using fexpr_t objects. Conversion works in both directions:
- Expression to number: the qqbar_set_fexpr method converts a given symbolic expression to a qqbar_t value. This method has no advanced tricks up its sleeve; it will just traverse a fixed formula like Add(Div(-1, 2), Div(Mul(Sqrt(3), NumberI), 2)) using qqbar_t temporary values and delegate each symbolic function to the relevant qqbar_t function. It will detect problems like division by zero or trying to construct the transcendental number $\sqrt{2}^{\sqrt{2}}$.
- Number to expression: the methods qqbar_get_fexpr_repr, qqbar_get_fexpr_root_nearest, qqbar_get_fexpr_root_indexed and qqbar_get_fexpr_formula convert a qqbar_t to an fexpr_t in various forms. The output of either method can be converted back to an algebraic number using qqbar_set_fexpr. I will discuss the various output formats in turn below.
Ugly output: the internal representation
Internally, the Calcium qqbar_t type stores an algebraic number as an fmpz_poly_t representing the unique normalized minimal polynomial in $\mathbb{Z}[x]$ together with an Arb complex interval (acb_t) guaranteed to enclose a unique root. The precision of the enclosure will normally be around 128 bits, but may be lower or higher depending on the separation of the roots and the sequence of operations that were used to compute the given number.
The qqbar_get_fexpr_repr method simply dumps the internal representation to a symbolic expression. For example, the complex number $(-2)^{1/3}$ (with minimal polynomial $x^3 + 2$) converts to the following fexpr_t:
AlgebraicNumberSerialized(List(2, 0, 0, 1), Add(RealBall(Mul(214364458495870623776120245247825577605, Pow(2, -128)), Mul(639499263, Pow(2, -152))), Mul(RealBall(Mul(46411266681479724132078742453131163747, Pow(2, -125)), Mul(661439827, Pow(2, -152))), NumberI)))
The above rendered to LaTeX:
$$\operatorname{AlgebraicNumberSerialized}\!\left(\left[2, 0, 0, 1\right], \left[214364458495870623776120245247825577605 \cdot {2}^{-128} \pm 639499263 \cdot {2}^{-152}\right] + \left[46411266681479724132078742453131163747 \cdot {2}^{-125} \pm 661439827 \cdot {2}^{-152}\right] i\right)$$This format is designed for efficiency: both input and output essentially just require rearranging bytes in memory. Given the special AlgebraicNumberSerialized constructor, qqbar_set_fexpr assumes that the expression has been generated verbatim from a valid qqbar_t instance, and will not bother to validate it for correctness. Validating such input would require checking that the given polynomial is irreducible and that the enclosure contains a unique root. These operations are not free, but they are also not terribly expensive; the cost would be comparable to that of a single arithmetic operation in the qqbar_t representation.
I have not attempted to make the LaTeX output pretty for the serialized representation. An immediate improvement would be to print the floating-point numbers in decimal instead of binary. This is dangerous, however: a binary-to-decimal conversion generally inflates the enclosure, which could lead to losing the root isolation property. Verifying that the inflated decimal interval is correct requires a nontrivial computation. At that point, we may as well go through the trouble to present the output in an even more human-friendly way (as covered below).
Pretty output: polynomial and approximation
The function qqbar_get_fexpr_root_nearest renders an algebraic number $a$ as its minimal polynomial together with a decimal approximation $\tilde a$ such that $\tilde a$ is closer to $a$ than any other root of the same polynomial (allowing $a$ to be reconstructed unambiguously). Here is the fexpr_t output for the golden ratio and the principal third root of unity:
PolynomialRootNearest(List(-1, -1, 1), Decimal("1.61803"))
PolynomialRootNearest(List(1, 1, 1), Add(Decimal("-0.500000"), Mul(Decimal("0.866025"), NumberI)))
Automatically rendered to LaTeX:
$$\left(\text{Root }\, x \approx {1.61803} \;\text{ of } \;{ x^{2}- x-1}\right)$$ $$\left(\text{Root }\, x \approx {-0.500000 + 0.866025 i} \;\text{ of } \;{ x^{2}+ x+1}\right)$$This is my preferred human-readable format for displaying an algebraic number unambiguously (reversibly), and I put a fair bit of thought into its implementation.
First of all, in the reverse direction, the PolynomialRootNearest function is convenient for input since it does not require providing an enclosure; any approximation of the root suffices. Thus PolynomialRootNearest(List(-2, 0, 1), 1) gives $\sqrt{2}$ and PolynomialRootNearest(List(-2, 0, 1), -1) gives $-\sqrt{2}$. A precise approximation is only needed to distinguish between clustered roots.
The output precision is normally six digits. Six is a good default for displaying numerical values since it is compact and mnemonic (six digits can be read as a pair of hundreds), while usually providing the user with enough precision for insight or further calculation (of course, the user can request more digits when this is not enough). In fact, qqbar_get_fexpr_root_nearest will automatically show more digits when it encounters clustered roots. Here is the list of roots of $x^{13} + (100x+1)^4$:
$$\left(\text{Root }\, x \approx {-0.00999999683773} \;\text{ of } \;{ x^{13}+100000000 x^{4}+4000000 x^{3}+60000 x^{2}+400 x+1}\right)$$ $$\left(\text{Root }\, x \approx {-0.0100000031623} \;\text{ of } \;{ x^{13}+100000000 x^{4}+4000000 x^{3}+60000 x^{2}+400 x+1}\right)$$ $$\left(\text{Root }\, x \approx {-7.73819} \;\text{ of } \;{ x^{13}+100000000 x^{4}+4000000 x^{3}+60000 x^{2}+400 x+1}\right)$$ $$\left(\text{Root }\, x \approx {7.28014 + 2.64814 i} \;\text{ of } \;{ x^{13}+100000000 x^{4}+4000000 x^{3}+60000 x^{2}+400 x+1}\right)$$ $$\left(\text{Root }\, x \approx {7.28014-2.64814 i} \;\text{ of } \;{ x^{13}+100000000 x^{4}+4000000 x^{3}+60000 x^{2}+400 x+1}\right)$$ $$\left(\text{Root }\, x \approx {3.87576 + 6.70532 i} \;\text{ of } \;{ x^{13}+100000000 x^{4}+4000000 x^{3}+60000 x^{2}+400 x+1}\right)$$ $$\left(\text{Root }\, x \approx {3.87576-6.70532 i} \;\text{ of } \;{ x^{13}+100000000 x^{4}+4000000 x^{3}+60000 x^{2}+400 x+1}\right)$$ $$\left(\text{Root }\, x \approx {-0.0100000 + 3.16228 \cdot 10^{-9} i} \;\text{ of } \;{ x^{13}+100000000 x^{4}+4000000 x^{3}+60000 x^{2}+400 x+1}\right)$$ $$\left(\text{Root }\, x \approx {-0.0100000-3.16228 \cdot 10^{-9} i} \;\text{ of } \;{ x^{13}+100000000 x^{4}+4000000 x^{3}+60000 x^{2}+400 x+1}\right)$$ $$\left(\text{Root }\, x \approx {-1.34005 + 7.62501 i} \;\text{ of } \;{ x^{13}+100000000 x^{4}+4000000 x^{3}+60000 x^{2}+400 x+1}\right)$$ $$\left(\text{Root }\, x \approx {-1.34005-7.62501 i} \;\text{ of } \;{ x^{13}+100000000 x^{4}+4000000 x^{3}+60000 x^{2}+400 x+1}\right)$$ $$\left(\text{Root }\, x \approx {-5.92676 + 4.97687 i} \;\text{ of } \;{ x^{13}+100000000 x^{4}+4000000 x^{3}+60000 x^{2}+400 x+1}\right)$$ $$\left(\text{Root }\, x \approx {-5.92676-4.97687 i} \;\text{ of } \;{ x^{13}+100000000 x^{4}+4000000 x^{3}+60000 x^{2}+400 x+1}\right)$$There is a cluster of four poorly-separated roots (two real and two complex) near $-0.01$. You may note that only the two clustered real roots are printed with higher precision: qqbar_get_fexpr_root_nearest is clever and only shows more digits where it is needed for disambiguation (in this case, the imaginary parts of the nonreal roots in the cluster provide adequate isolation, and the roots outside the cluster are all well separated).
Implementing qqbar_get_fexpr_root_nearest was quite tricky. The naive method would be to compute all the conjugates of the given algebraic number and then compare the decimal approximation to each other root, increasing the precision when necessary. However, computing all the conjugate roots is an expensive operation which should be avoided if possible. Another option would be to use a global root separation bound (the Mahler-Mignotte bound, for example), but such bounds are hopelessly pessimistic for polynomials much bigger than $x^2+1$. A third possibility would be to use the interval Newton method to certify that a region around the approximate root contains a unique root. The qqbar_t type depends extensively on this method in its internal functions to maintain correct root enclosures, but in my experiments this turned out to perform poorly when starting from low-precision (six digits) approximations.
In the end, I implemented a different method specifically for qqbar_get_fexpr_root_nearest: I do a Taylor shift to center the polynomial on the approximate point, and then use a test based on Rouché's theorem to make sure that there is exactly one nearby root. This seems to work well; it usually succeeds to validate a six-digit approximation quickly even for algebraic numbers of degree 100 or higher.
Right now, converting the output back to an algebraic number remains expensive: given a PolynomialRootNearest expression, qqbar_set_fexpr simply computes all the roots of the polynomial and selects the nearest root. This should be optimized by implementing a test based on Taylor shift + Rouché's theorem (or something equivalent). There is also plenty of room to use similar tricks to improve the root refinement and certification code used elsewhere by the qqbar_t type (usually, when an interval Newton check fails, all the roots will be recomputed from scratch, which is needlessly expensive).
Pretty output: polynomial and index
We may fix an ordering of $\mathbb{C}$ and refer to each root of a polynomial using its index with respect to this ordering. This is implemented by qqbar_get_fexpr_root_indexed. For the golden ratio and its conjugate root, it outputs the following:
PolynomialRootIndexed(List(-1, -1, 1), 1) PolynomialRootIndexed(List(-1, -1, 1), 2)
Automatically rendered to LaTeX:
$$\left(\text{Root \#}1 \text{ of }\, { x^{2}- x-1}\right)$$ $$\left(\text{Root \#}2 \text{ of }\, { x^{2}- x-1}\right)$$Of course, qqbar_set_fexpr is able to parse PolynomialRootIndexed calls, so this format is reversible.
Most computer algebra systems use a similar convention for naming roots, usually with functions called Root, RootOf or something similar.
This format is most convenient for iterating over all the roots of a polynomial. The absence of numerical information is a drawback for presentation: the output gives no indication that root #1 is near 1.61803 and that root #2 is near -0.618034. Indexed root objects are also not portable between systems: Calcium uses one particular convention for sorting roots, but Maple, Mathematica, SymPy etc. have their own conventions (some systems may not even have an internally consistent convention). Another drawback is that finding the correct index for a given qqbar_t generally requires computing the conjugate roots, so this is typically more expensive than the PolynomialRootNearest format.
Pretty output: closed forms
The qqbar_get_fexpr_formula method attempts to express the given algebraic number in closed form. A closed form is a formula that only uses some restricted set of operations, usually understood to exclude "implicit" operations such as "root of ..." or "infinite series over ...". The most interesting closed forms for algebraic numbers are those involving only arithmetic operations and radicals ($n$th roots) or elementary functions (e.g. roots of unity $e^{2 \pi i / q}$). Consider the following ways to display the same algebraic number:
$$\left(\text{Root }\, x \approx {3.14626} \;\text{ of } \;{ x^{4}-10 x^{2}+1}\right)$$ $$e^{\pi i / 6} - e^{5 \pi i / 6} + e^{\pi i / 4} - e^{3 \pi i / 4}$$ $$2 \sin\!\left(\frac{\pi}{3}\right) + 2 \sin\!\left(\frac{\pi}{4}\right)$$ $$\sqrt{5 + 2 \sqrt{6}}$$ $$\sqrt{2} + \sqrt{3}$$Each one has its advantages: the first is not a closed form according to the usual definition, but it makes the minimal polynomial and degree explicit (as well as the numerical value); the second expresses the number within a cyclotomic field (often useful for calculations); the third is similar, but avoids complex numbers; the last two formulas use only real square roots. Most people probably prefer the last formula $\sqrt{2} + \sqrt{3}$. There is a certain sense in which $\sqrt{5 + 2 \sqrt{6}}$ is structurally simpler, but intuitively, nested square roots are less elegant than square roots of integers.
The minimal polynomial has the benefit of being canonical and computable: given any closed form representation of an algebraic number, we can easily convert the number to this canonical representation. Closed forms, by contrast, are highly non-canonical. Finding any closed form of an algebraic number of degree $d \ge 5$, if it exists, is nontrivial (in general, requiring the computation of Galois groups); generating optimal closed forms (by most metrics) is even harder. If you take a formula involving radicals, convert it to a polynomial root, and ask a computer algebra system to re-express this root in terms of radicals, you will probably get a far more complex expression than the one you started with.
Indeed, even in the seemingly trivial case of quadratic numbers $a + b \sqrt{D}$, finding an optimal formula in the sense of minimizing $D$ requires integer factorization, which is prohibitive when the coefficients are large.
To take the example of the quartic number $3.1416\ldots$, most systems will probably output $\sqrt{5 + 2 \sqrt{6}}$ since this is the natural result of applying the quartic formula (or in this case, the quadratic formula twice). Finding the "atomized" form $\sqrt{2} + \sqrt{3}$ is less straightforward (it can be accomplished, for instance, by applying a square root denesting algorithm or by identifying the number as cyclotomic).
Closed forms are not necessarily pretty: for generic polynomials of degree 3 and 4, the minimal polynomial is usually far more compact than an optimized expression in terms of radicals; nevertheless, algebraic numbers with simple closed forms are quite common in applications, so it is an interesting problem to look for closed forms when possible.
The following table shows some formulas, the qqbar_t algebraic number (obtained by evaluating the expression using qqbar_set_fexpr), and the output of qqbar_get_fexpr_formula:
| Input formula | Algebraic number | Output formula |
|---|---|---|
| $\displaystyle{\varphi}$ | $\displaystyle{\frac{1 + \sqrt{5}}{2}}$ | |
| $\displaystyle{-\frac{1}{\varphi}}$ | $\displaystyle{\frac{1 - \sqrt{5}}{2}}$ | |
| $\displaystyle{e^{2 \pi i / 3}}$ | $\displaystyle{\frac{-1 + \sqrt{-3}}{2}}$ | |
| $\displaystyle{\frac{1}{\sqrt{-{20}^{21}} + 1}}$ | $\displaystyle{\frac{1-20480000000000 \sqrt{-5}}{2097152000000000000000000001}}$ | |
| $\displaystyle{\sqrt{2} + \sqrt{3}}$ | $\displaystyle{\sqrt{2} + \sqrt{3}}$ | |
| $\displaystyle{\frac{\sqrt{3}}{2 + 3 \sqrt{2}}}$ | $\displaystyle{\frac{3 \sqrt{2} \sqrt{3}-2 \sqrt{3}}{14}}$ | |
| $\displaystyle{\sin\!\left(\frac{\pi}{5}\right) + \sin\!\left(\frac{\pi}{8}\right)}$ | $\displaystyle{\sin\!\left(\frac{\pi}{5}\right) + \sin\!\left(\frac{\pi}{8}\right)}$ | |
| $\displaystyle{3 \tan\!\left(\frac{\pi}{7}\right) + 4 \tan\!\left(\frac{\pi}{5}\right)}$ | $\displaystyle{8 \cos\!\left(\frac{\pi}{10}\right)-6 \cos\!\left(\frac{\pi}{14}\right)-8 \sin\!\left(\frac{\pi}{5}\right) + 6 \sin\!\left(\frac{\pi}{7}\right) + 6 \cos\!\left(\frac{3 \pi}{14}\right)}$ | |
| $\displaystyle{\frac{1}{1 - e^{2 \pi i / 9}}}$ | $\displaystyle{\frac{2 + 2 e^{2 \pi i / 9} + 2 e^{4 \pi i / 9} + e^{2 \pi i / 3} + e^{8 \pi i / 9} + e^{10 \pi i / 9}}{3}}$ | |
| $\displaystyle{\operatorname{Re}\!\left(\frac{1}{1 - e^{2 \pi i / 9}}\right)}$ | $\displaystyle{\frac{1}{2}}$ | |
| $\displaystyle{\operatorname{Im}\!\left(\frac{1}{1 - e^{2 \pi i / 9}}\right)}$ | $\displaystyle{\frac{\sqrt{3} + 4 \cos\!\left(\frac{\pi}{18}\right) + 4 \sin\!\left(\frac{2 \pi}{9}\right)}{6}}$ | |
| $\displaystyle{\left|\frac{1}{1 - e^{2 \pi i / 9}}\right|}$ | $\displaystyle{\frac{\sqrt{3} + \cos\!\left(\frac{\pi}{18}\right) + 3 \sin\!\left(\frac{\pi}{9}\right) + \sin\!\left(\frac{2 \pi}{9}\right)}{3}}$ | |
| $\displaystyle{\operatorname{sgn}\!\left(\frac{1}{1 - e^{2 \pi i / 9}}\right)}$ | $\displaystyle{e^{7 \pi i / 18}}$ | |
| $\displaystyle{\frac{1}{{10}^{1 / 10}}}$ | $\displaystyle{{\left(\frac{1}{10}\right)}^{1 / 10}}$ | |
| $\displaystyle{5 {\left(\sqrt{2} - \sqrt{3}\right)}^{1 / 3}}$ | $\displaystyle{{\left(78125-31250 \sqrt{6}\right)}^{1 / 6} \frac{1 + \sqrt{-3}}{2}}$ |
The qqbar_get_fexpr_formula method currently uses four internal heuristics: the quadratic formula, detection of cyclotomic numbers, detection of perfect $n$th roots of lower-degree numbers, and separation of complex parts. As the table shows, these heuristics work quite well for finding reasonable closed forms of "familiar" numbers. There is plenty of room for optimizations as well as superficial customizations (choosing between radicals, exponentials and trigonometric functions, and so on).
I will of course need to implement the cubic formula, the quartic formula, and other special cases. I have no plan to implement computation of Galois groups in Calcium in the near future, and computing Galois groups will in any case be too slow for numbers of high degree. It would be interesting to look at heuristics for automatically decomposing an algebraic number into $a+b$ or $a \cdot b$ with $a, b$ of lower degree, without explicitly computing Galois groups. This should be doable at least in some cases.
Pretty output: keeping it simple
For printing algebraic numbers in the terminal, I've settled on the following compact format:
1.61803 (deg 2) 0.309017 + 0.951057*I (deg 4)
A possible LaTeX equivalent might be to show the degree as a subscript:
$$1.61803_{\,\text{deg } 2}$$ $$(0.309017 + 0.951057i)_{\,\text{deg } 4}$$This compact format is of course not reversible; if it is used by default, the user will have to request an exact description manually (when needed). It makes some sense to show the full form of an algebraic number when displaying one number by itself, but that will usually be too verbose for displaying a 10 by 10 matrix. This compact format is an attempt to maximize both compactness and utility: a numerical approximation is clearly useful, and the degree gives useful information about what kind of object we are dealing with; the precise coefficients of the minimal polynomial are often uninteresting, but it is qualitatively significant whether an algebraic number has degree 1, 2, 5 or 120.
Other possibilities
In what other ways may we represent algebraic numbers?
Thom encodings
The "Thom encoding" identifies a real root of a minimal polynomial by the sequence of signs of the derivatives at the root (it turns out that this sequence identifies each root uniquely). The Thom encoding is apparently popular in quantifier elimination contexts, but it seems rather esoteric as a way to display algebraic numbers. It also has the (minor) disadvantage of being defined only for real roots, meaning that complex algebraic numbers need to be decomposed into real and imaginary parts.
Numerical recovery
Here is a far more whimsical idea. If I tell you that $x \approx 0.414213$ is an algebraic number, you may be able to guess that $x = \sqrt{2} - 1$. This can be done automatically using integer relation methods such as LLL or PSLQ; for example the following Calcium code succeeds:
arb_set_str(acb_realref(x), "0.414213 +/- 0.000001", 53); qqbar_guess(guess, x, 2, 10, 0, 53); /* guess number of degree <= 2, coefficients <= 2^10 */
The problem of identifying an algebraic number from an approximation is clearly not well-posed unless more constraints are given: for example, $414213/1000000$ or $\sqrt{2} - 1 - 5/10000000$ would be valid guesses as well. However, $\sqrt{2} - 1$ is the "best algebraic approximation" of 0.414213 in the sense of minimizing the norm of the integer relation (or the size of the coefficient vector of the minimal polynomial) within the indicated precision. It should be possible to design an explicit scheme which, given any algebraic number, outputs a decimal approximation with a number of significant digits chosen so that feeding this particular decimal string back into LLL (with parameters determined automatically from the number of signficant digits) is guaranteed to recover the original number. This method is probably not very practical (since the necessary precision will be huge for numbers of high degree or with large coefficients), but it has a certain perverse elegance to it. Here is a mini-puzzle to solve with your favorite computer algebra system: what is this number?
0.003450727252145973045194665418747216554474554259161113891893888709465938930192026170738308580561008405449423847973636204359040966799321990097753158255879849989219162356420411777441050678788379848876264212307072764461401467308104488273784285153521023055158739186282471098901402796160876592263758278165511507470649664762133216159701258634514329803409363713680742424160500131649366990813697882063317976790292064087239592194136670351335300489664900788736532746758177112558962819927463733012243220997941449969542146246636369726449326253012930244538304268815904020044741554896235234089768852864199381609353376054658104641887225569810216020276049421668378016614560347807697040264370288989265880508980418037995125196573222932270506276095583328489785658593278755152243122109542399472011999416196796836023026780649397422150128416043913383469478825902485491538902840904741752858410332524255269560655516317697141876091215296453920161232676282901615425872359076974523867821910352311385529305509181156919519319005820
Enumerating the algebraic numbers
The set of algebraic numbers is countable, and we can define an explicit enumeration function $A : \mathbb{N} \to \overline{\mathbb{Q}}$ such that $A(n)$ is the $n$th algebraic number. This OEIS wiki page proposes one possible enumeration function based on a graded lexicographic ordering of minimal polynomials. Below is a list of the first 97 algebraic numbers generated using a similar enumeration:
| $n$ | Polynomial | Algebraic number $A(n)$ |
|---|---|---|
| 0 | [0, 1] | $\displaystyle{0}$ |
| 1 | [-1, 1] | $\displaystyle{1}$ |
| 2 | [1, 1] | $\displaystyle{-1}$ |
| 3 | [-2, 1] | $\displaystyle{2}$ |
| 4 | [-1, 2] | $\displaystyle{\frac{1}{2}}$ |
| 5 | [1, 2] | $\displaystyle{-\frac{1}{2}}$ |
| 6 | [2, 1] | $\displaystyle{-2}$ |
| 7 | [1, 0, 1] | $\displaystyle{i}$ |
| 8 | [1, 0, 1] | $\displaystyle{-i}$ |
| 9 | [-3, 1] | $\displaystyle{3}$ |
| 10 | [-1, 3] | $\displaystyle{\frac{1}{3}}$ |
| 11 | [1, 3] | $\displaystyle{-\frac{1}{3}}$ |
| 12 | [3, 1] | $\displaystyle{-3}$ |
| 13 | [-2, 0, 1] | $\displaystyle{\sqrt{2}}$ |
| 14 | [-2, 0, 1] | $\displaystyle{-\sqrt{2}}$ |
| 15 | [-1, -1, 1] | $\displaystyle{\frac{1 + \sqrt{5}}{2}}$ |
| 16 | [-1, -1, 1] | $\displaystyle{\frac{1 - \sqrt{5}}{2}}$ |
| 17 | [-1, 0, 2] | $\displaystyle{\frac{\sqrt{2}}{2}}$ |
| 18 | [-1, 0, 2] | $\displaystyle{-\frac{\sqrt{2}}{2}}$ |
| 19 | [-1, 1, 1] | $\displaystyle{\frac{-1 + \sqrt{5}}{2}}$ |
| 20 | [-1, 1, 1] | $\displaystyle{\frac{-1 - \sqrt{5}}{2}}$ |
| 21 | [1, -1, 1] | $\displaystyle{\frac{1 + \sqrt{-3}}{2}}$ |
| 22 | [1, -1, 1] | $\displaystyle{\frac{1 - \sqrt{-3}}{2}}$ |
| 23 | [1, 0, 2] | $\displaystyle{\frac{\sqrt{-2}}{2}}$ |
| 24 | [1, 0, 2] | $\displaystyle{-\frac{\sqrt{-2}}{2}}$ |
| 25 | [1, 1, 1] | $\displaystyle{\frac{-1 + \sqrt{-3}}{2}}$ |
| 26 | [1, 1, 1] | $\displaystyle{\frac{-1 - \sqrt{-3}}{2}}$ |
| 27 | [2, 0, 1] | $\displaystyle{\sqrt{-2}}$ |
| 28 | [2, 0, 1] | $\displaystyle{-\sqrt{-2}}$ |
| 29 | [-4, 1] | $\displaystyle{4}$ |
| 30 | [-3, 2] | $\displaystyle{\frac{3}{2}}$ |
| 31 | [-2, 3] | $\displaystyle{\frac{2}{3}}$ |
| 32 | [-1, 4] | $\displaystyle{\frac{1}{4}}$ |
| 33 | [1, 4] | $\displaystyle{-\frac{1}{4}}$ |
| 34 | [2, 3] | $\displaystyle{-\frac{2}{3}}$ |
| 35 | [3, 2] | $\displaystyle{-\frac{3}{2}}$ |
| 36 | [4, 1] | $\displaystyle{-4}$ |
| 37 | [-3, 0, 1] | $\displaystyle{\sqrt{3}}$ |
| 38 | [-3, 0, 1] | $\displaystyle{-\sqrt{3}}$ |
| 39 | [-1, -2, 1] | $\displaystyle{1 + \sqrt{2}}$ |
| 40 | [-1, -2, 1] | $\displaystyle{1 - \sqrt{2}}$ |
| 41 | [-1, 0, 3] | $\displaystyle{\frac{\sqrt{3}}{3}}$ |
| 42 | [-1, 0, 3] | $\displaystyle{-\frac{\sqrt{3}}{3}}$ |
| 43 | [-1, 2, 1] | $\displaystyle{-1 + \sqrt{2}}$ |
| 44 | [-1, 2, 1] | $\displaystyle{-1 - \sqrt{2}}$ |
| 45 | [1, -1, 2] | $\displaystyle{\frac{1 + \sqrt{-7}}{4}}$ |
| 46 | [1, -1, 2] | $\displaystyle{\frac{1 - \sqrt{-7}}{4}}$ |
| 47 | [1, 0, 3] | $\displaystyle{\frac{\sqrt{-3}}{3}}$ |
| 48 | [1, 0, 3] | $\displaystyle{-\frac{\sqrt{-3}}{3}}$ |
| 49 | [1, 1, 2] | $\displaystyle{\frac{-1 + \sqrt{-7}}{4}}$ |
| 50 | [1, 1, 2] | $\displaystyle{\frac{-1 - \sqrt{-7}}{4}}$ |
| 51 | [2, -1, 1] | $\displaystyle{\frac{1 + \sqrt{-7}}{2}}$ |
| 52 | [2, -1, 1] | $\displaystyle{\frac{1 - \sqrt{-7}}{2}}$ |
| 53 | [2, 1, 1] | $\displaystyle{\frac{-1 + \sqrt{-7}}{2}}$ |
| 54 | [2, 1, 1] | $\displaystyle{\frac{-1 - \sqrt{-7}}{2}}$ |
| 55 | [3, 0, 1] | $\displaystyle{\sqrt{-3}}$ |
| 56 | [3, 0, 1] | $\displaystyle{-\sqrt{-3}}$ |
| 57 | [-2, 0, 0, 1] | $\displaystyle{{2}^{1 / 3}}$ |
| 58 | [-2, 0, 0, 1] | $\displaystyle{{2}^{1 / 3} \frac{-1 + \sqrt{-3}}{2}}$ |
| 59 | [-2, 0, 0, 1] | $\displaystyle{{2}^{1 / 3} \frac{-1 - \sqrt{-3}}{2}}$ |
| 60 | [-1, -1, 0, 1] | $\displaystyle{\left(\text{Root }\, x \approx {1.32472} \;\text{ of } \;{ x^{3}- x-1}\right)}$ |
| 61 | [-1, -1, 0, 1] | $\displaystyle{\left(\text{Root }\, x \approx {-0.662359 + 0.562280 i} \;\text{ of } \;{ x^{3}- x-1}\right)}$ |
| 62 | [-1, -1, 0, 1] | $\displaystyle{\left(\text{Root }\, x \approx {-0.662359-0.562280 i} \;\text{ of } \;{ x^{3}- x-1}\right)}$ |
| 63 | [-1, 0, -1, 1] | $\displaystyle{\left(\text{Root }\, x \approx {1.46557} \;\text{ of } \;{ x^{3}- x^{2}-1}\right)}$ |
| 64 | [-1, 0, -1, 1] | $\displaystyle{\left(\text{Root }\, x \approx {-0.232786 + 0.792552 i} \;\text{ of } \;{ x^{3}- x^{2}-1}\right)}$ |
| 65 | [-1, 0, -1, 1] | $\displaystyle{\left(\text{Root }\, x \approx {-0.232786-0.792552 i} \;\text{ of } \;{ x^{3}- x^{2}-1}\right)}$ |
| 66 | [-1, 0, 0, 2] | $\displaystyle{{\left(\frac{1}{2}\right)}^{1 / 3}}$ |
| 67 | [-1, 0, 0, 2] | $\displaystyle{{\left(\frac{1}{2}\right)}^{1 / 3} \frac{-1 + \sqrt{-3}}{2}}$ |
| 68 | [-1, 0, 0, 2] | $\displaystyle{{\left(\frac{1}{2}\right)}^{1 / 3} \frac{-1 - \sqrt{-3}}{2}}$ |
| 69 | [-1, 0, 1, 1] | $\displaystyle{\left(\text{Root }\, x \approx {0.754878} \;\text{ of } \;{ x^{3}+ x^{2}-1}\right)}$ |
| 70 | [-1, 0, 1, 1] | $\displaystyle{\left(\text{Root }\, x \approx {-0.877439 + 0.744862 i} \;\text{ of } \;{ x^{3}+ x^{2}-1}\right)}$ |
| 71 | [-1, 0, 1, 1] | $\displaystyle{\left(\text{Root }\, x \approx {-0.877439-0.744862 i} \;\text{ of } \;{ x^{3}+ x^{2}-1}\right)}$ |
| 72 | [-1, 1, 0, 1] | $\displaystyle{\left(\text{Root }\, x \approx {0.682328} \;\text{ of } \;{ x^{3}+ x-1}\right)}$ |
| 73 | [-1, 1, 0, 1] | $\displaystyle{\left(\text{Root }\, x \approx {-0.341164 + 1.16154 i} \;\text{ of } \;{ x^{3}+ x-1}\right)}$ |
| 74 | [-1, 1, 0, 1] | $\displaystyle{\left(\text{Root }\, x \approx {-0.341164-1.16154 i} \;\text{ of } \;{ x^{3}+ x-1}\right)}$ |
| 75 | [1, -1, 0, 1] | $\displaystyle{\left(\text{Root }\, x \approx {-1.32472} \;\text{ of } \;{ x^{3}- x+1}\right)}$ |
| 76 | [1, -1, 0, 1] | $\displaystyle{\left(\text{Root }\, x \approx {0.662359 + 0.562280 i} \;\text{ of } \;{ x^{3}- x+1}\right)}$ |
| 77 | [1, -1, 0, 1] | $\displaystyle{\left(\text{Root }\, x \approx {0.662359-0.562280 i} \;\text{ of } \;{ x^{3}- x+1}\right)}$ |
| 78 | [1, 0, -1, 1] | $\displaystyle{\left(\text{Root }\, x \approx {-0.754878} \;\text{ of } \;{ x^{3}- x^{2}+1}\right)}$ |
| 79 | [1, 0, -1, 1] | $\displaystyle{\left(\text{Root }\, x \approx {0.877439 + 0.744862 i} \;\text{ of } \;{ x^{3}- x^{2}+1}\right)}$ |
| 80 | [1, 0, -1, 1] | $\displaystyle{\left(\text{Root }\, x \approx {0.877439-0.744862 i} \;\text{ of } \;{ x^{3}- x^{2}+1}\right)}$ |
| 81 | [1, 0, 0, 2] | $\displaystyle{-{\left(\frac{1}{2}\right)}^{1 / 3}}$ |
| 82 | [1, 0, 0, 2] | $\displaystyle{{\left(-\frac{1}{2}\right)}^{1 / 3}}$ |
| 83 | [1, 0, 0, 2] | $\displaystyle{{\left(-\frac{1}{2}\right)}^{1 / 3} \frac{-1 - \sqrt{-3}}{2}}$ |
| 84 | [1, 0, 1, 1] | $\displaystyle{\left(\text{Root }\, x \approx {-1.46557} \;\text{ of } \;{ x^{3}+ x^{2}+1}\right)}$ |
| 85 | [1, 0, 1, 1] | $\displaystyle{\left(\text{Root }\, x \approx {0.232786 + 0.792552 i} \;\text{ of } \;{ x^{3}+ x^{2}+1}\right)}$ |
| 86 | [1, 0, 1, 1] | $\displaystyle{\left(\text{Root }\, x \approx {0.232786-0.792552 i} \;\text{ of } \;{ x^{3}+ x^{2}+1}\right)}$ |
| 87 | [1, 1, 0, 1] | $\displaystyle{\left(\text{Root }\, x \approx {-0.682328} \;\text{ of } \;{ x^{3}+ x+1}\right)}$ |
| 88 | [1, 1, 0, 1] | $\displaystyle{\left(\text{Root }\, x \approx {0.341164 + 1.16154 i} \;\text{ of } \;{ x^{3}+ x+1}\right)}$ |
| 89 | [1, 1, 0, 1] | $\displaystyle{\left(\text{Root }\, x \approx {0.341164-1.16154 i} \;\text{ of } \;{ x^{3}+ x+1}\right)}$ |
| 90 | [2, 0, 0, 1] | $\displaystyle{-{2}^{1 / 3}}$ |
| 91 | [2, 0, 0, 1] | $\displaystyle{{\left(-2\right)}^{1 / 3}}$ |
| 92 | [2, 0, 0, 1] | $\displaystyle{{\left(-2\right)}^{1 / 3} \frac{-1 - \sqrt{-3}}{2}}$ |
| 93 | [1, 0, 0, 0, 1] | $\displaystyle{e^{\pi i / 4}}$ |
| 94 | [1, 0, 0, 0, 1] | $\displaystyle{e^{7 \pi i / 4}}$ |
| 95 | [1, 0, 0, 0, 1] | $\displaystyle{e^{3 \pi i / 4}}$ |
| 96 | [1, 0, 0, 0, 1] | $\displaystyle{e^{5 \pi i / 4}}$ |
Quick hack code that I used to generate the table with the help of Calcium:
from flint import *
from pyca import qqbar
import itertools
def enum(index):
allps = []
numnum = 0
for d in range(1,index):
R = range(-index,index+1)
pd = itertools.product(*([R for i in range(d)] + [[c for c in R if c > 0]]))
for p in pd:
if sum(abs(c) for c in p) + d == index:
allps.append(p)
numnum += d
return allps
def isprimitive(f):
c, fs = f.factor()
return c == 1 and len(fs) == 1 and fs[0][1] == 1
count = 0
for ind in range(2,7):
for pol in enum(ind):
if isprimitive(fmpz_poly(list(pol))):
roots = qqbar.polynomial_roots(list(pol))
for r in roots:
print("%i %s $\displaystyle{%s}$
The ordering is not exactly as that shown on the OEIS wiki page (there are also some errors in the OEIS wiki table). The enumeration function can of course be tweaked; for example, it would surely be more elegant if the grading function favored sparsity more strongly so that the ubiquitous eighth roots of unity appeared earlier! Aesthetics aside, it would be neat if there was some agreed-upon enumeration function so that one could just write, say, $A(84)$ for the real root of $x^3+x^2+1$.
Actually, the function $A$ described above is rather useless since it does not allow "random access". It is easy to enumerate the first few thousand algebraic numbers with this definition, but it is completely infeasible to compute $A(10^{30})$ or to find the unique $n$ such that $A(n) = \cos(2 \pi / 37)$. The underlying difficulty is that it seems very hard to count irreducible polynomials among all polynomials. We could avoid this problem by designing an enumeration function $B : \mathbb{N} \to \overline{\mathbb{Q}}$ that gives $B(n) = 0$ repeatedly (when the internally enumerated polynomial is reducible) and a unique element of $\overline{\mathbb{Q}} \setminus \{0\}$ otherwise. It could be a fun small research project to design some appropriate graded lexicographic order together with an explicit, efficiently computable $B$ (and $B^{-1}$) such that $B(n) = 0$ entries are as sparse as realistically possible. (If such a function were published, it could serve as a standardized, portable way to encode algebraic numbers. I'm only half joking.)
fredrikj.net |
Blog index |
RSS feed |
Follow me on Mastodon |
Become a sponsor