How should I approximate real numbers by algebraic ones? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T16:53:04Z http://mathoverflow.net/feeds/question/2861 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/2861/how-should-i-approximate-real-numbers-by-algebraic-ones How should I approximate real numbers by algebraic ones? Scott Morrison 2009-10-27T18:27:59Z 2010-07-24T18:37:51Z <p>Given a high precision real number, how should I go about guessing an algebraic integer that it's close to?</p> <p>Of course, this is extremely poorly defined -- every real number is close to a rational number, of course! But I'd like to keep both the coefficients and the degree relatively small. Obviously we can make tradeoffs between how much we dislike large coefficents and how much we dislike large degrees.</p> <p>But that aside, I don't even know how you'd start. Any ideas?</p> <p><strong>Background</strong>: this comes out of the project that prompted Noah's <a href="http://mathoverflow.net/questions/2396/solving-polynomial-equations-when-you-know-in-which-number-field-the-solutions-li" rel="nofollow">recent question</a> on solving large systems of quadratics. We're trying to find subfactors inside their graph planar algebras. We've found that solving quadratics numerically, approximating the solutions by algebraic integers, and then checking that these are actually exact solutions is very effective. So far, we've been making use of Mathematica's "<a href="http://reference.wolfram.com/mathematica/ref/RootApproximant.html" rel="nofollow">RootApproximant</a>" function which does exactly what I ask here, but it's an impenetrable black box, like everything out of Wolfram.</p> http://mathoverflow.net/questions/2861/how-should-i-approximate-real-numbers-by-algebraic-ones/2863#2863 Answer by Alon Amit for How should I approximate real numbers by algebraic ones? Alon Amit 2009-10-27T18:39:52Z 2010-02-19T04:06:51Z <p>Basically you're looking for a small integral relation among the powers of the given number. This can be done effectively with the LLL algorithm (Lenstra-Lenstra-Lovasz) and variations of it (especially PSLQ), and indeed this approach is used to determine "inverse symbolic" candidates for an approximate real number. Look up papers by Plouffe and Bailey such as <a href="http://www.google.com/url?sa=t&amp;source=web&amp;ct=res&amp;cd=4&amp;ved=0CBYQFjAD&amp;url=http%3A%2F%2Fcrd.lbl.gov%2F~dhbailey%2Fdhbpapers%2Fpslq-cse.pdf&amp;ei=Mj3nSp-zCpjYtAPXi%5FybAQ&amp;usg=AFQjCNGnae-chOA%5FWdif1Tmhs4BwvX3sSA&amp;sig2=vor2JXGPKLko3BBxRZXiwQ" rel="nofollow">this one</a>. </p> http://mathoverflow.net/questions/2861/how-should-i-approximate-real-numbers-by-algebraic-ones/2864#2864 Answer by engelbrekt for How should I approximate real numbers by algebraic ones? engelbrekt 2009-10-27T18:41:26Z 2009-10-27T18:41:26Z <p>The Lenstra-Lenstra-Lovasz lattice basis reduction algorithm is what you need. Suppose that your real number is a and you want a quadratic equation with as small coefficients as possible, of which a is nearly a root. Then calculate 1,a,a^2 (to some precision), find a nontrivial integer relation between them, and use the LLL algorithm to find a much better one from the first one. Exactly this example is discussed in the Wikipedia entry on the LLL algorithm, applied to the Golden Section number. And there is a big literature on the algorithm and its many applications. (For higher degree, calculate 1,a,a^2,...,a^n).</p> http://mathoverflow.net/questions/2861/how-should-i-approximate-real-numbers-by-algebraic-ones/33217#33217 Answer by Anweshi for How should I approximate real numbers by algebraic ones? Anweshi 2010-07-24T18:37:51Z 2010-07-24T18:37:51Z <p>I do not know about algebraic number approximations; but the most canonical approximation to real numbers by rational numbers is the <a href="http://en.wikipedia.org/wiki/Continued_fraction" rel="nofollow">continued fraction expansion</a>. They and their convergents (of first or second orders) are in many senses the best approximations to a real number by a rational number. These are simple to prove, but I do not want to get into it here. When you have a free weekend instead of reading some novel you can have a look at Khintchine's book "Continued Fractions", in which everything is explained very clearly.</p> <p>For approximation with algebraic numbers, I suppose some experts on <a href="http://en.wikipedia.org/wiki/Mahler_measure" rel="nofollow">Mahler measure</a> can contribute something.</p> <p>This is an answer more theoretical in spirit compared to the algorithmic ones given so far.</p>