function to check for algebraic dependence given a list of polynomials

[Alex Raichev]

Hi all:

As a newbie Sage contributor, i thought it would be good practice to
submit small chunks of code (instead of big ones like what i recently
submitted). So i wrote a useful little function to check algebraic
dependence for a given list of polynomials (documentation below). I'd
like to get it incorporated into Sage, but where in the Sage library
should i propose to put it? If it operated on a single polynomial,
then i think i would add it as a method to the class
MPolynomial_libsingular(sage.rings.polynomial.multi_polynomial.MPolynomial).
But it operates on a list of polynomials. Any advice?

Alex

def alg_dep(fs):
r"""
This function returns an irreducible annihilating polynomial for
the
polynomials in `fs`, if those polynomials are algebraically
dependent.
Otherwise it returns 0.

INPUT:

- ``fs`` - A list of polynomials `f_1,\ldots,f_r` from a common
polynomial
ring.

OUTPUT:

If the polynomials in `fs` are algebraically dependent, then the
output is an irreducible polynomial `g` in `R[T_1,...,T_r]` such
that
`g(f_1,\ldots,f_r) = 0`.
If the polynomials in `fs` are algebraically independent, then the
output
is 0.
"""

[Simon King]

Hi Alex!

On 6 Jan., 04:15, Alex Raichev <tortoise.s...@gmail.com> wrote:
> As a newbie Sage contributor, i thought it would be good practice to
> submit small chunks of code (instead of big ones like what i recently
> submitted).

First of all, thank you for contributing to Sage! And I think it is a
good thing to start with something small.

> So i wrote a useful little function to check algebraic
> dependence for a given list of polynomials (documentation below).  I'd
> like to get it incorporated into Sage, but where in the Sage library
> should i propose to put it?  If it operated on a single polynomial,
> then i think i would add it as a method to the class
> MPolynomial_libsingular(sage.rings.polynomial.multi_polynomial.MPolynomial).
> But it operates on a list of polynomials.  Any advice?

I agree that it should be a method, not a function. The doc string
that you provide gives some idea where it could be put.

>     INPUT:
>
>     - ``fs`` - A list of polynomials `f_1,\ldots,f_r` from a common
> polynomial ring.

Since f_1,...,f_r all belong to the same polynomial ring R, why not
make it a method of a polynomial ring? There are different
implementations of polynomial rings, but I suppose that your code
relies on libsingular. So, why not
sage.rings.polynomial.multi_polynomial_libsingular.MPolynomialRing_libsingular?
If the code is generic, then of course it should better be put into
sage.rings.polynomial.multi_polynomial_ring_generic.MPolynomialRing_generic

Alternatively, it could be a method of polynomial ideals, since ideals
in Sage have a fixed list of generators - like f_1,...,f_r.

Do you already have a trac account and know how patches are submitted
and refereed?

Best regards,
Simon

[Alex Raichev]

Thanks for your advice, Simon. Sounds like
sage.rings.polynomial.multi_polynomial_ideal.MPolynomialIdeal would be
a good class choice. I do have a trac account ('araichev') and have
read about patches but have not actually submitted one yet. So i'll
get on that by submitting my simple alg_dep method.

Alex

[Martin Albrecht]

On Thursday 06 January 2011, Simon King wrote:
> Alternatively, it could be a method of polynomial ideals, since ideals
> in Sage have a fixed list of generators - like f_1,...,f_r.

While that's true note that in principle the design is such that we
distinguish between ideals and their generating sets. For example: reduction
by an ideal f.reduce() is different from reduction by a list of generators.

Also, this is the reason why the interreduced_basis() is somewhat awkwardly
named: it shouldn't be a function on ideals but we didn't really have any
other object. mq.MPolynomialSystem might be a good candidate for stuff that
really works with polynomial lists but it would have to be moved away from the
crypto module first.

Cheers,
Martin

--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://martinralbrecht.wordpress.com/
_jab: martinr...@jabber.ccc.de

[Alex Raichev]

I had some library problems in creating a Sage sandbox but resolved
them with the help of ask.sagemath.org. So now i'm back into
submitting to Sage a function that checks whether a list of
polynomials is algebraically independent. Since my function uses an
elimination ideal, i took Simon's advice and added it as a method of
the class
sage.rings.polynomial.multi_polynomial_libsingular.MPolynomialRing_libsingular.
Then i ran into trouble, because that class is written in Cython, i
only know Python, and my code is written in Sage. Man, this is
getting difficult, and yet my function is so simple!

So do i need to convert my code to Cython? For concreteness, here's
the code, which is short. The examples are kind of bogus, because,
while the answers are correct ---i got them by running a non-object-
oriented version of the method--- the syntax of the calls currently
doesn't work.

Alex

====================================
def algebraic_dependence(self,fs):
r"""
Returns an irreducible annihilating polynomial for the polynomials
in the
list `fs`, if those polynomials are algebraically dependent.
Otherwise returns the zero polynomial.

INPUT:

- ``fs`` - A list of polynomials `f_1,\ldots,f_r' from self.

OUTPUT:

If the polynomials in the list `fs` are algebraically dependent,
then the
output is an irreducible polynomial `g` in `K[T_1,\ldots,T_r]`

such that
`g(f_1,\ldots,f_r) = 0`.

Here `K` is the coefficient ring of self and `T_1,\ldots,T_r` are
indeterminates different from those of self.

If the polynomials in `fs` are algebraically independent, then the
output

is the zero polynomial.

EXAMPLES::

sage: R.<x>= PolynomialRing(QQ)
sage: fs= [x-3, x^2+1]
sage: g= R.algebraic_dependence(fs); g
10 + 6*T0 - T1 + T0^2
sage: g(fs)
0

::

sage: R.<w,z>= PolynomialRing(QQ)
sage: fs= [w, (w^2 + z^2 - 1)^2, w*z - 2]
sage: g= R.algebraic_dependence(fs); g
16 + 32*T2 - 8*T0^2 + 24*T2^2 - 8*T0^2*T2 + 8*T2^3 + 9*T0^4 -
2*T0^2*T2^2 + T2^4 - T0^4*T1 + 8*T0^4*T2 - 2*T0^6 + 2*T0^4*T2^2 + T0^8
sage: g(fs)
0
sage: g.parent()
Multivariate Polynomial Ring in T0, T1, T2 over Rational Field

::

sage: R.<x,y,z>= PolynomialRing(GF(7))
sage: fs= [x*y,y*z]
sage: g= R.algebraic_dependence(fs); g
0

AUTHORS:

-Alexander Raichev (2011-01-06)
"""
r= len(fs)
R= self
B= R.base_ring()
Xs= list(R.gens())
d= len(Xs)

# Expand R by r new variables.
T= 'T'
while T in [str(x) for x in Xs]:
T= T+'T'
Ts= [T + str(j) for j in range(r)]
RR= PolynomialRing(B,d+r,tuple(Xs+Ts))
Vs= list(RR.gens())
Xs= Vs[0:d]
Ts= Vs[d:]

# Find an irreducible annihilating polynomial g for the fs if
there is one.
J= ideal([ Ts[j] -RR(fs[j]) for j in range(r)])
JJ= J.elimination_ideal(Xs)
g= JJ.gens()[0]

# Shrink the ambient ring of g to include only Ts.
# Using the negdeglex because i find it convenient in my work.
RRR= PolynomialRing(B,r,tuple(Ts),order='negdeglex')
return RRR(g)

[Martin Albrecht]

On Wednesday 12 January 2011, Alex Raichev wrote:
> I had some library problems in creating a Sage sandbox but resolved
> them with the help of ask.sagemath.org. So now i'm back into
> submitting to Sage a function that checks whether a list of
> polynomials is algebraically independent. Since my function uses an
> elimination ideal, i took Simon's advice and added it as a method of
> the class
> sage.rings.polynomial.multi_polynomial_libsingular.MPolynomialRing_libsingu
> lar.

I still think that mq.MPolynomialSystem would be a good class, since
essentially implements a list of polynomials in light of the fact that we
don't identify lists of polynomials and ideals in Sage. Of course, it should
be moved to sage.rings.polynomial (I can do that, so you don't have to worry
about that).

> Then i ran into trouble, because that class is written in Cython, i
> only know Python, and my code is written in Sage. Man, this is
> getting difficult, and yet my function is so simple!

Just drop your code into the class of your choice - Python or Cython. Cython
implements most of Python's syntax, so your code should just work.

[Alex Raichev]

Cool beans, Martin. I'll take your advice and pop the method into
mq.MPolynomialSystem after you move the class into
sage.rings.polynomial.

Thanks.
Alex

On Jan 13, 12:21 pm, Martin Albrecht <martinralbre...@googlemail.com>
wrote:

> _jab: martinralbre...@jabber.ccc.de