Mathematicians try to understand how CS proof solves Connes embedding conjecture(abstractions.nautil.us)
abstractions.nautil.us
Mathematicians try to understand how CS proof solves Connes embedding conjecture
http://abstractions.nautil.us/article/538/graced-with-knowledge-mathematicians-seek-to-understand
13 comments
> I really would have liked a discussion of why people assumed the conjecture must be true, given that the only analogy presented was obviously not true.
I'm trained in the field (on the math side, actually at the same institution as Vern Paulsen quoted in the article), and I never got the impression that the answer was universally assumed to be true. One of the major consequences of a positive answer would have been that every countable discrete group is hyperlinear, which would have violated a well-known heuristic principle of Gromov that every property of all finitely generated groups is either false or trivial.
The frustrating aspect about the refutation via quantum information theory is that there is no obvious way to transfer the insight to also refute the consequences of a positive answer to the problem.
I'm trained in the field (on the math side, actually at the same institution as Vern Paulsen quoted in the article), and I never got the impression that the answer was universally assumed to be true. One of the major consequences of a positive answer would have been that every countable discrete group is hyperlinear, which would have violated a well-known heuristic principle of Gromov that every property of all finitely generated groups is either false or trivial.
The frustrating aspect about the refutation via quantum information theory is that there is no obvious way to transfer the insight to also refute the consequences of a positive answer to the problem.
Cwzwarich could you explain further what the Gromov heuristics is about? or where could I read more about it? Thank you
The analogy holds. For a 2x2 matrix the error bound is obviously quite large, but you still know it exists. Physics do not allow you to simply modify the temperature of a point. Thermodynamics prevent that.
Now the interesting question is, does the conjecture follow from the model itself? Apparently not. But I do neither understand the model nor the proof.
Now the interesting question is, does the conjecture follow from the model itself? Apparently not. But I do neither understand the model nor the proof.
But, according to the article, the Connes conjecture applies to all infinite matrices. There's nothing strange about modifying the value of one entry in a matrix.
> Physics do not allow you to simply modify the temperature of a point. Thermodynamics prevent that.
gotcha - in terms of the analogy, the temperature distribution cannot be any arbitrary distribution with a finite average (i.e. a finite L2 norm) --- including those pathological cases e.g. the temperature is 0 everywhere except at one point x where it takes the value 1 ---- no, the temperature distribution has to have some minimum smoothness structure, meaning that if you adjust the temperature at a single point, you have to also locally adjust the temperature of neighbouring points enough for it to make a difference to the overall global average temperature over the entire space.
for intuition, the animation on the wikipedia "heat equation" page is a good start: https://en.wikipedia.org/wiki/Heat_equation
When you plug initial conditions into the heat equation, over time it evolves to be smoother.
gotcha - in terms of the analogy, the temperature distribution cannot be any arbitrary distribution with a finite average (i.e. a finite L2 norm) --- including those pathological cases e.g. the temperature is 0 everywhere except at one point x where it takes the value 1 ---- no, the temperature distribution has to have some minimum smoothness structure, meaning that if you adjust the temperature at a single point, you have to also locally adjust the temperature of neighbouring points enough for it to make a difference to the overall global average temperature over the entire space.
for intuition, the animation on the wikipedia "heat equation" page is a good start: https://en.wikipedia.org/wiki/Heat_equation
When you plug initial conditions into the heat equation, over time it evolves to be smoother.
Quite a nice result. Along the lines of your point 2., it's not the first time in recent years a problem in operator algebras was resolved by the computer science community using unexpected methods: https://www.quantamagazine.org/computer-scientists-solve-kad.... Perhaps looking at these problems from a more concrete angle is the way to go, especially for a problem like disproving the Connes conjecture.
As this is referring to photons I'm reminded of a concept that comes from the use of Feynman diagrams to model interactions. I think this answers your question.
If you're calculating the probability that a photon goes from A to B you can calculate the probability (or more technically, the amplitude) that it goes straight there (this is the crude approximation), but you also have to account for the case where it went a bit off the way, hit another photon and then arrived at B (a slightly less crude approximation), and you can account for the path where the photon interacted with two other photons for a more accurate approximation, and with three other photons for an even more accurate approximation.
People stop the calculation from being infinitely complex because it appears that the probability of the cases with many interactions is incredibly unlikely. I guess the conjecture here was that if you have some error bound for the N interactions case, then the N+1 interactions case would have lower error. And that's been proven to not always be true.
I may be way off the mark, my knowledge of QED comes purely from watching Feynman and Susskind on YouTube.
If you're calculating the probability that a photon goes from A to B you can calculate the probability (or more technically, the amplitude) that it goes straight there (this is the crude approximation), but you also have to account for the case where it went a bit off the way, hit another photon and then arrived at B (a slightly less crude approximation), and you can account for the path where the photon interacted with two other photons for a more accurate approximation, and with three other photons for an even more accurate approximation.
People stop the calculation from being infinitely complex because it appears that the probability of the cases with many interactions is incredibly unlikely. I guess the conjecture here was that if you have some error bound for the N interactions case, then the N+1 interactions case would have lower error. And that's been proven to not always be true.
I may be way off the mark, my knowledge of QED comes purely from watching Feynman and Susskind on YouTube.
If I understand the article correctly, the conjecture in fact holds for all of the kinds of infinite matrices we know about and had tested it with. So either the example in the article is not one of the known examples of the conjecture working (which is not likely, given that the article says we are yet to find the matrices for which this doesn't work), or there is something else going on with the terms used.
I think what they are trying to describe in laymans terms is the delta-epsilon definition of uniform continuity. That for any desired error bound you can reach it with a fine enough mesh.
The paper 'MIP* =RE' https://arxiv.org/abs/2001.04383, where the article is referring to, has already been discussed here extensively. It is also being studied by many people, because it is a very important and surprising result. I guess that Connes conjecture is but one of the many things that is affected by the MIP* =RE result.
I truly enjoy all of Kevin Hartnett’s articles. He’s a great science writer. He shines a light on some really impenetrable ideas.
1. Describes a simplified analogy to the Connes conjecture. The analogical conjecture is obviously false. ("The average temperature over some portion of the earth's surface must necessarily approximate the actual temperature at each point within the portion, with bounded error." That can't be true, because while modifying a single point affects the average temperature, you can modify a set of multiple points, including any arbitrary increase or decrease to one of those points, without affecting the average at all. Thus, there is no bound on the deviation between the temperature at an individual point and the average temperature over every point.)
2. Goes on at length about how everyone just assumed the Connes conjecture would turn out to be true, and they've all been blindsided by a proof that it isn't.
I really would have liked a discussion of why people assumed the conjecture must be true, given that the only analogy presented was obviously not true.