5
$\begingroup$

Suppose you calculate the first few (dozen, hundred) digits of a number which you believe to be a rational number. You can calculate the continued fraction for the number and truncate after a large number:

$$ 0.67272727272727745455778089309\approx[0; 1, 2, 17, 1, 69929887587, 5, 1, 1, 2, 2] $$

is probably $[0; 1, 2, 17, 1]=37/55.$

I'm wondering if there is a similarly good method for finding an algebraic number, ideally one that I can use in some computer system since large numbers are hard to work with by hand.

  • 2
    [RootApproximant](http://reference.wolfram.com/mathematica/ref/RootApproximant.html) in _Mathematica_ does just that, if you have access to it. Implementing similar algorithm requires access to lattice reduction algorithm, such as [LLL](http://mathworld.wolfram.com/LLLAlgorithm.html) or [PSLQ](http://mathworld.wolfram.com/PSLQAlgorithm.html).2012-01-31
  • 0
    `algdep` works on PARI/GP.2013-07-08
  • 0
    Python's `mpmath` module has a `findpoly` function.2014-03-23

1 Answers 1

10

Yes, PLSQ is used on the finite set $\{1, \; \lambda, \; \lambda^2, \; \ldots, \; \lambda^n \}$ in hopes of finding a polynomial with integer coefficients for which the number $\lambda$ is a root. If such is found, sometimes the apparent relation can be proved to be correct.

  • 0
    Wow, it's that easy? Thanks!2012-01-31
  • 0
    Any idea how I can tell if I've found the answer? With rational numbers, I can use the Gauss-Kuzmin distribution to quantify "large", which helps distinguish between things that are close (rational approximation to pi) from those which are unusually close and likely to be 'the' answer. Anything similar here?2012-01-31
  • 0
    @Charles I don't know. Borwein, Borwein, Bailey, and Plouffe are the big names here. I imagine they have some surveys or discussion of purely technical aspects interspersed with their articles giving the proved results. Part of it is, do you have any good reason to think the number is algebraic in the first place?2012-01-31
  • 0
    Coefficients of Binet formulas are algebraic, right? That's one application. I guess the characteristic polynomial gives clues as to the extension field if one knows how to look, but this seems like something that should be done automatically rather than by hand.2012-01-31