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

11–20 of 38 posts

Re: Why study Diophantine equations?

#11

Post by gweinberg »

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

Wait, are you saying they can't be solved by a Turing machine, but they can be solved some other way? If so, how?

Re: Why study Diophantine equations?

#12

Post by 2snakes »

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…

In Science I think this phenomenon is called consilience.

Re: Why study Diophantine equations?

#13

Post by [deleted] »

gweinberg wrote: post #11
boxfire wrote: post #7

Earlier quoted context omitted.

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

Wait, are you saying they can't be solved by a Turing machine, but they can be solved some other way? If so, how?

[deleted]

Re: Why study Diophantine equations?

#14

Post by mtsolitary »

renyicircle wrote: post #3

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…

Don’t think that has anything to do with langlands..? Euclidean algorithm is literally just an explicit algorithm for prime factorisation

Re: Why study Diophantine equations?

#16

Post by ForOldHack »

gweinberg wrote: post #11
boxfire wrote: post #7

Earlier quoted context omitted.

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

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.

Re: Why study Diophantine equations?

#17

Post by SyzygyRhythm »

ForOldHack wrote: post #15

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.

Re: Why study Diophantine equations?

#18

Post by dheera »

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.

Re: Why study Diophantine equations?

#19

Post by mswphd »

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…

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.

Post reply on HN