News for hackers. Stuff that matters.
Re:A Formal Proof of Complexity Bounds on Diophantine Equations by kevinventullo on Friday May 23, 2025 @06:59PM (#44077358)
A mind-blowing consequence of the MRDP theorem is that there is a multi-variate polynomial which fits on a sheet of paper with the property that the set of values of the first variable which appear in integer solutions are exactly the set of prime numbers.

https://en.wikipedia.org/wiki/Formula_for_primes#Formula_bas...

Re:A Formal Proof of Complexity Bounds on Diophantine Equations by sega_sai on Friday May 23, 2025 @09:28PM (#44078105)
Non-negative integer solutions
Re:A Formal Proof of Complexity Bounds on Diophantine Equations by colinhb on Saturday May 24, 2025 @06:12AM (#44080038)
> is a polynomial inequality in 26 variables, and the set of prime numbers is identical to the set of positive values taken on by the left-hand side as the variables a, b, …, z range over the nonnegative integers.

I hadn’t heard of this result, and my exposure to Diophantine equations is limited to precisely one seminar from undergrad, but this feels like taking von Neumann’s famous quip to its most fantastical extreme:

> With four parameters I can fit an elephant, and with five I can make him wiggle his trunk.

Re:A Formal Proof of Complexity Bounds on Diophantine Equations by marcodavid on Saturday May 24, 2025 @06:22PM (#44084141)
An even crazier consequence was pointed out by J.P. Jones in 1982. He explained:

"Via Gödel numbering, the theorems of an axiomatizable theory T become in effect an recursively enumerable set. The search for proofs becomes the search for solutions of a Diophantine equation. [...]

"Theorem. For any axiomatizable theory T and any proposition P, if P has a proof in T, then P has another proof consisting of 100 additions and multiplications of integers."

See https://www.jstor.org/stable/2273588

Re:A Formal Proof of Complexity Bounds on Diophantine Equations by UltraSane on Saturday May 24, 2025 @07:32PM (#44084413)
Why 100?