One context in which diophantine equations arise is hidden within the innards of loop optimizing compilers, where loop carried dependencies are considered, as they constrain parallelization.
I had (and donated to an engineering library in Urbana) a book about just this from the early 90s. I tried finding it on Amazon but no such luck.
I have a PhD in ML compilers (one of my papers is cited on the site I linked) and as I mentioned in the previous "discussion" I currently work in FAANG as an ML compiler engineer.
Is your thesis published and at a URL? Since I'm an old parallelizing compilers person, I'm curious what you did. (genuinely curious, not obnoxiously curious).
You should know a serious fraction of folks commenting on these threads have resumes like you're bragging about.
yes but i'm not going to link it here in order to preserve my anonymity
> You should know a serious fraction of folks commenting on these threads
<X to doubt> not because i'm not aware there aren't lots of people with PhDs in tech, but because generally the comments on hn are from outsider wannabes
Check the link above...it seems we're considering different topics.
Most often these analyses were framed in terms of integer indices on multidimensional arrays in Fortran loops, though that was just the common format academics all knew, as i recall. Personally I'd started with C (and x86 assembly and Basic on Apple ][ and Atari 800) so was a younger vintage.
Probably in the future nobody will be able to figure out how these things are written, because studying math doesn't make as much money as vibe coding.
I love this topic and look forward to reading the next articles, but I suggest not saying two numbers are "equal" mod N. I would say they are "equivalent" mod N and maybe point out the broader insight: Equality is often too rigid a constraint, and we usually want to consider equivalence relations instead. We know 3 and 6 and 9 are obviously not equal, but it's useful to notice the pattern that they are all divisible evenly by 3, i.e., they are all in the equivalence class 0 mod 3.
When I think about Langlands, I think it is the power of equivalence over equality that shockingly allows us to connect the discrete world of the natural numbers (or Q) with the world of the continuous (R or C), across disparate branches of mathematics. The Modularity Theorem (every elliptic curve over Q is modular) is the foundational idea and at every step along the way, we obtain evidence of more remarkable equivalences: The conductor N of an elliptic curve versus the level N of certain congruence groups; the point count deficiency (p'th Hecke eigenvalue) of a curve and the p'th coefficient of the Fourier q-expansion; Galois reciprocity showing an equivalence between the traces of Frobenius elements acting on a cohomology, and the eigenvalues of Hecke operators; Ribet's theorem about level lowering; etc. Time and again, the theme in Langlands is that equivalence relationships make it possible for us to reason why two intricate mathematical structures that seem completely foreign are actually "essentially the same" -- not equal, but equivalent.
When saying “6 = 9 mod 3”, the “mod 3” is changing what “6” and “9” are referring to: they are now referring to the equivalence classes modulo 3 that 6 and 9 respectively belong to, and the statement expresses that those two equivalence classes are equal (hence using the equals sign is correct), are the same class. It’s a shorthand for “[6]_3 = [9]_3”, or whatever your notation is for equivalence classes.
Exactly, so [0]_3 = [3]_3 = [6]_3 = ... (and here these are indeed equalities inside Z/3Z because these are equalities of sets and not just equivalences). And for that reason, we take the "best" or canonical representative of the equivalence class to be [a]_n where 0 is less than or equal to `a`, which is always strictly less than n; hence, [0]_3 is canonical.
Actually, since the modulus is often fixed within a computation or expression, we often simply abuse notation by writing:
0 := [0]_n ("zero is defined to be the equivalence class of 0 mod n")
1 := [1]_n
...
I don't think quibbling over "equivalence" vs "equality" is useful personally. They're both "equality". Just what the sign "=" means differs depending on the type information.
E.g x: ZmodN == y: ZmodN is a different operation than x: Z == y: Z, but they're both the equality operation. We wouldn't makeup a new name for addition in this context.
It's also worth mentioning we can use the equality function (==): Z x Z -> bool to define the (==_N): ZmodN x ZmodN -> bool function in a semi-generic way. To do so, we "just" need a way to assign a unique representative (in Z) to any x: ZmodN. In other words, this is choosing a partial inverse to the reduction function modN: Z -> ZmodN. I think the partial inverse is a right inverse? so a function g : ZmodN -> Z such that (modN) o g x == x for all x in ZmodN. Anyway, given such a right inverse g, you can define (==_N): ZmodN x ZmodN -> bool via
(==_N) x y := (==) (g x) (g y)
This has the benefit that it doesn't treat ZmodN as special in any way. You can apply the same song and dance for more general quotient structures. This can be useful when doing e.g. matrix arithmetic, where you might want equivalence up to the choice of some rotation or something.
The article doesn't really tell us much about the "why" unfortunately. Diophantine equations are introduced but all the interesting stuff is promised in future articles which haven't come yet. All the reader can take from this is that these equations lead to some "profound hidden structures" without a good idea what they are.
I get that it's hard to wrap one's head around the Langlands program but I'd love to see at least more exposition on the following statement:
>inventing the Euclidean algorithm is essentially equivalent to inventing unique prime factorization
I mentioned Langlands because it's one of the cool things related to Diophantine equations that the article mentions but I wouldn't expect it to be covered there. The connection between the Euclidean algorithm and unique prime factorization is simpler but also not obvious (the Euclidean algorithm on the surface just computes the GCD of two numbers and doesn't mention primes) so it would make sense to explain it in the article. However, they don't explain what the algorithm is, maybe assuming that the reader knows about it, while the rest of the article seemingly assumes no familiarity with basic number theory concepts like modular arithmetic. That confused me.
Diophantine equations are as they say Turing complete. That is for any question about does this Turing machine with this tape halt with a certain value there is a corresponding Diophantine equation, which has solutions if the machine halts with the output corresponding to the values it is solved by. I think this paper covers it for register machines rather than Turing machines directly: https://carleton.ca/math/wp-content/uploads/Nick-Murphy-Hono...
This is not bidirectional. The Davis-Putnam-Robinson-Matiyasevich theorem shows we can make a Diophantine equation that acts as a universal Turing machine, but there’s Diophantine equations that cannot be solved by Turing machines:
The smallest known Diophantine equation that cannot be solved by any Turing machine last I checked had ~8000 states as a Turing machine. This Turing machine cannot be decided to halt, and if it does halt in finite time then an (outer) Turing machine could execute it to predict that, so this lives beyond decidability:
I find it annoying that the response to this from the Chaitain perspective is to throw your hands in the air and say not all of math is predictable and let “equivalent to halting decidability” be the death of effort. There’s a richer field of ‘hypercomputation’ sitting beyond the pale, and I believe it will be topological applications that untwist this knot [pun intended]. I’m excited for the post Turing world but i dare say I won’t live to see it.
The correspondence is bidirectional. The Diophantine equation you mention encodes a Turing machine that halts iff the Diophantine equation is solvable, and the proof of the independence (impossible to prove true nor false) of the halting problem for that specific Turing machine from Zermelo-Fraenkel set theory implies that whether or not the Diophantine equation in question has solutions is also independent from Zermelo-Fraenkel set theory.
The Matiyasevich theorem (which settled Hilbert's 10th Problem) proved that Diophantine equations are fundamentally tied to the Halting Problem. Because a universal Turing machine cannot determine if any arbitrary program will halt, no computer program or mathematical algorithm can ever be written to determine if any arbitrary Diophantine equation has an integer solution.
It is a surprising and delightful consequence of this observation that there is a polynomial whose integer-valued roots are exactly the set of all prime numbers.
Of course to measure out 42 litres from two jugs of 5 and 17 litres each on the day that the Sun is in the exact same position among the constellations as today, and so is the Moon and in the same phase.
I thought this was obvious, like which is the better editor vi or whatever that other one was.
The purpose of this article was, secretly, to tell the reader about another class of Diophantine equations which leads to the Langlands program, which studies from incredibly intricate hidden structure inside of number theory. The Langlands program studies Diophantine equations of the form
This is of course an oversimplification by graduate students trying to reach a broad audience, but one could argue that it in fact is. Langlands himself viewed his program as part of an attempt to achieve non-abelian reciprocity laws. See for instance: https://www.phys.ens.psl.eu/~kashani/slides_chenevier.pdf
Here is a prime factorization: 2 = 2 x 1. Every number has a product of 1. Every prime has itself as the only factor, and 1. Kind of silly to write about number theory and just pass over that simple fact.
One context in which diophantine equations arise is hidden within the innards of loop optimizing compilers, where loop carried dependencies are considered, as they constrain parallelization.
I had (and donated to an engineering library in Urbana) a book about just this from the early 90s. I tried finding it on Amazon but no such luck.
This was a recurrent tool at
https://en.wikipedia.org/wiki/University_of_Illinois_Center_...
Perhaps you’re referring to one of Utpal Banerjee’s books?
https://www.thriftbooks.com/a/utpal-banerjee/1265627/?srslti...
I owned a few of them along with Michael Wolfe’s book, Allen & Kennedy, etc when I was working in this space.
Yes, those are the ones we had. Wolfe had graduated before i was there.
Hn upvotes the weirdest things. You're talking about polyhedral analysis which emphatically does not work on diophantine forms
http://polyhedral.info/
What's with this phenomenon of new accounts that confidently make authoritative false claims in things that they have no competence in.
Few days ago there was this account claiming there's no rotation matrices to be seen in any ML algorithms.
EDIT: oh it's the same guy. LoL.
> March 9, 2023
This is a new account?
> no competence in.
I have a PhD in ML compilers (one of my papers is cited on the site I linked) and as I mentioned in the previous "discussion" I currently work in FAANG as an ML compiler engineer.
But thanks for playing :)
That was my guess anyhow. A common affliction among newly minted PhDs. They usually out grow it.
I am reminded of https://news.ycombinator.com/user?id=almostgotcaught
Won't be surprised if it's the same person.
FAANG are now in the midst of a hype cycle. So that place of employment signal is pretty noisy now, especially if employed in the hyped field.
Coming back to the point, Polyhedral models for loop analysis and Diophantine equation based address aliasing analysis are quite different techniques.
Is your thesis published and at a URL? Since I'm an old parallelizing compilers person, I'm curious what you did. (genuinely curious, not obnoxiously curious).
You should know a serious fraction of folks commenting on these threads have resumes like you're bragging about.
> Is your thesis published and at a URL
yes but i'm not going to link it here in order to preserve my anonymity
> You should know a serious fraction of folks commenting on these threads
<X to doubt> not because i'm not aware there aren't lots of people with PhDs in tech, but because generally the comments on hn are from outsider wannabes
definitely increasingly over the last years from outsider folks, agreed. lots of obnoxious sniping nonsense over the last few years too.
anyway, fun stuff for folks like us otherwise still
Check the link above...it seems we're considering different topics.
Most often these analyses were framed in terms of integer indices on multidimensional arrays in Fortran loops, though that was just the common format academics all knew, as i recall. Personally I'd started with C (and x86 assembly and Basic on Apple ][ and Atari 800) so was a younger vintage.
Probably in the future nobody will be able to figure out how these things are written, because studying math doesn't make as much money as vibe coding.
Yeah it most definitely can. That said, you have a good point, in terms of how often it can.
I love this topic and look forward to reading the next articles, but I suggest not saying two numbers are "equal" mod N. I would say they are "equivalent" mod N and maybe point out the broader insight: Equality is often too rigid a constraint, and we usually want to consider equivalence relations instead. We know 3 and 6 and 9 are obviously not equal, but it's useful to notice the pattern that they are all divisible evenly by 3, i.e., they are all in the equivalence class 0 mod 3.
When I think about Langlands, I think it is the power of equivalence over equality that shockingly allows us to connect the discrete world of the natural numbers (or Q) with the world of the continuous (R or C), across disparate branches of mathematics. The Modularity Theorem (every elliptic curve over Q is modular) is the foundational idea and at every step along the way, we obtain evidence of more remarkable equivalences: The conductor N of an elliptic curve versus the level N of certain congruence groups; the point count deficiency (p'th Hecke eigenvalue) of a curve and the p'th coefficient of the Fourier q-expansion; Galois reciprocity showing an equivalence between the traces of Frobenius elements acting on a cohomology, and the eigenvalues of Hecke operators; Ribet's theorem about level lowering; etc. Time and again, the theme in Langlands is that equivalence relationships make it possible for us to reason why two intricate mathematical structures that seem completely foreign are actually "essentially the same" -- not equal, but equivalent.
When saying “6 = 9 mod 3”, the “mod 3” is changing what “6” and “9” are referring to: they are now referring to the equivalence classes modulo 3 that 6 and 9 respectively belong to, and the statement expresses that those two equivalence classes are equal (hence using the equals sign is correct), are the same class. It’s a shorthand for “[6]_3 = [9]_3”, or whatever your notation is for equivalence classes.
Exactly, so [0]_3 = [3]_3 = [6]_3 = ... (and here these are indeed equalities inside Z/3Z because these are equalities of sets and not just equivalences). And for that reason, we take the "best" or canonical representative of the equivalence class to be [a]_n where 0 is less than or equal to `a`, which is always strictly less than n; hence, [0]_3 is canonical.
Actually, since the modulus is often fixed within a computation or expression, we often simply abuse notation by writing:
0 := [0]_n ("zero is defined to be the equivalence class of 0 mod n") 1 := [1]_n ...
I don't think quibbling over "equivalence" vs "equality" is useful personally. They're both "equality". Just what the sign "=" means differs depending on the type information.
E.g x: ZmodN == y: ZmodN is a different operation than x: Z == y: Z, but they're both the equality operation. We wouldn't makeup a new name for addition in this context.
It's also worth mentioning we can use the equality function (==): Z x Z -> bool to define the (==_N): ZmodN x ZmodN -> bool function in a semi-generic way. To do so, we "just" need a way to assign a unique representative (in Z) to any x: ZmodN. In other words, this is choosing a partial inverse to the reduction function modN: Z -> ZmodN. I think the partial inverse is a right inverse? so a function g : ZmodN -> Z such that (modN) o g x == x for all x in ZmodN. Anyway, given such a right inverse g, you can define (==_N): ZmodN x ZmodN -> bool via
(==_N) x y := (==) (g x) (g y)
This has the benefit that it doesn't treat ZmodN as special in any way. You can apply the same song and dance for more general quotient structures. This can be useful when doing e.g. matrix arithmetic, where you might want equivalence up to the choice of some rotation or something.
In Science I think this phenomenon is called consilience.
The article doesn't really tell us much about the "why" unfortunately. Diophantine equations are introduced but all the interesting stuff is promised in future articles which haven't come yet. All the reader can take from this is that these equations lead to some "profound hidden structures" without a good idea what they are.
I get that it's hard to wrap one's head around the Langlands program but I'd love to see at least more exposition on the following statement:
>inventing the Euclidean algorithm is essentially equivalent to inventing unique prime factorization
Don’t think that has anything to do with langlands..? Euclidean algorithm is literally just an explicit algorithm for prime factorisation
I mentioned Langlands because it's one of the cool things related to Diophantine equations that the article mentions but I wouldn't expect it to be covered there. The connection between the Euclidean algorithm and unique prime factorization is simpler but also not obvious (the Euclidean algorithm on the surface just computes the GCD of two numbers and doesn't mention primes) so it would make sense to explain it in the article. However, they don't explain what the algorithm is, maybe assuming that the reader knows about it, while the rest of the article seemingly assumes no familiarity with basic number theory concepts like modular arithmetic. That confused me.
Diophantine equations are as they say Turing complete. That is for any question about does this Turing machine with this tape halt with a certain value there is a corresponding Diophantine equation, which has solutions if the machine halts with the output corresponding to the values it is solved by. I think this paper covers it for register machines rather than Turing machines directly: https://carleton.ca/math/wp-content/uploads/Nick-Murphy-Hono...
This is not bidirectional. The Davis-Putnam-Robinson-Matiyasevich theorem shows we can make a Diophantine equation that acts as a universal Turing machine, but there’s Diophantine equations that cannot be solved by Turing machines:
https://www.nlp-kyle.com/post/number_computability/
The smallest known Diophantine equation that cannot be solved by any Turing machine last I checked had ~8000 states as a Turing machine. This Turing machine cannot be decided to halt, and if it does halt in finite time then an (outer) Turing machine could execute it to predict that, so this lives beyond decidability:
https://scottaaronson.blog/?p=2725
I find it annoying that the response to this from the Chaitain perspective is to throw your hands in the air and say not all of math is predictable and let “equivalent to halting decidability” be the death of effort. There’s a richer field of ‘hypercomputation’ sitting beyond the pale, and I believe it will be topological applications that untwist this knot [pun intended]. I’m excited for the post Turing world but i dare say I won’t live to see it.
The correspondence is bidirectional. The Diophantine equation you mention encodes a Turing machine that halts iff the Diophantine equation is solvable, and the proof of the independence (impossible to prove true nor false) of the halting problem for that specific Turing machine from Zermelo-Fraenkel set theory implies that whether or not the Diophantine equation in question has solutions is also independent from Zermelo-Fraenkel set theory.
Wait, are you saying they can't be solved by a Turing machine, but they can be solved some other way? If so, how?
The Matiyasevich theorem (which settled Hilbert's 10th Problem) proved that Diophantine equations are fundamentally tied to the Halting Problem. Because a universal Turing machine cannot determine if any arbitrary program will halt, no computer program or mathematical algorithm can ever be written to determine if any arbitrary Diophantine equation has an integer solution.
It is a surprising and delightful consequence of this observation that there is a polynomial whose integer-valued roots are exactly the set of all prime numbers.
Of course to measure out 42 litres from two jugs of 5 and 17 litres each on the day that the Sun is in the exact same position among the constellations as today, and so is the Moon and in the same phase.
I thought this was obvious, like which is the better editor vi or whatever that other one was.
More here
https://web.archive.org/web/20160615205452/http://www2.slgb.... Section 2
https://hal.science/hal-01254966v1/file/MayaEnigma.pdf
https://www.ias.ac.in/article/fulltext/reso/007/10/0006-0022
you're thinking of vim
The purpose of this article was, secretly, to tell the reader about another class of Diophantine equations which leads to the Langlands program, which studies from incredibly intricate hidden structure inside of number theory. The Langlands program studies Diophantine equations of the form
This is not what the Langlands program is
This is of course an oversimplification by graduate students trying to reach a broad audience, but one could argue that it in fact is. Langlands himself viewed his program as part of an attempt to achieve non-abelian reciprocity laws. See for instance: https://www.phys.ens.psl.eu/~kashani/slides_chenevier.pdf
They give a better example at the end of https://hidden-phenomena.com/articles/quadratic-residues
Here is a prime factorization: 2 = 2 x 1. Every number has a product of 1. Every prime has itself as the only factor, and 1. Kind of silly to write about number theory and just pass over that simple fact.
That's why 1 is not generally considered prime. If it was, 2 could be factored as 2, 2x1, 2x1x1, etc., which breaks the uniqueness property.
[flagged]