Ask Your Question

listing desired polynomials of given degree

asked 2023-12-31 19:45:13 +0200

jacop gravatar image

updated 2024-04-14 08:15:50 +0200

FrédéricC gravatar image

I want to write a program such that it takes values a and b where a is for the degree of the polynomial and b is for the field. After that I wanted to list all reducible and irrecucible polynomials of degree a in $F_b$. Can you help me to write it using sagemath ?

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted

answered 2024-01-01 06:29:03 +0200

dan_fulea gravatar image

Here is a first brute force solution. I will use q instead of b. Let $F=\Bbb F_q=$GF(q) be the field with $q$ elements. One can use itertools.product (the pythonic way) or the sagemath specific cartesian_product to have a loop over (the tuples of) monic polynomials. We will collect only the irreducible ones of degree $a$ in $F[t]=\Bbb F_q[t]$.

q, a = 9, 5    
# feel free to use other values, 
# or arrange for a function to use an adapted code working in the following manner.

F = GF(q, names='w')
R.<t> = PolynomialRing(F)

all_polynomials = [
    t^a + sum([coeff*t^c for (c, coeff) in enumerate(my_tuple)])
    for my_tuple in cartesian_product([F for counter in range(a)])

irreducible_polynomials = [pol for pol in all_polynomials if pol.is_irreducible()]

And we obtain after some time the wanted list irreducible_polynomials. How many polynomials are in there?

sage: len(irreducible_polynomials)

And which is the number we expect? Well, every polynomial in the list has $a=5$ roots which are not elements of a proper subfield of $\Bbb F_{9^5}$. There is only one proper subfield of $\Bbb F_{9^5}$, which is $\Bbb F_9$. (In general, we have all $\Bbb F_{q^d}$ for $d \ne a$ a divisor of $a$. These fields may have common elements, and the divisibility graph of $a$ mimic the intersection scheme of these fields.) So there are exactly $9^5-9$ elements of degree $5$ over $F=\Bbb F_9$, and collecting them in conjugacy groups (irreducible polynomials) we obtain $(9^5-9)/5=11808$ such groups.

We may also use this counting scheme to have an other way to generate the irreducible polynomials.

The above can be shortened to generate all monic irreducible polynomials by using instead the loop over the iterator R.polynomials(...):

q, a = 9, 5
F = GF(q, names='w')
R.<t> = PolynomialRing(F)

irreducible_polynomials = [
    t^a + pol 
    for pol in R.polynomials(max_degree=a - 1)
    if (t^a + pol).is_irreducible()

If the monic assumption is not needed, then all the irreducible polynomials of degree $a$ are alternatively given by:

q, a = 9, 5
F = GF(q, names='w')
R.<t> = PolynomialRing(F)

all_irreducible_polynomials = [
    for pol in R.polynomials(of_degree=a)
    if pol.is_irreducible()

And we expect of course $(9-1)$ times $11808$ such polynomials, and producing them takes a lot of time. Indeed:

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2023-12-31 19:45:13 +0200

Seen: 117 times

Last updated: Jan 04