2018-02-09.ipynb

Kernel: SageMath 8.1

Math 157: Intro to Mathematical Software

UC San Diego, winter 2018

Homework 4: due February 9, 2018

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

Through this problem set, use the SageMath 8.1 kernel.

Problem 1: QR codes

Grading criterion: correctness of code and output.

1a. The following image is the file "qr.gif" in this folder: . Using the command scipy.misc.imread, convert this QR code into the underlying 0-1 matrix that it represents (black = 0, white = 1). You might want to read the Scipy Lectures section on image processing for some context on image processing.

1b. Using the command matrix_plot, convert your answer for part (a) back into a QR code. Your answer should be legible to a standard QR code reader (e.g., on your phone).

Problem 2: Timing

Grading criterion: correctness of code.

2a. Write a straightforward Python function (that is, directly implement the definition without using any Sage or NumPy shortcuts) to compute the standard deviation of a list of numbers.

def f(v):
    # your code goes here

2b. Using timeit, compare the speed of your program when given as input v = range(1000), v = range(10000) and v = range(100000) with the built-in functions provided by the following systems:

• numpy;

• R (use r.??? to access R functions);

• stats.TimeSeries.

Problem 3: Playing cards

Grading criterion: correctness of code and output.

Overall hint: you may want to read this tutorial which solves an easier version of this problem.

3a. Form a "deck of playing cards" by making a list of 52 tuples, each of which is an ordered pair whose first member is one of the 13 possible ranks (A,2,3,4,5,6,7,8,9,T,J,Q,K) and whose second member is one of the 4 possible suits (C,D,H,S).

3b. A poker hand consists of five distinct cards (order not important). Construct an iterator (not a list) that enumerates the possible poker hands from your deck.

3c. Write a function that, given a poker hand, returns the classification of this hand according to the Wikipedia list of poker hands.

3d. Using your answer to 3c, compute the probability that a poker hand, chosen randomly from a deck, is of any particular type.

Problem 4: The weak Goldbach problem

Grading criterion: correctness of code and thoroughness of analysis.

The notorious Goldbach problem is to prove that every even integer greater than 2 can be written as the sum of two primes. A slightly easier problem (which would follow from the original Goldbach problem) is to prove that every odd integer greater than 5 can be written as the sum of three primes. This was shown for sufficiently large integers by Vinogradov in 1937; the gap between "sufficiently large" and "all" was closed by Helfgott in 2013. (This involves serious use of interval arithmetic, but never mind for now.)

4a. Define a function that, given an odd positive integer $n$, returns a list of all of the ways to write $n$ as a sum of three odd primes (up to permutations) by doing a list comprehension over all partitions of $n$ into three positive integers, testing whether each summand is prime.

4b. Define another function that does the same combination, but this time by doing a list comprehension over all combinations of three elements of the set of primes less than $n$, testing whether each triple adds up to $n$.

4c. To confirm that the two methods agree, count the number of solutions returned by 4a and 4b for $n=10^k+1$ for $k=1,2,3,4$.

4d. Using the result of 4c, make a guess about how the number of solutions behaves for large $n$. You may collect additional data if that helps.

Problem 5: A threshold property of random graphs

Grading criterion: correctness of code and thoroughness of analysis.

5a. Let us say that a graph is mostly connected if there is a single connected component containing at least 75% of the vertices. Write a function to test whether a given graph has this property.

5b. Let $G(n, p)$ be a graph on $n$ vertices in which each possible edge is included with probability $p$. Let $H(n,p)$ be the probability that such a graph is highly connected. Write a function to approximate $H(n,p)$ based on a sample of 100 random graphs; then for $n = 100, 500, 1000$, plot $H(n,p)$ as a function of $p$.

5c. Write a function that, for a given $n$, finds a value of $p$ for which $0.25 \leq H(n,p) \leq 0.75$. Hint: you might want to exploit the fact that $H(n,p)$ is monotonic as a function of $p$ to narrow down the search.

5d. Plot the values of $p$ you computed in 5c as a function of $n$, going up to at least $n=1000$ with at least 10 sample points. Then make a guess as to how these values depend on $n$.

Problem 6: Spectral gaps of graphs

Grading criterion: correctness of code and thoroughness of analysis.

6a. Let $G$ be a graph on $n$ vertices which is $k$-regular (each vertex has $k$ neighbors). Let $A$ be the adjacency matrix of $G$. Explain what the Perron-Frobenius theorem implies about the eigenvalues of $A$.

6b. Let $G_{n,k}$ be the graph with vertices $\{0,\dots,n-1\}$ in which $x$ is adjacent to $y$ if and only if $x - y$ is congruent to one of $\pm 1, \dots, \pm k$ modulo $n$. Write a function that constructs the adjacency matrix of $G_{n,k}$ and returns the norm of its second-largest eigenvalue. For efficiency, I recommend using numpy.linalg.eig to compute eigenvalues instead of Sage's built-in function.

6c. Write a function that constructs the adjacency matrix of a random $2k$-regular graph on $n$ vertices and returns the norm of its second-largest eigenvalue.

6d. For $k=3,4,5$, make a plot that compares the answers of 6b and 6c for $n$ from 100 to 1000 (with at least 10 sample points).

6e. In as much detail as possible, interpret your answer to 6d in terms of mixing of random walks.