For the P-NP problem,
here is the Clay math entry. Here is a Turing
machine emulator.
This was a Javascript
implementation from 2000. Unlike the above implementation, it only
implements one machine.
Here are some
"Busy beavers", Turing machines which produce a long string of 1, before
halting. Here is the
trailer of the "imitation game" from which we have seen some scenes.
We have seen some old computers in class. Here are some links
May 20:
We talked about Diffie-Hellman encryption.
A related vulnerability
is called log jam". From that article
To exploit vulnerable connections, attackers must use the number field sieve algorithm to precompute data. Once they have completed that task, they can use it to perform man-in-the-middle attacks against vulnerable connections in real time. Using academic-level hardware, the researchers required just two weeks to generate data needed to attack the two most commonly called prime numbers 512-bit Diffie-Hellman uses to negotiate ephemeral keys. Those two data sets allow the attackers to compromise about 92 percent of sites supporting the export cipher. It wouldn't require much additional work to generate data needed to attack the remaining sites.
The work required to precompute data needed to attack 768- and 1024-bit primes is orders of magnitude harder, but the researchers said the load is nonetheless within the means of state-sponsored eavesdroppers. In a research paper titled Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice, the researchers speculate the technique may be the means the National Security Agency reportedly uses to routinely break millions of encrypted connections. Documents leaked by former NSA subcontractor Edward Snowden revealed the mass crypto attacks but didn't say how they're carried out. Besides attacking HTTPS-protected Web and e-mail sessions, the researchers said, the same technique may be used to break SSH and VPN connections, too.
Here is the movie
to the 4 polytopes and 5 polytopes.
Alicia Boole Stott
who established independently to
Ludwig Schlaefli
that there are exactly 6 regular polytopes in 4 dimensions. Alicia introduced the
term "polytop" and Schlaefli pioneered geometry in higher dimensions.
A correction: I mentioned in class that Schlaefli had been a high school teacher. It seems that he was a middle
school teacher first before becoming a Privatdozent in Bern. Here are pictures of Alicia and Ludwig.
Turning the sphere
inside out. This "Smale paradox" started with a theorem of Smale in 1957:
"Any two immersions of the sphere into R^{3} are homotopic.
In 1960, a first eversion was constructed. This was improved until
1984 when Bill Thurston got the version which is in the movie.
More about the history
and here
is the geometry center page.
Software for the sphere eversion is
here (the original link
on the geometry center page does not work anymore).
A screen saver.
Here are three scanned pages of the work of Schlaefli. It was one of the first
works of geometry in higher dimensions.
When looking at the "Dave has two kids, one is a boy was born at night. What is the probability
that the other kid is a boy" problem, for which the probability is a surprising 3/7, we first
tried to set up the probability space with 3*3 different elements. This happened, when we did not
split also the girl into "Girl born at night" and "Girl born at day". Its a typical fallacy where
the probability measure is chosen in a wrong way (see Bertrand). The right setup is to take 4*4
cases and to compute there the conditional probability, which is 3 out of 7 cases.
Its still surprising that
"Dave has two kids. One is a boy. What is the probability that the other is a boy?" gives 1/3
"Dave has two kids. One is a boy born at night. What is the probability that the other is a boy?" gives 3/7
In the first case we have the probability space X = { BB,GB,BG,GG }, where we look at the
event {BB} within {BB,BG,GB} which has probability 1/3.
In the second we have the probability space { BB,Bb,BG,Bg,bB,bb,bG,bg,GB,Gb,GG,Gg,gB,gb,gG,gg }
and look at the event {BB,Bb,bB} in {BB,Bb,BG,Bg,bB,GB,gB}
Set theory lecture
In this lecture, we will look at naive set theory, the question, "what is infinity",
paradoxa shaking the foundation of mathematics and the Goedel
incompleteness theorem.
Calculus lecture
The Ed Burber Video "calculus in 20 minutes" is here
In this lecture we look at some beautiful
results about prime numbers like that (n-1)!+1 is divisible by n if and only if
n is prime or that 2^{p}-2 is divisible by p if p is prime. For example:
4!+1 = 25 is divisible by 5 and 2^{5}-2 = 30 is divisible by 5.
The topic of number theory is also a place with many open problems. Like the
question whether every even number larger than 2 is a sum of two primes.
Geometry lecture
We mentioned also about Euclid.
Here is a wonderful
edition of the Elements of Euclid.
Pythagoras lives strong also in the Youtube time.
Here is an example.
We mentioned that it is unlikely that Babylonians already knew Pythagoras even so
YBC 7289
contained a glimpse of the theorem as it does it with an example. One has however not to confuse examples
with the general theorem. The above mentioned Youtube movie for example illustrates the 3-4-5 triangle
which is a specific example and is far away from the real theorem which tells that it is true for all triangles.
Here is a school scene
where Pythagoras appears.
Here is a TV show (Samos Magazine) about Pythagoras, the person.
Here is a TV show (Boyah) about Thales, the person.
Arithmetic lecture
Discussion points which came up at the makeup meeting on Presidents day:
The question whether the Babylonians had a 0 must be
considered must be difficult. They certainly had a place value system
but did not
A worksheet based on an exercise
in Berlinghoff and Gouvea. We worked on that. A strange thing: why did the
Mayans write upwards?
We made a little table about the system where one can argue whether the romans
have a 5 or 10 based system, as they had letters for 5, 50 etc.
On the 18th, a separate discussion asked about the Quipu:
Origin
Egyptians
Babylonians
Mayan
Roman
Hindu-Arabic
Americas
System
Papyrus
Clay tablets
Maya script
Roman numerals
Modern numerals
Quipu knots
Place value
No
Yes
Yes
No
Yes
Yes
Zero
No
Only space
Yes
No
Yes
Only space
Base
10
60
20
5(10)
10
10
Since also the arithmetic lecture fell into the snow, I produced a lecture for online viewing.
Here are some remarks
Notes (PDF) to the lecture. Only the first two
sections are relevant. The notes and the Youtube recording contain more material. The part on powers requires some exposure
to complex numbers, in particular the Euler formula exp(i x) = cos(x) + i sin(x). The last section on
pi needs the fundamental theorem of calculus telling that the integral of the derivative F' from a to b is F(b)-F(a).
The picture of Ivan Niven on the book shelf is
from that Wikipedia page. His proof of the irrationality of pi is at the end of the youtube lecture.
Niven lived from 1915-1999. He was president of the MAA from 1983-1984 and best known for his
work on the Waring problems. He authored one book on Diophantine
approximations, one on real numbers and one with Zuckerman and Montgomery on number theory.
Here is the painting
by Byodor Bronnikov which I flashed during the lecture
showing the Pythagoreans, a spiritual and mystical group. The fact that a simple fact like the incommensurability of the diagonal of
the square produced a crysis is mirrored in other places of history: the shift from circles to ellipses in Kepler's time,
the shift from smooth objects to fractals, abstract topological spaces,
the existence of non-Euclidean geometry (Gauss,Bolay,Lobetchevsky),
the realization that different cardinalities exist (Cantor), Goedels realization that any strong enough
axiomatic system is not complete or Grothendieck's extension of algebraic geometry.
In each case (and there are more) one can look at the previous point of view as narrow
minded. There is no doubt that future generations will look at some of our mathematics as narrow minded.
Introduction lecture
A discussion point which came up at the makeup meeting on Presidents day:
We looked at the question why it is not possible that K_{5} can not be embedded into the two dimensional plane.
While exploring this, an idea was why not reuse a given edge to connect the new edge outside the triangle with the one inside.
As we have excluded ``crossings", being part of an other edge has not been excluded strictly speaking. It illustrates the
difficulties to make precise definitions. The problem of embedding K_{5} into the plane is closely related to
the problem of the 5 princes, when translated into maps.
If you want to challenge yourself a bit, try to color the
Icosahedron graph
with as few colors as possible.
An other question asked about why the complete graph K_{5} (the magic pentagon) can not be drawn in the
plane without intersections. In other words. Why is the graph K_{5} not planar.
I would have liked to discuss this in class as it is not obvious at all.
It is part of what one calls Kuratowski theorem.
Here is some insight: if you draw a triangle the it divides the inside and outside. You can not cross
from a vertex inside to a vertex outside without crossing the triangle. Mathematicians call this the Jordan curve
theorem. It looks simple but is surprisingly hard to prove. Anyway, if one assumes this result, then you can convince
yourself that it is not possible to add an other 5th vertex to a K_{4} graph (tetrahedron) without
crossing a triangle. For example, you can not place the 5th vertex outside the triangle because there would be no
connection to the inside vertex. In the same way, it is impossible to place the 5th vertex in one of the three inside
triangles of K_{4} as one would have to connect to the forth vertex outside.
There was a question, why in the Blackboard lecture,
I mentioned that it is ``magic". Indeed, there is a lot of
history about it.
It appeared already in sumerian scripts and until today frequently appears in literature like the "Da Vinci Code".
It had also been a sign of recognition of Pythagoreanism.
Why is the complete graph K_{5} 4 dimensional? Here is some justification: one can realize the triangle K_{3}
with equal side length in the plane, the tetrahedron K_{4} with equal side length
in space. We need to go into 4 dimensional space to realize K_{5} with equal side length.
This is how Erdoes, Harary and Tutte
defined dimension for graphs. There is a way to define dimension which does not refer to Euclidean space: the dimension
of a graph can be defined recursively as "1 + the average dimension of the unit spheres in the graph". The unit sphere of a vertex
consists of the vertices attached to it. How do we define the dimension of this unit sphere? In the same way.
Look at the unit spheres of the vertices in that graph and so on. We just have to start with the assumption that any
graph without edges has dimension 0. The dimension of K_{n} is now by definition 1 plus the dimension of
the unit sphere K_{n-1}. We see also here that the dimension of K_{n} is n-1.
In the presentation, I had planned to elaborate a bit more on Taxonomies.
They have always been important for teachers, as they provide a ``guide" on what to look for. And everybody naturally makes
up their own taxonomies. Teaching is very personal and practical. The Bloom taxonomy is such a fixture in education that it
borders the brink of obsession. It had been developed by Benjamin Bloom.
Bloom was a theoretical psychologist. His taxonomy has been modified and
is now called revised Taxonomy.
It can boil down to "Knowledge, Understanding, Application and Modification", or shortly
"What, Why, How" and "Why not?" Moore has put "Evaluate" on top of this but
it can make more sense to put "evaluation" out of this and apply evaluation to all the four parts.
(For example: for arithmetic, a student first has to know the symbols for the numbers, then see whether two numbers
can be multiplied. The third part is to understand the structure like why 5 * 7 = 7 * 5 or why there are numbers
which can not be written as the product of two numbers larger than 1. Eventually, the fourth "why not" part could explore whether
one can build structures, where x * y = y * x is no more true. The answer is yes and that this is how nature indeed operates
on a fundamental level (quantum mechanics)). Now, each part can be evaluated: one can ask a kid first whether it can read the numbers
("What is this"), then ask to add numbers ("How is this done"), then ask more conceptual parts like whether it understands that
(3+4)+5 is the same than 3+(4+5) ("Why is that true?") and finally test creativity by asking whether one could look at
other numbers too ("Why not?"). My critics with putting the evaluation into the mix is that most of the teaching we do
deals with the "What" and "How" part. Already the "Why" is the holy grail of education and only folks who have never taught can
believe that this is easy. The creative part is almost unreachable. There are teaching methods which aim for it, like the Montessori
system but often creativity in reality boils down to have students just copy already known things.
Its hard to teach creativity. Some try to build tips.
If you look at this (which appeared also as a slide, you
realize how hard it is for example to be creative as a designer. Most just copy each other.
The liberal arts and sciences provide a metaphor for an other taxonomy: as pointed out in the slide,
one can see Grammar as a metaphor for "What", Rhetorik as a "How", and Logic as a "Why". The creative part is not in the Trivium.
But the quadrivium includes it and even more. Arithmetic can be seen as a metaphor for "Doing things", Geometry to "See things",
Music to "Feel things" and Astronomy as "Seek new things". Any way, this bending of the 7 liberal arts and sciences to a taxonomy
shows how arbitrary taxonomies can be. So, here is an advise: make your own taxonomy and test it in the field.
Unfortunately, our first lecture fell into the snow. Here is a short introduction to the worksheet and part of the slides.
On the blog
Maxwell Demon
there is a nice slide of what Mathematicians do: