Determine if a number is algebraic.

Question

I recall there is an algorithm involving lattices that would tell me if a given number(approximation) is an algebraic number or not, along with the exact algebraic form of the number. Is there any tool (Gap, Mathematica, python package, etc) that has an implementation of this?

I have numbers which I can approximate to any degree of accuracy I want and I would like to know if they are algebraic or not.

Answer 1

Yes, there is an implementation in Magma called MinimalPolynomial (there is also a deprecated command PowerRelation). It takes as arguments the floating point approximation and a bound on the degree of the desired minimal polynomial. You can try it out using the online Magma calculator.

Here's an example recognizing $\sqrt{2}$. First let's get its floating point approximation.

K<a> := QuadraticField(2);
places := InfinitePlaces(K);
nu := places[1];
approx := Evaluate(a,nu);
approx;

This outputs

1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659

Now we compute a likely algebraic relation

MinimalPolynomial(approx,2);

which outputs

$.1^2 - 2
1.6958303447609538905660350145496826911258884898871672008389210380315213081007910443386606153581914903410305676643102063857015146129982219146054751103274804089508645103E-167

which is the polynomial $x^2 - 2$ and the error.

As others have pointed out, this command won't tell you for certain that your floating point number is algebraic; it simply says that there exists an algebraic number of degree $\leq d$ whose floating point approximation (under an embedding into $\mathbb{C}$) is close to the given approximation, and whose minimal polynomial is small, in some sense. The key is the LLL algorithm, which finds short vectors relative to a lattice.

Answer 2

I have numbers which I can approximate to any degree of accuracy I want and I would like to know if they are algebraic or not.

Unless I'm misunderstanding the question, this is not decidable in finite time. For example, you might check that the first 10000000000000 digits of your number agree with $\sqrt{2}$, but you will never be able to verify that all of the digits agree with $\sqrt{2}$ (i.e. that the number is $\sqrt{2}$).

Answer 3

PARI has a function algdep which does exactly what you describe:

• https://pari.math.u-bordeaux.fr/dochtml/html/Vectors__matrices__linear_algebra_and_sets.html#algdep

SageMath wraps that PARI function, also under the name algdep:

• https://doc.sagemath.org/html/en/reference/rings_standard/sage/arith/misc.html#sage.arith.misc.algdep

Sort of related, Ordner is a directory of real numbers:

• http://fungrim.org/ordner/

Ordner was introduced in a blog post by Fredrik Johansson:

• http://fredrikj.net/blog/2019/09/what-is-the-most-common-real-number/