Numerical integration
Named by 4 essays across 2 fields — each of them below, with the objects they name alongside it.
Points on a lattice that see almost nothing
Average a function over the points of a carefully tilted lattice and the error can fall like one over the square of the number of points — far faster than random sampling, and faster than the most evenly spread sequences. The reason is that a lattice rule is blind to only a thin set of frequencies, its dual lattice, and a smooth periodic function has almost nothing there.
An error bar for points that are not random
Evenly spread points integrate far better than random ones and give no error bar; random points give an error bar and integrate badly. Randomise the even points themselves — shift a lattice by a random vector, or scramble the digits of a Sobol' sequence — and both are kept: an unbiased estimate, a confidence interval from a handful of repeats, and an error that falls faster than any deterministic set's.
What a jump costs evenly spread points
Scrambled Sobol' points integrate a smooth function with an error that falls like N to the power −3/2. Put a jump in the integrand along a tilted line and the exponent halves, to −3/4, because about √N of the N boxes the points fill are cut by the jump and each of those is left to chance. A jump along an axis costs almost nothing, the cost grows with the length of the jump and the dimension, and integrating across the jump before sampling gives the whole rate back.
The area of the Mandelbrot set, from two sides
The Mandelbrot set has an area, and nobody knows it. Counting grid cells closes in on 1.5066 from both sides, but every count judges a cell by a single point, and points on the boundary never declare themselves. An exact formula exists — π times one minus a sum over the coefficients of the map onto the set's outside — and every partial sum is a guaranteed upper bound; after sixteen thousand coefficients the bound is still 1.786, and at the rate it falls it would need something like 10²⁵ more.
Named alongside it
The objects these essays reach for when they reach for this one.
Quasi-monte carloConvergence rateDiscrepancyScramblingSobol sequenceAreaConfidence intervalConformal mapCurse of dimensionalityDual latticeFourier seriesLattice