Amazing progress on longstanding open problems
For those who haven’t seen it:
- Aubrey de Grey, better known to the world as a radical life extension researcher, on Sunday posted a preprint on the arXiv claiming to prove that the chromatic number of the plane is at least 5—the first significant progress on the Hadwiger-Nelson problem since 1950. If you’re tuning in from home, the Hadwiger-Nelson problem asks: what’s the minimum number of colors that you need to color the Euclidean plane, in order to ensure that every two points at distance exactly 1 from each other are colored differently? It’s not hard to show that at least 4 colors are necessary, or that 7 colors suffice: try convincing yourself by staring at the figure below. Until a few days ago, nothing better was known.
This is a problem that’s intrigued me ever since I learned about it at a math camp in 1996, and that I spent at least a day of my teenagerhood trying to solve.
De Grey constructs an explicit graph with unit distances—originally with 1567 vertices, now with 1585 vertices after after a bug was fixed—and then verifies by computer search (which takes a few hours) that 5 colors are needed for it. Update: My good friend Marijn Heule, at UT Austin, has now apparently found a smaller such graph, with “only” 874 vertices. See here.
So, can we be confident that the proof will stand—i.e., that there are no further bugs? See the comments of Gil Kalai’s post for discussion. Briefly, though, it’s now been independently verified, using different SAT-solvers, that the chromatic number of de Grey’s corrected graph is indeed 5. Paul Phillips emailed to tell me that he’s now independently verified that the graph is unit distance as well. So I think it’s time to declare the result correct.
Question for experts: is there a general principle by which we can show that, if the chromatic number of the plane is at least 6, or is 7, then there exists a finite subgraph that witnesses it? (This is closely related to asking, what’s the logical complexity of the Hadwiger-Nelson problem: is it Π1?) Update: As de Grey and a commenter pointed out to me, this is the de Bruijn-Erdös Theorem from 1951. But the proofs inherently require the Axiom of Choice. Assuming AC, this also gives you that Hadwiger-Nslson is a Π1 statement, since the coordinates of the points in any finite counterexample can be assumed to be algebraic. However, this also raises the strange possibility that the chromatic number of the plane could be smaller assuming AC than not assuming it. - Last week, Urmila Mahadev, a student (as was I, oh so many years ago) of Umesh Vazirani at Berkeley, posted a preprint on the arXiv giving a protocol for a quantum computer to prove the results of any computation it performs to a classical skeptic—assuming a relatively standard cryptographic assumption, namely the quantum hardness of the Learning With Errors (LWE) problem, and requiring only classical communication between the skeptic and the QC. I don’t know how many readers remember, but way back in 2006, inspired by a $25,000 prize offered by Stephen Wolfram, I decided to offer a $25 prize to anyone who could solve the problem of proving the results of an arbitrary quantum computation to a classical skeptic, or who could give oracle evidence that a solution was impossible. I had first learned this fundamental problem from Daniel Gottesman.
Just a year or two later, independent work of Aharonov, Ben-Or, and Eban, and of Broadbent, Fitzsimons, and Kashefi made a major advance on the problem, by giving protocols that were information-theoretically secure. The downside was that, in contrast to Mahadev’s new protocol, these earlier protocols required the verifier to be a little bit quantum: in particular, to exchange individual unentangled qubits with the QC. Or, as shown by later work, the verifier could be completely classical, but only if it could send challenges to two or more quantum computers that were entangled but unable to communicate with each other. In light of these achievements, I decided to award both groups their own checks for half the prize amount ($12.50), to be split among themselves however they chose.
Neither with Broadbent et al.’s or Aharonov et al.’s earlier work, nor with Mahadev’s new work, is it immediately clear whether the protocols relativize (that is, whether they work relative to an arbitrary oracle), but it’s plausible that they don’t.
Anyway, assuming that her breakthrough result stands, I look forward to awarding Urmila the full $25 prize when I see her at the Simons Institute in Berkeley this June.
Huge congratulations to Aubrey and Urmila for their achievements!
Update (April 12): My friend Virgi Vassilevska Williams asked me to announce a theoretical computer science women event, which will take during the upcoming STOC in LA.
Another Update: Another friend, Holden Karnofsky of the Open Philanthropy Project, asked me to advertise that OpenPhil is looking to hire a Research Analyst and Senior Research Analyst. See also this Medium piece (“Hiring Analytical Thinkers to Help Give Away Billions”) to learn more about what the job would involve.
Follow
Comment #1 April 11th, 2018 at 10:18 am
what about this amazing progress on the quantum PCP conjecture?
https://arxiv.org/abs/1801.03821
Comment #2 April 11th, 2018 at 10:40 am
Typo in point 1, “De Grey constructs an explicit graph with unit distances—originally with 1657 vertices,” ; 1657 should be 1567, and in fact he gives a construction first of a 20425-vertex unit distance graph before “shrinking” it to the 1567-vertex example.
Comment #3 April 11th, 2018 at 10:50 am
“Is there a general principle by which we can show that, if the chromatic number of the plane is at least 6, or is 7, then there exists a finite subgraph that witnesses it?”
Assuming the axiom of choice, yes. One explanation that’s correct but not all that great is that it follows from Tychonoff’s theorem. Another answer that’s also correct but not all that great is that, roughly speaking, you can color the points in the plane by transfinite induction.
Comment #4 April 11th, 2018 at 11:00 am
>is there a general principle by which we can show that, if the chromatic number of the plane is at least 6, or is 7, then there exists a finite subgraph that witnesses it?
Sure, “compactness”. Consider the propositional logic generated by statements of the form “point (x,y) has colour A” (where x and y range over the reals, and A ranges over the colours you want to use), with axioms forcing any two points unit distance apart to have different colours. It’s known that if any such theory is consistent it has a model. So if there isn’t a colouring then the theory is inconsistent, i.e. there is a proof of “false”. But such a proof uses only finitely many axioms. So there are finitely many points such that just considering the subgraph on those points is enough to show that the whole graph can’t be coloured with however many colours it was that you let A range over.
Comment #5 April 11th, 2018 at 11:13 am
Okay, I think this works.
Theorem in ZF: If G is a graph with well-ordered vertices, and if every finite subgraph of G has a k-coloring, then G has a k-coloring.
Proof: Call a k-coloring of a subset S of V(G) (not necessarily a finite subset) *finitely extensible* if it can be extended to every superset T such that T\S is finite. The empty set has only one k-coloring, and by hypothesis, it is finitely extensible.
The idea now is that you can color the vertices of G in a finitely extensible manner by induction. Suppose that S is an initial subset of V(G) and that we have found finitely extensible colorings for all previous initial subsets that all agree with each other. If S is limit ordinal, then just take the union of everything that came before. On the other hand, if S is a successor ordinal, then it has a new element v and we found a finitely extensible coloring of S\v. One of the k colors for v has to work: The way to rule out a color i for v as finitely extensible is to find some finite subset T_i such that S\v does not extend to S union T_i. But if you could do that for each of the k colors, then S\v would not extend to S union every T_i. To avoid making any choices, assign v the first finitely extensible color.
Comment #6 April 11th, 2018 at 11:47 am
Chromatic number is always witnessed by a finite subgraph:
https://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(graph_theory)
Comment #7 April 11th, 2018 at 12:00 pm
This is the de Bruijn-Erd\H{o}s theorem, proof as sketched.
Comment #8 April 11th, 2018 at 12:07 pm
Anthony #1: Also very cool!
Comment #9 April 11th, 2018 at 12:08 pm
j.c. #2: Thanks; fixed!
Comment #10 April 11th, 2018 at 12:13 pm
But note for the last sketch, comment #5 – there are models of ZF in which de Bruijn-Erd\H{o}s fails, see
https://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(graph_theory)
and so you really need to be given a well-ordering which in general doesn’t exist without choice.
Comment #11 April 11th, 2018 at 12:18 pm
Greg Kuperberg and Oscar Cunningham: Thanks! The following is the point that I was stuck on:
But such a proof uses only finitely many axioms. So there are finitely many points such that just considering the subgraph on those points is enough…
From the fact that there’s (say) a ZF disproof of the existence of a k-coloring of the plane, we can’t immediately conclude that there’s a finite counterexample—but I see that we could conclude that from a disproof in a propositional “logic” with uncountably many axioms, one for each neighboring pair of points.
Greg, is your argument still using the Axiom of Choice, in the guise of the assumption that the vertices in the infinite graph are well-ordered? Is Oscar’s argument preferable for not needing AC? Or are the two arguments basically equivalent?
Also, can we argue from here that the Hadwiger-Nelson problem is Π1? For that, we would need not only that there’s a finite subgraph witnessing non-k-colorability, but also that the coordinates of the points are describable using only finitely many bits.
Comment #12 April 11th, 2018 at 12:20 pm
Thanks so much for posting about this, Scott. Yesterday I fixed the bug that led me to believe I had a 1567-vertex solution and reran my deleteability-seeking code overnight ; the result is that I now have a 1581-vertex graph (i.e., four vertices can be removed from the graph that various people verified yesterday) and I have stuck a revised manuscript on the arxiv which should go live later today.
Comment #13 April 11th, 2018 at 12:39 pm
My proof also uses Choice. You need it to prove the Completeness Theorem that every consistent theory has a model.
I’m not sure if Choice is actually necessary or not to prove that you can always find a finite counterexample when one exists, but it is necessary in similar colouring problems. Consider trying to colour a circle with irrational perimeter. Each point lies in an infinite chain which you can two-colour by alternating red and blue. But to colour every such chain you have to use Choice to pick a starting point for each of them. Without Choice it can require infinitely many colours.
Comment #14 April 11th, 2018 at 12:49 pm
Scott:
Not quite exactly like that. A disproof in ZF is also a disproof in ZFC, which does imply a finite counterexample. A proof that the coloring can’t be constructed in ZF (which might be what you meant) might not yield a finite counterexample, because the question could be independent of ZF.
There are many variations of this problem depending on the desired quality of the coloring, or the quality of the obstruction. For instance you could ask for a measurable coloring, and optionally also allow a measure zero set of unit distance pairs that are the same color.
That’s right. In fact my guess is that this graph coloring theorem is equivalent to the axiom of choice. For instance, if the graph is a forest of twigs, then finding a 2-coloring is exactly the binary choice case of the axiom of choice. My naive guess is that that’s already all of AC. Note that you can do rather fancier things with other infinite graphs of your choosing; you can make gadgets in the spirit of NP-completeness arguments.
I wasn’t quite sure what Oscar was saying. I think that his argument rather sidesteps question of whether you need AC.
That’s certainly true, because any finite counterexample graph has an algebraic position.
Comment #15 April 11th, 2018 at 1:32 pm
[…] Amazing progress on longstanding open problems 5 by weinzierl | 0 comments on Hacker News. […]
Comment #16 April 11th, 2018 at 1:43 pm
Scott, the following might help clarify the use of choice in Oscar and Greg’s proofs. Instead of using compactness for propositional logic, as Oscar did, we can just use compactness for first order logic (for instance, our language can have a constant for each real number and a binary relation telling us when they are unit distance apart and a unary relation for each of the k colors). The key point is that the standard proof of compactness for first order logic uses choice only to ensure that the language is well-ordered. This is used to complete (a Henkinized version of) the theory (by doing transfinite induction on the sentences in the language). Greg’s proof assumed a well-ordering of the reals, which also gets you compactness for the language that Oscar used in his proof. And actually, if you unravel the usual proof of compactness for first order logic in this specific instance, you’ll get something that looks a lot like Greg’s proof.
I don’t know exactly how much choice is needed for this theorem. It is not, as Greg claims, full choice. This is because Compactness for first order logic with arbitrary languages is strictly weaker than AC (and does not even imply countable choice). See the following stack exchange thread for more details:
https://math.stackexchange.com/questions/402543/is-the-compactness-theorem-from-mathematical-logic-equivalent-to-the-axiom-of
Greg, it is not true that binary choice implies choice (and as I mentioned above, this theorem about graph colorings is also strictly weaker than AC). In fact, binary choice does not even imply a choice function for every family of sets with three elements each. A curious fact is that it does imply choice functions for all families of sets with 4 elements each, but not for any other number!
Comment #17 April 11th, 2018 at 2:02 pm
A place where the reduction from the infinite problem to the finite problem is not known is for the Borsuk’s problem. If f(d) is the smallest number of sets of diameter < 1 needed to cover every set of diameter 1 in $R^d$, and g(d) is the same but for finite sets then I dont know if f(d)=g(d). It is quite reasonable to think that these quantities are not the same.
Comment #18 April 11th, 2018 at 2:46 pm
Greg #14: The idea of using 3SAT gadgets works immediately and shows that “Every graph such that every finite subgraph can be 3-colored, can be 3-colored” implies “Every infinite 3SAT instance (i.e. with a set of variables and a set of clauses) such that every finite subset can be solved, can be solved” which itself implies the axiom of choice for finite sets.
For the first reduction, we take the gadget-based proof of the reduction from 3SAT to 3-coloring essentially verbatim – start with a triangle to define the three colors, then add gadgets for each variable and gadgets for each clause.
For the second reduction, there is an obvious way to write it as an infinite SAT instance. The SAT to 3SAT reduction relies on ordering the variables in each clause, but we can simply take the union of all the circuits obtained from all possible orderings.
It is not clear whether we can handle the axiom of choice for infinite sets, however.
Comment #19 April 11th, 2018 at 3:24 pm
Wait, so how general is this verification result (assuming the needed cryptographic assumptions)? Naïvely I would just assume it makes sense for search problems (incorporating language and promise problems into there) but the abstract makes it sound like it somehow works for sampling problems too. Is that right? It’s not entirely clear to me what it would mean to verify those… meanwhile the paper itself seems to do the usual thing of only talking explicitly about language problems.
Comment #20 April 11th, 2018 at 3:30 pm
@Aubrey
What are the chance that similar methods could be used to produce counterexamples for five or six colours? (Assuming that such counterexamples exist)
Comment #21 April 11th, 2018 at 4:30 pm
By the way, does anyone here know if anyone looked at Hadwiger-Nelson problem restricted to rational points? My naive guess would be that something like De Grey’s construction could be appropriately modified so that every point has rational coordinates, but it isn’t obvious from the construction.
Comment #22 April 11th, 2018 at 5:22 pm
Right. I wanted to give an argument that was better than just restating the theorem via a citation. I suspect that this graph coloring result is actually equivalent to compactness of first-order logic. It seems similar to the theorem that k-coloring is NP-complete for k at least 3.
That’s interesting! The Math Stackexchange seems to sum up the situation.
Comment #23 April 11th, 2018 at 6:20 pm
@Oscar: that is absolutely a major motivation for my suggesting that the search for simpler 5-chromatic examples is an attractive Polymath project. The simpler we get, the more comprehensible the examples are likely to be, which may lead to strategies for seeking a 6-chromatic example. If you agree, please say so at the discussion thread:
https://wordpress.com/read/blogs/8741421/posts/1139
Comment #24 April 11th, 2018 at 6:21 pm
@Joshua: yes, this has been looked at, and in fact it is quite easy to show that the rational plane is bipartite. Things get more challenging in higher dimensions (surprise).
Comment #25 April 11th, 2018 at 11:20 pm
Sniffnoy #19:
I’ll disclaim that I don’t yet understand most of the paper. The primitive that Mahadev constructs allows a verifier to certify that the prover performs specific Pauli measurements on their state and reports the results.
In order to verify a BQP computation, you use that BQP is in QMA with efficiently-prepared ground states and that you can convert the Hamiltonian to XZ-form. So the measurements that the verifier asks are random terms from the Hamiltonian, and the prover’s answers allow to accurately measure the energy of the Hamiltonian with respect to the state. The details are in Section 8 of her paper.
There certainly *exist* sampling problems which can be verified by this protocol, for example:
“Given a state which is the unique ground-state of a gapped local XZ-Hamilonian H, output the results of some specific XZ measurements on that state” (We need to use a ground state of a gapped hamiltonian so that estimating the energy of the hamiltonian characterizes the state.)
It seems plausible that one could capture some fairly general sampling problems in this framework, but I’m not sure.
Comment #26 April 12th, 2018 at 12:48 am
Sniffnoy #19: I think there’s no problem at all doing arbitrary sampling problems with the earlier protocols of Broadbent-Fitzsimons-Kashefi and Aharonov-BenOr-Eban. But with Mahadev’s protocol, I’m really not sure; good question! (Was about to say so, but Jalex beat me to it.) I’ll email Urmila to ask.
Comment #27 April 12th, 2018 at 12:57 am
Everyone: The fact that the Erdös-deBruijn theorem requires the Axiom of Choice means that there’s still a little corner of set-theoretic weirdness in the Hadwiger-Nelson problem, which is really what my question was trying to get at. Namely: it’s conceivable, even if unlikely, that someone might prove (for example) that the plane had a chromatic number of 6, but only via some nonconstructive coloring that required AC and couldn’t be visualized.
Comment #28 April 12th, 2018 at 12:58 am
The De Bruijn–Erdős theorem depends on the axiom of choice, but for this special case, it seems easy to show that, if a finite witness exists then the coordinates of the vertices can be chosen to be algebraic numbers (just write polynomial equations asserting unit distance corresponding to the edges of the graph, and choose any point of the resulting algebraic variety). In particular, the witness has a finite description. So, maybe for this special case we can somehow prove the De Bruijn–Erdős theorem without the axiom of choice?
Comment #29 April 12th, 2018 at 1:03 am
Vanessa #28: Yes, excellent question! I hereby announce that as whatever is the local Shtetl-Optimized equivalent of a polymath project. The place to discuss it: this comment section.
Comment #30 April 12th, 2018 at 1:18 am
I don’t know that it’s all that unlikely! It could well have a connection to Banach-Tarski-type questions. For instance, how about a coloring of the real numbers by countably many colors, with the property that if a-b is rational, then a and b have different colors?
Comment #31 April 12th, 2018 at 1:23 am
Scott, Jalex: I’m just confused about what it means to verify a sampling problem in the first place. Like, there is some set of computations you can do on the information it sends you that lets you determine that the value it ultimately spits out really was drawn from a particular distribution? Like… let me put it this way. Is this something we could do with a classical prover, have it do sampling problems in a verifiable way? Like imagine the sampling problem is just “choose 0 or 1 uniformly at random” — we can have verifiable sources of randomness, then (provided we have a true RNG in the first place)? Like there are computations you could do that let you say “Yes, it may seem unlikely that after 1000 runs the RNG has only spit out 1s, but we’ve verified it is in fact sampling from the uniform distribution on {0,1}?” Even if we really do need a quantum prover for this, that’s pretty surprising to me.
Also thought: If this works for both sampling and search, does that mean it works for the unified “sample from some distribution which is in this convex set which depends on the input” notion of problem I suggested here? 🙂
Comment #32 April 12th, 2018 at 1:45 am
Sniffnoy #31: Well, in the case of the earlier, information-theoretic protocols (BFK and ABE), the verifier can simply enforce that the prover is carrying out the quantum computation that it expects, gate by gate, and therefore that whatever the prover outputs is a sample from the desired probability distribution. (Note that it’s important here that the verifier isn’t just examining the final output, but is interacting with the prover in every step of the computation.) So, that gives a clear target that one could aim for in the case of purely classical communication.
Comment #33 April 12th, 2018 at 1:47 am
Relevant to the axiom of choice issue:
A related problem is finding the Borel chromatic number of the plane, which means the smallest number of colors that suffices to color the plane so that for each color, the set of points of that color is Borel (and no 2 points unit distance apart have the same color). Not using the axiom of choice isn’t quite the same thing as getting Borel sets, but “Borel” is a good notion of having an explicit description, so it’s pretty close.
The Borel chromatic number of the plane was already known to be at least 5, and the chromatic number of the plane was suspected by many to be 4. There are Borel graphs whose chromatic number and Borel chromatic number are known to be different. For example, the chromatic number of the circle (with two points connected iff they are 1 radian apart) is 2, but it does not admit a Borel 2-coloring. (In fact, it was even known that there was no Lebesgue measurable 4-coloring of the plane, and no Lebesgue measurable 2-coloring of the circle.)
Comment #34 April 12th, 2018 at 2:10 am
Joshua Zelinsky #21, rational points would be a totally (I was about to say radically) different problem. For example, there is no unit equilateral triangle in the rational plane, by simple algebra. I think that means that 2 colors suffice but maybe I’m missing something.
Comment #35 April 12th, 2018 at 2:30 am
Scott #32: So I guess then fundamentally what’s going on here is that we trust that measuring a quantum state really does produce a random result according to the Born rule, i.e. we have a physical mechanism for enforcing true randomness, assuming the computation part was carried out correctly; whereas if we were to do the analogous classical thing, verifying a probabilistic computation (where we assume all sampling is postoponed to the end), even if we verify the computational part we don’t then have any simple verifiably random physical way of sampling from our resulting distribution afterwards? (Other than by setting up quantum states and measuring them, I guess! 😛 ) Is that all that’s going on then?
Comment #36 April 12th, 2018 at 3:28 am
Sniffnoy #35: Well, in all of these verified QC protocols, you do presuppose the validity of quantum mechanics. And yes, QM does give you powerful tools to verify that an outcome is actually random, which were fundamentally impossible in the classical world, since there you always could’ve subbed in a PRG. This is exactly what gets exploited in, for example, the protocols of Vazirani and Vidick and others for certifiable randomness generation using Bell inequality violation, and the very recent work of Brakerski et al., and some closely related work that I’ve been doing myself (paper hopefully out in a month or so).
Comment #37 April 12th, 2018 at 4:11 am
The assertion that the chromatic number of the plane is 7 is (equivalent over ZFC to) a Σ₁ statement of arithmetic, because it asserts the existence of a unit distance graph which is not 6-colorable, and the existence of such a graph over the reals can always be witnessed over the real algebraics (viz., the algebraic closure of ℚ inside ℝ). So if the correct chromatic number is 7, then this fact is provable. See §5 (and in particular ¶5.4) of my note https://arxiv.org/abs/1509.07023 for details.
Comment #38 April 12th, 2018 at 4:29 am
Gro-Tsen #37: Thanks! But as discussed above, it still seems to me that there’s an asterisk on that statement, which is that conceivably the plane could be 6-colorable but only in a non-constructive way that required AC. If so, then there clearly wouldn’t be any finite obstruction to a 6-coloring, but a person who denied AC might still say that the chromatic number was 7.
Comment #39 April 12th, 2018 at 6:58 am
If we don’t assume AC, then this raises the meta-question of which question we should be asking: “what is the smallest number of colors needed to color the plane so that no two points at distance 1 have the same color?” or “what is the smallest number of colors needed to color any finite subset of the plane <etc.>?” In other words, there is not one Hadwiger-Nelson problem/number but two. And I submit that the latter is, in fact, more interesting (because it is effectively a finistic problem, and works around the whole problem of AC by, in effect, taking Erdős-de Bruijn as a definition).
If the chromatic number of the plane χ is 7 in some model of ZFC then it is 7 in every model of ZF (the statement χ=7 is provable in ZF, with the stronger definition of the problem as per the above paragraph). So, while it is indeed conceivable that χ takes the values 5,6,7 in various models of ZF, or indeed that χ takes the values 5,6 in various models of ZFC, de Grey’s new result makes it much more plausible now that χ=7 is provable with no room for logical shenanigans.
Comment #40 April 12th, 2018 at 8:28 am
Scott, re #27 and #38, I must agree with Alex Mennen here. This is such a graph where I would expect that you may need a strange coloring requiring AC. I don’t understand why you would think that unlikely, unless it’s because you believe the chromatic number is 7.
Comment #41 April 12th, 2018 at 9:34 am
Gro-Tsen #39 and jonas #40: Indeed, I suppose my current bet would be that “χ=7 is provable with no room for logical shenanigans.” But I think part of understanding a math problem is knowing the space of shenanigans that are a-priori possible, whether or not actually realized.
Comment #42 April 12th, 2018 at 10:03 am
Sniffnoy: Urmila confirmed by email that, in contrast to the situation with the ABE and BFK protocols (which just follow a quantum computation step by step), she does not know how to handle arbitrary sampling problems with her new protocol, because sampling problems don’t naturally mesh with the circuit-to-Hamiltonian construction she uses. She says “Jalex’s answer [#25] was perfect.”
Comment #43 April 12th, 2018 at 12:43 pm
[…] of some of the new results is over Dustin G. Mixon’s blog Short, Fat Matrices. A post over Shtetl Optimized describe the new development along with another important development on quantum computation. Let […]
Comment #44 April 12th, 2018 at 1:25 pm
Scott: Interesting, thanks! It does work for search problems though I assume? Which is basically the usual sort of general problem?
Comment #45 April 12th, 2018 at 2:51 pm
Sniffnoy #44: Unless I’m mistaken, my general equivalence between sampling and searching implies that if it works for search problems, then it works for sampling problems as well. Which would mean that it also has to be open whether it works for search problems.
Comment #46 April 12th, 2018 at 3:07 pm
Just a correction: my earlier statement
should have the word “standard” inserted between “some” and “model of ZFC” — i.e., if the chromatic number of the plane χ is 7 in some standard model of ZFC then it is 7 in every model of ZF.
Comment #47 April 12th, 2018 at 3:07 pm
Oh geez so it’s really only decision problems then? If it can’t even do search problems then it’s not really “any computation”, it seems to me… (still a big advance, obviously!)
Comment #48 April 12th, 2018 at 9:27 pm
Scott #42:
I thought about this more with Thomas Vidick. It seems like Urmila’s protocol can verify sampling problems, though there might be something subtle that we missed.
Any problem in sampleBQP can be solved by applying a quantum circuit and then measuring in the computational basis. This computational basis measurement is already of XZ-form, so all that remains is to encode the final state as the unique ground state of a local hamiltonian. This can’t be done *exactly* in general, but it can be done approximately with arbitrary inverse-polynomial approximation factor using a trick that I first learned of in a paper of Nirkhe–Vazirani–Yuen. (https://arxiv.org/abs/1802.07419) The trick is to take the circuit, append a whole bunch of identity gates, and then take the history state of this padded circuit. The history state is approximately a tensor product between the clock register and the desired state.
Comment #49 April 13th, 2018 at 5:27 am
Jalex #48: Thanks!! (I actually know that padding trick from other contexts, and I wondered why you couldn’t just make a local Hamiltonian that encodes a sampling problem, but I understand Urmila’s protocol so poorly right now that I defer to those who know it better…)
Comment #50 April 13th, 2018 at 6:30 am
Scott: you should update the paragraph “As de Grey and a commenter pointed out to me, this is the de Bruijn-Erdös Theorem from 1951. But the proofs inherently require the Axiom of Choice. Still not sure about the Π1 part.” to make it clear that the Π1 part has been answered if you assume choice.
Perhaps you also want to ask: Can the Borel version of Hadwiger-Nelson be reduced to a Π1 problem? Or: Can Hadwider-Nelson be reduced to a Π1 problem in ZF+AD or some other extension of ZF that rules out “weird” sets coming from AC?
Comment #51 April 13th, 2018 at 7:51 am
Aubrey de Grey #23: Simpler 5-chromatic examples might help to find a 6-chromatic example, but consider the following. If there is a 6-chromatic example, then there is a finite subgraph of the plane whose vertices all have degree at least 5. Now there is a fairly simple example of a finite subgraph of the plane whose vertices all have degree at least 4: the graph K from your paper but with the black vertices removed. This is a 37-vertex graph, of which 24 vertices are degree 4. Does this graph help us if we want to find a finite subgraph of the plane whose vertices all have degree at least 5? Maybe, but to me it seems that there are too many degree 4 vertices, and it is not at all clear how to expand the graph so as to even decrease the number of degree 4 vertices! And as far as I can tell, the graph G in your paper also has plenty of degree 4 vertices, and so would any reduction of it.
Comment #52 April 13th, 2018 at 11:11 am
Many thanks for this observation Dacyn. Please visit the Polymath discussion page and add your thoughts there:
https://wordpress.com/read/blogs/8741421/posts/1139
It actually turns out to be relatively easy to get to a minimum degree of 5 – indeed, my 1345-vertex graph M is an example Nonetheless, it would be very interesting (and yet I know of no work on this) to determine whether there is a maximum possible minimum degree, or even how the minimum size of a UD graph of minimum degree n rises with n. Such questions could, I think, very powerfully inform the search for 6-chromatic cases.
Comment #53 April 13th, 2018 at 1:30 pm
Aubrey de Grey Comment #52:
The d-dimensional cube is a unit-distance graph
https://mathoverflow.net/questions/132763/maximal-minimum-degree-of-unit-distance-finite-graphs
which already gives a lowerbound of log n for the minimum degree.
Then again, you might ask if there are such examples which are far from being bipartite.
Comment #54 April 13th, 2018 at 5:13 pm
Scott, Jalex: So I’m guessing it works too for search problems after all, then? Nice!
Now I have to wonder about problems that generalize sampling and search… 🙂 (I’d be surprised if it didn’t also work in that generality if it works for sampling and for search.)
Comment #55 April 13th, 2018 at 5:28 pm
As the MO solution explains, the hyperbcube idea can be repeated. Given any finite collection of graphs with unit-distance realizations, their Cartesian product also has a unit-distance realization. This can be quite far from bipartite, but without extra edges it does not boost the chromatic number.
Comment #56 April 13th, 2018 at 6:39 pm
Edouard, Greg: ah yes, so the question is of course very boring as stated. I guess there might be ways to make it interesting by imposing this or that required property for the graph, but I can’t immediately think of a nice one.
Comment #57 April 14th, 2018 at 2:47 am
Is it really such a great idea to discuss the chromatic number of the plane and quantum computing in the same roll? Scott, save us!
Comment #58 April 14th, 2018 at 3:38 am
Domotor #57: I sometimes enjoy weird mashups.
Comment #59 April 14th, 2018 at 6:13 am
Suppose we declare a “quantum colouring” with d colours to be an assignment of a unit vector in C^d to each vertex such that adjacent vertices are orthogonal. Are there graphs which can be quantum coloured in fewer colours than classically?
Comment #60 April 14th, 2018 at 10:51 am
Oscar #59: Great question! There’s now a whole little literature on the subject of “quantum chromatic numbers” of graphs—see for example this paper—and there are indeed graphs known for which the quantum chromatic number is less than the classical value.
However, a warning: in this literature, people mean something a bit different by “quantum chromatic number” than the “natural/obvious” definition that you gave: they mean the minimum number k of colors such that a verifier can be “convinced” that the graph is k-colorable, via a two-prover interactive protocol where the provers have to answer with the same color when asked about the same vertex or with different colors when asked about adjacent vertices, but the provers are now entangled with each other.
What you call a “quantum coloring” is called an “orthogonal representation of a graph” in this literature. The minimum dimension of any orthogonal representation is a lower bound on the quantum chromatic number, but they’re not the same concept (does anyone know if we know an example that separates them?).
In any case, one can indeed now ask about the quantum chromatic number of the plane, as well as the orthogonal representation dimension of the plane! A first step would be to prove that these are at least 4, and then (by analyzing Aubrey’s construction more closely) to prove that they’re at least 5. I’d be shocked if either of these numbers turned out to be different from the ordinary chromatic number of the plane—the examples of graphs that separate quantum from classical chromatic number are weird and constructed for exactly that purpose—but hey, one can ask. 🙂
Comment #61 April 14th, 2018 at 11:31 am
The Moser spindle shows that the plane does not have a 3d orthogonal representation, because in 3d the two vertices at opposite ends of a diamond have to be proportional.
Comment #62 April 14th, 2018 at 11:37 am
Lior #61: Good observation, thanks!
Comment #63 April 14th, 2018 at 11:51 am
It’s worth noting the the papers 1,
2 of Shelah–Soifer in which they construct graphs in the spirit of the unit distance graph whose colouring numbers are independent of ZF.
Comment #64 April 14th, 2018 at 12:39 pm
Dacyn #15, Aubrey #52, The maximum known minimum degree for unit distance graphs is $n^{c/\lohlogn}$ by Erdos construction for his famous unit-distance problem. The construction is (to the best of my memory) by looking at points (i,j),i,j\le \sqrt {n} and choosing as edges the distance which occur most number of times. (I suppose the distance is some constant times \sqrt n.) This is conjectured to be best possible.
I am curious (but this might be well known) about the chromatic number of this and related graphs. (Just asked about it in the polymath project.)
Comment #65 April 14th, 2018 at 12:47 pm
Aubrey de Gray #52: If M doesn’t have any degree 4 vertices, I guess that means G doesn’t either, right? I suppose that is a good sign in terms of being useful for finding a 6-chromatic example. Anyway, I guess my intuitions were wrong here. Good luck with the Polymath project!
Comment #66 April 14th, 2018 at 5:53 pm
There is another way of looking at the Hadwiger-Nelson problem, especially in light of Lior’s remark and reference that some similar problems can indeed be independent of ZF. You can define the local chromatic number of a graph G to be the supremum of the chromatic numbers of all of its finite subgraphs. Now, the de Bruijn-Erdös theorem says that, if the supremum is finite, it simply is the chromatic number of G itself, in ZFC. (Or, in light of Patrick’s remarks, ZF plus the compactness theorem, which I think Wikipedia is telling me is equivalent to ZF plus ultrafilter.) Still, even if it’s not the chromatic number of all of G, you can study the local chromatic number. After all, Aubrey de Grey’s construction is directly about the local chromatic number of the Hadwiger-Nelson graph.
I’m wondering whether anyone believes that the local chromatic number of the Hadwiger-Nelson graph could be independent of ZF as well. Now, I think Scott’s point about Π1 problems (although I don’t know that particular terminology) is that any lower bound that is actually true (in some standard sense) has a proof given by finding some explicit subgraph. So, I’m wondering what the chance is that there is no finite graph like Aubrey’s with chromatic number 6, but that we’ll never be able to prove that it doesn’t exist. Or maybe that we can prove to ourselves that it doesn’t exist, but some popular axiom systems (Peano or ZF) are too weak to prove it. Do the Soifer-Shelah papers also imply something about this?
As it stands, we have a simple proof (indicated in the figure) in ZF, and I guess in Peano arithmetic as well, that no such finite graph exists with chromatic number 8.
Comment #67 April 15th, 2018 at 2:44 am
Greg #66, I think I can answer some of your questions.
First, one small point: Peano arithmetic is a theory in the language of the natural numbers, so it does not have any way to talk about or prove things about the real numbers. One appropriate setting (which is still quite close to things like PA) for things like the Hadwiger-Nelson problem is second order arithmetic (where we can quantify not just over natural numbers, but also sets of natural numbers). In this setting we can talk about real numbers as e.g. Dedekind cuts.
Second, yes the figure showing that the local chromatic number of the plane is at most 7 is valid in ZF and also in all but extremely weak theories of second order arithmetic.
Third, a sentence in first order logic is called Π_1 if the only quantifiers that appear in it are universal (although typically, bounded existential quantifiers are also allowed). More properly, this should be called Π^0_1 where the superscript indicates that the sentence is first order. A sentence in second order logic where the only second order quantifiers are universal is called Π^1_1 and so on. What Scott is asking is if the Hadwiger-Nelson problem is equivalent to a Π^0_1 statement in the language of the natural numbers. Note that a sentence being Π^0_1 in set theory is pretty different than a sentence being Π^0_1 in arithmetic (because in set theory this already means we can quantify over all sets and not just over natural numbers). The reason Scott is asking this is because Π^0_1 sentences over the natural numbers have the interesting property that if they are independent of PA (or whatever sufficiently strong theory you fancy) then they are actually true. This is because a Π^0_1 statement being false is equivalent to the existence of a counterexample satisfying a statement where all quantifiers are bounded and PA is strong enough to prove all true statements with only bounded quantifiers (in fact, much less than PA is needed).
Fourth, the de Bruijn-Erdos theorem (along with the observation about finite unit-distance graphs being always represented in the plane by algebraic numbers) shows that in ZFC, the problem of showing that the chromatic number of the plane is greater than, say, 6 is equivalent to a Π^0_1 statement of arithmetic (though note that this is not quite the same as the Hadwiger-Nelson problem). But without choice (or more accurately, without the ultrafilter lemma), it is at least not obviously equivalent to a Π^0_1 statement. On the other hand, your proposed “local chromatic number” can be shown to be equivalent to a Π^0_1 statement even in a very weak theory. So if someone were to show this “local” version independent of your favorite theory of second order arithmetic (or ZF or whatever) then they would have simultaneously resolved the problem itself in whatever stronger system they used to prove the independence. Of course, it is also possible for it to be independent of ZF but independent that it’s independent, etc.
Fifth, the Shelah-Soifer papers don’t say anything about the local version. In fact, they show that for some graphs, the local version and the global version can disagree when choice is not present (in their case, specifically in a model without choice and where all sets of reals are Lebesgue measurable).
Comment #68 April 15th, 2018 at 5:00 am
Scott #60:
I’ll use “orthogonal rank” to refer to “the smallest dimension in which there is an orthogonal representation”.
This recent paper by Laura Mančinska and David Roberson gives separations between quantum chromatic number and orthogonal rank. They need only three colors and separate in both directions! That is, they find one graph with quantum chromatic number 3 but orthogonal rank > 3 and another graph with orthogonal rank 3 but quantum chromatic number > 3.
Comment #69 April 15th, 2018 at 5:27 am
Greg #66: I think it would be pretty surprising if an upper bound on the local chromatic number could be proven in ZF (or some stronger theory) but not in PA. There are plenty of Π_1 statements that have this property, but they are usually pretty artificial.
For a similar reason, I think it would be surprising if the statement could be proven to be independent of ZF (because that would mean it could be proven true in a slight strengthening of ZF, but not in PA). However, I wouldn’t be particularly surprised if the statement was in fact independent of ZF (not that we would have any way of finding out that this is the case, if the independence is unprovable).
Patrick #67: To formalize in PA, you use the fact that the coordinates of the points in any counterexample can be assumed to be algebraic.
Comment #70 April 15th, 2018 at 8:42 am
Jalex #68: Thanks—I hadn’t seen that paper, and it’s a treasure trove of examples and intuitions about quantum chromatic number!
I confess that I was totally confused about how orthogonal rank could possibly be greater than quantum chromatic number, as this paper claims, since can’t we get a k-dimensional orthogonal representation by taking a quantum k-coloring and then picking any one color? And indeed, the Cameron et al. paper had a result (Proposition 7) that seemed to be saying that quantum chromatic number is an upper bound on orthogonal rank, as I’d expect.
On closer examination, though, the upper bound on orthogonal rank is given by “rank-1 quantum chromatic number”—i.e., quantum chromatic number when we restrict ourselves to projectors of rank 1. I had thought that those were the only kind of projectors ever allowed.
So then, this must be the resolution: if you want quantum chromatic number to be less than orthogonal rank, you do so using higher-rank projectors (though I confess I still don’t have any intuition for it).
Comment #71 April 15th, 2018 at 10:13 am
Patrick and Dacyn – Thanks for your comments!
Comment #72 April 15th, 2018 at 11:11 am
Dacyn #69: Your comment says how to formalize the “local chromatic number” in PA using a fact about it that is provable in ZF. My point was that you can’t formalize the original Hadwiger-Nelson problem in first order arithmetic unless you use something like the de Bruijn-Erdos result to get an equivalent statement in first order arithmetic. But it is not obvious (and maybe not even true) that ZF proves the Hadwiger-Nelson problem is equivalent to a first order sentence of arithmetic, so it doesn’t seem fair to say we can talk about it in PA.
Comment #73 April 15th, 2018 at 1:03 pm
Sure, you can’t even define the entire Hadwiger-Nelson graph in PA, much less prove anything about it.
Still, what I meant in this case was finding (in PA) the maximum chromatic number of every finite graph which is realizable in the plane with unit distances. Those graphs evidently can be defined in PA.
Comment #74 April 15th, 2018 at 1:14 pm
Patrick #72: Your comment #67 was a response to Greg #66 who was talking about the local chromatic number, so I assumed you were as well. Sorry for any confusion!
Comment #75 April 15th, 2018 at 1:26 pm
Meanwhile here is something else interesting. The Hadwiger-Nelson problem for the hyperbolic plane depends on the specific choice of the edge length ℓ. It seems that the known lower bounds are bounded as a function of ℓ, but the known upper bounds grow linearly in ℓ.
Comment #76 April 15th, 2018 at 4:33 pm
Scott #70:
I don’t have a lot of intuition for strategies in graph-coloring games (indeed, I think one of the main theses of that paper is that almost nobody does), but I think that the idea of using projectors of rank >1 should not be too surprising. Already this is necessary for winning the Magic Square game.
For anybody interested in the question of the quantum chromatic number of the plane, section 4.2 of the Mančinska-Roberson gives some pretty concrete tools for proving that the quantum chromatic number of a graph is at least 4. At a first glance, it seems like the Moser spindle (the minimal unit distance graph of classical chromatic number 4) is too small to analyze with these tools, but that some kind of sum of a few Moser spindles may be enough.
Comment #77 April 17th, 2018 at 2:38 am
[…] on the ArXiv The chromatic number of the plane is at least 5, on Jordan Ellenberg’s blog Amazing progress on longstanding open problems, on Scott Aaronson’s blog The chromatic number of the plane is at least 5, on Dustin […]
Comment #78 April 18th, 2018 at 8:18 am
Pareidolia! Have a look at Figure 9 in de Grey’s paper and let me know if you also see a face there? Here’s a screenshot:
https://screencast.com/t/oTjOvOZy
Or is someone trying to send us a hidden message? 😉
Comment #79 April 18th, 2018 at 4:46 pm
asdf # 34,
That’s not in general enough. One can have graphs without triangles with high chromatic number. The easiest example is the Grötzsch graph which is triangle free and has chromatic number 4. https://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph
Comment #80 April 18th, 2018 at 4:48 pm
Aubrey De Grey # 24,
Ah yes, so that makes the rational case of the plane not interesting.
Comment #81 April 19th, 2018 at 2:06 am
Question I’m wondering about now: Given an abstract graph, how does one determine whether it can be realized as a unit-distance graph or not?
Comment #82 April 19th, 2018 at 2:50 am
Joshua Zelinsky #79, asdf #34:
Let me just expand on Josh Zelinsky’s point here and point out that in fact much more is true. We can define the girth of a graph to be the size of the smallest cycle (if there are no cycles, the girth is ∞.)
Obviously, a graph with girth ∞ is necessarily 2-colorable. But for finite girth, for graphs that do indeed contain a cycle, Erdos showed that you can find graphs with arbitrarily high girth and arbitrarily high chromatic number.
…except that actually, that’s only true if when we say “arbitrarily high chromatic number”, we’re only talking about finite possibilities for the chromatic number! I was implicitly restricting to finite graphs above. But if we want to allow infinite graphs, and if we thus similarly allow the chromatic number to be infinite, this is no longer true: It’s a theorem of Erdos and Hajnal that any graph with no 4-cycles is countably colorable!
(OK, the theorem is actually much stronger than that — what it actually says is, if a graph is not countably colorable, then it contains, for every n, a copy of the complete bipartite graph K_{n,aleph_1}. But in particular that means it contains a 4-cycle. 🙂 )
However, with a modification, the theorem becomes true for infinite chromatic numbers as well. We can define the odd girth of a graph to be the size of the smallest odd cycle (so the odd girth is ∞ if and only if the graph is 2-colorable). Restricting ourselves once again to graphs of finite odd girth, graphs that do indeed contain an odd cycle, it is indeed the case (and yes this is Erdos again 😛 ) that you can find graphs of arbitrarily high odd girth and arbitrarily high chromatic number — even if the chromatic number is allowed to be an infinite cardinal.
In particular, there are triangle-free graphs with arbitrarily high chromatic number, even if the chromatic number is allowed to be an infinite cardinal. 🙂
(The construction for this last theorem isn’t too bad, either! IIRC it goes as follows: Say you want a graph with chromatic number at least X and odd girth at least 1+2n. Take Y=℘^n(X) (i.e., take the power set of X, iterated n times), and put a total order on it (obviously using choice there, but interestingly not its full strength; it doesn’t need to be a well-order). Turn Y into a directed graph by drawing an edge from a to b if a<b. Now, given a directed graph G, we’ll define its directed line graph, L(G), to be the graph whose vertices are the edges of G, and for edges e and e’ of G, we’ll draw an edge from e to e’ in L(G) if the head of e equals the tail of e’. We’ll take L^n(G). Then the underlying undirected graph of this has the required chromatic number and odd girth!)
Comment #83 April 19th, 2018 at 6:14 am
Sniffnoy #81: That’s a great question, which I’d wondered about too! Well, the complexity is no greater than that of the Existential Theory of Reals, which is in PSPACE. It would be nice to have a better upper bound though. 🙂
Comment #84 April 19th, 2018 at 10:51 am
Ok. So we know that if we restrict the points of our graph to the rationals then the coloring number is 2. Aubrey De Grey’s graph and the subsequent smaller graphs all have coordinates living in extensions of Q. Also note that s observed by a few people every unit distance graph can be embedded so that its’s coordinates are in the algebraic closure of Q). So what is the smallest algebraic extension of Q where we can get graphs with 5 colors? More generally, if we restrict our coordinates in the plane to be in some field F where F is a real algebraic extension Q, what is the coloring number of that graph? This looks like another possible metric for how complicated a 5-color unit distance graph is, where instead of looking at reducing the number of vertices directly we could also look at trying to reduce the size of the extension our graph lives in.
Comment #85 April 19th, 2018 at 1:36 pm
Scott #83: Oh huh. Yeah I forgot for a moment that theory of reals / real algebraics is decideable and therefore was confused how you’d even do it at all given that it seemed like degrees could potentially get arbitrarily large. But yeah, that totally does it. I didn’t know at all about that bound on the purely existential theory though! Interesting, thanks…
Comment #86 April 19th, 2018 at 5:23 pm
Sniffnoy #85,
> But yeah, that totally does it. I didn’t know at all about that bound on the purely existential theory though! Interesting, thanks…
Did this not come up in the infamous conversation I had with you when Ettienne and I got back that one time at PROMYS, or did we only discuss the complexity of the general decidability of questions involving the reals?
Comment #87 April 19th, 2018 at 9:10 pm
No that was only about the general (first-order) theory of the reals pretty sure. 😛
Comment #88 May 9th, 2018 at 7:30 pm
Solved it in about 30 seconds. If it needs 5 pens for 1581 dots then for more dots up to infinity it is no more than 5.
Please call this the Peter Wilson Proof dated 5/10/18 at 7 in the morning AE standard time & I hope no one else has done it yet!
Here goes;
Draw two circles around one of the points at the center such that they could cross the outer edges of the dots and assume all the dots are filled in.
At the outer two edge rows of dots, the 2nd most outer being say red and blue alternating, and the outer one being green and yellow alternating then this can go on layer by layer indefinitely.
The circle diameters approach each other but can never meet.
Until (and if) there needs to be an odd number of dots in the outer circle layer. Then there are two colours the same next to each other, hence the need for 5 colours. Ok this matches the earlier proof.
Now this fifth colour can be used on the two outer layers of dots if both contain coincidentally odd numbers of dots.
What happens when the fifth colour is adjacent in the two outer layers? You just rotate the layers slightly and the colours don’t coincide. Now it doesn’t matter if the two outer layers of dots are odd or even in total which is ALWAYS the case. The fifth colour can ALWAYS be offset and only needs to be used at most once in a layer of dots.
Ok so now overlay another set of dots. if one or two don’t coincide then none ever will be exactly 1 unit away from the first set. If two coincide then it is the same set. If only one coincides then exactly no others can ever coincide. Either way the original solution stands.
Comment #89 July 2nd, 2018 at 4:32 pm
[…] Plane. There have been fine blog posts on this by Gil Kalai here amd Scott Aaronson here. Rather than blog on it ourselves we have recruited and expert in the field, Alexander Soifer. He […]
Comment #90 September 24th, 2019 at 9:22 pm
[…] opening plenary talk on her verification protocol for quantum computation (which I blogged about here), and Avishay Tal’s upcoming plenary on his and Ran Raz’s oracle separation between BQP […]