8 ms·

New Proofs Probe the Limits of Mathematical Truth

94 points by headalgorithm 2y ago

empath75 2y ago
Something that may not be clear when reading this is the distinction between complex numbers and the ring of integers adjoined with i. "Complex numbers" are of the form a+bi where a and b can be any real number -- 1, 5, pi, the square root of 2, -2.14, etc. The ring of integers adjoined with i are numbers of the form a+bi where a and b are both integers (-1, 5, 34, etc). You can also, in addition to using i, adjoin any real number to the integers and get a new field with numbers of the form a+bx where a and b are integers and x is any additional number you want to add-- frequently square roots like the square root of two. This result shows undecidability of diophantine equations in all those fields of integers, but not complex numbers, for which it's easy to prove that there are _always_ solutions.
- Sniffnoy 2y ago
  Note that Z[i] is called the "Gaussian integers" -- you don't have to keep repeating "the ring of integers with i adjoined"! Also I should point out that in general Z[r] for some r (note obviously r doesn't have to be real!) will contain more than just a+br; it'd only be just a+br if r satisfies a monic quadratic over Z. (I also have to nitpick and point out that these results apply to rings of integers -- actually more broadly -- but not to the fields. Yeah unfortunately mathematicians often abuse the language here, using "number field" to refer to the ring, and it's annoying. But Hilbert's 10th for Q remains open to my knowledge.) Edit: Ugh I forgot this site doesn't allow bold
- deleted 2y ago
  [deleted]
coldcode 2y ago
Math is such an interesting field. People can work for decades and not make progress, then discover something in a moment of clarity from some seemingly unrelated problem. As a programmer, I don't have that type of patience.
- groby_b 2y ago
  Get yourself a slower compiler ;) But all kidding aside, you likely will have those moments. Not because you had patience, but because over you career you collected enough knowledge bits in your brain that they'll at some point click together in extremely odd shapes. Like with maths, if you choose to follow up, this is either a moment of clarity, or the moment you enter crankdom.
- godelski 2y ago
  Honestly, this happens in a lot of fields, including programming. I often wonder why we spend so much time trying to justify certain research avenues over others and don't let people just research what they find is interesting. I hear you, we should be efficient and not waste money. But is there actually good evidence that we have strong predictive powers here? There's at least strong evidence that dark horses are quite common in the innovation space and exceptionally common in major breakthroughs. So even if we want to primarily focus on funding promising directions there is still good evidence that optimal funding requires funding unpopular ideas. Which if we think about a lot of this, it should make sense anyways. Just by thinking about optimization theory. It is often quite good to add noise so that your optimization function can escape local minima. We can only travel directly to the global optima if we know exactly where it is. But should we not expect that expert predictive power is much better at pointing to local optima rather than global? (global very likely doesn't exist but that doesn't mean there aren't better optima). There's also many famous scientists that didn't "spend much time working." I add quotes, because if you're a researcher you'd naturally understand there's no real thing as "not working." There is only active work and inactive work. You're likely consumed by the topics and problems you're trying to solve. So doing things like going on walks, playing your favorite sport, or whatever ends up being beneficial as you can relax and shift between focused and creative modes. But that doesn't happen as much if your boss thinks "working" is staring at the chalkboard. Sometimes it is best to go sit outside and daydream, while other times it is best to hammer your head against that metaphorical chalkboard. > I don't have that type of patience. As for this, patience is a skill. Delayed rewards. Long term rewards are often noisier and more difficult to attribute to their appropriate causes. Even if the long term rewards are substantially greater than the short term, and the timeframe isn't too large, most people prefer the short term. Not just because reward, but because interpretability. As an example, just think about education in of itself. Lots of effort but also lots of reward. Even though the process is very noisy and it is unclear which aspects of education contributed the most to success, it is very clear that there's a strong connection between education and success (does not mean there aren't other pathways to success nor that you are guaranteed to be successful by being educated. It can be easy to conflate these things).
dooglius 2y ago
> Where is the cutoff Is there a reason to believe there is a "cutoff"? As in, do we know that if the undecidability property holds for some ring A, then it holds for every subring of A?
- eru 2y ago
  I guess it depends a bit on what you mean by subring? If you go by the strict definition of subring, I'm not sure. But we probably also want to explore other constructions like quotient rings, where I know that we can say some things. Eg calculating modulo some (given fixed) integer is a quotient ring on the integers.
  - dooglius 2y ago
    I mean it pretty loosely, I'm just trying to figure out what Mazur meant. The quote and reference to a cutoff seems to imply that solveability preserves some kind of structural partial order between Z and C, but it's not clear to me why one would expect that to be the case.
wslh 2y ago
Could Matiyasevich's result be viewed in the same vein as Turing’s Halting Problem, but in an even more compact form regarding the limits of mathematics and logic? Diophantine equations are expressed in a simpler form than Turing machines, which makes the size and expressiveness of the problem particularly interesting for study.
- isaacfrond 2y ago
  Matiyasevich just says: for every Turing machine a diophantine equation can be constructed such that the diophantine equation has integer solutions if and only if the Turing machine halts.

94 points by headalgorithm 2y ago

Something that may not be clear when reading this is the distinction between complex numbers and the ring of integers adjoined with i. "Complex numbers" are of the form a+bi where a and b can be any real number -- 1, 5, pi, the square root of 2, -2.14, etc. The ring of integers adjoined with i are numbers of the form a+bi where a and b are both integers (-1, 5, 34, etc). You can also, in addition to using i, adjoin any real number to the integers and get a new field with numbers of the form a+bx where a and b are integers and x is any additional number you want to add-- frequently square roots like the square root of two. This result shows undecidability of diophantine equations in all those fields of integers, but not complex numbers, for which it's easy to prove that there are _always_ solutions.

Sniffnoy 2y ago
Note that Z[i] is called the "Gaussian integers" -- you don't have to keep repeating "the ring of integers with i adjoined"! Also I should point out that in general Z[r] for some r (note obviously r doesn't have to be real!) will contain more than just a+br; it'd only be just a+br if r satisfies a monic quadratic over Z. (I also have to nitpick and point out that these results apply to rings of integers -- actually more broadly -- but not to the fields. Yeah unfortunately mathematicians often abuse the language here, using "number field" to refer to the ring, and it's annoying. But Hilbert's 10th for Q remains open to my knowledge.) Edit: Ugh I forgot this site doesn't allow bold
deleted 2y ago
[deleted]

coldcode 2y ago

Math is such an interesting field. People can work for decades and not make progress, then discover something in a moment of clarity from some seemingly unrelated problem. As a programmer, I don't have that type of patience.

groby_b 2y ago
Get yourself a slower compiler ;) But all kidding aside, you likely will have those moments. Not because you had patience, but because over you career you collected enough knowledge bits in your brain that they'll at some point click together in extremely odd shapes. Like with maths, if you choose to follow up, this is either a moment of clarity, or the moment you enter crankdom.
godelski 2y ago
Honestly, this happens in a lot of fields, including programming. I often wonder why we spend so much time trying to justify certain research avenues over others and don't let people just research what they find is interesting. I hear you, we should be efficient and not waste money. But is there actually good evidence that we have strong predictive powers here? There's at least strong evidence that dark horses are quite common in the innovation space and exceptionally common in major breakthroughs. So even if we want to primarily focus on funding promising directions there is still good evidence that optimal funding requires funding unpopular ideas. Which if we think about a lot of this, it should make sense anyways. Just by thinking about optimization theory. It is often quite good to add noise so that your optimization function can escape local minima. We can only travel directly to the global optima if we know exactly where it is. But should we not expect that expert predictive power is much better at pointing to local optima rather than global? (global very likely doesn't exist but that doesn't mean there aren't better optima). There's also many famous scientists that didn't "spend much time working." I add quotes, because if you're a researcher you'd naturally understand there's no real thing as "not working." There is only active work and inactive work. You're likely consumed by the topics and problems you're trying to solve. So doing things like going on walks, playing your favorite sport, or whatever ends up being beneficial as you can relax and shift between focused and creative modes. But that doesn't happen as much if your boss thinks "working" is staring at the chalkboard. Sometimes it is best to go sit outside and daydream, while other times it is best to hammer your head against that metaphorical chalkboard. > I don't have that type of patience. As for this, patience is a skill. Delayed rewards. Long term rewards are often noisier and more difficult to attribute to their appropriate causes. Even if the long term rewards are substantially greater than the short term, and the timeframe isn't too large, most people prefer the short term. Not just because reward, but because interpretability. As an example, just think about education in of itself. Lots of effort but also lots of reward. Even though the process is very noisy and it is unclear which aspects of education contributed the most to success, it is very clear that there's a strong connection between education and success (does not mean there aren't other pathways to success nor that you are guaranteed to be successful by being educated. It can be easy to conflate these things).

dooglius 2y ago

> Where is the cutoff Is there a reason to believe there is a "cutoff"? As in, do we know that if the undecidability property holds for some ring A, then it holds for every subring of A?

eru 2y ago
I guess it depends a bit on what you mean by subring? If you go by the strict definition of subring, I'm not sure. But we probably also want to explore other constructions like quotient rings, where I know that we can say some things. Eg calculating modulo some (given fixed) integer is a quotient ring on the integers.
- dooglius 2y ago
  I mean it pretty loosely, I'm just trying to figure out what Mazur meant. The quote and reference to a cutoff seems to imply that solveability preserves some kind of structural partial order between Z and C, but it's not clear to me why one would expect that to be the case.

wslh 2y ago

Could Matiyasevich's result be viewed in the same vein as Turing’s Halting Problem, but in an even more compact form regarding the limits of mathematics and logic? Diophantine equations are expressed in a simpler form than Turing machines, which makes the size and expressiveness of the problem particularly interesting for study.

isaacfrond 2y ago
Matiyasevich just says: for every Turing machine a diophantine equation can be constructed such that the diophantine equation has integer solutions if and only if the Turing machine halts.