What a formula keeps when letters are fixed

The formula that cannot share computed the smallest formula, in and, or and not, for every one of the 65,536 functions of four letters, and checked Khrapchenko’s lower bound against the exact sizes. It ended at a wall. Counting shows that almost every function of $n$ letters needs formulas of length about $2^n/\log n$. But for any function anyone can actually write down, the best lower bound anybody has proved is about $n^3$ letters. That essay named the wall. This one draws the machine that got the bounds up to it, and shows why the machine can go no further.

The machine is called shrinkage. Fix some of a formula’s letters to constants and simplify. Many of its leaves stop mattering, because a constant under an “and” or an “or” either decides the connective’s output or drops out. If formulas lose leaves faster than the function loses complexity, a function that stays hard after fixing must have had a large formula to begin with. Every improvement in formula lower bounds from 1961 to 2014 came from proving that formulas shrink faster than the previous proof had shown.

Constants that switch off their siblings #

The hero figure is the whole mechanism on one example. Parity of four letters, $x_1 \oplus x_2 \oplus x_3 \oplus x_4$, is true when an odd number of letters are true. Written with and, or and not, with the "not"s pushed down to the letters by De Morgan’s laws — one connective is enough showed how far that rewriting can go — its smallest formula has sixteen leaves, and that is exactly the size the formula that cannot share found for it. The tree combines $x_1 \oplus x_2$ and $x_3 \oplus x_4$, each written as $(a \wedge \neg b) \vee (\neg a \wedge b)$.

Now fix $x_3$ to 0 and $x_4$ to 1. Each leaf reading $x_3$, $\neg x_3$, $x_4$ or $\neg x_4$ becomes a constant. A 0 under an “and” makes the whole “and” 0, and the other branch of that “and” stops mattering, however large it is. A 1 under an “or” does the same to its sibling. A 1 under an “and” or a 0 under an “or” simply disappears. When the dust settles, the four leaves on $x_3$ and $x_4$ have taken the other branch of their half of the tree with them. What remains is $\neg(x_1 \oplus x_2)$ with four leaves.

Fixing half the letters removed three-quarters of the formula. A crude estimate would remove half, the leaves on the fixed letters themselves. The other quarter went because constants switch off their siblings. That multiplier — leaves lost beyond the ones on the fixed letters — is what the rest of this essay measures.

A restriction, at random #

The right way to make the mechanism quantitative is to fix letters at random — to choose a random face of the cube of a formula as a corner of a cube and look at the function on it. A random restriction with parameter $p$ leaves each letter free with chance $p$ and otherwise fixes it to 0 or 1 with equal chances, independently. Apply it to a function $f$ and to its smallest formula, and compare the smallest formula of what is left with the original.

For four letters the expectation can be computed exactly rather than sampled. Each letter is free, fixed to 0 or fixed to 1, so there are $3^4 = 81$ restrictions, each with a known probability. For each, the restricted function is a function of the free letters, and its smallest formula is in the table of all 65,536 sizes. One detail matters: a restriction that leaves a constant leaves a formula with no leaves at all, and the table is adjusted so that constants count as zero.

At $p = \tfrac12$, half the letters free on average, parity keeps $0.328$ of its formula, majority $0.270$, and the hardest functions $0.264$. At $p = \tfrac14$ the shares are $0.112$, $0.087$ and $0.086$. On logarithmic axes the curves are close to straight lines. Their slopes lie between $1.5$ and $2$ — far steeper than the slope of 1 that leaves on fixed letters alone would give.

Parity, where everything can be counted #

Parity is the case where the exact answer has a closed form. A restriction leaving $k$ letters free turns parity of four letters into parity of $k$ letters, or its negation, whose smallest formula has a known size: 0, 1, 4, 10 and 16 leaves for $k = 0$ to 4. The expected size is the average of those sizes over the binomial distribution of $k$, which the computation reproduces exactly.

The middle value is a small surprise in its own right. Khrapchenko’s bound gives $n^2 = 9$ leaves for parity of three letters, and the true smallest formula has 10. The bound is exact for two and four letters and off by one at three, because a formula’s leaves must be divided among an odd number of letters as evenly as a tree allows. For larger $n$ the parity of $n$ letters needs exactly $n^2$ leaves when $n$ is a power of two, and is known to need more for some other $n$, as it does at three. That difference is invisible to every argument in this essay, which all bound sizes only up to constants.

Since parity of $k$ letters needs about $k^2$ leaves and a restriction leaves about $pn$ letters free, parity’s formula shrinks by about $p^2$ in expectation. That is why parity is the natural test case. It shrinks by exactly the factor that the best possible shrinkage theorem allows, so no shrinkage argument can prove a better bound for parity than $n^2$. To go beyond $n^2$ the function has to be built more cleverly, and Andreev’s function, below, is that construction.

The exponent of every function #

The slope of a curve in the last figure is its shrinkage exponent — the $\Gamma$ for which the restricted size is about $p^\Gamma$ times the original. It can be read for every function of four letters at once.

The exponents average $1.90$. None is below $1.6$, and some are above 2. That last fact needs care, because Johan Håstad proved in 1998 that the shrinkage exponent of and–or–not formulas is exactly 2. His theorem is about the worst case as the number of letters grows: no family of formulas can shrink more slowly than $p^{2 - o(1)}$ times its size. Individual functions of four letters can shrink faster, because constants and small sizes dominate. Rounding to whole leaves makes a function of eight leaves that loses five look like an exponent well above 2. The figure is a measurement at a size where the asymptotic statement has not yet taken hold. Its message is only that shrinkage is strong everywhere, not that 2 is exceeded.

Subbotovskaya’s step #

The first shrinkage theorem, Bella Subbotovskaya’s of 1961, looks at one letter at a time. In any formula with $L$ leaves on $n$ letters, some letter appears at least $L/n$ times. Fix that letter well, and every leaf on it disappears. Moreover, each such leaf takes at least one more leaf with it, because its constant either decides its gate or vanishes, and the sibling subtree goes either way in at least half the cases. Averaged over the two values, fixing that letter removes at least a $3/(2n)$ share of the leaves. That gives a size after one fixing of at most $(1 - 1/n)^{3/2}$ times the original, to first order.

Every one of the functions in the figure obeys the step. Its best single fixing leaves at most $(3/4)^{3/2} \approx 0.65$ of its formula, and the worst case keeps exactly $0.625$, five leaves of eight. Iterating the step — fixing letters one at a time until a $p$ share remain — gives shrinkage like $p^{3/2}$. Applied to parity, which stays parity under every fixing, it gives Subbotovskaya’s lower bound. After fixing all but one letter, parity still needs one leaf, so it must have started with at least about $n^{3/2}$.

The argument wastes something, and the waste is what later work recovered. It credits each fixed leaf with removing only one sibling on average, while in a balanced formula a constant near the leaves often decides a whole chain of gates above it. Mike Paterson and Uri Zwick improved the exponent to $1.63$ in 1993 by tracking those chains. Håstad reached 2 by analysing what happens to a formula under many simultaneous fixings, controlling the rare cases where a formula fails to shrink.

Andreev’s function #

Shrinkage alone gives bounds for parity of at most $n^2$, since parity itself shrinks like $p^2$. Alexander Andreev saw in 1987 how to use shrinkage to prove more, by building a function that does not shrink as fast as its formulas must.

Split $n$ letters in two. The first half is a table: $2^k$ bits, with $2^k$ about $n/2$, describing an arbitrary function of $k$ inputs. The second half is split into $k$ blocks, each about $n/(2k)$ letters long, and each block’s parity supplies one input. The function’s value is the table’s entry at the address the parities spell out.

Now argue from the outside in. Choose the table to be a function of $k$ inputs that needs about $2^k/\log k$ leaves, which counting guarantees exists, so that fixing the table leaves a function that is hard because the table is. Then apply a random restriction to the block letters, with $p$ chosen so that each block keeps about one free letter. Each block’s parity is then still a free input, and the restricted function contains the hard table function of $k$ inputs, needing about $n/\log n$ leaves. By shrinkage, the formula before restriction must have been larger by a factor of about $p^{-\Gamma}$, and with $p$ about $k/n$ that factor is about $(n/\log n)^{\Gamma}$. The bound comes out as about $n^{1 + \Gamma}$: $n^{2.5}$ with Subbotovskaya’s $\Gamma = 3/2$, and $n^{3}$ with Håstad’s $\Gamma = 2$.

Sixty years of bounds #

Set side by side, the history of formula lower bounds for explicit functions is a history of shrinkage exponents.

Subbotovskaya’s $n^{1.5}$ for parity came from shrinkage $3/2$. Khrapchenko’s $n^2$ for parity, in 1971, came from a different argument, the edge-counting of the formula that cannot share. Everything after that was Andreev’s function fed a better exponent. Andreev’s own $n^{2.5}$ used Subbotovskaya’s $3/2$. Paterson and Zwick’s $n^{2.63}$ used their $1.63$. Håstad’s $n^{3 - o(1)}$ used his $2$. Avishay Tal sharpened the lower-order factors in 2014, to $n^3$ divided by logarithmic terms. Since 2 is the true shrinkage exponent, Andreev’s function cannot be pushed past $n^3$ by this route, and no explicit function is known to need formulas longer than about $n^3$.

The same tool against depth #

Random restrictions have a second famous use, and it came first. A circuit of constant depth — a fixed number of layers of and and or gates, each with any number of inputs — is a formula of a special shape, wide rather than deep. In 1981 Merrick Furst, James Saxe and Michael Sipser, and independently Miklós Ajtai, showed that such circuits cannot compute parity in polynomial size, by restricting at random. Håstad’s switching lemma of 1986 made the argument sharp. Under a random restriction, an “or” of small "and"s collapses with high probability into an “and” of small "or"s, so two adjacent layers of the circuit can be merged into one. Each restriction removes a layer, and after a few of them a constant-depth circuit has become a shallow decision tree. Parity, which stays parity on whatever letters are left free, cannot be one.

The two uses are cousins, and they share the reason they work. Parity is maximally sensitive — flipping any letter flips the output, the property half the cube and root n neighbours measured — so it survives restriction intact while circuits and formulas collapse. Against constant depth the collapse is exponential and the bound is exponential, $2^{n^{1/(d-1)}}$ for depth $d$. Against formulas the collapse is only polynomial, the factor $p^2$, and the bound is only polynomial. The difference between those two results is the difference between a wall that was broken in the 1980s and one that still stands.

Why $n^3$ is a wall and not a theorem #

The wall at $n^3$ is a limit of the method, not of the functions. Almost every function needs formulas of length about $2^n/\log n$, exponentially larger, and the functions in how many gates a truth table needs that can be computed by small circuits are widely believed to include some that need formulas of more than polynomial length. Proving that would separate two classes of computation — what can be done in parallel in very little time from what can be done efficiently in sequence — and is open, one of the separations that sit beside the question there is a relation such that described.

Shrinkage cannot get there because it is a statement about random restrictions, and any function computed by a formula of size $s$ shrinks to size about $s p^2$. To prove a bound of $n^4$, an argument would need a function that stays much harder than that under restrictions, and the obstacle is that random restrictions destroy too much structure. They make every known explicit function simple once few enough letters remain. Other methods — communication games, the Karchmer–Wigderson characterisation, rank arguments — have each given bounds for formulas, and each has its own barrier at or below $n^3$ for explicit functions.

What four letters can show #

The figures here are exact, and they are exact at a size where every asymptotic statement is distorted by constants. The shrinkage exponents of four-letter functions average $1.9$ and include values above 2, which only shows that small formulas shrink in jumps. Subbotovskaya’s step is checked exactly, and it holds with room to spare. Håstad’s exponent 2 cannot be seen at four letters at all, since it is a statement about the limit. And Andreev’s construction is drawn rather than computed, because its smallest interesting case needs far more letters than the table of all functions reaches.

Still open: formulas longer than the cube #

No explicit function is known to need formulas of length $n^{3 + \epsilon}$ for any $\epsilon > 0$. The cubic barrier has stood since 1998 in essentially the same form. The Karchmer–Raz–Wigderson conjecture proposes a route beyond it: that composing functions multiplies their formula complexities, as composing parity with a hard table does in Andreev’s argument. A proof would give super-polynomial formula lower bounds for a function computable in polynomial time. Partial results confirm the conjecture for special kinds of composition and leave the general case open.

A second question is closer to this essay. For formulas over the full binary basis — allowing exclusive-or gates as well as and and or — the shrinkage exponent is 1, since parity costs only $n$ leaves there. The best lower bound for an explicit function is about $n^2/\log n$, by an older counting argument of Èduard Nechiporuk. Whether anything better than that can be proved over that basis is open, and no shrinkage argument can help, because there is no shrinkage to use.

Leaves that take their siblings with them #

A formula is a tree, and fixing a letter turns its leaves into constants that switch off whole branches. That simple observation, made quantitative, is shrinkage. A random restriction leaving a $p$ share of letters free leaves about a $p^2$ share of a formula. The exponent 2 is exact, and every function of four letters already shrinks faster than $p^{3/2}$. Fed into Andreev’s construction of a table addressed by parities, shrinkage $\Gamma$ gives lower bounds of $n^{1 + \Gamma}$, which is where the best bound for any explicit function has stood since 1998. The barrier is the exponent itself: formulas cannot be shown to be larger than $n^3$ by an argument whose only tool is that they shrink like $p^2$.