Mathematics A path through The Default Library ======================================== What is true for certain, why, and how far the structures of number, space and change reach. Step 1. Calculus I: Slopes, Totals and the Bridge Between Them -------------------------------------------------------------- Why: Limits, derivatives and integrals: the calculus every later course makes rigorous. Your car's speedometer is a derivative. Its odometer is an integral. Everything a first calculus course teaches is a way of moving between the two. Look at a dashboard. The odometer says how far you have gone in total. The speedometer says how fast the total is changing right now. Press the accelerator and the speedometer moves first; the odometer follows, a little behind, like a patient accountant adding up what the speedometer reported. Nobody gave the speedometer a ruler or a clock to look at the whole trip. It reads one instant. Yet it reports a rate, which is a statement about change, from a single moment. How can a single moment say anything about change? That puzzle is what the course exists to answer, and the answer turned out to run most of modern engineering and computing. This is the second time the library has met calculus. Calculus: Derivatives, Integrals, and the Language of Motion (12/11) is the easier first read, with the tangent line and the rectangle sum. Here we go a step further: what the course trains you to see, how a computer gets it wrong, and where the idea is used afterwards. The course in one box Who takes it: first-year students in Mechanical & Aerospace Engineering and in Computer Science, and almost every other science or engineering degree. What it is for: turning "how much?" into "how fast?" and back, so that change can be calculated instead of guessed. Comes after: nothing in this series. Algebra and a little trigonometry are all it assumes. Leads to: Multivariable Calculus (34/02), Differential Equations (34/03), Probability & Statistics (34/05), Physics I: Mechanics (34/06), Thermodynamics (34/14), and from them nearly everything else on both majors. Honest line: you will not be able to differentiate a hard formula by hand after this. You will see why a flat spot on a curve is where the best answer hides, and why the area under a rate is a total. A limit is where a calculation settles The speedometer puzzle is this. Speed is distance divided by time, but in an instant no time passes and no distance is covered, so you seem to be dividing zero by zero. The way out is to stop asking what happens at zero and ask what a sequence of better and better answers is settling towards. Measure over one second, then a tenth, then a hundredth, and watch the average speed home in on a number. That number is the limit. speed now = limit of (distance change ÷ time change) as the time change shrinks to 0 A graduate does not carry the formal definition around, but carries the habit: if a quantity looks like 0 ÷ 0, ask what it is approaching. Take sin(x) ÷ x as x goes to zero, with x in radians. At x = 0.1 it is 0.99833; at 0.01, 0.99998; at 0.001, 0.9999998. It never "is" 1 at zero, since it is undefined there, but it settles on 1. That one limit is why the derivative of sine turns out to be cosine. Interactive · Shrink the gap until the computer gives up We estimate the slope of ex at x = 1 by (e1+h − e) ÷ h. The true slope is e = 2.718281828459045. Make the gap h smaller. Gap h = 10−k The error falls as the gap shrinks, as the limit promises, until about h = 10−8, where it bottoms out near 7 × 10−9. Shrink further and it gets worse: the two values being subtracted agree in almost all of their roughly 16 stored digits, so the subtraction wipes out the information. At 10−16 the answer is exactly 0. This is a computer-science lesson hiding in a calculus course: the limit is a mathematical idea, and a machine can only approach it so far. The derivative is a slope, and a slope is a rate Zoom in on any smooth curve and it straightens out. The steepness of that straight piece is the derivative. In plain words: how much the output moves per unit nudge of the input. If the curve is distance against time, the derivative is speed. If it is temperature against position, it is how sharply it warms as you walk. Rate and slope are one thing seen two ways. f′(x) = limit of [f(x+h) − f(x)] ÷ h as h → 0 The graduate's real asset is not computing derivatives but reading them. Where the curve is rising, the derivative is positive. Where it is flat, the derivative is zero. Where the curve is steepest, the derivative is at its peak. Try it: the lower graph is the derivative of the upper one, drawn point by point. Interactive · A curve and its slope, side by side x³ − 3x sin x bell: e^(−x²) Position x Check the three curves. Every time the top curve peaks or dips, the bottom one crosses zero. Every time the top is climbing, the bottom is above the axis. For x³ − 3x the slope is 3x² − 3, which is zero at x = −1 and x = 1: the hill top and the valley floor. The chain rule: rates multiply down a chain Rates often come in chains. A bicycle's pedals turn the chainring, the chain turns the rear wheel, the wheel moves the bike. If the wheel turns 3 times per pedal turn, and the bike moves 2 metres per wheel turn, the bike moves 6 metres per pedal turn. You multiply the ratios. That is the chain rule, and it is the most used rule in the course. d(outer)/d(input) = d(outer)/d(middle) × d(middle)/d(input) The classic worked case is a balloon. Its volume depends on its radius, and the radius depends on time. At radius r the surface has area 4πr², so one extra centimetre of radius adds a shell of volume about 4πr² cm³: that is dV/dr. Multiply by how fast the radius is growing and you have how fast the volume is growing. At r = 10 cm, growing 2 cm each second, volume grows at 4π × 100 × 2 ≈ 2,513 cm³ per second. Pull the sliders and confirm it. Interactive · Inflate a balloon Radius now Radius is growing at The picture shows why it works: the shaded shell is what one second adds, a skin of area 4πr² and thickness equal to the radius growth. The same rule runs inside every neural network, where the "chain" is dozens of layers long and the multiplication is called backpropagation (Machine Learning, 34/32; Multivariable Calculus, 34/02). Where the slope is zero, something is best At the top of a hill you stop going up and have not yet started going down. The slope is zero. So to find the biggest or smallest value of anything smooth (strongest, cheapest, lightest, fastest) look for where its derivative is zero. That is optimisation, and it is why engineers love the derivative. Take a 30 cm by 20 cm sheet of card. Cut a square of side x from each corner and fold up the sides to make an open box. Its volume is V = x(30 − 2x)(20 − 2x). Cut too little and the box is shallow. Cut too much and it is narrow. In between there is a best x, and the slope tells you where: at x ≈ 3.92 cm the volume peaks at about 1,056 cm³. Interactive · The best box Corner cut x Jump to the flat spot Notice what the slope does as you drag. To the left of the peak the slope is positive, so a bigger cut helps. To the right it is negative, so a smaller cut helps. At the peak it is zero and nothing nearby is better. Gradient descent, the algorithm that trains machine-learning models, is exactly this reasoning repeated: look at the slope, step downhill, repeat. The integral adds up a rate into a total The odometer is the speedometer added up over time. Draw speed against time; the area between the curve and the time axis is distance. That is the integral. Anywhere a rate is known and a total is wanted (litres per minute into a tank, watts into a battery, newtons over a distance) the answer is an area. Try it before you read on. A car accelerates steadily from 0 to 20 m/s in 10 seconds, cruises at 20 m/s for 30 seconds, then brakes steadily to a stop in 10 seconds. How far has it gone? Interactive · Predict, then reveal 600 m 800 m 1,000 m 1,200 m Choose an answer. The shape is two triangles and a rectangle: ½ × 10 × 20 + 30 × 20 + ½ × 10 × 20 = 100 + 600 + 100 = 800 m. The common wrong guess, 1,000 m, uses the top speed for all 50 seconds and forgets that the car spends time slower than that. The Fundamental Theorem: two jobs, one idea Here is the surprise that makes the course a single subject. Build a running total from a rate: the amount in the tank after time T. Then ask how fast that total is growing at T. The answer is just the rate at T. Accumulating and differentiating undo each other, the way the odometer and speedometer do. Newton and Leibniz, working separately in the late 1600s, each saw this. if A(T) = area under the rate up to T, then A′(T) = the rate at T Its practical power is that you can find a total without adding anything: find a function whose slope is your rate and subtract its values at the two ends. Below, water flows into a tank at a rate that wobbles: 4 + 3 sin(t/2) litres per minute. Drag the time and watch the right-hand graph, the tank's total, steepen exactly when the rate on the left is high. Interactive · The tank and its rate Time T The readout checks the theorem two ways: area by adding 600 thin slices, and the exact formula 4T + 6(1 − cos(T/2)). At T = 12 minutes both give 48.24 litres. The slope of the total at that moment is 4 + 3 sin 6 ≈ 3.16 litres per minute, the rate at that moment. Every smooth thing is nearly a straight line The last habit is the most useful in daily engineering. Close to any point, a smooth curve is almost its tangent line, so you can replace it with a straight line and be nearly right. The small-angle rule sin x ≈ x is why a pendulum swings at a steady rhythm. The rule √(1 + x) ≈ 1 + x/2 gives mental square roots: √1.1 ≈ 1.05, true value 1.0488. f(a + x) ≈ f(a) + f′(a) · x   (good when x is small) How small is small? The error shrinks faster than the step. Halve the step and the error falls about four times for √(1 + x) and ex, and about eight times for sine. Interactive · How good is the straight line? sin x ≈ x √(1+x) ≈ 1 + x/2 eˣ ≈ 1 + x Step x from the point What a graduate just sees A rate and a slope are the same thing, and "how fast?" always means a derivative. A total is an area under a rate, and adding up thin slices is a calculation, not a mystery. Rates multiply along a chain: gear ratios, units, layers of a network. The best value of a smooth quantity sits where its slope is zero. Differentiating and accumulating are inverse jobs, so a total can often be found without adding. Up close, everything smooth is a straight line, and engineers exploit that constantly. Subtracting two nearly equal numbers on a computer destroys precision, so a naive slope estimate gets worse when the gap gets too small. Where it shows up next Physics I (34/06) and Dynamics (34/12): velocity is the derivative of position, acceleration of velocity, and Newton's law ties force to the second one. Differential Equations (34/03): when a law is written as a rate, solving it means integrating, which is the whole next course. Thermodynamics (34/14) and Heat Transfer (34/16): heat added is an integral of power; temperature profiles are read from slopes. Probability & Statistics (34/05): the chance of a range of outcomes is the area under a density curve. Algorithms (34/24) and Machine Learning (34/32): growth rates of running time are compared with limits, and models are trained by following slopes downhill. If you want to go deeper 📘 Textbook: James Stewart, Daniel Clegg and Saleem Watson, Calculus: Early Transcendentals (9th ed., Cengage). The most-assigned text; best for worked examples and a huge problem bank. 📘 Textbook: Hass, Heil, Bogacki and Weir, Thomas' Calculus (15th ed., Pearson). Strong on applications, popular in engineering departments. ▶️ Gentler: Grant Sanderson's Essence of Calculus series on 3Blue1Brown, a visual tour of the same ideas. Also Steven Strogatz, Infinite Powers, for the story. 🌐 Free course: MIT OpenCourseWare 18.01SC Single Variable Calculus, with video lectures, notes and problems. Khan Academy also covers it. The takeaway Calculus I teaches two moves and one bridge. The derivative turns a total into a rate (a slope); the integral turns a rate into a total (an area); and the Fundamental Theorem says they undo each other. From that come the habits of mind: chain rates together, look for zero slope to find the best, and treat smooth things as lines up close. Our slope estimate for ex was best near a gap of 10−8 and useless at 10−16, a reminder that the ideas are exact and the machines are not. Try this: next time you are in a car or on a bike, watch the speedometer and ask what the area under its history means. Then on a hill, find the spot where the road is flat. That is a derivative equal to zero. Sources & Further Reading Sources. Every number in the interactives was computed in node: the forward-difference error of ex at x = 1 for h = 10−1 to 10−16 (best 6.6 × 10−9 at 10−8, exactly 0 at 10−16, in IEEE double precision); sin(x)/x at 0.1, 0.01, 0.001; the box V(x) = 4x³ − 100x² + 600x, zero slope at x = (50 − √700)/6 = 3.9237, V = 1,056.3 cm³; the balloon 4π × 10² × 2 = 2,513.27 cm³/s; the car, 800 m; the tank, A(12) = 48.239 L; small-step errors of the three approximations. Book editions checked against the publishers' pages (Cengage, Pearson) and the course numbers against MIT OpenCourseWare. 🌐 MIT OpenCourseWare 18.01SC Single Variable Calculus ▶️ 3Blue1Brown: Essence of Calculus 🌐 Khan Academy: Calculus 1 📘 Stewart, Clegg and Watson, Calculus: Early Transcendentals, 9th ed. (Cengage) 📘 Hass, Heil, Bogacki and Weir, Thomas' Calculus, 15th ed. (Pearson) 📘 Steven Strogatz, Infinite Powers, a popular history of calculus Step 2. Linear Algebra: Machines That Move Space ------------------------------------------------ Why: Vectors and matrices: the most useful structure in mathematics. A grid of numbers is really a machine that moves all of space at once. Learn to see it, and circuits, bridges, search engines and AI all start to look alike. You pinch two fingers on a photo and it rotates and zooms smoothly under them. A game character turns to face you and every corner of its face swings round together. A search for "best pizza near me" ranks millions of pages in a fraction of a second. A bridge designer presses "solve" and a screen of colour shows how every beam is being squeezed. Underneath all four is the same object: a grid of numbers, and one habit of thought about what a grid of numbers does. A graduate of a linear algebra course no longer sees a table of numbers. They see a machine that grabs the whole plane, or the whole of space, and moves it. This piece builds that picture with seven things you can drag. You will not come out able to compute a determinant of a 5×5 by hand (nobody does that on purpose). You will come out seeing why a system of equations sometimes has no answer, why a bridge hums at particular pitches, and why the chips that run AI are built for one operation only. The course in one box Who takes it: nearly every engineering and computer science student, usually in the first or second year. It is the single most reused maths course in both majors. What it's for: handling many unknowns and many dimensions at once, with one set of tools. Comes after: only school algebra and a little geometry. (Calculus helps but is not required.) Leads to: Statics (34/10), Control Systems (34/20) and Machine Learning (34/32) list it as a prerequisite; Vibrations (34/17), Computer Architecture (34/25) and Multivariable Calculus (34/02) lean on it constantly. Honest line: you won't be able to run a finite element program after this piece. You will see why it spends nearly all its time solving one equation, Ax = b. If you want an easier first read, try the library's Vectors, Matrices and Linear Transformation (12/14); this one goes further into solving, eigenvectors, fitting and why hardware cares. A matrix moves all of space at once Start with the picture a graduate keeps. A 2×2 matrix is not four numbers. It is two arrows. The first column says where the arrow pointing one step right (call it i) ends up. The second column says where the arrow pointing one step up (j) ends up. Once you know where those two land, you know where everything lands, because every point is some amount of i plus some amount of j, and the machine is straight and even: grid lines stay straight, and evenly spaced lines stay evenly spaced. Ax = x1(column 1) + x2(column 2) Read that in words: the matrix times a point is "that many of the first column, plus that many of the second". Try it. The grey grid is the original plane; the blue grid is where the matrix sends it. Interactive · Move the plane Do nothing Rotate 30° Stretch Shear Mirror Column 1, right part (a) Column 2, right part (b) Column 1, up part (c) Column 2, up part (d) Without JavaScript: the rotate-30° matrix sends the arrow (1, 0) to (0.87, 0.5) and (0, 1) to (−0.5, 0.87). Every grid line turns 30° and the unit square keeps area 1. Notice what the shaded unit square does. In "Rotate" it keeps its size. In "Stretch" it doubles. In "Shear" it leans over but keeps its area. That area change is the next idea. The determinant is how much area gets scaled The determinant is one number that says how much the machine scales area. If the unit square becomes a shape with area 5, the determinant is 5. If it becomes a mirror image, the determinant is negative: area is kept (or scaled) but orientation is flipped. For a 2×2 matrix with columns (a, c) and (b, d) the rule is short: det = ad − bc Worked number: the matrix with columns (2, 1) and (1, 3) has det = 2×3 − 1×1 = 5, so it stretches every area in the plane by a factor of five. In three dimensions the determinant scales volume. The interesting case is zero. A determinant of zero means the machine flattens space: the plane is squashed onto a line (or a point), and the area becomes nothing. Squashing cannot be undone, because many different starting points land on the same spot. Drag the slider until the determinant reaches zero. Interactive · Squash the plane flat Tilt the second arrow: s Without JavaScript: the matrix with columns (1, 0.5) and (s, 1) has determinant 1 − 0.5s. At s = 2 the determinant is 0, the whole plane lands on one line, and the points (0, 0) and (2, −1) both land on the origin. The orange dot is a probe at (2, −1). At s = 2 it lands exactly on the origin, the same place as the point (0, 0). Two different inputs, one output: no machine could tell you which one you started from. That is the whole meaning of "this matrix has no inverse", and it is why a zero determinant is the alarm bell in every solver you will ever meet. Solving many equations at once: Ax = b Now use the machine backwards. Given the output b, which input x did the machine start from? That is the equation Ax = b, and it is the most common problem in applied mathematics. Every time you have several unknowns that are tied together by several straight-line relationships, you have one. A circuit is the cleanest example. Two loops share a resistor. Kirchhoff's voltage law says the voltage gained around each loop equals the voltage lost, which gives one equation per loop. With a 10 V battery, R1 = 2 Ω, R2 = 3 Ω (shared) and R3 = 4 Ω: 5I1 − 3I2 = 10−3I1 + 7I2 = 0 The determinant is 5×7 − 3×3 = 26, so there is exactly one answer: I1 = 2.69 A and I2 = 1.15 A. Change the resistors below and watch the matrix and the answer change together. Interactive · Solve a circuit with a matrix Battery V R1 (loop 1 only) R2 (shared) R3 (loop 2 only) Without JavaScript: with 10 V, 2 Ω, 3 Ω and 4 Ω the equations are 5I1 − 3I2 = 10 and −3I1 + 7I2 = 0, its determinant is 26, and the loop currents are 2.69 A and 1.15 A. The reason an engineer cares: nothing about this method knows it is a circuit. A truss is the same. At each joint of a bridge, the horizontal forces must add to zero and so must the vertical ones: two equations per joint. A simple triangle truss has three joints and so six equations, for three member forces and three support reactions, and the answer is one solve of Ax = b. A real structure has thousands of joints. Finite element programs routinely solve systems of many thousands of equations, and research codes have reported solving over a million unknowns at once. The method is the same one you just used; only the size has changed. (Statics, 34/10, is this idea applied to forces.) A zero determinant in a structure's equations is a warning: the structure may be able to move without any member pushing back. Eigenvectors: the directions a transformation only stretches Most arrows are turned by a matrix as well as stretched. But for many matrices there are special directions where the arrow comes out pointing the same way (or exactly backwards), only longer or shorter. Those are the eigenvectors, and the stretch factor along each is its eigenvalue. (Eigen is German for "own": the matrix's own directions.) Av = λv In words: feed the matrix the special arrow v and it hands back the same arrow multiplied by a plain number λ. For the matrix with columns (2, 1) and (1, 2) the special directions are 45° (stretched by 3) and 135° (stretched by 1). Every other arrow gets bent towards the stretchy one. Turn the dial and look for the moments the two arrows line up. Interactive · Find the directions that only stretch Stretch & mix Shear Rotation Two springs Direction of the input arrow Without JavaScript: for the matrix with columns (2, 1) and (1, 2), an arrow at 45° comes out at 45° three times longer, and an arrow at 135° comes out at 135° unchanged. A pure rotation has no such direction at all. Three things to notice. The shear has only one special direction (along the x-axis, where nothing happens at all). The rotation has none, because every arrow turns. And "Two springs" has two special directions with different stretch factors, 1 and 3; hold that thought. Eigenvectors at work: bridges that hum, pages that rank Vibration. Picture two equal masses on springs between two walls. Push them any way you like and the motion looks messy. But there are exactly two clean patterns: both swing together, or they swing in opposite directions. These are the modes, and they are the eigenvectors of the "two springs" matrix above, (1, 1) and (1, −1). The eigenvalues 1 and 3 fix how fast each mode vibrates: the squared frequency is the eigenvalue times k/m, so the opposite-motion mode vibrates √3 ≈ 1.73 times faster. Any messy motion is just a mix of the modes. That is how engineers find which pitches will shake a wing, a bridge deck or a drive shaft (Vibrations, 34/17). Ranking pages. Google's founders modelled a web surfer who follows a random link from each page, and now and then jumps to a random page instead. The long-run share of time spent on each page is its PageRank, and it is the eigenvector (with eigenvalue 1) of the matrix describing one step of that surfer. In their 1998 paper Brin and Page used a "damping" probability of 0.85 for following links. You can find the eigenvector without solving anything fancy: start with equal scores and apply the machine over and over. Press Step. Interactive · A four-page web finds its eigenvector Step onceRun 20 stepsReset Without JavaScript: A links to B and C, B links to C, C links to A, D links to C. After many steps with damping 0.85 the ranks settle to A 0.373, B 0.196, C 0.394, D 0.038. D, which nobody links to, keeps only the base share. After about twenty steps the numbers stop changing: the vector has become an eigenvector, because applying the machine again returns the same vector. Page C wins because two pages point at it and one of them (A) is itself well-ranked. Least squares: the best answer when there is no exact one Real data is never perfect. Six measurements that "should" lie on a straight line will not, so the equations Ax = b have more equations than unknowns and no exact solution. Do you give up? No. You choose the line whose total mistake is smallest. Measure each miss vertically, square it, and add up the squares. The least squares line makes that total as small as possible. In pictures: each squared miss is literally a square. Drag the line and watch the squares shrink and grow. Interactive · Make the squares as small as possible Slope Height at x = 0 Snap to the least-squares line Without JavaScript: for the six points (1, 1.2), (2, 2.9), (3, 3.1), (4, 4.8), (5, 5.2), (6, 7.1) the best line is y = 1.089x + 0.24, with total squared miss 0.798. The guess y = x gives 2.75. The graduate's picture is geometric: the right-hand side b is a point outside the flat sheet of everything the matrix can reach, and the best answer is the point on the sheet closest to it, found by dropping a perpendicular. That perpendicular condition gives the one equation to remember: ATA x̂ = ATb In words: multiply both sides by the matrix flipped on its side and you get a square system you can solve. The history is a priority fight: Legendre published the method in 1805, Gauss said he had used it since 1795 and published in 1809, and Gauss's use of it to predict where the asteroid Ceres would reappear in 1801 made it famous. Today it sits under every trend line, every calibration of a sensor, and the first model most machine-learning students ever train. Why GPUs and AI are matrix multiplication Multiplying two matrices is just many dot products: every cell of the answer is one row of the first matrix paired with one column of the second, multiplied and added. Click a cell below and see the row and column that make it. Interactive · Build a product cell by cell Tap a cell of C = A × B. Matrix size n (n × n times n × n) 1 billion multiplies per second 100 billion per second 10 trillion per second The speeds are round illustrative numbers, not any particular chip. Without JavaScript: multiplying two n×n matrices takes n×n×n multiplications. For n = 1,000 that is 1,000,000,000, and the 1,000,000 cells of the answer can all be computed independently. Two facts follow. First, the work is huge: n×n matrices need n³ multiplications, so 1,000×1,000 is a billion. Second, the cells are independent, so a thousand workers (or a million) can each take cells at the same time. That is exactly the shape of work a graphics chip was built for, because drawing a 3D scene means pushing every corner of every triangle through a matrix that rotates, moves and projects it. Modern neural networks turned out to be the same shape. A layer of a network is a matrix of learned numbers times a vector (or a matrix) of inputs. In their scaling-law paper, Kaplan and colleagues estimate that a transformer language model with N parameters needs roughly 2N arithmetic operations to process one token. GPT-3, with 175 billion parameters, therefore needs about 3.5×1011 operations for each token, nearly all of them inside matrix products. NVIDIA's Volta GPUs (2017) put dedicated "tensor core" circuits on the chip that do nothing but a small matrix multiply-and-add (4×4) per clock tick. When people say AI runs on GPUs, they mean it runs on hardware shaped like linear algebra. (Computer Architecture, 34/25, and Machine Learning, 34/32.) What a graduate just sees A matrix is a machine that moves all of space; its columns say where the basis arrows go. The determinant is the area (or volume) scale factor, and zero means the machine flattens space and cannot be undone. "Solve Ax = b" is the same question for a circuit, a truss, a fitted line and a game physics step. If there are as many independent equations as unknowns there is one answer; fewer, many answers; contradictory, none. Eigenvectors are the directions a machine only stretches; they simplify any problem the machine drives. A vibrating structure is a mix of modes, one per eigenvector; the eigenvalues are the pitches. When there is no exact answer, take the closest one: project onto what you can reach. Matrix multiplication is many independent dot products, which is why it parallelises and why hardware is built around it. Where it shows up next Statics (34/10) and Mechanics of Materials (34/11): joint and member forces are a linear system; stiffness matrices tie loads to deflections. Vibrations (34/17) and Dynamics (34/12): mode shapes and natural frequencies are eigenvectors and eigenvalues of mass and stiffness matrices. Control Systems (34/20): the eigenvalues of a system's matrix say whether a drone's wobble dies away or grows. Machine Learning (34/32): data is a matrix, a layer is a matrix, and training adjusts matrices; least squares is the model you meet first. Computer Architecture (34/25) and graphics: GPUs and tensor cores exist to multiply matrices fast. If you want to go deeper 📘 Gilbert Strang, Introduction to Linear Algebra (Wellesley-Cambridge Press; 6th edition, 2023). The standard first course for engineers; best for the four fundamental subspaces and for application. 📘 David C. Lay, Steven R. Lay and Judi J. McDonald, Linear Algebra and Its Applications (Pearson; 6th edition, 2021). Gentle, example-heavy, widely assigned. For proofs, Sheldon Axler's Linear Algebra Done Right (Springer; 4th edition, free to read online at linear.axler.net) is the elegant theoretical route. ▶️ 3Blue1Brown, Essence of Linear Algebra: the best visual series for learning alone; it builds exactly the "matrix as moving space" picture used here. 🌐 MIT OpenCourseWare 18.06, Linear Algebra (Gilbert Strang): full video lectures, free. The takeaway Linear algebra is the study of machines that move all of space at once. Read a matrix by its columns, read its determinant as the area scale, solve Ax = b when you need to run the machine backwards, look for the eigenvector directions when you want it to be simple, and project onto what you can reach when there is no exact answer. Try this: next time an app zooms, rotates or recolours a photo, picture the two column arrows moving. And for the fun of it, in the circuit widget raise R2 to 10: the shared resistor starts to decide what both loops do. Sources & Further Reading Sources. Strang, Introduction to Linear Algebra (6th ed., 2023) and MIT 18.06 for the standard course content. Kirchhoff loop equations and the spring-mass modes are textbook derivations; every number above was recomputed in code. Legendre's 1805 publication and Gauss's priority claim and Ceres prediction: Wikipedia, "Least squares"; MacTutor biography of Legendre. PageRank and the 0.85 damping factor: Brin and Page, "The Anatomy of a Large-Scale Hypertextual Web Search Engine" (1998). Volta tensor cores (4×4 matrix multiply-accumulate): Markidis et al., "NVIDIA Tensor Core Programmability, Performance & Precision" (2018). About 2N operations per token: Kaplan et al., "Scaling Laws for Neural Language Models" (2020); GPT-3 at 175 billion parameters: Brown et al. (2020). Million-unknown structural solves: NASA Technical Reports Server and OSTI conference papers on parallel sparse solvers. Go deeper. The books and courses above. Step 3. Discrete Mathematics: Counting, Logic and Proof ------------------------------------------------------- Why: Logic, counting and the first real proofs. Computers cannot handle the smooth infinite; they handle countable things. This is the maths of switches, steps, networks and clocks. Your phone adds two numbers in a few billionths of a second, using nothing but switches that are either on or off. A barcode scanner knows you mistyped one digit of a book's number before it looks anything up. A map app finds the quickest route among millions of roads without trying them all. And a password check takes the same instant whether the password is long or short. None of these runs on the smooth, continuous maths of calculus. They run on things you can count: bits, steps, roads, remainders. A graduate of a discrete mathematics course carries a small set of habits for reasoning about countable things, and they are the habits that separate "it seems to work" from "it must work". This piece gives you those habits through six ideas and eight things to try: build an adder from logic, count what you cannot list, watch an induction proof grow, search a graph, wrap numbers around a clock, and see why some programs take longer than the age of the universe. The course in one box Who takes it: every computer science student in the first year, and many engineers; it is the entry ticket to the theory side of computing. What it's for: reasoning exactly about finite and countable things: logic, collections, steps, networks. Comes after: nothing but school mathematics. (Programming Fundamentals, 34/09, helps but isn't required.) Leads to: Algorithms (34/24), Computer Architecture (34/25), Databases (34/28) and Theory of Computation (34/29) all list it as a prerequisite. Honest line: you won't be able to prove a hard theorem after this. You will be able to see why a loop must stop, why a network has a shortest path, and why one algorithm will never finish. For easier first reads, see the library's Graph Theory (12/18) and Cryptography (12/09); this piece goes further into logic, proof, counting and growth. Logic: truth tables become circuits A proposition is a statement that is either true or false. Three operations build all the rest: AND (true only when both are true), OR (true when at least one is) and NOT (flips it). A truth table lists every case, and for two inputs there are only four rows. Another useful operation is XOR ("one or the other, but not both"). ABA AND BA OR BA XOR B 00000 01011 10011 11110 Boole's 1854 book treated logic as algebra; the AND/OR/NOT algebra we use today was tidied up by his successors. The leap to hardware came in 1937, when Claude Shannon's MIT thesis showed that networks of switches could carry out exactly this algebra. Every gate in a processor since is a physical truth table. Look at the XOR column: it is adding. 1 + 1 = 10 in binary, so the digit is 0 (XOR) and there is a carry of 1 (AND). Chain that into a full adder (it also takes the carry from the column on its right) and line four of them up, and you have a circuit that adds numbers up to 15. Choose two numbers and watch the carries ripple. Interactive · Add with nothing but logic gates First number Second number Without JavaScript: 7 + 9 is 0111 + 1001 in binary. The carry ripples through all four columns and the result is 10000, which is 16. sum = A XOR B XOR carry-in    carry-out = (A AND B) OR (carry-in AND (A XOR B)) That is a complete circuit for one column: five gates. Everything a processor does (comparing, jumping, multiplying) is built the same way, so Computer Architecture (34/25) is largely this idea scaled up. Engineers also use the same logic on whole systems: a fault tree in reliability analysis is AND and OR gates over "this valve fails" and "this pump fails" (Systems Engineering, 34/22). Sets, functions and counting: sorting the world and counting it A set is a collection with no repeats; a function assigns each member of one set exactly one member of another. A function is one-to-one if no two inputs share an output, and onto if every possible output is hit. Remember these words: "the hash has collisions" means "the function is not one-to-one", and a compression scheme that shrinks every file would have to be one-to-one into a smaller set, which is impossible. The first counting rule is about overlap. If you add the sizes of two sets, anything in both gets counted twice, so subtract it once. This is inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B| In a class of 40, 25 take computing, 18 take maths and 9 take both: 25 + 18 − 9 = 34 take at least one, so 6 take neither. Interactive · Count the overlap Take computing Take maths Take both Without JavaScript: in a class of 40 with 25 in computing, 18 in maths and 9 in both, 34 take at least one subject and 6 take neither. Next, counting arrangements. If order matters, choose the first item in n ways, the next in n−1, and so on: choosing and ordering k of n items gives n!/(n−k)! possibilities. If order doesn't matter, divide by the k! ways to shuffle the chosen ones: that is a combination, written C(n,k). C(n,k) = n! / ( k! (n−k)! ) Worked example: a five-card poker hand from 52 cards is C(52,5) = 2,598,960 hands, while the number of orderings of a whole deck is 52! ≈ 8.07×1067. A shuffled deck has almost certainly never been in that order before in history. Interactive · Orderings versus selections Items to choose from: n Items chosen: k Without JavaScript: choosing 3 of 10 gives 720 ordered ways and 120 unordered ways; choosing 5 of 52 gives 2,598,960 hands. The sneakiest counting idea has no formula. The pigeonhole principle says that if you put more than m items into m boxes, some box holds two. It sounds trivial, and it proves strong things: among any 13 people, two share a birth month; no compression method can shrink every file; any hash function that maps many inputs to few outputs must collide. Dirichlet used it in number theory in 1834. Drop random people into the seven days of the week: you are guaranteed a repeat by the eighth, and you will usually get one sooner (most often between the 3rd and 5th drop). Interactive · Pigeons into seven boxes Drop a pigeonDrop until a doubleClear Without JavaScript: with 7 boxes, the 8th pigeon is guaranteed to share a box. With random drops the first double typically comes earlier, most often between the 3rd and the 5th pigeon. Proof: induction and contradiction You can't test infinitely many cases, so mathematicians prove. Two tools do most of the work. Induction is the domino proof: show the first domino falls (the base case), and show that if any domino falls, the next one does (the step). Then they all fall. Take the claim that the first n odd numbers add up to n². Base case: 1 = 1². Step: if the first n odd numbers make an n×n square, the next odd number, 2n+1, is exactly an L-shaped border that turns it into an (n+1)×(n+1) square. Slide n and watch the border go on. Interactive · Squares grown by odd numbers Odd numbers added: n Without JavaScript: 1 + 3 + 5 + 7 + 9 = 25 = 5². Adding the next odd number, 11, makes 36 = 6²: a border of 2×5+1 = 11 squares. Induction is how you prove a loop does what it should: the loop invariant is the claim, the first pass is the base case, and each pass is the step. It is also the heart of recursion, which is a program that calls a smaller copy of itself. Contradiction works the other way: assume the claim is false and show that this leads to nonsense. Euclid's proof that there are infinitely many primes is usually told this way: suppose the list of primes were finite, multiply them all together and add one. That number leaves remainder 1 when divided by every prime on your list, so either it is itself a new prime or it has a prime factor you didn't list. Either way the list was incomplete. (Some historians point out Euclid's own argument can be read as a direct one; the contradiction telling is the modern standard.) A programmer uses the same move when they say "suppose the algorithm returned a wrong answer; follow that and it breaks the invariant". Graphs and trees: things and their connections A graph is dots (nodes) and links (edges); the library's Graph Theory piece (12/18) introduced it. Here is a deeper habit. Count the edge ends: each edge has two, so the degrees (links at each node) always add up to exactly twice the number of edges. This handshake lemma is why the number of guests who shook an odd number of hands is always even. The workhorse algorithm is breadth-first search: visit the start, then everything one step away, then everything two steps away, using a queue. It finds the fewest-hops route to every node. The edges it used to reach each new node form a tree: a connected graph with no loops, which always has exactly one fewer edge than nodes. Pick a start and press Step. Interactive · Breadth-first search, one step at a time StepRun to endRestart Without JavaScript: in the 8-node, 11-edge graph, the degrees add to 22, twice the edge count. Breadth-first search from A reaches every node in at most 3 hops, using exactly 7 edges, one fewer than the number of nodes. Graphs appear everywhere in the two majors. A truss is a graph whose nodes are joints and edges are members (Statics, 34/10). A circuit is a graph (the loop equations you meet in Linear Algebra, 34/04, come straight from it). A road map, a network of routers, a dependency chart for building a product and a social network are all graphs, and a file system is a tree (Operating Systems, 34/26). Routers and links are a graph too (Computer Networks, 34/27). Modular arithmetic: clocks, hashes and check digits On a clock, 10 o'clock plus 5 hours is 3 o'clock, not 15. Modular arithmetic wraps numbers around: a mod m is the remainder when you divide a by m. It is used wherever a quantity cycles or has to be squeezed into a fixed number of slots. Try the clock, and below it a tiny hash table: each word is turned into a number, and that number mod the table size picks its slot. Interactive · Clock and hash table The number Clock size m (also the number of table slots) Without JavaScript: 47 mod 8 = 7, because 47 = 5×8 + 7. With 8 slots, adding up each word's letter codes and taking the remainder sends "bolt" and "cam" to the same slot, and "shaft" and "valve" to the same slot: two collisions. Slide the clock size up and the collisions mostly disappear, but by the pigeonhole principle you can't remove them while there are more words than slots. Databases (Databases, 34/28) and compilers use hash tables everywhere. Remainders also catch mistakes. The last digit of a 13-digit book number (ISBN-13) is chosen so that the digits, weighted 1, 3, 1, 3 and so on, add to a multiple of 10. Take 978-0-306-40615-7: the first twelve digits give 93, and 10 − (93 mod 10) = 7. Change any one digit and the total is no longer a multiple of 10, so a scanner rejects it. Most swaps of neighbouring digits are caught too (those that differ by 5 slip through). Cryptography (12/09) is the same arithmetic taken to huge numbers, and it underlies Computer Security (34/33). Engineers meet it in machines. A shaft encoder reports its angle modulo one turn. And gear designers sometimes choose tooth counts with no common factor, such as 20 and 21, so that each tooth meets every tooth on the other gear before any pair repeats: the pattern repeats only after lcm(20, 21) = 420 meshes, against 60 for 20 and 30 teeth, which spreads wear evenly (Machine Design, 34/19). Big-O: growth as a counting idea How long does a program take? Count its steps, as a function of the input size n, and keep only the part that grows fastest: big-O notation. Searching an unsorted list takes about n steps, O(n). Searching a sorted list by repeatedly halving takes about log2n, which is 20 steps for a million items. Comparing every pair is about n². And trying every subset of n things is 2n, which is where counting becomes a wall. Pick a size and a machine speed. The shape of the growth matters more than the speed of the machine. Interactive · How long would it take? Problem size n Machine speed: one billion steps per second (an illustrative round number). Without JavaScript: at n = 1,000,000 an O(n) job takes 0.001 seconds, an n log n job 0.02 seconds, an n² job 1,000 seconds (about 17 minutes), and a 2n job would take far longer than the age of the universe. Even at n = 60, a 2n job needs about 36.5 years at a billion steps per second. That wall is the difference between an algorithm and a method that works in principle. Algorithms (34/24) is a whole course on getting from the right side of this table to the left; Theory of Computation (34/29) asks which problems can never be moved over. What a graduate just sees Any decision, however tangled, is AND, OR and NOT; a processor is a pile of truth tables. When you count two overlapping groups, subtract the overlap once. Order matters means n!/(n−k)!; order doesn't matter means divide by k!. More items than boxes means some box holds two: collisions are guaranteed, not unlucky. Induction is dominoes: base case plus step proves infinitely many cases; a loop invariant is the same. To prove something is impossible, assume it and chase the contradiction. Graphs are dots and links; edge ends add to twice the edges; a tree has one fewer edge than nodes. A remainder is a clock: mod wraps numbers into slots, and a check digit is a remainder that catches typos. Growth shapes (log, linear, n log n, squared, exponential) decide what is feasible far more than hardware does. Where it shows up next Algorithms (34/24) and Data Structures (34/23): induction proves them correct, big-O ranks them, graphs and trees are their raw material. Computer Architecture (34/25): gates, adders and the whole processor are applied logic. Databases (34/28): sets, functions and relations are the model; hashing makes lookups fast. Theory of Computation (34/29): proofs by contradiction show some problems are unsolvable. Statics (34/10), Systems Engineering (34/22) and Machine Design (34/19): trusses as graphs, fault trees as logic, tooth counts as remainders. If you want to go deeper 📘 Kenneth Rosen, Discrete Mathematics and Its Applications (McGraw Hill; 8th edition). The most-assigned university text, with huge problem sets. 📘 Susanna Epp, Discrete Mathematics with Applications (Cengage; 5th edition). Slower and gentler on logic and proof. 📖 Richard Hammack, Book of Proof (free from the author, who is at Virginia Commonwealth University): the gentle route for learning alone, focused on how to write proofs. For a free full text aimed at computer scientists, see the open textbook for MIT's 6.042J below. 🌐 MIT OpenCourseWare 6.042J, Mathematics for Computer Science (Spring 2015): lectures, problem sets and a free textbook by Lehman, Leighton and Meyer. The takeaway Discrete mathematics is exact reasoning about things you can count. Logic turns decisions into circuits, counting tells you what is possible, proof tells you what must be true for every case, graphs model connection, remainders give clocks and check digits, and growth rates tell you what will ever finish. Try this: check an ISBN on the back of a book yourself, weighting its digits 1, 3, 1, 3 and adding them. The total should end in 0. Then in the growth widget above, set n to 40 and then to 60, and watch the 2n job go from minutes to years while the n² job barely moves. Sources & Further Reading Sources. Logic, counting, induction, graphs and modular arithmetic are standard textbook content (Rosen; Lehman, Leighton and Meyer); every number shown was recomputed in code. Boole, An Investigation of the Laws of Thought (1854), and the later history of Boolean algebra: Wikipedia, "The Laws of Thought". Shannon, "A Symbolic Analysis of Relay and Switching Circuits" (MIT master's thesis, 1937). Euclid, Elements IX.20 (D. Joyce's commentary). Dirichlet and the pigeonhole principle (1834): Wikipedia, "Pigeonhole principle". ISBN-13 check digit: Wikipedia, "Check digit" and the ISBN agency rules. Age of the universe, about 13.8 billion years: NASA, from the Planck 2018 results. Go deeper. The books and course above. Step 4. Foundations: What Mathematics Stands On ----------------------------------------------- Why: Sets, infinity and the axioms: what mathematics stands on, and its famous limits. Sets, logic and infinity: the three things every proof leans on, how they let you reach certainty about the endless, and the famous places where they run out. Ask a child for the biggest number they know, then say "plus one". You have just done mathematics. You did not check every number. You gave a short argument that works for all of them, and no list could ever match it. That move, certainty about something endless from a few steps of reasoning, is what a first mathematics course is really about. It is also a little frightening, because it asks what the steps are allowed to be. What counts as a legal move? What are numbers made of? Is there a largest infinity? Around 1900 mathematicians found that the loose answers they had used for centuries produced actual contradictions, and rebuilt the ground floor. What they built, and the discovery in 1931 that the building can never be finished, is what this course teaches. A graduate does not carry the axioms around. A graduate carries a feel for what a proof is, for which statements are slippery, and for the fact that "infinite" is not one thing. The course in one box Who takes itEvery mathematics major, in year 1 or early year 2, usually as an "introduction to proof" course (Cambridge's first-year Numbers and Sets is a classic shape). Computer science majors meet a lighter version as discrete mathematics. Logic and set theory then return as electives for people who want to go further. What it is forLearning the rules of the game (sets, logical statements, proof) so that every later course can be trusted, and learning where the rules stop. Comes afterDiscrete Mathematics (34/08). Leads toReal Analysis (34/72) and Abstract Algebra (34/73), and through them Topology (34/76), Number Theory (34/75) and Complex Analysis (34/74). What this piece gives youYou will not be able to write a formal set-theory derivation. You will know what a proof by contradiction feels like, why Cantor's diagonal argument works, why "the set of all sets" is not allowed, and what Gödel actually showed. Easier first reads: Infinity Comes in Sizes (12/16) and Gödel's Incompleteness Theorems (12/08). This one has you build the arguments yourself. Everything is a collection: sets A set is a collection of things, and the only question you may ask about a set is which things are in it. Order does not matter, repeats do not matter. {1, 2, 3} and {3, 2, 1, 1} are the same set. That sounds too thin to build anything on, yet by 1900 almost all of mathematics had been rewritten in the language of sets: a function is a set of input-output pairs, a number can be a set (zero is the empty set, one is the set containing the empty set, and so on), a shape is a set of points. The first surprise is how fast sets multiply. A subset is a collection you can form by picking some of a set's elements. For each element there are two choices, in or out, and the choices are independent. So a set with n elements has 2n subsets Five elements give 32 subsets; ten give 1,024; a mere 30 give over a billion. The collection of all subsets of S is the power set of S, and it will matter again when we reach infinity. Switch elements in and out below; each choice of in/out is a binary number, which is why the count is a power of two. Interactive · Build a subset Elements in the full set Without JavaScript: a set with 4 elements has 2 × 2 × 2 × 2 = 16 subsets, including the empty set and the whole set. With 6 elements there are 64. Logic: "for all" and "there is" do not commute A proof is a chain of statements, so the first skill is reading one exactly. Two phrases carry most of the weight. "For all" (∀) claims something about every member; one counter-example kills it. "There exists" (∃) claims at least one member works; one example proves it. And the order you write them in changes the meaning. "Everybody loves somebody" is: for every person, there is someone they love. "Somebody is loved by everybody" is: there is one person, whom all love. The first can be true while the second is false, if everyone loves a different person. The reverse never happens. This is the exact trap in the definition of a limit (next course): "for every ε there is a δ" is not the same as "there is a δ that works for every ε", and confusing them is how false proofs happen. Two more habits. To negate a statement, flip the quantifiers and negate the end: the opposite of "everybody loves somebody" is "somebody loves nobody". And an implication "if P then Q" is only broken by P true and Q false; it is equivalent to its contrapositive, "if not Q then not P" ("if the grass is dry, it did not rain"). Many proofs are easier backwards. Make your own relation below. Interactive · Who loves whom? Everyone loves the next person Everyone loves Dee Nobody loves anybody Rows love columns. Press a cell to change it. Without JavaScript: if Ann loves Bo, Bo loves Cy, Cy loves Dee and Dee loves Ann, then everybody loves somebody, but nobody is loved by everybody. If all four love Dee, both statements are true. Proof by contradiction: the biggest prime does not exist The most powerful single move in mathematics is to assume the opposite of what you want and watch it fall apart. Two proofs, both over 2,000 years old, show how it feels. Euclid gave the first in his Elements; the second is traditionally credited to the early Greek mathematicians. Infinitely many primes. Suppose, for contradiction, you had a complete list of primes. Multiply them all together and add 1; call it N. Divide N by any prime on your list and the remainder is 1, because the product part divides evenly. So no prime on the list divides N. But every number above 1 has some prime factor (that is the quiet fact the proof leans on), so a prime outside your list exists. The list was not complete. The trick is the "+1": it manufactures a number your list cannot reach. Note that N itself need not be prime; the proof only says a new prime divides it. The square root of 2 is irrational. Suppose √2 = p/q in lowest terms. Then p² = 2q², so p² is even, so p is even, say p = 2r. Then 4r² = 2q², so q² = 2r² and q is even too. Both even contradicts "lowest terms". The trick is choosing lowest terms first, so that a shared factor of 2 is forbidden. Interactive · Try to complete the list of primes Pick the primes on your "complete" list. The page multiplies them, adds 1, and factors the result. Without JavaScript: the primes 2, 3, 5, 7, 11, 13 multiply to 30,030, so N = 30,031. It is not divisible by any of them; it equals 59 × 509, two primes your list missed. Infinity comes in sizes: Cantor's diagonal Two sets are the same size if you can pair their elements one to one, with none left over on either side. That is how a child checks that every guest has a chair. Applied to infinite sets it gives strange results: the even numbers pair with all the counting numbers (2n with n), so there are "as many" evens as numbers. A set you can list as a first, second, third... item is called countable. The whole numbers, the integers and even the fractions are countable. In 1891 Georg Cantor published a short argument that the real numbers are not. Take any supposed list of infinite sequences of 0s and 1s (think: which numbers are in each set). Build a new sequence by going down the diagonal and flipping each entry: it differs from the first sequence in the first place, from the second in the second place, and so on. It cannot be anywhere on the list. The trick is making the new object disagree with the n-th item at the n-th place, so it differs from everything at once. Read each row of the grid as a subset of {1, ..., n}, and the argument becomes Cantor's theorem: no list of subsets of S, indexed by the elements of S, can contain every subset. The missing one is D = {x : x is not in its own row}. That works for any set at all, so the power set is always strictly bigger, and there is no largest infinity. The proof is the same one you can run on a finite grid. Interactive · The diagonal always escapes Size of the grid Shuffle the rows Each row is a subset of {1..n}: a filled cell means that number is in it. Press cells to edit. The bottom row is the diagonal, flipped. Without JavaScript: write any 3 rows of 3 bits. Flip the diagonal. The new row differs from row 1 in column 1, from row 2 in column 2, from row 3 in column 3, so it is not any of them, however you filled the rows. Cantor's names for the sizes: the countable infinity is ℵ0 ("aleph-null"); the reals have size 2ℵ0, which is bigger. Whether anything sits between them is the continuum hypothesis, and we will get to what happened to that question. Russell's paradox and the axioms Early set theory allowed any rule to define a set: "the set of all things that are red", "the set of all sets". Around 1901 Bertrand Russell asked about the set R of all sets that do not contain themselves. Is R a member of itself? If yes, then it is a set that contains itself, so by its own rule it should be out. If no, it is a set that does not contain itself, so it should be in. Either way, a contradiction. It is the barber who shaves exactly those men who do not shave themselves: who shaves the barber? Interactive · Who shaves the barber? The rule: the barber shaves every man who does not shave himself, and nobody else. Guess, then test. The barber shaves himself The barber does not Pick one. Without JavaScript: if the barber shaves himself, the rule says he shaves only men who do not, so he must not. If he does not, the rule says he must. There is no such barber, and there is no such set. Gottlob Frege, who had just finished the first great attempt to base arithmetic on logic, received Russell's letter at the worst moment. The repair that most of mathematics now uses is Zermelo–Fraenkel set theory (ZF, or ZFC with the axiom of choice). Zermelo's 1908 system replaced "any rule makes a set" with a safer one, separation: given a set A you may carve out the members satisfying a rule, but you cannot conjure a set out of thin air. Then {x in A : x not in x} is fine; it just turns out not to be a member of A. Fraenkel and Skolem sharpened the system in 1922 and added replacement. Its main ingredients, in plain words: AxiomWhat it lets you do ExtensionalitySets with the same members are the same set. Pairing, UnionForm {a, b}; gather the members of members. Power setAll subsets of a set form a set. InfinityAn infinite set exists (the counting numbers). Separation, ReplacementCarve out by a rule; swap members for their images. FoundationNo set contains itself, and no endless descending chain of memberships. ChoiceFrom any family of non-empty sets you can pick one from each. The axiom of choice is the one that has history. It is needed for many theorems (every vector space has a basis) and also gives weird ones, like the Banach–Tarski paradox of 1924, which cuts a ball into pieces that reassemble into two balls the same size. The pieces are not measurable, so nothing physical is violated. Most mathematicians accept it; constructive mathematicians, who insist on explicit constructions, do not. A graduate knows which of their proofs use it. What the rules cannot settle: Gödel and the continuum David Hilbert hoped for a single formal system strong enough for all of mathematics, provably free of contradiction, and able to decide every statement. In 1931 Kurt Gödel showed that this cannot be had. His first incompleteness theorem: any consistent system that can express basic arithmetic, and whose axioms can be listed by a computer program, has true statements it cannot prove. His second: such a system cannot prove its own consistency. The sketch has three steps, and the first is the one to see. The trick is to turn statements into numbers. Give each symbol a code, and encode a formula by raising successive primes to those codes. Now a statement about formulas is a statement about numbers, which the system can express. Second, with some work, "this number codes a proof of that formula" becomes an arithmetic statement. Third, build a sentence G that says, via the coding, "I am not provable". If the system proves G, it proves something false (assuming it is sound). If it does not, then G is true and unprovable. Try the coding yourself. Interactive · Turn a formula into one number UndoClearTry: S0 = S0 Without JavaScript: with the codes 0→1, S→2, +→3, =→4, the formula "0=0" is 21 × 34 × 51 = 810. Factor 810 and you can read the formula back. Gödel's result did not make mathematics unreliable. It said the foundations are never "finished". And it has a concrete sibling. The continuum hypothesis says nothing lies between the size of the counting numbers and the size of the reals. Gödel showed in 1940 that ZFC cannot disprove it (assuming ZFC is consistent); Paul Cohen showed in 1963, with a new method called forcing, that ZFC cannot prove it either. Set theorists still disagree about what that means: some hope a compelling new axiom will settle it, and others think it has no single true answer. As far as anyone can tell, the answer is not in the axioms we have. Two more statuses so you can tell open from closed. Closed: the incompleteness theorems and the independence of CH are proved. Open: whether any natural new axiom decides CH. And the earliest question we asked, whether ZFC itself is consistent, cannot be proved inside ZFC (if it is consistent), by Gödel's second theorem. What a graduate just sees A statement with "for all" is killed by one counter-example; one with "there exists" is proved by one example. The order of the two changes the meaning. To prove "if P then Q" you may prove "if not Q then not P"; to prove something never happens, assume it does and chase the consequence. A subset is an in/out choice for each element, so a set of n things has 2n subsets. "Infinite" is not one size. Pairing things one to one is the test, and the diagonal beats any list. "The set of everything satisfying X" is dangerous. Carve from a set you already have. Every proof starts from something assumed. The honest questions are which axioms, and what follows. There are statements, true or not, that a given system cannot settle, and that is a theorem, not a failure of effort. Where it shows up next Real Analysis (34/72): the ε–δ definition is nested quantifiers, and the real numbers are built from sets of rationals. Abstract Algebra (34/73): a group is a set with an operation, and everything is proved from axioms in the style you just met. Topology (34/76): a space is a set with a chosen family of subsets, and the axiom of choice shows up as a real theorem (Tychonoff's). Computer science: the diagonal argument reappears as Turing's proof that no program can decide whether every program halts. The same trick, applied to programs rather than numbers. Practice: proof assistants like Lean and Coq check proofs against a fixed foundation, exactly the "legal moves" idea made mechanical. If you want to go deeper 📘 Textbook. Richard Hammack, Book of Proof. The standard free first text on proof, sets and logic, offered online by the author. 📘 Textbook. Herbert Enderton, Elements of Set Theory (Academic Press, 1977). The classic next step into axiomatic set theory, if you want the real ZF development. 📘 Gentler. Agustín Rayo, On the Brink of Paradox (MIT Press, 2019). Puzzles from infinity to Gödel's theorem, with almost no formal prerequisites. 🌐 Free course. MIT OpenCourseWare 24.118 Paradox and Infinity (Spring 2019, taught by Agustín Rayo): infinities, paradoxes, computability and Gödel, built on his book. The takeaway Mathematics rests on three things you can now see: sets as the raw material, logic with its careful "for all" and "there exists", and proof as the only way to reach certainty about the endless. They explain the surprises (more than one infinity, a set that cannot exist) and the limit (no finite list of rules decides everything). Try this: this week, take any "always" or "never" claim you hear ("nobody reads anymore") and negate it exactly. Notice that the negation only needs one example. Sources & Further Reading Sources. Set counting, quantifier logic, Euclid's primes argument, the √2 proof and Cantor's diagonal/Cantor's theorem are standard textbook mathematics (Hammack; Enderton). Cantor's diagonal paper: 1891. Russell's paradox c. 1901, Zermelo's 1908 axioms using separation, and Fraenkel and Skolem's 1922 addition of replacement: Stanford Encyclopedia of Philosophy and the MacTutor biographies. Gödel 1931 (incompleteness); Gödel 1938–40 (CH consistent with ZFC); Cohen 1963 (CH independent, forcing): standard accounts; sources differ slightly on Gödel's exact year (announced 1938–39, monograph 1940). Banach–Tarski 1924. Course: MIT OCW 24.118 (Spring 2019). Every number the interactives show was computed in node: 2n subsets for n=1..6; 2·3·5·7·11·13+1 = 30031 = 59×509; 810 = 2×34×5. 🌐 MIT OCW 24.118 Paradox and Infinity 📘 Rayo, On the Brink of Paradox 📘 Hammack, Book of Proof Step 5. Programming Fundamentals: Instructions, State and Taking Things Apart ----------------------------------------------------------------------------- Why: Mathematicians experiment with code before they prove. A computer can't guess what you meant. Everything in a first programming course is a way of saying it exactly enough, and of working out why you didn't. Tap "sort by price" and a list of a thousand items rearranges before you've lifted your finger. Somewhere, a person wrote down steps so exact that a machine with no judgment, no memory of yesterday and no idea what a "price" is could do it perfectly, a thousand times over. That is the whole trade. A programmer isn't someone who knows a language, they're someone who can state a task so precisely that nothing is left to guess. And since people are bad at being precise on the first try, the other half of the skill is finding out what you actually said, as opposed to what you meant. Mechanical and aerospace engineers use the same habits to simulate a wing before it's built; computer scientists use them to build every other subject on the degree. Python and MATLAB are the common first languages for engineers, and this piece uses Python-style code. The ideas carry to every language. The course in one box Who takes it: first-year students of Computer Science (usually their very first course) and Mechanical & Aerospace Engineering (often in MATLAB or Python). What it's for: telling a machine what to do exactly, and finding out when you didn't. Comes after: nothing; it has no prerequisites. Leads to: Data Structures (34/23), Computer Architecture (34/25) and Software Engineering (34/31) on the computing side; Differential Equations (34/03), Dynamics (34/12) and Control Systems (34/20) on the engineering side, all of which are solved on a computer in practice. Honest line: you won't be able to ship an app after this. You will be able to read ten lines of code, predict what they do, and make a physics model in a loop. A program is instructions plus state Strip away the syntax and a program is two things: a list of instructions, and the state, the current values of all its named boxes. Each instruction reads the state and changes it a little. Running the program is just that, one step after another, and the answer is whatever state is left (or printed) at the end. The graduate habit is to run the program in their head: keep a small table of variable values and update it line by line. Below is a tiny interpreter that does it visibly. Press Step. Then edit the program: change the 6 in the Collatz example, or write your own with =, +=, if/else, while, for … in range(…) and print. Interactive · Step through a program Add 1 to 5 Collatz steps Count down by 3 The program (edit me) StepRun to the endStart again A real mini-interpreter, written for this page. It stops after 400 steps, in case you write a loop that never ends. The first program adds 1 + 2 + 3 + 4 + 5 and prints 15. The Collatz one halves even numbers and triples-plus-one odd ones until it reaches 1: starting from 6 it takes 8 steps. Nobody knows if every starting number reaches 1, and yet the program is five lines long. That's what "simple instructions, deep behaviour" feels like. Variables and types: what a number is made of A variable is a name for a box in memory. A type says what kind of thing is in the box, and therefore what you may do with it: you can add two numbers, join two pieces of text, but adding "3" and 4 is an error or a surprise. Types exist because the machine stores everything as patterns of bits, and the pattern means nothing without the type. The box has a size too. A signed 16-bit integer holds −32,768 to 32,767, and nothing more. Decimals are stored as floating point, binary fractions of limited precision, so 0.1 can't be stored exactly and 0.1 + 0.2 gives 0.30000000000000004. On 4 June 1996 the first Ariane 5 rocket veered off course and broke up about 37 seconds after lift-off, a loss of more than US$370 million. The investigation traced it to the guidance software, reused from Ariane 4: a 64-bit floating-point value (the horizontal bias) was converted to a 16-bit signed integer, and on the faster rocket it didn't fit. The failure shut down both inertial units. A number too big for its box was enough. Interactive · Does it fit? 8 bits 16 bits 32 bits Number to store Ariane's code reportedly raised an error on overflow; some systems wrap silently instead, which is shown here. Conditionals and loops: choosing and repeating With state and instructions, only two more ideas are needed to compute anything: choose (if something is true, do this, else that) and repeat (while something is true, or for each value in a range). Together they let ten lines do work that would take ten million lines written out. The classic trap is in the edges. In Python's range(1, 10) the loop starts at 1 and stops before 10, so it runs 9 times, not 10. Off-by-one errors are the "fencepost" mistake: a fence of 10 sections needs 11 posts. Try the bounds yourself. Interactive · Edit the loop Add up i Add up i² Just count Start Stop (never reached) Step With the defaults, range(1, 11) runs 10 times and adds up to 55. Make the step negative and the start bigger than the stop to count down. Set the start above the stop with a positive step and the body never runs at all, which is perfectly legal and a common source of silent bugs. Functions and recursion: naming a piece, then calling it again A function packages some instructions under a name, takes inputs, and gives back an output. That is decomposition, the central skill of engineering of any kind: break a big problem into pieces small enough to understand and test alone, give each a name, then build on the names. The tracer above could be one function; so could braking distance. Recursion is a function that calls itself on a smaller version of its problem, until it reaches a case it can answer directly. The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, …, each the sum of the previous two) have a one-line recursive definition. Run it naively and the machine re-solves the same sub-problems again and again. Interactive · Count the calls Naive Remember answers (memo) Compute fib(n), n = Time it on this device Naively, fib(5) makes 15 calls, fib(20) makes 21,891, and fib(30), whose answer is just 832,040, makes 2,692,537. Remembering answers brings fib(30) down to 59 calls. Same answer, a different algorithm, and the course after this one (Algorithms, 34/24) is the study of exactly that difference. Data: lists and dictionaries Most programs aren't about single numbers but collections. A list is an ordered row of values, found by position (the third item). A dictionary maps a key to a value (a word to its count, a student ID to a name) and finds an entry by key without scanning. Choosing the right container is the first lesson of Data Structures (34/23). The difference is speed. To find a word in a list of n you may have to look at all n. A dictionary (usually built as a hash table) jumps almost straight to it, in roughly constant time on average, however large it is. Paste some text below and look a word up. Interactive · Count the words Textthe cat sat on the mat and the dog sat on the cat Look up a word Debugging is the scientific method Programs don't do what you meant; they do what you wrote. Finding the gap is science: look at the result, form a hypothesis ("the loop is skipping the last item"), make a prediction ("if I print the count here it will be one short"), run the experiment (print it), and revise. Guessing and changing things at random is the opposite, and it's how you add new bugs. The strongest move is bisection. If the code is a chain of steps and the result is wrong, check the value halfway along. If it's right, the fault is in the second half; if wrong, the first. Each check halves the suspects. In 1947 operators of Harvard's Mark II computer taped a moth found stuck in a relay into the logbook with the note "First actual case of bug being found" — a joke that only works because engineers already called faults "bugs". Interactive · Find the bug in as few probes as you can Start with x = 5. Slide to a step and probe the value there against what you'd get by hand. Look at x Probe hereBlame this stepNew bug Twelve suspect lines need at most four probes when you halve each time, because 2⁴ = 16 is at least 12. Checking from the top, one line at a time, can take twelve. Modelling: a physics simulation in a dozen lines Engineers model long before they build. Most physical laws give a rate of change (acceleration from forces, as in Physics I), and a computer can follow a rate forward in small steps: update the position using the velocity, update the velocity using the acceleration, repeat. That is the Euler method, and the loop is the whole simulation. x, y = 0.0, 0.0 vx, vy = 21.2, 21.2 # 30 m/s at 45 degrees dt = 0.1 # time step in seconds while y >= 0: x = x + vx * dt y = y + vy * dt vy = vy - 9.81 * dt # gravity changes vy only print(x) # about 93.9 metres Smaller time steps are more accurate and cost more. For the cannonball at 30 m/s and 45°, the exact range without air is 91.7 m. With a step of 0.5 s the simulation says 102.1 m, 0.1 s gives 93.9 m, and 0.001 s gives 91.8. Now add air drag, for which no tidy formula exists: the same loop still works, which is why engineers simulate. Interactive · A cannonball in code No air With air drag Launch speed Launch angle Time step Drag is modelled as a quadratic term with a baseball-like coefficient (0.007 per metre); a model, not a measurement. Readable code is a letter to a person A program is run by a machine once and read by people many times: the next engineer, the reviewer, you in six months. The well-known line from the preface of Structure and Interpretation of Computer Programs is: "Programs must be written for people to read, and only incidentally for machines to execute." The machine will accept either version below. Only one of them can be checked by a human. def f(a, b): return (a / 3.6) ** 2 / (2 * b * 9.81) def braking_distance(speed_kmh, friction): speed = speed_kmh / 3.6 # convert to metres per second return speed ** 2 / (2 * friction * 9.81) Both give 14.05 m for 50 km/h and a friction of 0.7, the braking distance of Physics I. Only the second tells you what it means, and so lets a reader spot a wrong constant. Good names, small functions and comments that say why are the cheapest debugging tools there are. People disagree on how much structure is enough: some teams favour heavy up-front design, others short cycles of build, test and revise; Software Engineering (34/31) covers both camps. What a graduate just sees A program is instructions plus state; to understand it, track the variables line by line. Every value has a type and a size, and a number too large for its box is a real way to lose a rocket. Loops run until their stop value, not through it: watch the edges. Break a problem into named functions you can test one at a time. A function that calls itself can be elegant and wildly wasteful; counting calls shows which. The right container (list or dictionary) can be the difference between instant and never. Debugging means hypotheses and experiments; halve the suspects each time. Simulation is a rate of change plus a loop, and smaller steps cost more for less error. Code is read far more often than it is written. Where it shows up next Data Structures (34/23) and Algorithms (34/24): the list-versus-dictionary and naive-versus-memo contrasts above, measured properly. Computer Architecture (34/25): the fixed-size boxes and overflow are the hardware's registers; instructions plus state is literally how a processor works. Software Engineering (34/31): decomposition, testing and readable code, scaled to teams and years. Differential Equations (34/03), Dynamics (34/12), Control Systems (34/20): the Euler loop is the starting point of numerical solvers, vehicle simulators and the code that runs a controller. Machine Learning (34/32): training is a loop that nudges numbers until the error falls. If you want to go deeper 📘 Standard textbook. John Guttag, Introduction to Computation and Programming Using Python (3rd ed., MIT Press, 2021), the text behind MIT's introductory course, written for engineers and scientists, with modelling and data. 📘 Gentler, free. Allen Downey, Think Python (3rd ed., Green Tea Press / O'Reilly), free to read online at greenteapress.com. For the deeper "why", Structure and Interpretation of Computer Programs by Abelson and Sussman is free online from MIT Press. 🌐 Free course. MIT OpenCourseWare 6.0001 Introduction to Computer Science and Programming in Python (Fall 2016), or Harvard's CS50x (starts in C, then Python and SQL) and CS50P (Python only), free on OpenCourseWare. The takeaway A program is instructions acting on state. Variables, types, choices, loops and functions are how you say it exactly; lists and dictionaries are how you hold data; debugging is hypothesis and experiment; and a simulation is a rate of change inside a loop. The graduate's real skill is reading code, predicting it, and taking a big problem apart. Try this: take any small thing you do by hand, like splitting a bill or converting recipe units, and write it as exact steps for a friend to follow without any judgment. Then watch where they get stuck: those are your bugs. Sources & Further Reading Sources. Ariane 5 flight 501 (4 June 1996; 64-bit floating-point to 16-bit signed integer conversion overflow; about 37 seconds; more than US$370 million): Wikipedia, "Ariane flight V88", which summarises the Inquiry Board's report. The Mark II moth (9 September 1947, logbook note "First actual case of bug being found", now at the Smithsonian) from the Computer History Museum and JSTOR Daily, "The bug in the computer bug story", which notes the term was already in use. The SICP quotation from the preface of Abelson & Sussman, Structure and Interpretation of Computer Programs (MIT Press, 1985). CS50x language order from cs50.harvard.edu/x; Think Python 3rd ed. from greenteapress.com. Computed and checked in node, including by running the page's own interpreter on its example programs: 15; 8 Collatz steps; −2; 40,000 wraps to −25,536 in 16 bits; fib call counts 15, 177, 21,891 and 2,692,537 (and 2n−1 with a memo); projectile ranges 91.74 m exact and 102.1, 93.9, 91.8 m for steps of 0.5, 0.1 and 0.001 s; 14.05 m braking distance. 🌐 MIT OpenCourseWare: 6.0001 🌐 Harvard CS50x and CS50P 📘 Think Python, 3rd edition (free online) 📘 Guttag, Introduction to Computation and Programming Using Python, 3rd ed. (MIT Press) 🌐 JSTOR Daily: the bug in the computer bug story Step 6. Multivariable Calculus: Calculus on a Landscape ------------------------------------------------------- Why: Calculus in many dimensions, the gateway to geometry and physics. A raindrop on a hillside picks the steepest way down without thinking. The arrow it follows is the same one that trains every neural network and drives heat through a metal plate. Stand on a hillside with a map. Height depends on two things at once: how far east you are and how far north. Single-variable calculus handles one input at a time. The hillside needs a new question: of all the directions I could step, which one rises fastest? Almost nothing real depends on one number. Temperature in an engine block depends on position in three dimensions. The error of a language model depends on billions of adjustable weights. Air pressure depends on place and time. This course takes the slope-and-area ideas of Calculus I (34/01) and lets them live in more than one dimension. Surprisingly little new is needed: one new arrow, the gradient, and one new accounting rule, the idea that what flows out of a region is what is made inside it. The course in one box Who takes it: second-year Mechanical & Aerospace Engineering students; Computer Science students meet it in year 4 when machine learning needs it. What it is for: calculating change and totals when many things vary at once. Comes after: Calculus I (34/01). Leads to: Physics II: Electricity & Magnetism (34/07), Fluid Mechanics (34/15), Machine Learning (34/32), and through them Heat Transfer (34/16) and Propulsion (34/21). Honest line: you will not be able to grind through a surface integral after this. You will see why a gradient points uphill, why training an AI is "just" rolling downhill, and what the big theorems say in plain words. Two inputs make a landscape, and a partial derivative is one slope A function of two inputs is a surface: height above each point of a map. Engineers draw it the way hikers do, with contour lines: closely spaced lines mean steep ground, widely spaced lines mean gentle ground. To ask "how steep?" you must say in which direction. Walk due east and note the slope: that is the partial derivative with respect to x, written ∂f/∂x. Hold east still and walk north: that is ∂f/∂y. The recipe is simple: treat every other variable as frozen and differentiate as before. ∂f/∂x = slope of f as only x changes, with y held still The landscape below has a tall hill near (1, 1) and a lower one near (−1.2, −0.8). Drag the point on the map (or use the sliders). The cyan arrow shows the slope eastward and the green arrow the slope northward; a leftward or downward arrow means the ground falls in that direction. Interactive · Walk the map East–west position x North–south position y At the starting point (−0.2, 0.3) the height is 0.684, the eastward slope +0.621 and the northward slope +0.226: the ground rises both ways, more steeply towards the east. The gradient points straight uphill Put the two partial slopes together as one arrow, east component first: that is the gradient, written ∇f. It has a beautiful property: it points in the direction of steepest ascent, and its length is how steep that is. Step in any other direction and the slope is the gradient's length times the cosine of the angle between your step and the arrow. Straight along it, cosine is 1: the most you can get. Sideways to it, cosine is 0: you walk along a contour and stay level. slope in direction u = ∇f · u = |∇f| cos(angle) Two consequences follow. The gradient is always perpendicular to the contour line through that point, which is why water runs across contours, not along them. And the same arrow governs heat: in Fourier's law, heat flows down the temperature gradient, from hot to cold, at a rate proportional to its steepness. Many diffusion laws have this shape: flow follows the negative gradient. Interactive · Which way is uphill? Direction you step (0° = east, 90° = north) Turn to the gradient Turn the pink direction until the slope is largest: it lines up with the orange arrow. Turn it 90° from the arrow and the slope is zero. At the very top of a hill the gradient shrinks to nothing, which is the multivariable version of "zero slope means a peak" from Calculus I. Rolling downhill is how a network learns Now flip the sign. A machine-learning model has adjustable numbers (weights), and a loss measures how wrong it is on the training data. The loss is a landscape over the weights, with one dimension per weight. To learn, take a small step against the gradient, so downhill, then recompute and repeat. This is gradient descent, which Augustin-Louis Cauchy proposed in 1847 for solving equations, long before computers. The chain rule from Calculus I is what lets the gradient be computed layer by layer, in the method called backpropagation, published by Rumelhart, Hinton and Williams in Nature in 1986. A model like GPT-3 (2020) has 175 billion weights, so its landscape has 175 billion dimensions, yet the rule is the same arrow. new position = old position − (step size) × ∇(loss) The step size matters, and you can feel why. In the bowl below, one direction is twelve times steeper than the other. Too small a step crawls; just right is fast; too large and each step overshoots the valley floor by more than it started and the loss explodes. For this bowl, steps above 1/6 (about 0.167) diverge. Interactive · Learning rate Too small Good Zig-zag Too big Step size (learning rate) Steps taken Real training uses refinements (momentum, adaptive step sizes, random mini-batches), but all of them are ways of coping with exactly this picture: a long narrow valley where the steepest direction is not the direction of the destination. Double and triple integrals add up a landscape's worth Integrals extend the same way. A single integral adds thin slices along a line. A double integral adds tiny patches over an area: if each patch has a density (kilograms per square metre), the sum is the plate's mass. A triple integral does the same over a solid, with density in kilograms per cubic metre. The recipe is slice, multiply, add, repeated once per dimension. mass = sum over all pieces of (density × piece size)  =  ∬ ρ dA The same sums also give the centroid, the balance point: weight each position by its piece's mass and divide by the total. Engineers use it constantly: the centre of mass of a rocket, a car or an aircraft decides whether it is stable. Try a plate 2 m long and 1 m wide whose density rises along the length. Interactive · Where does the plate balance? Density rises along the length: a (kg per m² per m) Density rises across the width: b The density here is 1 + ax + by kg/m². With a = 3 and b = 0, the plate's mass is 2 + 2×3 = 8 kg and it balances at x = 1.25 m, shifted from the middle (1 m) towards the heavy end. A vector field puts an arrow on every point Wind on a weather map, water in a pipe, the pull of a magnet: each attaches an arrow (a direction and strength) to every point in space. That is a vector field. Two numbers computed from the field's partial derivatives tell you most of what it is doing locally. Divergence: is the field spreading out from here, or converging? A tap under water is a source; a drain is a sink. A positive divergence means a small blob of fluid is expanding. Curl: is the field spinning? Put a tiny paddle wheel in the flow. If it turns, the curl is not zero, and the sign tells you which way. divergence = ∂vx/∂x + ∂vy/∂y    curl = ∂vy/∂x − ∂vx/∂y Pick a field and let a round blob of fluid (grey dashes show where it started) be carried along. You will see that a source inflates the blob without turning it, a whirlpool turns it without changing its area, and a saddle stretches it one way and squeezes it the other while keeping its area. Interactive · Drift a blob through a field Source Whirlpool Shear Saddle Time elapsed Divergence and curl are the two words in Maxwell's equations of electromagnetism (Physics II, 34/07) and in the equations of fluid flow (Fluid Mechanics, 34/15). Spreading and spinning are the two things a field can do locally, besides moving along as a whole. What flows out of a region is what is made inside Here is the idea behind the three big theorems, in the language of a bathtub. If water pours out through the boundary of a region, then some taps inside must be producing it (or the level inside must be falling). Add up every tiny source and sink inside and you get the net flow out through the boundary. Nothing more is needed. net flow out through the boundary = total divergence inside That is the divergence theorem, the three-dimensional version of the statement. Green's theorem is the flat version (the name honours George Green, whose Essay of 1828 contained the related surface-to-volume formula), and Stokes's theorem relates the spinning of a field inside a surface to the flow around its edge. All three say the same kind of thing: a sum over a boundary equals a sum of local changes inside. It is why one can measure a rotating machine from outside and why conservation laws can be written either as "this region's total changes by what crosses its walls" (integral form) or as an equation about each point (differential form). Interactive · Count the flow two ways Source Cubic Source in, sink out Steady wind Circle radius Circle centre, left or right The first number adds up the field's push through the circle itself. The second never looks at the circle's edge: it adds the divergence in every patch inside. They agree for every field, radius and position. For the plain source (x, y), the divergence is 2 everywhere, so a unit circle encloses 2 × π = 6.283 units of production, and exactly 6.283 flows out through its rim. What a graduate just sees A slope needs a direction; a partial derivative is the slope with every other input held still. The gradient points straight uphill, its length is the steepness, and it is perpendicular to the contour. "Downhill" is the whole idea behind training a model: step against the gradient, and mind the step size. Heat, and many other things, flow down a gradient from high to low. A double or triple integral is slice, multiply, add, once per dimension; mass and balance point come from it. A field can only spread (divergence) or spin (curl), locally. What leaves a region through its wall is exactly what its insides produce. Where it shows up next Physics II: Electricity & Magnetism (34/07): Maxwell's equations are statements about the divergence and curl of the electric and magnetic fields. Fluid Mechanics (34/15): conservation of mass is a divergence equation, and the divergence theorem turns "what crosses the walls of this control volume" into "what happens inside it". Heat Transfer (34/16): conduction is heat flowing down the temperature gradient; the heat equation is the gradient and divergence together. Machine Learning (34/32): training is gradient descent on a loss landscape with millions or billions of dimensions. Mechanics of Materials (34/11) and Dynamics (34/12): centroids and moments of inertia are integrals of exactly the kind you added up above. If you want to go deeper 📘 Textbook: Stewart, Clegg and Watson, Calculus: Early Transcendentals (9th ed.), chapters 14 to 16: the standard multivariable text, rich in examples. 📘 Textbook: Jerrold Marsden and Anthony Tromba, Vector Calculus (6th ed., W. H. Freeman): the classic for the geometry of divergence, curl and the big theorems. ▶️ Gentler: Khan Academy's Multivariable Calculus course, which has videos with a strong visual feel, and Grant Sanderson's multivariable lessons. 🌐 Free course: MIT OpenCourseWare 18.02SC Multivariable Calculus, with lectures, notes and exercises. The takeaway With many inputs, a slope needs a direction. The partial derivatives are the slopes along the axes; the gradient joins them into one arrow that points uphill and measures how steep it is. Walk against it and you are doing gradient descent, which trains models with billions of weights and also describes how heat flows. Integrals extend to areas and volumes, giving mass and balance points, and for flows the whole subject rests on one bookkeeping rule: what leaves a region through its boundary is what its interior produces. Try this: on any hill, a park slope or a street, find the line along which a ball would roll: that is the negative gradient. Then notice that the ball's path crosses the contours at right angles. Sources & Further Reading Sources. Gradient descent: A.-L. Cauchy, "Méthode générale pour la résolution des systèmes d'équations simultanées", Comptes rendus 25 (1847), pp. 536–538; Claude Lemaréchal, "Cauchy and the gradient method", Documenta Mathematica, Extra Volume ISMP (2012). Backpropagation: Rumelhart, Hinton and Williams, Nature 323 (1986), pp. 533–536. GPT-3's 175 billion parameters: Brown et al., "Language Models are Few-Shot Learners" (2020, arXiv 2005.14165). Green's Essay of 1828 containing the theorem named after him: MacTutor biography and the essay itself. Computed in node: the landscape f = 2e−((x−1)²+(y−1)²)/1.5 + 1.2e−((x+1.2)²+(y+0.8)²)/1.0 and its analytic gradient (checked against finite differences, agreement to 3 × 10−10); gradient descent on ½(x² + 12y²), stable for step sizes below 2/12; plate mass and centroid by 3,200-cell sums against the exact formulas; blob area against ediv·t; circle flux against the divergence integral for four fields (agreement to 4 decimals). 🌐 MIT OpenCourseWare 18.02SC Multivariable Calculus 🌐 Khan Academy: Multivariable calculus 🌐 Documenta Mathematica, ISMP volume, which contains Lemaréchal's short history of gradient descent 📘 Stewart, Clegg and Watson, Calculus: Early Transcendentals, 9th ed. (Cengage) 📘 Marsden and Tromba, Vector Calculus, 6th ed. Step 7. Differential Equations: Laws Written as Rates ----------------------------------------------------- Why: Differential equations: where mathematics meets every science. A cup of coffee cools, a capacitor charges, a car bounces over a bump, a fish stock collapses. Each follows a rule that says how fast things change, not where they will be. Solving it is the whole course. Pour coffee and watch it cool. It loses heat fast at first, when it is far hotter than the room, and ever more slowly as it approaches room temperature. Nobody wrote down the temperature at every minute in advance. All you need is a rule: the hotter the cup is above the room, the faster it cools. That sentence, turned into an equation, is a differential equation, and it predicts the whole curve. This is the secret structure of physics. Nature rarely says "the position will be this". It says "the rate of change is that, given the state right now". Newton's second law is such a rule. So are the equations of electrical circuits, chemical reactions, populations, heat, and the flow of air over a wing. A differential equations course teaches how to read these rules and how to turn them into predictions, either exactly or step by step on a computer. The course in one box Who takes it: second-year Mechanical & Aerospace Engineering students. It is not on the Computer Science route in this series, but CS students meet the same ideas whenever they simulate, animate or train anything that evolves in time. What it is for: predicting how a system evolves when you only know the rule for its rate of change. Comes after: Calculus I (34/01). Leads to: Dynamics (34/12), Fluid Mechanics (34/15), Heat Transfer (34/16), Vibrations (34/17), Control Systems (34/20). Honest line: you will not learn the solution tricks that fill the textbook. You will see the three behaviours that recur everywhere (settling, oscillating, tipping) and why a simulation can lie to you. An equation about a rate hands you a direction at every point An ordinary differential equation, an ODE, is an equation that mentions a quantity and how fast it is changing. The simplest useful kind says the rate depends on how far the quantity is from a target: dy/dt = k (target − y) Read it aloud: the further I am from the target, the faster I move towards it. Coffee towards the room's temperature, a capacitor towards the supply voltage, a medicine level towards zero. The picture is a slope field: at every point of the plane the equation fixes the direction a solution must go through, drawn as a tiny segment. A solution is any curve that follows those segments the whole way, like a leaf carried along a stream. Different starting points give different curves, all flowing toward the target. Interactive · Follow the arrows Pull strength k Target value Starting value Notice that the segments get flatter as you approach the dashed line: the rate shrinks with the distance. That is why the curve approaches the target but never quite arrives. The exact solution is the target plus the starting gap times a decaying exponential, e−kt. The time constant: how fast a first-order system forgets The rule dy/dt = k(target − y) has one number that sums it up: the time constant, τ = 1/k. In one τ the system covers about 63.2% of the remaining gap; after about 4.6 τ it has covered 99%. Engineers read response speed from that single number. fraction of the gap covered after time t = 1 − e−t/τ In an electrical circuit, a resistor R in series with a capacitor C charges towards the supply with τ = R × C. A 10 kΩ resistor and a 100 µF capacitor give τ = 10,000 Ω × 0.0001 F = 1 second: after 1 s the capacitor holds 63.2% of the supply (3.16 V of 5 V), after 4.6 s, 99%. A cooling coffee follows the same curve; only the story and the units change. Interactive · Charge a capacitor Resistance R Capacitance C Notice what the sliders do: double either one and the curve stretches twice as wide, but keeps exactly the same shape. The same shape is why a thermometer takes a while to read a fever, and why a control engineer (Control Systems, 34/20) asks first: "what is the time constant?" Solving it step by step: Euler's method Most differential equations have no neat formula. The fall-back is to walk along the slope field in small steps. At the current point read the slope, move a short time h in that direction, and repeat. This is Euler's method, set out by Leonhard Euler in his Institutionum calculi integralis (1768), and it is the ancestor of every physics engine, weather model and circuit simulator. ynext = y + h × (the rate at y) Test it on a rule we can also solve exactly, dy/dt = −y, starting from 1. Each Euler step multiplies the value by (1 − h). Small steps follow the true curve e−t closely. But raise h and something stranger happens. Interactive · Euler versus the exact answer Step size h At h = 1 the first step lands exactly on zero. Beyond 1 the steps overshoot, and past h = 2 each step makes the number bigger in size, so the "answer" explodes even though the real one decays. That is numerical instability: a stepping rule has its own stability limit, and a simulation that ignores it will happily print nonsense. At h = 0.5 Euler gets 0.000244 at t = 6, where the true value is 0.00248: right shape, ten times too small. Smaller steps, or smarter methods (the Runge–Kutta family), fix that. Second order: the spring, the mass and the damper Newton's second law says force equals mass times acceleration, and acceleration is the rate of change of the rate of change of position. So a mass on a spring obeys a second-order equation: the second derivative of position x depends on position and velocity. m x″ + c x′ + k x = 0 The three terms are inertia (mass m), a damper that resists velocity (c) and a spring that pulls back with force proportional to displacement (k). Two numbers decide everything: the natural frequency, ω = √(k/m), and the damping ratio, ζ = c ÷ (2√(km)). ζ below 1, underdamped: it rings, swinging past rest and fading. ζ = 1, critically damped: the fastest return without overshoot. ζ above 1, overdamped: no swing, but a sluggish crawl home. Engineers tune for it. A door closer is aimed near critical damping so the door shuts without banging or bouncing. A shock absorber is a compromise: enough damping to stop the bouncing, not so much that the wheel can't follow the road. Interactive · Tune the damper No damping Light Critical Heavy Mass m Spring stiffness k Damping c With m = 1 kg and k = 25 N/m the natural frequency is 5 rad/s, or about 0.8 Hz. Setting c = 10 N·s/m gives ζ = 1, critical. With c = 2, ζ = 0.2 and the first swing past rest reaches 52.7% of the starting displacement on the other side. This same equation, with different symbols, describes the RLC circuit, a building in an earthquake and a robot arm: that is the next courses (Vibrations, 34/17, and Control Systems, 34/20). Equilibria: where things settle, and where they tip Often you do not need the whole curve, only the places where change stops: the equilibria, where the rate equals zero. Two questions follow. Where are they? And is each one stable (nudge it and it comes back) or unstable (nudge it and it runs away)? The answer is the slope of the rate curve at that point, from Calculus I: negative slope means stable, positive means unstable. A toy model shows why this matters. Fish regrow according to dy/dt = y(1 − y/100) per year (a standard logistic model), and a fleet takes a fixed catch H every year. For H = 20 there are two equilibria, at about 27.6 and 72.4 fish: the upper is stable, the lower unstable. Start just above 27.6 and the stock recovers to 72.4. Start just below it and the stock collapses to zero in a few years. Raise the catch above 25, the most the stock can regrow, and no equilibrium remains at all. Interactive · A fishery on the edge Catch 20, start 30 Catch 20, start 25 Catch 26 Fixed catch H per year Starting population The lesson generalises: a system can look healthy while it sits near an unstable tipping point, and a slow change in a parameter (here the catch) can make the stable state vanish suddenly. Bridges, power grids, aircraft and ecosystems are all analysed this way. The model is a classroom toy, not a description of any real fishery. Why physics is written in differential equations Why do laws come as rates? Because change is local. What a system does next depends only on what is happening here, now: the forces, the gradients, the current state. Newton's second law (second order in position), Maxwell's equations for electric and magnetic fields, the equations of heat flow and the equations of fluid motion all have this shape. Give the rule and the starting conditions and the future follows. Two kinds appear. An ordinary equation (ODE) has one changing variable, usually time: a pendulum, a circuit, a rocket's trajectory. A partial differential equation (PDE) has several, such as time and position: the temperature along a rod, the pressure in the air around a wing. The Navier–Stokes equations of fluid flow (Fluid Mechanics, 34/15) are PDEs so hard that the Clay Mathematics Institute named a question about them one of its seven Millennium Prize problems in 2000. Most real ones are solved on computers using the stepping idea above. A glimpse of PDEs: the heat equation Joseph Fourier wrote the heat equation in his Théorie analytique de la chaleur (1822). It says: the temperature at a point changes at a rate proportional to how much its surroundings, on average, are hotter or cooler than it is, which is the curvature of the temperature curve. ∂u/∂t = α ∂²u/∂x² A peak has negative curvature, so it cools; a dip has positive curvature, so it warms. Heat flows from hot to cold and the profile smooths out. The rod below is insulated at both ends, so the average temperature, the total heat, never changes, only its distribution. Fourier's great discovery (see the library's piece on the Fourier transform, 12/12) is that smooth wiggles of different sharpness die away at different rates: a wiggle five times sharper dies 25 times faster, because it decays like e−(n²π²)t. Interactive · Heat spreading along a rod Hot spot Half hot Gentle wave Sharp wave Time Time step, as a fraction of the stability limit Try the two waves at the same time. The gentle wave 1 + 0.8 cos(πx) has faded to 0.298 high at t = 0.1, matching the exact 0.8e−π²t. The sharp wave 1 + 0.8 cos(5πx) is gone almost at once, 25 times faster in the exponent. Then drag the time-step slider above 0.5 and watch the simulation explode: Euler's lesson again, now in a PDE. Real heat solvers (Heat Transfer, 34/16) must respect the same limit or use methods built to avoid it. What a graduate just sees A law about a rate is a direction at every point; a solution is a curve that follows those directions. First-order systems approach their target by a time constant: 63% in one τ, 99% in about 4.6 τ. Cooling, charging and decay are the same curve with different labels. A step-by-step simulation has a stability limit: too big a step creates growth that is not in the physics. Mass, spring and damper give three behaviours: ring, crawl, or the sweet spot at ζ = 1. Equilibria matter, and slope tells stable from unstable. Systems tip. Sharp features smooth out first in diffusion, and total heat is conserved. Where it shows up next Dynamics (34/12): every motion problem becomes an equation of the form above. Vibrations (34/17): the damped spring is the building block of everything that shakes, from engines to aircraft wings. Control Systems (34/20): a thermostat, cruise control or autopilot is a differential equation you shape with feedback; time constants and damping ratios are its vocabulary. Heat Transfer (34/16) and Fluid Mechanics (34/15): the heat equation and Navier–Stokes are PDEs; the stepping and stability ideas carry straight over. Computer science: physics engines in games, climate and weather models, and circuit simulators are loops of Euler-like steps; neural ODEs even treat a network as a flow. If you want to go deeper 📘 Textbook: William Boyce, Richard DiPrima and Douglas Meade, Elementary Differential Equations and Boundary Value Problems (12th ed., Wiley): the classic course text. 📘 Textbook: Steven Strogatz, Nonlinear Dynamics and Chaos (3rd ed., CRC Press): an unusually readable treatment of equilibria, stability and tipping. ▶️ Gentler: 3Blue1Brown's differential equations series, and Strogatz's Infinite Powers for the story of why calculus describes nature. 🌐 Free course: MIT OpenCourseWare 18.03SC Differential Equations, with video lectures, notes and problem sets. The takeaway Physics speaks in rates. A differential equation gives a direction at every point and a solution follows it. First-order systems approach a target with a time constant (63% in one τ). Second-order systems, from springs and masses, ring, crawl or sit at the sweet spot of critical damping. Equilibria are where change stops and slope tells stable from unstable. When no formula exists, you step along on a computer, but only small enough steps tell the truth: past a limit, a simulation blows up even though nature does not. Try this: take a hot drink and a thermometer (or just your hand) and note how long it takes to lose half its excess heat over the room. It will take about the same time again to lose half of what is left. That constant "half-life" is the time constant in disguise. Sources & Further Reading Sources. Euler's method: Institutionum calculi integralis, vol. 1 (1768); Encyclopedia of Mathematics, "Euler method". Newton's law of cooling originates in Newton's anonymous 1701 paper "Scala graduum caloris"; the modern differential form is not in the original (Wikipedia, "Newton's law of cooling", and history-of-science references). Fourier's Théorie analytique de la chaleur (1822). Millennium Prize problems announced by the Clay Mathematics Institute in 2000, Navier–Stokes among them. Computed in node: RC charging (τ = RC = 1 s for 10 kΩ and 100 µF, 63.2% at τ, 99.0% at 4.605τ); Euler at h = 0.5 gives 2.44 × 10−4 at t = 6 against the exact 2.48 × 10−3; spring closed-form solutions for the three regimes checked against a step-by-step integration (agreement to 5 decimals) and the first-swing overshoot e−πζ/√(1−ζ²) = 52.7% for ζ = 0.2; harvested logistic equilibria 50(1 ± √(1 − H/25)) = 27.64 and 72.36 for H = 20, with collapse after 4.3 years from a start of 25; the explicit heat scheme (100 cells, stable below 0.5) against the exact decay 0.8e−π²t = 0.2982 (numerical 0.2981) at t = 0.1. 🌐 MIT OpenCourseWare 18.03SC Differential Equations ▶️ 3Blue1Brown: differential equations 📘 Boyce, DiPrima and Meade, Elementary Differential Equations and Boundary Value Problems, 12th ed. (Wiley) 📘 Steven Strogatz, Nonlinear Dynamics and Chaos, 3rd ed. (CRC Press) 🌐 Newton's law of cooling (with the history of the law) Step 8. Real Analysis: Why Calculus Works ----------------------------------------- Why: Why calculus works: limits, continuity and completeness, proved. Calculus gave right answers for 150 years before anyone could say why. Analysis is the answer: the number line has no gaps, and "gets close" can be made exact. Your calculator says √2 is 1.41421356... and you trust it, because squaring that gives something extremely close to 2. But "extremely close" is a strange foundation. Newton and Leibniz built calculus on quantities that were "infinitely small but not zero", and a bishop, George Berkeley, mocked them in 1734 as "ghosts of departed quantities". The answers were right. The explanation was missing. Add a second discomfort. Rearrange the order of an infinite sum and you can change its value. Take a function that is smooth at every step of a construction and the limit can have a jump in it. Draw a curve with no gaps and it can still have no tangent at any point. Each of these was a shock in the nineteenth century, and a course called real analysis is where you learn why they happen and how to stay out of trouble. A graduate "just sees" that a limit is a promise you can keep for any tolerance, that the real line is solid in a precise sense, and that infinite processes need conditions before you may trust them. The course in one box Who takes itEvery mathematics major, in year 2 (MIT's 18.100 family; Cambridge's Analysis I in the first year). Physics and economics majors often take a lighter version. The course is where many students first feel what "proof" means. What it is forProving, from the properties of the real numbers alone, that the calculus you already know is correct, and finding where it breaks. Comes afterCalculus I (34/01) and Foundations: What Mathematics Stands On (34/71). Leads toComplex Analysis (34/74) and Topology (34/76), and it quietly underlies Differential Equations (34/03) and Numerical Analysis (34/78). What this piece gives youYou will not be able to work through a Rudin chapter. You will know what the ε–δ game is, why the rationals have holes, why some series cannot be reordered, and why a limit of continuous functions need not be continuous. The easier first read is Calculus: The Language of Change (12/11) and the first course of this series, Calculus I (34/01). This one asks why those answers hold. The real numbers have no gaps The rational numbers (fractions) are dense: between any two there is another. Yet they have holes. Euclid's argument, recalled in 34/71, shows no fraction squares to 2. Still you can walk towards the hole: 1, 1.4, 1.41, 1.414, ... each of these is a fraction whose square is a little under 2. Each also has a partner one last digit higher whose square is a little over 2. The gap between the pair shrinks by a factor of ten each time, and yet no fraction sits where they close in. The real numbers fill every such hole. That property is called completeness, and it can be stated in one line: every set with an upper bound has a least upper bound(the supremum: sup of {x : x² < 2} is √2, which is a real number but not a rational one) In 1872 Richard Dedekind and Georg Cantor each gave a construction of the reals that makes this true, so the number line is built rather than assumed. The trick of the whole subject is that this one property, plus the ordinary rules of arithmetic, is enough to prove everything in calculus. The rationals satisfy all the same arithmetic and fail only this, which is why calculus fails over the rationals: a continuous function on fractions can go from below zero to above zero without ever being zero. Interactive · Squeeze the hole Decimal digits kept Exact integer arithmetic, no rounding: both ends are fractions with the denominator 10k. Without JavaScript: 1.414 and 1.415 are fractions with 1.414² = 1.999396 < 2 < 2.002225 = 1.415². Add digits and the pair closes in on √2 = 1.41421356..., which is not a fraction. Each pair is an interval, each inside the last. The nested interval principle (a consequence of completeness) says that nested closed intervals always share a point. For fractions only, the shared point is missing; for reals, it is there. That is the whole difference. A limit is a game you always win Here is the definition that rescued calculus, mostly the work of Cauchy in the 1820s and Weierstrass in the 1860s. To say f(x) tends to L as x approaches a is to say you win this game. An opponent names any tolerance ε > 0 however small. You must answer with a distance δ > 0 so that every x within δ of a (but not equal to a) has f(x) within ε of L. If you can always answer, the limit is L. If the opponent has some ε you cannot answer, the limit is not L. Order matters here, exactly as in 34/71: for every ε, there is a δ, and the δ may depend on ε. A worked win for f(x) = x² near a = 2 (limit 4): we have |x² − 4| = |x − 2| · |x + 2|. If δ ≤ 1, then x is between 1 and 3, so |x + 2| < 5, and the product is under 5δ. So choose δ = min(1, ε/5). The trick is to bound the awkward factor first, then let the small factor do the work. Now play it. Choose a function, an opponent's ε, and your δ; the page tests your δ at 20,001 sample points and also hunts for the best δ. Then try the two functions that have no limit, and watch the opponent win however you play. Interactive · The epsilon–delta game x² near 2, claim 4 sin(x)/x near 0, claim 1 a jump at 1, claim 1 sin(1/x) near 0, claim 0 Opponent's ε Your δ Without JavaScript: for x² near 2 with ε = 0.1, δ = min(1, 0.1/5) = 0.02 wins. For the jump function (0 left of 1, 1 from 1 on) no δ wins against ε = 0.5, because there are always points just left of 1 where the value is 0. Note where the proof lives. You never "go to" a. You answer a question about distances, which are plain numbers, so no ghosts remain. Infinite sums need rules: the series you can reorder, and the ones you cannot A series is a sum with infinitely many terms, and it converges if its partial sums settle to a limit. A quick fact: if the terms do not shrink to zero it cannot converge. The converse is false, and the best example is the harmonic series 1 + 1/2 + 1/3 + 1/4 + ... It diverges. Proof sketch, due to Oresme in the 14th century: group the terms 1/3 + 1/4 > 1/2, then 1/5 + ... + 1/8 > 1/2, then the next eight terms, and so on. Every group adds at least 1/2, so you pass any number. The trick is grouping so each batch is compared to a fixed amount. Flip every other sign and it converges: 1 − 1/2 + 1/3 − 1/4 + ... = ln 2 ≈ 0.6931. Now the shock. Take exactly the same terms, none left out, and reorder them. In the 1850s Bernhard Riemann showed you can make the sum equal any real number you like. The reason: the positive terms alone add up to infinity, and so do the negative ones, while each term shrinks to zero. To aim at a target, add positive terms until you pass it, then negative terms until you drop below, and repeat. The overshoots get smaller because the terms do. Series that stay safe when reordered are the absolutely convergent ones, whose absolute values also sum finitely. That is the condition behind a lot of fine print in later courses. Interactive · Make the series equal what you want Target sum Terms used Without JavaScript: in the usual order, the partial sums of 1 − 1/2 + 1/3 − ... head to 0.6931. Reordered greedily (add odd-denominator positives while below the target, even-denominator negatives while above), the same terms head to 2, or to any target you choose. Continuous functions cannot skip a value Completeness delivers the theorem behind every "there must be a point where..." in applied mathematics: the intermediate value theorem. If a continuous function is negative at one end of an interval and positive at the other, it is zero somewhere in between. Proof sketch: take the supremum of the points where the function is still negative. By continuity it cannot be negative or positive there, so it is zero. The trick is that the supremum exists, which is exactly where the gap-free real line is used. Over the rationals the sup of {x : x² < 2} does not exist, and the theorem fails. The proof is also an algorithm. Check the midpoint, keep the half where the sign changes, repeat. This is bisection. Every step halves the interval, so after 10 steps the root is trapped in a window 1/1,024 of the original, and after 50 steps in a window around 10-15 of it. The guarantee is mathematics, but the computer is not mathematics: floating-point numbers have only about 16 significant digits, so the halving must stall. Watch it happen. Interactive · Bisection until the numbers run out cos x − x on [0, 1] x³ − x − 1 on [1, 2] x² − 2 on [1, 2] Bisection steps Without JavaScript: bisection on x² − 2 over [1, 2] traps √2 in an interval of width 2-10 ≈ 0.001 after 10 steps. In double precision the width stops shrinking near 2-52 ≈ 2.2 × 10-16. This is the first brush with Numerical Analysis (34/78): a theorem tells you the answer exists, and arithmetic tells you how close you can get. A limit of nice functions can be rude Take fn(x) = xn on [0, 1]. Every one is continuous and smooth. As n grows, each fixed x below 1 gets xn → 0, while at x = 1 the value stays 1. The limit function jumps. A limit of continuous functions need not be continuous, if the convergence is only pointwise. The fix is a stronger notion, uniform convergence: one ε works for all x at once, so the whole graph squeezes into a thin band round the limit. For xn on [0, 0.9] that happens, since 0.9n → 0. On [0, 1) it never does: for any n you can find an x close enough to 1 that xn is as big as 0.99. The trick of the proof is to compare the worst point, not each point. The theorem to remember: a uniform limit of continuous functions is continuous. This is what lets you differentiate a power series term by term. Interactive · Pointwise is not uniform Power n in xn Inspect the region [0, r] Without JavaScript: for n = 20, 0.920 ≈ 0.12 and 0.9920 ≈ 0.82, while the limit function is 0 there. On [0, 0.9] the worst gap shrinks to nothing as n grows; on [0, 1) it stays near 1. A curve with no tangent anywhere Until the 1870s mathematicians assumed a continuous curve had a tangent at most points, because anything you could draw did. In 1872 Karl Weierstrass presented a counter-example, now called the Weierstrass function: W(x) = Σ ak cos(bk π x)0 < a < 1, b an odd integer, ab > 1 + 3π/2 (Hardy 1916 showed ab ≥ 1 is enough) It is a sum of waves, each narrower and smaller than the last. The widths shrink by a factor b and the heights by a, so the wiggles get taller relative to their width: slope of the k-th wave is about (ab)k, which grows without bound. The sum is continuous (the tiny waves add up fast) but no matter how far you zoom in, new wiggles keep arriving. Historical note: Bolzano is thought to have built such an example earlier, and Weierstrass may have lectured on his in 1861, but 1872 is when it was published. Interactive · Zoom in on a function with no slope Waves added (a = 0.5, b = 13) Zoom: window width Without JavaScript: for a smooth function the slope across a shrinking window settles to one number. For W with a = 0.5 and b = 13, the average slope across ever narrower windows keeps growing in size (it multiplies by roughly 6.5 per wave) until the finite number of terms runs out. Weierstrass's function is not a curiosity. It shows what "continuous" does and does not give you, and it prepared the way for fractals, Brownian motion paths (nowhere differentiable too) and measure theory, where Henri Lebesgue's 1902 integral handles functions Riemann's integral cannot. What a graduate just sees The real line has no holes, and that single fact (every bounded set has a supremum) is the root of calculus. "Gets close" means: for any tolerance you can name, I can find a distance that delivers it. The δ may depend on ε. A limit claim is false if the opponent has one ε you cannot answer. One bad point-sequence suffices. An infinite sum needs a convergence condition, and conditionally convergent sums change if you reorder them. A continuous function on an interval hits every value in between, and attains its maximum; both need completeness. Pointwise limits can break continuity; uniform limits cannot. Always ask whether the closeness is the same everywhere. Smooth is rare. Most continuous functions are jagged, and calculus lives on the nice ones. Where it shows up next Complex Analysis (34/74): the same ε–δ ideas on the plane, where being differentiable once forces being smooth forever. Topology (34/76): continuity, completeness and compactness, stripped of distances. "Closed intervals attain their maximum" becomes a theorem about compact sets. Differential Equations (34/03) and Numerical Analysis (34/78): existence and uniqueness theorems, and error bounds, are analysis. The floating-point stall above is the first sign. Probability (34/05): expected values are integrals, and Lebesgue's integral is why probability on the real line works at all. The world: guarantees that an optimiser converges, that a signal's Fourier series reproduces it, that a simulation tends to the true solution as the step shrinks. If you want to go deeper 📘 Textbook. Walter Rudin, Principles of Mathematical Analysis (McGraw-Hill, 3rd edition, 1976). Terse and famous, the standard hard text; "Baby Rudin". 📘 Textbook. Stephen Abbott, Understanding Analysis (Springer, 2nd edition, 2015). Friendlier, built around the same examples as this piece, best for self-study. 📘 Gentler. Steven Strogatz, Infinite Powers (2019): the story of why calculus works and where infinity bites, with no proofs. 🌐 Free course. MIT OpenCourseWare 18.100A Real Analysis (Fall 2020): lecture videos, notes and problem sets. The takeaway Analysis puts a floor under calculus. The real line is complete, so intervals squeeze to points and continuous functions cannot skip values. A limit is a game with a guaranteed winning reply. And infinite processes (sums, limits of functions, derivatives) have conditions: without them they misbehave in specific, instructive ways. Try this: this week, when someone says "as it gets closer and closer", ask "closer than what, and how do you know it stays that close?" That question is the epsilon. Sources & Further Reading Sources. The definitions, completeness, the ε–δ limit, harmonic series divergence (Oresme), Riemann's rearrangement theorem, the intermediate value theorem, uniform convergence and the term-by-term results are standard (Rudin; Abbott). Berkeley's The Analyst (1734). Dedekind and Cantor's 1872 constructions of the reals. Weierstrass 1872 (continuous nowhere differentiable function), condition ab > 1 + 3π/2, Hardy 1916 (Trans. Amer. Math. Soc. 17, 301–325), and the Bolzano precedence note: summarised from standard accounts found by search (University of Minnesota notes, Quanta Magazine, 23 January 2025). Lebesgue 1902. Textbook editions: Rudin 3rd ed. (McGraw-Hill, 1976); Abbott 2nd ed. (Springer, 2015); MIT OCW 18.100A (Fall 2020). Every number the interactives show was computed in node and python: nested rationals via exact BigInt (e.g. 1.414² = 1.999396, 1.415² = 2.002225); δ = min(1, ε/5) checked; greedy rearrangement partial sums; bisection in IEEE doubles on cos x − x (root 0.7390851332151607), x³ − x − 1 (1.324717957244746), x² − 2; 0.920 = 0.1216, 0.9920 = 0.8179. 🌐 MIT OCW 18.100A Real Analysis 📘 Abbott, Understanding Analysis 📘 Rudin, Principles of Mathematical Analysis 📘 Strogatz, Infinite Powers Step 9. Abstract Algebra: Symmetry as a Structure of Its Own ------------------------------------------------------------ Why: Groups, rings and fields: symmetry as a structure of its own. Forget what the objects are. Keep only how they combine. That one move turns clock arithmetic, Rubik's cube and the unsolvable quintic into the same kind of problem. Rotate a square tile by a quarter turn, then flip it over. Flip it first, then rotate it. Do you get the same result? Try it on a real object and you will find you do not. The order of the moves matters, and yet the full list of ways to put a square back into its own outline is a tidy, closed family: eight moves, each one undoable, any two combining into another on the list. That family has a name, a group, and the course called abstract algebra starts from a daring idea. Do not study squares, clocks or cubes. Study the thing they share, the rules of combining, and prove everything that follows from the rules. Whatever you prove about groups is then true of every square, every clock and every cube at once. A graduate does not remember the theorems so much as the habit: when something has symmetry, ask for its group, and count. The course in one box Who takes itEvery mathematics major, in year 2 or 3 (MIT's 18.701 and 18.702; Cambridge's Groups in the first year and Groups, Rings and Modules in the second). Computer scientists meet it in cryptography and coding theory; physicists meet it as symmetry. What it is forGiving symmetry, and the structure of arithmetic, an exact language: groups, rings and fields. Comes afterLinear Algebra (34/04) and Foundations: What Mathematics Stands On (34/71). Leads toNumber Theory (34/75), and, in later courses, Galois theory, representation theory and algebraic geometry. What this piece gives youYou will not be able to classify groups of order 24. You will know what a group is, why a subgroup's size divides the group's, why a swapped pair of tiles can make a puzzle unsolvable, why arithmetic mod a prime is as good as the fractions, and how big the Rubik's cube group is and why. Easier first reads: The Most Beautiful Ideas in Math (12/04), Cryptography (12/09) and Vectors, Matrices and Linear Transformation (12/14). A group is a set of moves you can always undo A group is a set of things with a way of combining any two into a third, obeying four rules: Closed: combining two members gives a member. Associative: (a then b) then c equals a then (b then c). Identity: some member e does nothing. Inverses: each member has a partner that undoes it. Commutativity is not a rule. A group in which order never matters is called abelian; most interesting groups are not. A first proof, to feel the style: the identity is unique. Suppose e and e′ both do nothing. Then e combined with e′ equals e (since e′ does nothing) and equals e′ (since e does nothing). So e = e′. The trick is feeding each hypothesis to the other. The smallest non-commutative group is the six ways of moving an equilateral triangle onto itself: three rotations (turn 0, 120, 240 degrees) and three flips. Call a 120-degree turn r and a flip s. "rs" will mean "do r, then s". Pick any two moves and see the result, and check whether the other order gives the same triangle. Interactive · The symmetries of a triangle First move Then Without JavaScript: turning the triangle 120° and then flipping it leaves it in a different arrangement than flipping first and then turning. In symbols, rs ≠ sr, so the group is not commutative, and its multiplication table has six rows and six columns. The table at the bottom of the card is the group's Cayley table. Each element appears exactly once in every row and column, because you can always undo. A whole group, symmetries and all, is nothing but that table. Clock groups and the idea of order The simplest groups are clocks. Add hours on an n-hour clock and you have the group ℤn. Pick a step size a and keep adding it: how many steps until you come back to 0? That count is the order of a, and the places you visit form a subgroup, a group inside the group. order of a in ℤn = n ÷ gcd(n, a)on a 12-hour clock, a 5-hour step visits all 12 hours; a 4-hour step visits only 3 of them (0, 4, 8) An element that visits everything is a generator; 5 generates ℤ12 but 4 does not. This also settles when two groups are really the same. Two groups are isomorphic if you can relabel one into the other so the tables match. ℤ6 is isomorphic to ℤ2 × ℤ3 (the 1 of ℤ6 has order 6, and so does the pair (1, 1)). But ℤ4 is not isomorphic to ℤ2 × ℤ2: the first has an element of order 4 and the second has none. Comparing element orders is the standard way to tell groups apart. Interactive · Walk around the clock Clock size n Step size a Without JavaScript: on a 12-hour clock a step of 5 visits all 12 positions, so it generates the group; a step of 4 visits 0, 4, 8 and returns after 3 steps; a step of 6 visits only 0 and 6. Exactly 4 of the 12 step sizes (1, 5, 7, 11) are generators. Lagrange's theorem: subgroups tile the group Take a subgroup H inside a group G and "translate" it: pick any member g and form gH, everything you get by doing g and then a member of H. These translates are called cosets. Two facts make a picture. First, each coset has exactly as many members as H, because the move "do g first" can be undone, so it matches H one to one with gH. Second, any two cosets are either identical or share nothing. If they shared a member, you could rewrite one as the other. So the cosets cut G into equal-sized, non-overlapping tiles. Count the tiles: |G| = (number of cosets) × |H|. That is Lagrange's theorem: the size of a subgroup always divides the size of the group. The tricks are that a translation is reversible, so it preserves size, and that two overlapping cosets must coincide. It was Lagrange (about 1771, in his study of polynomial equations) who noticed the pattern before groups existed as a concept. The converse is false, and that is what makes the theorem a tool rather than a tautology. A group of order 12 need not have a subgroup of every size that divides 12. The alternating group on four things, which has 12 members, has no subgroup of order 6. Choose a group below and the page finds every subgroup by brute force. Interactive · Find the subgroups, tile the group Clock of 12 Triangle moves (6) Square moves (8) Even shuffles of 4 (12) All shuffles of 4 (24) Subgroup number Without JavaScript: the 12-member group of even shuffles of 4 things has subgroups of orders 1, 2, 3, 4 and 12 but none of order 6, though 6 divides 12. The full group of 24 shuffles has subgroups of every order that divides 24. A consequence you will use for life: in the multiplication of non-zero residues mod a prime p (which has p − 1 members), every element's order divides p − 1. Hence ap−1 ≡ 1 (mod p), Fermat's little theorem, and the engine inside RSA encryption (see 12/09 and 34/75). Invariants: what a move can never change A homomorphism is a map between groups that respects the combining: do two moves and then translate equals translating each and then combining. It forgets detail but keeps structure, and its great use is catching things that cannot happen. The standard example is parity. Every shuffle of n things is a product of swaps of two items. A shuffle may be written with many swaps, but always an even number or always an odd number, never both. Call these even and odd, and the map "even → +1, odd → −1" respects combining (two odds make an even, as −1 × −1 = +1). Now the 15 puzzle: a grid of sliding tiles with one gap. Every legal slide leaves the parity of a certain count (for the 3×3 version, the number of "inversions", pairs of tiles that are out of order) unchanged. Swap two tiles by lifting them out and you flip that parity. Those positions can never be reached by sliding, and exactly half of all arrangements are in that unreachable half. An 1879 paper by Johnson and Story proved this for the 15 puzzle. The trick is to find a quantity that no move changes, then show the target has a different value. Interactive · The 8-puzzle and its invariant Scramble with 60 slides Lift out and swap tiles 7 and 8 Reset Without JavaScript: the solved board 1 2 3 / 4 5 6 / 7 8 _ has 0 inversions (even). Swapping tiles 7 and 8 gives 1 inversion (odd). Sliding never changes the inversion parity, so that swapped board can never be solved by sliding. Press a tile next to the gap to slide it. Scramble as hard as you like: the inversion count stays even. The swap button produces a board that looks innocent and cannot be solved. Rings and fields: which clocks let you divide A group has one operation. A ring has two, addition and multiplication, linked by the distributive law: the integers, the clock numbers, polynomials and matrices are rings. A field is a ring where you can also divide by anything non-zero: the rationals, the reals, and the complex numbers. Clock arithmetic is a ring for any n. Is it a field? Division by a means finding a number b with a·b ≡ 1. Such a b exists exactly when gcd(a, n) = 1, and Euclid's algorithm finds it (stepping back through the remainders). If gcd(a, n) > 1 you are in trouble: mod 12, 3 × 4 = 12 ≡ 0, so two non-zero numbers multiply to zero, and "zero divisors" make division impossible. So ℤn is a field exactly when n is prime. The trick behind inverses: if gcd = 1, Euclid's remainders can be run backwards to write 1 as a combination of a and n. Interactive · Who has an inverse? Clock size n Green: has an inverse. Red: shares a factor with n. Press a number. Without JavaScript: mod 12, the numbers 1, 5, 7 and 11 have inverses (each is its own inverse: 5×5 = 25 ≡ 1). Mod 7, a prime, all of 1 to 6 do, and 3×5 = 15 ≡ 1. Finite fields are not a curiosity. They are the arithmetic behind error-correcting codes (QR codes, CDs, deep-space probes), elliptic-curve cryptography, and the AES cipher in your phone. Rubik's cube, the unsolvable quintic, and the monster The moves of a Rubik's cube form a group, and counting it uses everything above. Naively a cube has 8 corner pieces in 8 places with 3 twists each, and 12 edge pieces in 12 places with 2 flips each. Multiply: 8! × 38 × 12! × 212. But real turns obey three rules (an invariant, again): the corner twists must total a multiple of 3, the edge flips must total an even number, and corners and edges must have the same permutation parity. Those cut the count by 3, 2 and 2, a factor of 12, leaving 43,252,003,274,489,856,000about 4.3 × 1019 positions reachable by turning faces A team led by Tomas Rokicki showed in 2010, using a lot of donated computer time, that every one of these positions can be solved in at most 20 face turns ("God's number" is 20). The 12 unreachable arrangements for every reachable one are the cube you get by prying it apart and reassembling it badly. Interactive · Count the cube Switch the rules of the cube on and off. Without JavaScript: 8! × 38 × 12! × 212 = 519,024,039,293,878,272,000. Dividing by 3 (twist rule), 2 (flip rule) and 2 (parity rule) gives 43,252,003,274,489,856,000. At a billion positions per second, looking at each once would take about 1,371 years. The same subject settles an old problem. The quadratic formula has cousins for cubics and quartics (16th century). For the general fifth-degree equation no formula using only +, −, ×, ÷ and roots exists. Abel and Ruffini gave proofs in the 1820s; Évariste Galois explained why a few years later, shortly before his death in 1832 at age 20. His idea: attach to each equation the group of ways to shuffle its roots while keeping all their algebraic relations. An equation is solvable by roots exactly when that group can be built up in simple abelian stages. The group for a general quintic is the full set of 120 shuffles of five things, which cannot be so built. The obstruction is a group-theoretic fact, with no pencil-and-paper cleverness needed. That raises a question: what are the "atoms" of groups? A group with no inner structure to peel away is simple, and every finite group is built from simple ones. The classification of finite simple groups lists them all: a few infinite families (the cyclic groups of prime order, the alternating groups on five or more things, and several families of matrix groups) plus exactly 26 "sporadic" groups that fit no family. The largest, the Monster, has about 8 × 1053 members. The classification is one of the largest proofs ever assembled, spread over tens of thousands of journal pages by many authors. Its completion was announced in 1983, a gap in one case was filled in 2004, and a streamlined "second-generation" proof (the Gorenstein–Lyons–Solomon programme) is still unfinished; the result is accepted by the field. What a graduate just sees If something has symmetry, ask for its group and count it. The count often explains the object. The order of moves matters in most groups; "abelian" is the special, easy case. A subgroup's size always divides the group's size. If a number does not divide, no such subgroup exists. When a puzzle seems impossible, look for an invariant, a quantity that no legal move changes. Two structures are the same if their tables match after relabelling; element orders tell them apart. Clock arithmetic lets you divide exactly when the clock size is prime. Whether an equation can be solved by a formula is a statement about the group of its roots. Where it shows up next Number Theory (34/75): the units mod n form a group, and Fermat's and Euler's theorems are Lagrange's theorem in disguise. Cryptography and coding: RSA uses the group of units mod a product of two primes; elliptic-curve systems use a group built from points on a curve; error-correcting codes use finite fields. Physics: conserved quantities come from symmetry (Noether's theorem), and the particle zoo is sorted by representations of symmetry groups. See Quantum Mechanics (34/83) and the Standard Model piece (13/07). Chemistry and materials: the 230 space groups classify every crystal; molecule vibrations are sorted by their symmetry group. Topology (34/76): algebraic topology attaches groups to shapes to tell them apart, the same "invariant" trick as the puzzle. If you want to go deeper 📘 Textbook. Joseph Gallian, Contemporary Abstract Algebra (10th edition). The usual first text: many examples, gentle on proofs. 📘 Textbook. David Dummit and Richard Foote, Abstract Algebra (Wiley, 3rd edition). The comprehensive reference that mathematics students keep for years. 📘 Gentler. Nathan Carter, Visual Group Theory (MAA). Groups taught through pictures and Cayley diagrams, with the Rubik's cube in view; or Mark Ronan, Symmetry and the Monster (Oxford, 2006) for the story of the classification. 🌐 Free course. MIT OpenCourseWare 18.701 Algebra I (Fall 2010, taught by Michael Artin): the full undergraduate group, ring and field course with notes and problem sets. The takeaway Algebra stops asking what things are and asks how they combine. A group captures symmetry; counting it gives Lagrange's divisibility rule; invariants prove impossibility; rings and fields capture arithmetic you can trust. The same few ideas explain a clock, a puzzle, a cipher and the limits of a formula. Try this: this week, pick a symmetric thing (a snowflake, a chair, a logo) and list the moves that put it back on itself. Count them. Then check that doing two of them in either order lands in the list. Sources & Further Reading Sources. The group axioms, cosets, Lagrange's theorem, homomorphisms, parity, rings and fields, Fermat's little theorem and the Rubik's cube count are standard textbook algebra (Gallian; Dummit & Foote; Artin). Rubik's cube group order 43,252,003,274,489,856,000 and God's number 20 (Rokicki, Kociemba, Davidson and Dethridge, 2010): cube20.org. Classification of finite simple groups: announced 1983, quasithin gap closed by Aschbacher and Smith (2004), second-generation proof incomplete: MacTutor and standard accounts; 26 sporadic groups; Monster order 246·320·59·76·112·133·17·19·23·29·31·41·47·59·71 ≈ 8.08 × 1053 (computed). Abel–Ruffini (1820s) and Galois (died 1832), Johnson and Story (1879) and Lagrange (c. 1771) are standard history and were not re-searched for this piece. Editions: Dummit & Foote 3rd ed. (Wiley, 2004); Gallian 10th ed.; MIT OCW 18.701. Every number the interactives show was computed by brute force in node: subgroup orders of ℤ12, S3, the square's group, A4 and S4; Euclid inverses mod n; 8-puzzle inversion parity; cube counts as above with BigInt. 🌐 MIT OCW 18.701 Algebra I 🌐 cube20.org: God's Number is 20 📘 Dummit & Foote, Abstract Algebra 📘 Carter, Visual Group Theory Step 10. Probability & Statistics: Reasoning with Uncertainty ------------------------------------------------------------- Why: Probability: the mathematics of uncertainty. Nothing you measure is exact, and no part comes out the same twice. Statistics is the discipline of knowing how much to trust a number. A machinist turns a hundred steel shafts to "10 millimetres". Measure them with a good micrometer and no two are the same: 9.981, 10.012, 10.004. Nothing is wrong. That scatter is a fact of every process, every material and every sensor. Now stack five of those parts end to end in a gearbox. Will the stack still fit the housing? A pollster calls a thousand people and says 52% will vote yes, give or take three. A drug trial says "significant". A forecast says 30% chance of rain. Every one of these is the same question: given scatter, how much should I trust this number? A graduate of probability and statistics doesn't see a single number any more. They see the shape of the scatter behind it. This piece builds that sight with eight things you can run: dice, tolerances, polls, a drug-trial trap, a belief that updates, and a gearbox stack. The course in one box Who takes it: almost every engineering and science student, usually in the second year; computer scientists meet it again before machine learning. What it's for: deciding what to believe, and how far to trust a measurement, when outcomes are uncertain. Comes after: Calculus I (34/01), which helps with continuous distributions, though the ideas here need little more than arithmetic. Leads to: Machine Learning (34/32) needs it directly. It also shows up in Materials Science & Manufacturing (34/13: process control and defects), Systems Engineering (34/22: reliability) and Computer Security (34/33: randomness and guessing). Honest line: you won't be able to design a clinical trial after this. You will see why "significant" doesn't mean "important", why a bigger sample beats a cleverer guess, and why most real quantities look like a bell curve. For easier first reads, see the library's Probability: How to Not Fool Yourself (12/03), Statistics for Reading the World (12/05) and Bayes' Theorem (12/17); this piece goes further into the engineering side. Random variables: a shape with a centre and a spread A random variable is a number that comes out of a process you can't predict one run at a time. The key move is to stop asking "what will it be?" and ask "what is the shape of what it could be?" Roll two dice and add them: 7 is six times as likely as 2 or 12, so the shape is a tent. Roll many times and the tent appears. Interactive · Roll dice, grow a shape Dice added together Roll 10 timesRoll 1,000 timesClear Without JavaScript: two dice add to 7 with probability 6/36 and to 2 or 12 with probability 1/36 each. The mean total is 7 and the standard deviation is about 2.42. Two numbers summarise a shape. The mean is its balance point: 7 for two dice. The standard deviation (the "spread") says how far values typically stray from the mean: about 2.4 for two dice, which means totals usually land between roughly 5 and 9. The variance is the standard deviation squared, and it is the one that adds up neatly when you combine independent things. standard deviation = √( average of (value − mean)² ) Now the shape that matters most. Measured quantities (shaft diameters, heights, sensor noise) tend to form the normal curve, the bell. Its great convenience is a fixed rule: about 68.3% of values fall within one standard deviation of the mean, 95.4% within two, and 99.7% within three. Engineers use it every day. Say the shaft's spec is 10.00 mm ± 0.05 mm. Slide the process around and see what share of parts get thrown away. Interactive · How many parts fail the spec? Average diameter Spread (standard deviation) Without JavaScript: a centred process with standard deviation 0.025 mm (the spec limits are exactly ±2 standard deviations) scraps about 4.55% of parts. Cut the spread to 0.01 mm and about 0.00006% are scrapped. Shift the average 0.02 mm off-centre with spread 0.02 mm and about 6.7% are scrapped. Two lessons graduates keep. First, spread, not average, decides quality: a process centred perfectly but wide still scraps parts. Second, being off-centre costs a lot even when the spread is fine. That is why factories track both. The central limit theorem: why the bell keeps appearing Why should so many things be bell-shaped? The answer is one of the most useful theorems in mathematics. Take almost any random process, however lopsided, and average a few dozen independent draws. The averages pile up in a bell, centred on the true mean, with spread shrinking like 1/√n. Early forms are due to de Moivre in 1733 (for coin flips) and Laplace, whose general version dates from about 1810. Pick a lopsided source and drag the sample size. Interactive · Average anything, get a bell Flat (0 to 1) Very lopsided Coin (0 or 1) Draws averaged together: n Without JavaScript: for the lopsided source (mean 1, standard deviation 1) the average of n = 30 draws has standard deviation 1/√30 = 0.183, and the 3,000 averages form a close-to-normal bell around 1. At n = 1 you see the raw source. By n = 30 even the lopsided one is a near-bell. The prediction (the curve) uses only two numbers from the source, its mean and its standard deviation. The shape of the source is forgotten. That is why a measurement made of many small independent errors is normal, and why so much of statistics can pretend things are bell-shaped. standard error of an average = σ / √n In words: the average of n draws wobbles less than one draw, by the square root of n. To halve the wobble you need four times the data, not twice. It is the quietest expensive fact in all of experimental science. Sampling and confidence intervals: how sure is a poll? You can't ask everyone, so you ask n people and treat the share saying yes as an estimate. How far off might it be? The standard error from the last section gives the answer. For a share p the wobble is √(p(1−p)/n), and a 95% confidence interval is the estimate plus and minus about two of those. For n = 1,000 and a share near half, that is ±3.1 percentage points: the familiar "margin of error". The wording is subtle, and the interactive makes it concrete. "95% confidence" is a statement about the method, not about one interval: if you ran the procedure again and again, about 95 intervals in 100 would capture the true value. Here the truth is secretly 52%. Run 100 polls. Interactive · 100 polls, one truth People asked in each poll Run 100 polls Without JavaScript: with 1,000 people per poll the margin of error is about 3.1 points; run 100 polls and about 95 of the intervals cover the true value. With 4,000 people the margin halves to about 1.5 points. Watch two things. Roughly five in a hundred intervals miss the truth even when everything is done correctly. And quadrupling the sample from 1,000 to 4,000 only halves the interval. A poll of a country and a poll of a town need the same sample size for the same precision, as long as the sample is random. The real danger is not the margin of error; it is a sample that isn't random at all, which no formula fixes. P-values and Bayes: two ways to weigh evidence A hypothesis test asks whether data are surprising if nothing is going on. The p-value is the probability, assuming nothing is going on, of seeing a result at least as extreme as yours. Flip a coin 100 times and get 60 heads: for a fair coin the chance of a split at least that lopsided in either direction is about 5.7%. It is not the probability that the coin is fair, and it is not the probability that the result was "due to chance". The American Statistical Association issued a rare formal statement on this in 2016, with six principles. Two of them: p-values do not measure the probability that a hypothesis is true, and a p-value does not measure the size or importance of an effect. The classic trap is testing many things. At the usual cut-off of 0.05, a test of a true "nothing" comes out "significant" one time in 20 by luck. Test twenty unrelated things and the chance that at least one lights up is 1 − 0.9520, about 64%. Try it: each press tests twenty effects that are, by construction, nothing. Interactive · Test twenty things that do nothing Run 20 testsReset the tally Without JavaScript: twenty tests of pure noise at the 0.05 level give at least one false "discovery" about 64% of the time, and one in 20 tests on average. If you report only the one that lit up, you have a headline and no finding. This is part of why many published results fail to repeat: in the Open Science Collaboration's 2015 attempt to replicate 100 psychology studies, 97% of the originals had statistically significant results but only 36% of the replications did. Bayes' rule answers a different question: given the data, how should my belief move? Start with a prior belief, multiply by how well each possibility explains the data, and renormalise. Say you test parts and want the defect rate. Know nothing at first (any rate from 0% to 100% equally likely) and add parts one at a time. Interactive · Learn a defect rate from parts Add a good partAdd 10 good partsAdd a defective partReset Without JavaScript: after 20 good parts and no defects, a flat starting belief gives a most-plausible defect rate near 0%, an average of 4.5%, and a 90% credible range of roughly a quarter of a percent to 13%. Twenty clean parts cannot rule out a defect rate near one in eight. Frequentists and Bayesians disagree about the philosophy: one treats probability as long-run frequency and never assigns it to a hypothesis, the other as degrees of belief that data update. In practice both are used, often on the same project, and on big data sets they usually agree. The Bayesian version has one practical advantage here: after twenty clean parts it honestly says "we still can't rule out one in eight". Correlation, regression and the trap of causation Correlation (called r) measures how tightly two quantities move together along a straight line, from −1 to +1. Regression fits the best line through the cloud (by least squares, as in Linear Algebra, 34/04). Both are summaries, and any summary can hide the story. In 1973 the statistician Francis Anscombe made four data sets with, to two decimals, the same mean, the same spread, the same r (0.82) and the same line (y = 3 + 0.5x). Look at each. Interactive · Four data sets, one set of numbers Set 1Set 2Set 3Set 4 Without JavaScript: all four Anscombe sets have mean x = 9, mean y = 7.50, correlation 0.816 and line y = 3.00 + 0.50x. Set 1 is a noisy line, set 2 a curve, set 3 a line with one outlier, and set 4 a single far point that creates the whole slope. The numbers agree and the stories do not: one noisy line, one curve, one line with a rogue point, one vertical stack held up by a single point. Always plot first. The other trap is the famous one. Ice-cream sales and drownings rise together, because summer heat drives both. A confounder (a hidden third factor) makes two things move together without either causing the other. The remedy graduates know is randomised assignment: if a coin decides who gets the treatment, nothing else can be systematically linked to it. Where you can't randomise, causal claims need much more than a line through a cloud. Engineering: tolerance stacks, reliability and Monte Carlo Five parts, each 10 mm ± 0.1 mm, line up in an assembly. What is the worst the total can be out? Worst-case stacking adds the tolerances: ±0.5 mm. It is safe and expensive, because it assumes every part is at its extreme in the same direction at once. If the parts vary independently, variances add, so the standard deviations add in quadrature: root-sum-square, √5 × 0.1 = ±0.224 mm. For five parts that is under half the worst-case figure. When the formulas get hard, engineers use Monte Carlo: let the computer build the assembly ten thousand times with random parts and count how often it fails. Here each part's tolerance is treated as three standard deviations. Choose how many parts are stacked. Interactive · Monte Carlo tolerance stack Parts in the stack Build 10,000 assemblies again Without JavaScript: five parts at ±0.1 mm (three standard deviations) give a worst-case limit of ±0.5 mm, a root-sum-square limit of ±0.224 mm, and in simulation only about 0.3% of assemblies exceed the root-sum-square limit; none come close to 0.5 mm. The honest caveat is that root-sum-square assumes the parts vary independently and are centred. A tool wearing in the same direction on every part breaks that assumption, and so does one supplier's batch. Engineers disagree about when to trust statistical stacking over worst-case; safety-critical designs often insist on worst-case. Reliability follows the same arithmetic. A system that needs all of its parts is a series system, and probabilities multiply: ten components that each work 99% of the time give 0.9910 ≈ 90.4% for the whole. Add a backup in parallel and failure needs both to fail: two units that each work 90% of the time give 1 − 0.1² = 99%. The two rules drive why aircraft duplicate systems and why complicated machines need very reliable components. What a graduate just sees Every number has a spread behind it; the first question is "how scattered?", not "what is it?". Spread, not the average, decides how many parts are scrapped, and centring matters too. Averages of many independent things are bell-shaped, whatever the source looked like. Halving the uncertainty costs four times the data. A 95% interval is a claim about a method: it misses one time in twenty by design. A p-value is "how surprising is this if nothing is going on", not "how likely is it true". Test twenty things and one will look significant; ask how many were tried. Plot the data; correlation is not causation, and only randomising breaks a confounder. Independent errors add in quadrature; series reliabilities multiply. Where it shows up next Machine Learning (34/32): training is fitting a model to noisy data; ideas of overfitting, error bars and Bayes are this course made bigger. Materials Science & Manufacturing (34/13): process capability and scrap rates are the normal curve against a spec limit. Mechanics of Materials (34/11) and Machine Design (34/19): safety factors exist because loads and strengths are distributions, not numbers. Systems Engineering (34/22): reliability budgets multiply series probabilities and add redundancy to push them back up. Computer Security (34/33) and Algorithms (34/24): good random numbers, randomised algorithms, and the odds of guessing a secret. If you want to go deeper 📘 Douglas Montgomery and George Runger, Applied Statistics and Probability for Engineers (Wiley; 7th edition). The standard engineering course text, with plenty of tolerance, quality and reliability problems. 📘 Joseph Blitzstein and Jessica Hwang, Introduction to Probability (CRC Press; 2nd edition, 2019). Best for deep intuition about probability itself, from Harvard's Stat 110. 📖 David Spiegelhalter, The Art of Statistics (2019): the most readable route for learning alone, built around real cases and honest about uncertainty. 🌐 MIT OpenCourseWare 18.05, Introduction to Probability and Statistics (Spring 2022): free notes and problem sets, with Bayesian and classical statistics side by side. The takeaway Nothing you measure is exact, so every number is a shape. Summarise a shape by its centre and its spread, trust averages more as the square root of the sample, read a confidence interval as a promise about a method, treat a p-value as a measure of surprise, and plot before you believe a correlation. Try this: next time you see a poll or a "significant" headline, find the sample size and ask how many things were tested. Then, in the dice widget above, add four dice and watch the tent turn into a bell. Sources & Further Reading Sources. The normal-curve rule (68.3%, 95.4%, 99.7%), the central limit theorem, confidence intervals, the binomial test, the Beta posterior, root-sum-square stacking and series/parallel reliability are standard textbook results (Montgomery and Runger; MIT 18.05); every number shown was recomputed in code. Wasserstein and Lazar, "The ASA's Statement on p-Values: Context, Process, and Purpose", The American Statistician (2016). Open Science Collaboration, "Estimating the reproducibility of psychological science", Science (2015): 97% of originals significant against 36% of replications. Anscombe, "Graphs in Statistical Analysis", The American Statistician (1973). Early forms of the central limit theorem: de Moivre (1733) and Laplace (c. 1810), as surveyed in recent histories such as Ulyanov, "From classical to modern central limit theorems" (arXiv 2405.19828). Go deeper. The books and course above; Wasserstein and Lazar's statement is free and short (doi.org/10.1080/00031305.2016.1154108). Step 11. Complex Analysis: Calculus on a Plane Where Everything Fits Together ----------------------------------------------------------------------------- Why: Calculus with complex numbers, where everything is unexpectedly beautiful. Take the calculus you know and let the variable wander off the number line into a plane. The rules get stricter, and in exchange the theorems become almost unreasonably strong. Here is a small mystery that nothing in first-year calculus can explain. The function 1/(1 + x²) is as well behaved as a function gets. It is smooth at every real number, with no jumps, no spikes and no division by zero anywhere. Yet if you write its Taylor series around x = 0, the series works for x between −1 and 1 and falls apart outside, even at x = 1.5, where the function itself is perfectly calm. Why would a series care about the number 1? The answer is not on the number line at all. The function 1/(1 + x²) does blow up, just not at a real number: it blows up where x² = −1, at x = i and x = −i. Those two points are exactly one step away from zero, and the series can feel them from the other side of the page. A graduate of a complex analysis course carries this picture permanently: a real function is a shadow of a function on the plane, and the shadow's behaviour is controlled by things you cannot see in the shadow. That is the whole subject in one image. Do calculus with numbers of the form a + bi, and the demand that derivatives exist turns out to be so strict that functions become rigid, predictable and tightly linked. This piece walks through the six ideas a graduate keeps, with a proof sketch for each, so you can feel why they are true. The course in one box Who takes itMathematicians, physicists and electrical engineers, usually in year 2 or 3. MIT teaches it as 18.04 Complex Variables with Applications to mathematicians, physicists and engineers together; the Cambridge Mathematical Tripos covers complex analysis in its second year. Some programmes run a proof-heavy version for mathematicians and a methods version for physicists. What it is forDoing calculus with complex numbers, which gives shortcuts to real integrals, a deep understanding of power series, and the language of waves, signals and quantum mechanics. Comes afterMultivariable Calculus (34/02) and Real Analysis (34/72). Leads toNo later subject in this series formally requires it, but it feeds Partial Differential Equations (34/79), Quantum Mechanics (34/83), Signals and Systems (34/37) and Number Theory (34/75), where the Riemann zeta function lives. What this piece gives youYou will not be able to prove the residue theorem in full generality. You will see why multiplying is turning, why a derivative on a plane is a stretch and a turn, why integrals around loops forget their shape, and how that lets you compute a real integral by leaving the real line. Easier first reads: Euler's Identity, Built Step by Step (12/19) and Calculus: The Language of Change (12/11). This piece goes further and makes you do it. Multiplying is turning: why the plane is the right home for numbers A complex number a + bi is a point on a plane: a steps along, b steps up. The only thing that sounds odd is the rule i² = −1. Here is the picture that makes it ordinary. Every complex number has a length (its distance from zero) and an angle (measured from the positive real axis). Multiplying two complex numbers does something simple to those two things: |zw| = |z|·|w| and arg(zw) = arg z + arg wmultiply the lengths, add the angles So multiplying by i, which has length 1 and angle 90°, is a pure quarter-turn. Do it twice and you have turned 180°, which is multiplying by −1. That is all i² = −1 means. The square root of −1 is not mysterious; it is the number you multiply by to turn a quarter of the way round. Proof sketch · why (1 + i)² must be 2i The number 1 + i sits 1 right and 1 up, so its length is √2 and its angle is 45°. Squaring it multiplies the length by itself (√2 × √2 = 2) and doubles the angle (90°). A point of length 2 at 90° is 2i. The real trick is the rule "lengths multiply, angles add"; once you have it, algebra becomes geometry. Expanding (1 + i)(1 + i) = 1 + 2i + i² = 2i agrees. Try it yourself. Set two numbers by length and angle and watch the product. Interactive · Multiply by turning i × i (1 + i) × (1 + i) Undo a turn Length of z Angle of z Length of w Angle of w Blue is z, orange is w, green is zw. The readout multiplies the real and imaginary parts directly, (a + bi)(c + di) = (ac − bd) + (ad + bc)i, and also shows length × length and angle + angle. They always agree. With z = 1.4 at 45° and w = 1 at 90°, the product has length 1.4 and angle 135°. The preset "Undo a turn" multiplies a length-2 number at 30° by a length-0.5 number at 330°, which is the same as −30°: the lengths cancel to 1 and the angles cancel to 0, landing on the number 1. Division is turning back. Differentiable means: only a stretch and a turn In real calculus, a derivative is a slope: near a point, the function looks like a straight line. In the complex plane the input and the output are both planes, and "looks like a straight line" becomes "looks like multiplying by one fixed complex number". And you now know what that does: it stretches by its length and turns by its angle. So a complex-differentiable function, viewed close up, only scales and rotates. It never shears or flips or squashes more in one direction than another. That is a much stricter demand than in real calculus, because the limit defining the derivative has to give the same answer no matter which direction you approach from: from the left, from below, along a spiral. The simplest function that fails is conjugation, z ↦ z̄ (flip the sign of the imaginary part): approach 0 along the real axis and the difference quotient is 1, along the imaginary axis it is −1. No single derivative exists, and conjugation is a mirror. Proof sketch · the Cauchy–Riemann equations Write f = u + iv. Step to the right by h and the derivative is ∂u/∂x + i ∂v/∂x. Step up by ih and it is (1/i)(∂u/∂y + i ∂v/∂y) = ∂v/∂y − i ∂u/∂y. The real trick is to demand these two be equal. Matching real and imaginary parts gives ux = vy and uy = −vx. Those are the Cauchy–Riemann equations, and they say exactly "the derivative is one stretch-and-turn". f′(z) = lim (f(z + h) − f(z)) ÷ hh is a complex step, and the answer must not depend on its direction The payoff is that these maps preserve angles: two curves crossing at 90° cross at 90° after the map. Map makers use this (conformal maps keep local shapes), and engineers use it to turn awkward shapes into easy ones. Watch a grid get bent and notice the squares stay square. Interactive · Bend the plane z² 1/z eᶻ z + 1/z Probe point, real part Probe point, imaginary part Left: the input grid with your probe point. Right: where the function sends it. The readout measures the image of a tiny right-pointing step and a tiny upward step numerically (step size 10⁻⁶). For z² at the probe point 0.7 + 0.5i the derivative is 2z = 1.4 + 1.0i, which stretches by about 1.72 and turns by 35.5°. The readout measures this from scratch and also reports the angle between the images of a rightward and an upward step: 90° every time, apart from the places where the derivative is zero. Slide the probe to 0 on z² and the angle rule fails honestly: z² doubles angles there, a clean example of why a zero derivative is special. Loops forget their shape: Cauchy's theorem and the pole Now integrate. Walk a loop in the plane and add up f(z) dz along the way. Here is the central theorem of the subject: if f is complex-differentiable everywhere inside a loop, the integral around the loop is exactly zero. Any loop, any shape, any size. Whatever the function does on the way out, it undoes on the way back. Proof sketch · why it's zero, and why 1/z is different If f has an antiderivative F (a function whose derivative is f), then the integral along a path is F(end) − F(start). A loop starts and ends at the same point, so the integral is F(start) − F(start) = 0. For z², the antiderivative is z³/3, and that is a perfectly good function of position. The real trick is to ask whether the antiderivative returns to its old value after a lap. For 1/z, the antiderivative is the logarithm, and log z = ln|z| + i·arg z. Walk once round the origin and the angle goes up by 2π, so the logarithm does not come back: it gains 2πi. That gain is the integral. ∮ dz ÷ z = 2πionce round the origin, whatever the shape of the loop, as long as it encircles 0 So the only thing a loop integral can detect is a pole: a point where the function blows up and the antiderivative picks up a twist. Move the loop around and see what it detects. Interactive · What does the loop enclose? z² 1/z (pole at 0) 1/z + 1/(z − 2) 1/z² Circle centre, x Circle centre, y Radius Poles are the orange dots. The integral is a trapezoid sum of f(z)·dz around the circle with 2,000 steps. If the circle runs through a pole the integral does not exist and the page says so. What to see: z² gives 0 for every loop. 1/z gives 2πi ≈ 6.283i when the loop contains the origin and 0 when it does not. The sum 1/z + 1/(z − 2) gives 4πi when the loop holds both poles, 2πi for one. And the surprise: 1/z² has a pole at the origin but the integral is still 0, because its antiderivative −1/z comes back to itself after a lap. It is the coefficient of 1/z, the residue, that the loop sees. Residues: solving a real integral by leaving the real line Put the last two ideas together and you get one of the most useful tricks in applied mathematics. The residue theorem: the integral around a loop is 2πi times the sum of the residues of the poles inside it. ∮ f(z) dz = 2πi × (sum of residues inside)the residue at a simple pole p is the number c in f(z) ≈ c ÷ (z − p) near p Why would that help with a real integral? Because you can close up a real line with a huge semicircle through the upper half of the plane, and the loop integral has two parts: the straight bit you want, plus the arc. If the arc part shrinks to zero as the semicircle grows, then the real integral equals 2πi times the residues inside. Take f(z) = 1/(1 + z²), which has poles at i and −i. Only i is in the upper half-plane. Near i, 1 + z² = (z − i)(z + i), so f ≈ 1/(2i) × 1/(z − i): the residue is 1/(2i). Then: ∫ from −∞ to ∞ of dx ÷ (1 + x²) = 2πi × 1/(2i) = πthe answer you can check with arctan, got here by a detour through the plane Proof sketch · why the arc vanishes On the arc, |z| = R, so |1 + z²| ≥ R² − 1. The arc has length πR. A bound on the integral is (length) × (largest value of the integrand) ≤ πR ÷ (R² − 1). The real trick is that R² in the denominator beats R in the numerator, so the bound shrinks like π/R. The same argument handles integrals like ∫ dx/(1 + x⁴) = π/√2 ≈ 2.2214, where the real-line antiderivative is a mess. Interactive · Close the contour Semicircle radius R The line integral is 2·arctan R (exact). The arc integral is a midpoint sum over 2,000 steps. Their total is π for every R > 1; that equals 2πi times the residue 1/(2i). The picture is drawn with the semicircle at fixed size, so the pole at i slides down as R grows. At R = 3 the straight part is 2.498 and the arc contributes about 0.644, summing to π = 3.1416. At R = 40 the straight part has grown to 3.092 and the arc has shrunk to 0.050. The total never moves from π; the arc is just the shortfall of the straight part, and the shortfall fades as R grows. That is the residue theorem doing its work. Power series know where the poles are Back to the opening mystery. A function that is complex-differentiable on a disc is equal to its Taylor series on that whole disc, and the disc can be as large as the distance to the nearest trouble. That is a theorem with a one-line reason: near a pole at w, the function behaves like 1/(z − w), and the geometric series 1/(z − w) = −(1/w)(1 + z/w + (z/w)² + …) only converges while |z| < |w|. The series is only as wide as the distance to the nearest pole, measured in the plane, not on the line. radius of convergence = distance from the centre to the nearest singularityfor 1/(1 + x²) at centre a: radius = √(1 + a²), because the poles are at ±i At centre 0, the poles ±i are 1 away, so the series 1 − x² + x⁴ − … converges for |x| < 1 and nowhere else. Move the centre to a = 1 and the distance becomes √2 ≈ 1.414. At a = 2, √5 ≈ 2.236. The series centred further out sees the poles from further away. Try a point beyond the radius and watch the partial sums fly apart. Interactive · Where does the series stop working? Centre a Evaluate at x Terms used Blue: 1/(1 + x²). Orange: the Taylor polynomial with the number of terms you pick (clipped to the frame). Shaded: the interval a ± √(1 + a²) where the series converges. Coefficients come from the exact formula cₙ = (1/2i)[−1/(i − a)ⁿ⁺¹ + 1/(−i − a)ⁿ⁺¹]. With a = 0 and x = 0.8, twelve terms give 0.568 against the true value 0.610, and forty terms give 0.6097: converging, slowly, because 0.8 is close to the edge. Push x to 1.5 and twelve terms give about −39.6, thirty terms give about 59,000. Outside the radius 1, more terms make it worse, not better. Now set the centre a = 1 and look at x = 1.5: it is inside the new radius √2, and twelve terms give 0.30769 against the true 0.30769. Every polynomial has a root The fundamental theorem of algebra says every non-constant polynomial with complex coefficients has a root in the complex numbers. No real-number-only version holds: x² + 1 has none. Once you allow the plane, it never again fails; this is why it is called "algebraically closed", and why engineers can always factor a transfer function into first-degree pieces. Proof sketch · by Liouville's theorem Suppose a polynomial p never equals zero. Then 1/p is complex-differentiable on the entire plane. As |z| grows, |p| grows without limit, so 1/p heads to zero at large distances and is bounded everywhere. The real trick is Liouville's theorem: a bounded function that is differentiable on the entire plane must be constant. Then 1/p is constant, so p is constant, contradicting that p was non-constant. The theorem says roots exist; it does not say how to find them. One method from first-year calculus, Newton's method, takes on a new character in the plane. Start at a guess z, and update z ← z − f(z)/f′(z). For f(z) = z³ − 1 there are three roots, the three cube roots of 1: at 1, and at 120° and 240°. Which root does each starting point end up at? The map of answers is a fractal and the boundaries between the three basins are infinitely intricate. Tap the picture to start from a point. Interactive · Newton's method on z³ − 1 Start, real part Start, imaginary part Colour shows which root a start reaches within 40 steps (red: 1, green: the 120° root, blue: the 240° root). Brighter means fewer steps. Tap the map or use the sliders. The white dot is your start and the white line is its path. At 0 the derivative is 0, so Newton's method cannot take a step. Starting at 0.6 + 0.9i, the path takes 7 steps and lands on the 240° root, even though the 120° and the real root are nearer in the plane's geometry: the first step jumps to 0.29 + 0.34i and the second throws the point down to −0.06 − 1.44i. Nearby starts can end at a different root. Near a boundary, a tiny nudge changes the answer, and zooming in never makes the boundary simple. What a graduate just sees Multiplying complex numbers is scaling and turning; i is a quarter-turn and i² = −1 is two of them. Complex-differentiable means locally a stretch and a turn, which is why such maps preserve angles. Integrals around loops forget the loop's shape; only the poles inside matter, through their residues. A real integral that looks hopeless often falls to a detour through the upper half-plane. A power series dies at the nearest pole, even one that sits off the real line where you can't see it. Every polynomial factors completely over the complex numbers. Where it shows up next Signals and Systems (34/37): the Fourier and Laplace transforms live on complex frequencies, and the poles of a transfer function say whether a system rings, settles or explodes. Quantum Mechanics (34/83): amplitudes are complex numbers whose phases interfere, and the evolution of a state is multiplication by a turning factor. Partial Differential Equations (34/79): the real and imaginary parts of a differentiable function solve Laplace's equation, so conformal maps solve problems of heat, electric potential and ideal fluid flow. Number Theory (34/75): the Riemann zeta function is a function on the complex plane, and the location of its zeros controls how the primes are spread. In the world: AC circuit analysis with phasors and aerofoil theory by conformal maps. If you want to go deeper 📘 Textbook. Elias Stein and Rami Shakarchi, Complex Analysis (Princeton Lectures in Analysis II, Princeton University Press, 2003). Rigorous and elegant, the standard upper-level proof-based text. 📘 Textbook. James Ward Brown and Ruel Churchill, Complex Variables and Applications (McGraw-Hill, 9th edition). The standard text for the methods-and-applications version, heavy on residue integrals. 📘 Gentler. Tristan Needham, Visual Complex Analysis (Oxford University Press, 1997; a 25th anniversary edition appeared in 2023). Proves everything with pictures, and is the best match to the stretch-and-turn view in this piece. 🌐 Free course. MIT OpenCourseWare 18.04 Complex Variables with Applications (Spring 2018, Jeremy Orloff), with notes and problem sets. The takeaway Let the variable live on a plane and "differentiable" shrinks to "only a stretch and a turn". That strictness buys miracles: loop integrals that forget their path and see only poles, series whose width is the distance to hidden trouble, a real integral done by a detour, and a root for every polynomial. Try this: this week, take a smooth function you know, such as 1/(1 + x²), and ask where it would break if x could be any complex number. The answer tells you what its series, its integrals and its behaviour far from zero will do. Sources & Further Reading Sources. The Cauchy–Riemann equations, Cauchy's theorem, the residue theorem, Liouville's theorem and the fundamental theorem of algebra are standard (Stein & Shakarchi, ch. 1–3; Brown & Churchill). Course contents: MIT OCW 18.04 page (Spring 2018). Every number an interactive shows was computed in node: (1+i)² = 2i; f′(0.7+0.5i) = 1.4+1.0i, modulus 1.7205, argument 35.54°; line integral 2·arctan(3) = 2.4981 plus arc gives π to 10 digits; ∫dx/(1+x⁴) = π/√2 = 2.2214; Taylor sums at a = 0, x = 0.8: 12 terms 0.5679, 40 terms 0.60968, true 0.60976; x = 1.5, 12 terms −39.6, 30 terms 59,000; a = 1, x = 1.5, 12 terms 0.307693 vs 0.307692; arc at R = 3 is 0.6435, at R = 40 is 0.04999; Newton from 0.6+0.9i reaches the 240° root in 7 steps. The Taylor-series and radius example is the standard textbook one. 🌐 MIT OCW 18.04 Complex Variables with Applications 📘 Stein & Shakarchi, Complex Analysis 📘 Needham, Visual Complex Analysis Step 12. Number Theory: Primes, Clocks and the Secrets Built on Them -------------------------------------------------------------------- Why: Primes, divisibility and the oldest open questions. The whole numbers 1, 2, 3, … look like the simplest thing in mathematics, and hide the hardest questions. The same ideas that settle them also lock every web browser's connection. When you open a padlock icon in your browser, your device and a server that has never met you agree on a shared secret, in public, in a few milliseconds. The agreement rests on a fact so plain a child can state it: multiplying two big prime numbers is easy, and finding which two primes were multiplied is, as far as anyone knows, very hard. Take two primes of a thousand digits each and a laptop multiplies them instantly. Hand someone the product and ask for the pair, and every method we have takes longer than the age of the universe. That asymmetry is old, pure mathematics. It comes from the oldest corner of the subject, number theory: the study of whole numbers, their divisors and their primes. A graduate's relationship to a number like 1001 changes for life. It is no longer "one thousand and one"; it is 7 × 11 × 13, and that splitting is the number's fingerprint. Number theory is also the field with the largest gap between how easy a question is to state and how hard it is to answer. This piece builds six ideas you can play with, each with a proof sketch, and ends with the open problems that have outlived everyone who has tried them. The course in one box Who takes itMathematics majors, usually in year 2 or 3, and many computer scientists as an elective for cryptography. MIT's 18.781 Theory of Numbers is an undergraduate course in the mathematics department. Programmes differ: some teach an elementary version, others add algebraic and analytic number theory later. What it is forUnderstanding the whole numbers through divisibility and primes, and using that structure for codes, error correction and proof. Comes afterAbstract Algebra (34/73): groups and rings are the language the course quietly speaks. Leads toIt is a terminus in this series, and a doorway to advanced courses beyond it, but it feeds Computer Security (34/33), Theory of Computation (34/29), Algorithms (34/24) and, through the Riemann zeta function, Complex Analysis (34/74). What this piece gives youYou will not be able to prove the prime number theorem. You will see Euclid's algorithm run, why there are infinitely many primes, why every number has one prime fingerprint, how clock arithmetic gives inverses, and how a toy version of RSA works, with every number computed live. Easier first reads: Cryptography: The Math That Keeps Your Secrets (12/09) and The Most Beautiful Ideas in Math (12/04). This one goes further and makes you do the calculation. Euclid's algorithm: the greatest common divisor in a few lines How do you find the biggest number that divides both 1071 and 462? Factoring both works for small numbers. Euclid's method, written around 300 BCE in the Elements and still used in computers today, works for any size and needs no factoring at all. Divide the larger by the smaller and keep the remainder. Then repeat with the smaller number and that remainder, until the remainder is zero. The last non-zero remainder is the answer. gcd(a, b) = gcd(b, a mod b)the greatest common divisor does not change when you replace the pair by (smaller, remainder) Proof sketch · why the remainder is safe to use Write a = q·b + r. If d divides both a and b, then d divides r = a − q·b. Conversely, if d divides both b and r, it divides a = q·b + r. The real trick is that the two pairs (a, b) and (b, r) have exactly the same common divisors, so they have the same greatest one. And since the remainder is always smaller than b, the numbers shrink and must hit zero. Run on 1071 and 462: 1071 = 2·462 + 147, then 462 = 3·147 + 21, then 147 = 7·21 + 0. The answer is 21. Better, running the steps backwards expresses 21 as a combination of the two starting numbers: 21 = 1071·(−3) + 462·7. That identity, Bézout's identity, is the engine of everything later: it is how you find inverses in clock arithmetic and how RSA computes its secret key. Interactive · Euclid's algorithm, step by step 1071, 462 Fibonacci pair (slowest) Neighbours a b Each row is one division. The last line is Bézout's identity from the extended algorithm. The Fibonacci pair is the worst case for its size: every quotient is 1, so it takes the most steps. Notice how few steps it takes. For numbers with a thousand digits Euclid's algorithm takes a few thousand steps at most, because the remainder at least halves every two steps. That speed, versus the impossible slowness of factoring, is the first half of the cryptography story. There are infinitely many primes, and they thin out predictably A prime is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13, …. Every other number above 1 is a product of primes. A natural question: does the list ever stop? Proof sketch · Euclid's argument, about 300 BCE Suppose there were only finitely many primes, say p₁, p₂, …, pk. Multiply them all and add one: N = p₁p₂⋯pk + 1. N has some prime factor, because every number above 1 does. That factor cannot be any pi, because dividing N by pi leaves remainder 1. So there is a prime not on the list. Contradiction. The real trick is the "+1", which guarantees a remainder of 1 against every prime on the list. A common mistake: N itself need not be prime. With the first six primes, 2·3·5·7·11·13 + 1 = 30,031 = 59 × 509. It is not prime, but both its factors are new primes, which is all the proof needs. To find primes, the ancient method is the sieve of Eratosthenes: write the numbers out, cross off multiples of 2, then of 3, then of 5, and so on. Whatever is never crossed off is prime. You can stop early, because every composite number up to N has a prime factor no bigger than √N. For N = 100 that means sieving only with 2, 3, 5 and 7. Interactive · The sieve for 1 to 100 Cross off multiples of the first … primes Blue: still standing. Grey: crossed off (1 starts grey because it is not prime). After 2, 3, 5 and 7 are used, exactly the primes remain: there are 25 of them below 100. How common are primes? There are 25 below 100, 168 below 1,000, 1,229 below 10,000 and 9,592 below 100,000. They thin out, but in a pattern: near N, roughly one number in ln N is prime, where ln is the natural logarithm. This is the prime number theorem, proved independently by Hadamard and de la Vallée Poussin in 1896: the count of primes up to N is about N ÷ ln N, with the ratio tending to 1 (slowly). Interactive · How thin do primes get? Count primes up to N The count is a fresh sieve run in your browser each time. The ratio of the true count to N ÷ ln N falls slowly toward 1. At N = 100,000, the true count is 9,592 against the estimate 8,686: a ratio of 1.104. The estimate improves, but only like 1/ln N, which is a snail's pace. The exact size of the error is what the Riemann hypothesis is about, in the last section. Every number has one prime fingerprint Here is a fact so familiar you never question it: every whole number above 1 splits into primes in exactly one way, apart from the order. 360 = 2³ · 3² · 5, and nothing else. This is the fundamental theorem of arithmetic. Its uniqueness is what lets you treat the prime exponents as a number's coordinates, and from them read off everything: how many divisors, which numbers it shares factors with, whether it is a perfect square (all exponents even). Proof sketch · why √2 is irrational, by counting 2s Suppose √2 = a/b. Then a² = 2b². Look at the exponent of the prime 2 on each side. In a² it is twice the exponent of 2 in a: an even number. In 2b² it is one more than twice the exponent in b: an odd number. A number cannot have both an even and an odd count of 2s, because the factorisation is unique. The real trick is uniqueness of the prime fingerprint; without it, the two counts could differ without contradiction. Uniqueness is not automatic. In the number system built from √−5 (numbers a + b√−5), 6 = 2 × 3 = (1 + √−5)(1 − √−5), and all four factors are irreducible there. Unique factorisation fails. This is why nineteenth-century attempts at Fermat's Last Theorem stumbled, and why algebra (34/73) grew the idea of "ideals": to repair the lost uniqueness. Try a number yourself. Interactive · The prime fingerprint 360 1001 999983 1,048,576 Number n (2 to 10,000,000) Trial division by every number up to √n. For n with exponents e₁, e₂, …, the divisor count is (e₁+1)(e₂+1)⋯, and Euler's φ(n) counts the numbers up to n sharing no factor with n. For 360 = 2³·3²·5 the divisor count is 4 × 3 × 2 = 24, and φ(360) = 96. 999,983 is the largest prime below a million: the factoriser tries every candidate up to 999 and finds none. 1,048,576 is 2²⁰, a perfect square because the exponent is even. Clock arithmetic: working modulo n It is 10 o'clock. What time is it in 5 hours? Not 15: it is 3. On a clock you add and then keep only the remainder after dividing by 12. Mathematicians write 15 ≡ 3 (mod 12) and call it congruence. You can add, subtract and multiply this way and everything still works. The interesting question is division. When can you undo a multiplication on the clock? On a 12-hour clock, multiplying by 5 can be undone: 5 × 5 = 25 ≡ 1, so 5 is its own inverse. Multiplying by 4 cannot: 4 × 3 = 12 ≡ 0, and information is lost. The rule is exactly Euclid: a has an inverse mod n ⟺ gcd(a, n) = 1and Bézout's identity a·x + n·y = 1 hands you the inverse: x Proof sketch · from Euclid to inverses If gcd(a, n) = 1, Bézout gives integers x and y with a·x + n·y = 1. Reduce mod n: the n·y term vanishes, so a·x ≡ 1, and x is the inverse. If instead d = gcd(a, n) > 1, every multiple of a is a multiple of d, so it can never be 1 mod n. The real trick is reading Bézout's equation mod n. This is group theory arriving without announcement: the numbers coprime to n form a group under multiplication, with φ(n) elements. Mod a prime, every nonzero number has an inverse, so clock arithmetic becomes a field. Play with the multiplication table. Interactive · The multiplication table mod n Modulus n Row a Green cells: products that equal 1, so the two factors are inverses. Orange cells: a non-zero times a non-zero giving 0. Those can only appear when n is not prime. The ringed row is your a. At n = 12, a = 5: the row 5·k mod 12 for k = 0 to 11 hits 1 at k = 5, so 5 is its own inverse; there are φ(12) = 4 invertible numbers (1, 5, 7, 11) and plenty of orange cells. Switch to n = 13 and every nonzero row hits 1 exactly once, and there are no orange cells. Fermat, Euler and RSA: easy to multiply, hard to undo Fermat noticed in the 1600s that if p is prime and a is not a multiple of p, then raising a to the power p − 1 always lands on 1 mod p. ap−1 ≡ 1 (mod p)Fermat's little theorem, for prime p and a not divisible by p Proof sketch · multiplication shuffles the numbers Take the numbers 1, 2, …, p − 1 and multiply each by a, mod p. The results are all different (a has an inverse, so no two collide) and none is 0, so you get the same list in a different order. Multiply all of both lists together: ap−1·(p − 1)! ≡ (p − 1)!. The real trick is that multiplying by an invertible element only permutes the list. Cancel the (p − 1)! (also invertible) and what remains is ap−1 ≡ 1. Euler generalised it to any modulus n: aφ(n) ≡ 1 when gcd(a, n) = 1. That is Lagrange's theorem from group theory in costume. RSA, published in 1977 by Rivest, Shamir and Adleman, turns it into a lock. Pick two primes p and q and publish n = p·q. Choose a public exponent e coprime with φ(n) = (p − 1)(q − 1). Anyone can encrypt a message m as me mod n. Only someone who knows p and q can compute φ(n), and so the inverse d with e·d ≡ 1 mod φ(n), and decrypt by cd mod n. It works because med = m1 + kφ(n) = m · (mφ(n))k ≡ m by Euler. Play with a toy lock. The primes here are tiny, so an attacker can factor n in a flash; real keys use primes hundreds of digits long. Interactive · A toy RSA lock Prime p Prime q Message m Computed with exact big-integer arithmetic. e is the smallest odd number from 3 up that is coprime with φ(n); d comes from the extended Euclidean algorithm. The attacker's cost is the number of odd trial divisions before the smaller prime is found. With p = 19 and q = 41, n = 779, φ = 720 and the first valid e is 7, giving d = 103. The message 42 encrypts to 42⁷ mod 779 = 329, and 329 to the power 103 mod 779 gives 42 back. Finding the smaller prime by trial division takes only 9 tries. A 2,048-bit modulus, a typical size for RSA keys today, has 617 decimal digits. At that size, trial division would need around 10³⁰⁰ steps, and the best factoring methods, which are far cleverer, are still hopelessly out of reach for a well-chosen 2,048-bit key. No one has proved factoring is hard; only that nobody has found a fast method on ordinary computers. (Shor's 1994 quantum algorithm would factor quickly on a large, error-corrected quantum computer, which does not exist yet.) Simple questions nobody can answer: Goldbach, twins and Riemann Number theory is full of questions a ten-year-old can read and the best mathematicians cannot answer. Here is the status of the famous ones. ProblemSaysStatus Goldbach (1742)Every even number above 2 is a sum of two primesOpen. Checked by computer up to 4 × 10¹⁸ (2013, published 2014) Twin primesInfinitely many pairs p, p + 2Open. In 2013 Zhang proved infinitely many pairs within 70 million of each other; a collaborative project cut that to 246 Riemann hypothesis (1859)The zeros of the zeta function lie on one line, which pins down how primes are spreadOpen. A Clay Millennium Problem with a US$1 million prize (2000) Fermat's Last TheoremNo whole-number solutions to xⁿ + yⁿ = zⁿ for n > 2Proved: Wiles announced in 1993, a gap was repaired with Richard Taylor in 1994, published 1995 Goldbach is easy to watch. For each even number n, count the ways to write it as a sum of two primes. The count does not go to zero, and in fact tends to grow, though ragged: a famous "comet" shape. Interactive · The Goldbach comet Even number n Each dot is one even number: how many ways it splits into two primes. The orange dot is your n. Seeing it hold for n up to 2,000 proves nothing; the theorem is about all of them. For n = 100 there are 6 ways (3 + 97, 11 + 89, 17 + 83, 29 + 71, 41 + 59, 47 + 53). For n = 4 and n = 6 there is exactly 1, the smallest the count ever gets; for n = 2,000 there are 37. The lower edge of the comet rises, which is why Goldbach is believed true. Believing is not proving. The Riemann hypothesis connects back to the prime-counting estimate above. The zeta function ζ(s) = 1 + 1/2s + 1/3s + … is secretly a statement about primes, because unique factorisation turns the sum into a product over primes. Its complex zeros control how far the true count of primes strays from N ÷ ln N. The hypothesis says the error is as small as it can be. What a graduate just sees Every number is a product of primes in exactly one way; its factorisation is its fingerprint. Euclid's algorithm finds a gcd with no factoring, and running it backwards gives Bézout's identity. There are infinitely many primes, they thin out like 1 in ln N, and no simple formula produces them. Working mod n means keeping only remainders; a has an inverse mod n exactly when gcd(a, n) = 1. Multiplying big primes is easy and unmultiplying is not known to be: all of public-key cryptography stands on that gap. Statements checked for a trillion cases can still be unproved; verification is not a proof. Where it shows up next Computer Security (34/33): RSA, Diffie–Hellman and elliptic-curve cryptography are number theory with a key length. Theory of Computation (34/29) and Algorithms (34/24): primality testing and factoring are the textbook cases of problems whose difficulty is subtle, and Shor's quantum algorithm is a number-theory idea. Abstract Algebra (34/73): the units mod n are a group, and prime moduli give fields; Fermat's little theorem is Lagrange's theorem in disguise. Complex Analysis (34/74): the Riemann zeta function is the bridge between primes and the complex plane. In the world: HTTPS and digital signatures, error-correcting codes in phones and QR codes (finite fields), check digits on ISBNs and bank accounts (modular arithmetic), and the 41-million-digit Mersenne prime 2136,279,841 − 1 found in October 2024 by the volunteer GIMPS project, the largest prime known when this piece was written (late 2026). If you want to go deeper 📘 Textbook. Kenneth Rosen, Elementary Number Theory and Its Applications (Pearson). A common first text; clear, with plenty of cryptography. 📘 Textbook. G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers (Oxford University Press, 6th edition, 2008). The classic: a mathematician's tour, slower to read and richer in ideas. 📘 Gentler. Simon Singh, Fermat's Enigma (1997), the story of Wiles and Fermat's Last Theorem for a general reader. Almost no formulas. 🌐 Free course. MIT OpenCourseWare 18.781 Theory of Numbers (Spring 2012, Abhinav Kumar), with lecture notes and problem sets. The takeaway Whole numbers have a hidden skeleton of primes, and Euclid's algorithm lets you reach in and use it without ever factoring. Clock arithmetic turns divisibility into group theory, and the gap between multiplying and factoring locks your messages. Meanwhile some of the simplest-sounding questions remain open after centuries. Try this: this week, take the number on a clock, a bus, a date or a price tag and factor it in your head. Spot which is divisible by 3 by adding its digits (why does that work mod 3?). Notice how often you reach for the fingerprint. Sources & Further Reading Sources. The theorems are standard (Hardy & Wright; Rosen; Ireland & Rosen). The prime number theorem (Hadamard and de la Vallée Poussin, 1896) is standard history. Goldbach checked to 4 × 10¹⁸: Oliveira e Silva, Herzog and Pardi, Mathematics of Computation 83 (2014). Bounded gaps: Zhang (2013; Annals 2014), Polymath8 reduced the bound to 246, per the project's retrospective on arXiv. Wiles: announced 1993, repaired with Taylor and published in Annals of Mathematics 1995. Largest known prime: 2^136,279,841 − 1, 41,024,320 digits, GIMPS, October 2024; no later record found in a search made for this piece. Course contents: MIT OCW 18.781 page. All numbers shown were computed in node: gcd(1071, 462) = 21 = 1071·(−3) + 462·7; π(100) = 25, π(1000) = 168, π(10⁴) = 1,229, π(10⁵) = 9,592; 2·3·5·7·11·13 + 1 = 30,031 = 59 × 509; φ(360) = 96; RSA with p = 19, q = 41: n = 779, e = 7, d = 103, 42 encrypts to 329 and decrypts to 42; Goldbach counts g(100) = 6, g(2000) = 37; 2,048 bits = 617 digits. 🌐 MIT OCW 18.781 Theory of Numbers 📘 Hardy & Wright, An Introduction to the Theory of Numbers 📘 Singh, Fermat's Enigma Step 13. Topology: Shape Without Measurement -------------------------------------------- Why: Shape without measurement: the doughnut and the coffee cup. Forget lengths, angles and distances. Keep only what survives stretching and bending without tearing. What is left is a handful of surprisingly powerful ideas, and a coffee cup that is secretly a doughnut. Look at the London Underground map. It is wrong about almost everything: distances, angles, even which station is north of which. Yet you can plan a journey with it perfectly, because the map keeps the one thing that matters for the journey: which stations connect to which. A map that gets the geometry wrong and the connections right is a topological map, and the reason it works is the reason this whole field exists. Topology asks what a shape is when you refuse to measure it. Imagine every object is made of perfectly stretchy rubber, and you may pull, squash and twist but never tear or glue. A sphere and a cube are the same. A coffee mug and a doughnut are the same, because you can squash the mug's body down into the doughnut's ring and the handle becomes the hole. A sphere and a doughnut are different, and no amount of stretching will change that. The graduate's trained question about any shape is: how many holes, of what kind, and can I prove it? This piece takes six ideas: counting with Euler, open sets, compactness, winding numbers, one-sided surfaces, and a modern use that finds holes in data. Each has a proof sketch and something to play with. The course in one box Who takes itMathematics majors, usually in year 3, and physicists headed for field theory or condensed matter. MIT's 18.901 Introduction to Topology (taught by James Munkres, whose textbook is the standard one) covers point-set topology and the fundamental group. Many programmes teach point-set topology first and algebraic topology in a second course. What it is forDefining continuity, closeness and shape without any ruler, then telling shapes apart by invariants such as holes. Comes afterReal Analysis (34/72), whose open sets, limits and compactness it generalises. Leads toNothing in this series requires it, but it underlies Differential Geometry (34/77), the geometry general relativity is written in, and it helps in Complex Analysis (34/74) and Quantum Mechanics (34/83). What this piece gives youYou will not be able to compute a fundamental group of a general space. You will see why a doughnut is not a sphere, what an open set is, why compactness matters, and how to count holes in data. Easier first read: Topology: The Shape of Space (12/10). This one goes further with proofs and computed counts. A mug is a doughnut: counting holes with Euler To tell shapes apart you need something that does not change when you stretch. Such a quantity is an invariant. The first one anyone found is a counting trick. Cover a surface with a net of corners (vertices V), edges (E) and faces (F), then compute V − E + F. For every solid built from flat faces without holes, this is 2. V − E + F = 2for any net drawn on a sphere; for a surface with g holes it is 2 − 2g A cube: 8 − 12 + 6 = 2. A tetrahedron: 4 − 6 + 4 = 2. An icosahedron: 12 − 30 + 20 = 2. Now cover a doughnut with a grid of squares, say 3 by 4: 12 vertices, 24 edges, 12 faces, and 12 − 24 + 12 = 0. Every grid on a torus gives 0, whatever its size. The number is a property of the surface, not of the net. Proof sketch · why a sphere always gives 2 Draw the net on a sphere. Pick a set of edges that connects all V vertices without making a loop: a spanning tree, which always has exactly V − 1 edges. Now draw a second net on the faces: put a dot in each face and connect two dots whenever their faces share an edge that is not in the tree. These dual edges form a connected tree with F dots, because the first tree has no loop and so cannot cut the sphere into pieces; it has F − 1 edges. Every edge of the original net is used exactly once, in one tree or the other: E = (V − 1) + (F − 1). The real trick is splitting the edges between a tree and its dual. Rearrange: V − E + F = 2. On a torus a tree-and-dual-tree split leaves two extra edges that go around the two ways of the hole, which is where the 0 comes from. Interactive · Count V − E + F Tetrahedron Cube Octahedron Dodecahedron Icosahedron Doughnut grid Doughnut grid: squares around Doughnut grid: squares through the hole Surface with g holes The solids are the five Platonic solids. The doughnut grid is an m × n net of squares on a torus: m·n vertices, 2·m·n edges, m·n faces. The last line uses the formula 2 − 2g. Change the grid and the answer stays 0. Move the hole slider: one hole gives 0, two holes give −2, three give −4. A surface whose Euler number differs from another's cannot be stretched into it, so a sphere (2) is never a doughnut (0), and a doughnut is never a two-holed pretzel (−2). A mug has one hole, so it matches the doughnut. Open sets: closeness without distance In real analysis, "close" means "within a small distance". Topology throws the ruler away and keeps only a list of which regions count as open. A set is open if every point in it has some breathing room: you can move a little in any direction and stay inside. On the number line, (0, 1) is open and [0, 1] is not, because standing at 1 you cannot step right without leaving. Any collection of subsets can be a topology if it passes three tests: the empty set and the whole space are in it, any union of open sets is open, and the intersection of any two (hence any finite number) of open sets is open. That is the entire definition. Everything else follows: a function is continuous when the set of inputs landing in any open set is itself open. No distances appear. Proof sketch · why intersections are only finite On the line, the open intervals (−1/n, 1/n) for n = 1, 2, 3, … are each open, but all of them at once intersect in just {0}: a single point, which is not open. The real trick is that an infinite intersection can squeeze open sets down to nothing with room to spare, so the axiom allows only finitely many. Unions have no such problem: a union only adds room. The payoff is flexibility. A set of three points {1, 2, 3} has 8 possible subsets. Choose which of them to call open and see if the choice is a legitimate topology. Interactive · Is this a topology on {1, 2, 3}? Everything open Only {} and the whole set A nested chain Two singletons, no union Tap a subset to toggle it. The page tests the three rules over all pairs and reports the first failure. "Separated" counts pairs of points that have disjoint open neighbourhoods; it tells you how fine the topology is. With every subset open ("discrete"), all three pairs of points are separated: each point sits in its own tiny island. With only {} and the whole set open ("trivial"), no pair is separated and no function that picks one point out is continuous. The "two singletons" preset fails: {1} and {2} are open but their union {1, 2} is missing. The nested chain is legitimate, but separates nothing: you can tell 1 from 2 only from one side. Compactness: when infinity can be tamed by finitely many pieces A cover of a set is a family of open sets whose union contains it. A set is compact when every cover has a finite subfamily that still covers it. In practice, in familiar spaces, compact means closed and bounded: [0, 1] is compact, (0, 1) and the whole line are not. This sounds like paperwork. It is the property that makes theorems true. The example that makes it concrete is (0, 1). Use the open sets Uk = (1/(k + 2), 1) for k = 0, 1, 2, …: that is (1/2, 1), then (1/3, 1), then (1/4, 1). Together they cover all of (0, 1), since any point is above some 1/(k + 2). But take any finite handful and the largest set in it still leaves an uncovered strip down by 0. No finite subfamily covers. Now add the endpoint, forming the closed interval [0, 1]: the point 0 needs a set around it, say V = (−w, w). Then V together with a single Uk covers everything once 1/(k + 2) < w. Two sets suffice. Proof sketch · why compactness gives a maximum A continuous function on [0, 1] attains its largest value. Suppose it did not. For each x, the sets where f < f(x) + 1 cover [0, 1]. Take a finite subcover: finitely many bounds, so f is bounded, and the least upper bound M is never reached. Then 1/(M − f) is continuous, hence bounded, which is absurd since f gets arbitrarily close to M. The real trick is that "finite" lets you take a maximum over the pieces. On (0, 1) the function 1/x has no maximum, precisely because (0, 1) is not compact. Interactive · Cover it with finitely many Use sets U₀ … UN−1 on (0, 1) Closed interval: width w of the set around 0 Top bar: the open interval (0, 1) with N of the sets. The orange strip is what is still uncovered, always between 0 and 1/(N + 1). Bottom bar: [0, 1] with V = (−w, w) plus one Uk. Slide w down to see the one Uk needed grow. With N = 5 sets, the union is (1/6, 1) = (0.167, 1) and the strip (0, 0.167] is left. With 200 sets the strip is (0, 0.0050] and still not empty; it never will be. In the closed case with w = 0.05, you need 1/(k + 2) < 0.05, so k + 2 > 20, so k = 19: just two sets, V and U19, cover [0, 1]. Loops that cannot shrink: the winding number Open sets tell you about closeness. To see holes, topologists use loops. Take a loop in the plane with one point removed. A loop that does not go round the missing point can be shrunk to nothing. A loop that goes once round it cannot: the missing point is in the way. Count how many times a loop circles the point, signed by direction, and you have the winding number. Proof sketch · why you cannot shrink a loop around a hole As you walk the loop, track the angle from the missing point to you; the winding number is the total angle gained divided by 2π. Deform the loop a little, and the total angle changes a little. But the winding number is always a whole number, and a whole number that changes only a little cannot change at all. The real trick is that an integer-valued quantity is rigid. It can jump only if the loop passes through the point, which is forbidden. So a loop with winding number 1 can never shrink to a point (winding number 0). That one fact proves Brouwer's fixed-point theorem in the plane: any continuous map of a disc to itself fixes some point. If it did not, you could build a continuous map pushing the whole disc onto its edge circle, leaving the edge fixed. That would shrink a winding-number-1 loop, on the edge, across the disc to a point, which is impossible. Interactive · Count the turns Circle once Circle twice Circle backwards Loop with an inner loop Figure eight Point, x Point, y The winding number is computed by summing the small signed angle changes seen from the point as you walk 2,000 steps around the curve, then dividing by 2π. If the point is within 0.03 of the curve, the number is not defined and the page says so. Circle once with the point at the centre: winding number 1. Slide the point outside the circle and it drops to 0. For the loop with an inner loop, the points in the small inner loop get 2, the points between get 1, outside gets 0. For the figure eight, one lobe gives +1 and the other −1: you walk one lobe clockwise and the other anticlockwise. The same number is Cauchy's integral from 74 in disguise: (1/2πi) ∮ dz/(z − p) counts exactly this. One-sided surfaces and the classification of surfaces Take a strip of paper, give one end a half-twist (flip it over), and tape the ends together. The result, a Möbius strip, has one side and one edge: an ant can walk along it and return upside down having never crossed an edge. The discoverers, August Möbius and Johann Listing, found it independently in 1858. A surface like this is non-orientable: you cannot consistently say which way is "up" across it. Every closed surface (no edge, finite) is built from the same few parts: a sphere with g handles added (g = 0 is the sphere, g = 1 the doughnut), or a sphere with some Möbius-style cross-caps added. That is the classification of closed surfaces: Euler number and orientability tell you which one you have. It is one of the few places in topology where the full answer is known and fits on a page. Proof sketch · counting laps to decide one side or two Imagine the strip with t half-twists. Walk along the edge once around. If t is even you come back to the same edge, and the strip has two edges and two sides. If t is odd you come back on the other edge, so you must go around twice to close up: one edge, one side. The real trick is that a half-twist swaps the two sides, and only the parity of the number of swaps matters. Interactive · Twist, glue, cut down the middle Half-twists t The strip is drawn unrolled, as seen from above, with its ends to be glued. Blue: front side showing. Orange: back showing. The counts come from simulating laps: a lap swaps the edges when t is odd. For t = 1 the readout says one edge, one side, and one piece after cutting along the middle. That piece is not a thinner Möbius strip. It is one band, twice as long, with two full twists. For t = 2 (a full twist, which is the same as no twist for sidedness) the cut gives two separate bands, linked once through each other. That a cut can turn one object into one longer one, or into two linked ones, depending on a parity, is a good taste of why topology is surprising. Three dimensions have a famous version of the classification. Henri Poincaré asked (in 1904, the date usually given) whether a closed 3-dimensional space with no holes (every loop shrinkable) must be the 3-sphere. The Poincaré conjecture was proved by Grigori Perelman in preprints posted in 2002 and 2003, building on Richard Hamilton's Ricci flow. The Clay Mathematics Institute named it one of seven Millennium Problems in 2000, and it remains the only one solved. Perelman declined both the Fields Medal (2006) and the million-dollar prize (2010). Seeing holes in data Modern applications ask a topologist's question of a cloud of dots: is it a ring? Two rings? A blob? Real data is noisy, so counting holes in the dots is not enough. The method of persistent homology grows a ball of radius ε around every point and joins any pair of points whose balls touch (two points within distance ε). Triples that are all joined get filled in. As ε grows, components merge and holes appear and fill. A true feature survives across a wide range of ε; noise appears and vanishes in a flash. The counts are the Betti numbers: β₀ is the number of connected pieces, β₁ the number of independent loops (holes). The page computes them exactly, from the matrices of the joined-up shape, with arithmetic mod 2. Interactive · Hunt for the hole Noisy ring Two rings Random blob Join points closer than ε Illustrative data: points on circles with small deterministic jitter, or scattered in a disc. Edges join points closer than ε; every triangle whose three sides are present counts as filled. β₁ = (edges − rank of the edge-vertex map) − rank of the triangle-edge map, found by exact elimination over mod-2 arithmetic. For the ring of 16 points, the neighbouring points are 0.39 apart. As ε crosses about 0.42 everything connects (β₀ drops to 1) and one hole (β₁ = 1) appears. It stays until ε reaches about 1.82, when triangles fill the middle. That long life is the signal: this cloud is a ring. For the random blob the holes that pop up near ε = 0.70 and 0.84 last only about 0.1 each: noise. What a graduate just sees Shape is what survives stretching without tearing; distances and angles are not part of it. A mug is a doughnut because both have one hole; a sphere has none, so it is a different thing. Counting trick: V − E + F is 2 on a sphere and 2 − 2g on a surface with g holes, however you draw the net. "Open" is the primitive idea; continuity, limits and closeness are all built from it. Compact means any infinite cover can be cut down to a finite one, which is why maxima exist. A whole number that cannot change continuously is a rigid invariant: winding numbers prove loops cannot shrink. A twist can turn two sides into one; orientability is a yes-or-no question about a space. In data, real holes are long-lived and noise is short-lived. Where it shows up next Differential Geometry (34/77): add smooth structure to topological spaces to get manifolds, the stage on which general relativity is played; the Euler number reappears as total curvature. Complex Analysis (34/74): the winding number is the count inside Cauchy's integral, and the residue theorem is topology in disguise. Quantum Mechanics (34/83) and Condensed Matter Physics (34/87): topological phases of matter are classified by integer invariants that cannot change without a transition. Real Analysis (34/72): compactness is the idea behind the extreme value theorem and the Heine–Borel theorem. In the world: network maps (the Underground map), robot motion planning around obstacles, DNA knotting, and topological data analysis of shapes in biology. If you want to go deeper 📘 Textbook. James Munkres, Topology (Pearson, 2nd edition, 2000). The standard point-set text, with a second half on the fundamental group. 📘 Textbook. Allen Hatcher, Algebraic Topology (Cambridge University Press, 2002). Freely available from the author's Cornell website; the usual next step. 📘 Gentler. Michael Henle, A Combinatorial Introduction to Topology (Dover reprint). Surfaces and knots with no point-set machinery. 🌐 Free course. MIT OpenCourseWare 18.901 Introduction to Topology (Fall 2004, James Munkres). The takeaway Topology throws the ruler away and keeps only closeness, then finds integers that cannot change under stretching: Euler numbers, winding numbers, counts of holes. Those integers are rigid, which is what lets them prove that two shapes differ, that a loop cannot shrink, and that a ring in noisy data is real. Try this: this week, look at a subway or train map and a real street map of the same city side by side. List what the schematic one throws away and what it keeps. Then count the holes in a pair of scissors, a pretzel and a teapot. Sources & Further Reading Sources. The topology axioms, compactness, winding numbers, Brouwer's theorem, classification of surfaces and persistent homology are standard (Munkres; Hatcher). Möbius and Listing found the strip in 1858 (standard history; see MacTutor). Poincaré conjecture: posed 1904, Perelman's preprints 2002 and 2003; Clay Millennium Problems named 2000; Fields Medal 2006 and the prize in 2010 both declined (Clay Mathematics Institute). Course contents: MIT OCW 18.901 page (Munkres, Fall 2004). Every number an interactive shows was computed in node: Euler numbers of the solids; torus grids always give 0; the cover of (0, 1) leaves (0, 1/(N + 1)]; w = 0.05 needs U₁₉; winding numbers by summed angle; ring of 16 points has 0.39 spacing, β₁ = 1 for ε from 0.42 to 1.82; blob holes at ε ≈ 0.70 and 0.84. 🌐 MIT OCW 18.901 Introduction to Topology 📘 Munkres, Topology 📘 Hatcher, Algebraic Topology Step 14. Partial Differential Equations: One Law for Every Point of a Field --------------------------------------------------------------------------- Why: The equations of heat, waves and quantum mechanics. A guitar string, a cooling pizza, an electric field, an electron in an atom and the air over a wing all obey one kind of statement: how a quantity changes at a point depends on how it is shaped around that point. Three families of equation cover most of physics. Pluck a guitar string and it sings a note and a tangle of fainter overtones. Pull a hot pizza from the oven and the crust cools long before the middle. Hang a wire between two hot and cold ends and, after a while, the temperature settles into a smooth ramp that never changes again. Three everyday scenes, three very different behaviours: something that rings and travels, something that smooths out and forgets, something that has settled and stays. The remarkable thing is that one idea writes all three down. Where an ordinary differential equation follows one quantity through time, a partial differential equation (PDE) follows a whole field: temperature at every point of the pizza, displacement at every point of the string. And the key quantity in all of them is the same: how the field curves in space. A peak with sharply curved top, a gentle ramp with none. As of the Clay Mathematics Institute's list, announced in 2000, whether the Navier–Stokes equations of fluid flow always have smooth solutions in three dimensions is still one of the seven Millennium Prize problems, worth one million dollars. A PDE course will not solve it, but it will show why even a one-line equation can be this hard. The course in one box Who takes it: Mathematics and Physics majors, typically in the third year, after multivariable calculus and ordinary differential equations. MIT teaches an undergraduate course on linear PDEs, analysis and numerics (18.303), and Cambridge's Tripos covers the classical equations in its methods courses. Engineers meet a lighter version earlier. What it is for: predicting how a field evolves or settles from a local rule plus its starting values and boundaries. Comes after: Multivariable Calculus (34/02) and Differential Equations (34/03). Leads to: Quantum Mechanics (34/83), where the Schrödinger equation is a PDE. It also underlies Electromagnetics and Waves (34/38), Heat Transfer (34/16) and Fluid Mechanics (34/15). Honest line: you will not solve a PDE on a strange shape. You will see how heat, waves and equilibrium differ, why sums of simple modes solve them, and why simulating them is a craft. Easier first reads: Differential Equations (34/03, a first glimpse of the heat equation), The Fourier Transform (12/12), Waves and Sound (13/13). Heat spreads, waves travel, and three kinds of equation Take a lump of heat on a long rod, or a lump of displacement on a long string, and ask what each equation does to it. heat: ∂u/∂t = α ∂²u/∂x²    wave: ∂²u/∂t² = c² ∂²u/∂x² The heat equation is first order in time: its curvature tells the temperature how fast to change, so a peak sinks and a dip fills. The wave equation is second order in time: curvature tells the field how fast its velocity changes, like a spring, so a bump does not sink but sets off a ripple. Add a third, Laplace's equation ∂²u/∂x² + ∂²u/∂y² = 0, in which time is absent altogether: it describes what is left when everything has settled. These are called parabolic, hyperbolic and elliptic, after the shapes of the curves Ax² + Bxy + Cy² = 1 whose coefficients A, B, C appear in the equation. For second-order equations, the sign of B² − 4AC sorts them: positive hyperbolic (wave), zero parabolic (heat), negative elliptic (Laplace). Interactive · The same lump, two laws Time Proof sketch: d'Alembert's solution of the wave equation. Change to coordinates that ride with the waves: ξ = x − ct and η = x + ct. In those coordinates the equation becomes ∂²u/∂ξ∂η = 0. Nothing depends on ξ after differentiating by η, so the solution is a function of ξ plus a function of η, u = F(x − ct) + G(x + ct): a shape moving right plus a shape moving left. The real trick is the change of variables. Jean le Rond d'Alembert found it for the vibrating string in 1747. For a lump starting at rest, the two shapes are half-size copies, exactly what the gold curve shows. No such pair of copies exists for heat: the lump sinks and widens, and its area stays the same. A plucked string is a chorus of standing waves A guitar string is pinned at both ends, so not every shape can ring steadily. Only some can: one hump, two humps with a still point in the middle, three humps, and so on. These standing waves or modes have frequencies in the ratio 1 : 2 : 3 : …, the harmonic series of music. Any starting shape, however jagged, can be built from them. u(x, t) = Σ bn sin(nπx/L) cos(nπct/L) Proof sketch: separation of variables. Guess a solution that is a product, u = X(x)T(t). Put it into the wave equation and divide by XT: the left side, X″/X, depends on x alone, and the right side, T″/(c²T), on t alone. A function of x alone can equal a function of t alone only if both are the same constant, say −k². Then X″ = −k²X, so X is a sine. Pinned ends force sin(kL) = 0, so k = nπ/L: only whole-number humps survive. The real trick is that last step: the boundary conditions pick out a discrete list of modes. A sum of solutions is again a solution, because the equation is linear, so you add the modes up with weights bn to match the starting pluck. Interactive · Build the pluck from its harmonics Where you pluck Harmonics included Time Add harmonics one at a time and the rounded blob sharpens into the triangle of the pluck; one is not enough, and six already look close. Pluck at the exact middle and every even harmonic vanishes, because the string is held at a node of each; pluck near the end and many overtones appear, which is why a guitar sounds brighter, thinner and more nasal near the bridge. Move the time slider and each harmonic advances at its own speed, so after half a period the whole shape has flipped upside down. This was not obvious to the people who first met it. D'Alembert and Euler, in the late 1740s, argued over which starting shapes the equation allowed, and Daniel Bernoulli proposed around 1750 that every motion was a sum of sines. The dispute ran for decades. Joseph Fourier's treatise on heat (1822) put sums of sines on firm ground as a general tool. Diffusion forgets: you cannot run heat backwards Put the same sine-mode recipe into the heat equation and a new thing happens. Each mode decays instead of oscillating, and mode n decays by a factor e−n²π²t (for a rod of unit length and unit diffusivity). The factor involves n squared, so wiggles die far faster than broad shapes. After a short time only the smooth parts of the starting temperature remain; the sharp detail is gone. mode n after time t = (its starting strength) × e−n²π²t Now try to go backwards: given the temperature today, what was it earlier? You must divide each mode by that decay factor, which means multiplying by en²π²t. For t = 0.01, mode 5 is boosted about 12 times, mode 10 about 19,000 times and mode 20 by about 1017. Any measurement error in the high modes is blown up by that factor. Proof sketch: there is nothing more than that exponential. The real trick is seeing that forward evolution is a smoothing operation that destroys information, and inverting it must therefore create enormous amplification of noise. Jacques Hadamard called a problem well-posed (1902) if a solution exists, is unique and depends continuously on the data; the backward heat problem fails the third test. Interactive · Try to un-cool a rod Time elapsed Measurement noise The starting temperature here is a hot rod with cold ends. With barely any noise and a short time, the recovery is close; wait longer or add a speck of noise, and the blue curve becomes a violent zigzag that bears no relation to the truth. This is the mathematical face of the arrow of time (see Entropy, 13/12): the forward direction is stable, and the backward is hopeless. It matters in practice, too: deblurring a photograph, or finding where a pollutant came from, are inverse problems with the same disease, which is why they need regularisation, a method of damping the highest modes on purpose. At equilibrium every point is the average of its neighbours Let the heat equation run for a long time with the edges of a plate held at fixed temperatures. The temperature stops changing, and at that point its time derivative is zero: what is left obeys Laplace's equation. Its meaning in plain words is that each point equals the average of the points around it. A point hotter than its neighbours would cool; a colder one would warm; at rest, none is out of line. The same equation rules the electrostatic potential in empty space, the flow of an ideal fluid and the shape of a soap film over a wire frame, when it is nearly flat. ∂²u/∂x² + ∂²u/∂y² = 0   ⟺   u(centre) = average of u on any circle round it Proof sketch: no hot spots inside. Suppose the largest value of u sat strictly inside the plate. That value is the average of its neighbours, none of which can exceed it, so all of them must equal it. Repeat for each neighbour and the maximum spreads out until it reaches the boundary. So the maximum (and likewise the minimum) lives on the edge: this is the maximum principle. The real trick is to use the averaging property twice. It also gives a second payoff: a square plate with four edges at four different temperatures has a centre that is exactly the average of the four, because rotating the plate by 90 degrees swaps the edges, and the solutions simply add. Interactive · Relax a hot plate to equilibrium Top edge Bottom edge Left edge Right edge Averaging sweeps The simulation does exactly what the equation says: it repeatedly replaces each interior cell by the average of its four neighbours, starting from a cold plate. Heat creeps in from the edges, slowly at first, and takes a few hundred sweeps to settle on this small grid; on a finer grid it takes many more, which is a hint of why large simulations need cleverer solvers. A simulation must let information cross each cell Put these equations on a computer and you replace the smooth field by values on a grid, stepping through time. 34/78 (Numerical Analysis) showed that stepping can explode; for PDEs it has a neat geometric explanation. Take the simplest wave: a shape sliding right at speed 1, ∂u/∂t + ∂u/∂x = 0. The upwind scheme updates each cell using its left neighbour: uinew = ui − ν (ui − ui−1),   ν = speed × time step ÷ cell width The number ν is the Courant number: the fraction of a cell the real wave travels in one step. Proof sketch. The true value at a point at the next time depends on the value one wave-travel upstream, which is ν cells to the left. If ν > 1 the true source lies more than one cell away, but the scheme only ever looks one cell to the left: it ignores the very information it needs, and the result cannot converge. The real trick is the idea of a domain of dependence. Richard Courant, Kurt Friedrichs and Hans Lewy published this necessary condition in 1928, in Mathematische Annalen; it is now the CFL condition. Interactive · March a pulse across a grid Square pulse Smooth bump Courant number ν At ν = 1 the scheme is exact, each step moving the pulse one cell. Below 1 it is stable but the pulse smears: the scheme secretly solves the exact equation plus a little diffusion, with a coefficient of about ½(1 − ν) times the cell width. Above 1 the shortest wavelengths are multiplied by |1 − 2ν| each step, which exceeds 1, and the numbers grow without bound; by ν = 1.2 the highest value is above 105 after 42 steps. The same kind of limit applied to the explicit heat equation in 34/03, where the time step had to stay below half the cell width squared. The same trick quantises the electron in a box Erwin Schrödinger's equation of 1926 looks different from the wave equation, with an i in it and only one time derivative: iħ ∂ψ/∂t = −(ħ²/2m) ∂²ψ/∂x²   (free particle in a box) But the method is identical. Separate variables, ψ = X(x)T(t), and the space part must again be a sine that vanishes at the walls, so only whole numbers of humps fit. Now the boundary condition does something stunning: it allows only a discrete ladder of energies, En = n²h²/8mL². This is quantisation, and it has the same proof as the guitar string's harmonics. The time part is just a spinning phase, so a single mode has a probability density |ψ|² that never changes: nothing visibly moves until you mix two modes, and then the density sloshes back and forth at the beat frequency set by their energy gap. Interactive · Two energy levels in a box Width of box Mix of level 1 and 2 Time For an electron in a box 1 nm wide (about the size of a few atoms), the lowest energy is 0.376 eV, the next 1.504 eV, the third 3.384 eV: each is n² times the first, using CODATA values for Planck's constant and the electron mass. Mixing the first two makes the electron slosh from one side to the other every 3.67 femtoseconds, some 270 trillion times a second. Narrow the box and the energies, and so the sloshing speed, rise sharply: confinement costs energy, a first taste of why chips shrink into the quantum regime (Quantum Mechanics, 34/83). What ψ means is a matter of real disagreement between interpretations (Copenhagen, many-worlds, pilot-wave), but all of them use these same numbers. What a graduate just sees A PDE says how a field changes at a point from how it is curved around the point. Heat smooths and forgets, waves carry shape without losing it, Laplace describes what is left at rest: the three families behave differently. Separation of variables turns a PDE into simpler pieces, and boundaries pick out discrete modes: harmonics of a string, energy levels of an atom. Linear problems add up: any shape is a sum of modes, and each evolves on its own. Diffusion destroys detail exponentially fast, so running it backwards amplifies noise: some problems are ill-posed. At equilibrium each point is the average of its neighbours, so extremes live on the boundary. A numerical scheme must look where the information comes from: step size and cell size are linked by CFL. Boundary and initial conditions matter as much as the equation; an equation alone has many solutions. Where it shows up next Quantum Mechanics (34/83): the Schrödinger equation is a PDE and the particle in a box is the first example. Hydrogen's orbitals come from separating variables in three dimensions. Electromagnetics and Waves (34/38): Maxwell's equations imply the wave equation for light and Laplace's equation for static fields. Heat Transfer (34/16) and Fluid Mechanics (34/15): the heat equation and the Navier–Stokes equations are PDEs; wind tunnels and weather models are numerical PDE solvers. Finance: the Black–Scholes option-pricing equation is a heat equation in disguise. Computing and imaging: image blurring, medical-scanner reconstruction and the physics in animated films are all PDE solvers, with the stability caution above. If you want to go deeper 📘 Textbook: Walter Strauss, Partial Differential Equations: An Introduction (2nd ed., Wiley, 2008): the standard first course, clear on waves, heat and Laplace together. 📘 Textbook: Lawrence C. Evans, Partial Differential Equations (2nd ed., American Mathematical Society, 2010): the rigorous graduate-level text for mathematicians. 📘 Gentler: Ian Stewart, In Pursuit of the Unknown: 17 Equations That Changed the World (Basic Books, 2012), which tells the stories of the wave, heat, Navier–Stokes and Schrödinger equations. 🌐 Free course: MIT OpenCourseWare 18.303 Linear Partial Differential Equations: Analysis and Numerics (Fall 2014, Steven G. Johnson), with notes and problem sets. The takeaway A PDE writes a law for a whole field from its local shape. Heat equations smooth and forget, wave equations travel and keep their shape, Laplace's equation describes rest. Boundaries select a ladder of modes, solving the string and the quantum box with one method. Forgetting makes backward problems ill-posed, and simulation must obey the speed at which information moves. Try this: this week, watch something cool down or settle (a cup of tea, a candle's warm glass) and notice whether the hot spot sinks, spreads or sloshes. Then pluck a stretched rubber band at its middle and at its end and listen: you are hearing which harmonics each pluck contains. Sources & Further Reading Sources. D'Alembert's 1747 memoir on the vibrating string and the d'Alembert formula; the Euler–d'Alembert–Bernoulli controversy and Fourier's role in resolving it (Wikipedia, "Wave equation"; arXiv 1803.05287, "Resolution of the 300-Year-Old Vibrating String Controversy"; Bernoulli's sine-series claim is dated "around 1750" in secondary sources). Fourier, Théorie analytique de la chaleur (1822). Hadamard's well-posed problems (1902) and the backward heat equation as an ill-posed example (Wikipedia, "Well-posed problem"). Courant, Friedrichs and Lewy, "Über die partiellen Differenzengleichungen der mathematischen Physik", Mathematische Annalen 100 (1928), 32–74. Schrödinger's equation, 1926. Navier–Stokes as a Clay Millennium Prize problem (announced 2000; listed as unsolved at the time of writing; check the Clay Mathematics Institute for the current status). Constants: CODATA 2018 values of the Planck constant (6.62607015 × 10−34 J s, exact), electron mass 9.1093837015 × 10−31 kg and elementary charge. Computed in node: Fourier sine series of the triangular pluck matches the triangle (maximum error 10−3 with 400 modes), and the fundamental carries 81.1% of the energy for a mid-point pluck (8/π² = 81.06%); heat and wave areas conserved (1.418); mode amplification en²π²t at t = 0.01: 11.8 (n = 5), 1.9 × 104 (n = 10), 1.4 × 1017 (n = 20); relaxation of a 21 × 21 grid converges to the mean of the four edges (25 for edges 100, 0, 0, 0 after 2,000 sweeps); upwind scheme at ν = 1.2 reaches 1.2 × 105 after 42 steps; box energies 0.37603, 1.50412 and 3.38427 eV for 1 nm and beat period 3.666 fs; mean position 0.3199 and 0.6801 of the box width at the extremes of the beat. All interactives use illustrative fields chosen for the lesson. 🌐 MIT OpenCourseWare 18.303 Linear Partial Differential Equations 📘 Walter Strauss, Partial Differential Equations: An Introduction, 2nd ed. (Wiley) 📘 Lawrence C. Evans, Partial Differential Equations, 2nd ed. (AMS) 📘 Ian Stewart, In Pursuit of the Unknown: 17 Equations That Changed the World (Basic Books) 🌐 Resolution of the 300-Year-Old Vibrating String Controversy (arXiv) Step 15. Numerical Analysis: Answers You Can Trust, and How Wrong They Are -------------------------------------------------------------------------- Why: Computing answers you can trust, and knowing how wrong they are. Type 0.1 + 0.2 into almost any programming language and it will not say 0.3. That is not a bug. It is the first lesson in the art of getting good answers out of a machine that cannot hold a single exact number. In the Gulf War, on 25 February 1991, a Patriot missile battery at Dhahran failed to engage an incoming Scud, which struck a barracks and killed 28 American soldiers. The US General Accounting Office traced the failure to a software problem: the system counted time in tenths of a second, and a tenth is not a number a binary computer can store exactly. Each tick carried a tiny error. After about 100 hours of continuous running the clock was off by roughly a third of a second, which for a missile moving at the speed of a Scud is more than half a kilometre. Nothing about that error was large. What mattered was that nobody had asked how a small error would grow over time. That question is the whole of numerical analysis: how to compute answers with finite digits, how big the error is, and which methods keep it small and which let it explode. Almost every number you see from a weather forecast, a bridge simulation, a flight path, a game physics engine or an AI model came out of a numerical method. Mathematics gives the equation; numerical analysis gives you an answer you can trust, with an honest estimate of how wrong it is. The course in one box Who takes it: Mathematics, Computer Science, Physics and engineering students, usually in the second or third year, once they know calculus, linear algebra and differential equations. Mathematics programmes (MIT's Course 18, Cambridge) treat it as a rigorous subject with proofs; engineering programmes teach it as a toolkit. What it is for: turning continuous mathematics into finite computation, and knowing when to believe the result. Comes after: Differential Equations (34/03), Linear Algebra (34/04) and Programming Fundamentals (34/09). Leads to: Partial Differential Equations (34/79), where every real simulation is numerical; also Machine Learning (34/32), which is numerical optimisation at scale. Honest line: you will not learn to write a production solver. You will see the six ideas every solver is built around: floating point, the two-error trade-off, fast root-finding, conditioning, order of accuracy and stability. Easier first reads: Differential Equations (34/03), which first met Euler's method breaking down, and Calculus (12/11). Computers keep about sixteen digits, and 0.1 is not one of them A computer stores a real number as a sign, an exponent and a fixed-length string of binary digits, in the standard first published as IEEE 754 in 1985 (revised in 2008 and 2019). The common "double" format has 53 significant bits, so neighbouring numbers near 1 differ by 2−52, about 2.2 × 10−16. That gap is called machine epsilon. Between any two stored numbers there is a hole, and every answer is rounded into the nearest one. relative rounding error of one operation ≤ ε / 2 ≈ 1.1 × 10−16 Proof sketch: why 0.1 is not stored exactly. A fraction has a finite binary expansion only when its denominator, in lowest terms, is a power of 2. One tenth is 1/(2 × 5), and the 5 is the problem: its binary expansion repeats forever, 0.000110011001100…. The real trick is the denominator test. The computer cuts the repetition after 53 significant bits and keeps the nearest value, which is 0.1000000000000000055511151231257827…, slightly too big. The same happens to 0.2 and 0.3, and the three errors do not line up, which is why 0.1 + 0.2 is 0.30000000000000004 rather than 0.3. Interactive · What the machine really stored 0.1 0.5 1/3 0.1 + 0.2 2⁵³ + 1 Add 0.1 to itself Notice that 0.5, which is 2−1, is stored perfectly, and so is any whole number up to 253 = 9,007,199,254,740,992. One more than that cannot be stored: the last button shows it silently rounding back down. The Patriot clock did what the slider does, but with only 24 bits and 3.6 million additions: the tiny drift per tick added up to the third of a second. Rounding errors are small; accumulated or amplified, they are not. The fix is rarely "use more digits". It is to design the computation so that errors cannot pile up, which the next five ideas show. Every method has two errors that fight Suppose you want the slope of a curve at a point and can only evaluate the function. The textbook recipe is the forward difference: (f(x+h) − f(x)) / h. The calculus says the smaller h is, the better. The computer disagrees. total error ≈ truncation (grows with h) + rounding (grows as h shrinks) Proof sketch. A Taylor series gives f(x+h) = f(x) + h f′ + ½h²f″ + …, so the recipe is off by about ½h f″: truncation error, from throwing away the rest of the series. But the two function values agree in nearly every digit when h is tiny, so their difference keeps only a few meaningful digits and carries an absolute noise of about εf. Dividing by h magnifies that noise to ε/h. The real trick is to balance the two: ½h ≈ ε/h gives h ≈ √ε ≈ 10−8. Subtracting two nearly equal numbers is called cancellation, and it is the root of most numerical disasters: for example, (1 − cos x)/x² at x = 10−8 returns 0 on a computer, though the true answer is 0.5. Interactive · The V-shaped error Step size h Slide left from large steps. The error falls along a straight line (truncation), reaches a floor, then climbs again as rounding takes over. The forward formula bottoms out near 10−8 with an error of about 3 × 10−9; the central difference, (f(x+h) − f(x−h))/2h, has a smaller truncation error (proportional to h²) and so reaches about 10−11 near h = 10−5. A better formula buys accuracy, but neither can beat the floor. Newton's method: the number of correct digits doubles To solve f(x) = 0, draw the tangent to the curve at your current guess, and jump to where the tangent crosses zero. Repeat. xnext = x − f(x) / f′(x) Newton described the idea for polynomials in 1669 (published 1711), Joseph Raphson gave a simpler form in 1690, and Thomas Simpson extended it to general equations with calculus in 1740. For square roots the idea is far older: a Babylonian clay tablet from about 1800–1600 BC, YBC 7289, records √2 as 1;24,51,10 in base 60, about 1.41421296, accurate to six decimals. Historians infer that scribes used an averaging rule equivalent to Newton's, though the tablet shows the answer and not the method. Proof sketch for √2. Newton's step for x² − 2 is xnext = (x + 2/x)/2, the average of a guess and 2 divided by the guess. A little algebra gives xnext − √2 = (x − √2)² / (2x). The real trick is the square: if the error is 10−3, the next error is about 10−6, and then 10−12. The number of correct digits roughly doubles each step, called quadratic convergence. Starting at 1 the errors are 0.41, 0.086, 0.0025, 0.0000021, 1.6 × 10−12, then rounding level. Bisection, which halves an interval known to bracket the root, gains only one binary digit per step: after the same five steps its error is still about 0.008. Interactive · Newton against bisection x² − 2 cos x − x x³ − 2x + 2 Starting guess Now try the third equation from a start of 0 or 1. Newton jumps from 0 to 1, back to 0, and never settles: it cycles forever. Try x² − 2 from 0: the slope is zero, so the tangent never crosses the axis. Newton is fast and fragile; bisection is slow and certain. Real solvers use both, bracketing with one and accelerating with the other. A numerical analyst always asks of a method: how fast, and when does it fail? Some problems amplify errors, whatever method you use Take two lines that are almost parallel. Their crossing point sits somewhere, but nudge one line by a hair and the crossing slides a long way. That is not the fault of the method used to find the point. It is a property of the problem, measured by its condition number. relative change in the answer ≤ cond(A) × relative change in the data Proof sketch. To solve Ax = b, suppose b is off by a small δb. The answer moves by δx = A−1δb. The size of A−1 bounds the output wobble, and the size of A bounds how small b can be relative to x. Putting both together: relative wobble in x ≤ ‖A‖ ‖A−1‖ × relative wobble in b. The real trick is to notice that the inverse of a nearly singular matrix is huge, so tiny input noise (a rounding error is noise of size ε) is blown up by cond(A). A condition number of 10k means you lose about k of your 16 digits, however clever the algorithm. The famous test case is the Hilbert matrix, with entries 1/(i + j − 1). It looks harmless. Below, the page builds one, sets the true answer to a vector of ones, and solves it in ordinary double precision. Interactive · Losing digits to conditioning Matrix size At 5 × 5 the condition number is about 106 and the answer is good to 12 digits. At 10 × 10 it is about 3.5 × 1013 and only three or four digits survive. At 13 × 13 (condition 1018) the "solution" is wrong in its first digit and the program raised no error. That silence is the lesson: a numerical answer does not announce its own accuracy, so you check the condition number, or a residual, or a second method. The order of a method says what a smaller step buys To find the area under a curve, cut it into n strips. The trapezoid rule replaces the curve by a straight chord in each strip; Simpson's rule uses a parabola through three points. Both converge as n grows, but at very different speeds. error ≈ C × hp   so halving h divides the error by 2p The exponent p is the method's order. The trapezoid rule has order 2 (halve the strip, error ÷ 4); Simpson's has order 4 (error ÷ 16). On a log–log plot every method is a straight line whose slope is −p, which is how analysts read off the order from an experiment. Proof sketch. A chord under a smooth curve misses by an amount proportional to the curvature f″ times the strip width squared, and there are 1/h strips, giving a total of order h². The real trick behind Simpson is that the leading h² error terms of two trapezoid estimates can be cancelled: Simpson's rule with 2n strips equals (4T2n − Tn)/3, where T is the trapezoid estimate. Combining two rough answers to cancel their main error is called Richardson extrapolation, and it is how a great deal of accuracy is bought cheaply. Interactive · Two methods, two slopes Strips With 8 strips the trapezoid rule is off by about 2 × 10−3 on ∫01 ex dx, and Simpson's by 2 × 10−6. At 1,024 strips Simpson's error hits roundoff and the slope bends flat: the V-shape of the second idea again. An engineer who cares about cost asks, "how many function evaluations does the order buy me?" A method can be accurate in theory and explode in practice The 34/03 piece showed Euler's method blowing up when the step is too large. The deeper fact is that the limit on the step often comes from a fast part of the problem you do not even care about. Take y′ = −50(y − cos t) − sin t, started at 1.2. The exact answer is cos t plus a fast transient 0.2e−50t that is gone within 0.1 seconds. After that the solution is a gentle cosine. A problem with a fast, uninteresting scale next to a slow, interesting one is called stiff. Proof sketch. Explicit Euler multiplies the transient by (1 − 50h) each step, which is smaller than 1 in size only for h < 0.04, even after the transient is gone. Implicit (backward) Euler evaluates the rate at the new time, which gives a multiplier of 1/(1 + 50h), always below 1 for any h. The real trick is to look at what each method does to the pure decaying mode and ask for what steps its multiplier stays below 1. The price: each implicit step means solving an equation, which brings back Newton's method and linear systems from the earlier ideas. Interactive · Stiff problem, two methods Step size Below h = 0.04 both methods follow the cosine. Push the slider past it and the explicit method flips sign each step, with growing swings: at h = 0.05 it ends at over two million, at 0.1 at over 1011, while the exact answer is about −0.416. The implicit method gets it right to three decimals at the same big steps. The general slogan of the field: a consistent method that is stable converges; without stability, accurate-looking formulas produce garbage. Where analysts disagree is on how much accuracy is worth buying. Scientific computing usually insists on 64-bit doubles, while the machine-learning world deliberately trains with 16-bit formats that keep only two or three decimal digits, trading precision for speed. Which is right depends on whether the problem is well conditioned and stable, which is exactly what this course teaches you to check. What a graduate just sees A computer keeps about 16 significant digits, and most decimal fractions, like 0.1, are not stored exactly. Subtracting two nearly equal numbers throws away digits: avoid cancellation, or rewrite the formula. Every method has a truncation error and a rounding error that pull in opposite directions; the best step size is a balance, not "as small as possible". Quadratic convergence means correct digits double; linear means one at a time. Always ask how fast and when it fails. Some problems are ill-conditioned: the answer is sensitive to the data no matter how good the algorithm is. Order p means halving the step divides the error by 2p; a log–log plot shows it as a straight line. Stability limits the step; stiff problems force you towards implicit methods. A number from a computer does not announce its own error. Check residuals, vary the step, try a second method. Where it shows up next Partial Differential Equations (34/79): every weather, aircraft and reactor simulation is a numerical PDE solver, and the stability limit of the last idea becomes the CFL condition. Machine Learning (34/32): training a model is numerical optimisation, and low-precision arithmetic trades the rounding of idea one for speed. Linear algebra in practice: libraries such as LAPACK solve linear systems with pivoting precisely because of conditioning. Finance and engineering: option pricing, circuit simulators (SPICE) and finite-element structural analysis are all numerical methods with error control. Safety-critical software: the Patriot clock is the textbook case of an accumulated rounding error with real consequences. If you want to go deeper 📘 Textbook: Richard Burden, J. Douglas Faires and Annette Burden, Numerical Analysis (10th ed., Cengage, 2015): a widely used first course, algorithm by algorithm. 📘 Textbook: Lloyd N. Trefethen and David Bau, Numerical Linear Algebra (SIAM, 1997): a short, elegant treatment of conditioning and stability. 📘 Gentler: David Goldberg, "What Every Computer Scientist Should Know About Floating-Point Arithmetic" (ACM Computing Surveys, 1991), free online, and Lloyd Trefethen's short essay "The Definition of Numerical Analysis". 🌐 Free course: MIT OpenCourseWare 18.330 Introduction to Numerical Analysis (Spring 2012, Laurent Demanet), with lecture notes. The takeaway Computers hold finite digits, so every answer is a rounded approximation. Good numerical work balances truncation and rounding, uses methods that converge fast, notices when the problem itself amplifies errors (conditioning), reads the order of a method from how its error shrinks, and respects stability. The result is an answer plus an honest idea of how wrong it is. Try this: open a calculator or any programming prompt and compute 1 − (1 − 10−16), and then (1 + 10−16) − 1. Then try 0.1 × 3 and compare it with 0.3. You will see for yourself that arithmetic on a computer is not the arithmetic you learned at school. Sources & Further Reading Sources. Patriot failure at Dhahran, 25 February 1991: US General Accounting Office, report GAO/IMTEC-92-26 (1992), and the summary by Douglas Arnold (University of Minnesota); the roughly 0.34 s drift after about 100 hours and the figure for the displaced range gate come from secondary write-ups of that report, and are given as approximate. IEEE 754 first published 1985, revised 2008 and 2019. YBC 7289 (about 1800–1600 BC; √2 = 1;24,51,10 ≈ 1.41421296). Newton 1669 (published 1711), Raphson 1690, Simpson 1740: history of Newton's method. Computed in node: stored value of 0.1 = 0.1000000000000000055511…; 0.1 + 0.2 = 0.3000000000000000444; forward-difference and central-difference errors of sin at 1 against step size (minimum 3 × 10−9 near 10−8, and 1.1 × 10−11 near 10−5); (1 − cos x)/x² at x = 10−8 gives 0 against 0.5; Newton errors for √2 from 1; Hilbert matrix 1-norm condition numbers computed from the exact integer inverse formula (27 for n = 2, 9.4 × 105 for n = 5, 3.5 × 1013 for n = 10, 1.3 × 1018 for n = 13) and double-precision solution errors; trapezoid and Simpson errors for ∫01 ex dx; explicit and implicit Euler on the stiff example at several steps. Interactive datasets are illustrative problems chosen for the lesson. 🌐 MIT OpenCourseWare 18.330 Introduction to Numerical Analysis 📘 Burden, Faires and Burden, Numerical Analysis, 10th ed. (Cengage) 📘 Trefethen and Bau, Numerical Linear Algebra (SIAM) 🌐 The Patriot Missile Failure (Douglas Arnold) 🌐 GAO report IMTEC-92-26 Step 16. Differential Geometry: Curvature You Can Feel From the Inside ---------------------------------------------------------------------- Why: Curvature, from soap films to Einstein's spacetime. A pizza slice droops until you fold it, an airline flight path bends toward the pole, and a pendulum in Paris slowly turns. All of them are one idea: you can measure how a space curves without ever stepping outside it. Pick up a slice of pizza. Held flat, the tip flops down. Fold the crust into a shallow trough and the whole slice stiffens, tip and all. You did not plan that. You exploited a theorem that Carl Friedrich Gauss proved in the 1820s: a sheet can be bent in one direction freely, but the moment it curves one way it cannot also curve the other without stretching. The fold buys the slice a stiffness it did not have. Look at a flight map and the shortest route from Madrid to Tokyo is a curve that arcs far north, over Siberia. The flat map lies. Stand a Foucault pendulum in Paris and its swing plane turns through about 270 degrees a day, with nothing pushing it sideways. The floor of the building is curving under it. Differential geometry is the mathematics of curvature: what it is, how to measure it with nothing but a ruler laid along the surface, and what it does to straight lines, triangles and arrows. It is the language Einstein needed in 1915, and in this piece you will play with its six central ideas. The course in one box Who takes it: Mathematics majors, usually in the third or fourth year as an elective after analysis (MIT offers it as Course 18.950; Cambridge teaches it within the Tripos Part II geometry courses), and Physics majors who are heading for general relativity. What it is for: making calculus work on curved spaces, so that curvature becomes a number you can compute and a quantity you can reason about. Comes after: Multivariable Calculus (34/02) and Linear Algebra (34/04). Leads to: General Relativity (34/85); it also sits beside Topology (34/76), which asks what survives when you stretch a shape. Honest line: you will not compute a Christoffel symbol or a Riemann tensor here. You will see what curvature is, why it can be felt from inside, and why the total on a closed surface is a whole number of 2π that no amount of denting can change. Easier first reads: Topology: The Shape of Space (12/10), Vectors, Matrices and Linear Transformation (12/14). A curve's curvature is how fast its direction turns Start with a line, which has no curvature. Now a circle. Walk around one and your direction turns steadily; a small circle makes you turn sharply, a huge one barely at all. So define the curvature of a curve at a point as the rate at which the direction turns per unit distance walked, and the radius of curvature as its reciprocal. For a circle of radius R that gives κ = 1/R. For any other curve, the osculating circle (from the Latin for "kissing") is the circle that hugs it most closely at that point, and its radius is the radius of curvature there. κ = rate the direction turns per metre walked = 1 / R Drag the point round an ellipse below. The curve is gentlest along the flat sides and sharpest at the ends of the long axis, where the kissing circle shrinks. Interactive · The kissing circle Half-width a Half-height b Position round the curve The proof sketch that stays with you. Add up all the turning along a closed loop that never crosses itself and you always get exactly one full turn, 360 degrees. Squash the loop, dent it, make it a potato: the total is unchanged (this is the turning tangents theorem of Heinz Hopf, 1935). The real trick is to slide the loop towards a circle without letting it cross itself. The turning total can only change in whole turns, and the only whole number it could be is the one the circle gives. The readout adds up the turning of your ellipse numerically, and it is 360 degrees for every shape you choose. A surface bends two ways at once On a surface there is no single curvature at a point, because the answer depends on which direction you slice. Cut a saddle along the line from the pommel to the cantle and the cut curves up; cut it across and the cut curves down. The two extreme slices, at right angles to one another, give the principal curvatures κ1 and κ2. Leonhard Euler showed that every other slice is a blend of the two. curvature of the slice at angle θ = κ1 cos²θ + κ2 sin²θ Gauss's one number multiplies the two: K = κ1 × κ2. A bowl or a ball curves the same way both ways, so K is positive. A saddle curves opposite ways, so K is negative. A cylinder, such as a rolled sheet, curves one way and is straight the other, so K = 0. The product is the point: flat in one direction is enough to make K zero. Interactive · Slice a surface κ₁ (one direction) κ₂ (at right angles) Slice angle θ Proof sketch of Euler's formula. Near a point, a smooth surface looks like z = ½(κ1x² + κ2y²). Slice along direction θ by putting x = s cos θ and y = s sin θ. You get z = ½(κ1 cos²θ + κ2 sin²θ)s², a parabola whose curvature is exactly the bracket. The real trick is the first step: choosing axes along the extreme directions makes the cross term vanish. Curvature can be measured from the inside Here is the surprise. K was defined using how the surface sits in three-dimensional space, which an ant on it cannot see. Yet in 1827 Gauss proved (in his Disquisitiones generales circa superficies curvas, published 1828) that K depends only on distances measured along the surface. He called it the Theorema Egregium, the "remarkable theorem". Bending without stretching, as you do with paper, never changes K. That is why a flat sheet can roll into a cylinder or a cone (K stays 0) but never into a ball (K = 1/R²): the pizza fold in the first paragraph, and the reason every flat world map distorts something. How would an ant find K? Draw a circle of radius r on the surface, measuring r along the surface from the centre, and then measure its circumference. On a flat plane it is 2πr. On a sphere of radius R it is 2πR sin(r/R), which is smaller. On a saddle it is larger, because there is extra room. C ≈ 2πr (1 − Kr²/6)   so   K ≈ 3 (2πr − C) / (πr³) On the Earth, a circle of radius 1,000 km measured over the surface has a circumference of 6,257 km, not 6,283 km: 26 km short, enough for a surveyor to notice and for the circle to know the planet is round. Interactive · The ant's circle Curvature K Circle radius r Proof sketch. The full proof of the Theorema Egregium is a calculation, but its idea is the circle test. Everything in the circle test is a distance measured along the surface, so K, which the formula extracts, is built from the surface's own distances. The real trick is the identity K = κ1κ2: two numbers that each need the outside view combine into one that does not. For a surface whose circles have circumference 2π f(r), the same idea gives the neat formula K = −f″/f. Straight lines and triangles on a curved surface A "straight line" on a surface is a geodesic: the path you follow if you walk without turning left or right. On a sphere these are great circles, which is why the Madrid-to-Tokyo flight arcs north. On any curved surface, geodesics do the odd things that straight lines do not. Two nearby ones on a ball meet again (all meridians meet at the pole); on a saddle they diverge faster than in a plane. Triangles built from geodesics have angles that no longer add to 180 degrees. angle sum of a triangle = 180° + K × (area) (in radians: π + K·area) Proof sketch on a sphere, which really is a proof. A lune, the slice of a sphere between two meridians that meet at angle α, covers a fraction α/2π of the area 4πR², so its area is 2αR². Extend the three sides of a triangle into full great circles: they cut the sphere into pieces, and adding up the lune areas and matching antipodal copies gives area = (α + β + γ − π)R². The real trick is counting each lune's area by its angle alone. The excess over 180 degrees equals the area divided by R². Gauss knew this. In his geodetic survey of the kingdom of Hanover he measured a large triangle between the peaks Hohehagen, Brocken and Inselsberg, with sides of about 69, 85 and 107 km. The excess works out to roughly 15 arcseconds, buried inside the survey's measurement error. The common story that Gauss was testing whether physical space is Euclidean is, according to his biographer Buhler and others, a myth; historians still argue about his motives, and what is clear is that he had the mathematics ready. Interactive · Equilateral triangle on three worlds Sphere, K > 0 Flat, K = 0 Saddle, K < 0 Side length (in units of the curvature radius) Carry an arrow round a loop and it comes back turned Take an arrow lying in a surface and slide it along a path, keeping it as parallel as the surface allows (no turning relative to the path's straight-ahead direction). That is parallel transport. In a plane it comes back unchanged however you wander. On a curved surface, it comes back rotated. The rotation, called holonomy, equals the total curvature enclosed by the loop. turn of the arrow = ∫ K dA over the region the loop encloses The cleanest picture is a circle of latitude φ on the Earth. Cut a cone that touches the sphere along that circle and unroll it flat: it becomes a pie slice whose angle is only 360° × sin φ, not a full circle. Carry an arrow along the edge and keep it fixed in the flat picture. When the two cut edges of the slice are glued back, the arrow no longer lines up with the local "north", and the gap is the missing angle, 360° × (1 − sin φ). This is exactly the Foucault pendulum: a pendulum keeps its swing plane parallel-transported, so relative to the ground it turns by 360° × sin φ a day. At Paris (48.85° N) that is about 271° a day. Foucault's public demonstration under the dome of the Panthéon was in 1851. Interactive · Unroll the cone Latitude of the loop The real trick. Unrolling the cone is free of stretching, so the arrow can be moved in the flat picture, where "parallel" has its ordinary meaning. All of the mismatch comes from the glued seam. Check against the formula: the area of the polar cap above latitude φ is 2πR²(1 − sin φ), and K = 1/R², so ∫K dA = 2π(1 − sin φ), the same missing angle. Total curvature is a whole number of turns Add up K over an entire closed surface and something astonishing happens. A sphere gives 4π. A dented, stretched or lumpy sphere also gives exactly 4π: the dents have negative curvature that precisely cancels the extra positive curvature around them. A doughnut gives 0, because its outer rim is bowl-like (positive curvature) and its inner ring is saddle-like (negative), and the two totals, +4π and −4π, cancel. This is the Gauss–Bonnet theorem: ∫ K dA = 2π χ   (χ = 2 for a sphere, 0 for a doughnut, −2 for a two-holed doughnut) The number χ is the Euler characteristic, which counts vertices − edges + faces on any triangulation of the surface and is the topologist's way of counting holes (Topology, 34/76). The theorem says that an average of a local, calculus quantity equals a global, hole-counting one. It is one of the first and most beautiful bridges between analysis and topology. Interactive · Add up all the curvature Ellipsoid Doughnut Axis a Axis b Axis c Proof sketch. Cut the surface into small geodesic triangles. Each has angle sum = π + ∫K dA over it, so adding all of them, ∫K dA over the whole surface equals (sum of every angle) − π × (number of triangles). The angles around each vertex add to 2π, so the sum of every angle is 2π × V, and the 'π per triangle' terms add to π × F. Each triangle has 3 sides and each edge is shared by 2 triangles, so 3F = 2E, which lets you rewrite πF as 2πE − 2πF. The total becomes 2π(V − E + F). The real trick is to use the triangle formula once per triangle and let the counting do the rest. Gauss–Bonnet has an unexpected afterlife. Richard Hamilton's Ricci flow, which smooths the curvature of a space like heat spreading, was the engine of Grigori Perelman's 2002–03 proof of the Poincaré conjecture, the one Millennium Prize problem solved so far. What a graduate just sees Curvature is how fast direction turns; its reciprocal is the radius of the circle that kisses the curve. On a surface, curvature is two numbers, and their product K tells you bowl (K > 0), saddle (K < 0) or can-be-rolled-flat (K = 0). If a sheet is bent one way it resists being bent the other: that is why a folded pizza slice and a corrugated roof are stiff. K is intrinsic: a creature on the surface can detect it by measuring circles and triangles, with no view from outside. Every flat map of a sphere must distort something, because the sphere cannot be flattened without stretching. "Straight" means no turning, which makes a geodesic a great circle on a sphere. Carry an arrow round a loop and it comes back turned by the curvature inside: a Foucault pendulum and a Paris-sized triangle are the same fact. Total curvature of a closed surface counts holes: 4π for any sphere, 0 for any doughnut, however dented. Where it shows up next General Relativity (34/85): Einstein's 1915 theory says matter tells spacetime how to curve and spacetime tells matter how to move. The curved geometry is that of Bernhard Riemann's 1854 lecture, the generalisation of Gauss to any number of dimensions; free-falling objects follow geodesics. Classical Mechanics (34/82): the state space of a mechanical system is a curved manifold, and a rigid body's rotation lives on one. Topology (34/76): Gauss–Bonnet is where local geometry meets global shape. Computer graphics and robotics: smoothing a 3D scan, flattening a mesh for a texture map, and planning a robot arm's motion on its configuration space all use discrete curvature and geodesics. Keenan Crane's course notes on discrete differential geometry are a good example. Navigation: GPS software computes distances on a curved Earth with geodesics on an ellipsoid, because the sphere is not exact enough. If you want to go deeper 📘 Textbook: Manfredo do Carmo, Differential Geometry of Curves and Surfaces (2nd ed., Dover, 2016): the standard first course on curves and surfaces, with Gauss–Bonnet as the climax. 📘 Textbook: Andrew Pressley, Elementary Differential Geometry (2nd ed., Springer, 2010): a clearer route for readers who want more worked examples. 📘 Gentler: Tristan Needham, Visual Differential Geometry and Forms (Princeton University Press, 2021): geometric pictures instead of index gymnastics. 🌐 Free course: MIT OpenCourseWare 18.950 Differential Geometry (Fall 2008, Paul Seidel), with lecture notes and problem sets. The takeaway Curvature is how fast direction turns. A surface has two principal curvatures, and their product K can be measured by an inhabitant from distances alone. K shows up in the circumference of circles, the angle sum of triangles and the turn of a transported arrow, and when summed over a closed surface it counts holes. That is the geometry of general relativity, and the reason a folded pizza slice stays up. Try this: this week, fold a slice of pizza (or a sheet of stiff paper) along its length and try to flop the tip. Then try to wrap a sheet of paper smoothly round a ball. The first works, the second creases, and you have just felt K = 0 against K > 0. Sources & Further Reading Sources. Gauss, Disquisitiones generales circa superficies curvas (presented 1827, published 1828), with the Theorema Egregium. The Hanover triangle and its roughly 14.85 arcsecond excess, and the view that the "test of Euclidean space" story is a myth: Buhler's biography of Gauss as summarised in Physics Today correspondence (“Gauss on the mountaintops”) and mathpages.com 8.6, “On Gauss's Mountains”; the debate over his motives is still open. Hopf's turning tangents theorem (1935). Riemann's habilitation lecture (1854). Perelman's proof of the Poincaré conjecture (2002–03) and the Clay Millennium list (2000). Foucault's Panthéon pendulum (1851); the rate 360° × sin φ per day is standard. MIT OpenCourseWare 18.950 page checked November 2026. Computed in node: circle of radius 1,000 km on Earth (6,371 km radius) has circumference 6,257.4 km against 6,283.2 km flat; the survey triangle (sides 69, 85, 107 km, area 2,929 km², on an Earth of radius 6,371 km) has excess 14.9 arcseconds; Paris holonomy and pendulum rate at 48.85° N (88.9° and 271.1° a day); ellipsoid and doughnut ∫K dA by numerical integration (4π; torus +4π and −4π). Numbers in the interactives are illustrative geometry, not measurements. 🌐 MIT OpenCourseWare 18.950 Differential Geometry 📘 Manfredo do Carmo, Differential Geometry of Curves and Surfaces, 2nd ed. (Dover) 📘 Andrew Pressley, Elementary Differential Geometry, 2nd ed. (Springer) 📘 Tristan Needham, Visual Differential Geometry and Forms (Princeton) 🌐 On Gauss's Mountains (mathpages) Step 17. Theory of Computation: What Can and Cannot Be Computed --------------------------------------------------------------- Why: What can and cannot be computed: logic's other great limit. Some questions no program can ever answer, and others it can answer only after the sun has burned out. Proving which is which is one of the strangest achievements of the twentieth century. Your code editor will warn you about an unused variable. It will not reliably warn you that your program never stops. For some loops it can tell; for others it cannot, and the surprise is that this is not a failing of today's editors. In 1936 it was proved that no program, however clever and however much time it is given, can look at every program and say whether it will finish. That is the opening of the theory of computation: a mathematical map of what machines can do at all, what they can do only slowly, and what they can never do. A graduate keeps the map for life. It tells them when to stop trying to build a perfect bug finder, and when a problem is "hard" in the specific, technical sense that decades of the best minds have not cracked it. The course in one box Who takes it: computer science majors in the third or fourth year, and many mathematics majors. What it is for: drawing the exact boundaries of computation: machines of increasing power, problems no machine can solve, and problems that are solvable but apparently very costly. Comes after: Discrete Mathematics (34/08) and Algorithms (34/24). Leads to: Programming Languages & Compilers (34/30), where automata and grammars become the front end of every compiler. What this piece gives you: you will not be able to prove a language is not context-free afterwards. You will see what a finite machine cannot count, why one proof ends the dream of a perfect bug detector, and what a quantum computer really does to all this. The library's Alan Turing: The Machine That Defined Computing (History-Makers 04) is the easier first read on the Turing machine, with an adding machine to step through; in Spanish, La máquina universal de Turing (es/21/15). This piece goes further. What "computable" means The theory starts by shrinking every question to a yes/no one: is this number prime? Does this string match? Does this program halt? A question is decidable if some program answers it correctly, always, in finite time, for every input. Not fast; just finishing and right. (If speed matters, that is the later half of the course.) But "some program" in which language? Here comes the quiet miracle. In 1936 Alonzo Church (with the lambda calculus) and Alan Turing (with his machines) gave two completely different definitions of "effectively calculable", and they turned out to describe exactly the same set of functions. Many later formalisms agree. The Church-Turing thesis says this set is what any step-by-step method can compute. It cannot be formally proved, because "any method" is an informal idea, but it has stood for ninety years, and some theorists simply treat it as the definition of computable. The rule a graduate remembers"Computable" means a Turing machine can do it. Your laptop, your phone and a supercomputer are all, in this sense, equivalent: they differ in speed, not in what they can ever compute. Finite automata and regular expressions: machines with no memory Start with the weakest useful computer: a finite automaton. It has a fixed handful of states (think of lights on a panel), reads its input one symbol at a time, and on each symbol moves to a state determined only by where it is and what it read. No tape, no counter, no scratch paper. At the end it says accept or reject. That is already more useful than it sounds. A turnstile, a vending machine's coin logic and the text matcher in your search box are automata. Stephen Kleene showed in 1951 that the languages such machines accept are exactly the ones you can describe with regular expressions: patterns built from letters, "or", "followed by" and "repeat". Ken Thompson built them into text editors in the late 1960s (first QED, then Unix's ed), which is where grep comes from. Interactive · Run a machine, compare with its regex Divisible by 3 (binary) Contains ab Even number of 1s Input Letters read0 States (the current one is filled; a tick means accepting) Example: the machine for "divisible by 3" keeps only the remainder so far, reading each new bit b as remainder = (2 × remainder + b) mod 3. On 110 (six) it ends at remainder 0 and accepts; on 101 (five) it ends at 2 and rejects. The regular expression ^(0|1(01*0)*1)*$ gives the same verdicts. The "divisible by 3" machine shows the trick of automata: it does not remember the number, only the remainder, three possible values. The limit is just as clear. A machine with k states can never tell apart more than k different histories. Ask it to check that a string has as many as as bs, anbn, and it would have to remember n, an unbounded number. No fixed number of states suffices. A practical footnote: the regex engines in programming languages are stronger than the theory's regular expressions (they add "backreferences"), and that extra power has a price. Some patterns can make a backtracking engine take exponential time, a real attack vector known as ReDoS. Grammars: nesting needs a stack To handle anbn or matching brackets, add one thing: a counter or, more generally, a stack. A machine with a stack (a pushdown automaton) recognises exactly what a context-free grammar generates. A grammar is a list of rewriting rules. For balanced brackets: S → ( S ) S or S → ε (the empty string). Start from S and keep rewriting. Interactive · Write a sentence with rules S → ( S ) SS → (nothing)Random derivationReset Now the other direction: how much must a checker remember? Example derivation: S ⇒ (S)S ⇒ ((S)S)S ⇒ (()S)S ... Every string it makes is balanced, and the string (()(())) needs a counter that reaches 3. Noam Chomsky described this ladder in 1956, and it has four rungs: regular (finite automata), context-free (stack), context-sensitive (a bounded tape) and unrestricted (a full Turing machine). Each contains the one below. anbn is context-free but not regular; anbncn is beyond context-free. Programming languages are specified by context-free grammars, which is why the compiler course (34/30) begins with them: parsing your code is turning a flat string back into the tree the grammar generated. Turing machines: adding a tape Give the machine an endless tape it can read, write and move along, and it stops being limited. That is a Turing machine, and the thesis above says it is as powerful as any computer can be. Nothing else is added: states, a tape, a head, a table of rules. Here is the proof that the tape matters. The machine below decides anbn, the language that defeats every finite automaton. Its method is what a person would do with a pencil: cross off the first a (mark it X), run right to the first unpaired b (mark it Y), return left to the X, and repeat. If every a and b are crossed off together, accept. Interactive · A Turing machine that counts aabbaaabbbaabbbabab Step0 Run on aabb, the machine accepts after 13 steps; on aaabbb after 25; on aabbb it rejects after 12; on abab it rejects after 4. Steps grow roughly with the square of n, because it re-walks the tape for every pair. A Turing machine can also read another machine's rule table off its own tape and imitate it. Turing called this the universal machine; it is the idea of a stored program, and every phone is one. The same fact sets up the next result. The halting problem: a proof you can say out loud Claim: no program H exists that, given any program P and input, always correctly answers "halts" or "loops forever". Here is the proof in words, in the style of Cantor's diagonal argument. Suppose H existed. Build a mischievous program D that takes a program as its input and asks H what that program does when fed its own text. If H says "halts", D loops forever. If H says "loops", D halts at once. Now run D on D. If it halts, then H said it loops, so H was wrong. If it loops, H said it halts, wrong again. Either way H is wrong about D, so no correct H exists. Interactive · The contrarian row Each row is a program, each column an input. Tap any cell to flip it between halts and loops, then watch the contrarian row. The contrarian does the opposite of program k on input k, so it differs from every row on the diagonal. A list of all programs therefore cannot contain it, yet it would be a program: a contradiction. Turing proved this in a paper that went to press in 1936 and appeared in 1937; he did not use the word "halting", which came from Martin Davis later. Church reached a closely related result for his own system a little earlier in 1936. The deeper consequence is Rice's theorem: every non-trivial question about what a program does (will it ever crash, will it ever print this word, does it compute the same thing as that other program?) is undecidable in general. What this does not say matters. Particular programs can be analysed, and good tools prove many programs terminate. And a computer with strictly finite memory does eventually repeat a state, so for it halting is decidable in principle, though the number of states is so astronomical that the fact is of no practical use. The result says: no one method handles all programs. P, NP and NP-completeness: easy to check, hard to find Now suppose the answer is computable, and the question is cost. P is the class of yes/no problems solvable in polynomial time (like n, n log n, n²): sorting, shortest paths, is this number prime. NP is the class where a proposed "yes" answer can be checked in polynomial time: the "N" is for "nondeterministic", an old way of saying "if you were handed a certificate". Every problem in P is in NP. The open question, P = NP?, asks whether checking is really easier than finding. Interactive · Checking against searching A formula over six true/false variables: 12 clauses, each needing at least one true literal. Set the variables to satisfy every clause. Search by brute force Variables in a bigger formula This formula has exactly 2 of its 64 assignments that work; trying them in order finds the first on the 34th try. At 60 variables brute force would need 260 tries, about 36.5 years at a billion a second. That formula is an instance of SAT, satisfiability: is there a setting of the variables that makes the whole formula true? Stephen Cook showed in 1971 (and Leonid Levin independently, in work published in 1973) that SAT is NP-complete: every problem in NP can be translated into it in polynomial time. That translation is called a reduction, and it is the theory's most useful move. If problem A reduces to problem B, then a fast method for B would give a fast method for A. A small reduction you can feel: in a friendship graph, a group of people who all know each other (a clique) is exactly a group of strangers in the opposite graph (an independent set). Solve one problem and you have solved the other. In 1972 Richard Karp used reductions to show that 21 well-known problems, including clique, vertex cover, the Hamiltonian circuit and knapsack, are all NP-complete. Many hundreds more have followed. The rule a graduate remembersNP-complete problems are the hardest in NP in the sense that all of NP reduces to them. One fast algorithm for any of them would give a fast algorithm for all of them, so P would equal NP. Nobody has found one, and nobody has proved none exists; the Clay Mathematics Institute offers US$1,000,000 for a proof either way. Opinion is lopsided but it is opinion. In a poll of researchers by William Gasarch in 2018, about 88% believed P is not equal to NP. Practically, NP-complete does not mean hopeless: industrial SAT solvers handle enormous real instances, and heuristics give good answers. It means no known method is fast on every instance, so engineers stop hunting for a perfect one and settle for good enough. What quantum computers do and do not change It is tempting to say a quantum computer tries every answer at once. That is wrong, and it matters. A quantum computer works on qubits, whose states combine as amplitudes that can cancel or reinforce. A clever algorithm arranges the cancellation so that wrong answers fade and the right one is likely when you finally measure. A measurement returns a single result, so there is no free "all at once". Interactive · How big is Grover's speed-up? Searching an unstructured space of 2n possibilities for the one that works. Bits of search space n For n = 64: about 9.2×1018 classical tries on average against about 3.4×109 quantum queries. The speed-up is large but the quantum count is still the square root. QuestionWhat quantum changes Is more computable than before?No. A classical computer can simulate a quantum one, just exponentially slowly. The halting problem stays undecidable. Factoring large numbersShor's algorithm (1994) does it in polynomial time, which would break RSA and Diffie-Hellman. It needs a large, error-corrected machine that does not yet exist. Unstructured searchGrover's algorithm (1996): a square-root speed-up, proven the best possible for this kind of search. Big, not magical. NP-complete problemsNo known efficient quantum method. Whether one exists is open; most researchers suspect not. So the honest summary: quantum computers do not change what is computable, only how fast certain problems can be solved, and the problems with large known gains (factoring, simulating quantum physics) are specific, not "everything". The classical definition of efficient computing, the "extended" Church-Turing thesis, is the part under threat, not the original. On the hardware, Craig Gidney estimated in 2025 that factoring a 2048-bit RSA number would need fewer than a million noisy qubits running for under a week, noting that today's devices have at most a few thousand noisy qubits and none is fully error-corrected. That is an estimate, and the engineering is hard. What a graduate just sees Every computer, big or small, can compute the same set of things; only speed differs. A machine with finite memory cannot count without bound; nesting needs a stack. Languages form a ladder: regular, context-free, context-sensitive, unrestricted. Self-reference can be turned into a proof: the halting problem is undecidable. Any non-trivial question about what a program does is undecidable in general (Rice). Easy to check does not mean easy to find; that gap is P versus NP. A reduction transfers difficulty: "if I could solve B, I could solve A". Quantum computers are fast at some structured problems, not at everything, and they compute nothing new. Where it shows up next Compilers (34/30): regular expressions tokenise your code and context-free grammars parse it. Algorithms (34/24) looks back: the salesman's tour and 2n blow-ups are exactly NP-hard territory. Security (34/33): modern cryptography leans on problems believed to be hard, which is why Shor's algorithm is such news. Software engineering (34/31): static analysers and type checkers are deliberately approximate, because Rice's theorem forbids exactness. In life: the search box, the spell-checker, logistics planners and chip designers all use SAT solvers or heuristics for NP-complete problems. If you want to go deeper 📘 Textbook: Michael Sipser, Introduction to the Theory of Computation (Cengage, 3rd ed.): the standard text, famous for its clarity. 📘 Textbook: Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (4th ed.), the NP-completeness chapter. 📘 Gentler: Scott Aaronson, Quantum Computing since Democritus (Cambridge University Press, 2013): an entertaining tour from Turing to quantum. 🌐 Free course: MIT OpenCourseWare 6.045J / 18.400J, Automata, Computability, and Complexity (Spring 2011, taught by Scott Aaronson), with lecture notes and problem sets. The takeaway Computation has exact limits. Finite automata cannot count, a stack handles nesting, and a tape gives everything computable. Self-reference proves the halting problem has no solution, which rules out perfect program checkers. Among solvable problems, P versus NP asks whether finding is ever as easy as checking, and quantum computers speed up special cases without making the impossible possible. Try this: next time a tool says "could not determine", remember it may be a case of Rice's theorem, not laziness. Then in the SAT demo, set the six switches to the working answer, and slide the variable count to find the size where brute force takes longer than a human life. Sources & Further Reading Sources. Textbook material: Sipser, Introduction to the Theory of Computation. Kleene's regular events (1951) and Thompson's use in QED/ed (1968): Wikipedia, "Regular expression". Chomsky, "Three models for the description of language" (1956): Wikipedia, "Chomsky hierarchy". Church-Turing thesis cannot be formally proven: Wikipedia, "Church-Turing thesis". Halting problem dates and the term's origin with Martin Davis: Wikipedia, "Halting problem". Cook 1971, Levin 1973, Clay prize US$1,000,000 and the Gasarch poll (88% in 2018): Wikipedia, "P versus NP problem". Karp, "Reducibility Among Combinatorial Problems" (1972): Wikipedia, "Karp's 21 NP-complete problems". Shor (1994) and Grover (1996): Wikipedia, "Quantum computing". BQP contained in PSPACE, relation to NP unknown: Wikipedia, "BQP". Gidney, "How to factor 2048 bit RSA integers with less than a million noisy qubits", arXiv:2505.15917 (May 2025). All machine runs and counts in the demos were computed and cross-checked in code. 📘 Introduction to the Theory of Computation, Michael Sipser (author's page) 🌐 MIT OpenCourseWare 6.045J (free) 📘 Quantum Computing since Democritus, Scott Aaronson 🌐 Clay Mathematics Institute: P vs NP Step 18. Game Theory: When Your Best Move Depends on Mine --------------------------------------------------------- Why: Strategy as mathematics. Two shops pick prices, two countries pick tariffs, a hundred bidders pick bids. Game theory is the maths of choosing when everyone else is choosing too, and it explains why smart people can trap themselves. Two petrol stations face each other across a road. If both charge a fair price, both make a decent profit. If one cuts its price, it steals the customers and makes more, for a while. So each is tempted to cut. Both cut. Both now earn less than before, and neither can raise prices alone without losing everyone. Nobody was stupid. Each did the sensible thing given what the other might do. That pattern, a trap built entirely out of sensible choices, is the first thing game theory teaches you to see. It then teaches how to get out of the trap: by repeating the game, by changing who moves first, by changing the rules. The same toolkit explains the design of radio-spectrum auctions and the matching of kidney donors. The course in one box Who takes itEconomics majors in year 2, straight after microeconomics. Business schools teach it inside strategy courses, and computer science and political science programmes teach it too, because algorithms and elections are games. What it is forPredicting what rational, self-interested players will do when each one's best move depends on the others, and designing rules so the result is a good one. Comes afterMicroeconomics (34/42). Leads toStrategy & Competition (34/54); it also underlies the auctions and pricing in Pricing (34/61) and the rules-of-the-game thinking in Public Economics (34/49). What this piece gives youYou will not be able to solve a multi-stage game with incomplete information. You will see why a dominant strategy can leave everyone worse off, why a threat only works if carrying it out is in your interest, and why an auction format changes how people bid. Easier first reads: the library's The Social Contract (18/14) asks why we accept rules and a state at all, and Anarchism (31/04) covers the commons problem in words. This piece puts numbers on that kind of trap. Players, strategies, payoffs, and the Nash equilibrium A game has three ingredients: the players (who decides), the strategies (what each can do) and the payoffs (what each gets for every combination of choices, in whatever they care about: money, time, votes, survival). Two players with two options each fit in a small grid, the payoff matrix. One player picks the row, the other the column, and each cell holds two numbers: the row player's payoff first, the column player's second. Two ideas solve most such grids. A dominant strategy is one that is best for you whatever the other does: if it exists, play it. When neither player has one, look for a Nash equilibrium: a pair of choices where neither player could do better by changing their own choice alone. John Nash proved in 1950 that every finite game has at least one, possibly in mixed strategies (rolling dice between options). Nash shared the 1994 economics Nobel prize with John Harsanyi and Reinhard Selten for it. Nash equilibrium: each player's choice is a best response to the other'snobody gains by switching alone; it says nothing about whether the outcome is good Interactive · The payoff-matrix workbench Prisoner's dilemma Stag hunt Chicken Matching pennies Which side to drive Each cell: your payoff (row player), then the column player's. Edit the numbers; the analysis updates. Shaded = a best response for that player; outlined cell = Nash equilibrium. Without JavaScript: in the prisoner's dilemma (5, 3, 1, 0), defecting is dominant for both players, the only Nash equilibrium is both defecting for 1 each, and both cooperating would give 3 each. Try the presets and read the verdicts. Chicken and the driving game have two pure equilibria and a mixed one at 50:50; matching pennies has no pure equilibrium at all, only the mixed one, which is why a goalkeeper and a penalty-taker must be unpredictable. In matching pennies, if the row player leans even slightly toward heads, the column player exploits it. The prisoner's dilemma: why smart players choose badly Merrill Flood and Melvin Dresher devised it at the RAND Corporation in 1950, and Albert Tucker gave it its story: two suspects, questioned separately. Stay silent (cooperate) and both get a light sentence. Betray the other (defect) and you walk free while he gets the worst. Both betray and both get a heavy sentence. With points instead of years, the standard payoffs are: temptation 5, mutual cooperation 3, mutual defection 1, being betrayed 0. Whatever the other does, defecting pays you more: 5 beats 3 if she cooperates, 1 beats 0 if she defects. So both defect and both get 1, when both cooperating would have given 3 each. The equilibrium is stable and bad. That is the logic of arms races, overfishing, price wars and the two petrol stations. Now play it. Ten rounds against a computer opponent whose rule you can pick; you know the game is exactly ten rounds long. Interactive · Play ten rounds Tit for tat Always defect Always cooperate Grudger Coin flip CooperateDefectRestart Payoffs per round: both cooperate 3 each; you defect on a cooperator 5 to 0; both defect 1 each. Tit for tat copies your last move; the grudger cooperates until you defect once, then never again. Against tit for tat, the best ten-round total is 32: cooperate nine times, defect on the last round when it can no longer be punished. Against always-defect, nothing beats 10. Against always-cooperate you can take 50. The right play depends on who is on the other side, which is the whole subject in one sentence. Repeated games: when tomorrow changes today Meet the same person again and again and the logic changes: defecting today invites revenge tomorrow. In 1980 the political scientist Robert Axelrod invited game theorists to send in programs for a repeated prisoner's dilemma, each program playing every other for 200 moves. The winner, in this tournament and in a second, larger one, was the simplest entry: tit for tat, sent by the psychologist and game theorist Anatol Rapoport. It cooperates first, then copies the opponent's last move. Axelrod's 1984 book The Evolution of Cooperation drew the lesson: successful strategies were nice (never defect first), provocable (punish defection at once), forgiving (return to cooperation) and clear (easy to read). Tit for tat never beats the partner it faces; the best it can do in a single match is tie. It won by getting good scores out of nearly everyone. Run your own small tournament. Six kinds of players meet in a 200-round round robin; add copies of Always-defect and see whether the winner changes. Interactive · A round-robin tournament (a toy field) Always-defect entrants No mistakes 5% of moves slip Entrants: Always cooperate, Tit for tat, Grudger, Pavlov (cooperate only if both did the same last round), Coin flip, plus the Always-defect copies. Everyone meets everyone else for 200 rounds; bars show the average points per round. Payoffs 5, 3, 1, 0. A toy field, far smaller than Axelrod's. With no Always-defect, the nice, retaliating strategies fill the top. Add more defectors and the field gets harsher: the defectors climb to the top once enough naive cooperators and coin-flippers are there to be exploited, while their scores against each other stay at 1. Success in a repeated game depends on who else is playing. Turn on the 5% slips and tit for tat loses ground too: after one accidental defection two tit-for-tat players can lock into a spiral of mutual retaliation. Later work found more forgiving variants, such as generous tit for tat, and the Pavlov rule do better in noisy worlds. Cooperation without a referee needs a future worth protecting, which is why long-term relationships, reputations and repeated dealings support trust that one-off meetings cannot. Coordination games: when you just need to match Not every game is a conflict. In the driving game, both of you want to pick the same side; which side hardly matters. Load "Which side to drive" above: two equilibria, both good, and nothing in the payoffs says which. Conventions (driving on the left in the UK, Japan and India, on the right in most of the rest of the world) are equilibria picked by history. The stag hunt adds risk: both hunting stag gives 4 each, but hunting hare alone is safe at 3. Two equilibria again, one better but riskier. Thomas Schelling, in The Strategy of Conflict (1960), noticed that when payoffs cannot choose, players use focal points: the obvious, salient option, like meeting "at the clock" in a station. Many real-world failures, from bank runs to standards wars, are coordination games stuck on the bad equilibrium. Sequential games: the credible threat When players move in turn, you solve the game backwards: start at the end, see what the last mover would do, and work back. Take a company deciding whether to enter a market held by an incumbent. The incumbent says: "If you enter, I'll start a price war." Should the entrant believe it? Only if fighting is actually best for the incumbent after entry happens. If, once the entrant is in, the war would cost the incumbent more than sharing the market, the threat is empty. A rational entrant sees that and enters. Reinhard Selten's refinement of Nash equilibrium, subgame-perfect equilibrium, rules such empty threats out. Interactive · Entry, threats and commitment Incumbent's profit if it fights after entry No commitment Commit to fight (contract penalty) Payoffs (entrant, incumbent): stay out (0, 10); enter and incumbent accommodates (4, 5); enter and incumbent fights (−2, your slider). The commitment option makes accommodating cost the incumbent 3 (so it pays only 2). The slider has a threshold. With a war worth less than 5 to the incumbent, the threat is empty and the entrant walks in. Raise the war's payoff above 5, or use the commitment button, and the threat becomes credible, the entrant stays out, and the incumbent never has to fight. Commitment devices (spare factory capacity already built, a contract that punishes backing down, a reputation) have this strange property: by taking away your own options they can make you better off. Auctions: bid your value, or shave it An auction is a game where the rules decide the payoffs. In a sealed-bid second-price auction, the highest bidder wins but pays only the second-highest bid. William Vickrey analysed it in 1961 (it had been used by stamp collectors since 1893). Here, bidding exactly your true value is a dominant strategy: bidding more risks paying above your value, bidding less risks losing an item you would have profited from. In a first-price auction you pay what you bid, so you shave your bid below your value, trading a bigger profit if you win against a smaller chance of winning. With four bidders whose values are equally likely to be anywhere in a range, the equilibrium bid is three-quarters of your value (in general, (n−1)/n of it). Interactive · Four bidders, two formats (3,000 simulated auctions) Your bid as a share of your value second-price   first-price Values for all four bidders are drawn uniformly between 0 and 100. The three rivals bid their full value in the second-price format and three-quarters of it in the first-price format. Your average profit is per auction, including those you lose. Slide the share. In the second-price format your profit peaks at 100% of your value; in the first-price format it peaks near 74%. Also watch the seller's average revenue: it is about 60 in both formats, a first glimpse of the revenue equivalence theorem. Real auctions differ from this textbook case. When bidders are unsure of the item's true value (oil leases, spectrum) the winner tends to be the one who overestimated most, the winner's curse. Mechanism design: design the game, then let people play it Game theory asks: given the rules, what will players do? Mechanism design turns it around: what rules would make self-interested players do what we want? Two famous cases. Spectrum auctions. Governments own radio frequencies and need to hand them to phone companies. For decades they used beauty contests and lotteries. From July 1994 the US Federal Communications Commission instead ran a "simultaneous multiple round" auction, where many related licences are sold together over many rounds and bidders see each other's bids. Theorists including Paul Milgrom and Robert Wilson helped shape the design, and they shared the 2020 economics Nobel prize for improvements to auction theory and new auction formats. In 2000 the UK's 3G auction raised £22.5 billion from five licences. Kidney exchange. Many people who need a kidney have a willing donor who is the wrong blood type. Selling kidneys is illegal almost everywhere, so prices cannot match people. Alvin Roth, Tayfun Sönmez and Utku Ünver designed algorithms (their 2004 paper in the Quarterly Journal of Economics) in which pair A's donor gives to pair B's patient while B's donor gives to A's: a swap, extended to longer cycles and to chains started by an altruistic donor. The first paired exchange recorded was in South Korea in 1991 and the first in the US in 2000; by 2012 the US National Kidney Registry had organised a 60-surgery chain, and by 2014 one of 70. Roth shared the 2012 economics Nobel prize with Lloyd Shapley for the theory of stable allocations and the practice of market design. Game theory predicts what people do under the rules. Mechanism design chooses the rules. What a graduate just sees Before asking what someone will do, ask what they would do if they expected you to do each of your options. A dominant strategy needs no guess about the other player. If it exists, it settles the game. A Nash equilibrium is stable, not good. The prisoner's dilemma's equilibrium leaves both worse off than cooperating. Repetition changes the game: cooperation can be rational when the future is long enough and defection is punishable. A threat counts only if carrying it out is in your interest when the time comes. Otherwise build a commitment or expect to be called. When payoffs do not choose between equilibria, the focal point does: salience, convention, a shared story. In a second-price auction, bid your value. In a first-price auction, shave your bid. The rules decide how people behave. When a market cannot use prices, you can still design the rules. Where it shows up next Strategy & Competition (34/54): firms setting prices, building capacity and deciding whether to enter are playing the games above. Pricing (34/61): discounts, price matching and surge pricing are games with customers and competitors. Behavioral Economics (34/46): the next piece asks when real people do not play the equilibrium, as in the ultimatum game. Machine Learning (34/32) and Computer Networks (34/27): game-playing AIs and congestion control both apply these ideas. In the world: online-advertising auctions, spectrum sales, school and hospital matching, climate treaties, arms control. If you want to go deeper 📘 Textbook. Robert Gibbons, Game Theory for Applied Economists (Princeton, 1992). Short and widely used in economics programmes. 📘 Textbook. Martin Osborne, An Introduction to Game Theory (Oxford). A fuller undergraduate treatment with many worked games. 📘 Gentler. Avinash Dixit and Barry Nalebuff, The Art of Strategy (Norton, 2008), and Robert Axelrod, The Evolution of Cooperation (1984). Real cases, almost no algebra. 🌐 Free course. Open Yale Courses ECON 159: Game Theory (Ben Polak, 24 lectures, recorded Fall 2007), covering Nash equilibrium, backward induction and signalling. The takeaway When your best move depends on others' moves, look for dominant strategies, then for equilibria, and remember that a stable outcome can be a bad one. Repetition, commitment and well-designed rules are the three ways out, and each is a way of changing the game rather than the players. Try this: this week, spot a situation where you and someone else are each waiting for the other to move first or to give in, and ask what the payoff grid looks like and whether it is a game you can change. Sources & Further Reading Sources. Dominance, Nash equilibrium, mixed strategies, backward induction and the second-price result are standard textbook game theory (Gibbons; Osborne; Polak's Yale lectures). The prisoner's dilemma was devised by Flood and Dresher at RAND in 1950 and named by Tucker (Wikipedia, "Prisoner's dilemma"). Nash, "Equilibrium points in n-person games," PNAS 36, 1950; the 1994 economics Nobel prize went to Nash, Harsanyi and Selten. Axelrod's tournaments (c. 1980) and 1984 book: tit for tat, by Anatol Rapoport, won both; matches were 200 moves; the death-spiral under noise and generous tit for tat are as described in Wikipedia's "Tit for tat". Schelling, The Strategy of Conflict (1960). The second-price auction was described by Vickrey in 1961 and used by stamp collectors from 1893. The FCC has held spectrum auctions since July 1994 using a simultaneous multiple round design; the UK's 2000 auction raised £22.5 billion from five 3G licences (Wikipedia, "Spectrum auction"). The 2020 prize went to Milgrom and Wilson, the 2012 prize to Roth and Shapley. Kidney exchange history from Wikipedia's "Kidney paired donation"; Roth, Sönmez & Ünver, "Kidney Exchange," QJE 2004. Every number an interactive shows was computed in node from the code on this page: ten-round best score against tit for tat 32, against always-defect 10, against always-cooperate 50; the four-bidder first-price optimum is near 0.74 (theory 0.75); the average winning price is near 60 in both formats; the toy tournament's ranking depends on the chosen field and is not Axelrod's result. 🌐 Open Yale Courses ECON 159 Game Theory 📘 Dixit & Nalebuff, The Art of Strategy 📘 Axelrod, The Evolution of Cooperation Step 19. Machine Learning: Programs That Write Their Own Rules -------------------------------------------------------------- Why: Learning from data is optimisation, linear algebra and probability. Nobody wrote the rule that tells a spam message from your mother's email. A program found it by looking at examples, and everything in the field is about whether you can trust what it found. Your phone groups your photos by person. Your inbox hides the lottery scams. A bank flags a card payment at 3 a.m. from another continent. Try to write the rules for any of these by hand and you hit a wall within an hour: what, exactly, makes a face a face, or a message spam? Machine learning gives up on writing the rules. Instead you show a program thousands of labelled examples and let it adjust itself until it gets them right. This is powerful, and it quietly changes the questions you have to ask. The hard part is no longer "what is the rule?" but "how do I know the rule it found will work tomorrow, on people it has never seen?" That question, and a handful of simple tools for answering it, are what a graduate of a machine-learning course keeps for life. The course in one box Who takes it: Computer Science majors, usually in year 4; also statistics, data science and engineering students. What it's for: building programs that learn their behaviour from data, and judging honestly whether they work. Comes after: Linear Algebra (34/04), Probability & Statistics (34/05), Multivariable Calculus (34/02) and Algorithms (34/24). Leads to: no later subject in this series lists it as a prerequisite; it feeds research and careers in AI, and touches Computer Security (34/33), where learning systems are both tools and targets, and Databases (34/28), where the training data lives. Honest line: you won't train a modern language model after this; you will understand the training loop all of them share. For the AI story and a tour of language models, read Artificial Intelligence (29/01) and How Large Language Models Actually Work (29/02) first; this piece goes underneath them. Learning from data, and the data you hold back Take a toy problem. Each email gets a "suspicious words" score, and you must decide spam or not. You could write a rule by hand: spam if the score is above 3. But why 3? Better: try every threshold on a set of labelled examples and keep the one that gets the most right. That, in miniature, is training: a rule with an adjustable knob, a way to score the rule on data, and a search for the best setting of the knob. Here is the trap. The setting that fits the examples you used will almost always look better on those examples than on fresh ones, because you tuned it to them. So practitioners split their data three ways: Training set: the examples the model adjusts itself on. Validation set: held back to compare choices (which model, which settings). Test set: touched once, at the very end, to estimate how it will do in the real world. If you keep tuning against it, it stops being a test. Try it: pick the threshold, then meet fresh data Filled dots are 30 training emails (orange = spam, blue = not spam); hollow squares are 20 held-back ones the rule never saw. All the data are made up for this demo. The best threshold on the training emails is 3.3, which gets 93% of them right, but only 85% of the 20 held-back emails. Threshold: spam if score > 3.0 Let the data choose Linear regression and gradient descent Many problems are about predicting a number. The simplest model is a straight line: prediction = w × input + b. The two knobs are the slope w and the intercept b. To score a line, measure how far it misses each point, square the misses so that over and under both count, and average them: the mean squared error (MSE). The method of least squares was first published by Adrien-Marie Legendre in 1805; Carl Friedrich Gauss claimed to have used it earlier, which started a priority dispute. For a line there is a formula for the best w and b. For huge models there is not, and we use the idea that carries the whole field: gradient descent. Stand on the error surface, feel which way is steepest downhill (the gradient, from Multivariable Calculus 34/02), and take a small step that way. Repeat. Augustin-Louis Cauchy suggested the method in 1847. new w = w − η × (slope of the error with respect to w)    same for bη ("eta") is the learning rate, the size of each step The learning rate is a real trade-off: too small and you crawl; too large and you overshoot the valley and bounce out of it. Try it. The 12 points below are made up around a line; the least-squares answer is w = 2.465, b = 8.289, with MSE 2.58. Try it: fit a line by rolling downhill Start from w = 0, b = 0 and press Step. Choose a learning rate. With η = 0.01, 200 steps reach w = 2.89, b = 5.79 and MSE 4.37, still on the way down; with η = 0.04 the steps are too big and the error explodes instead of shrinking. η = 0.001 η = 0.01 η = 0.03 η = 0.04 StepRun 20 stepsReset Overfitting and underfitting A line is a rigid model. A more flexible one, say a polynomial with more bends, can follow the data more closely. Flexibility is a dial, and both ends of it fail: Underfitting: the model is too simple to capture the pattern. It is wrong on the training data and wrong on new data. Overfitting: the model is so flexible that it memorises the noise in the training data. It is nearly perfect there and bad on new data. This is why the validation set exists. Training error only ever goes down as you add flexibility. Validation error goes down, then comes back up, and the bottom of that U is where you stop. Training error tells you how well the model remembers. Validation error tells you how well it learned. Try it: turn the complexity dial The true pattern is a smooth wave; the 12 filled dots are noisy samples of it, and the 40 hollow dots are fresh noisy samples used only to judge. The curve is a polynomial fitted to the filled dots. A degree-1 line misses the wave (errors 0.54 and 0.43), degree 3 does best on fresh data (0.28 train, 0.35 validation), degree 9 hugs the 12 dots (0.14) but is far worse on fresh ones (1.02). Polynomial degree: 3 Classification and neural networks as layered functions Classification predicts a label rather than a number: spam or not, which digit, which animal. A simple classifier computes a weighted sum of the inputs and squashes it into a probability between 0 and 1, and its decision boundary is a straight line (or plane). That is enough when the classes can be separated by a line. Some problems cannot. The classic example is XOR: the answer is 1 when exactly one of the two inputs is 1. No single straight line separates the four cases correctly. In the late 1960s Marvin Minsky and Seymour Papert's book Perceptrons analysed exactly this kind of limit for single-layer networks, and is often credited with helping to cool interest in neural networks for years (historians debate how much). The escape is to stack models. A neural network is a chain of simple functions: each layer takes a weighted sum of its inputs, applies a bend (a non-linear function such as tanh), and hands the result to the next layer. One layer draws a line; a layer built on top of lines can carve out regions that no single line can. Training a network means finding good weights, and the tool is backpropagation, which in words goes: Run an example forward through the layers and get a prediction. Measure how wrong it was. Walk backwards, layer by layer, asking each weight "how much of this error was your fault?", using the chain rule from calculus. Nudge every weight a little in the direction that reduces the error. Repeat on the next example. The idea was derived several times; the 1986 Nature paper by David Rumelhart, Geoffrey Hinton and Ronald Williams is the one that made it popular. Gradient descent plus backpropagation, run at scale, is still how neural networks are trained, including the large language models in 29/02. Try it: teach a network XOR Four training cases. Choose how many hidden units the network has, then slide through training steps (always the same starting weights). The picture shows the network's output over the plane. With no hidden layer, the best the model can do is output about 0.5 for every case (loss 0.693) and it stays stuck; with 4 hidden units, 500 steps already get all four right (loss 0.010). No hidden layer 2 hidden units 4 hidden units Training steps: 500 Evaluation: accuracy is not enough "The model is 99% accurate" can be meaningless. Imagine a rare disease affecting 1% of 10,000 people. A model that always says "healthy" is 99% accurate and finds nobody. Count outcomes instead: true positives (TP), false positives (FP), true negatives (TN), false negatives (FN). precision = TP / (TP + FP): of those flagged, how many were rightrecall = TP / (TP + FN): of those who were sick, how many were found The two pull against each other. A model that flags only when it is certain has high precision and low recall; one that flags at the slightest hint has high recall and swamps you with false alarms. Where to set the threshold depends on what each error costs: missing a cancer is not like sending a good email to the spam folder. And when the real condition is rare, even a decent test produces mostly false alarms. Try it: a test with a threshold 10,000 people. The test gives a score; sick people score on average 2 standard deviations higher than healthy ones (a decent test, invented for this demo). Move the threshold and the prevalence. At 1% prevalence and a threshold of 1.0, the test finds 84 of 100 sick people (recall 84%) but raises 1,571 false alarms, so only 5% of those flagged are actually sick. 1% are sick 10% 50% Flag when score > 1.0 Bias: the model learns the data you gave it A model has no opinion about fairness. It finds whatever pattern best fits the examples it was shown, including patterns in who is in the examples. If one group is a small part of the training data, the model's single rule is tuned to the majority and does worse on the rest. This is not hypothetical. In the 2018 Gender Shades study, Joy Buolamwini and Timnit Gebru found that the two benchmark face datasets they examined were 79.6% (IJB-A) and 86.2% (Adience) lighter-skinned subjects, and that three commercial gender-classification systems misclassified darker-skinned women at error rates of up to 34.7%, against at most 0.8% for lighter-skinned men. Try it: who is in the training data? Two groups, A and B, whose scores sit on different scales (an invented example). The model picks the one threshold that gets the most training cases right. Change how much of the training data is group B. With 2% of the data from group B the model is 84% accurate for A but 74% for B; at 50% both groups get 81%. Group B share of training data: 2% More data from the same source does not fix this; different data, or a model checked group by group, can. Bias can also come from the labels (past human decisions the model copies) and from how a system is used. Checking performance for each group, not just on average, is the habit to keep. The same discipline applies to the newest systems. The Stanford HAI AI Index 2026 report describes a "jagged frontier": one model earned a gold medal at the International Mathematical Olympiad, yet the top model it tested read analog clocks correctly only 50.1% of the time. An average score, or a headline result, says little about how a model will do on the case in front of you; that has to be measured. What a graduate just sees Learning means tuning knobs to fit examples; the rule is found, not written. Performance on the data you trained on is not evidence. Only data held back is. Gradient descent is "step downhill"; the learning rate is the step size and it matters. Too simple and too flexible both fail; validation error has a U shape. A network is stacked simple functions, and backpropagation is the chain rule applied layer by layer. Accuracy hides rare cases; ask for precision, recall and the cost of each mistake. When a thing is rare, most alarms are false alarms. A model is only as fair as its data; check each group, not the average. Where it shows up next Linear Algebra (34/04) and Multivariable Calculus (34/02): weights are vectors and matrices, and the gradients are partial derivatives. Probability & Statistics (34/05): the train/test idea is the statistician's out-of-sample check, and precision is Bayes' theorem in disguise. Algorithms (34/24): training is optimisation, and its cost is why hardware like GPUs matters (see 29/12). Computer Security (34/33): learning systems can be fooled by crafted inputs and poisoned data. In the world: fraud screening, search ranking, recommendations, translation, medical imaging, and the chatbots in 29/02. As of the 2025 Stanford AI Index, the compute used to train notable models was reported to be doubling roughly every five months, which is why training is now an industrial activity. If you want to go deeper 📘 An Introduction to Statistical Learning (James, Witten, Hastie, Tibshirani; 2nd edition 2021, with a Python edition in 2023): free from the authors, the standard first university text; clear and light on maths. 📘 Deep Learning (Goodfellow, Bengio, Courville, MIT Press 2016): the standard graduate text on neural networks, free to read online. ▶️ Gentler: 3Blue1Brown's neural-networks video series builds the ideas above with pictures. 🌐 Free courses: MIT OpenCourseWare 6.036 Introduction to Machine Learning and Stanford CS229. The takeaway Machine learning replaces hand-written rules with knobs tuned to examples, using gradient descent to find the settings. Everything else is about trust: hold data back to measure honestly, find the middle between too simple and too flexible, stack functions when a line is not enough, ask which errors matter, and check who is in the data. Try this: the next time you read "an AI that is 95% accurate", ask four questions. Accurate on what data? How rare is the thing it looks for? What does each kind of mistake cost? And has anyone checked it for the group you belong to? Sources: A.-M. Legendre (1805) and C. F. Gauss on least squares (priority dispute, as summarised in standard histories of statistics); A.-L. Cauchy (1847) on gradient descent; M. Minsky and S. Papert, Perceptrons, MIT Press, 1969; D. Rumelhart, G. Hinton and R. Williams, "Learning representations by back-propagating errors", Nature 323, 1986; J. Buolamwini and T. Gebru, "Gender Shades: Intersectional Accuracy Disparities in Commercial Gender Classification", Proceedings of Machine Learning Research 81, 2018; Stanford HAI, AI Index Report 2025 (training compute doubling about every five months) and AI Index Report 2026 (the "jagged frontier": IMO gold, 50.1% on analog clocks); G. James, D. Witten, T. Hastie, R. Tibshirani, An Introduction to Statistical Learning. All datasets in the demos are invented, and every number they show was computed and cross-checked for this piece. Go deeper: 📘 An Introduction to Statistical Learning (statlearning.com, free) 📘 Deep Learning — Goodfellow, Bengio, Courville (deeplearningbook.org, free online) ▶️ 3Blue1Brown: Neural Networks 🌐 MIT OCW 6.036 Introduction to Machine Learning