Ten results, ten different mathematical questions

Several results concern how tightly objects fit. A binary code of length $n$ and minimum distance $d$ is a set of strings in $\{0,1\}^n$, any two of which differ in at least $d$ positions; such a code corrects up to $t = \lfloor (d-1)/2 \rfloor$ errors. Balls of radius $t$ around the code words cannot overlap, which gives the Hamming bound on the largest size $A(n, d)$:

Spherical codes ask the same question for points on a sphere kept at least a given angle apart, and sphere packing asks it for balls in space. Improving a bound in these problems means either a better construction or a sharper proof that no configuration can do better.

The determinant and the permanent of an $n \times n$ matrix differ only in their signs:

Yet Gaussian elimination computes the determinant in polynomial time, while computing the permanent is #P-hard (Valiant, 1979). Arithmetic circuit complexity asks how many additions and multiplications a formula for the permanent needs; proving it needs many is an algebraic version of the P versus NP question.

Colour every edge of the complete graph $K_n$ with one of $k$ colours. The multicolour Ramsey number $R_k(3)$ is the smallest $n$ for which a triangle with all three edges the same colour is unavoidable. For two colours $R_2(3) = 6$, and for three colours $R_3(3) = 17$. Beyond that only bounds are known: $R_k(3)$ grows at least exponentially in $k$ and at most like $e \cdot k!$.

A group $G$ is sofic if its multiplication can be imitated by permutations of finite sets: for every finite $F \subseteq G$ and $\varepsilon > 0$ there is a map $\phi: G \to \operatorname{Sym}(n)$ that is almost multiplicative on $F$ and sends each $g \neq 1$ in $F$ to a permutation that moves almost every point. Many conjectures are known to hold for sofic groups, and whether every group is sofic was a long-standing open question. For each of the ten topics, the precise theorem is in the manuscript and its Lean module.