Discrete Mathematics Christmas Projects

These are optional projects that you may try after you have completed at least one past exam question from each topic. Each project covers a particular area of Discrete mathematics that will be useful in some other courses in the tripos. You are encouraged to use the internet and books (and you can collaborate with others if you want). You can also email me for hints.

If you take any of these projects, then you can choose to present your findings during the revision session. Of course, you may choose to investigate and present a (related) topic that interests you and is not listed below.

Project 1 [Euler’s Phi function + Cryptography]

(Useful for Discrete Maths and Cryptography)

Euler’s \(\phi : \mathbb{N} \to \mathbb{N}\) function is defined as:

\[\phi(n) = \text{number of elements in } \mathbb{Z}_n \text{ co-prime with n}\]

In this part, you will prove Euler-Fermat’s theorem:
1. Show that \(\mathrm{gcd}(a, n) = 1\) and \(\mathrm{gcd}(x, n) = 1\), then \(\mathrm{gcd}(ax, n) = 1\).
2. Cancellation law: Let \(\lbrace x_1, \ldots, x_{\phi(n)}\rbrace\) be the numbers co-prime with \(a\) in \(\mathbb{Z}_n\), then \(a x_i \equiv a x_j \ (\mathrm{mod\ } n) \Rightarrow x_i \equiv x_j \ (\mathrm{mod\ } n)\)
3. Use (1) and (2) to deduce that \((ax_1, \ldots, ax_{\phi(n)})\) is a permutation of \((x_1, \ldots, x_{\phi(n)})\).
4. Show that \(\prod_{i = 1}^{\phi(n)} x_i \equiv a^{\phi(n)} \cdot \prod_{i =1}^{\phi(n)} x_i \ (\mathrm{mod\ } n)\)
5. Using the cancellation law, deduce that \(a^{\phi(n)} \equiv 1\ (\mathrm{mod\ } n)\)
In this part, you will prove some basic properties of the \(\phi\) function:
1. Let \(p\) be prime. Show that \(\phi(p) = p - 1\).
2. Let \(p, q\) be primes. By writing out \(1, \ldots , pq\) in a \(p\times q\) table, deduce that \(\phi(p\cdot q) = (q-1) \cdot (p-1)\).
In this part, verify that the RSA cryptosystem works:
1. Receiver: Choose two large primes \(p, q\) and a large value \(n\).
2. Receiver: Choose \(e \in \mathbb{Z}_{\phi(n)}\) such that \(\mathrm{gcd}(e, \phi(n)) = 1\).
3. Receiver: Publish \(n\) and \(e\).
4. Sender: Wants to send message \(M \in \mathbb{Z}_{n}\). So, sends \(M^e \ (\mathrm{mod\ } n)\)
5. Receiver: Compute \(d\) such that \(ed \equiv 1\ (\mathrm{mod\ } \phi(n))\) (using extended gcd algorithm)
6. Receiver: \((M^e)^d \equiv M^{ed} \equiv M^{ed \equiv 1 \ (\mathrm{mod\ } \phi(n))} \equiv M \ (\mathrm{mod\ } n)\), so they can read the message.

Project 2 [Cyclic groups in \(\mathbb{Z}_n\)]:

(Useful for Discrete mathematics and Cryptography)

In the cyclic groups exercise, you showed that every element generates a cyclic group. In this exercise, you will determine the cyclic groups of \((\mathbb{Z}_n, +_n)\). For example, for \(n = 6\),

For \(a = 1\), \(a^1 = 1\), \(a^2 = 2\), \(a^3 = 3\), \(a^4 = 4\), \(a^5 = 5\), \(a^6 = 0\).
For \(a = 2\), \(a^1 = 2\), \(a^2 = 4\), \(a^3 = 0\).
For \(a = 3\), \(a^1 = 3\), \(a^2 = 0\).
For \(a = 4\), \(a^1 = 4\), \(a^2 = 2\), \(a^3 = 0\).
For \(a = 5\), \(a^1 = 5\), \(a^2 = 4\), \(a^3 = 3\), \(a^4 = 2\), \(a^5 = 1\), \(a^6 = 0\).

Write a program to find the cyclic group corresponding to every element of \((\mathbb{Z}_n, +_n)\). Do you notice a pattern? When does the cyclic group of \(a\) contain the entire \(\mathbb{Z}_n\)?
Let \(a\in \mathbb{Z}_n\) (\(a\neq 0\)) and \(\mathrm{gcd}(a, n) = 1\). Show that for every \(y \in \mathbb{Z}_n\), there exists \(x \in \mathbb{Z}_n\) such that \(a x \equiv y\ (\mathrm{mod\ } n)\).
Show that for \(a\in \mathbb{Z}_n\) (\(a\neq 0\)) and \(\mathrm{gcd}(a, n) = 1\), the cyclic group for \(a\) contains all elements of \(\mathbb{Z}_n\).
Let \(a\in \mathbb{Z}_n\) (\(a\neq 0\)) and \(\mathrm{gcd}(a, n) = d\). Show that for \(y \in \mathbb{Z}_n\), there exists \(x \in \mathbb{Z}_n\) such that \(ax \equiv y \ (\mathrm{mod\ } n)\) only if \(d \vert y\).
Show that for \(a\in \mathbb{Z}_n\) (\(a\neq 0\)) and \(\mathrm{gcd}(a, n) = d\), the cyclic group for \(a\) contains only the multiples of \(d\).

Project 3 [Periodicity in Markov chains]:

(Useful for Discrete Maths, Algorithms and Probability courses)

Show how to compute the gcd of \(n\) integers when given a \(\mathrm{gcd}\) function that takes two arguments.
Show that the Chicken McNugget theorem implies that for \(a, b \in \mathbb{Z}^+\) with \(\mathrm{gcd}(a, b) = g\), there exists a number \(m\), so that for all \(m' \in \mathbb{Z}^+\) with \(m'\cdot g > m\), \(m'\cdot g\) is representable as a linear combination of \(a\) and \(b\) with non-negative coefficients.
Use (1) and (2) to show that for \(x_1, \ldots , x_n \in \mathbb{Z}^+\) and \(\mathrm{gcd}(x_1, \ldots , x_n)\) there is an integer \(m\) such that for all \(m' \in \mathbb{Z}^+\) with \(m' > m\), \(m' \cdot g\) is representable as a linear combination of \(x_1, \ldots , x_n\) with non-negative coefficients.
A graph consists of vertices and edges (with direction) between the vertices. A graph is irreducible if for every two vertices \(x, y\), there exists a path of some length from \(x\) to \(y\). For example, in the figure below, the graph on the left is not irreducible (since you cannot get from \(1\) to \(3\)) and the other two graphs are.

We define for a vertex \(x\), \(T(x) = \lbrace t \geq 1 : \text{there is a path of length }t\text{ from }x\text{ to }x \rbrace\). The period \(p(x)\) of a vertex \(x\) is the greatest common divisor of the elements of \(T(x)\).

Show that if a graph is irreducible, then for all vertices \(x, y\), \(p(x) = p(y)\).
A graph is aperiodic if all vertices have period \(1\) (middle one is aperiodic). Show that for a graph that is aperiodic and irreducible, there is an integer \(r\) such that for all \(x\) and \(y\) there is a path from \(x\) to \(y\) of length \(r\).

Note: Irreducible and aperiodic graphs where the edge weights represent probabilities are extremely important in the study of Markov chains, as they satisfy several important properties.

Project 4 [Chinese Remainder Theorem]:

(Good practice for congruences, useful for Cryptography, (Group Theory) and Magic tricks)

Prove the Chinese Remainder Theorem: Consider \(a_1 \in \mathbb{Z}_{m_1}\) and \(a_2 \in \mathbb{Z}_{m_2}\) and \(x \in \mathbb{Z}_{m_1 \cdot m_2}\) such that \(x \equiv a_1 \ (\mathrm{mod\ } m_1)\) and \(x \equiv a_2 \ (\mathrm{mod\ } m_2)\). Then, \(x\) is uniquely determined.
Follow the steps in 2007p2q4 to prove the general version of the Chinese Remainder Theorem.
Prove why this Numberphile magic trick works.

Project 5 [Binary GCD (Stein’s algorithm)]:

(Good practice for mathematical reasoning, Useful for Discrete mathematics and Algorithms)

Read the Wikipedia page and:

Implement the binary GCD algorithm in OCaml.
Write a proof for why the binary GCD algorithm computes the GCD. [You may want to use the 2000p1q8 as guide]

Project 6 [Josephus problem]:

(Good practice for mathematical reasoning, Useful for Discrete mathematics and Algorithms)

Read Chapter 1.3 of “Concrete Mathematics” by Graham, Knuth and Patashnik and watch this Numberphile video.

Mathematically formulate the Josephus problem.
Write a program that solves the general version of Josephus problem.
Write a proof for the closed formula solution to Josephus problem.

Project 7 [Dismal arithmetic]:

(Good practice for discrete structures, Not useful for any course other than Discrete maths)

Watch this Numberphile video and if you want have a look at the original paper.

State a formal definition for dismal arithmetic.
Show that dismal plus is associative and commutative.
Show that dismal multiply is associative and commutative.
Show that dismal mutliply distibutes over dismal plus.
State the definition of a dismal prime.
Show that there are infinitely many dismal primes.

Project 8 [Wilson’s Theorem]:

(Good practice for number theory, Useful for Discrete Maths)

In this project, you will prove Wilson’s theorem:

For integer \(p > 1\), \((p-1)! +1\) is divisible by \(p\) iff \(p\) is prime.

(Forward direction) Assume that \(p\) is composite and by considering one of its factors \(d \neq 1\), show that for \(p\) to divide \((p-1)! +1\), \(d \vert 1\) (reaching a contradiction).
(Reverse direction) Consider \(a \in \mathbb{Z}_p \backslash \lbrace 0 \rbrace\) and \(p\) an odd prime:
1. Show that every \(a\) has an inverse \(a^{-1}\).
2. Show that the inverse of \(a^{-1}\) is \(a\) (i.e. inverses occur in pairs).
3. Show that \(a = a^{-1}\) implies \(a^2 = 1\) (under \(\cdot_p\)).
4. Show that \(a^2 = 1 \in \mathbb{Z}_p\), implies \(a = 0\) or \(a = p - 1\).
5. By pairing elements to their inverses show that
  \[(p-1) \cdot_p (p-2) \cdot_p \ldots \cdot_p 1 = p-1\]
  and deduce that \((p-1)! +1\) is divisible by \(p\).
Complete the reverse direction by showing that the statement holds for \(p = 2\).
Can this formula be used to generate primes?

Project 9 [Luca’s Theorem + Pascal’s Triangle]:

(Good practice for number theory, Useful for Discrete Maths)

In this project, you will explore Luca’s theorem and its connection to Pascal’s triangle.

Read this article by Brilliant.
State Luca’s theorem.
Re-write the proof in the article, justifying every step of the proof.
How does it relate to Pascal’s triangle?

Project 10 [Finite calculus]

(Great insight into connection between discrete and continuous sums)

Read section 2.6 of “Concrete Mathematics” by Graham, Knuth and Patashnik or this handout.

Define the difference operator.
Define the falling factorial powers. What is their importance for the difference operator?
Define the indefinite sum.
Show which basic rules of integration hold.
Demonstrate in an example, how finite calculus helps us evaluate a sum.

Project 11 [Peano’s axioms]

(Axiomatic foundations of number theory)

Read pages 1-7 from “Numbers, sets and axioms” by A.G. Hamilton.

Write down the five Peano’s axioms for natural numbers and reason (at a high level) why we need each of these.
How is additional defined?
How is multiplication defined?
Prove that addition and multiplication are commutative for natural numbers.
Prove that addition and multiplication are associative for natural numbers.
How is comparison defined between natural numbers?
Prove that every subset of the natural numbers has a least member.
(Optional) How is the set of integers \(\mathbb{Z}\) defined?

Project 12 [Alternative proofs to the core theorems]:

(Good practice for number theory, Useful for Discrete Maths)

Read about the following alternative proofs and write an exposition about them.

Combinatorial proof for Fermat’s Little Theorem (video, blog, notes).
Fermat’s Little Theorem using inverses.
1. Read about the generalisation of this technique to prove Euler-Fermat’s theorem (see FLT handout).
2. Read about Wilson’s theorem and explain how to use this technique to prove it (see wikipedia).
Fundamental theorem of arithmetic (wikipedia) which does not make use of Euclid’s theorem.
Infinitude of primes (see Chapter 1 in “Proofs from the Book” by Aigner and Ziegler).
Visual explanation for the gcd algorithm (see here).
1. (optional) Also read about the lcm algorithm.

Project 13 [What did Euclid really know?]:

In this project you will read some of the translated parts of Euclid’s short books, called Elements VII, VIII, IX (which can be found here) and establish connections between the propositions there and the lemmas/theorems of the lecture notes.

Read this high-level introduction to Euclid’s Elements.
Start by going through the VII book (see here) for some guidance. Try to indentify which propositions you also proved in lectures. Can you find a proof for some that you did not cover?
(Only if you have time) Go through the IX and VIII books (in that order) and do the same.

Project 14 [How many primes are there?]: (++)

In computer science, why do we care about how many primes are there below a number \(x\)? (Hint: how would you find a prime number to be used e.g. in the RSA)
(optional) Implement your favorite algorithm for finding primes and create a plot for the number of primes below \(x\). On the same plot graph \(x / \log(x)\). What do you notice?
The prime number theorem states that the number of primes below \(x\) for large \(x\) is approximately \(x / \log(x)\). The proofs for this theorem are quite advanced (using complex analysis) or complicated. However, for our purposes in computer science in most cases we do not care about the precise limit. Showing \(\Theta(x / \log(x))\) is good enough. Follow these slides or this chapter to prove Chebyshev’s prime number theorem. (You may prefer to read Chapter 9 in “Asymptopia” by Joel Spencer OR this exposition)

Project 15 [Matrices and recurrence relations]:

Complete the optional section on the relation between Fibonacci numbers and matrices in the Fibonacci Handout.
In the Fibonacci handout you derived a closed-formula for the Fibonacci numbers, and in the FoCS course you saw how to compute the \(n\)-th Fibonacci number using matrix multiplication in \(O(\log n)\) operations. Why is the matrix formula prefered for computing the \(n\)-term?
Given a Fibonacci number how can you use the matrix multiplication approach to find the index of that number?
How would you use matrix exponentiation to find the \(n\)-th term of \(a_{n+4} = a_{n+3} + 10 a_{n+2} + 3 a_{n+1} + 4a_n\) with \(a_0 = a_1 = a_2 = 0\) and \(a_3 = 1\)? Determine the matrix and produce code to generate the first few terms.
How does this generalise to a general recurrence relation of the form \(a_{n+k} = \sum_{i = 0}^{k-1} c_i a_{n + i}\) where \(c_i\) are some known constants (and the first few terms of the sequence are also known).
How would you compute the \(n\)-th term of a recurrence relation of the form \(a_{n+2} = 3a_{n+1} + 2a_{n} + 11\) using matrix exponentiation? Hint: You will need a vector in \(3\) dimensions.
How would you compute the \(n\)-th term of a recurrence relation of the form \(a_{n+2} = 3a_{n+1} + 2a_{n} + 11 + (n+2)\) using matrix exponentiation? Hint: Write a recursive formula for \((n+2)\).
How would you compute the \(n\)-th term of a recurrence relation of the form \(a_{n+2} = 3a_{n+1} + 2a_{n} + 11 + (n+2) + (n+2)^2\) using matrix exponentiation?
How would you compute the \(n\)-term of a two interdependent recurrence relations \(a_{n+2} = a_{n+1} + 3b_{n+1} + a_n\) and \(b_{n+2} = b_{n+1} + 4a_{n}\)?

Project 16 [Some prime factorisation methods]:

(Good practice for number theory)

(optional) See relevant project in FoCS for Eratosthenes’ sieve.
Read about Fermat’s factorisation method (either from wikipedia, from Chapter 5.4 in “Elementary Number Theory By D. M. Burton, Chapter 4.5.4 of “The art of computer programming” by D. Knuth or from Chapter 1.9 in “Higher arithmetic” by H. Davenport).
1. How many steps are required to factorise a prime number?
2. Show an example of Fermat’s factorisation method.
3. Implement Fermat’s factorisation method.
4. Why does this method work well if the number has a divisor that is close to \(\sqrt{N}\) (where \(N\) is the number to be factored)?
5. (optional) Read about Lehman’s improvement.
(optional) Read about Draim’s algorithm in his article “An Algorithm on Divisibility” (see here) and write an implementation in OCaml.
Read about Pollard-Rho’s method from Chapter 31.9 of “Introduction to Algorithms” and complete as many of the exercises as you can.

Project 17 [Miller-Rabin primality testing]:

(Good practice for number theory)

In this project, you will go through the Miller-Rabin algorithm (Chapter 31.8 in “Introduction to Algorithms”). Then you have the option to either write an exposition for the proof of Millen-Rabin (same chapter) or go (at high level) through the Solovay-Strassen and AKS primality testing algorithms (by reading this presenttation or chapters from the book “Primality Testing for Beginners” by L. Rempe-Gillen and R. Waldecker).

Project 18 [Erdős’ upper bound for Carmichael numbers]:

In this project you will explore Erdős’ proof for an upper bound for Carmichael numbers.

As a warm up, we explore the function \(\exp(a (\log(x))^b)\) for \(a > 0\) and \(0 < b < 1\).
1. Make a plot for \(\exp(\sqrt{\log(n)})\).
2. Make a plot for \(\exp(\log^{3/4}(n))\).
3. What happens as \(b \to 1\)? What happens as \(b \to 0\)?
4. Is the function increasing in \(a\)? Is the function increasing in \(b\)?
5. How do the functions \(\exp(a_1 (\log n)^b)\) and \(\exp(a_2 (\log n)^b)\) compare?
6. How does the function compare to \(\log(x)\), \(e^x\), \(\log(n)^n\), \(x^k\) (for \(0 < k < 1\))? Use \(\mathcal{O}(\cdot)\), \(\Omega(\cdot)\), \(o(\cdot)\) and \(\omega(\cdot)\) notation.
7. How does \(x^{k_1} \exp(\log(x) ^{b_1})\) compare with \(x^{k_2} \exp(\log(x) ^{b_2})\)?
Read the Euler-Fermat theorem section from the handout.
Read Erdős’ \(4\)-page paper, from JSTOR. You should write your own exposition of the proof. You may find the following questions helpful.
1. Which numbers are handled in case \(\Gamma_{1,1}\)?
  1. Define \(H\), \(k\).
  2. Why does \(2^r - 1\) have less than \(r\) prime factors? How is \(k\) upper bounded?
  3. How is the number of \(\Gamma_{1, 1}\) upper bounded? Note: \(\left( \frac{k}{t} \right)\) is an old notation for \(\binom{k}{t}\) and \(g\) does not refer to \(g(n)\).
  4. Why is \(W k^W (\log x / \log 2)^W\) smaller than \(x^{1/4}\)?
2. Which numbers are handled in case \(\Gamma_{1,2}\)?
  1. Define \(d(m)\) and \(v(m)\).
  2. Why is \(d(m) \geq 2^{v(m)}\)?
  3. Why is \(\sum_{m \leq x} \lfloor \frac{x}{m} \rfloor = \sum_{m \leq x} d(m)\)?
3. Which numbers are handled in case \(C_{2,1}\)?
  1. Define \(\delta\) and \(T\).
  2. Prove the equalities between \(n\), \(p\), \(\delta\), \(m\) and \(t\).
  3. The harmonic inequality says that \(\sum_{n=1}^N \frac{1}{n} \leq 1 + \log(N)\). How is this used to prove inequality (3)?
4. Which numbers are handled in case \(C_{2,1}\)?
  1. Define \(\delta_i\).
  2. Explain why \(H \leq T^k\).
  3. Explain the steps to bounding the number of elements in \(C_{2, 2}\).
5. How are the cases combined to yield the main theorem?
What implications does this upper bound have for the efficiency of Fermat’s primality test?

Project 19 [Recurrence relations and counting]:

(Good practice for recurrence relations, Useful for Probability and Formal Models of Language)

Complete as many of the following as you can.

Show that the number of ways to partition a list into sublists of length \(1\) or \(2\) is given by the Fibonacci numbers.
Count the numer of ways to tile a \(2 \times n\) board with \(2 \times 1\) and \(1 \times 2\) dominoes (for a hint see here).
Find a recurrence relation for the number of ways to partition a list into sublists of length \(1\), \(2\) or \(3\).
Derive the recurrence relation for the number of subsets of size \(k\) that can be created from a set of size \(n\).
[Stirling numbers of the First kind] Find a recurrence relation for \(s(n, k)\) the number of permutations of size \(n\) with \(k\) elements mapping to themselves (see wikipedia).
[Stirling numbers of the Second kind] Find a recurrence relation for the number of ways to partition a set of \(n\) items into \(k\) non-empty subsets (see wikipedia).
[Bell numbers] Find in terms of the Stirling numbers of the second kind, the number of partitions of a set of \(n\) items.
Find the number of bit strings of length \(n\) without two consecutive \(0\)s.
Count the number of steps needed to solve the Tower’s of Hanoi problem (see here).
[Catalan Numbers] Find a recurrence relation for the number of valid parentheses strings of length \(2n\) (e.g. ()() is valid, but ())( is not)(optional) Read about the second proof in wikipedia on how to solve the recurrence.
(optional) If you are interested in learning more, look at counting with generating functions.

Project 20 [Proof of Gödel’s incompleteness theorem]:

(Good practice for logic. Assumes that you have covered enumeration.)

In this project you will explore the proof of Gödel’s incompleteness theorem. We assume that if we can create an algorithm that computes \(f(x)\) then we assume it is representable in first-order logic (this will be seen in Part IB Computability and Logic & Proof).

At a high level what do Gödel’s incompleteness theorems state?
Read through this proof and try to write your own exposition of the proof. The following questions may be useful.
1. Which rules do we assume that our logic system supports?
2. How can we encode the statements in the proof system as natural numbers?
3. What is the provability predicate and why does it satisfy (7), (8), (9)?
4. Explain the construction of \(B_k(n)\) where \(n\) is a free variable (i.e. not bound by an existential or universal quantifier).
5. What is the diagonalisation of \(B(x)\)?
6. Prove (12) and (13).