Listing all polynomials of a given degree

[Noel]

Hello Y'all,

What's the best way of listing all polynomials of a given degree with
coefficients in a finite field?

Thank you!

NS

[Nick Alexander]

On 9-Mar-09, at 8:48 AM, Noel wrote:

>
> Hello Y'all,
>
> What's the best way of listing all polynomials of a given degree with
> coefficients in a finite field?

If you want a one liner, you could use

sage: [ GF(3)['x'](list(t)) for t in (GF(3)^2) ]
[0, 1, 2, x, x + 1, x + 2, 2*x, 2*x + 1, 2*x + 2]

Nick

[YannLC]

if you want another one liner, and an exact degree, you could use

list(GF(3)['x'].polynomials(of_degree=2))

Yann

[Nicolas M. Thiery]

Nice one. Here is a variant for homogeneous multivariate polynomials.
It's longer than one line :-) But the two first functions are standard
utilies that I would like to see in Sage (volunteers?)

Cheers,
Nicolas

K = IntegerModRing(2)
P = K['x,y']
n = 2 # num variables

def term(exponents):
"""
Return the term of P with the given exponent vector.

This should be a method of P, with a fast implementation using the
internal data structure!!!

Should this be term or monomial? The names in
CombinatorialFreeModule should be named accordingly

EXAMPLES:
sage: term([3,2])
x^3*y^2
"""
return prod((x^e for (x,e) in zip(P.gens(), exponents)), P(1))

def basis(d):
"""
Returns a basis of the homogeneous component of P of degree d.

This should be a method of P, available under:

EXAMPLES:
sage: b = P.basis().subset(degree=d)
sage: b.cardinality()
sage: 4
sage: list(b)
sage: [x^3, x^2*y, x*y^2, y^3]
"""
return IntegerVectors(d, n).map(term)

def all_polynomials(d):
"""
Returns all the homogeneous polynomials of P of degree d

This should be a method of P, available under something like:

EXAMPLES:
sage: P.subset(degree = 3, homogeneous = True)
[0,
y^3,
x*y^2,
x*y^2 + y^3,
x^2*y,
x^2*y + y^3,
x^2*y + x*y^2,
x^2*y + x*y^2 + y^3,
x^3,
x^3 + y^3,
x^3 + x*y^2,
x^3 + x*y^2 + y^3,
x^3 + x^2*y,
x^3 + x^2*y + y^3,
x^3 + x^2*y + x*y^2,
x^3 + x^2*y + x*y^2 + y^3]

"""
monomials = list(basis(d))
#
def coeff_to_poly(coeffs):
return sum( (c*m for (c,m) in zip(coeffs, monomials)), P.zero_element())
# We are missing CartesianPower here
return CartesianProduct(*[K for i in range(exponents.cardinality())]).map(coeff_to_poly)

count(all_polynomials(3))
16

list(all_polynomials(3))

[0,
y^3,
x*y^2,
x*y^2 + y^3,
x^2*y,
x^2*y + y^3,
x^2*y + x*y^2,
x^2*y + x*y^2 + y^3,
x^3,
x^3 + y^3,
x^3 + x*y^2,
x^3 + x*y^2 + y^3,
x^3 + x^2*y,
x^3 + x^2*y + y^3,
x^3 + x^2*y + x*y^2,
x^3 + x^2*y + x*y^2 + y^3]

--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[John Cremona]

That is better since (without the list) it is an iterator; also you
can put in max_degree= instead of of_degree= to get all polys up to a
given degree. Someone else must have needed this and implemented it!

John

>
> Yann

[Noel]

Thank you all for your replies! Now I have another problem:

sage: for f in list(GF(2)['x'].polynomials(of_degree=2)):
....: print len(prime_divisors(f)), f
....:
1 x^2
1 x^2 + 1
2 x^2 + x
1 x^2 + x + 1


Only one of these polynomials should have a 1 in the first column (the
polynomial that's irreducible). What am I doing wrong?

Thanks,
NS

[William Stein]

On Mon, Mar 9, 2009 at 2:21 PM, Noel <noel.s...@cox.net> wrote:
>
> Thank you all for your replies!  Now I have another problem:
>
> sage: for f in list(GF(2)['x'].polynomials(of_degree=2)):
> ....:     print len(prime_divisors(f)), f
> ....:
> 1 x^2
> 1 x^2 + 1
> 2 x^2 + x
> 1 x^2 + x + 1
>
>
> Only one of these polynomials should have a 1 in the first column (the
> polynomial that's irreducible).  What am I doing wrong?

Why do you think len(prime_divisors(x^2)) should be 2? It's 1 since
x^2 has only one prime divisor.

William

>
> Thanks,
> NS
>
>
>
>
>
>
> On Mar 9, 1:20 pm, John Cremona <John.Crem...@gmail.com> wrote:
>> On 9 Mar, 18:05, YannLC <yannlaiglecha...@gmail.com> wrote:
>>
>>
>>
>> > On Mar 9, 6:38 pm, Nick Alexander <ncalexan...@gmail.com> wrote:
>>
>> > > On 9-Mar-09, at 8:48 AM, Noel wrote:
>>
>> > > > Hello Y'all,
>>
>> > > > What's the best way of listing all polynomials of a given degree with
>> > > > coefficients in a finite field?
>>
>> > > If you want a one liner, you could use
>>
>> > > sage: [ GF(3)['x'](list(t)) for t in  (GF(3)^2) ]
>> > > [0, 1, 2, x, x + 1, x + 2, 2*x, 2*x + 1, 2*x + 2]
>>
>> > > Nick
>>
>> > if you want another one liner, and an exact degree, you could use
>>
>> > list(GF(3)['x'].polynomials(of_degree=2))
>>
>> That is better since (without the list) it is an iterator;  also you
>> can put in max_degree= instead of of_degree= to get all polys up to a
>> given degree.  Someone else must have needed this and implemented it!
>>
>> John
>>
>>
>>
>> > Yann
> >
>

--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org

[Carl Witty]

On Mon, Mar 9, 2009 at 1:21 PM, Noel <noel.s...@cox.net> wrote:
>
> Thank you all for your replies!  Now I have another problem:
>
> sage: for f in list(GF(2)['x'].polynomials(of_degree=2)):
> ....:     print len(prime_divisors(f)), f
> ....:
> 1 x^2
> 1 x^2 + 1
> 2 x^2 + x
> 1 x^2 + x + 1
>
>
> Only one of these polynomials should have a 1 in the first column (the
> polynomial that's irreducible).  What am I doing wrong?

prime_divisors() gives you the distinct prime divisors:
sage: prime_divisors(8)
[2]

What do you really want? If you want the factorization, you can use
factor(f); if you want to know if f is irreducible, you can use
f.is_irreducible().

Carl

[Noel]

Thank you...I'm wrong. Yes, prime_divisors gives the number of
distinct prime divisors (just like the name says).

NS



On Mar 9, 4:24 pm, William Stein <wst...@gmail.com> wrote:

[Noel]

William corrected my mistake. The code was working correctly. I
wanted the number of distinct prime divisors of each f. That's
exactly what the code was giving me.

Thank you for replying!

NS



On Mar 9, 4:29 pm, Carl Witty <carl.wi...@gmail.com> wrote: