Eran Nevo and Stedman Wilson have constructed triangulations with n vertices of the 3-dimensional sphere! This settled an old problem which stood open for several decades. Here is a link to their paper How many n-vertex triangulations does the 3 -sphere have?
1) Since the number of facets in an n-vertex triangulation of a 3-sphere is at most quadratic in n, an upper bound for the number of triangulations of the 3-sphere with n vertices is . For certain classes of triangulations, Dey removed in 1992 the logarithmic factor in the exponent for the upper bound.
2) Goodman and Pollack showed in 1986 that the number of simplicial 4-polytopes with n vertices is much much smaller . This upper bound applies to simplicial polytopes of every dimension d, and Alon extended it to general polytopes.
3) Before the new paper the world record was the 2004 lower bound by Pfeifle and Ziegler –
4) In 1988 I constructed triangulations of the d-spheres with n vertices. The new construction gives hope to improve it in any odd dimension by replacing [d/2] by [(d+1)/2] (which match up to logn the exponent in the upper bound). [Update (Dec 19) : this has now been achieved by Paco Santos (based on a different construction) and Nevo and Wilson (based on extensions of their 3-D constructions). More detailed to come.]
Borsuk asked in 1933 if every bounded set K of diameter 1 in can be covered by d+1 sets of smaller diameter. A positive answer was referred to as the “Borsuk Conjecture,” and it was disproved by Jeff Kahn and me in 1993. Many interesting open problems remain. The first two posts in the series “Around Borsuk’s Conjecture” are here and here. See also these posts (I,II,III, IV), and the post “Surprises in mathematics and theory” on Lipton and Reagan’s blog GLL.
Can we save the conjecture? We can certainly try, and in this post I would like to examine the possibility that Borsuk’s conjecture is correct except from some “coincidental” sets. The question is how to properly define “coincidental.”
Let K be a set of points in and let A be a set of pairs of points in K. We say that the pair (K, A) is general if for every continuous deformation of the distances on A there is a deformation K’ of K which realizes the deformed distances.
Conjecture 1: If D is the set of diameters in K and (K,D) is general then K can be partitioned into d+1 sets of smaller diameter.
We propose also (somewhat stronger) that this conjecture holds even when “continuous deformation” is replaced with “infinitesimal deformation”.
The finite case is of special interest:
A graph embedded in is stress-free if we cannot assign non-trivial weights to the edges so that the weighted sum of the edges containing any vertex v (regarded as vectors from v) is zero for every vertex v. (Here we embed the vertices and regard the edges as straight line segments. (Edges may intersect.) Such a graph is called a “geometric graph”.) When we restrict Conjecture 1 to finite configurations of points we get.
Conjecture 2: If G is a stress free geometric graph of diameters in then G is (d+1)-colorable.
A geometric graph of diameters is a geometric graph with all edges having the same length and all non edged having smaller lengths. The attempt for “saving” the Borsuk Conjecture presented here and Conjectures 1 and 2 first appeared in a 2002 collection of open problems dedicated to Daniel J. Kleitman, edited by Douglas West.
When we consider finite configurations of points we can make a similar conjecture for the minimal distances:
Conjecture 3: If the geometric graph of pairs of vertices realizing the minimal distances of a point-configuration in is stress-free, then it is (d+1)-colorable.
We can speculate that even the following stronger conjectures are true:
Conjecture 4: If G is a stress-free geometric graph in so that all edges in G are longer than all non-edges of G, then G is (d+1)-colorable.
Conjecture 5: If G is a stress-free geometric graph in so that all edges in G are shorter than all non-edges of G, then G is (d+1)-colorable.
We can even try to extend the condition further so edges in the geometric graph will be larger (or smaller) than non-edges only just “locally” for neighbors of each given vertex.
1) It is not true that every stress-free geometric graph in is (d+1)-colorable, and not even that every stress-free unit-distance graph is (d+1)-colorable. Here is the (well-known) example referred to as the Moser Spindle. Finding conditions under which stress-free graphs in are (d+1)-colorable is an interesting challenge.
2) Since a stress-free graph with n vertices has at most edges it must have a vertex of degree 2d-1 or less and hence it is 2d colorable. I expect this to be best possible but I am not sure about it. This shows that our “saved” version of Borsuk’s conjecture is of very different nature from the original one. For graphs of diameters in the chromatic number can, by the work of Jeff and me be exponential in .
3) It would be interesting to show that conjecture 1 holds in the non-discrete case when d+1 is replaced by 2d.
4) Coloring vertices of geometric graphs where the edged correspond to the minimal distance is related also the the well known Erdos-Faber-Lovasz conjecture..
See also this 1994 article by Jeff Kahn on Hypergraphs matching, covering and coloring problems.
5) The most famous conjecture regarding coloring of graphs is, of course, the four-color conjecture asserting that every planar graph is 4-colorable that was proved by Appel and Haken in 1976. Thinking about the four-color conjecture is always both fascinating and frustrating. An embedding for maximal planar graphs as vertices of a convex 3-dimensional polytope is stress-free (and so is, therefore, also a generic embedding), but we know that this property alone does not suffice for 4-colorability. Finding further conditions for stress-free graphs in that guarantee (d+1)-colorability can be relevant to the 4CT.
An old conjecture of mine asserts that
Conjecture 6: Let G be a graph obtained from the graph of a d-polytope P by triangulating each (non-triangular) face with non-intersecting diagonals. If G is stress-free (in which case the polytope P is called “elementary”) then G is (d+1)-colorable.
Closer to the conjectures of this post we can ask:
Conjecture 7: If G is a stress-free geometric graph in so that for every edge e of G is tangent to the unit ball and every non edge of G intersect the interior of the unit ball, then G is (d+1)-colorable.
A question that I forgot to include in part I.
What is the minimum diameter such that the unit ball in can be covered by n+1 sets of smaller diameter? It is known that for some constants C and C’.
Paul Erdős in Jerusalem,
I just came back from a great Erdős Centennial conference in wonderful Budapest. I gave a lecture on old and new problems (mainly) in combinatorics and geometry (here are the slides), where I presented twenty problems, here they are:
Around Borsuk’s Problem
Let be the smallest integer so that every set of diameter one in can be covered by sets of smaller diameter. Borsuk conjectured that .
It is known (Kahn and Kalai, 1993) that : , and also that (Schramm, 1989) .
Problem 1: Is f(d) exponential in d?
Problem 2: What is the smallest dimension for which Borsuk’s conjecture is false?
Volume of sets of constant width in high dimensions
Problem 3: Let us denote the volume of the n-ball of radius 1/2 by .
Question (Oded Schramm): Is there some so that for every there exist a set of constant width 1 in dimension n whose volume satisfies .
Around Tverberg’s theorem
Tverberg’s Theorem states the following: Let be points in with . Then there is a partition of such that .
Problem 4: Let be the smallest integer such that given points in , there exists a partition of such that every among the convex hulls , have a point in common.
Reay’s “relaxed Tverberg conjecture” asserts that that whenever (and ), .
Problem 5: For a set , denote by those points in which belong to the convex hull of pairwise disjoint subsets of . We call these points Tverberg points of order .
Conjecture: For every , .
Note that .
Problem 6: How many points in guarantee that they can be divided into two parts so that every union of convex sets containing the first part has a non empty intersection with every union of convex sets containing the second part.
A question about directed graphs
Problem 7: Let G be a directed graph with n vertices and 2n-2 edges. When can you divide your set of edges into two trees and (so far we disregard the orientation of edges,) so that when you reverse the directions of all edges in you get a strongly connected digraph.
Erdős-Ko-Rado theorem meets Catalan
Conjecture: Let be a collection of triangulations of an n-gon so that every two triangulations in share a diagonal. Then is at most the number of triangulations of an (n-1)-gon.
F ≤ 4E
Problem 9: Let K be a two-dimensional simplicial complex and suppose that K can be embedded in . Denote by E the number of edges of K and by F the number of 2-faces of K.
Conjecture: F ≤ 4E
A weaker version which is also widely open and very interesting is: For some absolute constant C, F ≤ C E.
Problem 10: The diameter of graphs of d-polytopes with n facets is bounded above by a polynomial in d and n.
Analysis – Fixed points
Problem 11: Let K be a convex body in . (Say, a ball, say a cube…) For which classes of functions, every which takes K into itself admits a fixed point in K.
Number theory – infinitely many primes in sparse sets
Problem 12: Find a (not extremely artificial) set A of integers so that for every n, , where you can prove that A contains infinitely many primes.
Möbius randomness for sparse sets
Problem 13: Find a (not extremely artificial) set A of integers so that for every n, where you can prove that
Computation – noisy game of life
Problem 14: Does a noisy version of Conway’s game of life support universal computation?
Ramsey for polytopes
Conjecture: For a fixed k, every d-polytope of sufficiently high dimension d contains a k-face which is either a simplex or a (combinatorial) cube.
Expectation thresholds and thresholds
Problem 16: Consider a random graph G in G(n,p) and the graph property: G contains a copy of a specific graph H. (Note: H depends on n; a motivating example: H is a Hamiltonian cycle.) Let q be the minimal value for which the expected number of copies of H’ in G in G(n,q) is at least 1/2 for every subgraph H’ of H. Let p be the value for which the probability that G in G(n,p) contains a copy of H is 1/2.
Conjecture: [Kahn – Kalai 2006] p/q = O( log n)
Problem 17: Let X be a family of subsets of .
How large X is needed to be so that the restriction (trace) of X to some set , has at least elements?
Problem 18: Let P be a property of graphs. Let be a collection of graphs with n vertices so that the symmetric difference of two graphs in has property P. How large can be.
Conditions for colorability
Problem 19: A conjecture by Roy Meshulam and me:
There is a constant C such that every graph G
with no induced cycles of order divisible by 3 is colorable by C colors.
Another conjecture by Roy Meshulam and me: For every b>0 there
is a constant C=C(b) with the following property:
Let G be a graph such that for all its induced subgraphs H
The number of independent sets of odd size minus the number of independent sets of even size is between -b and b.
Then G is colorable by C(b) colors.
The title of the lecture is borrowed from several papers and talks by Erdős. Continue reading
The news in brief
Andriy V. Bondarenko proved in his remarkable paper The Borsuk Conjecture for two-distance sets that the Borsuk’s conjecture is false for all dimensions greater than 65. This is a substantial improvement of the earlier record (all dimensions above 298) by Aicke Hinrichs and Christian Richter.
Borsuk’s conjecture asserted that every set of diameter 1 in d-dimensional Euclidean space can be covered by d+1 sets of smaller diameter. (Here are links to a post describing the disproof by Kahn and me and a post devoted to problems around Borsuk’s conjecture.)
Two questions posed by David Larman
David Larman posed in the ’70s two basic questions about Borsuk’s conjecture:
1) Does the conjecture hold for collections of 0-1 vectors (of constant weight)?
2) Does the conjecture hold for 2-distance sets? 2-distance sets are sets of points such that the pairwise distances between any two of them have only two values.
Reducing the dimensions for which Borsuk’s conjecture fails
In 1993 Jeff Kahn and I disproved Borsuk’s conjecture in dimension 1325 and all dimensions greater than 2014. Larman’s first conjecture played a special role in our work. While being a special case of Borsuk’s conjecture, it looked much less correct.
The lowest dimension for a counterexample were gradually reduced to 946 by A. Nilli, 561 by A. Raigorodskii, 560 by Weißbach, 323 by A. Hinrichs and 320 by I. Pikhurko. Currently the best known result is that Borsuk’s conjecture is false for n ≥ 298; The two last papers relies strongly on the Leech lattice.
Bondarenko proved that the Borsuk’s conjecture is false for all dimensions greater than 65. For this he disproved Larman’s second conjecture.
In this paper we answer Larman’s question on Borsuk’s conjecture for two-distance sets. We found a two-distance set consisting of 416 points on the unit sphere in the dimension 65 which cannot be partitioned into 83 parts of smaller diameter. This also reduces the smallest dimension in which Borsuk’s conjecture is known to be false. Other examples of two-distance sets with large Borsuk’s numbers will be given.
There was much interest in understanding sets of points in which have only two pairwise distances (or K pairwise distances). Larman, Rogers and Seidel proved that the maximum number can be at most (n+1)(n+4)/2 and Aart Blokhuis improved the bound to (n+1)(n+2)/2. The set of all 0-1 vectors of length n+1 with two ones gives an example with n(n+1)/2 vectors.
This is a good opportunity to mention another question related to two-distance sets. Suppose that you have a set of lines through the origin in so that the angles between any two of them is the same. Such a set is called an equiangular set of lines. Given such a set of cardinality m, if we take on each line one unit vector, this gives us a 2-distance set. It is known that m ≤ n(n+1)/2 but for a long time it was unknown if a quadratic set of equiangular lines exists in high dimensions. An exciting breakthrough came in 2000 when Dom deCaen constructed a set of equiangular lines in with lines for infinitely many values of n.
Strongly regular graphs
Strongly regular graphs are central in the new examples. A graph is strongly regular if every vertex has k neighbors, every adjacent pair of vertices have λ common neighbors and every non-adjacent pair of vertices have μ common neighbors. The study of strongly regular graphs (and other notions of strong regularity/symmetry) is a very important area in graph theory which involves deep algebra and geometry. Andriy’s construction is based on a known strongly regular graph .
1. E ≤ 3V
Let G be a simple planar graph with V vertices and E edges. It follows from Euler’s theorem that
E ≤ 3V
In fact, we have (when V is at least 3,) that E ≤ 3V – 6.
To see this, denote by F the number of regions or faces determined by G (in other words, the number of connected components in the complement of the embedded graph). Euler’s theorem asserts that
E – V + F = 2
V – E + F = 2
and now note that every face must have at least three edges and every edge is contained in two faces and therefore , so 6=3V – 3E + 3F ≤ 3V – 3E +2E.
2. F ≤ 4E
Now let K be a two-dimensional simplicial complex and suppose that K can be embedded in . Denote by E the number of edges of K and by F the number of 2-faces of K.
Here is a really great conjecture:
F ≤ 4E
A weaker version which is also widely open and very interesting is:
For some absolute constant C,
F ≤ C E
Remarks: The conjecture extends to higher dimensions. If K is an r-dimensional simplicial complex that can be embedded into then the conjecture is that
Where is a constant depending on r. Here is the number of i-dimensional faces of K. A stronger statement is that . The conjecture also extends to polyhedral complexes and more general form of complexes. In the conjecture ’embed’ refers to a topological embedding.
Over the last two meetings of our HU quantum computation seminar we heard two talks about symplectic geometry and its relations to quantum mechanics and quantum noise.
Yael Karshon: Manifolds, symplectic manifolds, Newtonian mechanics, quantization, and the non squeezing theorem.
The first informal lecture by Yael Karshon gave an introduction to the notions of manifolds and symplectic manifolds. Yael described the connection with Newtonian physics, gave the example of symplectic structure on phase spaces coming from physics, and talked about dynamics and physical laws. She also gave other examples of symplectic manifolds. The 2-dimensional sphere is an important example, and also complex projective manifolds are symplectic.
Now, if symplectic geometry describes Newtonian mechanics how should we move to describe quantum mechanics? Yael talked a little about quantization, described an impossibility theorem by Groenweld and Van Hove for certain general types of quantization, and mentioned a few ways around it. (More details at the end of this post.)
Non squeezing, symplectic camels and uncertainty.
Yael concluded with Gromov’s non-squeezing theorem. This theorem asserts that a ball of radius R cannot be “squeezed” by a symplectic map to a cylinder whose base is a circle of radius r, for R > r. Yael mentioned that Gromov’s non squeezing theorem can be regarded as a classical manifestation of the uncertainty principle from quantum mechanics. (The Wikipedia article gives a nice description of the theorem, mention the metaphor of passing a symplectic camel through the eye of a needle, and notes the connection with the uncertainty principle.)
Leonid Polterovich: Geometry of Poisson Brackets and Quantum Unsharpness
A week later Leonid Polterovich gave a lecture entitled “Geometry of Poisson brackets and quantum unsharpness.” (Here are the slides Update: here is a video of a related lecture in QStart). Leonid reviewed the notion of symplectic manifolds, and gave a vivid explanation, based on areas of parallelograms, of how to think about a symplectic form. Then he defined a displaceable set (a notion introduced by Helmut Hofer) in a symplectic manifold. This is a set X such that you can find a Hamiltonian diffeomorphism so that the image of X is disjoint from X. On small discs are displaceable but the equator is not!
Poisson brackets and the fiber theorem
Another crucial ingredient in the lecture was the notion of Poisson brackets which measure non-commutativity of Hamiltonian flow. Leonid continued to describe the Polterovich-Entov “non displaceable fiber theorem,” which asserts that if you have a function from a compact symplectic manifold to described by n real functions whose pairwise Poisson brackets vanish, then there is a point whose pre-image is not displaceable.
Partition of unity, classical registration, and cell phones.
A partition of unity is a collection of non-negative valued real functions that sum up to 1. Suppose we are given an open cover of M by n sets and ask if there exists a partition of unity such that is supported on and all Poisson brackets vanish. Next comes a theorem of Entov Polterovich and Zapolsky which asserts that this is not possible for covers with small sets, namely, if all sets are displaceable. In fact, the theorem gives a quantitative relation between how small the sets in the cover are and a “measure of non-commutativity” for any partition of unity that respects this open cover. Both the proof and the interpretations of this theorem have strong relations to quantum mechanics. This was the next topic in Leonid’s lecture. Leonid gave us a choice between ideas of QM playing a role in the proof and QM interpretation of the result and connections to quantum noise. In the end he talked about both topics.
Before going quantum, note that if the sets in the cover represent areas covered by an antenna for cell phones, you can ask how to register cellphones to antennas and regard the partition of unity as a probabilistic recipe.
Quantum mechanics, The correspondence principle
Enters quantum mechanics. Here is a dictionary
The correspondence principle in physics states that the behavior of systems described by the theory of quantum mechanics reproduces classical physics in the limit.
POVMs and projector valued POVMs (von-Neumann observables).
Leonid talked about two notions of observables. The more general one is based on positive operator valued measures (briefly – POVM’s). The more special one is von-Neumann observables which are special cases of POVM’s (called projector valued POVM’s). POVM’s on the quantum side are analogs of partition of unity on the classic side, and they lead to a sort of “quantum registration.” (This is the familiar probabilistic aspect of quantum measurement.)
Quantum noise, non-commutativity and the unsharpness principle
Following Ozawa, and Busch-Heinonen-Lahti, Leonid described a notion of “systematic quantum noise” and described a lower bound referred to as an “unsharpness principle” (Janssens 2006, Miyadera-Imai, 2008, and Polterovich 2012) of the systematic noise in terms of non commutativity of the components of the POVM. Quantum noise, in this context, refers only to measurements, and systematic quantum noise describes the extent to which POVM’s are not von-Neumann observables.
An unsharpness principle for Berezin-Toeplitz quantization
Leonid described next the unsharpness principle based on the Berezin-Toeplitz quantization of a symplectic manifold. In this case we can talk about a POVM which corresponds to an open cover of the manifold by small sets. The conclusion is that these POVMs cannot be too close to projector-valued POVM’s. The proof relies on the theorem of Entov-Polterovich-Zapolsky, the (difficult) correspondence principles for the quantization, and the linear-algebraic unsharpness principle for POVM’s. (I will give some more details below.)
Links to Leonid’s papers
Leonid briefly mentioned in his lecture the name of Grete Hermann. She was a German mathematician and philosopher, who is famous for her early work on the foundations of quantum mechanics and early criticism of the no-hidden-variable theorem by John von Neumann. Here is an English translation of her 1935 paper: The foundations of quantum mechanics in the philosophy of nature. At age 26 Hermann finished her Ph. D. in mathematics with Emmy Noether. In the 30s she participated in an underground movement against the Nazis and lived in exile from 1936 until 1946.
Symplecticism and skepticism: possible relations with my work
As some of you may know I am quite interested in quantum noise and quantum fault-tolerance. My work is about properties and models of quantum noise which do not enable quantum fault tolerance believed to be crucial for building quantum computers. (Here are slides from a recent talk.) Ultimately, the hope is to use the theory of quantum error-correction and quantum fault-tolerance to describe principles of quantum noise which do not enable computational superior devices based on quantum physics.
Leonid and I were surprised to discover that we are both interested in quantum noise, and some of the statements we made look linguistically similar. For example, we both talk about a certain “hard-core” noisy kernel that cannot be avoided, and relate it to measures of non-commutativity. Leonid talks about “smearing” while I talk about “smoothing,” etc.
Yet, there are also clear differences. The unsharpness principle talks about noisy measurements and not about noisy approximations to unitary evolutions or to pure states which are what my work is mainly about.
Yet again, there may be ways to reconcile these differences. Ideal quantum computer evolutions induce non-unitary operations on parts of the quantum memory, even when it comes to two qubits. (And I am quite interested in the case of two qubits.) Beside that, quantum fault-tolerance is based fundamentally on non-unitary evolutions. Another interesting question is to see if my “smoothed Linblad evolutions” which are obtained from an arbitrary noisy evolution by adding a certain “smoothing” in time satisfy the unsharpness principle. And another interesting question is to see if physics-models of noisy quantum computers like the ones proposed by Aharonov-Kitaev-Preskill, and Preskill do obey the unsharpness principle.
It will be interesting to explore connections between Leonid’s work and mine. The notion of a quantum computer abstracts away the geometry and much of the physics and this is also the case for models of noisy quantum computers – both the standard ones and mine. The same is true for classical computers – classical computers can be used to describe classical physics but the laws of physics do not emerge from Turing machines or Boolean circuits. In the quantum and classical cases alike, more structure is needed. So in order to check my conjectures on the behavior of noisy quantum systems we either need to study very specific proposed implementations of quantum computers or other specific noisy quantum systems, or to consider some middle ground that manifests the physics. Symplectic geometry can give a useful such middle ground.
Other relations with quantum information and quantum computation
Yet again once more, it looks like the connection of symplectic geometry, quantization and noise with the theory of quantum information and computation need not be restricted to my little skeptical corner. Useful ideas and examples can flow in both directions and involve mainstream quantum computation. The symplectic angle is certainly a good thing to be aware of and explore (and for me it will probably be a slow process).
A few more details on quantization in symplectic geometry as explained by Yael Karshon.
The challenge is to associate to every symplectic manifold M a Hilbert space H and to every real valued smooth function on M a self-adjoint operator on H such that
- Linear combinations of functions go to linear combinations of operators,
- Poisson brackets of functions go to i times the commutator of operators,
- the function 1 goes to the identity operator, and
- a “complete” family of functions passes to a “complete” family of operators.
The axioms (1)-(4) are attributed to Dirac. In (4), a family of functions is “complete” if it separates points almost everywhere and a family of operators is “complete” if it acts irreducibly. (There may be variations in these definitions. Some people require more, e.g., that the powers of a function be mapped to the powers of the corresponding operator.)
“No go theorems” say that there does not exist a correspondence (that is nontrivial in some sense) that satisfies the properties (1)-(4). A “no go theorem” for was given by Groenweld and Van Hove. Later “no go theorems” were also found for some compact symplectic manifolds. The 1996 review paper “Obstruction results in quantization theory”, by Gotay, Grundling, and Tuynman, should be relevant.
The first step in Geometric Quantization, which is called Prequantization, more or less achieves (1), (2), (3) but fails at (4). One compromise is to define the correspondence not for all smooth functions, but, rather, to restrict it to a sub-Poisson-algebra of the smooth functions. With this compromise, Geometric quantization can achieve (1)-(4). (But it depends on a choice of a so-called “polarization”. Often different choices give isomorphic answers but this is only partially understood.)
Other methods of quantization involve asymptotic in h-bar. This means that the desired correspondence is demonstrated in the limit with respect to some parameter regarded as 1 over the Planck constant. One of these is the Berezin-Toeplitz quantization that Leonid works with. Another is Deformation Quantization.
Berezin-Toeplitz quantization, smearing, coherent noise, and quasi-states as further explained by Leonid Polterovich
Berezin-Toeplitz quantization is a procedure to move from a symplectic manifold M to a sequence of Hilbert spaces which satisfy in the limit (when m tends to infinity) the quantization requirements. Leonid did not explain the construction in the lecture but later explained to Dorit Aharonov, Guy Kindler, and me how it works for the special case where M is a Cartesian product of n copies of . Very roughly you associate to each an m-dimensional Hilbert space and let m tend to infinity. The proofs of the correspondence principle: namely, the relation between commutators and Poisson brackets when m tends to infinity involve deep and difficult mathematics, with certain shortcuts when the symplectic manifolds have the extra structure of a “Kahler manifold.” While the main interest in the literature is for the case that m tends to infinity, for us, the case m=2 is quite interesting as it relates unitary evolution on an n-qubit quantum computer with Hamiltonian evolution on a Cartesian product of 2-spheres.
Quantum registration, smearing, unsmearing and coherent noise
POVMs can be used to describe a quantum registration rule analogous to the classical probabilistic rule based on partition of unity. Leonid described a statistical smearing operation on POMVs that increases noise. He asked to what extent we can denoise using unsmearing, and proved that, in certain circumstances, a certain amount of “inherent noise” persistent under unsmearing must remain.
Quantum and symplectic quasi-states
The lecture mentioned briefly another interesting aspect of the classical-quantum correspondence through symplectic geometry. Gleason proved in 1957 that for Hilbert spaces of dimension 3 or more every “quasi-state” is a state. (Quasi states are defined based on linearity requirement just when the observables are commuting.) Non linear symplectic “quasi-states” do exist and this is related to deep developments in symplectic geometry. Leonid’s talk shows that quasi-states provided by symplectic geometry vanish on functions with dispaceable (“small”) supports. This readily rules out existence of Poisson commuting partitions of unity with displaceable supports.)
Happy new year, everybody!
A planned “Kazhdan’s seminar” spring 2014.
In 2003/2004 David Kazhdan and I ran a seminar on polytopes, toric varieties, and related combinatorics and algebra. (A lot has happened since and this spring Sam Payne and I will give together a course at Yale on similar topics this spring. There will be a separate post about it.) David and I felt that it is time to run another such event in 2014, perhaps establishing a tradition for a decennial joint seminar. So next spring, the plan is that David with me and Leonid and hopefully also Michael and Dorit will devote one of David’s Sunday seminars to computation, quantumness, symplectic geometry, and information.
A 1965 letter by Richard Palais
In a widely circulated but unpublished letter in 1965, Richard Palais explained the symplectic formulation of Hamiltonian mechanics. See this MO question.
Small and large in mathematics
Different notions of “small” and “large” and the tension between them are quite important in many areas of mathematics. Of course, sets of measure zero, sets of Baire-category one, sets of lower dimensions, subsets of smaller (infinite) cardinality, come to mind. In the symplectic context displaceable sets are small: note that the lower-dimensional equator is symplectically “large” while caps with positive area are “small.”
Let me remind myself that I should attempt to blog some time about deep recent results on “null-sets” in Eucledian spaces connected also to combinatorics. (Meanwhile, here are links to two papers by Alberti, Csörnyei, and Preiss, Structure of null sets in the plane and applications, and Diﬀerentiability of Lipschitz functions, structure of null sets, and other problems.)
In theoretical computer science, what do the terms “Yaelism” and “Adamology” refer to?
Camels and elephants through the eye of a needle
The term “symplectic camel” refers to a quote of Jesus: “It is easier for a camel to pass through the eye of a needle than for a rich man to enter heaven.” (I learned about it when it was used in Aram Harrow’s reply in one part of our quantum debate, See also this post on The Quantum Pontiff ) A nice discussion of this phrase can be found here. The Jewish analog (from the Talmud) is about passing an elephant through the eye of a needle which is used to describe making convoluted arguments which have no basis in reality, attributed to the scholars of Pompeditha. Rabbi Shesheth answered Rabbi Amram “Maybe you are from the school at Pumbeditha, where they can make an elephant pass through the eye of a needle.”
Greg Kuperberg referred in this context to: Rowan Atkinson – Conservative Conference
“It is easier for a rich man to pass through the eye of a needle than…for a camel to!”
An additional clarification on symplectic camels by Yael
Gromov Nonsqueezing and the Symplectic Camel Theorem are two different theorems. (The Wikipedia article is unclear about this.) The Symplectic Camel theorem says this. Take , say, with coordinates Remove the hyperplane minus a ball of radius r in this hyperplane.
Thus, we get two “rooms” separated by a “wall” but with a “hole” in the wall. If R<r then a ball of radius R that lies entirely in the “left room” can be continuously translated through the “hole” into the “right room” If R>r we cannot move the ball to the “right room” continuously by translations nor rigid transformations but we can move it through volume preserving transformations (by first squishing it so it becomes long and narrow). The theorem says that we cannot do this symplectically: if R > r then there is no path of symplectic embeddings of the ball of radius R that starts with an embedding into and ends with an embedding into (An interesting open question is whether there exists a “compact camel“: a compact symplectic manifold in which the space of symplectic embeddings of a ball of some fixed radius R into the manifold is disconnected.)
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 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.
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.
Problems 16-18 in Thurston’s Bulletin paper.
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
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.
The Sylvester-Gallai Theorem: Let X be a finite set of n points in an eulidean space such that for every two distinct points the line through and contains a third point . Then all points in 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 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 the number of such that the line through and contains another point of is at least . Then
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 -query locally correctable -code over a field is a subspace of so that, given any element that disagrees with some in at most positions and an index , we can recover with probability 3/4 by reading at most coordinates of . 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 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 ? 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.