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