Part II of Sage Workshop:  Introduction to packages

Sage has a variety of packages.  In this section, feel free to try out different packages that may be useful for your research, class, or just to practice with Sage more.

A.  Polynomials and Symbolic Computation in Sage

Polynomials versus expressions

Warm-up (Example 1)

Define the expression $f=x^4-5x^3+8x^2-4x$.  We know that $f$ is a polynomial with rational (in particular, integer) coefficients.

Plot the graph of this polynomial in sage.  Be sure that the plot displays all its (real) zeros.  Note that $f$ has at least one integer zero in particular, x=2).  Let's try to divide $f$ by $g=x-2$ by using the command quo_rem:

f.quo_rem(g)

Try out this command.  What happens?

Even though some of the expressions we have run into in examples previously look to us like polynomials, Sage would not recognize them that way. Sage makes a distinction between general symbolic expressions and polynomials. This means, for instance, that there are operations permitted on one type of object that are not defined on the other (for example, quo_rem does not work on an expression). This is somewhat annoying at times, but fortunately, there are ways to get Sage to display  what type of thing a given object is and to change that if necessary.

Defining the ring of polynomials with coefficients in a specific ring

Say we want to perform computations with polynomials in
the ring $R = {\bf Q}[x]$ (What does $\bf{Q}[x]$ mean?). Sage lets us define this structure
in several different ways. Here is the most direct:

R.<x> = PolynomialRing(QQ)

(Other possibilities for the coefficient ring would be ZZ -- the ring of integers, Integers(n) for the integers mod $n$ (fill in the specific integer $n$, of course!), GF(p) for the finite field of order $p$, and many, many others.)

Try it out! (Example 2)

Define the ring $R = {\bf Q}[x]$.

If you need to determine whether something (say f) is really a polynomial (for example, if it is causing an error message), you can enter a command like this:

f.parent()

Try it out!  (Example 3)

What is your $f$ that you defined before?

The output will indicate the ``parent structure'' in which  f is defined.  It should be something like Univariate Polynomial ring over x over Rational Field for some of the following commands to work. If the output is something like Symbolic Ring, then the object is not a polynomial; it is just a general symbolic expression.

All is not lost, though. If you have a symbolic polynomial expression that contains only the variable $x$, you can ``force'' Sage to treat it as an element of the ring $R$ defined above with a command like this:

 fR = R(f)

(you could also use the same name if you wanted to).    

Try it out! (Example 4)

Use your newfound knowledge of defining polynomials to redefine $f$ as a polynomial.

Operations on polynomials

Sage has built-in commands:

• factor to factor a polynomial. This gives the factorization over the specified coefficient ring. For instance, if we defined ${\bf Q}[x]$ as above, then the factor command does not know about radicals, complex numbers, etc.  Formats: factor(poly) or poly.factor(). This works on polynomials in any number of variables.

Try it out! (Example 5)

Factor $f$ over the rationals.

Example 6

Factor the following polynomials over the rationals:

a.)  $p=x^2-2x+1$

b.)  $s=x^3-3x^2+4$

c.)  $t=x^2-2$.

• quo_rem() to compute the quotient and remainder on division of one polynomial $f(x)$ by another $g(x)$. This has a slightly strange format: f.quo_rem(g) Note: the polynomial g in the parentheses is used as the divisor; the polynomial being acted on (the f) is the dividend. If $f$ or $g$ contain other variables besides $x$, this will fail. The output from this is a Sage list -- the quotient is the first element and the remainder is the second element. If you want to assign names to the outputs, you can do something like this: (q,r) = f.quo_rem(g)

Try it out! (Example 7)

Compute the following:

a.) Divide $x^4-5x^3+8x^2-4x$ by $x-2$ (what do you expect to get?)

b.) Divide $x-2$ by $x^4-5x^3+9x^2-4x$.

c.) Divide $x^3-4x-5$ by $x^2-2x-4$.

• gcd to compute the greatest common divisor of two polynomials $f(x)$ and $g(x)$. Format: f.gcd(g). The greatest common divisor of a set of several polynomials can be computed by nested gcd's.  For example, $\gcd(f,g,h)$ can be computed by f.gcd(g).gcd(h)

Try it out! (Example 8)

Compute the gcds of the following pairs of polynomials.  Given your results from Example 7, think critically about whether or not these answers make sense.

 a.) $\gcd(x^5-2x^4-4x^3+8x^2-2x+4, x-2)$

b.) $\gcd(x^3-4x-5, x^2-2x-4)$

• diff(f,x) computes the formal derivative of $f$ with respect to $x$.

Example 9

Here is a sample sequence of Sage input lines illustrating some of these commands. Try entering and executing them in sequence. Look carefully at the output and make sure you understand what happened in each case:

R.<x> = PolynomialRing(QQ)

cube = (x**2 - 16)**3

print cube

s = (x**2-x+1)*(x - 4)

print s

(q,r) = cube.quo_rem(s)

print "q = ", q," , r = ", r

q*s + r == s 

B.  Graph Theory

Sage can be used to generate graphs.  

 

For example, you can use sage to create any complete graph with $n$ vertices using graphs.CompleteGraph(n)

Example 1

See below for the complete graph on 5 vertices.

d3-based renderer not yet implemented

You can also figure out properties of graphs using commands:

• is_connected() : Determines if a graph is connected or not
• connected_components() : Gives you the connected components of the graph
• is_hamiltonian() : Determines if a graph has a Hamiltonian cycle (circuit that passes through every vertex once)
• hamiltonian_cycle() :Gives you a hamiltonian cycle
• chromatic_number() : Tells you the minimum coloring needed for the vertices of this graph

Try it out! (Example 3)

Try out some of these commands on our previous graph $G$.

How do you input graphs?

To create a graph, you can use one of the ready-made commands like CompleteGraph or Bipartite.  If your graph is a little more unusual, you could use the adjacency matrix instead:

$M=(m_{ij})$, where $m_{ij}=1$ if and only if there is an edge between vertex $i$ and vertex $j$.

Then you would create the graph as:

Graph(M)

Try it out! (Example 4)

Try creating a graph using an adjacency matrix.  How would you create loops?

C. Game Theory

The game theory package has some options for creating common games, such as the Prisoners Dilemma.

Notice that the assumed matrices are

$$A=\begin{bmatrix} R & S \\ T & P \end{bmatrix}=\begin{bmatrix} -2 & -5 \\ 0 & -4\end{bmatrix}$$

$$B=\begin{bmatrix} R & T \\ S & P \end{bmatrix}=\begin{bmatrix} -2 & 0 \\ -5 & -4\end{bmatrix}$$ 

You can obtain the Nash equilibrium for this via the command g.obtain_nash()

Try it out! (Example 1)

Find the Nash equilibrium for the above system.

If you'd like to change the values of $R, P, S, T$, you can do so via the command

game_theory.normal_form_games.PrisonersDilemma(R=0, P=-1, S=-4, T=5)

Try it out! (Example 2)

Try out different values for the game, along with computing  the Nash equilbirium.  Which values are prohibited?

Some other games (look them up if interested)

• Rock, paper, scissors, lizard, spock: game_theory.normal_form_games.RPSLS()
• Stag Hunt: game_theory.normal_form_games.StagHunt()
• Battle of the Sexes: game_theory.normal_form_games.BattleOfTheSexes()
• Chicken: game_theory.normal_form_games.Chicken()