Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why study Diophantine equations?

hidden-phenomena.com

Post reply on HN
Print view View original

21–30 of 38 posts

Re: Why study Diophantine equations?

#21

Post by boarsofcanada »

jjtheblunt wrote: post #2

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_C…

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.

Re: Why study Diophantine equations?

#22

Post by jackolantern22 »

paulpauper wrote: post #5

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

They give a better example at the end of https://hidden-phenomena.com/articles/quadratic-residues

Re: Why study Diophantine equations?

#23

Post by yorwba »

boxfire wrote: post #7
lanstin wrote: post #4

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-co…

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.…

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.

Re: Why study Diophantine equations?

#24

Post by layer8 »

simonreiff wrote: post #10

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…

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.

Re: Why study Diophantine equations?

#25

Post by simonreiff »

layer8 wrote: post #24
simonreiff wrote: post #10

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…

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 ...

Re: Why study Diophantine equations?

#26

Post by mathisfun123 »

jjtheblunt wrote: post #2

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_C…

Hn upvotes the weirdest things. You're talking about polyhedral analysis which emphatically does not work on diophantine forms

http://polyhedral.info/

Re: Why study Diophantine equations?

#27

Post by jjtheblunt »

boarsofcanada wrote: post #21
jjtheblunt wrote: post #2

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_C…

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.

Re: Why study Diophantine equations?

#28

Post by jjtheblunt »

mathisfun123 wrote: post #26
jjtheblunt wrote: post #2

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_C…

Hn upvotes the weirdest things. You're talking about polyhedral analysis which emphatically does not work on diophantine forms http://polyhedral.info/

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.

Re: Why study Diophantine equations?

#29

Post by jjtheblunt »

dheera wrote: post #18
jjtheblunt wrote: post #2

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_C…

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.

Re: Why study Diophantine equations?

#30

Post by tpoacher »

srean wrote: post #8

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/fi…

you're thinking of vim
Post reply on HN