A plane through the cube

A formula about three letters is a set of corners of a cube: the assignments that make it true. A handful of connectives can build every such set, and a map that puts neighbours side by side finds short formulas by covering the true corners with rectangles. Those are questions about how to write a function. A different question asks what kind of shape its true corners make, and the simplest shapes are those that can be sliced off the cube by a single flat cut.

A function is a weighted vote — a threshold function — when there are numbers $w_1, w_2, \ldots$ and a threshold $t$ such that the function is true exactly when the weights of the true letters add to more than $t$. Majority of three letters is one: weights 1, 1, 1 and threshold 1.5. “All three” is one, with threshold 2.5. “At least one” is one, with threshold 0.5.

The picture sorts the eight corners by their weighted total. For majority the corners with total 2 or 3 are the true ones, and a cut at 1.5 separates them from the corners with total 0 or 1. For “$p$, or both $q$ and $r$”, weights 2, 1, 1 do the same job: $p$ alone reaches 2, $q$ and $r$ together reach 2, and nothing else does. For parity — true when an odd number of the letters are true — the true and false corners alternate along the line, and no choice of weights makes them stop alternating.

A plane, seen from the cube #

The weighted total is a linear function of the corner’s coordinates, and the set where it equals the threshold is a plane. So a threshold function is one whose true corners lie strictly on one side of some plane and whose false corners lie on the other: the cube is cut in two by a flat slice, and the function is the side.

Majority’s true corners are the four at the top of the cube when it is stood on the corner $000$: the corner $111$ and its three neighbours. A plane perpendicular to the long diagonal, halfway up, cuts them off. Any function whose true corners can be sliced away like that — a cap of the cube, however tilted — is a weighted vote, and the weights are the direction the plane faces.

The geometric view makes some facts immediate. A threshold function is monotone in each letter’s direction: if a letter has positive weight, switching it from false to true can only move the total up and so can only turn the function from false to true, never the reverse. So any function that goes both ways in one letter depending on the others — exclusive-or, equivalence, parity — is not a threshold function. The converse fails: there are functions monotone in every letter that are still not weighted votes — “both $p$ and $q$, or both $r$ and $s$” is the smallest — because their true corners, though closed upwards, do not lie on one side of any plane. The functions that are closed upwards are counted by Dedekind’s numbers, the count of the antichains of the cube’s order, and the weighted votes are a small part of them.

Why exclusive-or cannot be cut #

Exclusive-or of two letters is true at $01$ and $10$ and false at $00$ and $11$. On the square of assignments the true corners are a diagonal pair.

A line cutting the square with $01$ and $10$ on one side and $00$ and $11$ on the other would put the midpoint of each diagonal on the corresponding side — but the two diagonals share their midpoint. That is the whole proof. In weights it reads: $f(00) = 0$ needs $0 \le t$; $f(01) = f(10) = 1$ needs $w_1 > t$ and $w_2 > t$; and $f(11) = 0$ needs $w_1 + w_2 \le t$. Adding the middle two gives $w_1 + w_2 > 2t \ge t$, contradicting the last. Four inequalities, no solution.

The argument uses nothing about the particular numbers: whatever weights are proposed, the two true corners together outweigh the threshold twice over while the corner with both letters true must stay below it once, and a sum cannot be both. Parity of three letters fails for the same reason on every face of the cube, and parity of any number of letters is as far from a weighted vote as a function can be. Every pair of neighbouring corners has one true and one false, so any plane that tried to separate them would have to cut every edge of the cube.

A certificate that no plane exists #

The four-inequality argument is more general than it looks. Deciding whether a function is a weighted vote is deciding whether a system of linear inequalities in the weights and the threshold has a solution — one inequality per corner of the cube — and that is a linear program. Linear programming duality says that when such a system has no solution, there is a short proof of that fact: a combination of the inequalities, with non-negative multipliers, that adds up to something false.

For exclusive-or the certificate is the one given above: add the two inequalities for the true corners and compare with the two for the false ones. For parity of three letters there is a similar certificate using all eight corners, adding the inequalities for the four true corners and the four false corners and finding that the weighted totals must balance exactly, while the inequalities demand a strict gap. Every function that is not a weighted vote has such a certificate, a list of corners whose averages coincide on the two sides — in geometric language, the convex hulls of the true and false corners overlap, and the certificate is a point in both.

That turns an impossibility into a picture. A function is a weighted vote exactly when the smallest convex shape containing its true corners does not meet the smallest convex shape containing its false corners. For exclusive-or the two shapes are the two diagonals of the square, and they cross at the centre.

How many functions are weighted votes #

On three letters there are 256 functions and the search finds 104 threshold functions among them. On four there are 65,536, and the count falls to 1,882.

The search is simple. Whole-number weights are enough — a separating plane can be tilted slightly to have rational coefficients and then scaled — so the search tries every choice of weights from $-W$ to $W$ for each letter, every threshold between consecutive totals, and records the function each produces. As $W$ grows the count of distinct functions grows and then stops: on four letters it reaches 1,882 at $W = 3$ and does not move at 4 or 5. That the count has stopped is evidence, not proof, that none are missing, and here the number agrees with the one found by other methods: 1,882, followed by 94,572 on five letters and 15,028,134 on six.

The fraction collapses because the two counts grow at different rates. There are $2^{2^n}$ functions of $n$ letters, a doubly exponential number. A threshold function is fixed by a plane, and a plane through the cube is essentially fixed by which $n$ of the $2^n$ corners it touches, so the number of threshold functions is at most about $2^{n^2}$. Yuri Zuev showed in 1989 that this is the right order: the logarithm of the count grows like $n^2$. Almost no function is a weighted vote.

One neuron #

The threshold function is older than its name. Warren McCulloch and Walter Pitts proposed in 1943 that a neuron could be modelled as a unit that fires when the weighted sum of its inputs passes a threshold, and showed that networks of such units can compute any truth function. A single unit computes exactly the threshold functions.

Frank Rosenblatt’s perceptron of 1958 added learning: start with arbitrary weights, show the unit an example, and if it answers wrongly, nudge each weight towards the right answer — up for a letter that was true if the answer should have been yes, down if it should have been no.

On majority the mistakes fall to zero within four passes, and the weights it settles on are a weighted vote for majority. On parity the mistakes never fall below four. The perceptron convergence theorem, proved by Albert Novikoff in 1962, says that whenever weights exist the rule finds some in a bounded number of mistakes; when they do not exist, the rule cycles for ever, and there is nothing to converge to.

Marvin Minsky and Seymour Papert’s book Perceptrons of 1969 made that limitation famous, with exclusive-or and parity as the standard examples of what a single unit cannot compute. Its influence on the funding of neural networks was large and is still argued about. The mathematics is the square with its two diagonals. The later remedy — a second layer of units, whose inputs are the outputs of the first — is exactly the observation that exclusive-or is an “or” of two weighted votes, “$p$ and not $q$” and “$q$ and not $p$”, and that any truth function is an “or” of weighted votes cutting off one true corner each.

Weighted votes in committees #

Every weighted voting rule in a committee is a threshold function. The members are the letters, each member’s vote is the letter’s truth value, their weights are the votes they carry, and the motion passes when the weighted total reaches the quota. The Council of the European Union, the electoral college, a shareholders’ meeting: each is a threshold function of its members’ votes.

The functions have a property that the weights hide. Two different sets of weights can give the same function, and the function — not the weights — is what decides outcomes. (It is also why no weighted rule escapes the conditions that no voting rule can meet together when more than two options are on the table: a threshold function decides yes-or-no questions, and the trouble begins with three.) In a committee with weights 3, 3, 3 and 1 and a quota of 6, the member with weight 1 can never change the outcome, since every coalition that passes with it passes without it: the committee is the same function as three members of weight 3 alone, and its fourth member holds a tenth of the votes and none of the power. The share of the votes is not the share of the power, and the reason is that the function throws most of the information in the weights away.

The theory of threshold functions and the theory of weighted voting games grew up separately and ask the same questions: which functions are weighted votes, how small the weights can be made, and when two weightings are the same rule. Chow’s parameters, below, have a direct reading in the second theory: they are counts of the winning coalitions each member belongs to, close relatives of the power indices a voting theorist would compute.

What makes a function one plane away #

The threshold functions are the simplest shapes on the cube, and there is a remarkable fact about how little is needed to recognise one. C. K. Chow proved in 1961 that a threshold function is determined, among all functions, by $n + 1$ numbers: how many corners it makes true, and for each letter, how many of those true corners have that letter true.

Those are the Chow parameters, and the theorem says that if a threshold function and any other function share them, the two are the same function. For majority of three letters they are four true corners, with each letter true in three of them. No other function of three letters has those counts. The proof is a short argument about the plane: two different functions with the same counts would have their disagreements balanced on both sides of the plane, which is impossible when one of them is the side of the plane.

The theorem gives a summary of a threshold function that is linear in the number of letters rather than exponential, and it is the starting point of the modern theory of learning such functions from examples. What it does not give is a fast way to find the weights from the Chow parameters, which is a harder problem and was only recently shown to be solvable efficiently to good approximation.

Nor does anything guarantee that the weights are small. On four letters every weighted vote can be written with weights no larger than 3, but the bound grows fast: Johan Håstad showed in 1994 that some threshold functions of $n$ letters need weights as large as roughly $n^{n/2}/2^n$, matching an upper bound Saburo Muroga had found decades earlier. A function simple enough to be a single plane can still need numbers with $n \log n$ digits to describe that plane, which is one of the ways threshold circuits are subtler than their definition.

What the figures cannot show #

The weighted-sum figure places each corner by one choice of weights, and for parity by the plain count. That the true and false corners alternate for those weights is visible; that they alternate for every choice is the four-inequality argument, and the figure’s own check is the search, which finds no weights for parity among the ones it tries. The two drawings of cubes place the corners in a fixed perspective, and the separating plane for majority is described in the caption rather than drawn, since a plane through a cube drawn in two dimensions is a polygon whose shape depends on the viewpoint more than on the function.

The counts come from a search over integer weights bounded by 3, stopped when enlarging the bound adds nothing. That is not a proof that the list is complete; the proof that bounded integer weights suffice for four letters, and the independent counts that agree with 1,882, come from the literature on threshold logic.

And the perceptron figure is one run from one start, with the examples in one order. The convergence theorem is about every order and every start; the figure shows one trajectory settling and one cycling, which is what the theorem predicts and not a demonstration of it.

The question it leaves: how sensitive a function can be #

A weighted vote changes its answer only when the total crosses the threshold, and near most corners the total is far from it. So a weighted vote is, at most corners, insensitive to changing any one letter. Parity is the opposite: at every corner, changing any letter changes the answer.

How many of a corner’s neighbours disagree with it — the function’s sensitivity there — turns out to measure something much deeper than the shape of its true set. For thirty years it was conjectured that sensitivity controls every other measure of a function’s complexity, and the conjecture was proved in 2019 by an argument about the cube that fits on two pages. That argument is the subject of half the cube and $\sqrt n$ neighbours.

The two properties pull in opposite directions. The weighted votes are the functions that change their answer on only a thin band of corners near the cut, and parity, the function no plane can describe, is the one that changes its answer across every edge. A measure of how much a function changes across edges is therefore a measure, of a sort, of how far it is from being a single cut.

One cut #

A weighted vote is the simplest thing a function of true and false letters can be: a single flat cut through the cube of assignments, with the function the side of the cut a corner lands on. Majority is one, “all” and “any” are ones, and a rule that counts one letter double is one. Exclusive-or is not, and the reason is that the two diagonals of a square cross.

Of the 65,536 functions of four letters, 1,882 are cuts; of the functions of many letters, almost none. That scarcity is why one neuron computes so little, and why two layers of neurons compute everything: any set of true corners can be assembled from caps, each cut off by one plane. The cube does not care which description is used. The functions that one plane can describe are a thin and structured family, and the rest need more planes than one.

How many planes a function needs is itself a measure of its complexity — the number of units in the smallest network of weighted votes computing it — and for most functions it is large. Parity of $n$ letters needs about $n$ units in two layers, and there are functions needing exponentially many. Between the single cut and the exponential tangle lies the whole theory of threshold circuits, and it begins with the two diagonals of a square.