Mathematicians crack a simple but stubborn class of equations | Hacker News Reader

Mathematicians crack a simple but stubborn class of equations

quantamagazine.org

73 pointsdigital554 comments

It's weird seeing Pell's equation discussed as something intractable or unsolved. We have deterministic ways of solving them (you can use convergents, which can be calculated using continuous fractions [0]). But then again, Diophantine equations sometimes show surprising patterns, and in this case the problem is not so much about solving the equation, but about finding cases where it doesn't have a solution. Which can be determined reasonably quickly for any given equation (at least, one with smallish coefficients), but apparently it's difficult to pinpoint an exact pattern of cases where this happens.

[0] https://en.wikipedia.org/wiki/Continued_fraction#Infinite_co...

It's not about finding a specific solution, It has to with the the average proportion of solutions of a certain type

Right, this is about the negative Pell's equation, x^2 - dy^2 = -1 (rather than +1). The question is for which d this has a solution. (For the usual +1 case, which is what you're talking about, there are solutions for every d, and indeed continued fractions can be used.)

There are no solutions when d has any factor that is 3 mod 4, and the result mentioned in the article (Stevenhagen's conjecture, now proved by Koymans and Pagano) is that there are solutions for about 58% of the rest, specifically 1 - product_{j odd}(1 - 1/2^j) ≈ 0.580577558…. The first couple of pages of the paper (linked from the article) are actually very readable without much background: https://arxiv.org/pdf/2201.13424.pdf

If you want to program and play around a bit with the Pell equation (and learn more than you'd ever think about continued fractions for square roots - it's magic), here's a Project Euler problem involving it:

https://projecteuler.net/problem=66

For warm up on continued fractions, solve problems 64 and 65 before.

Reply on news.ycombinator.com