December 10: everybody celebrates Ada Lovelac's 200th birthday.
Example (german).
Ada was born on December 10, 1815.
In this last lecture, we will look at the history of computing. After saying a bit more about the
project, we will look at the beginnings of computing (abacus, Antikythera, early computing machines
until the modern computers).
A NYT article
on the Antikythera.
We will also take the opportunity to point out changes in how we can
do mathematics like for example, how to use computers to experiment or artificial intelligence to prove
things. An other topic we will glance over are the limits of computing. There are problems called NP
hard problems which appear to be difficult. One of the most famous open problems is to understand this
and see whether there are indeed problems which can not be solved in polynomial time. There are
other limitations like Turings Halte problem. There are fundamental limitations what a computing device
can do. Turing came up with the concept of Turing machines. Its not yet clear whether how much
quantum computers will make an impact in
the future. While quantum computers can not compute more than a Turing machine,
there are indications that quantum computers could speed up computations significantly. So far this has
not been realized and there could be fundamental limitations.
A recent article on
Quantum computing.
and here an article in German mentioning the article from
September 7 about D-Wave.
An mathematical difficulty in computing related to quantum mechanics has
appeared here on December 10, 2015.
Lecture 12: Dynamics
What happens if one applies a map again and again? In general, it produces
an unpredictable sequence of numbers. One calls this chaos. The theory started
to grow at the beginning of the 20'th century and bloomed in the last half.
Even so the story is pretty well understood, major problems remain to be solved.
In particular there is a huge discrepancy of what one measures and what one can
prove, even for very simple systems. We will look at the history of this fascinating
topic which ranges from celestial mechanics to keep pushing the same button on a
calculator.
An other story
where encryption has been disabled by support software of a hardware seller.
A story on poor encryption
with youtube.
The discovery has been made by Samy Kamkar, who discovered a lot of other vulnerabilities
like combination locks.
The work of Samy illustrates, how disasterous poor encryption is.
The RSA encryption we have looked is completely transparent. We know its
mathematical difficulty which makes it hard.
Cryptology the science of breaking
codes. The journey starts in 2000 BC and goes up to
today where encryption is a hot topic. We will look
first at basic substitution cyphers like invented by
Caesar, then at more sophisticated versions up to the
Enigma, which was used in WW2.
Then we switch to public key encryption. It is a bit
ambitious but we will see how key exchange and
sending encrypted data works using primes.
This is RSA and Diffie Helleman.
Finally, we will also have a glimpse at quantum cryptology.
Lecture 10: Analysis
Analysis is a huge field: complex analysis, functional analysis, operator theory,
inverse problems, harmonic analysis, real analysis, calculus of variations,
spectral analysis are all part of it. Since it is so large, it is hopeless to get an overview: we will focus
almost entirely on one topic, the geometry of fractals. Our goal is to understand one single formula,
the formula for computing dimension. So, there will be lots of pictures and of course movies and many examples.
Lecture 9: Topology
In this lecture we look at topology. We first look at topological equivalence
which mathematicians call with a fancy name: homeomorphic.
It means for example that an apple is topologically
equivalent to a pear or that a doughnut is equivalent
to a cup. We will practice this on various objects.
Much of the time, we will spend with polyhedra and
see them both historically as well as in pop culture
or philosophy. We will also give the detailed proof that
there are exactly 5 platonic solids which is a theorem
of Theaetetus. We also will
informally look at platonic solids in higher dimensions
which have been explored first by less main stream mathematicians
like Ludwig Schlaefli and Alicia Boole Stott.
The subject of topology is also linked to graph
theory, which started with the Koenigsberg bridge problem.
Both for analyzing polyhedra and graphs, there is the
important notion of Euler characteristic and Euler's gem.
A good source about the history is the book of Max Brückner
from 1999 called "Vielecke und Vielflache". Here are a couple of pages
which describe the history (in German):
Lecture 8: Probability theory lecture
[ Update of December 1, 2015: Business insider (German) treats 4 problems (2 of which we covered in the lecture).
The first is the Monty Hall problem, the second is the boy-girl problem). There are two other famous
problems. You have a leaky sink. Somebody helps you to fix it. What is more probable: the person is
a Bookkeeper or a Bookkeeper and Plumber? The four problem is the friendship paradox:
It is more probable that one of your friends has more friends than you.
]
The fact that probability theory can be a bit of a tougher topic to grasp is illustrated
by the fact that it was developed relatively late: Mathematicians started
to think about it first in the context of gambling. The clear mathematical
foundations were only led about 60 years ago with Kolmogorov.
We have talked about the four basic formulas in combinatorics:
n! for permutations, n!/(k! (n-k)!) for choosing k objects,
k^{n} for combinations with possible repetition and
and n!/k! for choosing k objects where the order matters.
All except k^{n} need the factorial.
A nice question by Raquel is how come 0! is defined to be 1.
Here are some answers: there are various reasons: a) combinatorially, it makes sense also to talk about
the number of possibilities to do something with
no objects. Like in how many ways can you permute
nothing. There is just one way and the nothing stays
the nothing. b) One would like to have the recursion n! = n (n-1)! to hold. That
forces 0! to be 1. c) One can extend the factorial function to
non-integers. It is called the Gamma function. The function Gamma(x)
is defined as the integral of y^{x-1} e^{-y}, where
y goes from 0 to infinity. One can easily see that Gamma(0)=1
and Gamma(n)= n Gamma(n-1) using integration by parts. But the
integral in the Gamma function is defined for all x bigger or equal to 0.
For example, Gamma(5) = 4! Now, this function is defined
not combinatorially but as an integral and that integral
evaluates for t=0 to the integral of e^{-x} from 0 to infinity
which is 1. d) We want the Binomial coefficients
B(n,k) = n!/(k! (n-k)!) to work in the case k=0 or k=n. This is
useful also in algebra like for the FOIL formula
which shows that it is convenient to have B(2,0) and B(2,2) to be 1.
Why is it useful to extend the factorials to other numbers? One reason
is that one can now use calculus to conquer combinatorial problems.
The Gamma function by the way also appears naturally in other places of
probability theory and statistics.
A slate article on coin flipping. The short version is
on this handout. It is like the "Dave has two kids" problem. The probability depends on how you ask. If you throw
two dice and know that one is head, then the probability that the second is head is 1/3 only.
While if you throw a dice and know that the first one is head then the probability that
the second one is head is 1/2. In the first case the laboratory space is X={HH,HT,TH} where the event A={HH}
has probability |A|/|X|=1/3, in the second case, the laboratory space is {H,T}, where the event A={H}
has probability 1/2. Similarly than Monty Hall, these stories are very simple once one has put the right
model. Confusion comes into it, because one can also interpret the stories differently. The Bertrand
Paradox, which we have seen illustrates how important it is to have a right model. If one does not agree
on the model, then different answers can be right at the same time.
The coin problem, the Dave problem or the Monty Hall problem are all crystal clear once the model has
been nailed down. For Monty Hall, there were two scenarios: in the nonswich case, the laboratory was
X={Goat1,Goat2,Car} and the probability of the winning event {Car} is 1/3.
In the switch case, with the same laboratory, the winning event is {Goat1, Goat2} which has
probability 2/3.
While the Monty-Hall story is fascinating it is prototype story on how important mathematical models are.
Most disagreements we have are due to the presence of different models or even
different definitions. In colloquial language this happens more frequently than in mathematics. The
probability stories which appear in this lecture shows that it even appears in mathematics. The resolution is
very easy, once the model is chosen. If you want to learn more about conditional probability,
Here is a handout
from 2011. The Kolmogorov axioms are covered
in this handout.
The book of David J. Hand: "The Improbability Principle: Why Coincidences,
Miracles, and Rare Events Happen Every Day" explains well why some miracles happen.
There was a comment addressing this
on a youtube video of mine. I hope its ok to extract 2 pages from that excellent book here:
Lecture 7: Set theory lecture
.
In the first part of the lecture we talked about George Boole.
Was good timing because November 2 marks the 200th birthday of
George Boole:
An article.
Part of a movie on Boole.
can actually answered pretty well in mathematics. The riddle
of taming infinity has been done by Cantor. He showed that there
are different types of infinities. We will look at this in detail today.
The question whether we can formulate a theory which covers all knowledge
has been tackled by Goedel. The answer is "no". Whatever system we build
there are always statements which are true but not covered by the system.
While shocking at first, it makes mathematics more interesting.
We also look at some paradoxa, like the liar paradox or the Barber paradox.
and others.
Illustrating that both questions at the abyss of knowledge
demanded a lot of effort and energy is illustrated by the fact that
both mathematicians had to fight mental challenges. For the pioneers
it might have led to depression. But thanks to them, we can now enjoy
the topic and have clarity.
We will see that some of the topics also had repercussions in education.
Lecture 6: Calculus lecture
Calculus in 20 minutes:
The formula f(x)=x^{n}, f'(x)=n x^{n-1} and
its inverse for integration form an easy algebraic entry point
to derivatives and integrals.
The formal approach is the simplest to understand. What is the derivative
of f(x) = x^{5} - 3 x? It is f'(x) = 5 x^{4} - 3.
What is the anti-derivative of x^{7}. It is is x^{8}/8.
The interpretation as slope or area give meaning to it and makes it
applicable but it also need some intuition.
Archimedes already gave meaning to area and volume by exhaustion getting
close of what we describe today using limits. But the precise notion
was clarified only much later. Formally taking derivatives
of algebraic expressions using determined rules is so easy that a
machine can do it blindly. Taylor series allows to treat more functions
like that. Like sin(x)=x-x^{3}/3!+x^{5}/5!... gives
sin'(x)=1-x^{2}/2!+x^{4}/4! ...
The technique is also applied in formal setups like number theory or
combinatorics (derivations and formal power series).
Grasping the geometric aspects of calculus is more subtle to grasp, like
why the limit sin(h)/h is 1 ("the fundamental theorem of trigonometry").
The formal series approach immediately gives that.
Understanding it geometrically needs more understanding.
Calculus is a fascinating story which also can
scare students. The origins of calculus are interesting: How did the
concept of function or the concept of limit appear? How can one
use it to compute area, volume. We will spend most of the time with
the historical parts and see how the ideas were built and applied even
in much more basic situations like understanding sequences of numbers
like 1,4,9,16,25,36,.... One of the core goals of calculus is to compute the
future of a process. In the example above, we can predict the next one
by either recognizing the numbers as squares but also do it more systematically
by computing differences (taking derivatives) and then summing up (integrating).
The process of differentiation and integration is the core of calculus.
Lecture 5: Algebra lecture
The topic of symmetry was important in algebra, both when
"solving the cubic" as well as when "solving the rubik". Paul
sent in a link to a nice video explaining how symmetry and
puzzle type considerations can be used to build joints
Here is a
graphics of the Kawai Tsugite joint.
First thought: "would be nice to 3D print!" As usual, this
has already been done.
The picture to the left has been done by importing that into Mathematica.
When we derived the solution formula for the cubic equation, we tripped over
a substitution and entered x=u-p/3u which the computer interpreted as x=u-(p/3)u
rather than x=u-p/(3u). One would think, that according to PEMDAS
(Paranthesis, exponentials, multiplication, division, addition and subtraction),
the multiplication is done before the division. This is not the case. Almost all
programming languages, including Mathematica do first the division. I wrote about this
here. It is a
fascinating story. The bottom line is that there is a BEDMAS and PEMDAS rule and
that there is no common ground. There is only one solution to the problem:
write the brackets!
Dylan writes about this:
The M and D are meant to happen at the same
time. Multiplication does not have priority over division. For this reason,
and for potentially confusing instances involving parenthesis such as
6^2/4(x-5), some teachers are trying to replace PEMDAS with GEMA (grouping,
exponents, multiplication/division, addition/subtraction).
This is a nice simplification. And it avoids to take sides (which is futile).
Lecture 4: Number Theory
Here is a light-hearted exposition about the Twin prime conjecture:
and here is a numberphile comment about the relatively new
bounded gap theorem:
The movie also mentions the largest known twin prime.
Lecture 3: Geometry
Thanks to Lauren for telling about the
Euclidthegame.
In this geometry lecture I tried also to show that there is a lot of cross
fertilization from geometry to algebra as one can use algebra to perform
geometric proofs like the four miracle points in a triangle: the
circumcenter, the incenter, the centroid and orthocenter.
The orthocenter, centroid and circumcenter always are located on a line,
the Euler line.
We have also seen that the altitude and midpoints on a side
as well as the midpoints between the vertices and orthocenter are located
on a circle, the 9 point circle
which has a center also lying on the Euler line.
There are relations between geometry and number systems.
When looking at barycentric refinements for example one gets in
one dimensions to to a number system called dyadic numbers which
are a "quantized" analogue of the real numbers. You have played with
Barycentric subdivisions in the plane. Also in that case, there is
a ``number system" hidden. Its just not yet identified yet. I just myself
worked a bit more on that.
Lecture 2: Arithmetic
Raquel asked what "quaternions" are. Here is an attempt to explain
it briefly:
you have seen how to multiply numbers like 2*3 = 6.
How do you multiply pairs of numbers? The answer is
given by complex numbers (3+i) (2+3i) = 3*2 + 3*3i + i*2 + 3 (i*i)
now i*i=-1 so that the answer is 3+11i. The complex numbers give the
answer to the problem of "multiplying pairs of numbers".
Hamilton was wondering for many years how one can generalize this
to "multiply triplets". How would one set this up to have associativity
as in the case of real or complex numbers?
According to legend, every morning, he came down to Breakfast where
his son would ask: "Dad, can you multiply triplets?" And Hamilton
would answer. "No son, I can't do that yet".
One day, while walking over a bridge, he figured it out. He was so happy
that he inscribed it into a stone of the
bridge he was
walking over. The answer is to write the triplet (3,4,5) as 3i + 4j + 5 k
and then use the rules i*i=j*j=k*k=ijk=-1 to compute the product.
Quaternions are useful for computations as they implement rotations
in space nicely. What Hamilton was, is remarkable as the product both
introduces the dot and cross product in multivariable calculus.
We mentioned the book "Surreal numbers" by Donald Knuth. I have red
the German version:
Here [PDF] are the first pages of the
original book "Surreal numbers" from 1974.
In the second lecture, we had a look at the history and
structure of number systems. We will start with number systems developed
20'000 years ago (the positive integers) and look how various cultures
came up with ways to write them down. We will learn how to write like
the Babylonians, Egyptions, Romans or Mayans. We especially looked at a
revolution, when it was realized that real numbers exist which are not
fractions as well touch upon modern number systems like the complex numbers,
the hyper real numbers of Conway (the same Conway who invented the
amusical sequence or the game of Life). We will look at irrationality proofs
(also a newer, gorgeous one, also recently found by Conway ...).
Lecture 1: Mathematics
Non Youtube version
Here are Barycentric drawings by Raquel, Kyle and Lauren.
[PDF]
of a worksheet from Xenia suitable for holidays.
I myself still still work on smoothing out and understanding better
a new central limit theorem related to
Barycentric refinement see a draft
and miniblog about that.
And also used the computer to make pictures
like this.
It looks like a children's game or doodle but the process of Barycentric subdivision is
of fundamental importance in topology.
Jean
Dieudonne wrote once:
"There the three essential innovations that launched
combinatorial topology: simplicial subdivisions by the barycentric method, the use
of dual triangulation and, finally, the use of incidence matrices and of their
reduction."
Indeed, one can see the tool as getting from the discrete to the continuum, similarly
as using larger and larger fractions to approximate a real number.
Similarly as we can never understand
fully the scope of real numbers, or even simple special cases like Pi, we can hardly
ever understand the structure of space or even know how space is like physically.
The holographic barycentric picture (seeing space as a limit of barycentric refinements
similarly as real numbers are seen as as limits of rational numbers) could be even
fundamental as there is nice mathematics associated to it like unexpected
richness of the spectral structure, when seeing space as a limit of barycentric
refinements.
In the first lecture, we have looked at the general structure
of mathematics. One of the definitions of mathematics is that
it is the language and building block of the universe.
An other definition is that it is the science of structure.
To illustrate the range and scope of mathematics, we looked
at a particular sequence of numbers, the "amusical permutation"
of John Conway, which he suspects to be unsettlable.
I wanted to indicate that mathematics reaches even further, and allows us
to look at the boundary of what we can know or what we can do. The amusical
permutation of Conway is defined by the rule that n gets mapped into 3n/2 if n is even
and into (3n+1)/4 if n has remainder 1 when dividing by 4 and
(3n-1)/4 if n has remainder 3 after division by 4. There are some loops like
1 -> 1
2 -> 3 -> 2
5 -> 4 -> 6 -> 9 -> 7 -> 5
But if we start with 8, we don't know what happens. It is known that if the
sequence goes to infinity, but it is also known that if this is true then
no mathematical proof of it! We "know" that
it goes to infinity as the sequence is expected to hit even and odd numbers
the same number of times and that in that case, we multiply with 2 in average
in each step and a loop only can come back to 8 because the map is invertible.
This is a truly remarkable enigma. How can we know something which we also know
not to be able to prove? One point of view is to accept the fact that the
statement, if true can not be proved so that the only chance to get assurance
would be to have the statement to be false. Maybe we can find a pattern?
How can this ever go back to 8? It would need an astronomical number of "lucky steps", but as longer
we run the sequence as more luck we would need. With 2654 digits, the chance is 2^{-8816}
If you think that it is strange that we are unable to prove this sequence escapes to infinity
then you are not alone. Conway mentions the sequence in his article
J. Conway: On Unsettleable Arithmetical Problems,
"The American Mathematical Monthly,120(3), December 2012. I believe that problems like this at
the boundary of knowledge are similar to problems about the questions of the beginning of the universe.
Maybe we are in a stage like Zeno, when trying to grapple the notion of limit.
It needed more than 1000 years to cope with it. Maybe we will need 1000 years to understand the ramifications of
arithmetic problems which are unprovable and so to understand the boundary of mathematics.
Somehow, looking at a sequence like the amuscial sequence is like looking at light from the very early universe.
We know that we are close to the limits of what we can know. Here is a section of the paper of Conway: