Math E-320: Fall 2015
Teaching Math with a Historical Perspective
Mathematics E-320:
Instructor: Oliver Knill
Office: SciCtr 432

Lecture 13: Computing

 December 21: Some indication about weaknesses of Quantum cryptography . Science Advance. 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.

Lecture 11: Cryptology

• We also mentioned the Scytale. Xenia sent an activity [PDF] for 4th graders based on the Scytale idea. And a decoding riddle.
• 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, kn for combinations with possible repetition and and n!/k! for choosing k objects where the order matters. All except kn 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 yx-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
(1+x)2 = B(2,0) + B(2,1) x + B(2,2) x2 = 1+2x+x2,

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.
• Thanks to Paul for the following On Russell and Whitehead, and the Axiom of Choice, Axiom of Choice
• Some big questions like
• What is infinity?
• Can we know everything?
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.

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)=xn, f'(x)=n xn-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) = x5 - 3 x? It is f'(x) = 5 x4 - 3. What is the anti-derivative of x7. It is is x8/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-x3/3!+x5/5!... gives sin'(x)=1-x2/2!+x4/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?

F[x_]:=If[EvenQ[x],3x/2,If[Mod[x,4]==1,(3x+1)/4,(3x-1)/4]];
Last[NestList[F,8,100000]]

After 100000 iterations, we already have a number with 2654 digits:
8936556696196263925733087515155198149044140343917469953886799487672560608198946814970522777601164155
1243483141850038942366868825945955838637737474852048161421288245828546800086544620658226775717046993891
5687714910340953612313400194682266417678119895745944847192860378467074159446069227195207131142828937408
9408556731922714665839752955659084736843321790682567035583753326282475256803587252596318827754995412868
9096760537722799778448713507654113931353871048818233022552118964424463517311516312791250005076706925575
6315036328891841354655566078171776413363746188346701662256265495693659556938297970212667594679050552702
9724976430393163769912953177571307666632574090323000703170873192644897740409858705904664779277639802481
2929912290914181733770767056597515747573835078050347543212301372150767636476121392779708941369360333655
5439475250300286863300680658270269408368870687664776038337282462608991420715251493132865400145337656376
0041803518550112310968683059051532328403416870381070815068326142513608877276770468895288701945590273701
2670678638321301542300774509671138354512668958395689250240938939419766581705002467372564347124320165045
4050008357713529480487689630364868272102545097284030864619477628009188551258366190659587728292939242843
9909579137074491406680490409100276791540336811241668164077884586261066893099722864420097654525705639655
6387059025659826068324884888060082988412492316274384894325067456974038832325122508263477765277833882296
0899024569035638925751694384118122156811203581006916318827309255839083574063511182541516875230987923649
7232854633983296728052581934982122738758295279706253387952198229432296718263305111260687266494418438018
1518123459906156370113960733452203918376130011608469968361909552747508898562768576826685061645304615828
1381126154522183436742220839834979068708480596101200768586930853033294734944807681721055010493648141900
3848429280991540863378722709135651986203708435585225561504042515025269445410655831421790044660899619504
0163746477714981083664748354504755087925054985285227081613494731365255161493434113205271701714321351103
2525690212743935671855950556520238516260633751964536101230534703793698173710189210021132795542891909459
1018235176581581671294170678583503184162442949744459675716147979019933824327398647720884053049533833292
8584565237592220094233077804426451566199119844763033330203357199558175275459819819047454770768857381773
2604010177994966647378358432440374716581780492186103359522864678686337712741538066587563762149742003104
0723471020641000059455637147149525424812505627880621817908556544992726515642499350472295026582519072013
2642102918960097554741903818091266942318738491791931671179093737139057396900796605

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: