# Polynomial Hirsch Conjecture 5: Abstractions and Counterexamples.

This is the 5th research thread of polymath3 studying the polynomial Hirsch conjecture. As you may remember, we are mainly interested in an abstract form of the problem about families of sets. (And a related version about families of multisets.)

The 4th research thread was, in my opinion, fruitful. An interesting further abstraction was offered and for this abstraction a counterexample was found. I will review these developments below.

There are several reasons why the positive direction is more tempting than the negative one. (And as usual, it does not make much of a difference which direction you study. The practices for trying to prove a statement and trying to disprove it are quite similar.) But perhaps we should try to make also some more pointed attempts towards counterexamples?

Over the years, I devoted much effort including a few desperate attempts to try to come up with counterexamples. (For a slightly less abstract version than that of EHRR.) I tried to base one on the Towers of Hanoi game. One can translate the positions of the game into a graph labelled by subsets. But the diameter is exponential! So maybe there is a way to change the “ground set”? I did not find any. I even tried to look at games (in game stores!) where the player is required to move from one position to another to see if this leads to an interesting abstract example. These were, while romantic, very long shots.

Two more things: First, I enjoyed meeting in Lausanne for the first time Freidrich Eisenbrand, Nicolai Hahnle, and Thomas Rothvoss. (EHR of EHRR.) Second, Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick proved (mildly) subexponential lower bounds for certain randomized pivot steps for the simplex algorithm. We discussed it in this post.  The underlying polytopes in their examples are combinatorial cubes. So this has no direct bearing on our problem. (But it is interesting to see if geometric or abstract examples coming from more general games of the type they consider may be relevant.)

So let me summarize PHC4 excitements and, as usual, if I missed something please add it.

# Emmanuel Abbe: Erdal Arıkan’s Polar Codes

Click here for the most recent polymath3 research thread. A new thread is comming soon.

Emmanuel Abbe and Erdal Arıkan

This post is authored by Emmanuel Abbe

A new class of codes, called polar codes, recently made a breakthrough in coding theory.

In his seminal work of 1948, Shannon had characterized the highest rate (speed of transmission) at which one could reliably communicate over a discrete memoryless channel (a noise model); he called this limit the capacity of the channel. However, he used a probabilistic method in his proof and left open the problem of reaching this capacity with coding schemes of manageable complexities. In the 90’s, codes were found (turbo codes and LDPC rediscovered) with promising results in that direction. However, mathematical proofs could only be provided for few specific channel cases (pretty much only for the so-called binary erasure channel). In 2008,  Erdal Arıkan at Bilkent University invented polar codes, providing a new mathematical framework to solve this problem.

Besides allowing rigorous proofs for coding theorems, an important attribute of polar codes is, in my opinion, that they bring a new perspective on how to handle randomness (beyond the channel coding problem). Indeed, after a couple of years of digestion of Arıkan’s work, it appears that there is a rather general phenomenon underneath the polar coding idea. The technique consist in applying a specific linear transform, constructed from many Kronecker products of a well-chosen small matrix, to a high-dimensional random vector (some assumptions are required on the vector distribution but let’s keep a general framework for now). The polarization phenomenon, if it occurs, then says that the transformed vector can be split into two parts (two groups of components): one of maximal randomness and one of minimal one (nearly deterministic). The polarization terminology comes from this antagonism. We will see below a specific example. But a remarkable point is that the separation procedure as well as the algorithm that reconstructs the original vector from the purely random components have low complexities (nearly linear). On the other hand, it is still an open problem to characterize mathematically if a given component belongs to the random or deterministic part. But there exist tractable algorithms to figure this out accurately.

Let us consider the simplest setting. Let $X_1,...,X_n$ be i.i.d. Bernoulli($p$) and assume that $n$ is a power of 2. Define $G_n$ to be the matrix obtained by taking $\log_2(n)$ Kronecker products of $G_2=\begin{pmatrix}1&0\\1&1\\\end{pmatrix}$, and multiply $X=(X_1,...,X_n)$ with $G_n$ over $GF(2)$ to get $U=(U_1,...,U_n)$. Note that $U$ has same entropy as $X$, since $G_n$ is invertible (its inverse is itself). However, if the entropy of $X$ is uniformly spread out over its components, i.e., $H(X)=nH(X_1)$, the entropy of $U$ may not be, since its components are correlated. In any case, we can write $H(U)= \sum_i H(U_i|U^{i-1})$ where $U^{i-1}=(U_1,...,U_{i-1})$ are the `past components’. The polarization phenomenon then says that, except for a vanishing fraction of indices $i$ (w.r. to $n$), each term $H(U_i|U^{i-1})$ tends to either 0 or 1.

# Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier

Click here for the most recent polymath3 research thread.

I missed Tom by a few minutes at Mittag-Leffler Institute a year and a half ago

Suppose that $R_n$ is a subset of $\{1,2,\dots, n \}$ of maximum cardinality not containing an arithmetic progression of length 3. Let $g(n)=n/|R_n|$.

Roth proved that $g(n) \ge log logn$. Szemeredi and Heath-Brown improved it to $g(n) \ge log^cn$ for some 0″ src=”http://l.wordpress.com/latex.php?latex=c%3E0&bg=ffffff&fg=000000&s=0&#8243; alt=”c>0″ /> (Szemeredi’s argument gave $c=1/4$.) Jean Bourgain improved the bound in 1999 to $c=1/2$ and in 2008 to $c=2/3$ (up to lower order terms).

Erdös and Turan who posed the problem in 1936 described a set not containing an arithmetic progression of size $n^c$.  Salem and Spencer improved this bound to $g(n) \le e^{logn/ loglogn}$. Behrend’s upper bound from 1946 is of the form $g(n) \le e^{C\sqrt {\log n}}$. A small improvement was achieved recently by Elkin and is discussed here.  (Look also at the remarks following that post.)

In an earlier post we asked: How does $g(n)$ behave? Since we do not really know, will it help talking about it? Can we somehow look beyond the horizon and try to guess what the truth is? (I still don’t know if softly discussing this or other mathematical problems is a fruitful idea, but it can be enjoyable.)

We even had a poll collecting people’s predictions about $g(n)$.  Somewhat surprisingly 18.18% of answerers predicted that $g(n)$ behaves like $(\log n)^c$ for some $c<1$. Be the answer as it may be, reaching  the logarithmic barrier was considered extremely difficult.

A couple of months ago Tom Sanders was able to refine Bourgain’s argument and proved that $g(n) \ge (\log n)^{3/4}$. Very recently Tom have managed to reach the logarithmic barrier and to prove that

$g(n) \ge (\log n)/(\log \log n)^{5}.$

Quoting from his paper: “There are two main new ingredients in the present work: the first is a way of transforming sumsets introduced by Nets Katz and Paul Koester in 2008, and the second is a result on the $L_p$-invariance of convolutions due to Ernie Croot and Olof Sisask (2010).”

This is a truly remarkable result.

# János Pach: Guth and Katz’s Solution of Erdős’s Distinct Distances Problem

Click here for the most recent polymath3 research thread.

Erdős and Pach celebrating another November day many years ago. The Wolf disguised as Little Red Riding Hood. Pach disguised as another Pach.

This post is authored by János Pach

### A Festive Day: November 19

Today is a festive day. It was on this day, November 19, 1863, that Abraham Lincoln presented his famous Gettysburg Address. Seventy nine years later, on the same day (on his own birthday!), Georgy Zhukov, Marshal of the Soviet Union, launched Operation Uranus, turning the tide of the battle of Stalingrad and of World War II. Now sixty eight years later, here we stand (or sit) and experience my very first attempt to contribute to a blog, as Gil has suggested so many times during the past couple of years. But above all, this is a festive day, because earlier today Larry Guth and Nets Hawk Katz posted on arXiv
(http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.4105v1.pdf) an almost complete solution of Erdös’s Distinct Distances Problem. The story started with Erdős’s 1946 paper published in the American Mathematical Monthly. In this paper, he posed two general questions about the distribution of distances determined by a finite set of points in a metric space.

1. Unit Distance Problem: At most how many times can the same distance (say, distance 1) occur among a set of n points?

2. Distinct Distances Problem: What is the minimum number of distinct distances determined by a set of n points?

Because of the many failed attempts to give reasonable bounds on these functions even in the plane, one had to realize that these questions are not merely “gems” in recreational mathematics. They have raised deep problems, some of which can be solved using graph theoretic and combinatorial ideas. In fact, the discovery of many important combinatorial techniques and results were motivated by their expected geometric consequences. (For more about the history of this problem, read my book with Pankaj Agarwal: Combinatorial Geometry, and for many related open problems, my book with Peter Brass and Willy Moser: Research Problems in Discrete Geometry.)

Erdős conjectured that in the plane the number of unit distances determined by n points is at most $n^{1+c/loglog n}$, for a positive constant c, but the best known upper bound, due to Spencer, Szemeredi, and Trotter is only $O(n^{4/3})$. As for the Distinct Distances Problem, the order of magnitude of the conjectured minimum is $n/\sqrt{log n}$, while the best lower bound was $n^{0.8641...}$, thanks to combined efforts by J. Solymosi – C.D. Toth (2001) and N.H. Katz – G. Tardos (2004).

This was the situation until today! The sensational new paper of Guth and Katz presents a proof of an almost tight lower bound of the order of n/log n. Let us celebrate this fantastic development! In this area of research, it is already considered a great achievement if by introducing an ingenious new idea one is able to improve a bound by a factor of $n^{\delta}$ for some positive δ. Continue reading

# Aaronson and Arkhipov’s Result on Hierarchy Collapse

Scott Aaronson gave a thought-provoking lecture in our Theory seminar three weeks ago.  (Actually, this was eleven months ago.) The slides are here . The lecture discussed two results regarding the computational power of quantum computers. One result from this paper gives an oracle-evidence that there are problems in BQP outside the polynomial hierarchy.  The method is based on “magnification” of results on bounded depth circuits. (It is related to the Linial-Nisan conjecture.)

The second result that we are going to discuss in this post (along with some of my provoked thoughts) is a recent result of Scott Aaronson and Alex Arkhipov which asserts that if  the power of quantum computers can be simulated by digital computers  then the polynomial hierarchy collapses.  More precisely, their result asserts that if sampling  probability distribution created by quantum computers (this is abbreviated as QSAMPLE) is in P then the polynomial hieararchy collapses to its third level.

The beautiful and important paper of Aaronson and Arkhipov is now out. Its main point of view is related to what I describe in the sixth section about “photon machines”. Update: Let me mention related idependent results by Michael J. Bremner, Richard Jozsa, Dan J. Shepherd in the paper entitled: “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy“.

Here is the plan for this post

1) The polynomial hierarchy and results about hierarchy collapse

2) The Aaronson Arkhipov (AA) theorem and its proof

3) Two problems posed by AA

Those are: does P=BQP already leads to a collapse of the polynomial hierarchy? And does APPROXIMATE-QSAMPLE already leads to a collapse?

4) Does fault tolerance allow QSAMPLE (on the nose)? (Answer: yes)

5) Is there a quantum analog to Aaronson and Arkhipov’s result and what is the computational power of quantum computers?

6) Three Two competing scenarios

7) Aaronson and Arkhipov photon machines and the complexity class BOSONSAMPLING.

# Octonions to the Rescue

## Xavier Dahan and Jean-Pierre Tillich’s Octonion-based Ramanujan Graphs with High Girth.

Update (February 2012): Non associative computations can be trickier than we expect. Unfortunately, the paper by Dahan and Tillich turned out to be incorrect.

Update: There is more to be told about the background of the new exciting paper. In particular, I would like to tell you more about regular graphs with high girth. (I started below.) The Ramanujan graphs story is, of course, also fascinating so at the very least I should give good links.

Michael Atiyah‘s lecture at IAS physics last Friday was entertaining, educational and quite provocative.

The talk started with the following thesis: There are four fundamental forces of nature and there are four division rings over the reals. The real numbers, complex numbers, Quaternions and the Octonions. Atiyah expects that the Octonions will play a major role in physics and will allow a theory which accounts for gravitation. He described some specific steps in this direction and related ideas and connections. At the end of the talk,  Atiyah’s thesis looked more plausible than in the beginning. His concluding line was: “you can regard what I say as nonsense, or you can claim that you know it already, but you cannot make these two claims together.” In any case, it looks that the people in the audience were rather impressed by and sympathetic to the Octonionic ideas of this wise energetic scientific tycoon.

The same day I received an email from Nati Linial. The subject was: “a good topic for your blog” and the email contained just a single link.
http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.2642v1.pdf

Nati is my older academic brother and often I regard our relations as similar to typical relations between older and younger (biological) brothers. When he tells me what to do I often rebel, but usually at the end I do as he says and most of the times he is right.

So I waited a couple of hours before looking at the link. Indeed,  1011.2642v1.pdf is a great paper. It uses Octonions in place of Quaternions for the construction of Ramanujan graphs and describes a wonderful breakthrough in creating small graphs with large girth. Peter Sarnak’s initial reaction to the new paper was: “wow”.

Here is a link to a paper entitled “Octonions” by John Baez, that appeared in Bull. AMS.

### Some background:

Let $G$ be a $k$-regular graph with girth $g$ where $g$ is an odd integer. Continue reading

# Subexponential Lower Bound for Randomized Pivot Rules!

Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form $2^{n^{\alpha}}$ for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding if this is possible was an open problem for several decades. Here is a link to the paper.

Update: Oliver Friedmann have managed to use similar methods to find similar lower bounds also for Zadeh’s deterministic pivot rule. See this paper.

We can regard the simplex algorithm as starting from an arbitrary vertex of the feasible polytope and repeatedly moving to a neighboring vertex with a higher value of the objective function according to some pivot rule.

The pivot rules considered in the paper are

RANDOM EDGE- Choose an improving pivoting step uniformly at random.

RANDOM FACET- Choose at random a facet containing your vertex and apply the algorithm in that facet.