Election and debate special from GLL—note update

Aram Harrow is both a computer scientist and a physicist—something that makes him unique and special. Few people can explain what a probabilistic Turing Machine is and also what complementarity is. He has done some beautiful work in pure and applied mathematics, work that uses his dual abilities.

Today Dick and I wish to describe and interpret an intricate recent theorem of his in a joint paper with Alexandra Kolla and Leonard Schulman.

Aram is no stranger to these pages. Of course he has also been our honored participant in our year-long debate on the feasibility of building quantum computers, all during his current appointment in the Computer Science and Engineering department of the University of Washington in Seattle. He is also one of three mainstays on the prominent quantum computing blog created by Dave Bacon, and during our debate still managed to get a little bit of other work done. In January he will join the MIT Department of Physics as an assistant professor, and we congratulate him on that.

As related at the bottom of his post, the paper grew out of work on the unique games conjecture, seeking to apply quantum methods though the end result was “classical.” The impetus included models of physical noise, such as featured in Aram’s debate with Gil Kalai. To bring this full circle, Gil himself is the first person credited for discussions that spurred the paper, but these were in 2010 long before the debate idea arose, and not with Aram.

The Proof

Usually we discuss the paper first, or at least state its main results, but exceptional times demand exceptions. Their “Proof overview” subsection begins by defining a “senate operator,” based on the idea that in the U.S. Senate, states have equal weight regardless of population. Relaxing equal-weighting will lead to our main open problem. The Section~3 title summarizes their pivotal Proposition~2 as “senates dominate dictatorships.” A main ingredient of their proof are the Krawtchouk Polynomials, whose Internet page talks about “the destiny of the scientist during the Great Terror.”

Our interdisciplinary push seems to have entered Politics, but the real point is: the proof is hard. So hard that the authors tell me they have no idea of the value of the constant whose existence constitutes their main theorem. We will still try to give some idea of its significance, and why the result is hard, and how you can approach the issues without having to delve into the whole party manifesto. But you will not be able to make like President Gerald Ford in his first debate (parody) with Jimmy Carter in 1976:

“It was my understanding that there would be no math in this debate.”

The Paper

The paper’s title, “Dimension-free L2 maximal inequality for spherical means in the hypercube,” may not generate any 15-second sound bites. Nor may it help predict the outcome of the U.S. Presidential election, but it does contain an important new theorem.

Let’s first say why this theorem is significant and hard. The term “hypercube” is just the set of binary strings of length —one of the favorite objects for computer scientists. In this world, the sphere of radius around a point , written , is the set of strings that are Hamming distance from . Thus, if and the points in the sphere are:

Now imagine we select a small fraction of the points from the hypercube, say . Can one find a single point that is special, in that every sphere around of any radius has less than half of its points in the selected set? Clearly, this seems quite reasonable, if is small enough.

This is a case where the intuition is correct, but proving it is hard. A standard method of proving that special points exist is to pick at random, essentially using the probabilistic method. Alas this works for spheres of one radius, or a few radii, but does not seem to be powerful enough to show that the point works for all radii.

The probabilistic method is extremely powerful, but when it fails, often the requirements for a proof become very difficult. This is the case with their new result. Actually in our opinion this is one of the most important aspects of the new paper. Since the probabilistic method does not always work, any new ideas that can solve problems where it fails are automatically of great importance. Here one idea that Aram tells me was important is a different kind of “complementarity,” namely that where is the vertex opposite in the hypercube.

Let’s turn now to state the theorem in a mathematically precise manner and probe its reach.

The Result

The new inequality involves the standard norm of a function , which is defined by

The other functions involved maximize the average of over the spheres:

The key clause in the paper’s title is that the bound given by their inequality does not depend on . Here is their new result:

Theorem 1 There exists such that for all and ,

Pretty neat, no? Well it’s neat, but it can use some interpretation.

Speaking mathematically, call “light” if is below the average of the squares, i.e., . We might hope to “bulk up” by finding an average over one of the spheres enclosing that is greater. For many ‘s there will be some ‘s for which this makes a big difference. However, the theorem shows that under norms the cumulative effect of this extra allowance will never be more than a fixed constant factor—independent of the dimension. That’s fine, but can we give a more helpfully vivid interpretation?

An Election Interpretation

It is election season in the United States again. One hears often about how demographic and personal characteristics channel one’s political preferences, and that there are “typical Democratic voters” and “typical Republican voters.” The categories are often binary or close to it: male/female, married/single, urban/suburban-or-rural, over/under age 50, and so on.

We can define them by positions on single issues: pro-life/pro-choice, gun-rights/gun-control, for/against gay marriage, immigration amnesty, anything like that. We can also add categories that seem irrelevant: righthanded/lefthanded, dark/light eyes or hair, tall/short, nearsighted/not, Coke/Pepsi. We can even include divisions that are not roughly balanced in the population, such as vegetarian/carnivore. Hence also we can break multi-way categories into binary pairs, such as X/not-X for every ethnic group X. Then the possible combinations of values of characteristics correspond to the vertices of the -dimensional hypercube.

What justifies saying that a combination of characteristics is “typical” for a party is that if you vary some of them—any number of them—you still find mostly people who vote for that party. Importantly this should be true for changing any set of characteristics, not just specific ones. Given the strength of this requirement, do typical voters exist? The fact of single-issue voting may even make this seem unlikely. However, the following broad statement holds in enough cases to give a way to approach the issues in their paper:

Theorem 2
If a party wins by a large enough landslide, then it has typical voters.

That is, there are voters such that not only did vote for the winner, but for any , over all voters who differ from in characteristics, the winner got a majority of votes from those as well. Well this comes with some caveats, so we need to look closer.

The One-Vertex, One-Vote Case

Let us first suppose that every combination has exactly one voter. Let be the set of nodes that vote for the loser. Then we define an indicator function by:

Now if the loser won an portion of the vote, then since , we have:

By the theorem applied to , squaring both sides,

Dividing by makes the left side an average such that . There must exist some giving at most the average value, i.e. such that , which implies that for all ,

Taking small enough that makes for all . Thus the loser achieves no more than a minority over all of the spheres centered on . This carries over to all of the Hamming balls , which include their interiors, as well.

This makes a typical voter. By extending the averaging argument, one can show there are many typical voters. Thus when the election map is close to all-red or all-blue, there are many places where the same color prevails in all concentric spheres. However, things become trickier when we vary the requirements on the space.

Weighted Measures

Now suppose we have a weighted measure on the hypercube. With regard to this measure,

It also now makes sense to define weighted versions of the averages over the Hamming spheres, leading to the operator

Does their theorem now hold in the form that there exists such that for all , ? Expanded, this now means:

Theorem? We ask whether for all , all counting measures on , and all , there exists (possibly depending on or on ) such that

Update 10/9/12: With no dependence on , or restriction on values , this has been refuted—see Addendum below.

We can also define the modified max-averaging operator with regard to the balls rather than the spheres , and ask the same question. The paper does not address such matters directly, and we understand from private communication with the authors that they have not arrived there yet, because seemingly simpler cases are unresolved. If it were true, then we could derive the existence of “typical voters” in the most general setting.

To see how, assume that the -many voters who share the same characteristics all vote the same way. (If this is not true, we can create some new characteristics that separate them, and are free to add them as a co-ordinates to every vector because the count is allowed to be anything including zero.) Let again be the set of that vote for the loser. Then is the total number of votes for , out of a total electorate of . Define to be the 0-1 valued indicator function of as before. Then

while

The “Theorem?” and dividing both sides by yield

Again an averaging argument with respect to yields the existence of such that for all ,

Here the right-hand side has where is the loser’s percentage of the total vote, and a large enough victory makes . This implies that the loser still has a minority in every Hamming sphere centered on the voter .

Can We Use the Inequality They Proved?

We can try to work instead with the function

Then we obtain

while (using the original maximizing operator again)

In general this does not look very tractable, nor does the proved theorem seem either to imply or follow from the “Theorem?” above.

In our specific election case, we might try

Then , and the theorem they proved gives

The averaging argument, however, is still in terms of not as just above, so we get the existence of an such that for all ,

Neither side of this inequality yields the desired interpretation. The Cauchy-Schwarz inequality can relate the numerator to , but the inequality goes in the wrong direction for our purpose. This hints how tricky the considerations in the paper are.

The problem appears to be mainly the “white space” caused on the map when . We can argue that this still should see good behavior as a limiting case of always being positive but fractional (where we can also stipulate that ) and letting it tend to zero for some .

Resolving this, however, may entail solving some easier problems that Aram and the others have attempted, such as for spaces formed by Cartesian products of other graphs (besides the -fold product of 2-cliques giving the hypercube). Moreover their type of inequality is open even for , and for other norms including the -norm. An -norm inequality ostensibly would help our desired election conclusions, but one of their key propositions does not extend to it, at least not conveniently as they remark. As always we refer interested readers to the paper for full details and further questions.

Addendum

Aram contributes a counterexample to the unrestricted “Theorem?”, to some restricted versions and also with balls in place of spheres, and to the existence of “typical voters” in the weighted case with regard to spheres. Namely, let there be only voters, with the origin voting for the loser , i.e. , and her neighbors voting for the winner ( everywhere else). Then

because the neighbors see only the origin at distance 1. Thus there is no inequality with a constant independent of . Moreover, none of the winning voters is typical, again because its sphere at distance 1 has only the origin, while even the ball with radius 1 leaves a tied 1-1 result.

However, the weight-2 nodes such as still have the loser in a minority of all properly enclosing balls, so they are “typical combinations” even with there. Perhaps the most relevant cases are where for all and , and for balls not spheres—though Hamming balls lack the “complementarity” property mentioned near the top.

Open Problems

For what other norms and spaces does their inequality hold?

Does their inequality hold under weighted counting measures on , with reasonable restrictions on and perhaps using balls not spheres? Can we obtain the special case of “typical voters” from the inequality they have without the one-vertex, one-vote restriction, or under milder added assumptions? Can we prove it if and ?

Will math matter to the upcoming Presidential debates?

[Changed to distinguish “ball” from “sphere” consistently, added note on partial refutation of weighted case.]