The formula that cannot share

How many gates a truth table needs measured a function by the fewest gates that compute it, and drew the line between circuits and formulas in one paragraph. A circuit may send the output of a gate to as many later gates as it likes. A formula may not: it is written as a tree, every intermediate result feeds exactly one operation, and a value needed twice must be written out twice. The size of a formula is the number of letters in it, counting $a$ and $\neg a$ alike, and the connectives are “and”, “or” and “not” — enough between them to build every function, as one connective is enough showed of smaller sets still — with the negations pushed down onto the letters.

The difference between the two measures is the subject of this essay, and parity is the function that shows it. Parity is true when an odd number of its letters are true. As a circuit with exclusive-or gates it is a chain of $n - 1$ of them, and even without exclusive-or it needs only $3(n-1)$ gates of and, or and not. As a formula it needs about $n^2$ letters, and the proof of that, by Valeriy Khrapchenko in 1971, is a count of edges on the cube that a formula is a corner of a cube drew for every function.

Every edge of the cube is a disagreement #

Each corner of the cube is an assignment of true and false to the letters, and two corners are joined by an edge when they differ in exactly one letter. A function colours the corners true and false, and an edge whose two ends get different colours is a place where changing one letter changes the answer. Parity is the function in which every edge is of that kind: changing any letter changes the count of true letters by one, and so flips its parity. On the three-letter cube all twelve edges cross between true and false, and a walk that changes one thing at a time alternates between odd and even at every step for the same reason.

Majority, true when at least two of three letters are true, is much calmer; it is the simplest of the weighted votes that a plane through the cube separates with a single cut. Only six of its edges cross, the ones between the corners with one true letter and those with two. Khrapchenko’s theorem turns the count into a bound. Let $A$ be the true corners, $B$ the false ones and $E$ the crossing edges. Then every formula for the function has at least

$$\frac{|E|^2}{|A|\cdot|B|}$$

letters. For parity of three letters that is $12^2/(4\cdot4) = 9$; for majority $6^2/(4 \cdot 4) = 2.25$. And for parity of $n$ letters, with $2^{n-1}$ corners on each side and every one of the $n \cdot 2^{n-1}$ edges crossing, it is exactly $n^2$.

The theorem does not need all the corners. $A$ may be any set of true corners and $B$ any set of false ones, and the bound holds for each choice, so the best bound for a function is the largest quotient over all choices. For parity the full sets are already best. For majority they are not: keep only the three corners with two true letters and the three with one, and the six crossing edges give $6^2/(3 \cdot 3) = 4$, against the true shortest formula of five letters. The figure’s captions give both numbers.

Why counting edges bounds a formula #

The proof runs a pair of corners down the formula’s tree. Take a true corner $a$ and a false corner $b$. At the top, the formula is true at $a$ and false at $b$. If the top connective is “and”, then both of its parts are true at $a$, and at least one is false at $b$, so that part separates them as the whole did; if it is “or”, at least one part is true at $a$ and both are false at $b$, so again some part separates them. Following a separating part at each step leads down to a single letter, at a leaf, that is true at $a$ and false at $b$ — and a letter can only do that if $a$ and $b$ disagree on it. When $a$ and $b$ are the two ends of a crossing edge they disagree on exactly one letter, so the leaf the walk reaches is a copy of that letter.

The rest is arithmetic. Divide the crossing edges among the leaves where their walks end. A single leaf can receive at most as many edges as the smaller of the sets of true and false corners whose walks reach it, because each corner has only one neighbour across the leaf’s letter. That makes the quotient at most 1 at every leaf. And the quotient can only shrink when pairs of sets are combined, because of the inequality

$$\frac{(x_1 + x_2)^2}{a_1 + a_2} \le \frac{x_1^2}{a_1} + \frac{x_2^2}{a_2},$$

which is the Cauchy–Schwarz inequality in its simplest form. So the quotient for the whole function is at most the sum of the quotients at the leaves, at most 1 each, and the number of leaves is at least the quotient. That is the whole proof: a formula’s tree splits the crossing edges into pieces, no piece can hold much, and a function with many crossing edges needs many pieces.

The argument uses the tree in an essential way. A circuit’s gates can be shared, so the walk from $a$ and $b$ may pass through the same gate on behalf of many different pairs, and nothing stops a few gates from carrying every edge. A formula gives each leaf its own pairs and charges for every one.

The proof is a conversation #

The walk down the tree has a second reading that turned it into a tool. Imagine two people, one holding the true corner $a$ and the other the false corner $b$, who want to find a letter on which their corners differ while exchanging as few bits as possible. A formula gives them a way: start at the root, and at each “and” the holder of $b$ announces which part is false at $b$ — one bit — while at each “or” the holder of $a$ announces which part is true at $a$. When they reach a leaf, its letter is one on which they differ. The number of leaves is the number of different conversations, and the depth of the tree is the number of bits.

Mauricio Karchmer and Avi Wigderson showed in 1988 that this is exact in both directions: the shortest formula depth of a function equals the fewest bits of such a conversation in the worst case, and formula size equals the fewest distinct conversations. Khrapchenko’s bound becomes a statement about conversations: a protocol that must name a differing letter for every crossing edge of the cube needs many different endings when the crossing edges are many and spread evenly, and parity spreads them as evenly as the cube allows. The reformulation is why later lower bounds for formulas are often proved as lower bounds for communication, where the tools are different and sometimes stronger.

It also shows why sharing is the issue. A conversation cannot be reused: each pair of corners follows its own path, and two pairs that end at the same letter must still have been told apart along the way, which is the tree’s insistence that each part be written separately wherever it is used. A circuit corresponds to nothing so simple, and no comparable reformulation of circuit size is known.

Every function of three letters, measured #

The bound is a lower bound; how good it is can be checked by finding the shortest formula for every function. For three letters there are 256 functions, and the shortest formulas can be found by building upward: the six letters and their negations are the formulas of size one, and a formula of size $k$ is an “and” or an “or” of formulas of sizes $i$ and $k - i$. Building every size in turn until every function has appeared gives each its exact length.

Parity is the hardest function of three letters, and it is alone there with its negation: ten letters, against nine for Khrapchenko’s bound. The distribution has a structure that has nothing to do with the bound — no function needs exactly seven letters or exactly nine — and the parity functions stand one step above everything else. That matches the circuit picture in reverse: the hardest functions for circuits of three letters were majority and its relatives, while parity needed only two gates with exclusive-or available. Which function is hardest depends on whether results can be reused.

Every function of four letters, measured #

The same search runs for four letters, where there are 65,536 functions, and finishes in under a second.

No function of four letters needs more than sixteen letters, and parity needs exactly sixteen, which is Khrapchenko’s $n^2$ met with equality. Parity is not alone at the top this time — 114 functions need sixteen letters — but it is the one for which the bound proves it, since the bound for the other 112 is lower. The most common lengths are eight to ten letters, and the counts near the top do not tail off smoothly: 960 functions need thirteen letters, 1,472 fourteen, 96 fifteen and 114 sixteen.

The scatter uses the bound in its plain form, with all the true and all the false corners, and it is the honest picture of that form. It is never wrong — every function’s true length is at least its bound — and it is almost never right: of the 65,534 functions it is exact for only seventy. For most functions the true length is about twice the bound or more. The bound is sharp for parity because parity is the function the argument was built around, the one in which every edge of the cube crosses and every leaf of the formula carries as many edges as a leaf can.

Sixteen letters, written out #

The formula that meets the bound for four letters is the natural one, and its shape explains the square.

Exclusive-or of two things written in and, or and not is $(P \wedge \neg Q) \vee (\neg P \wedge Q)$. Each of $P$ and $Q$ appears twice, once plain and once negated. For two letters that costs four letters. For four, take $P = a \oplus b$ and $Q = c \oplus d$, each four letters, and each appears twice, which is sixteen; the negated copies cost the same as the plain ones, since pushing a “not” down through a formula swaps “and” with “or” and changes no letter count.

So each level of the tree doubles the cost of the level below and the number of levels is $\log_2 n$; doubling $\log_2 n$ times a cost of $n$ gives $n \cdot n$. A circuit would compute $a \oplus b$ once and send it both to the place that needs it and to a “not” gate, which is exactly the reuse a formula forbids. The square is the price of writing a shared value out in full at every place it is used.

The bound and the construction, as n grows #

The construction works for any $n$: split the letters into two groups, build parity of each and its negation, and combine. The cost is twice the sum of the two halves’ costs, and the best split gives 4, 10, 16, 28, 40, 52, 64 letters for two to eight letters. At powers of two it is exactly $n^2$, and between them it is a little more. For three letters the construction’s 10 is the true minimum, as the exhaustive search showed; for five letters it gives 28 against a lower bound of 25, and the exact value for five letters cannot be settled by the search that finished four, since the number of functions rises from 65,536 to more than four billion.

The circuit line at the bottom is the comparison that matters. Both curves describe the same function; one grows as a line and the other as a square, and the whole difference is the permission to reuse. For parity the square is the end of the story, because the upper and lower bounds meet. For other functions the gap between formulas and circuits could be much larger, and nobody has proved it is for any explicit function.

A method that cannot prove more than the square #

Khrapchenko’s bound is also a ceiling on itself.

Each corner of the cube has $n$ edges, so the number of crossing edges is at most $n$ times the smaller of $|A|$ and $|B|$, and the quotient $|E|^2/(|A||B|)$ is at most $n^2 \cdot \min/\max \le n^2$. Parity attains the maximum, and so the method that proves parity’s formulas quadratic can never prove more than quadratic for any function at all. Applied with all of majority’s corners it proves only about two-thirds of $n$; restricted to the two middle levels, where every corner has about half its edges crossing, it proves about $n^2/4$, which is the best this method can do for majority, and majority’s shortest formulas are believed to be considerably longer. For “all true” the plain form proves nothing, since there is one true corner against almost all the rest; the single true corner against its $n$ neighbours proves $n$, which is right, since a formula must mention every letter it depends on. Choosing the sets well is the craft of using the bound, and the ceiling applies to every choice.

That ceiling is the shape of lower bounds in this subject. A method strong enough to prove one function hard turns out, on inspection, to have a maximum it cannot pass, set by the same combinatorics that made it work. A cube half chosen and the neighbours it forces met the same phenomenon in sensitivity, where counting a function’s crossing edges at each corner is one of a family of measures that are all polynomially related and all stop well short of what one would like to prove.

Beyond the square #

Better bounds for formulas exist, for other functions. Alexander Andreev constructed in 1987 a function that needs about $n^{2.5}$ letters, and a series of improvements culminating in Johan Håstad’s work in 1998 and Avishay Tal’s in 2014 pushed the exponent for Andreev’s function to 3, up to factors of logarithms. The method is different: it hits a formula with random restrictions — fixing most letters to random values — and shows that a formula shrinks under them much faster than the function it computes, so a function that stays complicated under restriction must have started with a long formula.

The construction of the map that puts neighbours side by side measures something else again: two-level formulas, an “or” of "and"s, in which parity needs $2^{n-1}$ terms, one for each true corner, because no two of its true corners are neighbours and so no rectangle covers more than one. Two levels cost exponentially, any number of levels costs $n^2$, and a circuit costs $n$. Each relaxation of the form removes a cost, and each cost is exactly what the previous form could not share.

What the searches do not show #

The exhaustive searches are complete for three and four letters and say nothing directly about five. They also measure only the and-or-not basis. With exclusive-or allowed as a connective in formulas, parity becomes a formula of $n$ letters and the question changes completely; Khrapchenko’s argument is specific to bases in which a single connective cannot flip its answer on every edge.

The bound counts letters, not connectives or depth. A formula with $n^2$ letters has $n^2 - 1$ binary connectives, so the two counts agree to one, but depth is a different measure, and the relation between formula size and depth — every formula can be rebalanced to logarithmic depth without much growth — is a separate theorem with its own constants.

Still open: a formula longer than the cube #

No explicit function is known to need formulas longer than about $n^3$ letters in and, or and not. The counting argument says that almost every function needs formulas of length about $2^n/\log_2 n$, and functions computable by short circuits are widely believed to include ones that need formulas longer than any polynomial — which would separate the computations that can be done in parallel in very little time from those that can be done efficiently in sequence — but the best proven bound for any function anyone can name stops near the cube. Pushing it further is the subject of a programme built on combining functions so that their formula sizes multiply, proposed by Mauricio Karchmer, Ran Raz and Avi Wigderson in 1995; whether that composition always multiplies is open.

At the small end the questions are concrete and close to the figures above. The exact formula size of parity is known for every power of two, where the construction meets Khrapchenko’s bound, and the search here settles three letters; between powers of two the construction gives 28, 40 and 52 letters for five, six and seven, and the general exact answer between powers of two rests on arguments specific to parity rather than on any search, since the space of formulas outruns enumeration one letter beyond where it succeeds here. And the largest formula size needed by any function of five letters — the analogue of the sixteen that the figure found for four — is not known, for the same reason, although the question is entirely finite.