poly-sage.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section17.6Sage

¶

Sage is particularly adept at building, analyzing and manipulating polynomial rings. We have seen some of this in the previous chapter. Let's begin by creating three polynomial rings and checking some of their basic properties. There are several ways to construct polynomial rings, but the syntax used here is the most straightforward.

SubsectionPolynomial Rings and their Elements

R.<x> = Integers(8)[]; R

S.<y> = ZZ[]; S

T.<z> = QQ[]; T

Basic properties of rings are availble for these examples.

R.is_finite()

R.is_integral_domain()

S.is_integral_domain()

T.is_field()

R.characteristic()

T.characteristic()

With the construction syntax used above, the variables can be used to create elements of the polynomial ring without explicit coercion (though we need to be careful about constant polynomials).

y in S

x in S

q = (3/2) + (5/4)*z^2
q in T

3 in S

r = 3
r.parent()

s = 3*y^0
s.parent()

Polynomials can be evaluated like they are functions, so we can mimic the evaluation homomorphism.

p = 3 + 5*x + 2*x^2
p.parent()

p(1)

[p(t) for t in Integers(8)]

Notice that p is a degree two polynomial, yet through a brute-force examination we see that the polynomial only has one root, contrary to our usual expectations. It can be even more unusual.

q = 4*x^2+4*x
[q(t) for t in Integers(8)]

Sage can create and manipulate rings of polynomials in more than one variable, though we will not have much occasion to use this functionality in this course.

M.<s, t> = QQ[]; M

SubsectionIrreducible Polynomials

Whether or not a polynomial factors, taking into consideration the ring used for its coefficients, is an important topic in this chapter and many of the following chapters. Sage can factor, and determine irreducibility, over the integers, the rationals, and finite fields.

First, over the rationals.

R.<x> = QQ[]
p = 1/4*x^4 - x^3 + x^2 - x - 1/2
p.is_irreducible()

p.factor()

q = 2*x^5 + 5/2*x^4 + 3/4*x^3 - 25/24*x^2 - x - 1/2
q.is_irreducible()

q.factor()

Factoring over the integers is really no different than factoring over the rationals. This is the content of Theorem 17.14 — finding a factorization over the integers can be converted to finding a factorization over the rationals. So it is with Sage, there is little difference between working over the rationals and the integers. It is a little different working over a finite field. Commentary follows.

F.<a> = FiniteField(5^2)
S.<y> = F[]
p = 2*y^5 + 2*y^4 + 4*y^3 + 2*y^2 + 3*y + 1
p.is_irreducible()

p.factor()

q = 3*y^4+2*y^3-y+4; q.factor()

r = y^4+2*y^3+3*y^2+4; r.factor()

s = 3*y^4+2*y^3-y+3; s.factor()

To check these factorizations, we need to compute in the finite field, F, and so we need to know how the symbol a behaves. This symbol is considered as a root of a degree two polynomial over the integers mod 5, which we can get with the .modulus() method.

F.modulus()

So $a^2+4a+2=0\text{,}$ or $a^2=-4a-3=a+2\text{.}$ So when checking the factorizations, anytime you see an $a^2$ you can replace it by $a+2\text{.}$ Notice that by Corollary 17.8 we could find the one linear factor of r, and the four linear factors of s, through a brute-force search for roots. This is feasible because the field is finite.

[t for t in F if r(t)==0]

[t for t in F if s(t)==0]

However, q factors into a pair of degree 2 polynomials, so no amount of testing for roots will discover a factor.

With Eisenstein's Criterion, we can create irreducible polynomials, such as in Example 17.18.

W.<w> = QQ[]
p = 16*w^5 - 9*w^4 +3*w^2 + 6*w -21
p.is_irreducible()

Over the field ${\mathbb Z}_p\text{,}$ the field of integers mod a prime $p\text{,}$ Conway polynomials are canonical choices of a polynomial of degree $n$ that is irreducible over ${\mathbb Z}_p\text{.}$ See the exercises for more about these polynomials.

SubsectionPolynomials over Fields

If $F$ is a field, then every ideal of $F[x]$ is principal (Theorem 17.20). Nothing stops you from giving Sage two (or more) generators to construct an ideal, but Sage will determine the element to use in a description of the ideal as a principal ideal.

W.<w> = QQ[]
r = -w^5 + 5*w^4 - 4*w^3 + 14*w^2 - 67*w + 17
s = 3*w^5 - 14*w^4 + 12*w^3 - 6*w^2 + w
S = W.ideal(r, s)
S

(w^2)*r + (3*w-6)*s in S

Theorem 17.22 is the key fact that allows us to easily construct finite fields. Here is a construction of a finite field of order $7^5=16\,807\text{.}$ All we need is a polynomial of degree $5$ that is irreducible over ${\mathbb Z}_7\text{.}$

F = Integers(7)
R.<x> = F[]
p = x^5+ x + 4
p.is_irreducible()

id = R.ideal(p)
Q = R.quotient(id); Q

Q.is_field()

Q.order() == 7^5

The symbol xbar is a generator of the field, but right now it is not accessible. xbar is the coset $x + \langle x^5+ x + 4\rangle\text{.}$ A better construction would include specifying this generator.

Q.gen(0)

Q.<t> = R.quotient(id); Q

t^5 + t + 4

t^5 == -(t+4)

t^5

(3*t^3 + t + 5)*(t^2 + 4*t + 2)

a = 3*t^4 - 6*t^3 + 3*t^2 + 5*t + 2
ainv = a^-1; ainv

a*ainv