Half the cube and √n neighbours

A truth function of $n$ letters colours the corners of the $n$-dimensional cube true or false. At any corner, flipping one letter moves to a neighbouring corner, and the function either keeps its value or changes it. The number of neighbours where it changes is the function’s sensitivity at that corner: how many single letters, flipped alone, would change the answer.

“All three letters true” is sensitive only near its single true corner: at $111$ every letter matters, and the sensitivity there is 3, while far from it nothing does. Majority has sensitivity 2 at the corners with two true letters or one, since flipping the minority letter changes nothing. Parity has sensitivity 3 everywhere, because every edge of the cube joins a true corner to a false one. The largest label is the function’s sensitivity, and it measures the worst case: the corner where the most single changes would matter.

The functions of the previous essay give a feel for the range. A weighted vote changes its answer only along the band of edges its cutting plane crosses. Majority of $n$ letters, for instance, has sensitivity about $n/2$: at a corner where the vote is tied to within one, the letters on the winning side each matter and the others do not. Parity, which no plane can describe, has sensitivity $n$ at every corner. The simplest functions are sensitive on few edges, and the least plane-like function on all of them.

What sensitivity was meant to measure #

Sensitivity is one of several ways of measuring how complex a truth function is, and the others look more serious. The degree of a function is the degree of the unique polynomial, with $\pm 1$ values, that agrees with it at every corner: how large a group of letters the function needs to multiply together. Block sensitivity allows flipping groups of letters at once. Decision-tree depth is how many letters a questioner must look at, in the worst case, to know the answer. Certificate complexity, quantum query complexity, approximate degree: all measure how much of the input a function must consult.

In 1989 and 1992 Noam Nisan and Mario Szegedy showed that all the serious measures are polynomially related — each is bounded by a power of any other — and they asked whether sensitivity belonged to the family too. Sensitivity was the odd one out. It could be much smaller than the others for all anyone could prove, and examples were known in which block sensitivity was about the square of sensitivity. Whether it could be smaller by more than a polynomial factor became the sensitivity conjecture, and it resisted for thirty years.

It is a strange question to be hard. Sensitivity is defined by counting neighbours on a cube. Every function of four letters can be listed and its sensitivity and degree computed in a fraction of a second, and no counterexample appears at any size anyone can search. But the relation had to hold for every number of letters, and nothing about small cubes said why. A statement that is checked in milliseconds at every size a computer can reach, and that nobody can prove, is the characteristic situation of this corner of combinatorics: the difficulty is never the individual case but the absence of a reason that covers them all.

A statement about half the cube #

In 1992 Craig Gotsman and Nathan Linial turned the conjecture into a statement about the cube itself: any set of more than half the corners of the $n$-cube contains a corner with many neighbours in the set — many meaning at least some fixed power of $n$. If that were true, sensitivity would be polynomially related to degree; if false, not.

The claim is easy to test on small cubes by exhaustion. On the 4-cube, choose nine of the sixteen corners in every one of the 11,440 possible ways, and for each choice find the chosen corner with the most chosen neighbours. The search asks which choice makes that number smallest. The answer is 2: no matter how nine corners are chosen, one of them has at least two chosen neighbours, and there are choices, like the one drawn, where no chosen corner has three.

Why more than half? Exactly half is too few: the corners with an even number of true letters are half the cube, and no two of them are neighbours, since a single flip changes the parity. That set has largest degree 0. Adding even one more corner breaks the pattern, and the question is how badly.

On the 3-cube, five corners always include one with two chosen neighbours, and $\sqrt 3$ rounds up to 2. Hao Huang proved in 2019 that the pattern holds for every $n$: any set of more than half the corners of the $n$-cube contains a corner with at least $\sqrt n$ neighbours in the set. By Gotsman and Linial’s reduction, that settled the sensitivity conjecture.

The matrix whose square is n #

Huang’s proof is two pages, and its heart is a matrix.

The adjacency matrix of the cube has a 1 wherever two corners are neighbours. Huang’s idea was to change some of those 1s to $-1$, following a recursive rule: the matrix for $n$ letters is built from two copies of the matrix for $n - 1$, one of them negated, joined by the identity along the edges between the copies. With that signing, the matrix $A$ satisfies $A^2 = nI$. The figure checks it for three letters: every entry of $A^2$ is 3 on the diagonal and 0 elsewhere.

The square being $nI$ says the eigenvalues are $\pm\sqrt n$, and since the trace is zero they come half each — $2^{n-1}$ equal to $\sqrt n$ and $2^{n-1}$ equal to $-\sqrt n$. Now take any set of more than half the corners and look at the part of $A$ with those rows and columns. By Cauchy’s interlacing theorem, a principal part of a symmetric matrix that keeps more than half the rows still has an eigenvalue at least as large as eigenvalue number $2^{n-1}$ of the whole, counted from the top — which is $\sqrt n$.

And the largest eigenvalue of any matrix with entries $0$ and $\pm 1$ is at most the largest number of nonzero entries in any row. In the part of $A$ belonging to the chosen corners, the nonzero entries in a row are the chosen neighbours of that corner. So some chosen corner has at least $\sqrt n$ chosen neighbours. That is the whole proof.

Each step is a standard piece of linear algebra. That a matrix’s square fixes its eigenvalues — if $A^2 = nI$, every eigenvalue satisfies $\lambda^2 = n$ — is the kind of fact the characteristic polynomial exists to deliver. That a symmetric matrix has a full set of perpendicular directions it only stretches is what makes interlacing possible, since the eigenvalues of a symmetric matrix are the maxima and minima of a quadratic form over subspaces, and restricting to a subspace can only squeeze them between their old neighbours. And the bound of an eigenvalue by the largest row sum of absolute values is what a map does to a circle at its most stretched: no direction can be stretched by more than the heaviest row allows.

What the theorem says about functions #

Through the reduction, the corner theorem becomes an inequality between the complexity measures. Huang’s proof gives, directly,

$$\deg(f) \le s(f)^2,$$

the degree of a function is at most the square of its sensitivity, for every function of every number of letters.

On four letters the table shows what the inequality allows and what functions actually do. Half of all functions have sensitivity and degree both 4, as parity does, and for more letters a randomly chosen function almost always has both at the maximum. But 96 functions have sensitivity 2 and degree 4, sitting exactly on the curve: degree four, and yet at every corner at most two letters matter. Those are the functions that make the square in the inequality necessary, the small-scale version of the examples in which block sensitivity grows like the square of sensitivity.

The inequality is sharp in that sense: the square cannot be replaced by a smaller power. It also closes the gap for every other measure at once, since all of them were already known to be polynomially related to degree. Block sensitivity is at most the fourth power of sensitivity; decision-tree depth, a larger power. Sensitivity, the simplest and most local of the measures, turned out to be as good as any of them up to a polynomial.

Why the problem waited #

The proof uses nothing beyond undergraduate linear algebra: a matrix, its eigenvalues, and an interlacing theorem from the nineteenth century. Many people had tried eigenvalue methods on the cube. What they had used was the ordinary adjacency matrix, whose eigenvalues are $n, n - 2, n - 4, \ldots, -n$, and whose middle eigenvalue — the one interlacing reaches — is about zero, which proves nothing.

The signing is what moves every eigenvalue to $\pm\sqrt n$ and so lifts the middle of the spectrum. It is a choice of sign for each edge of the cube such that going round any square face, the product of the signs is $-1$. That condition is what makes $A^2 = nI$: the entry of $A^2$ between two corners at distance two is a sum over the two paths between them, and the signs make the two paths cancel. The idea had appeared in other contexts, and nobody had pointed it at this problem.

The same signing trick has since been used on other graphs, to show that other families of vertex sets must contain a crowded vertex, and it has become a standard tool: choose signs on the edges so that the signed adjacency matrix has a spectrum with a large middle, and interlacing does the rest. Whether a graph admits such a signing is now studied for its own sake.

It is also a lesson about which structure to keep. The cube’s parity colouring — even and odd corners — is what makes exactly half the corners possible with no neighbours at all, and it is what the signed matrix respects: a signing is a way of recording, on each edge, a little more than whether it joins even to odd.

The half that has no neighbours #

Exactly half the cube can be chosen with no chosen neighbours, by taking the corners of one parity, and that set has a second life. In coding, the even corners are the even-weight code: every word with an even number of ones, a code in which any two words differ in at least two places, so that a single flipped bit is always detected. It is the largest code of length $n$ with that property, and the largest set of corners with no two adjacent.

Huang’s theorem says how that fact degrades. A set of corners one larger than the even-weight code cannot be free of neighbours, and it cannot even keep every corner down to a few neighbours: some corner has $\sqrt n$ of them. The more-than-half sets are the codes that fail to detect errors, and the theorem measures how badly the best of them must fail at its worst point. The perfect Hamming code sits at the other extreme — far fewer than half the corners, spread so that every corner of the cube is within one step of exactly one of them — and between the two lies the whole range of ways a set of corners can crowd or avoid itself.

What the figures cannot show #

The searches are exhaustive on the 3-cube and the 4-cube, and the theorem is about every cube. On the 4-cube the bound $\sqrt 4 = 2$ is met exactly; for larger cubes, Fan Chung, Zoltán Füredi, Ronald Graham and Paul Seymour showed in 1988 that there are choices of more than half the corners with largest degree about $\sqrt n$, so Huang’s bound is tight up to rounding. None of that is visible at $n = 4$, where the sets are small enough to search and too small to show the growth.

The signed matrix is drawn for three letters, and its square checked. The recursive rule that builds it for every $n$, and the fact that the square is always $nI$, are a two-line induction that the figure represents by one instance. And the interlacing theorem, which does the real work, is not drawn at all: it is a statement about eigenvalues of symmetric matrices and their principal submatrices, and a grid of plus and minus signs does not display it.

The degree table counts every function of four letters. The inequality it illustrates is about all functions of all numbers of letters, and four letters is exactly the size where the table is complete and the interesting examples — sensitivity 2, degree 4 — first appear.

Still open: how close sensitivity really comes #

Huang’s theorem gives $\deg(f) \le s(f)^2$ and hence block sensitivity at most $s(f)^4$. The best known examples have block sensitivity only about $s(f)^2$. Whether the true relation between block sensitivity and sensitivity is quadratic, quartic, or something in between is open.

The gap sits between what one matrix proves and what the best constructions achieve. The known examples are built by composing small functions that are cheap in sensitivity and expensive in block sensitivity, and composition gives exactly the square. A proof that the square is the truth would need an argument that sees block sensitivity directly rather than through degree, and Huang’s argument goes through degree. Several other questions on the same cube — about the sensitivity of functions invariant under symmetries, and about the largest degree forced in sets of other sizes — remain open in the same way: the cube is small, the measures are easy to compute, and the relations between them for large $n$ are not all known.

What the solution did settle is the qualitative picture that motivated the whole enterprise. Every reasonable way of measuring how much of its input a truth function must look at gives the same answer up to a polynomial, and that includes the most local measure there is — the count, at a single corner, of letters that matter. The remaining questions are about exponents, not about whether the measures belong together.

A corner with company #

The problem began as a question about truth functions and was solved as a question about a cube. Take more than half the corners — any selection at all — and some chosen corner has at least $\sqrt n$ chosen neighbours. Exactly half can avoid neighbours entirely, by taking every corner of one parity; one more corner forces company, and the amount of company is forced to grow with the dimension.

The search on the 4-cube sees the theorem in miniature: 11,440 choices, and none does better than two. The proof sees it for every $n$, in a matrix whose square is $n$ times the identity. That something so short settled something so long-standing is not a sign that the problem was easy. It is a sign that the right object had not been written down, and once the signs on the cube’s edges were chosen so that every square face multiplied to $-1$, the rest was a page of linear algebra.

Huang’s paper appeared in the Annals of Mathematics in 2019, and within days of the preprint the argument had been retold on blogs and in lecture notes, compressed to a single paragraph, and generalised. That speed is itself a measure of the proof. A thirty-year conjecture whose resolution anyone with a linear-algebra course can check is rare; this one sits beside the parity of a Gray code’s changes and the two diagonals of a square as an argument about the cube that is complete, short and entirely visible.