Sharedsupport / 2014-11-06-algdep.sagewsOpen in CoCalc
Authors: Harald Schilly, ℏal Snyder, William A. Stein
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
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