Discrete Mathematics
—MATH1061 & MATH7861 in Semester 2, 2020—
Thursday 29 October
Benjamin Burton
Discrete Mathematics Thursday 29 October
Housekeeping
Revision session: Next Thursday, 5 November, 9am onwards, usual zoom link.
Final exam: Covers the entire course!
What you see today is non-examinable. . . but I hope interesting!
Discrete Mathematics Thursday 29 October
Hamiltonian circuits
An Eulerian circuit is a walk that starts and ends at the same vertex, and that uses every edge exactly once.
An Hamiltonian circuit is a walk that starts and ends at the same vertex, and that uses every vertex exactly once.
(Except for the start = end vertex, which must appear twice.)
We have a simple test for whether an Eulerian circuit exists. Is there a simple test for whether a Hamiltonian circuit exists?
Find one—or prove that you cannot—and you can have $1 000 000! This would solve the famous P vs NP problem.
Discrete Mathematics Thursday 29 October
P vs NP
A decision problem is a yes/no question, for which we wish to find an algorithm.
Examples:
Input: k ∈ N.
Question: Is k prime? Input: A graph G.
Question: Does G have an Eulerian circuit? Input: Logical statement forms P,Q.
Question: Is P ≡ Q?
P vs NP is about which decision problems you can solve quickly, and which problems are inherently difficult.
Discrete Mathematics Thursday 29 October
What do we mean by “quickly”?
Let n measure the size of the input:
Input: A graph G.
Question: Does G have an Eulerian circuit? Inputsize: n=|V(G)|+|E(G)|
Input: Logical statement forms P,Q.
Question: Is P ≡ Q?
Input size: n = number of symbols used in P and Q
Input: k ∈ N.
Question: Is k prime?
Input size: n = number of digits in k
An algorithm is considered fast if its running time (the number of steps required) is no worse than a polynomial in n.
Fast running times: n, n log n, n2, n5, n100 Slow running times: 2n, n!, een
Discrete Mathematics Thursday 29 October
The classes P and NP
A decision problem is in the class P if you can solve it quickly. Input: A graph G. Question: Is there an Eulerian circuit?
Solution: Check connectedness and even edge degrees. Input: k,l ∈ N. Question: Are k and l coprime?
Solution: Euclid’s algorithm!
A decision problem is in the class NP if, when the answer is “yes”,
I can give you information that lets you verify my solution quickly. Input: A graph G. Question: Is there a Hamiltonian circuit?
Information: I give you the circuit. Input: k ∈ N. Question: Is k composite?
Information: I give you the prime factorisation of k.
We know how to quickly test whether k is compositite.
We do not know how to quickly test if G has a Hamiltonian circuit!
Discrete Mathematics Thursday 29 October
P vs NP
The question P vs NP asks: are P and NP the same?
That is, if a “yes” solution is fast to verify, does that mean the
problem must be fast to solve?
The hardest problems in NP are called NP-complete:
a fast solution to any one of these would give a fast solution to every problem in NP!
Some NP-complete problems:
Input: A graph G. Does G have a Hamiltonian circuit? Input: A logical statement form P. Can P ever be true? Input: A set S ⊆ Z. Does S have a subset whose sum is 0?
If you can find a fast test for a Hamiltonian circuit, then you will show that P = NP!
Many people think that P ̸= NP. . . but they are not unanimous!
Discrete Mathematics Thursday 29 October
The Book
Paul Erd ̋os (1913–1996) was very interesting and very prolific.
Read about him on Wikipedia!
Erd ̋os would talk about The Book, in which God kept the most beautiful mathematical proofs.
“You don’t have to believe in God, but you should believe in The Book.”
Discrete Mathematics Thursday 29 October
Sums of squares
How many ways can we write an integer as a sum of two squares? n=a2+b2, wherea,b∈Z
For n = 13, there are eight solutions:
13 = 32 +22 = (−3)2 +22 = 32 +(−2)2 = (−3)2 +(−2)2
= 22 +32 = (−2)2 +32 = 22 +(−3)2 = (−2)2 +(−3)2 For n = 16, there are four solutions:
16=42 +02 =(−4)2 +02 =02 +42 =02 +(−4)2 For n = 11, there are no solutions.
Define a function f : N → Z, where f (n) denotes the number of solutionsforn. Sof(13)=8,f(16)=4,andf(11)=0.
Discrete Mathematics Thursday 29 October
How does f (n) behave on average?
What do you think happens to f (n) on average, as n grows large?
Let’s vote!
1 The average f (n) approaches 0
2 The average f (n) approaches the limit 1
3 The average f (n) approaches a limit between 1 and 4
4 The average f (n) approaches the limit 4
5 The average f (n) approaches a limit greater than 4
6 The average f (n) grows towards infinity
Discrete Mathematics Thursday 29 October
Looking at f (n)
n = 1 .. 10
0 2 4 6 8 10
n
Average f (n) ≃ 3.6
Discrete Mathematics Thursday 29 October
f(n)
02468
Looking at f (n)
n = 1 .. 100
0 20 40 60 80 100
n
Average f (n) ≃ 3.16
Discrete Mathematics Thursday 29 October
f(n)
0 5 10 15
Looking at f (n)
Discrete Mathematics
Thursday 29 October
0
200 400
600 800 1000
n = 1 .. 1000
0 5 10 15 20
f(n)
Average f (n) ≃ 3.148
n
Looking at f (n)
Discrete Mathematics
Thursday 29 October
0
2000 4000
Average f (n) ≃ 3.1416
n = 1 .. 10000
0 10 20 30 40
f(n)
n
6000 8000
10000
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. :
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. :
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 1:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 2:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 3:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 4:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 5:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 6:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 7:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 8:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 9:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 10:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 11:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 12:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 13:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 14:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 15:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 16:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 17:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 18:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 19:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Marking the solutions to a2 + b2 = 20:
Discrete Mathematics Thursday 29 October
Theorem
As n grows, the average of f (1), . . . , f (n) approaches π!
Proof: Consider pairs of integers a, b as lattice points. Thesolutionstoa2+b2 ≤nfillacircleofradius√n!
Discrete Mathematics Thursday 29 October
The average of f(1),…,f(n) is f(1)+f(2)+…+f(n).
n
But f(1)+f(2)+…+f(n) is the number of integer solutions to the equation a2 + b2 ≤ n (excluding the trivial case a = b = 0).
√
n So,asnbecomeslarge,f(1)+f(2)+…+f(n)≃π√n2 =π·n.
This is the number of lattice points inside the circle of radius (excluding the origin), which is roughly the area of this circle!
The average then becomes
f(1)+f(2)+…+f(n) ≃ π·n =π. nn
Discrete Mathematics Thursday 29 October
A different question about lattice points
Question
If you stand at the origin, what fraction of lattice points are visible?
A lattice point (a, b) is visible if and only if a and b are coprime!
Discrete Mathematics Thursday 29 October
A different question about lattice points
Question
If you stand at the origin, what fraction of lattice points are visible?
A lattice point (a, b) is visible if and only if a and b are coprime!
Discrete Mathematics Thursday 29 October
A different question about lattice points
Question
If you stand at the origin, what fraction of lattice points are visible?
A lattice point (a, b) is visible if and only if a and b are coprime!
Discrete Mathematics Thursday 29 October
A different question about lattice points
Question
If you stand at the origin, what fraction of lattice points are visible?
A lattice point (a, b) is visible if and only if a and b are coprime!
Discrete Mathematics Thursday 29 October
A different question about lattice points
Question
If you stand at the origin, what fraction of lattice points are visible?
A lattice point (a, b) is visible if and only if a and b are coprime!
Discrete Mathematics Thursday 29 October
A different question about lattice points
Question
If you stand at the origin, what fraction of lattice points are visible?
A lattice point (a, b) is visible if and only if a and b are coprime!
Discrete Mathematics Thursday 29 October
A different question about lattice points
Question
If you stand at the origin, what fraction of lattice points are visible?
A lattice point (a, b) is visible if and only if a and b are coprime!
Discrete Mathematics Thursday 29 October
A lattice point (a, b) is visible if and only if a and b are coprime.
So, the question becomes:
If you choose two integers n, m ∈ Z at random, what is the probability that n and m are coprime?
There is some delicacy required when talking about infinities: What do we mean by a “fraction of all lattice points”? How we choose an integer at random?
This is another story for another time.
Discrete Mathematics Thursday 29 October
Observation: Two integers n and m are not coprime if and only if some prime p divides both n and m.
So: n and m are coprime if and only if:
eithern̸≡0 (mod2)orm̸≡0 (mod2);and eithern̸≡0 (mod3)orm̸≡0 (mod3);and eithern̸≡0 (mod5)orm̸≡0 (mod5);and eithern̸≡0 (mod7)orm̸≡0 (mod7);and…
What are the probabilities? For any prime p: n ≡ 0 (mod p) with probability 1 .
p
n ≡ 0 and m ≡ 0 (mod p) with probability 1 · 1 = 1 . p p p2
n̸≡0orm̸≡0 (modp)withprobability1− 1 . p2
These properties are independent for different primes p, and so n and m are coprime with probability:
(1− 1)(1− 1)(1− 1)(1− 1)… 22 32 52 72
Discrete Mathematics Thursday 29 October
How can we evaluate (1− 1 )(1− 1 )(1− 1 )(1− 1 )…? 22 32 52 72
1 =1+x+x2+x3+…(aninfinitegeometricsum). 1−x
So, if our probability is x, then 1/x is:
(1+1+ 1 + 1 + 1 +…)
22 (22 )2 (22 )3 (22 )4
× (1+1+ 1 + 1 + 1 +…)
32 (32 )2 (32 )3 (32 )4
× (1+1+ 1 + 1 + 1 +…)
52 (52 )2 (52 )3 (52 )4
× (1+1+ 1 + 1 + 1 +…) × …
72 (72 )2 (72 )3 (72 )4 What happens when we expand this? We get:
11111 ∞1π2
1 + 22 + 32 + 42 + 52 + 62 + . . . =
Therefore our final probability is 6 ≃ 0.608. π2
n=1
n2 = 6 .
Discrete Mathematics Thursday 29 October
What did we just do?
∞ 1 π 2
n=1 n2 = 6 is a particular value of the Riemann zeta function:
ζ ( s ) = ∞ 1 , n=1 ns
where s can be any complex number.
We need Re(s) > 1 for this sum to converge, but there are ways to
extend this definition to all s ∈ C.
The zeta function is central to analytic number theory.
It has many far-reaching consequences; for instance, it tells us much about the distribution of primes.
When is ζ(s) = 0?
This would answer the Riemann hypothesis, also worth $1 000 000!
Discrete Mathematics Thursday 29 October
So. . . what is mathematics?
Mathematics consists in proving the most obvious thing in the least obvious way.
– George Polya Mathematics is no more computation than typing is literature.
– John Allen Paulos
Mathematics is not a careful march down a well-cleared highway, but a journey into a strange wilderness, where the explorers often get lost. Rigour should be a signal to the historian that the maps have been made, and the real explorers have gone elsewhere.
– W. S. Anglin
Discrete Mathematics Thursday 29 October
Reading
Proofs from THE BOOK
Martin Aigner and Gu ̈nter M. Ziegler
You can download this via SpringerLink if you are on campus!
Forever undecided: a puzzle guide to G ̈odel
Raymond M. Smullyan
G ̈odel, Escher, Bach: an Eternal Golden Braid
Douglas R. Hofstadter
Good luck with exams!
Discrete Mathematics Thursday 29 October