The book
The wiki read in prerequisite order as one page: every concept once, each after the ones it needs.
The Basel problem
Add up the reciprocals of the squares and the total stops at pi squared over six, a circle appearing in a question that never mentioned one.
The figure has two panels. The top one lays twelve squares in a row, of sides 1, 1/2, 1/3 and on down to 1/12, standing on one line, so the area of each square is one term of the sum. The bottom one draws the running total after each of the first forty terms as a bar, against the dashed line the totals are climbing towards.
The question is as plain as a question gets: what is 1 + 1/4 + 1/9 + 1/16 + 1/25 and so on forever, the sum of one over each square? It was posed in Basel, it stood unanswered for decades while good mathematicians chipped at it, and Euler settled it.
That the total is finite is easy. For k above 1 the term 1/k^2 is smaller than 1/((k - 1)k), which is the difference 1/(k - 1) - 1/k. Those differences cancel in pairs and add up to 1, so the whole sum is under 2. Knowing it is finite is one thing; knowing the number is another.
The approach is slow. What remains after n terms is close to 1/n, so forty terms give 1.6202 and are still 0.0247 short, and a thousand terms are still about 0.001 short. The bars in the lower panel flatten early and then creep.
The answer is pi^2/6, which is 1.6449340668. A sum of the reciprocals of the squares, built from nothing but whole numbers, turns out to be the square of pi over six.
The top panel is the same statement as an area. Each term is the area of a square of side 1/k: a unit square, then a square of a quarter its area, then a ninth, then a sixteenth. Lay every one of them down and the paint you need is pi^2/6 unit squares, a little under five thirds.
Euler's first argument was a raid. A polynomial can be rebuilt from the places where it is zero, and he treated the sine wave as an endless polynomial whose zeros sit at every whole multiple of pi. Matching one coefficient on each side gave the sum at once. The step was daring rather than sound, proper proofs came later, and the answer was right.
The number has a second life as a probability. Turn pi^2/6 upside down and you get 6/pi^2, about 0.6079, which is the chance that two whole numbers picked at random share no factor above 1. So the same constant that measures a pile of squares also measures how often a fraction is already in lowest terms.
In the tree
That reading is how the pi note gets pi out of a grid: lay the whole numbers out as points, count the ones visible from the corner, and the share of them is 6/pi^2, so counting points hands pi back. The fractions those visible points stand on are the Farey sequence, and the famous formulas measure how slowly this sum pays beside seven other rules.
The Euler-Mascheroni constant
Add 1 and a half and a third and on to one over n, take away the logarithm of n, and the difference settles on 0.5772157, a number nobody has yet placed.
Add the reciprocals of the whole numbers in order: 1, then 1 and a half, then 1 and a half and a third. That running total is the harmonic sum, and it has no ceiling. Add enough terms and it passes any number you name, but it does so unbearably slowly: it takes ten terms to pass 2.9, a hundred to pass 5.1, and a thousand to pass 7.4.
The thing it climbs like is the logarithm. Write ln n for the natural logarithm of n, the curve that rises by the same amount each time n is multiplied by the same factor. The harmonic sum of n terms and ln n grow at the same rate forever, and the interesting question is what separates them.
The figure answers it. The yellow staircase is the harmonic sum, one tread per term, standing at 1 after one term and just under 4 after thirty. The blue curve under it is ln n. The shaded strip between the two is the whole story: it is wide at the left, and by the right hand edge it has stopped narrowing.
Read the strip's width off the numbers. After one term it is exactly 1. After ten it is 0.626383. After thirty, the right edge of the figure, it is 0.593790. After a hundred it is 0.582207, and after a thousand it is 0.577716. Those numbers are falling towards something, and that something is the Euler-Mascheroni constant, written with the Greek letter gamma and worth 0.5772157 to seven places.
Why is there a strip at all? Every tread of the staircase adds one over n. Over the same stretch the curve rises by a little less than one over n, because the curve is already flattening while the tread is still using the old value. The surplus is a thin sliver, and the slivers shrink fast enough that all of them together come to a finite amount. Gamma is the total area of every sliver, counted to infinity.
The closing is slow and completely regular. At n terms the strip is wider than gamma by about one over twice n. At thirty terms that predicts a surplus near one sixtieth, or 0.0167, and the true surplus is 0.0166. At a thousand terms it predicts one two-thousandth, and delivers it. So to pin gamma down to one more decimal place by this route you need ten times as many terms, which is why nobody computes it this way.
Gamma turns up wherever a sum is traded for a curve. The commonest place is the logarithmic integral, the smooth curve that guesses how many primes lie below a number, and gamma sits in its series as a plain additive term. It is in that sense a conversion constant between counting and measuring.
What is not known about gamma is embarrassing. It has been computed to many billions of digits. No one has shown that it is not a fraction. Pi and e were both settled as irrational long ago, and gamma, the third constant of the same size and the same age, still has not been.
In the tree
The harmonic sum closing on gamma is one of the eight on the famous formulas hub, beside four other constant chasers and three systems that never settle. The same demo is the one the pi note points at when it puts its own slow estimator in that family. Where gamma does its real work here is inside the logarithmic integral of the prime counting function.
Euler's number
Split a year's interest into more and more payments and the yearly growth climbs, slows and stops at 2.718281828.
The figure is sixty points, one for each number of payments from one to sixty, and the height of a point is what a pound grows to in the year. The curve rises steeply and then flattens against the dashed line, which it never meets.
Start with one pound at an interest rate of 100 percent a year. Paid once at the end of the year, the pound becomes 2. Paid as half twice, the pound becomes 1.5 times 1.5, which is 2.25, because the second half year earns interest on the first half's interest as well.
Keep splitting. Four payments of a quarter give 1.25^4 = 2.4414. Twelve monthly payments give 2.6130. Three hundred and sixty-five daily payments give 2.71457. With n payments the rule is (1 + 1/n)^n.
Two things pull against each other. Each extra split lets interest start earning sooner, which raises the total, but the pieces being split are smaller, so what the split adds is smaller too. The second effect wins in the end and the total settles.
Where it settles is e, 2.718281828459. At sixty payments the pound is at 2.6960, short by 0.0223. The shortfall is close to e/(2n), so doubling the payments only halves it: the picture is another slow closer.
There is a fast recipe for the same number. Add the reciprocals of the factorials: 1 + 1 + 1/2 + 1/6 + 1/24 + 1/120 and on. Eleven of those terms pin e to seven decimal places, while a million payments a year pin it to five. The two recipes give the same number and cost wildly different amounts of work.
The reason e is everywhere is that it is what continuous growth costs. Anything that grows by the same proportion in equal stretches of time, money at interest, a population, a signal fading, is a power of e once the stretches are made small. Paid continuously for a year at 100 percent, a pound becomes exactly e pounds.
Like pi, e is irrational: its decimals never fall into a repeating block, so no fraction of whole numbers is equal to it, and the string 1828 appearing twice at the start is a coincidence and nothing more.
In the tree
The pi note keeps a list of elementary systems that close correctly and slowly, and (1 + 1/n)^n closing on e is one of them, beside the Wallis product and the Leibniz series closing on pi; the famous formulas draw the whole family's speeds on one board.
Famous formulas
Eight elementary rules run out to infinity. Five close on a constant, one counts the primes, one refuses to reach zero and one refuses to settle down at all.
Each of the eight is a rule a schoolchild can carry out by hand. Multiply these fractions. Add these terms with alternating signs. Count the ways this number splits into two primes. Do the rule n times and you have a number. Let n grow and that number goes somewhere, and the three things worth asking are always the same: what is the rule, where does it go, and how fast does it get there.
The third question is the one the page is really about. Two rules can land on the same constant and take a thousand times longer to do it. Speed is the property that separates a formula you would actually compute with from a formula you would only admire.
The figure puts all eight speeds side by side. It is a board of eight small panels, four across and two down, in the order of the list below. Each panel plots the gap, how far the rule stands from its target, against how far you have run the rule, with both scales logarithmic and four and a half decades of shrinking from the top of the panel to the bottom. A straight fall means the gap shrinks like a fixed power of n, and the steeper the line the faster the rule pays.
Read the board and the family sorts itself out. The five blue panels fall as straight parallel lines, five different constants paid at much the same rate. The prime count humps up before it starts falling, because the curve it is measured against overtakes it early. The Goldbach panel falls raggedly, shrinking only because the count it inverts is growing. The last panel is not a fall at all but a flat scatter, which is the whole point of it.
Not every panel has a target in the same sense. Five of them chase a number and the gap is an honest distance. The prime count is measured against a curve rather than a constant. Goldbach's panel shows one divided by the count of prime pairs, so it is a picture of a count refusing to be small. The Mertens panel shows a running total divided by the square root, and what it demonstrates is that the ratio stays put.
- The Wallis product: an endless product of fractions just above and just below one, closing on pi over two.
- The Leibniz series: one minus a third plus a fifth minus a seventh and on, closing on pi over four.
- The Basel problem: the reciprocals of the squares added up, closing on pi squared over six.
- Euler's number: one plus one over n, raised to the power n, closing on e.
- The Euler-Mascheroni constant: the harmonic sum less the logarithm, closing on gamma.
- The prime counting function: the staircase of primes, chased by two smooth curves that are only eventually right.
- Goldbach's conjecture: every even number as a sum of two primes, with a count that has never reached zero.
- The Mertens function: the Mobius marks added up, wandering against the square root of n.
Six of the eight are classical and settled. Two are not. Goldbach's is a conjecture, so its panel is a record of what has been checked and nothing else. The Mertens panel carries no claim either: the bound that its flatness suggests is the Riemann hypothesis, and nobody has it. Those two sit on the same board as the other six on purpose, because from close up an open question and a theorem look identical.
In the tree
The figure above draws all eight gaps closing on one set of axes, and each page opens on a figure of its own. The pi note counts pi out of the lattice by a ninth route of the same family, slow and honestly noisy, and says so.
The Farey sequence
Every fraction between zero and one whose bottom number is at most Q, written in order; each new Q slips a few new fractions between the old ones and never moves one.
Pick a whole number Q and write down every fraction between 0 and 1 whose denominator is Q or less, each in lowest terms, in increasing order. That list is the Farey sequence of order Q. For Q equal to 5 it reads 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1.
The figure grows the sequence one order at a time, a row per Q. The dots already on a row stay put on every row below it, and each new row only adds dots, in yellow, between the old ones. Order 1 holds 0/1 and 1/1. Order 2 adds 1/2, order 3 adds 1/3 and 2/3, order 4 adds 1/4 and 3/4, and 2/4 is not new because it is 1/2 already.
How many does each order add? A fraction a/Q is new exactly when a and Q share no divisor bigger than 1, so the count of new fractions at order Q is the count of numbers from 1 to Q that share nothing with Q. For a prime Q that is every number below it, Q minus 1, which is why the prime rows in the figure carry the most yellow.
Two neighbours in the list are always as close as fractions of their size can be. Take 2/5 and 1/2, side by side at order 5: the cross products are 2 times 2 and 5 times 1, and they differ by exactly 1. That holds for every pair of neighbours at every order, and it is the rule that decides what comes between them.
Between two neighbours a/b and c/d the first fraction to appear, at some later order, is the mediant, the fraction (a + c)/(b + d) made by adding tops and adding bottoms. Between 1/3 and 1/2 the mediant is 2/5, and it arrives at order 5, exactly the row where the figure shows it. The whole sequence can be built by mediants alone, starting from 0/1 and 1/1.
The stack above draws the same fractions another way. Lay a ruler with n equal divisions on the unit line for every n up to Q, and count how many rulers put a mark at each point: a fraction a/b is marked by every n that b divides, so the tallest bars are the simplest fractions and the primes stand out as the scales that mark the most new points.
In the tree
The grid of every design at every scale, laid over itself, lights up at the Farey fractions, and the Farey stack note reads that moire as a diagram of the fractions and of how evenly they spread. The circles standing on the same fractions are in the Apollonian demo, and counting the lit points of the grid is how pi comes out of the grid.
The greatest common divisor
The largest number dividing two others at once; Euclid finds it by taking remainders, and when it comes out 1 the two numbers share nothing.
A divisor of a number is a number that goes into it exactly. The divisors of 24 are 1, 2, 3, 4, 6, 8, 12 and 24. The divisors of 36 are 1, 2, 3, 4, 6, 9, 12, 18 and 36. Six numbers appear on both lists, and the largest of them is 12, so the greatest common divisor of 24 and 36 is 12.
There is always one. The number 1 divides everything, so the shared list is never empty, and no divisor of 24 is bigger than 24, so the list is finite and has a largest member.
Listing all the divisors is a bad way to find it. Euclid's way is to take remainders and never factor anything. Divide the larger by the smaller, keep the remainder, and repeat with the smaller and the remainder until the remainder is 0. The last number before the 0 is the answer.
Take 252 and 198. Divide 252 by 198 and the remainder is 54. Divide 198 by 54 and the remainder is 36. Divide 54 by 36 and the remainder is 18. Divide 36 by 18 and the remainder is 0. The answer is 18, found in four steps, and no factorisation of either number was needed.
It works because a number dividing both 252 and 198 divides the difference too, and the remainder is just a pile of differences. So the pair (252, 198) and the pair (198, 54) have exactly the same common divisors, and every step shrinks the numbers while leaving the answer untouched. The numbers shrink fast, so this stays quick on numbers with hundreds of digits.
Two numbers are coprime when their greatest common divisor is 1. They need not be prime themselves. 8 and 15 are coprime, because 8 is built from 2s and 15 from a 3 and a 5, and the two builds have no part in common.
Coprimality is what lowest terms means. The fraction 252 over 198 reduces by 18 to 14 over 11, and 14 and 11 are coprime, so it will not reduce again. Every fraction has exactly one lowest-terms form, and the greatest common divisor is what gets you there in one step.
The figure is a 24 by 24 board. The cell in column a and row b stands for the pair of numbers (a, b), with a running 1 to 24 left to right and b running 1 to 24 bottom to top. A cell is lit when a and b are coprime, and otherwise shaded by how much they share, faint for a small divisor and bright blue for a large one.
Three things read straight off it. The bottom row and the left column are fully lit, because everything is coprime to 1. The diagonal is the brightest line on the board, because a number shares all of itself with itself. And the shaded cells fall into slanted families, the darkest and commonest being the even column and even row crossings, where the pair shares a 2.
Count the lit cells and there are 359 of 576, a little under two thirds. That ratio is not an accident of the window. Pick two whole numbers at random and the chance that they are coprime settles at 6 divided by pi squared, which is 0.6079 and a bit. Why a circle constant should decide a question about divisors is a longer story and it is told elsewhere in the tree.
In the tree
That density is the whole point of pi out of the stack, which counts the lit points of this same grid and hands back pi from the count, and it is the question the coprimality spine asks again with the grid replaced by a design. What base 3 hides asks it on the hexagonal lattice instead of the square one, where the shared-divisor rule is the same and the constant that falls out is not. The lit cells are also the fractions in lowest terms, which is exactly the list drawn by the Farey sequence. Seen from the corner of a grid, those same cells are the visible lattice points.
The Kronecker product
Stamp a small picture into every filled cell of itself and it grows a level; that one move builds every design on this site.
Take a small picture drawn on a grid of cells, some filled and some empty. The one on the left of the figure is three cells by three with only the centre empty: eight filled cells around one hole.
The Kronecker product is a way to multiply two such pictures. To multiply picture A by picture B, take A and replace every filled cell of A by a whole copy of B, and every empty cell of A by an empty block the size of B. The result is a bigger grid, as wide as the width of A times the width of B.
Multiply the eight-around-a-hole picture by itself and you get the middle panel of the figure: nine by nine, sixty-four filled cells, one hole of three by three in the middle and eight small holes around it, one inside each copy. Multiply once more by the same picture and you get the right panel: twenty-seven by twenty-seven, five hundred and twelve filled cells, and holes of three sizes.
The order matters. A times B replaces the cells of A with copies of B, so the big shape comes from A and the fine detail comes from B. With the same picture on both sides the difference vanishes, and that is the case that grows a fractal: a picture multiplied by itself again and again looks the same at every scale.
Counting is the easy part. A filled cell of A meeting a filled cell of B gives one filled cell of the product, so the filled cells multiply: eight times eight is sixty-four, and eight times eight times eight is five hundred and twelve. The side multiplies too: three, nine, twenty-seven. After n rounds the picture has 8^n filled cells on a side of 3^n, which is how a fractal's dimension will be read off later.
The name comes from matrices. Write a picture as a table of ones and zeros, one for filled and zero for empty. The Kronecker product of two tables multiplies every entry of the first by the whole second table and lays those blocks out in the pattern of the first. A one times the table is the table, a zero times the table is a block of zeros, and that is exactly the stamping rule above, so the picture and the matrix say the same thing.
There is a looser version of the same move. Instead of one picture stamped into every filled cell, keep a small palette of pictures and a grid whose entries say which one goes where: entry by entry, lay down the picture the entry names, and the result is again as wide as the grid times the width of one picture. The Kronecker product is the case where the palette holds two pictures, a blank one and the picture itself, and the grid is a pattern of filled and empty cells choosing between them. A bigger palette is not harder to draw; it is only harder to count, because the filled cells no longer multiply and have to be added up picture by picture.
In the tree
Every design here is one small picture, a rule on the corners of a cube, grown by the Kronecker product. The core note states it as move two, the sponge demo grows a cube rule level by level, and the words demo multiplies two different pictures so the order shows.
The Leibniz series
Add one, take away a third, add a fifth, and the running total swings over and under a quarter of pi, closing on it very slowly.
The figure is thirty dots, one for each running total. The blue dots sit above the dashed line and the orange dots below it, and the thin thread joining them in order shows the swing. The dashed line is a quarter of pi.
The rule is short. Start at 1, take away 1/3, add 1/5, take away 1/7, add 1/9, and carry on: the denominators are the odd numbers in order and the signs alternate.
Every term is smaller than the term before it and points the other way, so each step carries the total across the line rather than up to it. The odd steps land above the limit and the even steps land below it, which is the alternation the figure draws.
That overshooting is useful. The limit is trapped between any two neighbouring totals, so a total is never wrong by more than the next term, 1/(2n + 1). After thirty terms the total is 0.7771 and the error is under 1/61, about 0.016, against a quarter of pi at 0.7853982.
It is the slowest of the classical closers. Halving the error means doubling the number of terms, so a millionth of accuracy asks for about half a million terms. Nobody computes pi this way; the series is here because it is so plain.
There is a free trick in the trapping. Since the limit lies between two neighbouring totals, their midpoint is a much better guess than either: the twenty-ninth and thirtieth totals average to 0.78554, off by 0.00014, about sixty times closer than the thirtieth total on its own.
The series comes from the rule that turns a tangent back into an angle, read at tangent 1. The angle whose tangent is 1 is 45 degrees, and 45 degrees measured in the way that makes a half turn equal pi is pi/4, which is why a sum of odd reciprocals knows about a circle at all.
The Wallis product is the same kind of statement in the same family: correct, convergent and slow. The difference is in the approach. The product climbs from below and never crosses its limit, while this series crosses at every single step.
In the tree
The pi note counts pi a different way, out of the density of the visible points of a grid, and puts that count in the same family as this series and the product: correct, convergent, not fast. The neighbouring pages here are the Wallis product and the Basel problem, and the famous formulas put all of them on one board of speeds.
Parity
Every whole number is even or odd, and that single bit, read on each coordinate at once, is the whole of what a design uses to choose its cells.
A whole number is even when it divides by two and odd when it does not. That is its parity, and there are only ever two answers. Zero is even, one is odd, and from there the answers alternate for ever.
Parity is easy to work with because it survives arithmetic. Even plus even is even, odd plus odd is even, even plus odd is odd. You never need the numbers themselves, only their two answers, and that is what makes parity a rule a machine can apply to a grid of any size.
A point on a line has one coordinate, so it has one parity. A cell in a grid has two, a row number and a column number, so it carries two parities at once, and there are four ways that can come out: both even, row even and column odd, row odd and column even, both odd.
The figure is a six by six grid with every cell painted by that pair. Four colours appear, nine cells of each, and they repeat every second row and every second column, so the whole picture is one two by two tile stamped nine times. Wherever you stand in the grid, you are in exactly one of the four classes, and moving one step in any direction moves you to another.
In three dimensions the same reading gives three parities and eight combinations. Write even as 0 and odd as 1 and those eight combinations are the eight corners of a cube: (0,0,0), (0,0,1), (0,1,0) and so on up to (1,1,1). Every cell of a three-dimensional grid, however far from the origin, belongs to exactly one corner.
That is the move the tree is built on. A design is a choice of which corners to keep. Keep a corner and every cell of that class is filled; drop it and every cell of that class is void. In two dimensions there are four corners, so 2^4 = 16 designs. In three there are eight corners, so 2^8 = 256. The list is finite and it is short enough to write down.
The Sierpinski carpet is one such choice. Lay a three by three block down, number the rows and columns 0, 1, 2, and throw away the one cell whose row and column are both the middle number. Eight cells survive of nine, and that rule, repeated, is the carpet.
The eight answers are also a number. Read the corners in binary order and write 1 for kept and 0 for dropped, and the byte you get is what the tree calls the design's code. The carpet is code 7 in the plane, the Menger sponge is code 23 in the cube, and the code is the whole of the design's name.
Past base 2 the reading widens. Parity is a coordinate's last binary digit, and the general rule reads a whole digit instead of a bit, one digit per axis, with base digits to choose from. At base 3 each coordinate has three residues rather than two, so a plane design chooses among nine cells rather than four. The idea does not change: the rule looks at one digit of each coordinate and nothing else.
In the tree
Choosing corners of the parity cube is move one of the tree, written up in the core, and the automata reads the same eight corners as a rule on a cell and its two neighbours. The universe demo is the gallery of every choice in dimensions 1 to 4, the sponge demo lets you pick corners of a cube and grow them, and the wolfram demo shows the eight corner bits of a rule as a stamp. Move two, stamping the chosen cells into themselves, is the Kronecker product.
Prime numbers
A prime is a number whose stones make only one rectangle; every other number is built from primes, and the supply never runs out.
A whole number is prime when exactly two numbers divide it, itself and 1. Lay n stones on a table and try to arrange them in a rectangle. Twelve stones make 2 by 6 and 3 by 4, so 12 is not prime. Thirteen stones make only the single row 1 by 13, so 13 is prime.
The number 1 is left out on purpose. It has one divisor, not two, and admitting it would break the one rule that makes primes worth having.
That rule is that every number above 1 is a product of primes in exactly one way, apart from the order you write the factors in. 60 is 2 times 2 times 3 times 5 and nothing else will do. The primes are the parts, and every other number is an assembly of them.
The figure is the oldest way of finding them, the sieve of Eratosthenes, run on the first hundred numbers laid out as ten rows of ten, 1 at the top left and 100 at the bottom right. Keep 2 and strike out every later multiple of 2. Move to the next number still standing, 3, keep it, strike out its multiples. Then 5, then 7. Whatever is still standing at the end is prime.
Every struck cell in the figure is tinted by the first prime that struck it, so the colours read as a history of the sieve. The grey cells are the even numbers, taken by 2. The next tint is the odd multiples of 3, the next the multiples of 5 that survived 2 and 3, and the last is the three cells 49, 77 and 91, which no prime below 7 could reach. The 25 cells still lit are the primes below 100.
The sieve finishes after 7 because 11 times 11 is 121, already off the board. Any composite number up to 100 must have a factor at or below 10, so four primes clear the whole hundred. To sieve up to a million you would need only the primes up to a thousand.
Primes thin out as you go. There are 25 below 100, 168 below 1000 and 1229 below 10000, so the share falls from about one in four to one in six to one in eight. The honest summary is that a number near n is prime about one time in ln n, which fades slowly and never reaches zero.
The gaps between them can be made as long as you like. Take the product of all the numbers from 1 to 100, call it P, and look at P + 2, P + 3 up to P + 100. Each one is divisible by the number you added, so that is a run of 99 numbers in a row with no prime in it, and the same trick gives a run of any length.
Even so, the primes never stop. Suppose you had a complete list of them. Multiply the whole list together and add 1. The new number leaves remainder 1 when divided by any prime on the list, so none of them divides it, so either it is prime itself or it has a prime factor the list missed. The list was not complete after all. Euclid wrote that down and nobody has needed to improve on it.
Those two facts sit together and neither one softens the other. Primes get sparse, they leave arbitrarily long empty stretches, and they still go on forever.
In the tree
The primes demo runs this sieve on a larger board and reads the same numbers three more ways: as stones in a rectangle, as a running count against x / ln x, and as a stack of grids whose layers fall out of step everywhere except at the primes. The Ulam spiral demo winds the whole numbers outward from the middle with the primes lit, where every straight line reads a quadratic and some of those lines are strangely prime-rich. How much a new scale adds to the Farey sequence is a test of primality, which the Farey stack note reads straight off the picture, and the coprimality spine asks the harder version of the question, which numbers of a design are prime at all.
Visible lattice points
Stand at a corner of the grid and some points hide behind nearer ones; the ones you can see are the pairs sharing no divisor, and counting them hands back pi.
The figure is a window on the grid, a hundred points across and a hundred up, with the corner you stand at in the lower left. Every point you can see from that corner is drawn as a full blue cell. Every point hidden behind a nearer one is left empty apart from a small square at its centre, and the smaller that square, the more thoroughly the point is hidden. Of the ten thousand points in the window, 6087 are full.
Put the corner at (0, 0) and pick the point (a, b), meaning a steps right and b steps up. Draw the straight line from the corner to it. The point is visible when no other grid point sits on that line between the two, and hidden when one does, because from the corner the two lie in the same direction and the nearer one stands in front.
Two whole numbers share a divisor when some whole number bigger than 1 divides both of them with nothing left over. 6 and 9 share the divisor 3. 6 and 35 share nothing, since 6 is built from 2 and 3 while 35 is built from 5 and 7. The rule of the picture is that (a, b) is visible exactly when a and b share no divisor.
One direction is easy to see. If some g bigger than 1 divides both a and b, then (a/g, b/g) is a grid point as well, it sits on the same line out of the corner, and it is g times nearer, so it hides (a, b). The other direction is the same sentence backwards: a grid point on the line between the corner and (a, b) is some fraction of the way along, the same fraction of both steps, and the bottom of that fraction divides a and b alike.
So every hidden point is a scaled copy of a visible one. Take any point, let g be the largest number dividing both its steps, and the point is exactly g times the visible point (a/g, b/g). That is what the figure shades: a hidden point owned by the scale g gets a square of side one over g, so the deeper a point is buried, the smaller its mark.
Read that backwards and the whole grid is the visible set stamped down over and over. Lay the visible points on the grid at scale 1, then again at scale 2, then at scale 3, and so on for every whole scale. The scale-2 copy lands on the points whose two steps are both even, the scale-3 copy on the points whose steps are both divisible by three, and between them the copies cover every point once and never twice.
Now count. A window n by n holds n^2 points, and the share of them that are visible settles down as the window grows. It does not settle on a round number. It closes on 6/pi^2, which is 0.6079 and a little more, so about three points in every five are visible however far you push the window out.
The pi in that constant comes from the primes. For a prime p, one pair of steps in p^2 has both steps divisible by p, so the share of pairs p does not spoil is 1 - 1/p^2. A pair is visible when no prime at all spoils it, which multiplies those shares over every prime, and that product is 1 divided by 1 + 1/4 + 1/9 + 1/16 + ..., the sum of one over every square. That sum is the famous one worth pi^2/6, so the share of visible points is its reciprocal, 6/pi^2.
Turn the constant round and the counting becomes a measurement. If the visible share of a window is d, then
Count the full cells of the figure, divide 6087 by 10000, and the formula gives 3.1396, which is pi to three figures from nothing but dots on a grid. It is an honest way to the constant and a slow one; how slowly it closes, and what happens when the grid is three dimensional instead of two, is the pi note's business.
The slider grows the window from eight points across to three hundred. The line under the picture counts the visible points, the points in the window and the share between them, and that share runs high in the smallest windows and settles towards 0.608 as you push the slider right. Turning the shading off flattens every hidden point to one tone, leaving only the two kinds of point.
In the tree
Counting these points is how pi comes out of the grid. The same count restricted to the cells of one design, where every design gets its own constant, is the coprimality spine. Written as fractions rather than as points, the visible set is the Farey sequence, and the stack of scales above is read there and in the Farey note.
The Wallis product
Multiply 4/3 by 16/15 by 36/35 and keep going, and the running product climbs forever without ever reaching half of pi.
The figure is forty bars. Bar n is the product of the first n factors, and the dashed line near the top is the number those products are climbing towards, half of pi. The first bar is short, the fortieth almost touches the line, and no bar ever crosses it.
The factors are built out of the even numbers. Factor k is 4k^2 / (4k^2 - 1), the square of the kth even number over that same square less one. The first four are 4/3, 16/15, 36/35 and 64/63.
Every factor is bigger than 1, so the running product only ever climbs. Every factor is also close to 1, and closer the further out you go: by the time k is 40 the factor is 6400/6399. The climb never stops, and it slows down fast.
Since 4k^2 - 1 = (2k - 1)(2k + 1), factor k is (2k)(2k) / ((2k - 1)(2k + 1)). Splitting each factor into its two halves gives the form the product is usually written in: 2/1 times 2/3 times 4/3 times 4/5 times 6/5 times 6/7 and on. Every even number is used twice on top and every odd number twice underneath.
Half of pi is 1.5707963. After forty factors the product is 1.5611, short by about 0.0097. After a thousand factors it is 1.5704, short by about 0.00039. The gap shrinks like one over four times the number of factors, so every extra decimal place costs about ten times as many factors. The product is a true statement about pi and a poor way to compute it.
Nothing in the recipe mentions a circle. The factors are ratios of whole numbers, the rule for making them is arithmetic, and pi arrives at the end anyway. That is the whole reason the product is famous.
Here is one place to see where the pi sits. For any whole number n above 1, 1 - 1/n^2 = (n - 1)(n + 1)/n^2. Multiply those from n = 2 up to n = N and almost everything cancels: the numerators of one factor eat the denominators of the next, and what is left is (N + 1)/(2N), which settles at exactly 1/2.
Now split that product in two. The even n, which are n = 2k, give the factors 1 - 1/(4k^2), and those are the Wallis factors upside down, so they multiply to 2/pi. The odd n, which are 3, 5, 7 and on, must therefore multiply to (1/2) divided by (2/pi), which is pi/4. The same product, read over the odd numbers instead of the even ones, is the area a square keeps when you punch holes in it forever.
In the tree
The odd half of the product is the area of the Wallis sieve, and the pi note uses that sieve to explain why no single fixed design can hold pi: one design has one ratio, and pi needs a product of changing ones. The move the sieve makes, a different tile folded in at every scale, is the one the words demo lets you build by hand, and the famous formulas race this product against seven other rules of the same kind.
Burnside's lemma
Counting arrangements that turning and flipping should not tell apart, by averaging how many each symmetry leaves untouched.
Colour each of the four cells of a two by two square either blue or grey. There are two choices per cell and four cells, so there are 16 arrangements. Now decide that two arrangements are the same thing if one can be turned or flipped into the other, the way a tile laid on a floor is the same tile whichever way round you set it down. How many genuinely different tiles are there?
Counting by hand is possible here and the answer is 6, but the honest problem is that dividing 16 by 8, the number of symmetries, gives 2, which is wrong. Dividing fails because some arrangements are left unchanged by some of the symmetries, so they are not counted eight times over. Burnside's lemma is the repair.
First, list the symmetries of the square. There are four turns: by nothing, by a quarter, by a half and by three quarters. There are four mirrors: across the vertical middle, across the horizontal middle, and across each of the two diagonals. Eight in all, and every way of picking the square up and putting it back down is one of them.
Now ask, for each symmetry, how many of the 16 arrangements it leaves looking exactly as they were. Doing nothing leaves all 16. A quarter turn sends each cell to the next one round, so an arrangement survives only if all four cells match, which allows 2. The half turn swaps the cells in two opposite pairs, so each pair must match and the two pairs are free, which allows 4. The three-quarter turn is like the quarter turn, 2. Each of the two middle mirrors swaps two pairs, so 4 each. Each of the two diagonal mirrors holds two cells still and swaps the other two, leaving three free choices, so 8 each.
Add those up: 16 + 2 + 4 + 2 + 4 + 4 + 8 + 8 = 48. Divide by the eight symmetries and you get 6. That is Burnside's lemma: the number of genuinely different arrangements is the average, taken over the symmetries, of how many arrangements each one leaves untouched.
The figure lays out all 16 arrangements in six rows, one row per class, blue for a filled cell and grey for an empty one. The top row is the single all-grey tile. The second row is the four tiles with exactly one blue cell, which are all the same tile turned. The third row is the four with two blue cells side by side, an edge of the square. The fourth row is the two with the blue cells on a diagonal, and there are only two of them because a diagonal pair maps to itself under the half turn. The fifth row is the four with three blue cells, and the last row is the single all-blue tile. Count the tiles in the six rows: 1 + 4 + 4 + 2 + 4 + 1 = 16, every arrangement once.
The fourth row is the reason plain division fails. Its two tiles have a genuine symmetry of their own, so the eight symmetries of the square only produce two distinct copies of each, not eight. The lemma handles that automatically, because an arrangement with extra symmetry shows up extra times in the fixed counts, which is exactly the compensation needed.
Why the averaging works is a counting trick worth seeing. Make a list of every pair consisting of a symmetry and an arrangement that symmetry leaves untouched. Counting the list one symmetry at a time gives the 48 above. Counting it one class at a time gives 8 for every class, always the group size, because a class of size m has 8/m symmetries fixing each of its members. So the list has 8 entries per class, and 48 divided by 8 is the number of classes.
Nothing about the argument is special to a two by two square. Necklaces of coloured beads counted up to rotation, the ways of painting the faces of a cube, patterns on a wallpaper strip: whenever the question is how many arrangements there are once some group of motions is declared harmless, the same average answers it, and the fixed counts are usually easy because a symmetry that shuffles cells in cycles forces every cycle to be one colour.
In the tree
The tree's own count is this count. A design is a choice of which corners of a cube to fill, two designs that differ only by turning or reflecting the cube are the same design, and the core states the census that follows. A design is a Boolean function carries the classification that census is taken in, and the universe demo draws every class in each dimension and base with the Burnside counts beside them. The arrangements being classified are choices made on parities, which is parity.
Cellular automata
A row of cells, a rule that reads each cell with its two neighbours, and a new row written underneath; run it and the rows draw a picture.
Draw a long row of cells and switch each one on or off. That row is the whole state of the world. Everything that happens next is decided by one rule applied to every cell at the same moment.
The rule looks at three cells: the cell itself and its two neighbours, left and right. Three cells that are each on or off make eight possible patterns, from all three off to all three on. The rule has to answer on or off for each of those eight, so a rule is eight answers.
Eight answers, each a 0 or a 1, is a byte, and a byte is a number from 0 to 255. That is how these rules are named. Write the eight answers in order and read them as a binary number and you get the rule's number, so there are exactly 256 rules of this kind and every one of them has a name.
Apply the rule to every cell at once and write the result as a new row under the old one. Do it again and again, and the rows stack into a picture with space running across and time running down. That picture is all there is to see, and it is very different from one rule to the next.
Rule 90 says: switch on exactly when one of your two neighbours is on, but not both. The cell's own state is ignored entirely. The figure runs it from a single live cell for 64 generations and the result is a triangle of triangles, holes inside holes, growing without ever repeating. It is Pascal's triangle read even and odd, the odd entries lit and the even ones left dark, sheared so the rows line up square.
Rule 110 is the famous one. Started from a soup it makes patches of stripes with small structures drifting between them, colliding, and coming out as other structures. Nothing settles and nothing repeats, and it has been shown that with the right starting row it can carry out any computation a computer can. Three cells and eight answers are enough.
The slider above walks all 256 of them. Most do nothing interesting: they die out, or fill the plane, or settle into stripes. A handful draw triangles like rule 90, and a smaller handful never settle at all. That the whole family is finite is the point, because it can be examined one rule at a time rather than argued about.
The eight patterns are worth a second look. Three cells each on or off is exactly three bits, and three bits are the eight corners of a cube. So a rule is a choice of which corners to switch on, which is the same kind of object as the choice of corners that makes a design in parity. The 256 rules and the 256 three-dimensional designs are the same 256 things read two ways.
Conway's Life is the two-dimensional cousin. The cells sit on a grid instead of a line, the neighbourhood is the eight cells around each one instead of two, and the rule reads only how many of those eight are alive: a dead cell with exactly three live neighbours is born, a live cell with two or three stays alive, everything else dies. Those two clauses are enough to produce blocks that sit still, blinkers that flash, and gliders that walk across the grid for ever.
Life's rule only counts. It asks how many of the eight neighbours are alive, never which ones, so a live neighbour on the left and a live neighbour on the right are the same news. Rules that only count are called outer-totalistic, and most of the 256 line rules are not: rule 110 can tell its left neighbour from its right one, and that is part of why it does so much.
Nothing forces the neighbourhood to be the cells next door, either. Pick any fixed set of positions around a cell, count how many of them are alive, and the same two clauses of Life run on that set instead. The set is just a picture drawn around the centre, so any design can be handed to the rule as its neighbourhood and asked what it does.
In the tree
The automata proves the identity above, that an elementary rule and a three-dimensional design are one object, and follows what the identity does and does not buy. The wolfram demo runs any of the 256 rules beside the design card the same byte fills in, the life demo runs Conway's rule from a soup or a glider, and mrlylife swaps the neighbourhood for any design the tree draws and runs the rule on that instead.
Euler's totient
Phi of n counts how many of the numbers 1 to n share nothing with n; it sinks for numbers with many small factors and hits its ceiling at every prime.
Write out the numbers from 1 to n and keep only the ones coprime to n, the ones whose greatest common divisor with n is 1. The count of survivors is Euler's totient, written phi(n).
Try n = 12. Strike the even numbers and the multiples of 3, and 1, 5, 7 and 11 are left. So phi(12) = 4. Try n = 10 and 1, 3, 7 and 9 survive, so phi(10) = 4 as well.
The value at 1 is 1, since the only number in the list is 1 itself and 1 shares nothing with anything. It is a convention that pays for itself everywhere else.
A prime is the easy case. If p is prime, nothing below it shares a factor with it, so every one of 1 to p - 1 survives and phi(p) = p - 1. That is the ceiling: no n above 1 can do better, because n itself always fails the test.
A prime power is nearly as easy. To count what survives 9, strike only the multiples of 3, which are 3, 6 and 9, leaving 6. In general phi(p^k) = p^k - p^(k-1), one in every p struck out and the rest kept. So phi(8) = 8 - 4 = 4 and phi(27) = 27 - 9 = 18.
Two coprime numbers multiply cleanly. If a and b share nothing then phi(a b) = phi(a) phi(b). Check it on 12, which is 4 times 3: phi(4) = 2 and phi(3) = 2, and 2 times 2 is 4, which is what the strike-out above gave. Check it on 15, which is 3 times 5: phi(3) = 2 and phi(5) = 4, and 2 times 4 is 8.
The coprime condition is not decoration. 8 is 4 times 2, but phi(4) phi(2) = 2 times 1 = 2 while phi(8) = 4. The rule fails because 4 and 2 overlap, and the prime power rule is what you use instead.
Those two rules together compute anything. Split n into prime powers, take the totient of each, multiply. For 60, which is 4 times 3 times 5, that is 2 times 2 times 4, so phi(60) = 16. The same sum written as one formula is n multiplied by (1 - 1/p) for each distinct prime p dividing n.
The figure draws phi(n) as a bar for every n from 1 to 60, with a hairline running along the ceiling n - 1. The yellow bars are the ones that touch the hairline. They touch it exactly at the primes, since phi(n) = n - 1 says every smaller number is coprime to n, which says n has no factor to share.
The blue bars fall away from the line in a pattern you can read. The deepest dips are the numbers made of many small primes: 30 and 60 each keep only a little over a quarter of their range, because they lose half to 2, then a third of what is left to 3, then a fifth of that to 5. Numbers that are a prime times a prime sit close under the line, and the whole picture fans out into bands rather than scattering.
In the tree
The totient is the counter behind the Farey sequence: the fractions a new denominator n adds are exactly the a/n in lowest terms, so the row grows by phi(n) and the prime rows grow the most. The Farey stack note turns that into a reading of primality off the stack, and pi out of the stack counts the coprime points of the whole grid as a running sum of totients before inverting the density into pi.
Ford circles
Above every fraction sits a circle resting on the number line, the simpler the fraction the bigger the circle, and no two of them ever overlap.
Draw a horizontal line and mark the fractions on it. Over the fraction a/b, written in lowest terms, place a circle that touches the line at that exact point and has radius 1/(2 b^2). That is the Ford circle of a/b, and there is one for every fraction, for ever.
The bottom number does all the work. Over 0/1 and over 1/1 the radius is 1/2, so those circles are as tall as the gap between the two fractions is wide. Over 1/2 the radius is 1/8, over 1/3 it is 1/18, over 1/7 it is 1/98. Each step up in the denominator shrinks the circle by the square, so the simple fractions are the big circles and the awkward ones are specks.
The figure is the unit interval with every circle of denominator 8 or less drawn as an outline, tinted from blue for the small denominators to yellow for the large, with a dot on the line at the point each one touches. The two halves at the far left and far right are the circles over 0 and 1. The big one in the middle stands over 1/2, the two beside it over 1/3 and 2/3, and so on down to the specks over the sevenths and eighths.
No two of these circles ever cross. Two of them touch, at a single point, exactly when their fractions are neighbours in the Farey sense, meaning that a/b and c/d satisfy a d - b c equal to plus or minus 1. Any other pair sits strictly apart.
That is a short calculation and worth seeing once. The horizontal gap between the two touching points is (a d - b c)/(b d), and the vertical gap between the two centres is the difference of the radii. Square both, add them, and compare with the square of the sum of the radii. Everything cancels except one term, and the two agree exactly when (a d - b c)^2 is 1. So the whole arrangement of touching is decided by that one cross product, which is precisely the rule that governs neighbours in the Farey sequence.
Two touching circles and the line between them leave a small curved triangle with three corners. The largest circle that fits in that gap is again a Ford circle, and it stands over the mediant of the two fractions, the one you get by adding the tops and adding the bottoms. Between 1/3 and 1/2 the gap is filled by the circle over 2/5. So the picture builds itself: start with the circles over 0 and 1, fill every gap with a mediant, and you have written down every fraction and every circle.
That gap-filling move is the beginning of something bigger. Three circles that all touch each other leave two curved triangles, and each of them holds exactly one circle touching all three. Draw both, and now there are more triples, each with its own gaps. Keep going and the circles multiply without end, their areas eating up almost all the room, and what is left over is a dust called an Apollonian gasket. The Ford circles are one slice of one such packing, the slice that sits on a straight line, with the line itself playing the part of a circle of infinite radius.
The whole picture also repeats itself. Shift everything one unit to the right and it lands back on itself, because the circle over a/b goes to the circle over (a + b)/b, which has the same denominator and so the same radius. Look instead at what happens near a single fraction and you find the same arrangement again at a smaller scale, which is the geometric face of the fact that a fraction with a big denominator has little room around it.
In the tree
The Apollonian gasket note identifies the circles of one integer packing that rest on the line as exactly these, so the packing's shadow on the line is the Farey stack, and the Farey stack note reads that same stack as a moire of rulers. The Apollonian demo grows the packing and lays the stack underneath it. The fractions the circles stand on are the ones the Farey sequence lists, and lowest terms is the greatest common divisor doing its job.
The Gaussian integers
Numbers of the form a plus b times i, drawn as a square lattice, where each point has a size and some ordinary primes break in two while others stay whole.
Let i be the number whose square is -1. A Gaussian integer is anything of the form a + b i with a and b ordinary whole numbers. Draw a across and b up and they are the corners of a square grid, one point per cell, stretching out in all four directions.
Adding two of them adds the coordinates, so the sum of two grid points is a grid point. Multiplying works out too, because i^2 folds back to -1: (2 + i)(2 - i) = 4 - 2i + 2i - i^2 = 5. So the grid is closed under both operations, and it is a world you can do arithmetic in.
Every point gets a size, called its norm: the norm of a + b i is a^2 + b^2. That is the square of the distance from the origin, so it is always a whole number and never negative. The one fact that matters about it is that it multiplies: the norm of a product is the product of the norms. Check the line above, 5 times 5 is 25, and 25 is the norm of 5.
Four points have norm 1: 1, -1, i and -i. These are the units, the Gaussian version of plus and minus one, and multiplying by one of them turns the picture a quarter turn. They are why every pattern in this world has four-fold symmetry.
A point is prime here when it cannot be written as a product of two points of norm bigger than 1. The norm rule makes this checkable: to split a point of norm N, you need two points whose norms multiply to N, so a point whose norm is an ordinary prime cannot split at all.
Now the interesting part. An ordinary prime, sitting on the horizontal axis, may or may not survive the move into this larger world. Three small cases tell the whole story.
Five splits. 5 = (2 + i)(2 - i), two points of norm 5 each, and neither of them can be broken further. So 5 is no longer prime once you allow i.
Two splits too, but oddly. 2 = (1 + i)(1 - i), and 1 - i is just 1 + i turned by a unit, so 2 is essentially a square: the same prime used twice. It is the only ordinary prime that behaves this way, and it is why the figure has a special point at 1 + i and its three reflections.
Three stays whole. To break 3 you would need a point of norm 3, which means whole numbers with a^2 + b^2 = 3. The squares available are 0, 1 and 4, and no two of them add to 3, so there is no such point and 3 stays prime. A prime that survives like this is called inert.
The rule behind the three cases is old and exact. An odd prime splits when it is one more than a multiple of four, and stays whole when it is three more. So 5, 13, 17 and 29 break up, and 3, 7, 11 and 19 do not. Another way to say the same thing is that a prime is the sum of two squares exactly when it is of the form 4k + 1, which is Fermat's theorem on two squares.
The figure marks every Gaussian prime inside a window reaching 20 steps in each direction. Blue is a point whose norm is an ordinary prime, which is a piece of a split prime, and there are a great many of them, arranged in a four-armed snowflake. Orange is an inert prime, and there are just sixteen: 3, 7, 11 and 19, each with its minus and each with its i copy, so eight on the horizontal axis and eight on the vertical. The orange points appear nowhere else, because an inert prime keeps sitting on an axis no matter how you turn it.
In the tree
The primes in the plane demo draws this window at any reach and switches the lattice from square to hexagonal, where the same three fates appear on a different grid. That switch is the subject of what base 3 hides: base 2 puts a design on the square lattice, which is this one, base 3 puts it on the hexagonal lattice, and which lattice a design lives on decides which constant it hides.
Graphs
Dots joined by lines and nothing else; count the lines at a dot for its degree, write the joins in a table of ones, and a design's filled cells become a network.
A graph is two lists. A list of dots, and a list of lines, each line naming the two dots it joins. The dots are called vertices and the lines are called edges. Nothing is said about where a dot sits or how long a line is, only about which pairs are joined, so the same graph can be drawn a hundred ways and stay the same graph.
The figure is one. It starts from a shape: the triangle you get by taking a two by two block, keeping three cells and dropping the fourth, then stamping that rule into itself three times. The result is 27 filled cells on a grid 8 cells wide. Put a dot in every filled cell and draw a line between two dots when their cells share a whole side. Cells that meet only at a corner are not joined.
That gives 27 dots and 26 lines. The dots are inked by how many lines meet them, and that count is the degree of the dot. Ten dots in the figure are yellow and have one line each, nine are blue and have two, and eight are pink and have three. No dot has four.
Add up all the degrees and you get 10 + 18 + 24 = 52, which is exactly twice the number of lines. That is never a coincidence. Every line has two ends, so counting ends dot by dot counts every line twice. It is the first fact about graphs worth remembering, and it holds for any graph at all.
The joins can be written as a table instead of drawn. Number the dots 1 to 27 and make a square table with one row and one column for each. Put a 1 in row i column j when dots i and j are joined, and a 0 when they are not. That table is the adjacency matrix. Here it is 27 by 27 with 52 ones in it, it is symmetric because joining is mutual, and its diagonal is all zeros because no dot is joined to itself.
Walking is the next idea. A walk is a list of dots where each one is joined to the next; you are allowed to go back over your tracks. A path is a walk that never uses the same dot twice. A cycle is a path that ends where it began, using at least three dots.
The graph in the figure has no cycle in it anywhere. Start anywhere, walk without immediately reversing, and you can never come home. A graph that is in one piece and has no cycle is called a tree, and a tree always has exactly one fewer line than it has dots. Twenty seven dots, twenty six lines, and the count checks.
Being in one piece has a name too. Two dots are in the same component when some walk runs from one to the other. This graph has one component, so every filled cell can be reached from every other by stepping side to side. A shape whose cells touched only at corners would fall apart into many components instead, and counting components is one of the cheapest things you can ask a graph.
That is why the tree here turns pictures into graphs at all. A design is a set of filled cells. Joining them face to face turns a picture with no moving parts into an object that can be walked on, measured for distance, cut into pieces and made to ring, and every one of those questions is a question about the dots and the lines.
In the tree
The graphs demo builds this network for any design and prints its tips, its junctions, its pieces and its length, flat or in the cube. The walk dimension note drops random walkers on exactly this graph and times how fast they spread. Structure against noise races a design's graph against a random set of the same size on components and boundary, and the complexity note reads the same graph's eigenvalues. The shape in the figure is grown by the Kronecker product.
The Mobius function
Mu of n is 0 when a square divides n, and otherwise plus or minus one depending on whether n has an even or an odd number of prime factors.
The Mobius function takes only three values and the rule for choosing between them is short. Factor n into primes. If any prime appears twice, mu(n) = 0. Otherwise count the distinct primes: an even count gives +1 and an odd count gives -1.
Work a few. mu(1) = 1, since 1 has no prime factors at all and zero is an even count. mu(2) = -1 and mu(3) = -1, one prime each. mu(6) = 1, two primes. mu(30) = -1, three primes. mu(4) = 0 and mu(12) = 0, because 4 divides both.
Here are the first thirty, the row of values under the row of numbers.
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
mu 1 -1 -1 0 -1 1 -1 0 0 1 -1 0 -1 1 1
n 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
mu 0 -1 0 -1 0 1 1 -1 0 0 1 0 0 -1 -1The zeros are the numbers a square divides, and they are common: 4, 8, 9, 12, 16, 18, 20, 24, 25, 27 and 28 in the first thirty. The numbers that survive are called squarefree, and among those the signs alternate by how many primes they carry.
The figure lays out the first hundred as ten rows of ten. Yellow is +1, blue is -1, grey is 0. There are 31 yellow, 30 blue and 39 grey. So about two fifths of the board is grey, and the signs on the rest are split almost evenly.
The reason for so odd-looking a definition is that mu is a subtraction machine. Add mu(d) over every divisor d of n and the total is 1 when n = 1 and 0 for every other n. For n = 6 the divisors are 1, 2, 3 and 6, the values are 1, -1, -1, 1, and they cancel to 0.
That cancellation is what makes it useful. It is inclusion and exclusion written as a number: if you count something by the multiples of 2, then the multiples of 3, you have double-counted the multiples of 6, and the signs of mu are exactly the bookkeeping that puts each thing back once. Any count that is easy over multiples can be turned into the count you actually wanted by weighting with mu.
Now add the values up as you go, mu(1) + mu(2) and onwards. That running sum wanders. It is -1 after 10 terms, 1 after 100 terms and 2 after 1000 terms, and in between it climbs and falls and crosses zero over and over, never settling and never running away.
How far it is allowed to wander is one of the famous open questions in mathematics. It is known that the sum keeps returning near zero rather than drifting, and it is known that the sum grows slower than n itself, but the exact size of its swings has never been pinned down.
In the tree
The running sum of mu over a restricted set of numbers is the object the Mobius meter note measures, where the question is how big the swings get when you only allow numbers whose digits come from a fixed list. The design zeta note reads the same meter from the other side, and the Mobius echo demo listens to it: the swings turn out to carry frequencies borrowed from the zeta zeros. Weighting by mu instead of by 1 also changes what the Farey stack draws, and it is mu that inverts the divisor count in pi out of the stack.
Moire
Lay two rulings over each other and they beat; the points both of them mark are the ones their scales agree on, and stacking many scales lights the points most scales share.
Rule the unit square into 5 equal columns and 5 equal rows. Now rule the same square into 7 columns and 7 rows, in another colour, and lay one over the other. That is the figure, and the pattern it makes is a moire.
Neither ruling is interesting on its own. Together they are, because their lines fall out of step. The blue line at 1/5 = 0.2 and its nearest orange neighbour at 1/7 = 0.1429 sit two thirty fifths apart; the blue line at 2/5 = 0.4 and the orange one at 3/7 = 0.4286 are only one thirty fifth apart. The gaps swell and shrink across the square, and that swelling is the beat.
The grey dots in the figure mark every place where a line of one ruling crosses a line of the other. There are 92 of them, and their spacing is visibly uneven: tight where the two rulings are in step, loose where they are not. Nothing is moving and nothing is curved, and still the eye sees bands.
The yellow discs are the four points where the two rulings actually agree, one at each corner. Those are the only places where a line of the 5-ruling and a line of the 7-ruling land on exactly the same coordinate.
Why only the corners? Scale n puts a line at every k/n. A point at the fraction a/b, written in lowest terms, gets a line from scale n exactly when b divides n. So a point marked by both scale 5 and scale 7 has a bottom number dividing both, which means it divides their greatest common divisor, and 5 and 7 share only 1. A bottom number of 1 leaves only 0 and 1 themselves.
Change the pair and the picture changes completely. Scales 4 and 6 share a divisor of 2, so they agree at 0, at 1/2 and at 1, and the beat is short and coarse. Scales 5 and 10 agree at every line the coarser one draws, and there is no beat at all, just one ruling sitting inside the other. Coprime scales are the ones that agree least and therefore beat longest.
Now stack instead of pairing. Draw the ruling for every scale n from 1 up to some limit, all faintly, one on top of another, and count how many lines land on each point. A point a/b collects one line from every multiple of b in the range, so its brightness is the count of those multiples. Small bottom numbers are bright, large ones are faint, and the brightness falls off like one over b.
That stack lights exactly the fractions in lowest terms, ordered by how simple they are: 1/2 brightest after the ends, then 1/3 and 2/3, then the quarters, and so on. It is the Farey sequence drawn as light. The picture is not a decoration of the fractions; it is the fractions.
One more reading follows for free. The new points a scale n contributes, the ones no smaller scale had already lit, are the fractions a/n with a sharing no factor with n. A prime scale shares a factor with nothing below it, so it contributes the most new points of any scale near it, and primality is visible in a stack of rulings as a sudden burst of new lines.
In the tree
The moire demo stacks one design's grid at scale 1, 3, 5 and on, and the interference is the fine grids landing on the coarse. The Farey note reads that moire as a diagram of the fractions and asks how evenly its lit points spread, while the algebra of the stack asks what happens when the layers are weighted, restricted or spun. The tourbillon demo turns every layer by its own angle so the shared grid breaks and only the centre survives, and the hexagon note runs the same interference on stacked diagonal slices.
Pascal's triangle
A triangle of numbers where every entry is the sum of the two directly above it, and colouring the odd ones draws a fractal.
Write a single 1. Under it write 1 1. Under that, write a 1 at each end and fill the middle by adding the two numbers above it, which gives 1 2 1. Carry on for ever: every entry is the sum of its two neighbours in the row above, and the ends are always 1. The first six rows read 1, then 1 1, then 1 2 1, then 1 3 3 1, then 1 4 6 4 1, then 1 5 10 10 5 1.
The entries count choices. The entry in row n at place k, counting both from zero, is the number of ways to pick k things out of n when the order of the picking does not matter. Row 4 is 1 4 6 4 1, so there is 1 way to pick nothing from four things, 4 ways to pick one, 6 ways to pick two, 4 ways to pick three and 1 way to pick all four. These numbers are called the binomial coefficients, because they are also the numbers that appear when you multiply out (x + y)^n.
The addition rule is that counting argument in disguise. To choose k things from n, either you take the last item, and then you need k - 1 more from the n - 1 that remain, or you leave it, and you need all k from those n - 1. Two cases, no overlap, so the entry is the sum of the two above it.
Each row adds up to a power of two. Row 4 adds to 16, row 5 to 32. Every subset of n things has some size, so counting the subsets by size and adding gives the total number of subsets, which is 2^n.
The figure has 64 rows, row 0 at the top and row 63 at the bottom. Every odd entry is a solid blue disc and every even entry is a faint dot. The odd entries do not scatter. They draw a triangle with a triangular hole in the middle, each of the three solid corners holding a smaller copy of the same shape, down to the single discs. That is the Sierpinski triangle, and nothing in the drawing was designed: it is the parities of the numbers and nothing else.
Counting the lit discs is easy once you look at the row numbers in binary. Row n holds exactly 2^d odd entries, where d is the count of 1s in the binary form of n. Row 7 is 111 in binary, three ones, so all 8 of its entries are odd, and indeed row 7 reads 1 7 21 35 35 21 7 1. Row 8 is 1000, one 1, so only 2 of its 9 entries are odd. Add that over rows 0 to 63, whose row numbers use six binary digits, and the figure holds 729 lit discs, which is 3 multiplied by itself six times.
Kummer's rule says which entry is odd, and it is a rule about carrying. The entry in row n at place k is odd exactly when adding k and n - k in binary needs no carry at any digit. Take row 4 and place 2: that is 2 + 2, which in binary is 10 + 10, and the two 1s collide, so there is a carry and the entry 6 is even. Take row 5 and place 2: that is 2 + 3, in binary 10 + 11, and again the 1s collide, so 10 is even. Take row 5 and place 1: 1 + 4 is 001 + 100, no digit is used twice, no carry, and the entry 5 is odd.
The same rule said another way: the entry is odd exactly when every 1 in the binary form of k sits where n also has a 1. So the odd places of row n are the subsets of the 1s of n, and there are 2^d of them, which is the count above.
That rule is why the picture repeats itself. Look at the top 32 rows and the bottom 32 rows. Adding 32 to a row number turns on one more binary digit, so the bottom half carries two separate copies of the top half, one on the left and one on the right, and the middle stays dark because a place in the middle would need a binary digit the row number does not have. Double the depth again and the same thing happens again. Three copies in place of one, at half the size, for ever.
In the tree
The odd entries are a parity rule on a grid, and choosing cells by parity is move one of the tree, set out in the core. The shape they draw is one of the tree's own designs, the gasket, grown by the Kronecker product, and the universe demo has it in the gallery beside every other rule of the plane. The sponge demo grows a rule of this kind level by level, and the Sierpinski carpet is the same construction on a three by three block instead of a two by two one. The bit being read is the one parity sets out.
The prime counting function
How many primes are there below a number? The answer is a staircase with one riser per prime, and two smooth curves that chase it without ever quite catching it.
Write pi(n) for the count of primes at or below n. It is the plainest question you can ask about the primes and it has no formula. Up to ten there are four primes, 2, 3, 5 and 7, so pi(10) is 4. Up to a hundred there are 25. Up to two hundred there are 46. Up to a thousand there are 168.
The figure draws that count from 2 up to 200. The yellow line is a staircase: it is flat wherever a number is composite and it jumps by exactly one at a prime. Each faint vertical hairline stands on a prime, so the hairlines are the risers. There are 46 of them, and you can watch them crowd the left of the picture and thin out to the right.
Thinning is the whole shape. The first hundred numbers hold 25 primes, the second hundred hold 21, and by a thousand only 168 numbers out of the thousand are prime, about one in six. The primes never stop, but they get rarer, and they get rarer in a way that is smooth enough to guess at.
The first guess is n divided by ln n, the blue curve in the figure. The natural logarithm ln n is the number of times you have to multiply by 2.71828 to reach n, and the guess says that a number near n has roughly a one in ln n chance of being prime. At 200 the guess reads 37.7 against the true 46. At 1000 it reads 144.8 against 168. It is always low, and it is low by a widening amount, yet the ratio of the true count to the guess creeps towards 1.
The second guess is better and is built the same way. If the chance of being prime near x is one in ln x, then add that chance up over every x from the start to n, as a curve adds things up. The result is the logarithmic integral, written li(n), and it is the area under the curve 1 over ln x. At 200 it reads 50.2 against 46. At 1000 it reads 177.6 against 168.
Compare the two guesses honestly. At 1000, n over ln n is short by 23 and li is over by 10, so the better curve is about twice as close, and the gap it leaves shrinks faster. The primes demo plots both against the staircase, and the picture there is the same picture: two curves, one below and one above, closing in slow motion.
That both ratios march to 1 is the prime number theorem, the central fact about how the primes thin out. It says the guesses are eventually right in proportion. It says nothing at all about the gap: the difference between the staircase and either curve can be, and is, large and jumpy forever.
One thing looks true in the figure and is not. Here and in every table anyone has printed, li(n) sits above the count. It is known that this cannot last, that the count overtakes the curve somewhere and then keeps swapping sides forever, and no one has produced a single number where it happens. It is the standard warning about reading a law off a table.
The staircase is also the slowest of the eight systems on the formulas page to pay. Five of them close on a constant at a steady, readable rate. The prime count against li closes too, but its gap is ragged at every scale, which is the visible face of the fact that nobody can say how ragged it is allowed to get.
In the tree
The primes demo runs the sieve, splits numbers into rectangles, and draws this staircase against both guesses. The Ulam spiral demo winds the whole numbers outward with the primes lit, so the same thinning reads as a texture. The pi note counts pi out of the lattice rather than the primes, and this count is one of the eight on the famous formulas hub. What is being counted is prime numbers.
The Riemann zeta function
Add one over every whole number raised to the power s; the answer is zeta of s, it equals pi squared over six at s equal to 2, and it can be rewritten as a product over the primes.
Pick a number s and add up 1 plus 1/2^s plus 1/3^s and on forever, one term for every whole number. The total is the zeta function, zeta(s).
The sum only settles if s is bigger than 1. At s = 1 the terms are 1, 1/2, 1/3, 1/4 and their total grows without bound, slowly but forever. Push s a little above 1 and the terms shrink fast enough that the total stops somewhere.
The figure shows three of those totals being built. Each curve is the running sum for one value of s, drawn term by term for the first forty terms, and each closes on its own hairline. The top curve is s = 2, still visibly short of its line after forty terms because its terms only shrink like 1/n^2. The middle is s = 3 and the bottom is s = 4, and both are flat long before the right edge.
The top line is the famous one. zeta(2) = 1 + 1/4 + 1/9 + 1/16 + ... comes out to pi squared over six, which is 1.6449 and on. Euler found that, and it is still surprising: a sum of reciprocal squares, nothing round anywhere in it, and the answer carries pi. The same happens at s = 4, where the answer is pi to the fourth over 90.
The odd powers do not behave. zeta(3) is 1.2020569 and a bit, and nobody has ever written it in terms of pi or anything else familiar. It is known not to be a fraction, and that is about as much as is known.
Now the part that ties zeta to the primes. Take one prime p and form the sum 1 + 1/p^s + 1/p^(2s) + ..., which is a geometric series and adds to 1/(1 - p^(-s)). Do that for every prime and multiply all of those sums together.
Multiplying out that product means choosing one term from each bracket, which means choosing a power of each prime, which means building a whole number. Every whole number gets built, and because a number factors into primes in exactly one way, every whole number gets built exactly once. So the product over the primes and the sum over the numbers are the same thing. Unique factorisation, written as an equation.
That is the bridge, and it runs both ways. Anything you learn about the sum, which knows only about counting, becomes a statement about the primes. The first prize won this way was the fact that zeta blows up at s = 1, which forces the primes to be infinite in number and, pushed harder, says roughly how densely they sit.
To push harder you have to let s be a complex number, a point in the plane rather than on a line, and then extend the function past s = 1 where the sum itself no longer works. That extension is unique, and it has zeros: points where zeta(s) is exactly 0.
Some of the zeros are dull and sit at the negative even numbers. The rest all lie in a vertical strip, and every one that has ever been found sits on a single line down the middle of that strip, the line where the real part of s is one half. That line is called the critical line. Whether every one of those zeros lies on it is the Riemann hypothesis, and it is unproved.
In the tree
The zeta walk in the critical line demo traces zeta along that line and shows the curve passing through the origin once for each zero. The design zeta note builds the same kind of sum over a design's own numbers instead of all of them, and asks where that function vanishes when the Euler product is no longer available. The Mobius echo demo hears the zeta zeros as frequencies in a counting function that never mentions them, and the Mobius meter note is where that measurement is kept honest. The value zeta(2) is what turns a count of coprime points into pi in pi out of the stack, and the Farey stack note states the old equivalence between how evenly fractions spread and where those zeros lie. The sum at s = 2 is the Basel problem.
The Sierpinski carpet
Cut a square into nine, throw the middle one away, then do the same to the eight that are left, and keep going for ever.
Start with a solid square. Divide it into a three by three grid of nine equal squares and remove the middle one. Eight squares are left, arranged in a ring around a square hole.
Now do the same to each of the eight. Each is cut into nine and loses its middle, so eight rings of eight sit where eight solid squares were. The picture is nine cells wide and holds 64 filled cells, with one hole of three by three in the middle and eight holes of one cell each around it.
Repeat. At level n the picture is 3^n cells wide and 8^n of them are filled. Level 1 is 8 of 9, level 2 is 64 of 81, level 3 is 512 of 729 and level 4, which the figure draws, is 4096 filled cells on a side of 81.
The step is one move, not a list of instructions. Take the eight-around-a-hole picture and stamp a copy of it into each of its own filled cells: that is the Kronecker product of the picture with itself, and doing it n times is the carpet at level n. The counts follow with no extra work, because eight filled cells each carrying eight filled cells is 64.
The area falls away. Each round keeps eight ninths of what it started with, so after n rounds the shape covers (8/9)^n of the original square. That number shrinks towards zero, and it never stops shrinking, so the carpet itself has no area at all. The figure looks solid only because it stops at level 4.
The holes are countable too. Level 1 opens one hole, level 2 opens eight more, level 3 opens sixty-four more, and level n has (8^n - 1)/7 holes in all: 1, then 9, then 73, then 585. Each round's holes are a third of the width of the round before.
Nothing ever gets cut off. At every level the filled cells form a single connected piece, because the eight cells of the rule touch each other edge to edge all the way round the ring, and stamping a connected picture into a connected picture leaves it connected. The carpet has no area and is still all one thing.
There is a short way to say which points survive. Write the two coordinates of a point in base 3. A point is thrown away at some round exactly when a 1 appears in the same place of both expansions, so the carpet is the set of points whose two base-3 expansions never carry a 1 in the same position. That is a rule on one digit of each coordinate, which is the tree's way of naming it: keep eight of the nine cells and drop the middle, code 495 read at base 3.
A shape that has no area but is not a curve does not fit the usual count of dimensions, and the honest answer is not a whole number. Counting boxes gives log 8 / log 3, about 1.89, which is the fractal dimension.
In the tree
The carpet is one code among the sixteen plane designs of the core, where it fills 8 of 9 cells at side 3 and 8^level at every level after. Structure against noise races it against a random set of exactly the same cell count and finds the carpet in one piece where the random set is in hundreds. The tour demo grows it level by level and reads its perimeter off as an integer sequence. Its cube is the Menger sponge.
The spirograph
A small wheel rolls inside a big ring carrying a pen, and the fraction made by the two radii decides how many petals the pen draws and when it comes home.
Take a ring of radius R with teeth on the inside, and a wheel of radius r with teeth on the outside. Drop the wheel in, press a pen through a hole in it, and push the wheel round the inside of the ring without letting it slip. The pen draws a curve. The only three numbers that matter are the ring, the wheel, and how far the pen sits from the wheel's centre, which we will call the reach and measure in wheel radii, so a reach of 1 puts the pen on the rim and a reach of 0 puts it dead centre.
A pen at the centre just draws a circle, of radius R - r, because the wheel's centre goes round and round at that distance. Everything interesting comes from the pen being off centre: while the centre travels its circle, the wheel is also spinning, and the pen feels both motions at once.
The spinning is fixed by the rolling. No slipping means the arc the wheel covers on the ring equals the arc that passes under it on its own rim, so the wheel turns through R/r full turns for every one trip the centre makes round the ring. With a big ring and a small wheel that is a lot of spin per lap, which is why the curve wanders in and out so many times.
The figure is the case R = 7 and r = 3 with the pen at reach 0.8, drawn from 4000 samples as one unbroken line, with the ring itself as a faint circle around it. The curve has seven arms. It runs out near the ring, turns, comes back in, and repeats, and after three trips round the ring it arrives exactly where it started and closes.
Those two counts are the fraction R/r in lowest terms. Write it as a/b with no common factor: the curve closes after b trips round the ring, and it has a-fold symmetry, so it shows a arms. Here 7/3 is already in lowest terms, so three laps and seven arms. If the ring and wheel share a factor, cancel it first: R = 6 and r = 3 is 2/1, so one lap and two arms, which is just a flattened oval.
This is why a spirograph set gives such different curves from wheels of similar size. A wheel of 30 teeth in a ring of 96 is 16/5 after cancelling, so five laps and sixteen arms. A wheel of 32 teeth in the same ring is 3/1, so one lap and three arms, done almost before it starts. Two teeth of difference, an entirely different picture, and the reason is nothing but the common factor.
The reach changes the shape of the arms without changing either count. At reach 1 the pen is on the rim, and at the moment a point of the rim touches the ring it is instantaneously still, so the curve comes to a sharp point there: the arms end in cusps. Below 1 the pen never reaches the ring and the arms end in smooth blunt tips, as in the figure. Above 1 the pen sticks out past the rim on an arm of its own, it overshoots at each turn, and the arms end in little loops that cross themselves.
Rolling the wheel around the outside of the ring instead gives the other family. The centre then travels a circle of radius R + r, the wheel spins the other way relative to the ring, and the arms point outwards like the petals of a flower rather than inwards like a star. The counting rule is the same one: cancel the fraction, and the numerator counts the arms while the denominator counts the laps.
In the tree
The spirograph note makes a design the wheel: it seats a pen at the centre of every cell at once, so one design draws a whole family of these curves in one roll, and it counts how many of those curves are genuinely different rather than the same curve drawn twice. The spirograph demo rolls any design on a circle, on a straight line or around a polygon and prints those counts as it draws. Reducing R/r to lowest terms is the greatest common divisor at work, and the fractions that give the longest curves before closing are the ones the Farey sequence orders.
The Thue-Morse sequence
A string of noughts and ones built by writing a block and then its opposite for ever, which is also the parity of the ones in each place number written in binary.
Start with a single 0. Write it down, then write the opposite of everything you have so far, which is 1, giving 01. Do it again: the opposite of 01 is 10, so you now have 0110. Again: the opposite of 0110 is 1001, so you have 01101001. Each round doubles the length and never changes a letter already written, so the string settles down to one infinite sequence: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 and on.
There is a second way to get the same letters, one place at a time, with no history at all. Take the place number, write it in binary, count the 1s, and the letter is 0 when that count is even and 1 when it is odd. Place 0 is 0 in binary, no ones, even, so the letter is 0. Place 3 is 11, two ones, even, so the letter is 0. Place 4 is 100, one 1, odd, so the letter is 1. Check those against the string above and they agree.
The two recipes agree because doubling a place number in binary just adds a 0 on the end, which does not change the count of 1s, while doubling and adding one puts a 1 on the end, which flips the parity. So the letter at place 2n is the letter at place n, and the letter at place 2n + 1 is its opposite. That is exactly the copy-and-flip rule, read forwards.
The strip along the top of the figure is the first 64 letters, one cell each, orange for 0 and blue for 1. Count them and there are 32 of each, which holds for the first 2^k letters at every k, because the rounds pair every letter with its opposite.
The sequence never says the same thing three times in a row. Whatever block you choose, that block repeated three times immediately does not occur anywhere in the string, and neither does any block followed by itself and then its own first letter. This is the reason the sequence was first written down: it settles the question of whether an endless string over two letters can avoid such repetition, and it does so with an explicit answer rather than a proof that one must exist.
It is also the fair way to take turns. Two players alternating by 0 1 0 1 gives the first player every early advantage. Sharing by 0 1 1 0 1 0 0 1 instead gives the second player the second pick, then the first player two in a row, and so on, so the running totals stay level far longer. That is why the pattern turns up in draw rules and in schedules.
The bottom panel of the figure is the sequence lifted to the plane. The cell in row i and column j is orange when the letters at places i and j agree and blue when they differ. That is one sequence read twice, once down and once across, and combined by the same exclusive-or that parity uses. The panel is 32 cells on a side, so it holds 1024 cells, half of each colour.
The plane picture is not a plain check pattern, and it is not random either. Blocks of 2 by 2, 4 by 4 and 8 by 8 repeat at every scale, some plain and some flipped, because the row and column rules both halve in the same way. Stand back and the same texture appears at each size, which is what self-similar means in practice.
In the tree
The Thue-Morse demo builds the word twice, once by the doubling rule and once by the digit rule, and lifts it to the plane as the figure does, with its run lengths beside it. A design that changes with the scale is the subject of magic words, where this word names the order the letters are taken in, and the words demo builds such a word letter by letter. The single bit being read is the one parity sets out, and the Mobius function is another string of signs read off a count, there of prime factors rather than binary digits.
The Ulam spiral
Wind the whole numbers outwards on a square spiral, light up the primes, and they fall on diagonal streaks instead of scattering evenly.
Put 1 on a square grid. Put 2 to its right, 3 above that, then 4 and 5 to the left, then 6 and 7 below, then 8, 9 and 10 to the right again, and carry on turning left whenever the cell ahead of you is already taken. The numbers wind outwards in a square spiral that fills the whole grid, one number to a cell, with no gaps and no choices to make.
Now light up every cell whose number is prime and leave the rest dark. That is all the construction there is. It was done on a scrap of paper by a bored mathematician during a talk, and the surprise is that the lit cells are not evenly scattered.
The figure is the spiral out to 101 cells on a side, so it holds every number from 1 to 10201, with the 1252 primes among them lit in blue. The eye finds diagonal streaks at once, some long and dense, others thin, with dark stretches between them. Nothing has been chosen or fitted. The only inputs are the winding and the primes.
The streaks are real, and they have an ordinary explanation. Walk along any straight diagonal of the spiral and write down the numbers you pass. They do not go up by a fixed step. They go up by a step that itself grows by a fixed amount each time, and a sequence like that is exactly what you get from a quadratic, a formula of the shape 4 k^2 + b k + c. Every straight line in the picture is one such formula, and the picture is a hundred of them side by side.
Some quadratics produce far more primes than others, and the reason is small divisors. A formula whose values are always even can only ever hit the prime 2, so its line is dark. A formula whose values avoid being multiples of 2, 3 and 5 has fewer ways to be composite than a random number of the same size, so it hits primes more often than its neighbours do, and its line is bright. The bright diagonals are the formulas that dodge the small primes, and the dark ones are the formulas that cannot.
The most famous of these is Euler's k^2 + k + 41, which is prime for every k from 0 to 39, forty values in a row with no exception. It fails at k = 40, where the value is 41 times 41, and it must fail somewhere for the simple reason that at k = 41 every term has a factor of 41. Still, over a long range it carries a startling share of primes, and on a spiral centred at the right number it draws one unbroken bright line.
Alternate diagonals of the spiral are even numbers, so half of the diagonal directions are dark by construction, and that alone makes the remaining ones stand out. But the effect is stronger than that: among the odd diagonals some are plainly richer than others, and that difference is the one the small divisors explain.
None of this says the primes are orderly. Change the centre, change the shape, wind the numbers on a hexagonal grid instead of a square one, and different lines light up, because the quadratic behind each line has changed. What the picture shows is one honest fact seen very clearly: primes are not uniform across the quadratics, and some polynomials are far better prime factories than others. Why the best ones are as good as they are is still open.
In the tree
The Ulam spiral demo winds the numbers on squares or on hexagons with the primes lit, and lets you pick out a single line and read the quadratic behind it. The primes demo reads the same numbers the other way, as a sieve and as a count, and the snail demo gives every cell of the winding a design tile whose side is a power of the base, so the spiral widens by that factor at each new digit. The lit cells are the subject of prime numbers, and how many of them there are up to a given point is the prime counting function.
The Wallis sieve
Cut a square into nine and drop the middle, cut each survivor into twenty-five and drop the middle, and keep going; the area left is a quarter of pi.
The figure is the sieve after three rounds, drawn on a square of 105 cells a side. One big hole sits in the middle, eight middling holes sit around it, and 192 small holes are scattered through what is left. That is 201 holes in three sizes, one size per round, and everything not painted is the body that survives.
The rule is one line. Round k cuts every surviving square into (2k + 1)^2 equal squares and drops the centre one. Round one cuts into nine and drops one, leaving eight. Round two cuts each of those eight into twenty-five and drops each centre. Round three cuts into forty-nine and drops each centre again.
The sides multiply: 3, then 3 times 5 is 15, then 3 times 5 times 7 is 105. The surviving cells multiply too: 8, then 8 times 24 is 192, then 192 times 48 is 9216. The holes are one per surviving square of the round before, so there is 1 hole, then 8, then 192, and the biggest is 35 cells wide, the next 7 and the smallest 1.
What matters is the area. Round k keeps (2k + 1)^2 - 1 squares out of (2k + 1)^2, which is a share of 1 - 1/(2k + 1)^2. Three rounds keep 8/9 times 24/25 times 48/49, which is 0.8359 of the original square. Carry on forever and the area is the product of 1 - 1/(2k + 1)^2 over every k, and that product is pi/4, or 0.785398.
Compare that with the Sierpinski carpet, which uses the same cut every round: nine squares, drop the centre, again and again. Its area is 8/9 of 8/9 of 8/9 without end, and that runs to nothing. The sieve escapes because its cuts get gentler fast: it drops a ninth, then a twenty-fifth, then a forty-ninth, and the shares stop falling before they reach zero. The sieve buys area by growing its letters.
Letter is the right word. Round k has a tile of its own, a square of side 2k + 1 with its centre cell removed, and the sieve is those tiles multiplied together by the Kronecker product: stamp the side-5 tile into every filled cell of the side-3 tile, then stamp the side-7 tile into every filled cell of that. Sides multiply and filled cells multiply, which is where 105 and 9216 came from.
Drag the level in the panel above. At level 1 you see the single hole in a 3 by 3 square and an area of 0.888889. At level 2 the side is 15 and the area has fallen to 0.853333. At level 3 the side is 105, the cells are 9216 of 11025, and the area is 0.835918, on its way down to pi/4 and not to zero.
The order and the choice of letters are the whole story. Use the same letter twice and the area starts dying again; use letters that grow, and the losses add up to something finite. That is why the product over the odd numbers, which the Wallis product splits off from a telescoping product, is exactly the area on the screen.
In the tree
The pi note uses this sieve as its counterexample: a fixed design keeps the same share every level, so its area is rational at every level and its limit is 0 or 1, while the sieve changes its share every level and so can land on pi/4. Reading a design as a word of letters, one per scale, is the move the words demo draws, and the Wallis product is the arithmetic behind the area.
The Eisenstein integers
Numbers built from a cube root of one, drawn as a hexagonal lattice, with six units and a size rule that turns the honeycomb into a number system.
There are three numbers whose cube is 1. One of them is 1 itself. Call either of the other two omega. It satisfies omega^2 + omega + 1 = 0, which is the only fact about it we will use, and drawn in the plane it sits a third of the way round the unit circle from 1.
An Eisenstein integer is anything of the form a + b omega with a and b ordinary whole numbers. Add two of them and the coordinates add. Multiply two of them and the rule omega^2 = -1 - omega folds the answer back into the same form. So these numbers are closed under both operations, exactly as the whole numbers are, and you can do arithmetic in them.
Plot them and you do not get a square grid. Because omega sits at a third of a turn, the point a + b omega lands on a triangular mesh: every point has six nearest neighbours at equal distance, and the cells between them are equilateral triangles. This is the honeycomb lattice, and the figure draws it out to eight steps from the middle, which is 217 points, with the short bonds between neighbours drawn faintly so the six-fold pattern shows.
Every point has a size, its norm, which is the square of its distance from the origin: the norm of a + b omega is a^2 - a b + b^2. The minus sign is there because the two directions are at 120 degrees rather than at a right angle. The norm is always a whole number, never negative, and the one property that matters is that it multiplies: the norm of a product is the product of the norms.
Six points have norm 1, and the figure marks them in yellow around the orange origin. They are 1, omega, omega^2 and the negatives of those three, and they are the six corners of a small hexagon. These are the units, the local version of plus and minus one, and multiplying any point by one of them turns the whole picture by a sixth of a turn. That is where the six-fold symmetry of everything in this world comes from. The square lattice has four units and quarter turns; this one has six units and sixth turns.
A point is prime here when it cannot be written as a product of two points of norm bigger than 1. The norm makes that testable: to split a point you would need two norms multiplying to its norm, so any point whose norm is an ordinary prime cannot split at all.
Ordinary primes behave in three ways when they move into this larger world, and which way is decided by the remainder on division by 3. A prime that leaves remainder 1 breaks in two: 7 = (3 + omega)(3 + omega^2), and each factor has norm 7. A prime that leaves remainder 2 stays whole: 2 and 5 cannot be split here at all. The prime 3 itself is the odd one out, because 1 - omega has norm 3, so 3 is a unit times that point squared, a prime that becomes a square.
Division with remainder works in this lattice, for the plain geometric reason that every point of the plane is within less than one unit of some lattice point. From division with remainder you get a greatest common divisor by the usual repeated-remainder method, and from that you get unique factorisation into primes. So the honeycomb is not just a pretty arrangement of dots. It is a number system with the same backbone as the ordinary whole numbers, and it is the natural home for questions where three-fold symmetry is built in rather than four-fold.
In the tree
What base 3 hides is the note that needs this ring: base 3 brings three-fold symmetry, a flat lattice with three-fold symmetry has to be the hexagonal one, and the arithmetic of that lattice is this. The primes in the plane demo draws both rings side by side with each point coloured by how it splits. The Gaussian integers is the square case this one mirrors, and the counting of neighbours by distance is the same sort of question as in visible lattice points.
The Euler characteristic
Count the corners, subtract the edges, add the faces; the answer is 2 for anything shaped like a ball, and bending the shape never changes it.
Take a cube and count three things. It has 8 corners, 12 edges and 6 faces. Now compute corners minus edges plus faces: 8 - 12 + 6 = 2. The left panel of the figure is that cube, its 8 corners marked, its 12 edges drawn, three of its six faces facing you and three behind.
Try another solid. A tetrahedron has 4 corners, 6 edges and 4 faces, and 4 - 6 + 4 = 2. An octahedron has 6 corners, 12 edges and 8 faces, and 6 - 12 + 8 = 2. A football, a pyramid, a brick with a bite out of it: every one of them gives 2.
The reason is that the count does not care about shape at all. Imagine the solid made of rubber and inflated until it is a sphere. The corners, edges and faces are now drawn on the sphere, and pushing them around, or cutting a face in two, or joining two edges, changes the three counts only in ways that cancel. Cut a face in half and you add one edge and one face, which cancel. So the answer depends on the sphere and not on the drawing, and for a sphere the answer is 2.
That number is the Euler characteristic. It is what is left of a shape when you forget every length and every angle: a single integer that survives any amount of stretching.
Change the shape and the number changes. A doughnut has a hole running through it, and no amount of inflating will turn it into a ball. Draw corners, edges and faces on a doughnut and the count comes out 0 every time, not 2. Two holes give -2, three give -4. Each hole costs 2, so the number is really a count of holes with a sign on it.
Pictures made of cells are the same idea with a shorter recipe. For a flat shape built out of little squares, the Euler characteristic is the number of separate pieces minus the number of holes. A solid blob is one piece with no holes, so it is 1. A square ring is one piece around one hole, so it is 0. A blob with two holes in it is -1.
The recipe is the same count as before if you insist on the long form: corners of the little squares, minus their edges, plus the squares themselves. The ring that is the Sierpinski carpet's first level has 16 corners, 24 edges and 8 cells, and 16 - 24 + 8 = 0, which is what one piece around one hole should give.
The carpet at level 2 is the right panel of the figure. It is still one connected piece, and it has 9 holes: the big three by three hole in the middle and eight single-cell holes around it, each ringed in the figure. So its Euler characteristic is 1 - 9 = -8. Level 3 has 73 holes and gives 1 - 73 = -72, and level n has (8^n - 1)/7 holes, so the number falls away as fast as the holes arrive.
That is what the count is for. Pieces and holes are the two things you can see in a picture without measuring anything, and the Euler characteristic bundles them into one integer that no stretching can move. It is the crudest description of a shape that is still worth having, and because it is crude it is cheap to compute and hard to fool.
In the tree
Structure against noise counts pieces, holes and the Euler characteristic of the designs, and those three are the readings that notice the order in which tiles are stamped together, where fill, side and density cannot tell one order from another. The shape the count is taken on here is the Sierpinski carpet.
Goldbach's conjecture
Every even number past two is a sum of two primes. Machines have checked it further than anyone can list and nobody has proved it.
Take an even number and try to write it as one prime plus another. Four is 2 plus 2. Six is 3 plus 3. Eight is 3 plus 5. Ten is 3 plus 7, and also 5 plus 5. Twelve is 5 plus 7. The conjecture is that this never fails: every even number from four upward is a sum of two primes.
Count the ways and you get a function. Write g(2n) for the number of ways to write the even number 2n as a sum of two primes, counting a pair once and not twice, so 3 plus 7 and 7 plus 3 are the same way. Then g(4) is 1, g(10) is 2, g(100) is 6 and g(400) is 14. The conjecture, in this shape, is the single sentence that g(2n) is never zero.
The figure is that count drawn as 199 bars, one per even number from 4 to 400. The bars start at height one, climb, and spread out into a widening spray. This picture is called the Goldbach comet, because at larger ranges the spray takes on a head and a tail. What matters here is that no bar has height zero.
The comet has stripes, and the figure paints them. A bar is yellow when its even number is a multiple of six and blue otherwise, and the yellow bars ride roughly twice as high. The tallest bar in the figure stands on 390, a multiple of six, with 27 different pairs.
The reason is the number three. Suppose the even number is a multiple of six. Every prime except three leaves a remainder of one or two when divided by three, and so does the partner it needs, so three never spoils a candidate pair. Now suppose the even number is not a multiple of three. Then about half the candidate primes leave a partner that three divides, and a number three divides is not prime. Half the candidates die, so the bar is about half as tall.
The counts grow because there are more primes to work with, but they grow with a lot of noise, and the noise is the same noise that makes the prime count jumpy. The smallest count in the figure is one, and it is reached at the small even numbers, four and six and eight and twelve. Past that the floor lifts away from zero and never comes back to it, in this range.
Here is the thing that a table cannot do. A table shows that the count is positive at every even number in it. The conjecture says the count is positive at every even number there is. No finite table can reach that, because a pattern can hold for a long stretch and then break: Euler's rule 4k^2 - 2k + 41 hands you a prime for its first twenty one values and then stops, and the Ulam spiral page draws exactly that line breaking. A checked range is evidence about the checked range and nothing more.
The machine check has been pushed past a billion billion even numbers, which is far enough to make almost anyone believe it and not far enough to be a proof. Statements like this one do get proved, but only when someone finds a reason rather than a table, and no reason has been found.
What has been proved is nearby and weaker. Every odd number past five is a sum of three primes. Every large even number is a prime plus a number with at most two prime factors. Both results come from sieve methods that can push a count above zero on average without ever pinning one particular even number down, which is exactly the gap that remains.
In the tree
The famous formulas hub sets this count beside seven other systems; the figure above stops at 400 and claims nothing past it. The primes demo sieves the primes the pairs are drawn from, and the Ulam spiral demo shows Euler's quadratic running out of primes at its twenty second value. The raw material is prime numbers and the staircase that counts them is the prime counting function.
The graph Laplacian
Degree minus adjacency, one table per network; its eigenvalues are the tones the network can ring at, and the staircase they make says how it is knit together.
Take a graph and build two tables. The first is the adjacency table: a 1 where two dots are joined and a 0 where they are not. The second is the degree table: the count of lines at each dot down the diagonal and zeros everywhere else. Subtract the first from the second and you have the graph Laplacian.
Written out, the rule is short. The diagonal entry for a dot is its degree. The entry for a pair of joined dots is -1. Everything else is 0. Every row therefore adds up to zero, because the degree on the diagonal is exactly the number of minus ones in that row.
What the table does is compare a dot with its neighbours. Give every dot a number, apply the Laplacian, and the answer at each dot is its own value times its degree minus the sum of its neighbours' values. It is zero when a dot agrees with the average of its neighbours and large when it disagrees, so the Laplacian measures roughness.
Now ask for the eigenvalues: the numbers lambda for which some assignment of values to the dots comes back multiplied by lambda and otherwise unchanged. A graph with v dots has v of them, counted with repeats, and none of them is negative. The smallest is always 0, belonging to the assignment that gives every dot the same value, because that one is perfectly smooth and the Laplacian flattens it to nothing.
Those eigenvalues are the tones. A drum skin has shapes it can vibrate in, each with its own frequency; a network has the same, with the Laplacian in place of the drum's smoothness, and the eigenvalue playing the part of the frequency squared. Small eigenvalues are slow, smooth, long-wavelength modes and large eigenvalues are jagged ones where neighbours disagree everywhere.
The figure sorts the eigenvalues from small to large and draws them as a staircase, one tread per eigenvalue, for two networks of 32 dots each. The blue staircase is a path: 32 dots in a row, each joined to the next, two loose ends. The orange staircase is a cycle: the same 32 dots with the two ends joined up.
Both have closed forms, and they are almost the same formula. The path's eigenvalues are 2 - 2 cos(pi k / 32) for k from 0 to 31, and the cycle's are 2 - 2 cos(2 pi k / 32) for the same k. Both climb from 0 towards 4, which is why the two staircases shadow each other so closely.
The difference is in the repeats. On the cycle, k and 32 - k give the same number, so all but two of its tones come in matched pairs, 17 distinct values across 32 eigenvalues. On the path every value is different, all 32 of them. Joining the two loose ends changes almost nothing about the pitch of the network and everything about how many ways it can ring at that pitch, and that is the cycle's symmetry made audible.
The shape of the staircase is the real reading. A gentle start with the tones packed close together means many slow modes, which means the network is loosely knit and slow to mix. A staircase that jumps away from zero at once means there is no slow mode at all, and a network that mixes fast. How many eigenvalues are 0 is a count of pieces: one zero for each component, so a network in one piece has exactly one.
Take a fractal instead of a path or a cycle and the staircase goes strange. Tones repeat in great blocks, the same eigenvalue arriving with a multiplicity that grows with the level, and the low end of the staircase follows a power law whose exponent is a dimension of its own. The shape of the shape is written in the list of its tones.
In the tree
The spectra demo diagonalises the Laplacian of a design's graph in the browser, draws this staircase, and fits the slope of its low end. The complexity note is where those repeats become laws, counted level by level, and the walk dimension note reads the same low end as the speed of a wanderer. The modes demo shows the other spectrum of the same object, the design laid on a torus, where the eigenvalue field turns out to be a picture of the tile.
The Menger sponge
The carpet's solid cousin: cut a cube into 27, drill out the middle and the middle of each face, then do the same to the 20 cubes that are left.
Take a solid cube and cut it into 27 small cubes, three along each edge, like a puzzle cube. Remove the one in the very middle, where nothing shows from outside, and remove the middle cube of each of the six faces. Seven cubes are gone and 20 are left.
What that leaves is a cube with a square tunnel drilled through it in each of the three directions, all three meeting in the hollow middle. The 20 survivors are the eight corner cubes and the twelve edge cubes.
Now do the same to each of the 20. Each is cut into 27 and loses its own seven, so the second round leaves 20 x 20 = 400 cubes on a side of nine. At level n the count is 20^n cubes on a side of 3^n: 20, then 400, then 8000. The figure draws level 3, all 8000 of its cubes standing on a side of 27.
The tree builds it with one move. Write the level-1 rule as a small block of 27 cells, 20 filled and 7 void, and stamp a copy of that block into every one of its own filled cells. Repeat, and each repetition is a level. The counts multiply because 20 filled cells each carrying 20 filled cells is 400.
The rule reads one digit of each coordinate. Number the three slots along each axis 0, 1 and 2, and a small cube is thrown away exactly when two or three of its digits are the middle one. Nothing else is looked at. That is the same kind of rule as the carpet's, one axis longer, and it is why the sponge and the carpet sit side by side in the tree rather than in separate stories.
Volume drains away. Each round keeps 20 of 27, so after n rounds the solid occupies (20/27)^n of the cube it started in. That falls to zero, so the finished sponge has no volume. Its surface does the opposite: every round drills new tunnels and new walls, and the surface area grows past any bound you name. The shape is all skin.
Look straight at a face and you see the carpet. The cells of the sponge that touch one outer face are exactly the cells the carpet keeps, because on that face one coordinate is pinned and the rule on the other two is the carpet's rule. So each of the six faces of the figure is a Sierpinski carpet at the same level, and the shadow the sponge casts along an axis is a carpet too.
Like the carpet it stays in one piece at every level, because the 20 cubes of the rule are joined face to face all the way round and stamping a joined-up block into a joined-up block keeps it joined. A shape of no volume whose surface never stops growing is still one connected object you could walk across.
Counting boxes gives the sponge a dimension of log 20 / log 3, about 2.73, more than a surface and less than a solid, which is the fractal dimension read on three axes instead of two.
In the tree
The sponge is the design bang dim 3, code 23 of the core, filling 20 of 27 cells at side 3 and 20^level at every level after. Structure against noise races it against a random set of matched size at 27^3 and 81^3 and finds it in one piece both times. The sponge demo grows it and any other cube rule level by level, the universe demo shows it among all 22 distinct cube designs, and the tour demo reads its exposed faces off as an integer sequence. Its square cousin is the Sierpinski carpet.
The Mertens function
Mark every whole number plus one, minus one or nothing, then keep a running total. How far that total is allowed to wander is the Riemann hypothesis.
Every whole number gets one of three marks. Factor it into primes. If any prime appears twice, the mark is 0. Otherwise count the distinct primes: an even count marks plus one, an odd count marks minus one. One has no prime factors at all, an even count of none, so it marks plus one. This mark is the Mobius value, written mu(n).
Run through the first few. mu(1) is 1. mu(2) is minus one, one prime. mu(3) is minus one. mu(4) is 0, because two appears twice. mu(5) is minus one. mu(6) is plus one, two primes. mu(12) is 0 again. Roughly six numbers in ten escape a repeated prime and get a live mark, and the other four are dead.
The Mertens function is the running total of those marks: M(n) = mu(1) + mu(2) + ... + mu(n). The first values are 1, 0, minus one, minus one, minus two, minus one. It is a walk. At each step you go up, down, or stand still, and where you are is the balance so far between the even-count numbers and the odd-count ones.
The figure walks it out to a thousand. The blue line is M(n). The two faint curves are plus and minus the square root of n, opening outwards like a trumpet. Inside that trumpet the walk wanders: it climbs to 7 at n equal to 586, it falls to minus 12 at n equal to 665, and it finishes at 2. The trumpet at the right edge is 31.6 wide either way, so the walk is nowhere near touching it.
The square root is the right yardstick for a reason you can feel. If the marks were coin flips, plus one or minus one at random, then after n flips you would expect to be about the square root of n away from where you started. That is how random walks behave. So the picture asks one question: are the Mobius marks as well balanced as coin flips, or do they conspire and drift?
Nothing in the picture says they are balanced. The walk staying inside the trumpet up to a thousand is one sample of one range. The walk sits exactly at zero 92 times below a thousand, which looks like good behaviour, and that is exactly what an unproved pattern looks like from close up.
The precise statement is short and unreachable. If M(n) stays below any fixed multiple of n^(1/2 + e) for every small e you pick, then the Riemann hypothesis is true, and if the Riemann hypothesis is true then it does. The two are the same statement wearing different clothes. Nobody has either one.
There was a stronger guess, that M(n) stays strictly inside the trumpet, below the square root of n exactly, for every n. That guess is false. It has been proved that the walk leaves the trumpet somewhere, and no one has produced the place where it does. The proof gives a fact about the far distance and hands you no number to check, which is the reverse of the Goldbach situation and just as unsatisfying.
Why anyone cares about these marks: the Mobius value is what inverts counting. Sum mu(d) over all the divisors d of a number and the answer is zero for every number except one, where it is one. That single line is the sieve written as arithmetic, and it is why a sum of Mobius values is a measure of how much the primes cancel against each other.
In the tree
The Mobius page measures exactly this cancellation, not on the whole numbers but on digit designs, with the classical Mertens function as its control. The zeta page holds the other face, the zeros, and says why no route runs between the two on a design. The Farey stack note weights the stack by mu and turns the picture into a Mertens meter, and the echo demo reads the swings of that meter against the zeta zeros. The plain sum against the square root sits with seven other formulas on the famous formulas hub. The marks being summed are the Mobius function, and the hypothesis the sum is equivalent to belongs to the Riemann zeta function.
The transfer matrix
A table that says which state may follow which; multiply it by itself and it counts the walks of any length, and those counts grow like a fixed power.
Some machines have a small number of states and a rule about which state may follow which. A traffic light may go green, amber, red, green. A word may be built letter by letter with a rule that forbids some pairs. In both cases all you need to write down is a list of allowed steps.
The figure has three states and four allowed steps. From the top state you may stay where you are or move to the right state. From the right state you may only move to the left state. From the left state you may only move to the top. The arrows in the left panel say exactly that, and the loop at the top state is the step that stays put.
The panel beside it says the same thing as a table. There is one row and one column for each state, rows for where you are and columns for where you go. A lit cell means the step is allowed and a dark cell means it is not. Three states give nine cells, four of them lit, one lit cell for each arrow. That table is the transfer matrix.
Now count. How many walks of length n are there, counting every starting state and every finishing state? Length 1 is easy, it is the four arrows. Length 2 means an arrow followed by an arrow, and there are six such pairs. The bars along the bottom of the figure are these counts for lengths 1 to 8: 4, 6, 9, 13, 19, 28, 41, 60.
Multiplying the table by itself is what produces them. Take the entry in row i and column j of the table times itself: it is the sum over every middle state m of (steps from i to m) times (steps from m to j), which is exactly the count of two-step walks from i to j. Multiply n times and every entry of the result is the count of walks of length n between that pair of states. Add up all nine entries and you get the bar.
So one table, multiplied, answers a question about walks of every length at once. That is the whole trick, and it is why the table is worth a name. Nothing in it is special to three states: the same multiplication counts the walks on any graph from its adjacency table.
The counts have a pattern. Each one is the one before it plus the one three before it: 13 = 9 + 4, 19 = 13 + 6, 60 = 41 + 19. That is the three-step loop showing up in the arithmetic, and it means the counts can be continued for ever without ever touching a matrix again.
Look at how fast they grow. Divide each count by the one before it: 1.500, 1.500, 1.444, 1.462, 1.474, 1.464, 1.463. The ratios are settling down, and what they settle on is about 1.4656, the number r with r^3 = r^2 + 1. After a while the counts are just multiplied by that fixed number again and again, so the count of walks of length n is roughly some constant times r^n.
Every transfer matrix behaves this way. The counts of walks grow like a power, and the base of that power is a number belonging to the matrix: its largest eigenvalue, also called the spectral radius. That page says what the number is and why a table of non-negative counts always has one. Here it is enough to know that a table of allowed steps carries a growth rate inside it, and that reading the rate off the table is easier than counting the walks.
The name comes from physics, where the same table transfers a description of one slice of a system to the next slice. Whenever something is built one step at a time under a local rule, a transfer matrix is usually hiding in it, and the number of things you can build grows like a power whose base is that matrix's own.
In the tree
A rule on the last few digits of a number is a machine of this kind, and the memory dial demo prints the accepted words a level and the growth rate that replaces plain doubling. Beneath a design prices that dial with the transfer matrix of the rule, and the cuts note counts the cells of a diagonal slice by carrying a small integer from digit to digit, which is the same table under another name. What a second base costs is the one place where this instrument stops working.
Fractal dimension
Cover a shape with boxes, shrink the boxes, and watch how fast the count grows; the growth rate is the dimension, and for a carpet it is not a whole number.
Dimension is usually a word, one for a line, two for a square, three for a cube. It can also be a measurement, and the measurement is counting.
Take a line segment and cut it in half. It takes 2 half-length copies of itself to rebuild it. Take a square and halve both sides: it takes 4 of the small squares. Take a cube and halve all three sides: 8 of the small cubes. The counts are 2^1, 2^2 and 2^3, and the exponent is the familiar dimension.
Nothing depends on halving. Cut everything into thirds instead and the counts are 3, 9 and 27, which are 3^1, 3^2 and 3^3. The exponent is the same each time, so the rule is general: if shrinking by a factor s takes N copies, the dimension is log N / log s.
The figure counts boxes three times over. Each panel lays the same three by three lattice over a shape and lights the boxes the shape actually touches. The filled square lights all 9. The carpet lights 8, because the middle box is empty at every level. The diagonal line lights 3, the boxes it runs through corner to corner.
Read the three counts back through the rule. Nine boxes at scale one third gives log 9 / log 3 = 2, which is the square. Three boxes gives log 3 / log 3 = 1, which is the line. Eight boxes gives log 8 / log 3, and that is 1.892789, which is no whole number at all.
The carpet's count is not an accident of the scale chosen. Shrink the boxes by 3 and 8 are needed, by 9 and 64 are needed, by 3^n and 8^n are needed, for ever, because each round of the construction replaces one filled cell by eight. The ratio never settles on a whole number, so the answer stays log 8 / log 3.
That the answer lies between 1 and 2 matches what the shape looks like. The carpet has no area, so it cannot be two-dimensional, and it is far too tangled to be drawn as a curve, so it is not one-dimensional either. A number between the two is the honest report.
The Menger sponge is the same sum with different counts. Shrink by 3 and 20 of the 27 small cubes are needed, so its dimension is log 20 / log 3, about 2.73. It has no volume, so it is not solid, and it has far too much surface to be a sheet, so a number between 2 and 3 is again the answer.
Write it once for everything the tree builds. If a rule keeps fill cells out of a block base cells wide on each axis, then at level n there are fill^n cells of side base^-n, so the count of boxes at scale base^-n is fill^n and the dimension is
The carpet is fill 8 at base 3, the sponge is fill 20 at base 3, and a solid square is fill 9 at base 3, which returns the ordinary answer of 2. Box counting never contradicts the usual dimensions; it just keeps working where the usual ones run out.
In the tree
The dimension is not a parameter anywhere in the tree, it is read off the fill count, and the core derives it from the one line that says fills multiply with the level. Complex dimensions promotes that single number to the real part of a whole family of them, which is what makes the box count wobble rather than settle. The walk dimension measures a second and different one, how far a random walker gets on the same shape, and pairs the two. The sponge demo prints the dimension of any cube rule beside its fills and voids.
The spectral radius
Multiply an arrow by the same matrix again and again and it settles on one direction; the factor it stretches by there is the spectral radius.
A matrix takes an arrow and gives back another arrow. Write the arrow as a pair of numbers, the matrix as a square block of numbers, and the rule is the usual one: each row of the matrix pairs off against the arrow and gives one number of the answer. The arrow generally comes back pointing somewhere else and with a different length.
The figure does it eight times with one matrix. The matrix is [[2, 1], [1, 3]], four positive numbers. The first arrow points down and to the right. Multiply, and you get the second arrow. Multiply again for the third, and so on. Each arrow has been cut back to the same length before it was drawn, so the picture shows only the turning and not the growth.
The turning stops. The arrows swing round and crowd together near one direction, the dim ray drawn across the figure, and after that they barely move at all. Every arrow you start with ends up there, apart from a few unlucky ones, and starting further away only means the swing takes a little longer.
That settled direction has a name. An arrow that the matrix does not turn at all, but only stretches, is an eigenvector of the matrix, and the number it is stretched by is the eigenvalue. The dim ray in the figure is an eigenvector: multiply an arrow lying along it and it stays along it, longer by a factor of about 3.618 each time.
A two by two matrix has two such directions, with a stretch for each. Any starting arrow is a mixture of the two. Multiplying multiplies each part by its own factor, so the part belonging to the bigger factor pulls ahead, doubling its lead over the other part at every step. After enough steps the mixture is almost entirely that one part, which is why the arrows in the figure settle where they do. The bigger stretch wins simply by growing faster.
The largest of these stretching factors, measured without regard to sign, is the spectral radius of the matrix. It is the growth rate of the whole process. Lengths eventually multiply by it every step, so after n steps an arrow is roughly its own starting size times the spectral radius to the power n.
Here is the useful case. Suppose the matrix has no negative entries anywhere, which is what any table of counts looks like: a count is never below zero. Perron and Frobenius proved that such a table behaves in the tidiest possible way. There is one largest stretch, it is a real number and not a pair of them, it is positive, and the direction it belongs to can be drawn with all its coordinates positive too. No other direction stretches as much.
The last part matters as much as the first. A positive arrow settling on a positive direction is what lets you say where the counting ends up as well as how fast it grows. The matrix [[2, 1], [1, 3]] in the figure has all four entries positive, its top stretch is 3.618, and the direction it settles on points up and to the right into the positive quarter, exactly as the theorem says.
Put that together with the previous page. A transfer matrix is a table of non-negative counts, so it has one clean top eigenvalue, and the counts of walks it produces grow like that eigenvalue to the power of the length. The whole growth rate of a counting problem is one number sitting inside one table, and it can be computed without ever listing a single walk.
Nothing here derives the number. Finding an eigenvalue exactly means solving a polynomial whose degree is the size of the matrix, which is hopeless by hand past a few states and easy for a machine. The name and the guarantee are what a reader needs; a computer supplies the digits.
In the tree
The memory dial demo reads the growth rate of a digit rule straight off its table and prints it beside the plain doubling it replaces. Beneath a design treats that number as the dial, showing which rules cost nothing and which pay for their memory, and the cuts note gets the dimension of a diagonal slice as the logarithm of the top root of an integer matrix. The circle on a design brackets one of these roots by hand with certificates rather than trusting a float.
The random walk
A walker on a graph steps to a neighbour picked at random; after n steps on a grid it is about the square root of n away, and on a fractal it is slower.
Put a walker on a dot. At every tick it looks at the dots joined to the one it is standing on, picks one with no preference at all, and steps there. Repeat. That is the whole rule, and there is nothing else to it: no memory, no aim, no speed.
The figure runs it once. The lattice is 64 cells by 64, the walker starts at the middle yellow dot, and the blue trace is its path over 1024 steps. The orange dot is where it finished. The dim circle is drawn round the start with radius 32 cells, which is the square root of 1024.
The end of the walk sits on that circle, and this is the point of the picture. After n steps the walker is not n away, which is what a walker with a purpose would manage, and it is not still at home either. It is about sqrt(n) away. A thousand steps buy about thirty two cells of distance; a million steps would buy a thousand.
The reason is that squared distances add and distances do not. Suppose the walker is at distance d from home and takes one more step. Half the time the step is roughly outward and half the time roughly inward, so the average change in d itself is about nothing. But the average of d squared goes up by exactly one every step, since each step has length one and its direction is uncorrelated with where the walker already is. Start at zero, add one per step, and after n steps the average of d squared is n, so the typical d is sqrt(n).
Look at the trace and you can see where the time went. The path is not a tour of the lattice; it is a dense scribble in two or three knots with thin threads between them. A random walker spends most of its steps revisiting cells it has already worn out, and only occasionally makes a run in one direction. The knots are the wasted time, and there is no way to avoid them.
That sqrt(n) is the honest shape of any walk on any full grid, in any number of dimensions. It is usually written as n^(1/2), or turned upside down: the time to travel a distance r is about r^2. Doubling the distance costs four times the wait. This is diffusion, the same law that spreads ink through still water.
Fractals break it. Give the walker a shape with holes at every scale, the carpet or the gasket, and it now has to work around a hole of every size on the way out. It still wanders, but the detours are built into the shape and never end, so getting a distance r from home costs more than r^2 steps.
The exponent is the measurement. Write the time to reach distance r as r to some power d_w, so that distance after n steps is about n^(1/d_w). That number d_w is the walk dimension. On any full grid it is exactly 2. On a fractal it is bigger than 2, and the bigger it is the slower the shape is to cross.
It is a second and independent number from the fractal dimension, which counts how fast mass piles up with scale. Mass tells you how much of the shape there is; the walk dimension tells you how well connected it is, how much of the mass is on the way to somewhere. Two shapes can weigh exactly the same at every scale and still take different times to cross.
The two together say how the shape rings. The density of low tones of the graph Laplacian is set by twice the mass dimension divided by the walk dimension, a ratio called the spectral dimension, so how a shape sounds is how much of it there is divided by how hard it is to get around it.
In the tree
The race demo puts walkers on two base-3 designs with the same mass and the same fractal dimension at once, and they spread at different speeds. The walk dimension note is the census behind that race, measuring d_w two ways on designs matched by fill, and the complexity note reads the same number off the low end of the Laplacian spectrum instead of off a stopwatch.