Matpic
mathematics, in pictures
Concept

Polynomial

An expression built from a variable by adding and multiplying only, with whole-number powers. Its degree bounds its number of roots, and over the complex numbers it has exactly that many when they are counted properly.

Named by 28 essays across 8 fields — each of them below, with the objects they name alongside it.

A degree-2 polynomial over GF(11), and the 7 values sent. A grid of the finite field with the polynomial's value at each point marked, and the transmitted symbols picked out.

A polynomial through the gaps

Write the message as the coefficients of a polynomial and send its values instead. Any k of them determine the polynomial, so it does not matter which ones are lost — and it does not matter how many, as long as k survive.

computation · Error-correcting codes The image of four circles, turning 0 to 3 times. The polynomial applied to circles of four radii, each image drawn as a closed loop with the origin marked, and the number of times the loop goes round it.

A loop that cannot miss the middle

Feed a circle into a polynomial and a closed loop comes out. A small circle gives a loop that does not enclose the origin; a large one gives a loop that goes round it as many times as the degree. Something has to happen in between, and that something is a root.

algebra · Polynomial roots 3 roots, and the two numbers the coefficients already knew. The roots of a degree-3 polynomial, found numerically, with the point they average to. That average, and their product, are readable straight off the coefficients without finding the roots at all.

What the coefficients already know

Finding the roots of a polynomial is hard and often impossible in closed form. Reading off their sum, their product and how many of them are real is none of those things — those numbers are sitting in the coefficients, and no root-finding is required to get at them.

algebra · Polynomial roots Counting the colourings, by deleting and contracting. A graph beside the two smaller graphs its edge deletion and contraction produce, with the number of proper colourings of each at every number of colours up to 5.

Counting the colourings

Asking whether a graph can be coloured with four colours gives a yes or a no. Asking how many ways there are gives a polynomial — and the polynomial answers the first question, and several others nobody asked.

discrete · Graph colouring Two coefficient arrays, one with determinant zero and one without. The Sylvester matrices of two pairs of polynomials drawn as grids of coefficients, one pair sharing a root and one not, with each determinant computed in whole numbers and checked against whether a shared root exists.

A shared root, found without finding it

Two polynomials have a root in common exactly when one determinant built from their coefficients is zero. No root is computed, nothing is approximated, and the same construction turns two equations in two unknowns into one equation in one.

algebra · Polynomial roots The polynomial whose roots are the stretches. The determinant of A − λI plotted against λ for the map [2, 1, 1, 2], with its roots at 3 and 1 marked.

The polynomial whose roots are the stretches

Finding the directions a map leaves alone means finding the numbers at which it crushes something to nothing. Those numbers are the roots of one quadratic, and everything the map does is written in its two coefficients.

algebra · Eigenvectors The polynomial that squeezes π. On the left, xⁿ(π − x)ⁿ/n! drawn at several degrees, its largest value falling toward nothing; on the right, the derivatives of the same polynomial at zero, every one a whole number.

An integral that cannot be a whole number

Niven's proof that π is not a fraction is the same squeeze as the one for e, with a much harder multiplier. A polynomial supplies the whole number; its own smallness supplies the contradiction; and both halves are computable.

number · Irrationality A 4-bit register that visits all 15 nonzero states. The first 15 states of a 4-bit linear feedback shift register with taps at 4 and 1, with the bit that leaves the register at each step; the output shows every nonzero window of 4 bits exactly once.

A memory of four bits

A register holding four bits, shifting them along and adding two of them back, runs through all fifteen nonzero states before it repeats. Which two are added back is a question about a polynomial, and getting it wrong costs fourteen of the fifteen.

computation · De bruijn Every pattern, exactly as often. A table over 4 window lengths of a shift register's output stream: how many bit patterns are possible, how many actually occur, and the difference between the most and least frequent, which is one in every row.

Nineteen thousand bits of state

The generator most simulations actually use is not clever. It is a linear recurrence over the two-element field with an enormous state, and its virtues are a proved period, a proved equidistribution and speed — none of which is unpredictability, which it does not have and does not claim.

computation · Pseudorandomness A polygon of 4 points averaged down to its curve at t = 0.40. A control polygon of 4 points, the 3 rounds of weighted averaging at t = 0.40 drawn as nested polylines, the single point they end at, and the whole curve those points trace. The weights on the control points are 0.216, 0.432, 0.288, 0.064.

Averaging down the triangle

Change one word in the rule that builds Pascal's triangle — take a share of each entry above instead of adding them — and the triangle stops counting and starts averaging. The same rule then draws smooth curves from polygons and approximates every continuous function by polynomials, at a rate that no amount of smoothness can improve.

discrete · Pascals triangle The zeros of x² + y² + z² over GF(5), and of x² + y² over GF(7). Grids of every point over a small prime field with the solutions of a quadratic equation filled in: the three-variable equation drawn as one slice per value of z, beside a two-variable equation with far fewer solutions.

Solutions that come in multiples of p

Count the solutions of x² + y² + z² = 0 in the field with five elements and there are 25; with seven, there are 49. Whenever a system of equations has more unknowns than its total degree, its number of solutions is a multiple of the characteristic — which forces a solution besides zero, and the reason is a sum over the field that vanishes because its non-zero elements form one cycle.

computation · Finite fields The cubic curves over GF(43) with the most and the fewest points. The solutions of two equations y squared equals x cubed plus ax plus b over the field with 43 elements, drawn as dots on a square grid: the curve with the most points and the curve with the fewest.

Give or take twice the square root

A cubic curve over the integers mod 43 should have about 44 points — one for each value of x, on average, and one at infinity. No curve misses by more than 13, the largest whole number below 2√43, and every count from 31 to 57 belongs to some curve. The first fact is Hasse's theorem, the second Deuring's, and the way the counts spread between the limits is a semicircle.

computation · Finite fields The Alexander matrix of the trefoil. The trefoil with its 3 arcs numbered and its 3 crossings lettered, beside the 3 by 3 matrix they give. A minor of the matrix is the Alexander polynomial t − 1 + t⁻¹, whose value at −1 is the determinant 3.

A polynomial behind the colourings

The figure-eight knot and the cinquefoil both have determinant five, so they admit exactly the same colourings, and every counting argument treats them as one. Put a variable where the colouring rule has a two and the determinant becomes a polynomial — and the two knots come apart.

topology · Knots 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.

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.

geometry · Figurate numbers The powers of 4 roots, added: 1, −1, 4, −5. For k from 1 to 4, the k-th powers of the roots of a degree-4 polynomial drawn as arrows placed tip to tail. Each walk ends on the real axis at a whole number, the k-th power sum, which the coefficients determine.

Every power sum, from the coefficients alone

Raise the roots of a polynomial to the k-th power and add them. However the roots turn, the total is a whole number when the coefficients are, and Newton's identities produce it from the coefficients one step at a time — no root is ever found. Run the rule on x³ − x − 1 and out comes Perrin's sequence, whose terms know which numbers are prime, nearly.

algebra · Polynomial roots The roots of the derivative inside the hull of the roots. Three polynomials of degree five, each drawn as its roots with their convex hull shaded, and the four roots of its derivative marked. Every root of the derivative lies inside the hull.

The roots of the slope stay inside

Mark the roots of a polynomial in the complex plane and stretch a band around them. However the roots are arranged, the roots of the derivative land inside the band — never outside, never on a new frontier. The reason is a balance of pushes, the same reason makes the derivative of a cubic mark the foci of an ellipse nobody asked for, and a question about how far inside the roots must sit has been open since 1958.

algebra · Polynomial roots "There is an x" is a shadow: x² + ax + 1 = 0 has a solution exactly when |a| ≥ 2. A grid with a horizontal and x vertical, marking the cells the curve x squared plus a x plus one equals zero passes through; beneath it, a strip marking the columns that contain a mark, which are exactly those with a at least two in size.

A quantifier is a shadow

'There is an x such that …' asks whether a column of a grid contains a mark — which is the same as asking whether a shape casts a shadow on the axis below it. Over the real numbers every such shadow can be described without the quantifier, by polynomial inequalities: 'x² + ax + 1 = 0 has a solution' is just a² ≥ 4. Over the whole numbers the same kind of shadow can carve out the primes, and any set a computer can list.

logic · Quantifiers Counting the real roots of x⁵ − 5x³ + x² + 3x − 1 with Euclid's algorithm. Above, the graph of a polynomial over an interval with its real roots marked; below, a step function counting sign changes in the polynomial's Sturm chain, which drops by one at each root; beside them the chain of polynomials listed.

The remainders that count the roots

Run Euclid's algorithm on a polynomial and its derivative, flipping the sign of each remainder, and write down the signs of the whole chain at any point. The number of sign changes drops by exactly one each time the point passes a real root — so the roots in any interval can be counted, exactly, without finding a single one.

geometry · Euclidean algorithm The three pairings of the roots of x⁴ + x + 1. Three panels each showing the same four roots of a quartic in the complex plane, joined in a different way into two pairs, with the value of the sum of the pair products beneath.

Three ways to pair four roots

Four roots can be split into two pairs in exactly three ways, and the three numbers r·r′ + r″·r‴ those pairings give are the roots of a cubic whose coefficients can be read straight off the quartic. That cubic is where Ferrari's formula gets its cube roots, and it is also a verdict: whether its roots are rational decides which of the twenty-four symmetries the quartic's roots actually have.

algebra · Galois correspondence A line in every direction in the plane over GF(7), in 31 points. A square grid of the points of a small finite plane with the points of a Kakeya set filled, beside a list of the lines it contains, one for each direction.

No set with a line in every direction is small

In the plane over the integers modulo 7 there are 49 points and lines in 8 directions. A set holding a whole line in every direction needs 31 of the points — more than half — and in any dimension such a set fills a fixed share of the space. In the real plane the same sets can have area zero. Over a finite field one polynomial of low degree shows they cannot be small.

computation · Finite fields A + B modulo 13: 4 and 3 residues make 9. A clock face of residues with two sets marked on an inner ring and their sumset marked on an outer ring.

A sum of two sets modulo a prime cannot be small

Add every element of one set of residues to every element of another. Over the whole numbers the sums always number at least |A| + |B| − 1. Modulo a prime the sums can wrap round and collide, and still they never number fewer — the theorem Cauchy proved in 1813 and Davenport again in 1935. Modulo 12 they can. A polynomial of low degree explains the difference in a paragraph.

computation · Finite fields The trefoil and its mirror image. The trefoil beside its reflection, with writhe 3 and −3. The Jones polynomials are t + t³ − t⁴ and −t⁻⁴ + t⁻³ + t⁻¹; the Alexander polynomial of both is t − 1 + t⁻¹.

A polynomial that tells left from right

The trefoil and its mirror image have the same colourings, the same determinant and the same Alexander polynomial, and the first proof that they differ was a hard argument about groups. Smooth every crossing both ways, count the circles in each of the resulting pictures, and add up the counts with the right weights: the total changes when the knot is reflected.

topology · Knots The best degree-3 polynomial to eˣ: its error touches its largest size 5 times. The error curve of the best uniform polynomial approximation of degree 3 to eˣ on the interval from −1 to 1. It reaches its maximum size 5.528 × 10⁻³ at 5 points, alternately above and below, at x = -1.000, -0.682, 0.050, 0.732, 1.000.

The error that keeps coming back to its worst

Judge a polynomial by its largest error on an interval and there is exactly one best one of each degree. It is recognised without comparing it to anything else — its error rises to the same largest size, alternately above and below, one more time than there are coefficients.

analysis · Taylor series The necklaces of 7 beads with 3 black. C(7, 3) = 35 arrangements in 5 rotation classes of sizes 7, 7, 7, 7, 7.

The row that proves a prime

Fermat's little theorem can be fooled: 561 passes it for every base and is not prime. Thread necklaces with a fixed number of black beads instead of any colours at all, and the count becomes a statement about a whole row of Pascal's triangle — every middle entry of row n is a multiple of n exactly when n is prime — which no composite can fake. Written as polynomials it is (x + a)ⁿ = xⁿ + a, and cut down to size it is the first proof that primes can be recognised in polynomial time.

number · Fermats little theorem The roots of random polynomials of degree 30 and 100: few are real. degree 30: 2 real roots at -2.335, -1.074; degree 100: 2 real roots at -0.327, 0.994.

Almost none of the roots are real

Pick the coefficients of a polynomial of degree a thousand at random, each one an independent draw from the bell curve, and ask how many of its thousand roots are real. The answer is about five. Mark Kac found in 1943 that the average grows only like (2/π) ln n, and the reason can be read off the real line itself: the real roots crowd towards +1 and −1 and spread evenly on a logarithmic scale of distance from them.

algebra · Polynomial roots The roots of every polynomial of degree 11 with coefficients ±1. 22528 roots; radii from 0.500 to 2.000; 42% within 0.1 of the unit circle.

Random roots crowd onto the circle

The roots of a random polynomial are not scattered across the plane. They gather within about 1/n of the unit circle, and their directions spread evenly round it. Paul Erdős and Pál Turán proved in 1950 that this is not a fact about randomness at all: any polynomial whose coefficients are all of roughly one size has roots whose directions are nearly even, and the inequality says exactly how nearly, in terms of nothing but the coefficients.

algebra · Polynomial roots The proof of Descartes' rule, one term at a time. Four stacked graphs: a four-term polynomial with three positive roots, and the three polynomials obtained by dividing out a power of x and differentiating, each with one fewer term, one fewer sign change and one fewer positive root.

What the signs allow

Descartes' rule reads the signs of a polynomial's coefficients and bounds its positive roots by how often they change — a bound set by the number of terms, not the degree, and proved by nothing more than Rolle's theorem. Each count the rule allows can be had. But not every pair of counts, positive and negative, that the rule allows together can be had together: the first combination that never occurs is at degree four, and the list of impossible ones is still being worked out.

geometry · Euclidean algorithm Two curves with five crossings: x⁶ + (44/31)y³ − y and its mirror. Two curves in the positive quadrant, each the zero set of a trinomial, crossing at five marked points.

Five where four were promised

In one unknown, a polynomial with three terms has at most two positive roots, whatever its degree. The natural guess for two equations in two unknowns, each with three terms, was two times two: four. It is wrong. Bertrand Haas found two such equations in 2002 whose curves cross five times in the positive quadrant, all five crowded within a tenth of one corner, and five turned out to be the most there can ever be.

geometry · Euclidean algorithm

Named alongside it

The objects these essays reach for when they reach for this one.

RootsFinite fieldComplex numbersDegreeDerivativeDiscriminantModular arithmeticSymmetric functionApproximationBinomial coefficientCoefficientCounting argument

All concepts