Greg Kuperberg: It is in NP to Tell if a Knot is Knotted! (under GRH!)

Wolfgang Haken found an algorithm to tell if a knot is trivial, and, more generally with Hemion, if two knots are equivalent.

Joel Hass, Jeff Lagarias and Nick Pippinger proved in 1999 that telling that a knot is unknotted is in NP. This is a major result!

An outstanding problem for many years was to determine if telling that a knot is unknotted is in coNP or equivalently if telling that a knot is nontrivial is in NP as well. A few month ago Greg Kuperberg proved it under GRH (the generalized Riemann hypothesis)! Amazing! Kuperberg ingenious short proof is based on a recent important knot-theoretic result by Kronheimer and Mrowka combined with computational complexity result by Koiran (discussed in the section “from Primes to Complexity”over this GLL’s post).

There were several results in knot theory in recent years that gradually showed that several invariants (related, generally speaking, to Jones polynomials but more detailed, e.g., Khovanov homology,) are enough to tell if a knot is trivial. I am not so sure about how this fascinating story goes.

An earlier, different,  approach (via the Thurston norm) from 2002 to showing that verifying that a knot is trivial is in coNP was by Ian Agol.

It is very interesting if the dependence on GRH can be removed. Of course, a major problem is if telling if a knot is trivial is in P. Showing that the problem is in BQP will also be great.

Eralier,  in a SODA 2005 article, Hara, Tani, and Yamamoto proved  that unknotting is in AM $\cap$ coAM. As mentioned in the comments the argument was incomplete. (One thing I learned from Greg’s preprint is that there is a preprint by Chad Musick who is describing a polynomial-time algorithm for testing if a knot is trivial. His work is based on a knot-invariant called “the crumble,” and its status is unclear at present.)

I am not sure what is the complexity for telling if two knots are equivalent. Haken and Hemion proved that it is decidable. Telling if a knot is trivial feels a little like PRIMALITY while telling two knots apart feels a little like FACTORING. Here is a survey article by Joel Hass on the computability and complexity of knots and 3-manifolds equivalence. It looks that the algorithmic theory of knots is related to both coltures of 3-dim topology, the one related to structural results, combinatorial group theory, geometrization etc, and the other related to invariants and physics, and this is nice. See also the post over GLL entitled “What makes a knot knotty.”

And here is Greg’s description of his ingenious proof. (It is not as easy as the description suggests.) Reading Greg’s short page paper is  recommended.

Exciting News on Three Dimensional Manifolds

The Virtually Haken Conjecture

A Haken 3-manifold is a compact 3-dimensional manifold M which is irreducible (in a certain strong sense) but contains an incompressible surface S. (An embedded surface S is incompressible if the embedding indices an injection of its fundamental group to the fundamental group of M. A 3-manifold is virtually finite Haken  if it has a finite cover which is Haken. (This is a typical way how the word “virtually” occurs in algebra and topology.)

The virtually Haken conjecture states that every compact, orientable, irreducible 3-dimensional manifold with infinite fundamental group is virtually Haken. The big news is that Ian Agol has just announced the proof of the virtually Haken conjecture!

Danny Calegary have just wrote three detailed posts about it over his blog “Geometry and the Imagination”:  Agol’s Virtual Haken Theorem (part 1),  Agol’s Virtual Haken Theorem (part 2): Agol-Groves-Manning strike back, and Agol’s Virtual Haken Theorem (part 3): return of the hierarchies. (Everything I say is taken from there.)

To quote Danny:

I think it is no overstatement to say that this marks the end of an era in 3-manifold topology, since the proof ties up just about every loose end left over on the list of problems in 3-manifold topology from Thurston’s famous Bulletin article (with the exception of problem 23 — to show that volumes of closed hyperbolic 3-manifolds are not rationally related — which is very close to some famous open problems in number theory).

Here are also few relevant posts from the blog: Low dimensional topology. A post about Wise conjecture  (that Agol proved)  with references and links;   An earlier post on Wise’s work; A post VHC post; Update (August ’14): Here is a post by Tim Gowers on Agol’s lecture at ICM2014. The videotaped lecture can be found here. Ian’s ICM paper can be found here. Dani Wises’s ICM talk is here.

A whole array of conjectures and a whole array of results: Wise, Haglund-Wise, Bergeron-Wise, Sageev, Kahn-Markovic, …

Perleman’s geometrization theorem reduces the conjecture to the case of hyperbolic manifolds. Continue reading

Fractional Sylvester-Gallai

Avi Wigderson was in town and gave a beautiful talk about an extension of Sylvester-Gallai theorem. Here is a link to the paper: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes by Boaz Barak, Zeev Dvir, Avi Wigderson, and Amir Yehudayoff.

Sylvester-Gallai

The Sylvester-Gallai Theorem:  Let X be a finite set of n points in an eulidean space such that for every two distinct points $x,y \in X$ the line through $x$ and $y$ contains a third point $z \in X$. Then all points in $X$ are contained in a line.

I heard about this result when I took Benjy Weiss’s mathematics course for high-school students in 1970/1. a  The Sylvester-Gallai theorem was the last question marked with (*) in the first week’s homework. In one of the next meetings Benjy listened carefully to our ideas on how to prove it and then explained to us why our attempts of proving it are doomed to fail: What we tried to do only relied on the very basic incidence axioms of Euclidean geometry but the Sylvester-Gallai theorem does not hold for finite projective planes. (Sylvester conjectured the result in 1893. The first proof was given by Mechior in 1940 and Gallai proved it in 1945.)

My MO question

Befor describing the new results let me mention my third ever MathOverflow question that was about potential extensions of the G-S theorem. The question was roughly this:

Suppose that V is an r dimensional variety embedded into n space so that if the intersection of every j-dimensional subspace with V is full dimensional then this intersection  is “complicated”. Then $n$ cannot be too large.

I will not reproduce the full question here but only a memorable remark made by Greg Kuperberg:

If you claimed that Gil is short for Gilvester (which is a real first name although rare), then you could say that any of your results is the “Gilvester Kalai theorem”. – Greg Kuperberg Nov 24 2009 at 5:13

The result by Barak, Dvir, Wigderson and Yehudayoff

Theorem:  Let X be a finite set of n points in an Euclidean space such that for every point $x \in X$ the number of $y, y\in X,y \ne x$ such that the line through $x$ and $y$ contains another point of $X$ is at least $\delta (n-1)$. Then

$\dim (Aff(X))\le 13/\delta^2$

Some remarks:

1) The proof: The first ingredient of the proof is a translation of the theorem into a question about ranks of matrices with a certain combinatorial structure. The next thing is to observe is that when the non zero entries of the matrix are 1’s the claim is simple. The second surprising ingredient of the proof is to use scaling in order to “tame” the entries of the matrix.

2)  The context – locally correctable codes:  A $q$-query locally correctable $(q,\delta)$-code over a field $F$ is a subspace of $F^n$ so that, given any element $\tilde y$ that disagrees with some $y \in C$ in at most $\delta n$ positions and an index $i$, $1 \le i \le n$ we can recover $y_i$ with probability 3/4 by reading at most $q$ coordinates of $\tilde y$.  The theorem stated above imply that, for two queries,  over the real numbers (and also over the complex numbers), such codes do not exist when $n$ is large. Another context where the result is of interest is the hot area of sum product theorems and related questions in the geometry of incidences.

3) Some open problems: Is there a more detailed structure theorem for configurations of points satisfying the condition of the theorem? Can the result be improved to $\dim (Aff(X))=O(1/\delta )$? Can a similar result be proved on locally correctable codes with more than two queries? This also translates into an interesting Sylvester-Gallai type question but it will require, Avi said, new ideas.

Polymath3 (PHC6): The Polynomial Hirsch Conjecture – A Topological Approach

This is a new polymath3 research thread. Our aim is to tackle the polynomial Hirsch conjecture which asserts that there is a polynomial upper bound for the diameter of graphs of $d$-dimensional polytopes with $n$ facets. Our research so far was devoted to an abstract combinatorial setting. We studied an appealing conjecture by Nicolai Hahnle and considered an even more general abstraction proposed by Yury Volvovskiy. Comments towards this abstract conjecture are most welcome!

Here, I would like to mention a topological approach which follows a result that was discovered independently by Tamon Stephen and Hugh Thomas in their paper An Euler characteristic proof that 4-prismatoids have width at most 4,
and by Paco Santos in his paper Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids. This post is based on a discussion with Paco Santos at Oberwolfach.

Two maps on a two dimensional Sphere

Theorem: Given a red map and a blue map drawn in general position on $S^2$ there is an intersection point of two edges of different colors which is adjacent (in the refined map) to a red vertex and to a blue vertex.

Blue and black maps

There are two proofs for the theorem. The proof by Stephen and Thomas uses an Euler characteristic argument. The proof by Santos applies a connectivity argument. Both papers are short and elegant. Both papers point out that the result does not hold for maps on a torus.

Santos’ counterexample to the Hirsch conjecture is based on showing that a direct extension of this result to maps in three dimensions fails. (Even for two maps coming from fans based on polytopes.) Of course, first Paco found his counterexample and then the two-map theorem was found in response to his question  of whether one can find in dimension four counterexamples of the kind he presented in dimension five.

The theorem by Santos, Stephen, and Thomas is very elegant. The proofs are simple but far from obvious and it seems to me that the result will find interesting applications. Its elegance and depth reminded me of Anton Klyachko’s car crash theorem.

A topological question in high dimensions

Now we are ready to present a higher-dimensional analog:

Tentative Conjecture: Let $M_1$ be a red map and let  $M_2$ be a blue map drawn in general position on $S^{n}$, and let $M$ be their common refinement.  There is a vertex $w$ of $M$ a blue vertex $v \in M_1$, a red vertex $u \in M_2$ and two faces $F,~G \in M$ such that 1) $v,w \in F$, 2) $w,u \in G$, and 3) $\dim F + \dim G =n$.

A simple (but perhaps not the most general) setting in which to ask this question is with regard to the red and blue maps  coming from red and blue polyhedral fans associated to red and blue convex polytopes. The common refinement will be the fan obtained by taking all intersections of cones, one from the first fan and one from the second.

(Perhaps when $n=2k$ we can even guarantee that $\dim F=\dim G=k$.)

Why the tentative conjecture implies that the diameter is polynomial

An affirmative answer to this conjecture will lead to a bound of the form $dn$ for the graph of $d$-polytopes with $n$ facets.

Here is why:

– It is known that the diameter of every polytope with $n$ facets and dimension $d$ is bounded above by the “length” of a Dantzig figure with $2n-2d$ facets and $n-d$ vertices.

Here a Dantzig figure is a simple polytope of dimension $D$ with $2D$ facets and two complementary vertices. (i.e., two vertices such that each vertex lies in half of the facets, and they do not belong to any common facet).

The length of the Dantzig figure is the graph distance between these two vertices. This is the classical “d-step theorem” of Klee and Walkup, 1967.

– The length of a Dantzig figure of dimension $d$ is the same as the minimum distance between blue and red vertices in a pair of two maps in the $(d-2)$-sphere, with $d$ cells each.

– Our tentative conjecture implies, by dimension on $d$, that the minimum distance between blue and red vertices in a pair of maps in the $d$-sphere and with $n$ cells is bounded above by (essentially) $nd$. ($n$ cells means “cells of the blue map plus cells of the red map”, not “cells of the common refinement”).

The abstract setting and other approaches

More comments, ideas, and updates on the abstract setting are of course very welcome Also very welcome are other approaches to the polynomial Hirsch conjecture, and discussion of related problems.

An example showing that the theorem fail for blue and red maps on a torus.

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

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

Benoît’s Fractals

Mandelbrot set

Benoît Mandelbrot passed away a few dayes ago on October 14, 2010. Since 1987, Mandelbrot was a member of the Yale’s mathematics department. This chapterette from my book “Gina says: Adventures in the Blogosphere String War”   about fractals is brought here on this sad occasion.

A little demonstration of Mandelbrot’s impact: when you search in Google for an image for “Mandelbrot” do not get pictures of Mandelbrot himself but rather pictures of Mandelbrot’s creation. You get full pages of beautiful pictures of Mandelbrot sets

.

Benoit Mandelbrot (1924-2010)

Modeling physics by continuous smooth mathematical objects have led to the most remarkable achievements of science in the last centuries. The interplay between smooth geometry and stochastic processes is also a very powerfull and fruitful idea. Mandelbrot’s realization of the prominence of fractals and his works on their study can be added to this short list of major paradigms in mathematical modeling of real world phenomena.

Fractals

Fractals are beautiful mathematical objects whose study goes back to the late 19th century. The Sierpiński triangle and the Koch snowflake are early examples of fractals which are constructed by simple recursive rules. Continue reading

Question: Let $X=[0,1]^d$ be the $d$-dimensional cube. Turn $X$ into a torus $T^d$ by identifying opposite facets. What is the minumum $(d-1)$-dimensional volume $f(d)$ of a subset $Y$ of $X$ which intersects every non-trivial cycle in $T^d$.
Answer: Taking $Y$ to be all points in the solid cube with one coordinate having value 1/2, gives you a set $Y$ that seperates all cycles and has $(d-1)$-dimensional volume equals $d$. It is not difficult to prove that $f(d) \ge C\sqrt d$. Guy Kindler, Ryan O’donnell, Anup Rao and Avi Wigderson proved the existence of $Y$ which seperates all cycles with $vol(Y) =O(\sqrt d)$. A simpler argument was found by Noga Alon and Boaz Klartag.  For an even simpler treatement of this result along with several discrete analogs see this paper by Noga.