2018-01-26-solutions.ipynb

Kernel: SageMath 8.1

Math 157: Intro to Mathematical Software

UC San Diego, winter 2018; materials by Kiran S. Kedlaya

Homework 2: due January 26, 2018

Please enter all answers within this notebook unless otherwise specified. As usual, don't forget to cite sources and collaborators.

Problem 1: Comparison of relevant software

Grading criterion: correctness. Remember to cite all sources!

1a. Specify whether each of the following computer algebra systems fits the Open Source Initiative definition of an "open-source" project (https://opensource.org/definition). If not, identify a criterion which fails to be met.

• GAP

• Geogebra

• Magma

• Maple

• Mathematica

• MATLAB

• Pari/GP

• Sage

• Sympy

GAP: Yes
Geogebra: Yes
Magma: No. Free distribution.
Maple: No. Free distribution.
Mathematica: No. Free distribution.
MATLAB: No. Free distribution.
Pari/GP: Yes.
Sage: Yes.
Sympy: Yes.

Source:
https://en.wikipedia.org/wiki/List_of_computer_algebra_systems
https://www.gap-system.org/
https://www.geogebra.org/
https://magma.maths.usyd.edu.au/magma/
https://www.maplesoft.com/
https://www.wolfram.com/mathematica/
https://www.mathworks.com/products/matlab.html
https://pari.math.u-bordeaux.fr/
http://www.sagemath.org/
http://www.sympy.org/en/index.html

1b. For each of the following projects, give a one-sentence description of the project, and indicate in what year and by what person/organization the first version was released.

• Cython

• Julia

• MacSyma / Maxima (treat as one project)

• Numpy

• Pandas

• Python

• R

• Sage

• Scipy

• TeX / LaTeX (treat as one project)

Cython: Cython is a superset of the Python programming language with C-like functionality/ 28 July 2007/ Robert Bradshaw, Stefan Behnel, et al.
Julia: Julia is a high level programming language for numerical analysis and computational science/ 2012/Jeff Bezanson, Alan Edelman, Stefan Karpinski, Viral B. Shah
MacSyma/Maxima: Maxima is a system designed for symbolic and numerical manipulations/ July 1968/ Carl Engelman, William A. Martin, Joel Moses
Numpy: Numpy is a library for the programming language Python designed for scientific computing/ 2006 (as Numpy)/ Travis Oliphant
Pandas: Pandas is a software library for the programming language Python designed for data structures and analysis/ 2008/ Wes McKinney
Python: Python is a high level programming designed for general purpose programming/ 20 February 1991/  Guido van Rossum
R: R is a programming language and software environment for statistical computing and graphics/ August 1993/ Ross Ihaka, Robert Gentleman
Sage: Sage is a mathematics software system covering many areas of mathematics/ 24 February 2005/ William Stein
Scipy: Scipy is a library for the programming language Python designed for scientific computating/ 2001/ Travis Oliphant, Pearu Peterson, Eric Jones
TeX/LaTeX: TeX is a typesetting system including features for scientific, technical documentation/ 1978/ Donald Knuth

Source:
https://en.wikipedia.org/wiki/Cython
http://cython.org/
https://en.wikipedia.org/wiki/Julia_(programming_language)
https://julialang.org/
https://en.wikipedia.org/wiki/Macsyma
http://maxima.sourceforge.net/
https://en.wikipedia.org/wiki/NumPy
http://www.numpy.org/
https://en.wikipedia.org/wiki/Pandas_(software)
https://pandas.pydata.org/
https://en.wikipedia.org/wiki/Python_(programming_language)
https://www.python.org/
https://en.wikipedia.org/wiki/R_(programming_language)
https://www.r-project.org/
https://en.wikipedia.org/wiki/SageMath
http://www.sagemath.org/
https://en.wikipedia.org/wiki/SciPy
https://www.scipy.org/
https://en.wikipedia.org/wiki/TeX
https://www.latex-project.org/

Problem 2: Under the hood

Grading criterion: correctness.

For each of the following Sage commands, identify one external component of Sage which is used to execute that command, and indicate how you did so. (Hint: in addition to the Sage documentation, inspecting docstrings or even source code may be helpful.)

factor(10^30-13)

factor uses PARI Source: factor?? "These implementations are not used by the generic factor command, which currently just calls PARI"

plot(lambda x: sin(x), 0, 2*pi)

plot uses matplotlib Source: plot?? "Any MATPLOTLIB line option may also be passed in."

G = AlternatingGroup(4)
G.subgroups()

AlternatingGroup uses GAP Source: AlternatingGroup?? "Returns the string used to create this group in GAP."

var('x,y,z')
f = (x+y)/z
f.derivative(z)

var uses pynac Source: var?? "The new (Pynac) symbolics are now the only symbolics"

R.<x,y,z> = PolynomialRing(QQ)
factor(x^3+y^3+z^3-3*x*y*z)

PolynomialRing uses FLINT Source: PolynomialRing?? " The default is FLINT"

Problem 3: Mersenne primes

Grading criteria: correctness of explanation and code.

3a. A Mersenne prime is a prime number of the form $2^p-1$ where $p$ is itself prime. (Note that these are the only possible primes of the form $2^n-1$ where $n$ is a positive integer). They are called this because Marin Mersenne was the first person to attempt to list these primes systematically: he claimed that for $p \leq 257$, $2^p-1$ is prime if and only if $$p \in \{2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257\}.$$ This list turns out to be incorrect; write Sage code to compute the correct list.

l = []
for i in range(1,258):
    if ZZ(i).is_prime() == True and ZZ(2^i -1).is_prime() == True:
        l.append(i)
l

[2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127]

3b. On January 3, 2018, the Great Internet Mersenne Prime Search announced that $2^{77232917}-1$ is the "50th known Mersenne prime." Why didn't they announce that it is the "50th Mersenne prime"?

It has not been fully checked in the sense that there could be another unknown Mersenne prime $2^p -1$ with $p< 77232917$.

Source: https://www.mersenne.org/

3c. The little Fermat theorem states that if $p$ is prime, then $2^{p-1} \equiv 1 \pmod{p}$. This can be used as a test for primality (the Fermat test) which has no false negatives, but does have some false positives (see part (d)).

Explain why the following code cannot be used to apply the Fermat test to the number $p = 2^{21701}-1$, then give an alternate approach that does work.

p = 2^21701 - 1
print(2^(p-1) % p) # This won't work.

Exponent exceeds maximum capacity for Python exponentiation.

p = 2^21701 - 1
a = mod(2, p)
a^(p-1)

1

3d. Find all integers up to 1000 which are false positives for the Fermat test. These include Carmichael numbers, in case you want to read more about this phenomenon.

l1 = []
for i in range(3,1001):
    a = mod(2,i)
    if a^(i-1) == 1 and is_prime(i) is False:
        l1.append(i)

l1

[341, 561, 645]

Problem 4: Defining and evaluating a function

Grading criteria: correctness of code.

4a. Define in Sage the symbolic function (not a Python function) $$f(x) = \sinh(x^2-x-1) + e^{\pi x} + \arcsin(x) + \frac{1}{x^3-x-e}$$.

x = var('x')
f = sinh(x^2 - x - 1) +e^(pi*x) + arcsin(x) + (x^3 - x - e)^(-1)
f

1/(x^3 - x - e) + arcsin(x) + e^(pi*x) + sinh(x^2 - x - 1)

4b. Compute $f(1/2)$ exactly (i.e., your answer should be a symbolic expression).

f(1/2)

1/6*pi - 8/(8*e + 3) + e^(1/2*pi) - sinh(5/4)

4c. Compute $f(1/2)$ numerically (i.e., your answer should be a decimal expansion).

n(f(y))

3.40887583146976

4d. Plot $f(x)$ from $-1$ to $1$.

plot(f, (x, -1, 1))

Problem 5: Numerical root-finding

Grading criteria: correctness (of code) and thoroughness (of explanation).

5a. Plot the function $f(x) = \displaystyle x^2 + \sin(x)$ on the interval $[-2,2]$.

x = var('x')
f = x^2 + sin(x)
plot(f, (x, -2, 2))

5b. Use Sage to compute the derivative and antiderivative of $f$.

l ={'derivative': derivative(f), 'antiderivative': integral(f)}
l

{'antiderivative': 1/3*x^3 - cos(x), 'derivative': 2*x + cos(x)}

5c. Find numerical approximations to all of the zeros of $f(x)$.

find_root(f,-2,-0.5), find_root(f,-0.25,0.25)

(-0.8767262153950622, -9.011553445415526e-16)

5d. In as much detail as you can, justify mathematically why your list in (c) is complete. Your explanation may include additional Sage code if necessary.

We note that $|\sin(x)|\leq 1$ for all $x$ while $|x^2|>1$ when $x$ isn't in the interval $[-1,1]$. All zeros of the function $f(x)$ must therefore be in the interval $[-1,1]$.

Problem 6: Taylor series

Grading criteria: correctness.

6a. Define the function $f(x) = \sin(x^2)$. Find the degree 3 Taylor series $p_3$ of $f$ about $x_0 = 2\pi$.

x = var('x')
f = sin(x^2)
f.taylor(x,2*pi,3)

4/3*(2*pi - x)^3*(8*pi^3*cos(4*pi^2) + 3*pi*sin(4*pi^2)) - (2*pi - x)^2*(8*pi^2*sin(4*pi^2) - cos(4*pi^2)) - 4*pi*(2*pi - x)*cos(4*pi^2) + sin(4*pi^2)

6b. Make a single Sage plot on the interval $x=[\pi, 3\pi]$ showing both $f(x)$ and its degree 10 Taylor series $p_{10}$ about $x_0 = 2\pi$.

g = f.taylor(x,2*pi,10)
p1 = plot(f, (x, pi, 3*pi), color='green', legend_label='$sin(x^2)$')
p2 = plot(g, (x, pi, 3*pi), color='blue', linestyle='--', ymin =-2, ymax = 2, legend_label='$p_{10}$')
show(p1 + p2)