Matpic
mathematics, in pictures
Concept

Bound — where it appears

A number known to lie above or below a quantity nobody can compute exactly. Its value is in being provable rather than sharp, and a bound met exactly somewhere is worth far more than one that is merely close everywhere.

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

The largest code at each length, distance 3, against four bounds. A table with one row per word length, giving the exact size of the largest code of that length at the stated minimum distance and the values of the Singleton, Hamming, Plotkin and Gilbert-Varshamov bounds.

The best a code can be

A code is a set of words chosen far apart, and every construction answers "here is one" rather than "here is the best". The best can be computed at small lengths, and putting four classical bounds beside the exact answer shows which of them is doing the work and where none of them is.

computation · Error-correcting codes How many codewords lie within each radius, for a [7,3] code over 11 symbols. A bar for each decoding radius, its height the largest number of codewords found inside a ball of that radius around a randomly drawn received word, with the unique-decoding radius and the Johnson radius marked.

Past half the distance

A code of minimum distance five corrects two errors, and every account stops there. Two is the largest number for which the answer is unique — and a decoder that returns a short list instead of one answer reaches considerably further, which can be measured by counting the codewords in a ball.

computation · Error-correcting codes What the degree-5 sum costs, and what the bound claims. The error of the degree-5 Taylor polynomial of sin x against x, on a logarithmic scale, with Lagrange's bound drawn above it. The bound exceeds the error by a factor of 1.8 at the right-hand end.

An error with an unknown in it

Taylor's theorem does not say a partial sum is close to anything. It says the error is one more derivative evaluated somewhere nobody can name, and everything the theorem is worth comes from what happens when that somewhere is replaced by the worst case.

analysis · Taylor series An online rule taking nine tenths of what an oracle takes. The share of the oracle's expected maximum secured by the best single threshold, and by the threshold at the median of the maximum, for 8 field sizes of independent uniform values.

Half of what an oracle takes

Compare an online rule not against the best it could have done but against a rule that has seen every value in advance. One fixed threshold secures half of what the oracle collects, whatever the distributions are — and there is an example on which half is all there is.

probability · Optimal stopping A series that gets better, then worse. The error of Euler's series against the number of terms kept, at x = 0.05 and 0.1 and 0.2. At 0.05 the error falls to 1.1e-8 at 20 terms and then climbs without limit. At 0.1 the error falls to 1.8e-4 at 10 terms and then climbs without limit. At 0.2 the error falls to 1.8e-2 at 5 terms and then climbs without limit.

A series that converges nowhere

Expand Euler's integral in powers of x and the coefficients are the factorials, so the series converges at no x but nought. Stopped at its smallest term it still computes the integral to within about e^(−1/x) — and every term added after that makes the answer worse.

analysis · Taylor series The same two lengths at 3 angles, and the area largest at the right angle. Parallelograms spanned by columns of lengths 1.6 and 1.25 at angles 38, 90, 142 degrees. Their areas are 1.23, 2.00, 1.23; the bound 2.00 is the product of the lengths and is reached only when the columns are perpendicular.

The biggest box built from signs

Fill a square table with plus and minus ones and ask how large its determinant can be. The columns all have the same length, so the answer is a box with fixed edges — largest when every corner is square, which is possible only when the size is a multiple of four.

algebra · Determinant 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

Named alongside it

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

ApproximationError-correcting codeConvergenceError analysisExhaustive searchHamming distanceRemainderTaylor seriesAsymptotic seriesChebyshev polynomialCompetitive ratioConditional probability

All concepts