7
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ See the slides How to Find Algebraic Relations? An important component algorithm is the LLL lattice basis reduction algorithm $\endgroup$
    – hardmath
    Aug 29, 2020 at 0:02
  • $\begingroup$ @hardmath Briefly looking at those slides, they seem to explain finding relations among sequences - does that apply to individual constants? $\endgroup$
    – Jair Taylor
    Aug 29, 2020 at 0:16
  • 1
    $\begingroup$ You can try an inverse symbolic calculator. $\endgroup$
    – Jair Taylor
    Aug 29, 2020 at 0:17
  • 3
    $\begingroup$ @JairTaylor: I believe the problem here is to find an integer relation among the natural powers of a constant, thereby establishing that the constant is algebraic. Detecting integer relations has many applications, and this one in particular. $\endgroup$
    – hardmath
    Aug 29, 2020 at 1:02
  • 1
    $\begingroup$ @hardmath I see, so you're looking for a recurrence relation for the sequence $x,x^2,x^3, \ldots$? That makes sense, thank you. $\endgroup$
    – Jair Taylor
    Aug 29, 2020 at 15:15

3 Answers 3

Reset to default
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

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

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

Ordner was introduced in a blog post by Fredrik Johansson:

$\endgroup$
1
  • $\begingroup$ Thank you for the response. I had a hard time deciding which answer to choose, but your response has been very helpful as well. $\endgroup$
    – ReverseFlowControl
    Mar 20, 2022 at 2:48
1
$\begingroup$

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}$).

$\endgroup$
8
  • 1
    $\begingroup$ It is. I can verify it with other facts in my problem once I have it. $\endgroup$
    – ReverseFlowControl
    Aug 29, 2020 at 0:27
  • 1
    $\begingroup$ So you want an algorithm which takes a decimal approximation of a number and guesses an algebraic number which is close to that approximation? Then you'll need to be more specific about what kinds of algebraic numbers you're looking for, since the algebraic numbers are dense in $\mathbb{R}$. For that matter, the decimal approximation itself is rational (hence algebraic), so that would always be the best guess if you don't narrow down your search. $\endgroup$
    – diracdeltafunk
    Aug 29, 2020 at 1:02
  • 2
    $\begingroup$ Every complex number is "algebraic over the complex numbers," so that is likely not your actual problem. What is tractable is to take successive natural powers of your constant (known to specified accuracy) and use a basis reduction algorithm to determine either an integer relation among those powers or that none exists with integer coefficients below an effectively computable bound. $\endgroup$
    – hardmath
    Aug 29, 2020 at 2:05
  • 2
    $\begingroup$ @diracdeltafunk Your objections are valid, but there is a way to make the OP's question precise. For instance, if we consider the floating point approximation as a rational number, its (degree $1$) minimal polynomial will have enormous coefficients, so we would intuit that this is a "bad" guess. To use LLL, one specifies a bound on the degree of the minimal polynomial, and then looks for possible minimal polynomials that are "small" in a certain sense by turning it into the problem of finding a short vector in a lattice. $\endgroup$
    – Viktor Vaughn
    Aug 29, 2020 at 6:26
  • 1
    $\begingroup$ @RichardD.James Thank you! This is very helpful and clears up my confusion about the question. $\endgroup$
    – diracdeltafunk
    Aug 29, 2020 at 6:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .