cs2102: Discrete Math
Class 23: Cryptosystems (Thu, 16 Nov 2017)
Schedule
Here’s the updated (and final) schedule for the rest of the semester:
- Problem Set 9: due on Friday, 1 December at 6:29pm. (This will be posted on 19 November.)
- Problem Set ω (this is optional, and not like the others, hence it uncountable number): due on Monday, 4 December at 11:59pm. See the Problem Set ω description for examples from previous students.
- Final Exam: Thursday, 7 December, 9am-noon (in the normal lecture room)
Modular Arithmetic
Definition: A number $a$ is congruent to $b$ modulo $n$ if and only if $n\, | \, (a - b)$. We can write this as $a \equiv b \;\; (\text{mod}; n)$.
Prove: $a \equiv b \;\; (\text{mod}\; n)$ iff $\text{rem}(a, n) = \text{rem}(b, n)$.
#
Groups, Rings, and Fields
Abelian group: set $R$, with a binary operation $+$:
associative, commutative, additive identity (0), additive inverse ($−a$)
Ring: set $R$, with two binary operations $+$, $\times$:
Abelian group under $+$
associative, multiplicative identity (1) under $\times$
TODO: finish
Class 22: Prime Detectives (Tue, 14 Nov 2017)
Schedule
Here’s the updated (and final) schedule for the rest of the semester:
- Problem Set 9: due on Friday, 1 December at 6:29pm. (This will be posted on 19 November.)
- Problem Set Omega (this is optional, and not like the others, hence it uncountable number): due on Monday, 4 December at 11:59pm.
- Final Exam: Thursday, 7 December, 9am-noon (in the normal lecture room)
Challenge Solution
Connor Roos’ solution to the challenge problem about the minimum number of NAND operations (using gates, not formulas) is here: Description (PDF), Code (Java).
Exam 2 Solutions
The solutions for Exam 2 are here: PDF. Please read these carefully and come to office hours with any questions you have, especially if you had difficulties on any of the exam problems.
Excerpt
G. H. Hardy, A Mathematician’s Apology, 1940.
A man (sic - Hardy’s quote, unfortunately, but typical for 1940, uses sexist language throughout, but I will leave it as written, but “man” here means “person”, and “he” and “his” are not meant to be limited to males) who sets out to justify his existence and his activities has to distinguish two different questions. The first is whether the work which he does is worth doing; and the second is why he does it, whatever its value may be. The first question is often very difficult, and the answer very discouraging, but most people will find the second easy enough even then. Their answers, if they are honest, will usually take one or other of two forms; and the second form is a merely a humbler variation of the first, which is the only answer we need consider seriously.(1) ‘I do what I do because it is the one and only thing that I can do at all well. I am a lawyer, or a stockbroker, or a professional cricketer, because I have some real talent for that particular job. I am a lawyer because I have a fluent tongue, and am interested in legal subtleties; I am a stockbroker because my judgment of the markets is quick and sound; I am a professional cricketer because I can bat unusually well. I agree that it might be better to be a poet or a mathematician, but unfortunately I have no talent for such pursuits.’
I am not suggesting that this is a defence which can be made by most people, since most people can do nothing at all well. But it is impregnable when it can be made without absurdity, as it can by a substantial minority: perhaps five or even ten percent of men can do something rather well. It is a tiny minority who can do something really well, and the number of men who can do two things well is negligible. If a man has any genuine talent he should be ready to make almost any sacrifice in order to cultivate it to the full.
…
There is also what I call the ‘humbler variation’ of the standard apology; but I may dismiss this in a very few words.
(2) ‘There is nothing that I can do particularly well. I do what I do because it came my way. I really never had a chance of doing anything else.’ And this apology too I accept as conclusive. It is quite true that most people can do nothing well. If so, it matters very little what career they choose, and there is really nothing more to say about it. It is a conclusive reply, but hardly one likely to be made by a man with any pride; and I may assume that none of us would be content with it.
…
A man’s first duty, a young man’s at any rate, is to be ambitious. Ambition is a noble passion which may legitimately take many forms; there was something noble in the ambitions of Attila or Napoleon; but the noblest ambition is that of leaving behind something of permanent value — …
There are many highly respected motives which may lead men to prosecute research, but three which are much more important than the rest. The first (without which the rest must come to nothing) is intellectual curiosity, desire to know the truth. Then, professional pride, anxiety to be satisfied with one’s performance, the shame that overcomes any self-respecting craftsman when his work is unworthy of his talent. Finally, ambition, desire for reputation, and the position, even the power or the money, which it brings. It may be fine to feel, when you have done your work, that you have added to the happiness or alleviated the sufferings of others, but that will not be why you did it. So if a mathematician, or a chemist, or even a physiologist, were to tell me that the driving force in his work had been the desired to benefit humanity, then I should not believe him (nor should I think the better of him if I did). His dominant motives have been those which I have stated, and in which, surely, there is nothing of which any decent man need be ashamed.
If intellectual curiosity, professional pride, and ambition are the dominant incentives to research, then assuredly no one has a fairer chance of satisfying them than a mathematician. His subject is the most curious of all—there is none in which truth plays such odd pranks. It has the most elaborate and the most fascinating technique, and gives unrivalled openings for the display of sheer professional skill. Finally, as history proves abundantly, mathematical achievement, whatever its intrinsic worth, is the most enduring of all.
…
A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas. … The mathematician’s patterns, like the painter’s or the poet’s must be beautiful; the ideas like the colours or the words, must fit together in a harmonious way. Beauty is the first test: there is no permanent place in the world for ugly mathematics.
…
The fact is that there are few more ‘popular’ subjects than mathematics. Most people have some appreciation of mathematics, just as most people can enjoy a pleasant tune; and there are probably more people really interested in mathematics than in music. Appearances suggest the contrary, but there are easy explanations. Music can be used to stimulate mass emotion, while mathematics cannot; and musical incapacity is recognized (no doubt rightly) as mildly discreditable, whereas most people are so frightened of the name of mathematics that they are ready, quite unaffectedly, to exaggerate their own mathematical stupidity.
…
It is undeniable that a good deal of elementary mathematics—and I use the word ‘elementary’ in the sense in which professional mathematicians use it, in which it includes, for example, a fair working knowledge of the differential and integral calculus—has considerable practical utility. These parts of mathematics are, on the whole, rather dull; they are just the parts which have the least aesthetic value. The ‘real’ mathematics of the ‘real’ mathematicians, the mathematics of Fermat and Euler and Gauss and Abel and Riemann, is almost wholly ‘useless’ (and this is as true of ‘applied’ as of ‘pure’ mathematics). It is not possible to justify the life of any genuine professional mathematician on the ground of the ‘utility’ of his work.
But here I must deal with a misconception. It is sometimes suggested that pure mathematicians glory in the uselessness of their work, and make it a boast that it has no practical applications. The imputation is usually based on an incautious saying attributed to Gauss, to the effect that, if mathematics is the queen of the sciences, then the theory of numbers is, because of its supreme uselessness, the queen of mathematics—I have never been able to find an exact quotation. I am sure that Gauss’s saying (if indeed it be his) has been rather crudely misinterpreted. If the theory of numbers could be employed for any practical and obviously honourable purpose, if it could be turned directly to the furtherance of human happiness or the relief of human suffering, as physiology and even chemistry can, then surely neither Gauss nor any other mathematician would have been so foolish as to decry or regret such applications. But science works for evil as well as for good (and particularly, of course, in time of war); and both Gauss and less mathematicians may be justified in rejoicing that there is one science at any rate, and that their own, whose very remoteness from ordinary human activities should keep it gentle and clean.
…
We have concluded that the trivial mathematics is, on the whole, useful, and that the real mathematics, on the whole, is not; that the trivial mathematics does, and the real mathematics does not, ‘do good’ in a certain sense; but we have still to ask whether either sort of mathematics does harm. It would be paradoxical to suggest that mathematics of any sort does much harm in time of peace, so that we are driven to the consideration of the effects of mathematics on war. It is every difficult to argue such questions at all dispassionately now, and I should have preferred to avoid them; but some sort of discussion seems inevitable. Fortunately, it need not be a long one.
There is one comforting conclusions which is easy for a real mathematician. Real mathematics has no effects on war. No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems very unlikely that anyone will do so for many years. It is true that there are branches of applied mathematics, such as ballistics and aerodynamics, which have been developed deliberately for war and demand a quite elaborate technique: it is perhaps hard to call them ‘trivial’, but none of them has any claim to rank as ‘real’. They are indeed repulsively ugly and intolerably dull; even Littlewood could not make ballistics respectable, and if he could not who can? So a real mathematician has his conscience clear; there is nothing to be set against any value his work may have; mathematics is, as I said at Oxford, a ‘harmless and innocent’ occupation.
The trivial mathematics, on the other hand, has many applications in war. The gunnery experts and aeroplane designers, for example, could not do their work without it. And the general effect of these applications is plain: mathematics facilitates (if not so obviously as physics or chemistry) modern, scientific, ‘total’ war.
It is not so clear as it might seem that this is to be regretted, since there are two sharply contrasted views about modern scientific war. The first and the most obvious is that the effect of science on war is merely to magnify its horror, both by increasing the sufferings of the minority who have to fight and by extending them to other classes. This is the most natural and orthodox view. But there is a very different view which seems also quite tenable, and which has been stated with great force by Haldane in Callinicus. It can be maintained that modern warfare is less horrible than the warfare of pre-scientific times; that bombs are probably more merciful than bayonets; that lachrymatory gas and mustard gas are perhaps the most humane weapons yet devised by military science; and that the orthodox view rests solely on loos-thinking sentimentalism. It may also by urged (though this was not one of Haldane’s theses) that the equalization of risks which science was expected to bring would be in the long range salutary; that a civilian’s life is not worth more than a soldier’s, nor a woman’s more than a man’s; that anything is better than the concentration of savagery on one particular class; and that, in short, the sooner war comes ‘all out’ the better.
I do not know which of these views is nearer to the truth. It is an urgent and a moving question, but I need not argue it here. It concerns only the ‘trivial’ mathematics, which it would be Hogben’s business to defend rather than mine. The cases for his mathematics may be rather more than a little soiled; the case for mine is unaffected.
Indeed, there is more to be said, since there is one purpose at any rate which the real mathematics may serve in war. When the world is mad, a mathematician may find in mathematics an incomparable anodyne.
Number Theory
Definition: $a$ divides $b$ ($a\, |\, b$) iff there is an integer $k$ such that $ak = b$.
Definition: A prime is a number greater than 1 that is divisible only by itself and 1.
Theorem: There are infinitely many prime numbers.
Prove by contradiction (and well ordering principle):
# ##
Fundamental theorem of arithmetic: every positive number $n$ can be written uniquely as a product of primes: $n = p_1 \cdot p_2 \cdot \cdots \cdot p_k$ where $pi \le p{i + 1}$.
Groups and Rings
$R$ is an Abelian group with respect to binary operation $P$ if it is:
- associative: $\forall a, b, c \in R. (a P b) P c = a P (b P c)$.
- commutative: $\forall a, b \in R. a P b = b P a$.
- has an identity: $\exists z \in R . \forall a \in R . a P z = a$.
- every element has an inverse with respect to that identity: $\forall a \in R . \exists w \in R . a P w = z$.
Which of these are Abelian groups:
- $R = \mathbb{N}, P = +$.
- $R = \mathbb{N}, P = \times$.
- $R = \mathbb{Z}, P = +$.
- $R = \mathbb{Q}, P = \times$.
- $R = { T, F}, P = NAND$.
Schedule Updates (Sun, 12 Nov 2017)
We are adjusting the schedule for Problem Set 9 and Problem Set Ω from the original schedule. Instead of being due on Wednesday, November 22 as previously scheduled, Problem Set 9 will now be due on Friday, 1 December (6:29pm). Its scope will be expanded to include Classes 20-24, and we expect to posted it on November 19.
Problem Set Ω (which is optional and different, and will be discussed in class this week) will now be due on Monday, 4 December (11:59pm).
If the schedule change causes any hardship for you, and you would prefer to have a PS9 due on Nov 22, let one of the professors know and we can arrange something different.
Class 21: Review (Tue, 7 Nov 2017)
Exam 2
Exam 2 will be in class on Thursday, 9 Nov. See Class 20 notes for details on the exam.
Main Topics for Review
Today we review the topics that we learned after Exam 1 with the exception of number theory (which will not be included in Exam 2).
State Machines and how to argue about correctness of programs.
Recursive Definitions and how to prove statements about them using structural induction.
Infinite Sets and Cardinalities, and how to show sets are finite, infinite, countable, or uncountable.
State Machines
$M = (S, G \subset S \times S, q_0 \in S)$ defines a state machine.
$P$ is a preserved invariant if: $$ \forall q \in S. (P(q) \wedge (q \rightarrow r) \in G) \implies P®$$
Invariant Principle: If $P$ is a preserved invariant and $P(q_0)$ is true, then property $P$ is true for all reachable states.
Proving Program Correctness
To prove a program $R$ produces the correct output:
Model it as a state machine, $M$.
Show that $M$ eventually terminates.
Show partial correctness:
- Find a suitable preserved invariant $P$ for $M$.
- Show that $P(q)$ for all final states implies the output correctness property. (Final states are states where the execution terminates.)
- Show $P(q_0)$ — the perserved invariant holds for the start state.
Recursive Data Types
To define a recursive data type $D$:
Define one or more base objects, $d \in D$.
Define one or more constructor cases that specify how to construct a new object $d \in D$ from one or more previoulsy-constructed objects, $d_1, d_2, \ldots \in D$.
Problem Set 8 Comments (Sat, 4 Nov 2017)
The Problem Set 8 solutions and comments are now posted in collab: PDF
Class 20: Number Theory (Thu, 2 Nov 2017)
Schedule
Problem Set 8 is due Friday at 6:29pm.
Tuesday’s class will include a review for Exam 2. Before 6:59pm Monday, send to uvacs2102staff@gmail.com topics you would like to review. We will have a similar rule to Exam 1:
- Fewer than 10 total requests: it means, class is not being sufficiently challenged and we should be doing more difficult material (except for the 10 requestors who get exam exemptions).
- Exactly 10 total requests: all requestors get automatic exam exemptions, review requested topics.
- More than 10 requests implies we should spend Thursday’s class on reviewing requested topics, no exam exemptions.
Exam 2
Exam 2 will be in class on Thursday, 9 Nov. You can get a good idea for what to expect on Exam 2 based on Exam 1, and also by looking at the Practice Exam 2 (from last year’s class). We strongly encourage you to try to problems on your own, before looking at the posted solutions. The main difference is that this year, we did not cover the topic of “stable marriage”, but the our exam 2 will also cover the topic of infinities (i.e. infinite sets, countable and uncountable sets, etc.) as well.
Resources. Similarly to Exam 1, you will be permitted to use a single paper page of notes that you prepare and bring to the exam. It is fine to collaborate with others to prepare your notes. The page should be no larger than a US Letter size page ($8.5 \times 11$ inches), and you may write (or print) on both sides of the page. You may not use any special devices (e.g., magnifying glasses) to read your page. No other resources, other than your own brain, body, and writing instrument, are permitted during the exam.
Content. The problems on the exam will cover material from Classes 1–19, Problem Sets 1–8 (including the provided solutions), and the relevant material from MCS Chapters 1–8. However, only one problem will be about the material covered by Exam 1, and the rest will be on the material we covered since Exam 1 (namely, classes 13-19, problem sets 6–8, and chapters 6,7,8). Everything on the exam will be something you have seen in at least two of these (Classes, Problem Sets, and MCS Book), and most of the exam will be things you have seen in all three. If you understand the problems on the problem sets and questions on the class notes well enough to be able to answer similar questions, you should do well on the exam.
Simiarly to Exam 1, for most students, we believe the best way to prepare for the exam will be to (1) go over the problem sets and their solutions, and make sure you understand well any of the problems you did not get before; (2) go through the provided practice exam and try to solve all the problems on your own before reading the solutions; (3) go through the questions in the class notes and convince yourself you can answer them well; (4) re-read chapters of the book, solving the associated practice problems, especially for any sections on topics where you had difficulty on the problem sets. If you do #1 and #2 and understand well the problems on the practice exam, you should be confident you’ll do well on the exam; if you struggled on the problem sets, you would benefit from doing #3 and #4 as well.
Links
Divisibility
Number theory is a study of integers $\mathbb{Z}={0,-1,1,-2,2,\dots}$. Adding, multiplying, and negating, are 3 operators on integers that we can define in a straight-forward way. Dividing is more tricky. For that, we first define the notation $a \mid b$ to denote the simpler situation where $b = k \cdot a$ for some $k \in \mathbb{Z}$. In this case, we say that $a$ is a divisor of $b$ and that $b$ is a multiple of $a$.
Show that if we assume $a \mid b$ and $a \mid c$ (for any integers $a,b,c$), then for all integers $x,y$ it will hold that $a \mid xa + yb$.
#
When $b$ is \emph{not} a multiple of $a$, we can still have some form of division, stated in the following theorem.
Theorem [Division Theorem] For all integers $n,d$, there are integers $q$ (called the quotiont) and $r$ (called the remainder, denoted by $rem(m,d)$) such that
$$n = q \cdot d + r \text{and} 0\leq r < |d|.$$
Note that the remainder, as defined here, is always non-negative. For example when dividing $-3$ by $5$ we get $q=-1$ and $r=2$.
Definition A prime $p$, is an integer $p>1$ such that $1$ and $p$ are the only positive divisors of $p$. Other $n>1$ numbers (that are not prime) are called composite.
The following well-known theorem can be proved by strong induction on $n$.
Theorem [Fundamental theorem of arithmetic]. Any $n>1$ has a unique represention in the following form: $$ n = p_1^{a_1} \dots p_k^{a_k}$$ where $pi < p{i+1}$ and $p_i$ is prime for all $i$.
Hint for proof: Use strong induction on $n$, and try to show that any two different representations for $n$ will have the same `smallest’ prime $p_1$ and the same power $a_1$ for $p_1$.
Easy-to-state, but hard-to-solve problems
In number theory, we can easily state problems that are super hard to solve. These are some examples.
Goldbach’s conjecture: Any even integer $n>2$ can be written as $n=p+q$ where $p,q$ are both primes. The conjecture is still open, though we know that it is correct for all $n \leq 10^{18}$.
Twin prime’s conjecture: There infinite prime numbers $p$ where $p+2$ is also prime. Note that we cannot `check the conjecture up to $n$’ anymore! And it is still open…
Fermat’s last theorem: For any integer $n>2$ there are no integers $a,b,c$ where $a^n + b^n = c^n$. Note that for $n=2$ there are integer solutions like $3^2 + 4^2 = 5^2$. Fermat claimed to have a proof, but nobody knows if he really did or not. Andrew Wiles eventually proved this in 1994, hence we call it a theorem and not a conjecture anymore.
Greatest Common Divisor
Definition For natural numbers $m,n>0$ we call $d>0$ their \emph{greatest common divisor}, denoted by $d=gcd(m,n)$ if $d$ is the largest number such that $d \mid m$ and $d \mid n$. (Make sure to verify why we can always say that such $d$ exists.)
We can use the fundamental theorem of arithmetic, to compute the gcd of any given pairs of integers. But how efficient is it? The problem is that factoring numbers $m,n$ into their prime factors is not something we know how to do efficiently. In particular, no known algorithm is guaranteed to factor all numbers with $1000,000$ digits in less than an (estimated) thousand years! The conjecture is that no such `efficient’ algorithm exists, and many cryptographic algorithms assume this is the case!
Euclid’s Algorithm
Despite not knowing how to factor integers efficiently, Euclid showed how to find gcd quite efficiently. This shows, even if the most ``natural” algorithm fails for doing something efficiently, we should always consider the possibility that an alternative way could still exist.
def Euclid_gcd(m, n):
while n > 0:
r = rem(m,n)
m = n
n = r
return m
What is a good state machine modeling the behavior of Euclid’s algorithm?
Suppose $d$ is any integer (in particular, it could be the gcd of the original state $(m,n)$ of the state machine for Eclid’s algorithm). Show that $gcd(a,b)=d$ is a preserved invariant for the transition graph of this state machine. Namely, if we go from one state to another state, the gcd does not change.
#
If the Euclid’s algorithm ends, at the very last step we will have $n=0$ which means $m$ is indeed the right gcd for that particular (final) state. Together with the preserved invariant (that you proved above), argue that the program has \emph{partial correctness}. Namely: if it ends, it outputs correctly.
#
Now prove the termination. Namely, show that the Euclid’s gcd algorithm will always end. Hint, look at $a+b$ for any state $(a,b)$ that we are in, and show that it always decreases.
#
Amazing thing about Euclid’s algorithm is that it is indeed quite efficient. A better analysis shows that it will always terminate in $\log (m+n)$ steps. (Hint: show that after two steps, $m$ will be at most half of what it was before..)
Problem Set 7 Comments (Wed, 1 Nov 2017)
The Problem Set 7 solutions and comments are now posted in collab: PDF
Class 19: Reviewing Infinities (Tue, 31 Oct 2017)
Schedule
Problem Set 8 is now due on Friday, Nov 3.
Comparing sets Recap:
Definition. Sets $A$ and $B$ have the same cardinality, denoted by $|A|=|B|$ if there is a bijection between $A$ and $B$.
Definition. Cardinality of $A$ is at least as big as cardinality of $B$, denoted by $|A|\geq |B|$ if and only if either of the following is true (they are equivalent). \begin{enumerate} \item There is a surjective function from $A$ to $B$. \item There is a total injective function from $B$ to $A$. \end{enumerate}
Infinite Sets Recap
Definition. A set $C$ is infinite if and only if either of the following happens (they are all equivalnet). \begin{enumerate}
\item Dedekind-infinite: There is a bijection between $C$ and a strict subset $B$ of $C$.
\item There is \emph{no} bijection between $C$ and any $\mathbb{N}_k$ for any natural number $ k \in \mathbb{N}$.
\item There exists a surjective function from $C$ to $\mathbb{N}$.
\item There exists a total injective function from $\mathbb{N}$ to $C$. \end{enumerate}
Definition. A set $C$ is countable if and only if there exists a surjective function from $\mathbb{N}$ to $C$. (That is, $\le 1$ arrow out from $\mathbb{N}$, $\ge 1$ arrow in to $C$.)
Definition. A set $C$ is countably infinite if and only if there exists a bijection between $C$ and $\mathbb{N}$.
Cantor’s Theorem
For all sets, $S$, $| pow(S) | > | S |$.
What does this mean for $| \mathbb{N} |$?
#
Show there is a bijection between $[0, 1]$ and $pow(\mathbb{N})$.
#
What is the cardinality of all the real numbers? Show a bijection between $[0, 1]$ and all real numbers. Hint, first show a bijection between $(0, 1)$ and real numbers, and then a bijection between $[0, 1]$ and $(0, 1)$.
#
Problem Set 8 (Sat, 28 Oct 2017)
Problem Set 8 [PDF] is now posted and is due Friday, 3 Nov at 6:29:00pm. Please read the collaboration policy carefully.
Class 18: Spooky Infinities (Thu, 26 Oct 2017)
Schedule
Problem Set 7 is due Friday (27 Oct) at 6:29pm.
Exam 2 is two weeks from today (November 9, in class). We will post more information about Exam 2 soon.
Links
Logicomix: An epic search for truth, comic book by Apostolos Doxiadis and Christos H. Papadimitrou.
Last year, there was a Problem Set ω - you can see some examples of student’s work. (Note that having a PS ω does not imply any limit on the number of regular problem sets, since there are infinitely many natural numbers before ω!)
Countable and Uncountable Sets
Definition. A set $S$ is countably infinite if and only if there exists a bijection between $S$ and $\mathbb{N}$.
Definition. A set $S$ is uncountable, if there exists no bijection between $S$ and $\mathbb{N}$.
The power set of $A$ ($\textrm{pow}(A)$)is the set of all subsets of $A$: $$ B \in \textrm{pow}(A) \iff B \subseteq A. $$
For all finite sets $S$, $|pow(S)| = 2^{|S|}$.
# #
For all sets $S$, $|pow(S)| > |S|$.
#
Prove $pow(\mathbb{N})$ is uncountable.
#
$\text{bitstrings} = \forall n \in \mathbb{N} . {0, 1}^n$.
#
Ordinal and Cardinal Numbers
$\omega$ is the smallest infinite ordinal. The first ordinal after $0, 1, 2, \cdots$.
What is the difference between an ordinal and cardinal number?
##
What should $2\omega$ mean?
##
Is $\text{InfiniteBitStrings} = {0, 1}^\omega$ countable?
#
Prove the number of real numbers in the interval $[0, 1]$ is uncountable.