Dear Julia, Dear Yuri: A mathematical correspondence (2022)(celebratio.org)
celebratio.org
Dear Julia, Dear Yuri: A mathematical correspondence (2022)
https://celebratio.org/Robinson_JB/article/964/
10 comments
Yeah, this is a little bit subtle. Please ignore the lack of rigor below, but this is my understanding: They aren't looking at a particular polynomial like 4x + 3y = 2. That has a solution x=2, y=-2, but they don't really care about the exact value for (x, y), just that it's integers. They're more interested in the parameters: (4, 3, 2), and in general Ax + By = C. If you like, it's almost like hyper parameter tuning: what are the parameter settings for (A, B, C) where I can get this shape of equation to "work", e.g. give me acceptable x and y? A "Diophantine set" is a family of parameters that all work. It turns out you can think of "parameters of a given shape of Diophantine equation" as an exotic programming paradigm.
Fermat: x^N + y^N = z^N. The Diophantine set only has the number N=2, because Fermat's Last Theorem tells us that no other possible N will work if x, y, z have to be integers. This is just a finite set.
Other polynomial expressions work with an infinite number of parameter settings: Pell's equation is x^2 - N*y^2 = 1. In this case, every N that is not a square will work. This is an infinite set.
Because a lot of the parameter sets are infinite like this, the size of the parameter set are instead measured using big-O notation. For Fermat's Last Theorem, {N=2} is constant, so big-O(1). For Pell's equation, {N not a square} is O(N). For other Diophantine expressions, the parameter settings are O(N^2), or O(2^N), or any other growth function you want that's achievable with Turing machines.
And this is the essence of what MRDP proved. Robinson, Davis, Putnam, and Matiyasevich over several papers proved that if you could encode a set that grew roughly like O(2^N), you also could encode any other computable set in the parameters. Approximately, demonstrating an exponentially-fast-growing family of parameters for some specific Diophantine problem was enough for Diophantine problems as a whole to be Turing complete. Matiyasevich's clinching discovery was a concrete example using the Fibonacci numbers.
Fermat: x^N + y^N = z^N. The Diophantine set only has the number N=2, because Fermat's Last Theorem tells us that no other possible N will work if x, y, z have to be integers. This is just a finite set.
Other polynomial expressions work with an infinite number of parameter settings: Pell's equation is x^2 - N*y^2 = 1. In this case, every N that is not a square will work. This is an infinite set.
Because a lot of the parameter sets are infinite like this, the size of the parameter set are instead measured using big-O notation. For Fermat's Last Theorem, {N=2} is constant, so big-O(1). For Pell's equation, {N not a square} is O(N). For other Diophantine expressions, the parameter settings are O(N^2), or O(2^N), or any other growth function you want that's achievable with Turing machines.
And this is the essence of what MRDP proved. Robinson, Davis, Putnam, and Matiyasevich over several papers proved that if you could encode a set that grew roughly like O(2^N), you also could encode any other computable set in the parameters. Approximately, demonstrating an exponentially-fast-growing family of parameters for some specific Diophantine problem was enough for Diophantine problems as a whole to be Turing complete. Matiyasevich's clinching discovery was a concrete example using the Fibonacci numbers.
In fact, according to the Esolang Wiki [https://esolangs.org/wiki/List_of_ideas#Mathematics] , Gregory Chaitin apparently has built a Diophantine equation whose parameters encode an entire Lisp interpreter.
Such a wonderful piece. I'd not heard of Julia Robinson or Yuri Matiyasevich...what a touching story of two people forming a friendship across time, place and culture.
> Julia thought of mathematicians “as forming a nation of our own without distinctions of geographical origins, race, creed, sex, age, or even time (the mathematicians of the past and you of the future are our colleagues too) — all dedicated to the most beautiful of the arts and sciences.”
The mathematics is way over my head, but I find this inspiring & would love to see how we might discover/co-create realms beyond such distinctions in other endeavors.
> Julia thought of mathematicians “as forming a nation of our own without distinctions of geographical origins, race, creed, sex, age, or even time (the mathematicians of the past and you of the future are our colleagues too) — all dedicated to the most beautiful of the arts and sciences.”
The mathematics is way over my head, but I find this inspiring & would love to see how we might discover/co-create realms beyond such distinctions in other endeavors.
I liked this quote too, though I wonder if it's not more out of necessity and the special nature of math than anything else.
Mathematicians speak languages non-math people can't grasp, so they gravitate toward and connect to one another.
Math simply doesn't advance without promiscuous sharing of ideas. Soviet censors notwithstanding, there's certainly a reason correspondence like this was permitted even during the Cold War.
You could say that the above is true of other sciences, but I imagine falsification of results in math is extremely difficult or just impossible. So math is mostly immune (I suggest) to the politics and protectionism that inevitably emerges around fuzzy and controversial scientific disciplines.
Just look at the good faith Julia has in her treatment of Chudnovsky's work. Even the skepticism is respectful.
Mathematicians speak languages non-math people can't grasp, so they gravitate toward and connect to one another.
Math simply doesn't advance without promiscuous sharing of ideas. Soviet censors notwithstanding, there's certainly a reason correspondence like this was permitted even during the Cold War.
You could say that the above is true of other sciences, but I imagine falsification of results in math is extremely difficult or just impossible. So math is mostly immune (I suggest) to the politics and protectionism that inevitably emerges around fuzzy and controversial scientific disciplines.
Just look at the good faith Julia has in her treatment of Chudnovsky's work. Even the skepticism is respectful.
> I imagine falsification of results in math is extremely difficult or just impossible.
Another quote I like from this piece: “No one can be a charlatan mathematician for long”.
If only that were true in certain other domains.
Another quote I like from this piece: “No one can be a charlatan mathematician for long”.
If only that were true in certain other domains.
gregory chaitin has an accessible version of the math, if you’re interested. he builds a LISP with it.
Thanks for the pointer to Chaitin, his writing seems approachable:
https://link.springer.com/chapter/10.1007/978-1-4471-0307-3_...
https://inference-review.com/article/doing-mathematics-diffe...
> he builds a LISP with it
cool, just found these:
The Limits of Mathematics---Tutorial Version : https://arxiv.org/abs/chao-dyn/9509010
An implementation of his Lisp, written to explore the above Tutorial : https://github.com/poppingtonic/chaitin-ait
https://link.springer.com/chapter/10.1007/978-1-4471-0307-3_...
https://inference-review.com/article/doing-mathematics-diffe...
> he builds a LISP with it
cool, just found these:
The Limits of Mathematics---Tutorial Version : https://arxiv.org/abs/chao-dyn/9509010
An implementation of his Lisp, written to explore the above Tutorial : https://github.com/poppingtonic/chaitin-ait
On one hand, the article claims that Diophantine equations are polynomials. On the other hand, it claims that when JR is true, a Diophantine equations grows faster than a polynomial.
How can a polynomial grow faster than polynomial? That seems like a contradiction to me.