Math Foundations from Scratch


Intro

Here we relearn algebra, geometry, and combinatorics as efficiently as possible by solving olympiad style problems, or as the Russian author calls them 'research level highschool mathematics'.

Do 1% effort for 100 days - Prof Ryan O'Donnell

Curriculum

We will do all at the same time:

The author has a free version of algebra and geometry, and the original Russian versions on his school page (including discrete math and other books) or Library genesis exists to get the books if you can't buy them.

Why Geometry

geometry.jpg
Figure 1: Geometry of mathematical finance uni.lu

Geometry was used for thousands of years to teach and demonstrate mathematical reasoning. Think of it as a tool for doing math like a framework you can manipulate visually.

Geometry & Isaac Newton

For geometry themed entertainment try reading Isaac Newton on Mathematical Certainty and Method by Niccolo Guicciardini as you go through the geometry problems here, as Newton claimed geometric synthesis helped him make mathematical discoveries when writing Principia by performing geometric synthesis on the cause to prove the effects he observed through analysis.

Isaac Newton entered Trinity College in 1661 as a sub-sizar meaning subsidised tuition in exchange for being an unpaid servant on campus. Cambridge then was just a diploma mill, there were seldom any lectures and fellows (graduate students) acted as P/T tutors to supplement their income. Undergrad degrees consisted of one of these tutors giving you a list of books to read. According to his Trinity College notebook which Cambridge still has, this was a large reading list of Greek and Roman classics in Latin: Aristotle's Organon and Metaphysics, Porphyry's Isagoge, Plato and manuscripts of commentary on Aristotle usually written by other fellows to sell to undergrads. This was because of the recovery of Aristotle in the middle ages which shaped logic courses for the next few centuries. Newton didn't read much of Aristotle or any of the books assigned to him, but he later claimed he read enough to have learned how to properly categorize a problem, how to think logically, and later when he wrote the Principia how to use a cause to prove the effect. His algebra lectures that later became the book Arithmetica Universalis described different 'species' ie: Aristotelian categories of math objects that can be combined together, essentially he was describing types.

According to Newton's notebooks and the writings of his close friend DeMoivre, here is how Newton learned mathematics. Wandering the town fair in 1663 he comes across a book on astrology, and out of curiosity buys a copy as Newton was always into alchemy and other occult topics. It features trigonometry he doesn't understand so he goes to the mathematics department of Cambridge to find books on trig only to discover everyone there is deeply immersed in the work of Descartes. They give him Euclid and Oughtred's Clavis. He retries Euclid's Elements after having given up reading it before, and sees the proof of the Pythagorean theorem which makes him want to read the rest of the text. Newton's college notebooks show he was influenced by books II (geometrical algebra), V (proportions), VII (number theory) and X (irrationals) and that Euclid taught him how to write a proof while Aristotle's system of logic he studied gave him the rigorous thought to be able to follow the proofs.

Since his Cambridge degree is essentially a joke, with the school so lax nobody cares what you're doing, he abandons the official curriculum for the rest of his undergrad to hang around the math department. He pursues Kepler and Oughtred's book, writing he understands it except for the quadratic and cubic equations however his takeaway in his notes is that algebra can used for exploration, which he starts doing writing out himself hundreds of examples. He gets a B.A. in 1665 despite never finishing any of the official curriculum and is offered to be elected as a minor fellow pursing a masters but the school is closed because of the plague in the summer of 1665.

geometrie.jpg
Figure 2: Cartesian Geometry by Van Schooten rarebooks

He goes home to his family farm and takes with him a 1659 two volume Latin translation of Descartes La Geometrie by van Schooten with appendices and commentary by other Cartesian research mathematicians. Newton later writes in his school notebook how a proof by Hudde to estimate the slope with a tangent in the appendix taught him how to transform one type of problem into another to study it in a different way. This book was considered a very hard text and the state of the art of 17th century analysis which uses almost the same notation we use today. He read 10 pages or so, couldn't understand the text, and reread from the beginning. Went a little further then stopped again going back to the beginning. He repeats this algorithm for all summer and autumn until he finally finishes the whole text. He misunderstands a technique of Descartes to his own benefit where he thinks Descartes is hinting the reader can figure out any properties of a curve and while trying to do so as an exercise develops his own sophisticated analysis well beyond the book or any other book of that time. During this period is when he started working 18 hours a day, 7 days a week. He didn't stop this work ethic until he died, even after becoming wealthy and living in London.

In the winter of 1665 he reads Arithmetica Infinitorum by Wallis which is the arithmetic of infintesimals and Viete's Opera Mathematica another very large book. In less than a full year Newton managed to bring himself completely up to date with the entire achievement of mid 17th century mathematics by himself. At this point he discovers the generalized binomial theorem and infinite series analysis which he invented to find short cuts to calculations. He returns briefly in 1666 to Cambridge before it's shut down by the plague again, his notes revealing he finished his differential and integral calculus during these few months back at school.

Describing his activities during the second plague year: "I am ashamed to tell to how many places I carried these computations, having no other business at the time, for then I took really too much delight in these inventions". There is notes he kept of calculating a logarithm to it's 52nd decimal point. He returns to Cambridge in 1667 and sometime during this period he becomes obsessed with uncovering the ancient analysis used in classical geometry. Pappus' book 7 contains a commentary about a lost group of tools and propositions that Euclid, Apollonius, Eratosthenes and other geometers of the day used which Pappus referred to as the 'treasury of analysis'. These lost Porisms (corollaries) are theorized by Newton to be projective geometry.

Newton in his Lucasian chair lectures said that the ancients would never bother to introduce the algebra of curves with geometry because you lose the simplicity of working within geoemtry, it's whole point was to escape the tediousness of calculations by simply drawing lines and circles. He also claims books like Pappus's Collectio deliberately hid the analysis, as it was considered an inelegant tool and that ancient synthesis where they deduced a consequence from a given premise (a corollary) using visual means was a superior method as the analysis could not be reversed in steps like geometric synthesis could. He went further and claimed if you wanted to discover seemingly unrelated corollaries you had to use synthesis, describing the analysis of his day as a 'tedious pile of probabilities used by bunglers'.

In Arithmetica Universalis which is an unauthorized book released by his successor at Cambridge who discovered Newton's Lucasian lectures in the library and published them as is, Newton writes how Descartes' attempts to include into standard plane geometry various curves like parabolas more than just a waste of time, they are 'ruining the simplicty of geometry'. In figure 108 he shows how he would solve this problem, by reinterpreting an ellipse, arguing the Cartesian methods fail to understand the point of doing everything with just a ruler and compass.

He later wrote in a manuscript on geometry that mechanics of motion was what generated all geometry, and that the ancients had understood this as well conceiving geometrical objects as generated by moving along a straight edge, circles via the movement of a compass, or translation like in Proposition 4 of Book 1 of Euclid's Elements where one triangle form is moved to compare to another. He then demonstrated that mechanical rotation of rulers were in fact transformations of the plane something that wasn't formally developed by other mathematicians for another 200 years.

Newton invented limits when writing the Principia during the geometric synthesis stage of his infintesimal analysis. He decided limits demonstrated as geometric vanishing augments to be 'more in harmony with the geometry of the ancients in that there should be no need to introduce infinitely small figures into geometry'. Since infintesimal analysis was merely a heuristic tool to him, he downgraded infinitesimals (which had no established theory or proofs anyway) to prefer his new limit proof method he derived from geometry synthesis, and is very similar to what everyone today is using in modern calculus courses.

"Comparing today the texts of Newton with the comments of his successors, it is striking how Newton’s original presentation is more modern, more understandable and richer in ideas than the translation due to commentators of his geometrical ideas into the formal language of the calculus of Leibnitz" -Vladimir Arnold 1990

Logic

After you start solving some problems, you will want to read more about logic since really math is just a long chain of deductions.

Mathematical reasoning

proofs.png
Figure 3: What is a proof from 15-251

The model for basically all mathematical reasoning:

  • AND \(\land\) (conjunction)
  • OR \(\lor\) (disjunction)
  • NOT \(\neg\)
  • Implies \(\implies\) is only false when A is true and B is false
  • Iff (if and only if) \(\iff\)

These connectives can of course be used to define each other:

  • A \(\implies\) B is \(\neg\) A \(\lor\) B
    • implication is only true when either A is false OR B is true
  • Iff is (A \(\implies\) B) \(\land\) (B \(\implies\) A)

Substitution

If a = b then you can substitute a for b, here's an example of using substitution to transform a hard problem into something more familiar:

Solve two systems of equations:

  • \((3x + y)(x + 3y)\sqrt{xy} = 14\)
  • \((x + y)(x^2 + 14xy + y^2 ) = 36\)

Substitute \(\sqrt x\) = u, \(\sqrt y\) = v:

  • uv(3u4 + 10u2v2 + 3v4) = 14
  • u6 + 15u4v2 + 15u2v4 + v6 = 36

Multiply the first by 2 and add both together

  • 36 + 2 · 14 = u6 + 6u5v + 15u4v2 + 20u3v3 + 15u2v4 + 6uv5 + v6

That's the binomial expansion of (u + v)6

  • 64 = (u + v)6

And you can keep going, these are the kinds of techniques we'll learn

Classical logic

Really we should just do what every student of math in history did before us which was to get a classical introduction to categories, logic, causality, and rhetoric, all which teach you how to break down a problem and formulate correct arguments ie: proofs.

You can decide for yourself which ancient civilization's authors are worth reading but be aware of translation quality as some are unreadable without extensive attached commentary.

The Aristoteles Latinus project probably has the best translations they collect all ancient manuscripts like the Boethius translations and then compare them to others, presenting the original Latin, and sometimes ancient Greek with the English translation beside it containing the best estimate of modern language, and a full codex in the index so you can read the Latin yourself. It is definitely worth your time to learn Latin if you speak English. Note the professor in the above video has absolute precision in English despite Dutch being her first language, this is what studying Latin helps you to achieve. Think of it as a model of English to help you learn English.

The same project also translates the ancient Syrian and Islamic empire manuscripts as these civilizations had direct access to many of the original Greek texts, again including the original Syriac or Arabic beside the translation with a codex in the index. Some of these you can find on library genesis otherwise a real library is your only hope, as they are extremely expensive books and exist behind an academic paywall where you need a school login to access the databse.

Some optional lectures on the history of logic from Aristotle to the present state:

Proof assistants

To teach yourself logic, you could also try Logic and Computation Intertwined. Described as a short stroll through proof assistants by building one yourself, Prof Ragde explains dependent types, propositional logic, predicate logic, and the constructive style logic used to model a proof and then run eliminations on it to verify it is correct. It uses Racket (Scheme/Lisp) anybody can follow. Fully demystifies how Coq and Agda work. He will also teach you how to prove facts in Agda about programming languages if you want to learn proofs by induction. These notes are filled with ascii casts of him working out the problems in Emacs. The notes follow the Agda book.

If you like this style of logic try a proof theory seminar by Frank Pfenning w/notes to learn more about natural deduction. The Per Martin-Lof lectures nicely accompany the seminar and are probably the best explanations you will ever read with precise clarity of the rules of inference, connectives, judgements and how eliminations work. In this theory a proof is a concrete object you construct and can test like a program. If you can't construct it, it's not a proof.

(Optional) Arithmetic review

Most of these videos are less than 10m in length and you can choose to watch them later as we go through the algebra problem book. The Hindu-Arabic number encoding is one of the first problems in the book. These are not Khan academy, they are foundational lectures to teach you different 'species' as Isaac Newton put it in Arithmetica Universalis or using modern lingo the different types of math objects. You almost certainly never learned math this way and I recommend you watch them.

The natural numbers

Numbers are objects you build to act like the concept of a number. Here we begin to construct the natural number object.

  • YouTube - Arithmetic and Geometry Math Foundations 1 *note these videos eventually get better in quality

Arithmetic with natural numbers

  • YouTube - Arithmetic and Geometry Math Foundations 2

An interesting explanation of multiplication.

  • Laws for addition
    • n + m = m + n (Commutative)
      • Changing the order of the elements.
    • (k + n) + m = k + (m + n) (Associative)
      • Changing the grouping of the elements.
    • n + 1 = s(n) (Successor)
  • Laws for multiplication
    • nm = mn (Commutative)
    • (kn)m = k(nm) (Associative)
    • n \(\cdot\) 1 = n (Identity)
  • Note the different notation for multiplication:
    • nm
    • n \(\cdot\) m
    • n \(\times\) m
  • Distributive laws
    • k(n + m) = kn + km
    • (k + n)m = km + nm

Exercise: Prove why the multiplication and distributive laws work. Since we have no idea what a proof is yet, we can instead try going through some of our own examples.

Identity law: n \(\cdot\) 1 = n.

  • We are creating n groups of 1. According to our definition of multiplication |||| \(\cdot\) | would be 4 groups of | or ||||. This is still 4.

Commutative law: nm = mn.

  • ||| \(\cdot\) || = || || || or 6. Rearranging this, || \(\cdot\) ||| is ||| ||| which is again 6.

Associative law: (kn)m = k(nm).

  • If k = |, and n = ||, and m = ||| and parens expressions are evaluated first:
    • Left side: (kn)m. We first evaluate (kn) as || (2 groups of 1, the identity law), and 2m is ||| ||| (2 groups of 3) for a total of 6.
    • Right side: k(nm): In the parens nm is 2 groups of 3, so ||| |||. k(6) is the identity law, one group of 6. Thus (kn)m = k(nm).

Distributive law: (k + n)m = km + nm.

  • If k = ||||, and n = ||, and m = |:
    • Left side: (|||| + ||) is 6, and (6) x 1 is six groups of 1 or 6 according to the identity law.
    • Right side: km + nm: 4 groups of one is 4, plus two groups of 1 is 2 (identity law). Answer is again 6.

Laws of arithmetic 2

  • YouTube - Arithmetic and Geometry Math Foundations 3

Wildberger shows another interpretation of multiplication, and walks through the proofs of the laws by rearranging according to the commutative law.

Subtraction and division

  • YouTube - Arithmetic and Geometry Math Foundations 4

Subtraction is the inverse of addition

  • If k + m = n then k = n - m
  • Note: n - m is only defined if n > m as we are still in the realm of the Naturals and negative numbers/integers aren't yet defined.

+, -, are binary operations and can only do 2 operations at a time

  • Laws of Subtraction:
    • n - (m + k) = (n - m) - k
    • n + (m - k) = (n + m) - k
    • n - (m - k) = (n - m) + k
  • Distributive laws of subtraction:
    • n(m - k) = nm - nk
    • (n - m)k = nk - mk

Note to remove parens: https://www.themathpage.com/alg/parentheses.htm we can drop the grouping enforcement when using addition (associative law) but must distribute the negative sign, as subtraction is not associative.

  • n - (m + k) = (n - m) - k
    • removing grouping: n - m - k = n - m - k

The Hindu-Arabic number system

  • YouTube - Arithmetic and Geometry Math Foundations 6

A simplified Roman numeral system is introduced to abstract our previous notation of one's so we can manipulate bigger numbers.

  • Uses powers of 10
    • 327 = 3 x 102 + 2 x 101 + 7 x 100

Arithmetic with Hindu-Arabic notation

  • YouTube - Arithmetic and Geometry Math Foundations 7

Multiplication with the Hindu-Arabic notation:

  • Same laws as before:
    • (ab)c = a(bc)
    • a(b + c) = ab + ac
    • (a + b)(c + d) = ac + ad + bc + bd

A different way of hand multiplication is shown, taking advantage of the fact the notation is using the distributive law.

Division

  • YouTube - Arithmetic and Geometry Math Foundations 8

Division is repeated subtraction. Laws of Division:

  • 1. \(\frac{k}{m}\) + \(\frac{n}{m}\) = \(\frac{k + n}{m}\)
  • 2. \(\frac{k}{m}\) \(\cdot\) \(\frac{n}{l}\) = \(\frac{kn}{ml}\)
  • 3. \(\frac{k/m}{n}\) = \(\frac{k}{mn}\)
  • 4. \(\frac{k}{m/n}\) = \(\frac{kn}{m}\)

Fractions

  • YouTube - Arithmetic and Geometry Math Foundations 9

We're still using only natural numbers.

  • Def: A fraction, is an ordered pair (m,n) of natural numbers also written m/n.
    • Fractions m/n and k/l are equal precisely when ml=nk.

Arithmetic with fractions

  • YouTube - Arithmetic and Geometry Math Foundations 10

We're still in the natural numbers, which he defined as beginning with 1 so we aren't working with zeros yet (no division by zero corner cases). The prime notation (the ' character so c', a', b') used in the proof represents another variable. What we are trying to prove is ab' = ba' and cd' = dc'. He introduces some extra notation multiplying both sides by (dd') to help prove this. This is our first experience with a proof strategy: multiply both sides of something linear by a scalar.

Laws of arithmetic for fractions

  • YouTube - Arithmetic and Geometry Math Foundations 11

Wildberger proves the distributive and commutative laws using fractions while still in the natural numbers.

Introducing the integers

  • YouTube - Arithmetic and Geometry Math Foundations 12

He walks through a proof of a-(b-c)=(a-b)+c

Rational numbers

  • YouTube - Arithmetic and Geometry Math Foundations 13

A rational number is (a-b)/(c-d) according to it's definition but we write them as p/q and in some cases just p if q = 1.

Visualizing the rational numbers

  • YouTube - Arithmetic and Geometry Math Foundations 14

The rational number line sits on [0, 1], so you don't end up with a zero denominator which isn't defined. A rational number is a line through the origin [0,0], and an integer lying on point [m,n]. Ford circles are an example of the massive complexity of the rational numbers, which are expanded upon in the next lecture if you're interested..

Decimal numbers

Wildberger has a basic introduction lecture using natural numbers that assumes you know nothing about exponents and reviews the hindu-arabic notation, showing how to convert a decimal to a fraction. The second lecture introduces rational number decimals and their visualization.

His definition is a decimal number is a rational number a/b, where b is a power of 10 (hence deca/decimal), then shows various examples how you can manipulate rational numbers like 1/2 to be 5/10, or 0.50, we also find out why 1/3 is not a decimal number. In binary, which is a base-2 system, the only prime factor is 2. If you load up any language interpreter and try and add 0.1 + 0.2 you will get surprising results, typically this number: https://0.30000000000000004.com/ because of the way floating point is used to represent decimals.

At 36:00 arithmetic w/decimals is covered, showing how the rational number and decimal number arithmetic methods are the same so you can just stay w/rational numbers if you want converting back to decimals at anytime.

Start here

What is a math circle? It's how they have taught math in eastern Europe for over a century essentially an informal group of all ages from professors to grad student TAs, to elementary school kids all get together to group solve a problem and repeat. Read the preface of Mathematics via Problems: Algebra

How to solve a math problem

Let's start with Poh-Shen Loh's problem seminars. It's discrete combinatorics so no background needed.

The first lecture begins ~14:30 mins. Note what's going on, you are just throwing out little ideas for strategies and writing them all down investigating as you go, making yourself examples. His advice: "If the order matters, you always have an opportunity to order it another way". @45:18 If you're trying to guess the formula for something, it's useful to prime factorize whatever values you are getting. If you start seeing other small primes then you know the answer is a factorial or n choose k binomial coefficient. At the end his general form for En includes n+ (-1)n for alternating rounding, something we will see in the problem books.

If you forgot or have never seen factorials/binomial coefficients, he has a middle school seminar on basic combinatorics here for n choose k and Wildberger has a full explanation on Pascal's array and the Binomial Theorem here completely working through Newton's generalized binomial formula.

Algebra 1

These problem books are designed for grade 9 - 11 Russian national math competition training if you read the author's page. They are given a few sheets from the book to try and solve by themselves at home, then once a week meet either at the Moscow Center for Continuous Mathematical Education or in the woods outside, what he calls 'math walks' where they hike to a local lake and do math outdoors, a good idea. Afterwards they work on unsolved research problems accessible to highschool students. Keep in mind the target audience would have already had middleschool competition training so don't be surprised if you can't solve the problems at first, these are not going to be like any highschool math you remember. I will have a lot of text in the beginning walking through everything then can assume a background so this workshop gets more terse and precise over time.

1.1.1 [MVPA] State and prove the rules of divisibility by 2,4,5,10,3,9,11. Look at the notation guide in the preface to learn x|n means x divides n, or written as a fraction n/x or there exists an integer k such that n = xk. Recall the Wildberger Hindu-Arabic notation lectures: 392 is the sum of (300) + (90) + 2 or ((102 x 3) + (101 x 9) + (100 x 2)). Write your own examples out as tests for each number, if you shave off 2 from 992 then you have 990, which is still divisible by 2. So is 900 if you shave off 92 from 992. Writing more tests you discover if any number ends in 0, 2, 4, 6, 8 or in other words is even, then it's divisible by 2.

The proof is given by the author on the next page, using substitution he rewrites a number n to it's generalized Hindu-Arabic form then subtracts off pieces to reason about the results.

\[n = \pm (10^m \cdot a_m + 10^{m - 1} \cdot a_{m - 1} +..+ 10 \cdot a_1 + a_{0})\]

Where the a in am is between 0 and 9, and the m in am is just an index denoting the position of the terms.

Input examples: 312 = (102)32 + (101)11 + 20 and 312 - a0 is 310. Try the divisible by 3 rule, subtract the sum of digits from the number: 123 - 1 - 2 - 3 = 117 and divisible by 3 (since 1 + 1 + 7 = 9). Try the equivalent method: (102 - 1)1 + (101 - 1)2 + (100 - 1)3 = 99 + 18 + 0 = 117. The key to the proof is in the observation that if you take 10k - 1, convert it to it's Hindu-Arabic form and factor out (10 - 1), then the sum is divisible by 3, therefore a number is divisible by 3 if it's am digits all add up to a number divisible by 3.

The proof of divisibility by 11 f(n) is the function or algorithm where you alternate signs of each digit am and subtract odd digits from even. Using 2728 as an example: 2728 = (103 x 2) + (102 x 7) + (101 x 2) + (100 x 8). 103 and 101 are odd, 102 and 100 are even: f(2728) = 2(-1) + 7(1) + 2(-1) + 8(1) = 11.

Another example: f(9999) = (9-9) + (9-9) and 0 is divisible by 11, or 9999 mod 11 = 0. f(451) = (4-5) + 1 = 0 and again divisible by 11. So for 1.1.1(b) is that number consisting of 1993 ones divisible by 11 (since 111111 is divisible by 11)? Try 111111 x 37 = 4111107 or f(4111107) = (4-1) + (1-1) + (1-0) + 7 = 11 so any number divisible by 111111 follows the same f(n) algorithm rule.

Because f(number-with-1993-1's) has odd number of digits, if we cancel all even with odd there is a remainder: 996 1's subtracted from 997 1's there's 1 left over and not divisible by 11. 1.1.1(c) notice that 37 will divide any number consisting of all 1's if the sum of those digits are divisible by 3 ie: 111 digit sum is 3 and divisible by 37, so is 111111, and 2001 digits all 1's is divisible by 3 as well, so will also be divisible by 37.

You can even write a program to verify 1.1.1(b):

# run this program at https://code.pyret.org/
fun link-ones(n :: Number, l :: List<Number>) -> List<Number>:
  doc: "Make a gigantic list of 1993 1's"
  if n == 1993:
    l
  else:
    link-ones(n + 1, link(1, l))
  end
where:
  link-ones(1, [list: 1]).length() is 1993
  link-ones(0, empty).length() is 1993
end

fun count(n :: Number, l :: List<Number>) -> Number:
  doc: "f(n) algorithm to subtract even/odd digits"
  cases (List) l:
    | empty => 0
    | link(f, r) =>
      if n == 0:
        f + count(1, r)
      else:
        (-1 * f) + count(0, r)
      end
  end
where:
  # begins 10^2 or even
  count(0, [list: 1, 1, 1]) is 1
  # begins 10^3 or odd
  count(1, [list: 1, 1, 1, 1]) is 0
  count(1, [list: 2, 7, 2, 8]) is 11
  # begins 10^5 or odd
  count(1, [list: 5, 9, 3, 2, 7, 4]) is 0
end

check "1993 1's even and odd":
  huge-number = link-ones(1, [list: 1])
  count(0, huge-number) is 1
end

Home