Random mapping
Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.
Two constants that do not walk at random
Pollard's factoring method trusts x² + c modulo a prime to repeat as soon as a random function would, after about √p steps. For c = 1 and c = 3 it does. For c = 0 and c = −2 it runs twelve to eighteen times longer on average, with almost no tail and enormous cycles, because those two maps are multiplication in disguise and their cycles are set by the order of 2 rather than by chance. Every other constant walks at random — including in the one respect in which x² + c is plainly not random, that it is two-to-one.
Houses traded in cycles
Everyone owns a house and would rather have someone else's. Let each point at the owner of the house they want most, follow the arrows into a cycle, and trade around it; repeat. The result is the only allocation no group can improve with its own houses, and nobody can gain by lying about what they want — the two guarantees stable matching could not give together.
Named alongside it
The objects these essays reach for when they reach for this one.
Birthday problemChebyshev polynomialCollisionKidney exchangeMarket designMultiplicative orderPareto efficiencyPollard rhoPrimitive rootStable matchingStrategy-proofnessThe core