# SageMath basics

## Building blocks

• Functionality: supports computation with objects in many different computer algebra systems “under one roof” using a common interface and clean programming language.
• GAP https://www.gap-system.org/ system for computational discrete algebra, emphasis on Computational Group Theory, consisting of a programming language, libraries, objects.
• GP/PARI
• Singular
• Maxima
• SageMath Wiki
• SageMath expository from David Joyner - legacy
• SageMath - William Stein - legacy

## Notebooks

Refer also to LW0200MATHEMATICS.

Invocation:
• 'sage' in a console starts a Sage session. To quit the session enter quit and then press .
• 'sage -n jupyter' in a console starts a Sage session in a Jupyter notebook
• HELP takes you to tutorials etc
Alternatively, there's the online version
Useful:
• With some minor exceptions, Sage uses the Python programming language, so most introductory books on Python will help you to learn Sage.
• Preceding a command with 'time' shows the time it took to perform the calculation.
• Use 'parent' to find out the construction, 'type' to find out its type.
• Use the 'tab'-button for autocompletion.
• Use the 'show' function to nicely display output in LaTeX style.

## Object-orientation

### Python

In Python, everything is an object so there isn’t any difference between types and classes. One can get the class of the object el by type(el). Behavior is defined through methods.

Compared to Python, Sage has particular ways to handle objects:
• Any classes for mathematical objects in Sage should inherit from SageObject rather than from object. Most of the time, they actually inherit from a subclass such as Parent or Element.
• Printing should be done through _repr_ instead of __repr__ to allow for renaming.
• More generally, Sage-specific special methods are usually named _meth_ rather than __meth__. For example, lots of classes implement _hash_ which is used and cached by __hash__. In the same vein, elements of a group usually implement _mul_, so that there is no need to take care about coercions as they are done in __mul__.
For more details, see the Sage Developer’s Guide.

## Numbers

### Intro

• 7 # integer, type is class 'sage.rings.integer.Integer', parent is Integer Ring
• 7.0 # real, type is class 'sage.rings.real_mpfr.RealLiteral and parent is Real Field with 53 bits of precision</li>
When mixing different type of numbers, Sage does its best: if possible, it computes the result in the smaller set of numbers containing all the arguments.

Sage is a *computer algebra system*: unless specified otherwise, it does *symbolic computation* (as opposed to *numerical computation*).

Also when computing a division, Sage keeps the result exact and simplifies it only when possible. Check this: compute `10/2` and `7/2`.

### Exact versus numerical approximation

Some mathematical expressions return ‘exact’ values, rather than numerical approximations.

To get a numerical approximation, use 'numerical_approx', in full, or use either of the abbreviations the function N or the method n (the function N is the same as n).
• To get help: 'numerical_approx?'
• Returns: 'numerical_approx(x, prec=None, digits=None, algorithm=None)'
• where prec is in bits, and digits is in decimal digits
• default is 53 bits of precision (approximately 16 digits)
• the accepted algorithms depend on the object

### Length of a number

• If n is a number, len(n.str(2)) gives n's lenght as binary string.
• If n is a number, len(n.str(10)) gives n's lenght as decimal number.

### Dynamic typing

• a = 5 # a is an integer
• type(a)
• class 'sage.rings.integer.Integer'
• a = 5/3 # now a is a rational number
• type(a)
• class 'sage.rings.rational.Rational'
• a = 'hello' # now a is a string
• type(a)
• <... 'str'>

## Operations

• 2**3 # ** means exponent
• 2^3 # ^ is a synonym for ** (unlike in Python)
• 10 % 3 # for integer arguments, % means mod, i.e., remainder
• 10/4
• 10//4 # for integer arguments, // returns the integer quotient

## Symbolic variables and expressions

By default, the only symbolic variable predefined in Sage is x. To use more variables, use 'var', e.g. var('y,z').

You may need to specify assumptions. E.g.
• bool(sqrt(x**4)==x**2)
• Returns False # counter-intuitive but correct given signs
• One can use 'assume':
• assume(x > 0), bool(sqrt(x**4)==x**2)
• Returns: (none, True)
• Remember you clear your assumption with 'forget', and erase it completely with 'reset'.
One can define *symbolic functions* using symbolic variables. Symbolic functions are useful to represent mathematical functions in Sage. For instance:
• Definition: f(x,y) = (x^2+2*y)/(log(y)+1)
• Invocation ('evaluation'): f(0,1) returns '2'
Use of methods:
• Use of 'substitution method': f(x,y).subs(x==1) returns (2*y + 1)/(log(y) + 1)
• Another 'substitution': f(x,y).subs(y==sqrt(3)) returns (x^2 + 2*sqrt(3))/(log(sqrt(3)) + 1)
More:
• To compute the derivative of the function f(x,y) with respect to the variable y using the derivative method: f(x,y).derivative(y)
• There are many methods, which can be identified through autocompletion tab: f.tab

## Solve function

The solve function is the most general tool in Sage to solve equations, systems of equations, or inequalities. It provides only exact i.e. symbolic solutions (as opposed to numerical solutions). Of course Sage is not always able to compute exact solutions. It has other functions dedicated to solving equations numerically. More details e.g. here.

# SageMath Number Theory

## Logarithm

• 'log(*args, **kwds)' # Returns the logarithm of the first argument to the base of the second argument which if missing defaults to "e".
• examples:
• sage: log(e^2)
• 2
• To change the base of the logarithm, add the second parameter: sage: log(1000,10)
• 3
• The synonym "ln" can only take one argument: sage: ln(RDF(10))
• 2.302585092994046
From 'log?': The log function also works in finite fields as long as the argument lies in the multiplicative group generated by the base:
• sage: F = GF(13); g = F.multiplicative_generator(); g
• 2
• sage: a = F(8)
• sage: log(a,g); g^log(a,g)
• 3
• 8
• sage: log(a,3)
• Traceback (most recent call last):
• ...
• ValueError: No discrete log of 8 found to base 3 modulo 13
• sage: log(F(9), 3)
• 2

## Groups

Group is a set and an operation that combines any two elements of the set to produce a third element of the set, in such a way that the operation is associative, an identity element exists and every element has an inverse.

## Rings

### Number rings

Ring is a set with 2 binary operations (+ and *) such that R is abelian with respect to +, * is associative, and + and * are distributive.

#### Rings of integers - referred to as ZZ, Z/nZ, ...

Defining a finite ring of integers:
• One way:
• R = Integers(97)# 'Integers' creates a finite ring of integers mod 97
• R
• Ring of integers modulo 97
• list(R)
• 0...96
• parent(R)
• class 'sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic_with_category'
• Another way:
• R = IntegerModRing(97) # 'IntegerModRing(x) creates apparently the same of the preceding example
• parent(R)
• class 'sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic_with_category>
Working with elements:
• a = R(5)
• a
• 5
• parent(a)
• Ring of integers modulo 97
• a = R(2) / R(3)
• a
• 33
• a.rational_reconstruction()
• 2/3

### Polynomial rings

You can simply use polynomials via symbolic expressions, without specifying the coefficient ring. However for more advanced algebra, this approach lacks some algebraic structure. To begin with, we would like to consider polynomials with coefficients in a predefined ring, for instance ℚ or a finite field.

#### Polynomial rings QQ

• Syntax 1 to build the ring R ℚ[𝑋] of polynomials with coefficients in ℚ and indeterminate X.
• R. = PolynomialRing(QQ)
• R
• Univariate Polynomial Ring in X over Rational Field
• R.base_ring()
• Rational Field
• R.variable_name()
• 'X'
• R.tab-for-autocomplete
• Syntax 2 to build the ring R ℚ[𝑋] of polynomials with coefficients in ℚ and indeterminate X.
• R.< X > = QQ[]
Working with QQ: any expression constructed from `X` and rational constants with operations `+` and `*` is an element of `R`. E.g. P = X^2+3/2*X+1.

Methods include
• P.list() to list of coefficients of P,
• degree (to find the highest exponent of the variable),
• factor, and roots, e.g.
• R. = PolynomialRing(QQ)
• Q = X^3 + 4/3*X^2 + 4/3*X + 1/3
• Q.factor()
• (X + 1/3) * (X^2 + X + 1)
• Q.roots()
• [(-1/3, 1)])
• is_irreducible, ...

#### Integer polynomial rings, ZZ or Z/nZ or Zn or Zn

• R = IntegerModRing(15) # here n=15 and 'R = Integers(15)' is an equivalent syntax
• R(2021) # Converts an integer into an element of `R`, to construct an element of R
• R(2021).parent() # Contrary to what appears to be, this element is not an integer but an element of `R`
• R.is_field() # One may ask Sage about the properties of the ring `R` using its associated methods
• # Of course Z/15Z is not a field because 15 is not a prime number (hence there is no multiplicative inverse guaranteed for all elements)

#### Other polynomial rings RR, GF

• A. = ZZ[] # ... with coefficients in Z
• B. = RR[] # ... with coefficients floating-point approximations of real numbers
• C. = GF(17)[] # ... with coefficients in a finite field of 17 elements

#### Changing the base ring

Changing the base ring may be useful, for instance when studying the irreducibility or factorization of a polynomial. For example:
• M = X^3+X+1
• M.is_irreducible()
• True
Polynomial M is irreducible over ℚ. Now let us look at it over ℝ.

Approach:
• Using the change_ring method, construct the polynomial N which is a "copy" of M in ℝ[𝑋]
• Check if N is irreducible in ℝ[𝑋]
• If not, factor N in ℝ[𝑋]
SageMath:
• N=M.change_ring(RR)
• N
• X^3 + X + 1.00000000000000 # observe the real
• type(N)
• class 'sage.rings.polynomial.polynomial_real_mpfr_dense.PolynomialRealDense'
• N.is_irreducible()
• False
• factor(N)
• (X + 0.682327803828019) * (X^2 - 0.682327803828019*X + 1.46557123187677)
• So M is irreducible over ℚ but reducible over ℝ.
From documentation 'Polynomials Release 9.8' - illustration of 'change_ring' method.
• R. = RR[]; R
• Univariate Polynomial Ring in x over Real Field with 53 bits of precision
• R.change_ring(QQ)
• Univariate Polynomial Ring in x over Rational Field

#### Polynomials with multiple variables

Polynomial with several variables are constructed and manipulated in a similar way.
• A. = PolynomialRing(QQ) # so three variables now
• P = 2*x^2+y^3-y-2
• Q = x^2-x*y+y^2-1

### Other rings

Other rings include finite fields, p-adic integers, the ring of algebraic numbers, and matrix rings.

## Fields

• GF(3)
• Finite Field of size 3
• GF(27, 'a') # need to name the generator if not a prime field
• Finite Field in a of size 3^3
• Zp(5)
• 5-adic Ring with capped relative precision 20

## Factorisation - often using integers or polynomials

The 'Factorization' class provides a structure for holding quite general lists of objects with integer multiplicities. These may hold the results of an arithmetic or algebraic factorization, where the objects may be primes or irreducible polynomials and the multiplicities are the (non-zero) exponents in the factorization. Functions include:
• gcd(m, n)
• factor(n) Use 'factor?' for help...
• Calls Pari’s factor C library function.
• This has proof False by default. Sage has a global proof flag, set to True by default (see "sage.structure.proof.proof", or proof.[tab]). To override the default, call this function with proof=False.
• E.g. sage: factor(3^89-1, proof=False)
• qsieve (n) - Bill Hart - the best algorithm for factoring numbers of the form pq up to around 100 digits.
• ecm.factor(n) - GMP-ECM - Paul Zimmerman
• The elliptic curve factorization (ECM) algorithm is the best algorithm for factoring numbers of the form n=pm, where p is not “too big”. ECM is due to Hendrik Lenstra, which works by “pretending” that n is prime, choosing a random elliptic curve over Z/nZ, and doing arithmetic on that curve - if something goes wrong when doing arithmetic, we factor n.
Factoring is a useful technique for solving polynomial equations. By breaking a polynomial down into smaller factors, we can often simplify the equation and find the solutions more easily. To factor polynomials: e.g. define the sets of polynomials with rational coefficients and real coefficients:
• ratpoly. = PolynomialRing(QQ)
• realpoly. = PolynomialRing(RR)
You can then factor polynomials:
• factor(t^2-2)
• t^2 - 2
• factor(z^2-2)
• (z - 1.41421356237310) * (z + 1.41421356237310)

## Congruences

### Relative primes and Euler phi (totient) and theorem

#### Modulus

Mod(x,p): Mod(33,9) = 6
• b = R(47)
• b^20052005
• 50
• b.modulus()
• 97
• b.is_square()
• True

#### Euler's phi-function

phi(n) is the amount of numbers that are relatively prime to n.
• For a prime: phi(p)=p-1
• For a composite: phi(20)=phi(4)*phi(5)=8, and this is {1, 3, 7, 9, 11, 13, 17, 19}

#### Euler's Theorem

If gcd(x,n)=1 then xphi(n)=1 (mod n).

#### Relative primes

How to get list of relative primes for a given number? See ask.sagemath.org.

There are multiple ways to list integers coprime to a given integer in Sage.

One way is to build the ring of integers modulo m, then list the multiplicative group of that ring.
• sage: m = 8
• sage: Zmod(m).list_of_elements_of_multiplicative_group()
• [1, 3, 5, 7]
Note that this returns a list of Python integers:
• sage: type(Zmod(m).list_of_elements_of_multiplicative_group())
To get Sage integers one would need
• sage: m = 8/li>
• sage: [ZZ(k) for k in Zmod(m).list_of_elements_of_multiplicative_group()]
• [1, 3, 5, 7]
Check:
• sage: [ZZ(k) for k in Zmod(m).list_of_elements_of_multiplicative_group()].parent()
• Integer Ring

Another way is to use the method coprime integers, which expects another argument to say how far you want to list integers that are coprime to m. To get them up to m - 1:
• sage: m = 8
• sage: m.coprime_integers(m)
To get them further:
• sage: m.coprime_integers(29) # list up to 29 (excluded)
• [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27]
These are returned as Sage integers:
• sage: m.coprime_integers(m).parent()
• Integer Ring