Sharedsupport / 2014-11-06-algdep.sagewsOpen in CoCalc
Authors: Harald Schilly, ℏal Snyder, William A. Stein
License: GNU General Public License v3.0
Description: Examples for support purposes.
a = N((2/3)^(1/5)); a
0.922107911481728
algdep?
File: /usr/local/sage/sage-6.3.beta6/local/lib/python2.7/site-packages/sage/rings/arith.py Signature : algdep(z, degree, known_bits=None, use_bits=None, known_digits=None, use_digits=None, height_bound=None, proof=False) Docstring : Returns a polynomial of degree at most degree which is approximately satisfied by the number z. Note that the returned polynomial need not be irreducible, and indeed usually won't be if z is a good approximation to an algebraic number of degree less than degree. You can specify the number of known bits or digits of z with "known_bits=k" or "known_digits=k". PARI is then told to compute the result using 0.8k of these bits/digits. Or, you can specify the precision to use directly with "use_bits=k" or "use_digits=k". If none of these are specified, then the precision is taken from the input value. A height bound may be specified to indicate the maximum coefficient size of the returned polynomial; if a sufficiently small polynomial is not found, then "None" will be returned. If "proof=True" then the result is returned only if it can be proved correct (i.e. the only possible minimal polynomial satisfying the height bound, or no such polynomial exists). Otherwise a "ValueError" is raised indicating that higher precision is required. ALGORITHM: Uses LLL for real/complex inputs, PARI C-library "algdep" command otherwise. Note that "algebraic_dependency" is a synonym for "algdep". INPUT: * "z" - real, complex, or p-adic number * "degree" - an integer * "height_bound" - an integer (default: "None") specifying the maximum coefficient size for the returned polynomial * "proof" - a boolean (default: "False"), requires height_bound to be set EXAMPLES: sage: algdep(1.888888888888888, 1) 9*x - 17 sage: algdep(0.12121212121212,1) 33*x - 4 sage: algdep(sqrt(2),2) x^2 - 2 This example involves a complex number: sage: z = (1/2)*(1 + RDF(sqrt(3)) *CC.0); z 0.500000000000000 + 0.866025403784439*I sage: p = algdep(z, 6); p x^3 + 1 sage: p.factor() (x + 1) * (x^2 - x + 1) sage: z^2 - z + 1 0.000000000000000 This example involves a p-adic number: sage: K = Qp(3, print_mode = 'series') sage: a = K(7/19); a 1 + 2*3 + 3^2 + 3^3 + 2*3^4 + 2*3^5 + 3^8 + 2*3^9 + 3^11 + 3^12 + 2*3^15 + 2*3^16 + 3^17 + 2*3^19 + O(3^20) sage: algdep(a, 1) 19*x - 7 These examples show the importance of proper precision control. We compute a 200-bit approximation to sqrt(2) which is wrong in the 33'rd bit: sage: z = sqrt(RealField(200)(2)) + (1/2)^33 sage: p = algdep(z, 4); p 227004321085*x^4 - 216947902586*x^3 - 99411220986*x^2 + 82234881648*x - 211871195088 sage: factor(p) 227004321085*x^4 - 216947902586*x^3 - 99411220986*x^2 + 82234881648*x - 211871195088 sage: algdep(z, 4, known_bits=32) x^2 - 2 sage: algdep(z, 4, known_digits=10) x^2 - 2 sage: algdep(z, 4, use_bits=25) x^2 - 2 sage: algdep(z, 4, use_digits=8) x^2 - 2 Using the "height_bound" and "proof" parameters, we can see that pi is not the root of an integer polynomial of degree at most 5 and coefficients bounded above by 10: sage: algdep(pi.n(), 5, height_bound=10, proof=True) is None True For stronger results, we need more precicion: sage: algdep(pi.n(), 5, height_bound=100, proof=True) is None Traceback (most recent call last): ... ValueError: insufficient precision for non-existence proof sage: algdep(pi.n(200), 5, height_bound=100, proof=True) is None True sage: algdep(pi.n(), 10, height_bound=10, proof=True) is None Traceback (most recent call last): ... ValueError: insufficient precision for non-existence proof sage: algdep(pi.n(200), 10, height_bound=10, proof=True) is None True We can also use "proof=True" to get positive results: sage: a = sqrt(2) + sqrt(3) + sqrt(5) sage: algdep(a.n(), 8, height_bound=1000, proof=True) Traceback (most recent call last): ... ValueError: insufficient precision for uniqueness proof sage: f = algdep(a.n(1000), 8, height_bound=1000, proof=True); f x^8 - 40*x^6 + 352*x^4 - 960*x^2 + 576 sage: f(a).expand() 0 TESTS: sage: algdep(complex("1+2j"), 4) x^2 - 2*x + 5
algdep(a,5)
3*x^5 - 2