10 ms·

The Ramanujan Machine: Using algorithms to discover new mathematics

158 points by mci 7y ago

thom 7y ago
Seems slightly less rich than Doug Lenat's Automated Mathematician (which in turn led to Eurisko which was one of the earliest genuinely interesting AI systems): https://en.wikipedia.org/wiki/Automated_Mathematician https://en.wikipedia.org/wiki/Automated_Mathematician
- beagle3 7y ago
  The story of Eurisko doesn't add up. So advanced for its time, not replicated for 30 years (or at all) and Lenat lost the source code and was not interested in doing anything similar again, with the next version (Cyc, IIRC) not getting anywhere close? I would guess there was a lot more manual handholding that was not documented.
  - thom 7y ago
    Yes, I mostly agree here. But even with that manual handholding, it's no different from current, mostly-supervised AI approaches. Even if you think of Eurisko as a very clever optimiser when posed problems in a certain way, it clearly delivered some interesting results. Also, you _can_ find the source code for large parts of Eurisko if you look hard enough, I believe. Cyc never seemed in the least bit interesting to me, tbh. Even today several "we taught our AI common sense!" articles have hit HN, and it's still not _really_ true.
mometsi 7y ago
Why on earth did they not call it the Ramanutron??
- thaumasiotes 7y ago
  Possibly because that only really works if you know the correct stress pattern of "Ramanujan". Americans, at least, are likely to want to stress it on the "nu".
  - bryanrasmussen 7y ago
    Didn't Good Will Hunting teach the proper pronunciation?
nurettin 7y ago
It seems aptly named because Ramanujan also dealt with infinite series. One of his most famous equations is the ramanujan summation [1] where he derives that the sum of infinite series 1 + 2 + 3 + 4 + ... = - 1 / 12 [1] https://en.wikipedia.org/wiki/Ramanujan_summation https://en.wikipedia.org/wiki/Ramanujan_summation
- amelius 7y ago
  I still don't understand why this derivation is such an achievement. If anything, it seems like dirty hacking, but this time done by a mathematician.
  - nurettin 7y ago
    I read somewhere that the result is confirmed in applied physics where it somehow relates to the casimir force, but I'm not a physicist.
    - mathandpoop 7y ago
      It's a theorem of analytic number theory. It's just a special value of the ζ-function. People misunderstand how analytic continuation works and therefore (wrongly) interpret ζ(-1) as the divergent series 1+2+3+... (The correct interpretation is as the unique analytic continuation of the holomorphic function $\sum_{n\geq 1}\frac{1}{n^s}$ defined on the half-plane $\Re(s)>1$ to $\mathbb{C}\setminus\{1\}$.) It's actually a pretty simple consequence of the functional equation for ζ and a few special values of Γ. That in turn comes from a theta-function identity which can be proven using Poisson's summation formula. What I'm trying to say is that it's legit maths, that has been distorted due to the shock value of writing the equation "1+2+3+... = -1/12". If you're looking for a reference, go to Davenport's "Multiplicative Number Theory". It's short, self-contained, and extremely well-written. Serre's "A Course in Arithmetic" should also work.
- eximius 7y ago
  Except he didn't. He created a way of assigning surrogate values to forms that otherwise wouldn't have one. To quote from the Wikipedia article you linked: > assigning a value to divergent infinite series Every time someone claims that series is EQUAL to -1/12, someone loses faith in math.
lifthrasiir 7y ago
Related: Robert Munafo's RIES [1] tries to synthesize increasingly complex formula which solution is a given number. [1] https://mrob.com/pub/ries/ https://mrob.com/pub/ries/
Grue3 7y ago
Well, the continuous fraction for e is pretty well known. Doubt they discovered anything new here that can't be obtained from the original formula. On the other hand, the continuous fraction for pi is irregular, so it's interesting to see what they discovered... but I can't really find any pattern in the "conjectures" for pi. Take the first one: pi/−4 = 1/(−1 + 1/(−4 + −2 /(−7 + −9/(−10 + −20/(−13+...)))) What exactly am supposed to prove here? The denominators are an arithmetic progression but numerators (1, 1, -2, -9, -20, ...) are just some bizarre sequence without an obvious pattern. The thing with continous fractions is that every number has one, so the fact that pi is presented as continous fraction is not impressive in itself.
- gjm11 7y ago
  All their conjectures have low-degree polynomial formulae for both numerators and denominators, with exceptions allowed in the first couple. So I guess the nth numerator, counting from 0, is -n(2n-3) which goes 0, 1, -2, -9, -20, ..., so n=0 is a special case. It would seem more natural to rewrite it like this -4/pi = −1 + 1/(−4 + −2 /(−7 + −9/(−10 + −20/(−13+...)))) which avoids the gratuitously different first numerator -- but I guess they wanted to reproduce results exactly as they happened to emerge from their program. I think this is, further, equivalent to the following which avoids some gratuitous-looking minus signs: 4/pi = 1 + 1/(4 + −2 /(7 + −9/(10 + −20/(13+...)))) Continuing the fraction using the quadratic polynomial I gave above does indeed seem to make it converge to 4/pi, though not very quickly.
  - gjm11 7y ago
    I wonder whether this one might be equivalent to a known infinite product for pi or pi/4 or something. The ratios between successive convergents are all of the form (a_n+k_n)/a_n where k_n is 1, 1, 3, 3, 15, 15, 105, 105, 315, 315, ... -- i.e., the least common multiples of odd numbers up to n. [EDITED to add:] This should make you think of the Wallis product formula for pi/4, though this doesn't seem to be the Wallis product in disguise. Clearly these k_n divide n!, so maybe the right way to say this is that the conjecture seems to be equivalent to 4/pi = product (a_n+n!)/a_n where (a_n) = (4,130,2464,45448,882528,18410640,...) ... though I don't know what that sequence _is_, haven't shown that it has a nice form, etc. None of (a_n), (a_n+n!), (a_n+n!/2) seems to occur in OEIS or to be a subsequence of anything in OEIS.
Zenst 7y ago
I was pondering a few weeks back about the prospects of using ML/AI to find new ways to factor primes and if their is any sequence in primes and how to calculate them in a way that you input N and it will produce the Nth prime. That would be something.
- m3kw9 7y ago
  Can primes be estimated?
  - drinfinity 7y ago
    Through my genius I've come to the conclusion that primes are related to entropy. There is no hope.
  - OscarCunningham 7y ago
    The nth prime is about nlog(n).
- klipt 7y ago
  We can already do this approximately (asymptotically): https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem "The prime number theorem is equivalent to the statement that the nth prime number p_n satisfies p_n ~ nlog(n) the asymptotic notation meaning, again, that the relative error of this approximation approaches 0 as n increases without bound. For example, the 2^1017th prime number is 8512677386048191063, and (2^1017)log(2^1017) rounds to 7967418752291744388, a relative error of about 6.4%."
  - eesmith 7y ago
    https://www.johndcook.com/blog/2019/06/20/bounds-on-the-nth-prime/ https://www.johndcook.com/blog/2019/06/20/bounds-on-the-nth-... is a recent blog posted titled "Bounds on the nth prime". It lists tighter upper and lower bounds: from math import log def f(n, k): ln = log(n); lln = log(log(n)) return ln + lln - 1 + (lln-2)/ln - ((lln**2) - 6*lln+k)/(2*ln*ln) With that in place, and once I realized that 2^1017 mean 2E17 not 2 to the power of 1017: >>> n = 2E17 >>> lo = n * f(n, 11.847) >>> hi = n * f(n, 10.273) >>> lo 8.512627944213742e+18 >>> hi 8.512727125430618e+18 >>> exact = 8512677386048191063 >>> (exact - lo)/exact 5.80802398678381e-06 >>> (exact - hi)/exact -5.842977499434444e-06
xvilka 7y ago
I wonder if it somehow can be integrated with Coq[1] and Univalent Foundations[2]. Probably these can be used as a more substantial "base" for this machine. [1] https://github.com/coq/coq https://github.com/coq/coq [2] https://github.com/UniMath https://github.com/UniMath
mathandpoop 7y ago
"New mathematics" is a bit of an overstatement. There is a lot more to maths than continued fractions. It bugs me a bit that the authors write (I would love for anyone affiliated with the project to talk to me about this) "Any new conjecture, proof, or algorithm suggested will be named after you.". No offense, but there are very few mathematicians out there with that kind of a world view. Seems a bit like a high school project without proper guidance from a mathematician.

158 points by mci 7y ago

thom 7y ago

Seems slightly less rich than Doug Lenat's Automated Mathematician (which in turn led to Eurisko which was one of the earliest genuinely interesting AI systems): https://en.wikipedia.org/wiki/Automated_Mathematician https://en.wikipedia.org/wiki/Automated_Mathematician

beagle3 7y ago
The story of Eurisko doesn't add up. So advanced for its time, not replicated for 30 years (or at all) and Lenat lost the source code and was not interested in doing anything similar again, with the next version (Cyc, IIRC) not getting anywhere close? I would guess there was a lot more manual handholding that was not documented.
- thom 7y ago
  Yes, I mostly agree here. But even with that manual handholding, it's no different from current, mostly-supervised AI approaches. Even if you think of Eurisko as a very clever optimiser when posed problems in a certain way, it clearly delivered some interesting results. Also, you _can_ find the source code for large parts of Eurisko if you look hard enough, I believe. Cyc never seemed in the least bit interesting to me, tbh. Even today several "we taught our AI common sense!" articles have hit HN, and it's still not _really_ true.

mometsi 7y ago

Why on earth did they not call it the Ramanutron??

thaumasiotes 7y ago
Possibly because that only really works if you know the correct stress pattern of "Ramanujan". Americans, at least, are likely to want to stress it on the "nu".
- bryanrasmussen 7y ago
  Didn't Good Will Hunting teach the proper pronunciation?

nurettin 7y ago

It seems aptly named because Ramanujan also dealt with infinite series. One of his most famous equations is the ramanujan summation [1] where he derives that the sum of infinite series 1 + 2 + 3 + 4 + ... = - 1 / 12 [1] https://en.wikipedia.org/wiki/Ramanujan_summation https://en.wikipedia.org/wiki/Ramanujan_summation

amelius 7y ago
I still don't understand why this derivation is such an achievement. If anything, it seems like dirty hacking, but this time done by a mathematician.
- nurettin 7y ago
  I read somewhere that the result is confirmed in applied physics where it somehow relates to the casimir force, but I'm not a physicist.
  - mathandpoop 7y ago
    It's a theorem of analytic number theory. It's just a special value of the ζ-function. People misunderstand how analytic continuation works and therefore (wrongly) interpret ζ(-1) as the divergent series 1+2+3+... (The correct interpretation is as the unique analytic continuation of the holomorphic function $\sum_{n\geq 1}\frac{1}{n^s}$ defined on the half-plane $\Re(s)>1$ to $\mathbb{C}\setminus\{1\}$.) It's actually a pretty simple consequence of the functional equation for ζ and a few special values of Γ. That in turn comes from a theta-function identity which can be proven using Poisson's summation formula. What I'm trying to say is that it's legit maths, that has been distorted due to the shock value of writing the equation "1+2+3+... = -1/12". If you're looking for a reference, go to Davenport's "Multiplicative Number Theory". It's short, self-contained, and extremely well-written. Serre's "A Course in Arithmetic" should also work.
eximius 7y ago
Except he didn't. He created a way of assigning surrogate values to forms that otherwise wouldn't have one. To quote from the Wikipedia article you linked: > assigning a value to divergent infinite series Every time someone claims that series is EQUAL to -1/12, someone loses faith in math.

lifthrasiir 7y ago

Related: Robert Munafo's RIES [1] tries to synthesize increasingly complex formula which solution is a given number. [1] https://mrob.com/pub/ries/ https://mrob.com/pub/ries/

Grue3 7y ago

Well, the continuous fraction for e is pretty well known. Doubt they discovered anything new here that can't be obtained from the original formula. On the other hand, the continuous fraction for pi is irregular, so it's interesting to see what they discovered... but I can't really find any pattern in the "conjectures" for pi. Take the first one: pi/−4 = 1/(−1 + 1/(−4 + −2 /(−7 + −9/(−10 + −20/(−13+...)))) What exactly am supposed to prove here? The denominators are an arithmetic progression but numerators (1, 1, -2, -9, -20, ...) are just some bizarre sequence without an obvious pattern. The thing with continous fractions is that every number has one, so the fact that pi is presented as continous fraction is not impressive in itself.

gjm11 7y ago
All their conjectures have low-degree polynomial formulae for both numerators and denominators, with exceptions allowed in the first couple. So I guess the nth numerator, counting from 0, is -n(2n-3) which goes 0, 1, -2, -9, -20, ..., so n=0 is a special case. It would seem more natural to rewrite it like this -4/pi = −1 + 1/(−4 + −2 /(−7 + −9/(−10 + −20/(−13+...)))) which avoids the gratuitously different first numerator -- but I guess they wanted to reproduce results exactly as they happened to emerge from their program. I think this is, further, equivalent to the following which avoids some gratuitous-looking minus signs: 4/pi = 1 + 1/(4 + −2 /(7 + −9/(10 + −20/(13+...)))) Continuing the fraction using the quadratic polynomial I gave above does indeed seem to make it converge to 4/pi, though not very quickly.
- gjm11 7y ago
  I wonder whether this one might be equivalent to a known infinite product for pi or pi/4 or something. The ratios between successive convergents are all of the form (a_n+k_n)/a_n where k_n is 1, 1, 3, 3, 15, 15, 105, 105, 315, 315, ... -- i.e., the least common multiples of odd numbers up to n. [EDITED to add:] This should make you think of the Wallis product formula for pi/4, though this doesn't seem to be the Wallis product in disguise. Clearly these k_n divide n!, so maybe the right way to say this is that the conjecture seems to be equivalent to 4/pi = product (a_n+n!)/a_n where (a_n) = (4,130,2464,45448,882528,18410640,...) ... though I don't know what that sequence _is_, haven't shown that it has a nice form, etc. None of (a_n), (a_n+n!), (a_n+n!/2) seems to occur in OEIS or to be a subsequence of anything in OEIS.

Zenst 7y ago

I was pondering a few weeks back about the prospects of using ML/AI to find new ways to factor primes and if their is any sequence in primes and how to calculate them in a way that you input N and it will produce the Nth prime. That would be something.

m3kw9 7y ago
Can primes be estimated?
- drinfinity 7y ago
  Through my genius I've come to the conclusion that primes are related to entropy. There is no hope.
- OscarCunningham 7y ago
  The nth prime is about nlog(n).
klipt 7y ago
We can already do this approximately (asymptotically): https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem "The prime number theorem is equivalent to the statement that the nth prime number p_n satisfies p_n ~ nlog(n) the asymptotic notation meaning, again, that the relative error of this approximation approaches 0 as n increases without bound. For example, the 2^1017th prime number is 8512677386048191063, and (2^1017)log(2^1017) rounds to 7967418752291744388, a relative error of about 6.4%."
- eesmith 7y ago
  https://www.johndcook.com/blog/2019/06/20/bounds-on-the-nth-prime/ https://www.johndcook.com/blog/2019/06/20/bounds-on-the-nth-... is a recent blog posted titled "Bounds on the nth prime". It lists tighter upper and lower bounds: from math import log def f(n, k): ln = log(n); lln = log(log(n)) return ln + lln - 1 + (lln-2)/ln - ((lln**2) - 6*lln+k)/(2*ln*ln) With that in place, and once I realized that 2^1017 mean 2E17 not 2 to the power of 1017: >>> n = 2E17 >>> lo = n * f(n, 11.847) >>> hi = n * f(n, 10.273) >>> lo 8.512627944213742e+18 >>> hi 8.512727125430618e+18 >>> exact = 8512677386048191063 >>> (exact - lo)/exact 5.80802398678381e-06 >>> (exact - hi)/exact -5.842977499434444e-06

xvilka 7y ago

I wonder if it somehow can be integrated with Coq[1] and Univalent Foundations[2]. Probably these can be used as a more substantial "base" for this machine. [1] https://github.com/coq/coq https://github.com/coq/coq [2] https://github.com/UniMath https://github.com/UniMath

mathandpoop 7y ago

"New mathematics" is a bit of an overstatement. There is a lot more to maths than continued fractions. It bugs me a bit that the authors write (I would love for anyone affiliated with the project to talk to me about this) "Any new conjecture, proof, or algorithm suggested will be named after you.". No offense, but there are very few mathematicians out there with that kind of a world view. Seems a bit like a high school project without proper guidance from a mathematician.