Matpic
mathematics, in pictures
Theme

Counting the same thing twice — page 6

One collection, counted by two different methods, and an identity that falls out because both answers have to agree. The proof is the pair of counts.
The two squares of 97, produced by division. A table of the division chain on 97 and a square root of minus one modulo it, with each row's quotient and remainder, the point at which the remainder falls below the square root marked, and the two squares that add to 97. Number

The two squares actually produced

Three proofs say a prime one more than a multiple of four is a sum of two squares, and not one of them hands over the squares. Running the Euclidean algorithm half-way does — and where to stop is the whole of the correctness argument.

 Waiting for all 6 when they are not equally likely. One bar per kind giving the expected wait for that kind on its own, with the rarest much the tallest, and the expected wait for the whole collection printed above them. Probability

The one that hardly ever comes up

Make the kinds unequally likely and the tidy decomposition into stages fails, because a stage's rate now depends on which kinds turned up rather than on how many. What replaces it is an alternating sum over every subset — and the rarest kind turns out to be nearly the whole answer.

 Six lists of cycle shapes, and how many coverings each has. A table of lists of cycle shapes over a sphere, each with the Euler characteristic the Riemann–Hurwitz count gives, the number of lists of permutations with that product, and the number of those that connect all the sheets. Topology

A count that can say zero

The branched count ends on a list of cycle shapes that passes every test and describes no covering. There is an exact formula for how many coverings a list has — a sum over the character table of a symmetric group — and it returns nought without giving any reason why.

 A circle trapped between two 12-sided polygons. A circle with a regular polygon of 12 sides inscribed in it and another circumscribed about it, beside a table of the bounds on pi obtained by doubling the side count. Geometry

Pinned between two sequences

The ring dissection makes the answer obvious and proves nothing. Archimedes' method proves it and makes nothing obvious — it never exhibits the area at all, it rules out every other value — and the recursion that drives it computes π by hand with one square root a step.

 A hemisphere and a cylinder with a cone taken out, sliced at one height. Two solids drawn in profile — a hemisphere, and a cylinder with a cone removed — each cut at the same height, with the disc and the annulus the cut produces marked and their equal areas given. Geometry

The slice that has to match

The same slicing one dimension up gives the sphere's volume in a line, once one comparison is noticed: at every height a hemisphere's disc has exactly the area of a cylinder's slice with a cone's taken out of it. The principle that licenses that comparison also returns a false answer the moment the slices are not parallel.

 2 independent rows and 2 independent columns. An array of 3 rows and 4 columns beside its transpose, with the independent rows of each shaded, showing the same count on both. Algebra

Counted across and counted down

A rectangular array has a number of independent rows and a number of independent columns. The two are counted in different spaces, from different objects, by computations that share nothing — and they are always the same number, which is why 'rank' is one word.

 2 independent cycles and 3 independent cuts, on 5 edges. A small graph beside its incidence matrix, with the matrix's rank and nullity given and shown to be the number of independent cuts and the number of independent cycles. Algebra

The cycles and the cuts

The count that splits a map's source into what dies and what survives has nothing to do with graphs. Apply it to a matrix built from a graph's edges and points and it says that a graph's independent cycles and its independent cuts add to its number of edges — a theorem about drawings, obtained from an array.

 A design on 7 points cannot have fewer than 7 blocks. The incidence matrix of a design on 7 points and 7 blocks beside the product of it with its own transpose, which has a constant off the diagonal and a determinant computed exactly. Computation

More blocks than points

A schedule in which every pair meets once cannot use fewer groups than it has people. Nothing about the counting conditions says so, and the proof is not combinatorial at all — it is a determinant, computed over a field the schedules have nothing to do with.

 A plane of 13 points from a list of 4 numbers. A ring of 13 points with one block of 4 of them drawn as a closed path, beside the table of the 13 blocks its shifts produce. Computation

A plane in a list of numbers

A projective plane of order three has thirteen points and thirteen lines and fifty-two incidences. All of it is in the four numbers 0, 1, 3, 9 — because their pairwise differences hit every non-zero residue modulo thirteen exactly once, and the plane is that list's thirteen shifts.

 A year of birthdays with a seasonal swing of ±50%, peaking in September. Bars for the 365 days of a model calendar with a seasonal swing of ±50%, peaking in September, drawn as each day's excess or shortfall against an even year. A shared birthday among 23 people has chance 54.86% against 50.73% for the even year, the first group with an even chance is 22, and the calendar behaves like 324.4 equally likely days. Probability

Any unevenness brings the match sooner

Real birthdays are not spread evenly across the year, and every such departure pushes the famous twenty-three down rather than up. The proof is one move on two days at a time, and what it leaves behind is a single number — the one ecologists use to count species.

 How the abundancy σ(n)/n is distributed, up to 1,000,000. The share of numbers up to 1000000 whose ratio σ(n)/n is at least t, for t from 1 to 4. It is 0.2475 at two, 0.0202 at three and 0.00023 at four, with a steep fall just above one, where the numbers with no small prime factor sit. Number

Why a quarter of numbers overshoot

About one number in four has proper divisors adding to more than itself. That a proportion exists at all is not automatic — there are sets defined just as simply that have no proportion — and the reason this one does is that abundance is inherited by multiples, and the numbers it is first inherited from are sparse enough to add up.

 The Seifert circles of the trefoil. The trefoil with an orientation, cut at each of its 3 crossings and reconnected the way the orientation allows. The 6 segments form 2 circles, and the surface built from them has genus 1. Topology

The surface a knot bounds

Every knot is the edge of a surface with two sides, and Seifert found a way to build one from any diagram: smooth the crossings, fill the circles that result with discs, and join them with twisted bands. Counting the handles gives an upper bound on how complicated the knot is, the Alexander polynomial gives a lower one, and for the simplest knots the two meet.

 Lissajous figures for every coprime pair of frequencies up to 4. A 4 by 4 grid of Lissajous figures x = sin(pt + 0.3), y = sin(qt), with the crossing count 2pq − p − q under each and the non-coprime pairs left blank. Analysis

When two circular motions come home

Drive a point across with one sine wave and up and down with another. If the two frequencies are in a whole-number ratio the point retraces a closed figure whose crossings can be counted in advance — 2pq − p − q of them — and if they are not, it never comes back and fills the square, spending twenty times longer in the corners than in the middle.

 The sum of the first 6 squares, as a staircase over a curve. Bars of height k^2 for k from 1 to 6, totalling 91, drawn over the curve y = x^2, whose area up to 6 is 72.00. The slivers between staircase and curve hold 19.00, close to half the last bar. Geometry

Sums of powers, read off a staircase

Add the first n squares, or cubes, or seventh powers, and the answer is always a polynomial in n. Its first term is the area under a curve, its second is half of the last step, and every term after that is a correction for the corners of a staircase — which is where the Bernoulli numbers come from, and why they eventually grow without bound.

 100 as three triangular numbers. 100 drawn as three triangles of dots with 36, 36 and 28 dots. There are 6 such decompositions. Geometry

Three triangular numbers, and no fewer

On 10 July 1796 Gauss wrote in his diary: ΕΥΡΗΚΑ — num = Δ + Δ + Δ. Every whole number is a sum of three triangular numbers. Two are not enough, and not by a little: the numbers that are sums of two thin out to a share of nought. Both facts are statements about squares in disguise, and one picture translates them.

 Even and Paz's halving, for 4 people. The recursive halving procedure run on a cake valued differently by 4 people: each round's marks and cuts, and the final pieces, each worth at least a 1/4 share to its owner. 8 marks are made. Applied

How many cuts a fair share costs

Every person can be guaranteed a share of a cake worth at least one n-th by their own measure, and the oldest rule that does it asks about n²/2 questions. Splitting the people into halves and the cake at a median mark asks about n log n — and a theorem says nothing can ask fewer. Fairness has a price, and it can be counted.

 Seven powers of √2 + ∛3 in a space of six. A table of the powers 1 to (√2 + ∛3)⁶ as coordinate vectors over a six-element basis, with the coefficients of the dependency among them: the minimal polynomial x⁶ − 6x⁴ − 6x³ + 12x² − 36x + 1. Algebra

Seven powers in a space of six

Is √2 + ∛3 a root of some polynomial with whole-number coefficients? It lives in a field of dimension six, so its first seven powers are seven vectors in a six-dimensional space and must be dependent — and the dependency, solved exactly, is the polynomial. The same count shows every sum, product and quotient of algebraic numbers is algebraic, without ever needing a formula.

 The integers of ℚ(√5), with ℤ[√5] inside them. Points a + bφ plotted against their conjugates for small whole a and b, with the index-two sublattice ℤ[√5] filled and the basic cells of both lattices shaded, of areas √5 and 2√5. Algebra

The integers a field contains

Inside the field of numbers a + b√5, the obvious integers are those with whole a and b. They are not all of them: the golden ratio has a one-half in it and satisfies x² = x + 1, a monic equation with whole coefficients, exactly as an integer should. The right integers form a lattice twice as dense as the obvious one — and a whole-number matrix proves they are closed under addition.

 Breadth-first levels in a planar triangulation. A Delaunay triangulation of 160 random points with each point coloured by whether it is inside, on or outside the level 4 steps from the centre; that level of 23 points separates 31 from 106. Discrete

The few points that cut a flat graph

Any graph that can be drawn without crossings, however large, falls into pieces of at most two thirds once a few points are removed — about the square root of its size, never more than 2.83 times it. A grid shows the square root cannot be beaten, a ring of breadth-first neighbours comes close, and a cycle through a shallow tree finishes the job.

 Every stable matching leaves out the same people. 4 stable matchings of a market with short lists, drawn as two columns joined by edges; every one leaves the same letter and number unmatched. Applied

The people every stable answer leaves out

Let the lists be short and let one side take several partners. Stable matchings still exist and there can be many of them — but every one leaves out exactly the same people, and a member who is left with an empty place holds exactly the same partners in every one. A three-line count proves it.

 The most edges with no four-cycle. Points for n = 2 to 9: the largest number of edges with no four-cycle, 1, 3, 4, 6, 7, 9, 11, 13, between the counting bound above and ½n^(3/2) below, far under the complete graph's count. Discrete

The densest graph without a square

Forbid four points joined in a cycle and a graph can keep only about ½n^(3/2) of its edges — far fewer than the quarter of all pairs a triangle-free graph keeps. Counting pairs of neighbours proves the ceiling in two lines. What reaches it is not a random graph but a finite geometry: the points of a projective plane, joined when they are orthogonal.

 A triangle, its midpoints and its centroid, turned into lines. The dual arrangement of 7 points: one line per point, crossing where points were collinear. 3 crossings are of exactly two lines, the dual of the ordinary lines; the others are where three or more meet. Geometry

Three ordinary lines from a count

Kelly's proof finds one line through exactly two of the points by minimising a distance. Melchior, seven years earlier, had found three — by turning every point into a line and counting the corners, edges and regions of the picture that results. Euler's formula for the projective plane does the rest, and it says exactly which configurations have no more than three.

 The continued fraction of e. Bars for the first 30 continued-fraction terms of e: mostly ones, with every third bar rising in a straight staircase, 2, 1, 2, 1, 1, 4, 1, 1, 6, …. Number

The pattern in e's continued fraction

Written as a continued fraction, e is 2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8 — two ones, then the next even number, for ever. Euler found the pattern and proved it with a differential equation. A proof from 2006 needs only three integrals, each of which turns out to be exactly the error of one of e's own convergents.

 Two children, and at least one is a boy. Four equally likely families drawn as quarters of a square: the question “is at least one a boy?” rules out only the girl–girl family, and leaves three equal quarters; the chance of two boys is 33.3%. Probability

Two children and the sentence about one of them

A family has two children and at least one is a boy. The chance that both are boys is one in three — or one in two, or anything from one in three to certainty — and every one of those answers is right for some way the sentence could have come to be said. There is no host and no door, and the protocol is still the whole problem.

All themes