Square root
Named by 8 essays across 5 fields — each of them below, with the objects they name alongside it.
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.
A root lifted one digit at a time
On a dial of seven, 3 × 3 is 2. On a dial of forty-nine the square root of 2 must reduce to 3, so there are only seven candidates, and exactly one of them works: 10. On a dial of 343 exactly one lift of 10 works: 108. Each step adds one digit on the left, found by solving a linear equation, and the digits go on for ever — a number …21216213 whose square is 2, in a world where closeness means divisibility by seven.
The lengths dividers cannot reach
A pair of dividers carries a length from one place to another and draws nothing. With a straightedge it finds midpoints, parallels and right angles, and it draws the regular 17-gon. It cannot draw a segment of length √(1 + √2) — and the reason is not on the page at all, but in the other root of the equation that number solves.
Four lists find a collision sooner
Two lists of random 24-bit strings need about four thousand entries each before some string appears in both — the birthday bound. Ask instead for one string from each of four lists whose exclusive-or is zero, and lists of a few hundred suffice, because merging the lists in pairs manufactures the near-misses a direct search would have to find by luck. David Wagner's algorithm turns the square root into a cube root, and more lists into smaller roots.
Counting a population by its repeats
The birthday problem runs forwards from a known year to the chance of a match. Run it backwards and the matches measure the year: count how many pairs among the draws came out the same, and the number of kinds is about the number of pairs divided by that. It costs the square root of the population rather than a census of it — and when the kinds are unevenly common, what the repeats measure is not how many kinds there are but how many they behave like.
What two points build in two rounds
Start with two points and draw every line and circle they allow; mark every crossing; do it again. The first round gives six points, the second gives 203, and the third gives over 1.7 billion. Computed exactly, the 203 points show the tower of square roots growing in real time — eleven rational points, seventy-six that need √3, and the rest needing one of six new square roots.
How close two sums of square roots come
Two different sums of square roots of whole numbers are never equal: square roots of different squarefree numbers are independent, so no cancellation can make them agree. But they can come very close. Among sums of two square roots of numbers up to 320, √88 + √289 and √171 + √177 agree to eight decimal places. How many digits must be computed, in the worst case, to tell two such sums apart is not known — the best proof allows a number of digits doubly exponential in the length of the sums, the examples suggest only a modest polynomial, and the gap between them is why nobody knows whether the shortest route through points in the plane can be checked quickly.
A vote worth a square root
Give each country in a council votes in proportion to its people, and a citizen of the largest has about fifteen times the say of a citizen of the smallest. Give each country one vote and the same ratio runs the other way. Lionel Penrose saw in 1946 that the fair weight is the square root of the population, because one voter's chance of deciding an election falls as one over the square root of the crowd. Computed for twenty-seven states, the best quota is 61.5%, and it holds the ratio to 1.006.
Named alongside it
The objects these essays reach for when they reach for this one.
Birthday problemCollisionConjugateConstructible numberExpectationField extensionSimulationAlgebraic numberAlgorithmApportionmentBinaryBinomial coefficient