5 ms·

In layman's term, how did one discover this series which generates the pi digit patterns?

loa_in_ 5y ago
Lots and lots and lots of experimentation (experimentation on paper) and looking out for clever ways to find parts of the equation-at-hand that cancel each other out, so that the resulting notation is hopefully as short and practical as the equation is good at being accurate.
abetusk 5y ago
Judicious use of lattice reduction techniques such as LLL [0] or other integer relation algorithms, like PSLQ [1]. The basic idea with LLL is that it's a sort of generalized Euclid's algorithm. Euclid's algorithm can be made to find the smallest integer relation between two numbers that sums to zero (efficiently). You can generalize Euclid's algorithm to more numbers and to use vectors instead of base integers, except now the "divide, take the integer quotient and subtract" becomes "take off the integral component of the projection and subtract, then swap entries to try and make progress". Lattice reduction techniques give a polynomial algorithm to factor polynomials with integral coefficients (does the polynomial factor into other polynomials with integral coefficients). To use lattice reduction techniques, you set up a "lattice basis" that has successive powers of pi (pi^0, pi^1, pi^2 etc) up to a certain accuracy and then tries to find an integer relation between them. Once one is found, it's checked to see if it actually equals pi by other techniques. For an introduction to LLL, I've found Chee Yap's book to be good (see chapter VIII) [2]. Plouffe has a little bit of history about the discovery and how Bailey and Borwein muscled in [3]. [0] https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%... [1] https://en.wikipedia.org/wiki/Integer_relation_algorithm https://en.wikipedia.org/wiki/Integer_relation_algorithm [2] http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental%20Problems%20in%20Algorithmic%20Algebra%201993%20Yap.pdf http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental... [3] http://xahlee.info/math/Simon_Plouffe_pi_formula.html http://xahlee.info/math/Simon_Plouffe_pi_formula.html
- phkahler 5y ago
  >> Lattice reduction techniques give a polynomial algorithm to factor polynomials with integral coefficients (does the polynomial factor into other polynomials with integral coefficients) Wait, are you saying factorization of polynomials is in P? That doesn't feel right since factoring integers has not been shown to be in P (yet).
  - abetusk 5y ago
    Yes, that's what I'm saying. Factoring univariate polynomials with integer coefficients (that is, seeing if a polynomial with integer coefficients has smaller degree polynomial factors with integer coefficients) is in P [0]. Factoring univariate polynomials over the integers has known to be in P since the 1980s (since LLL came out, which is one of the major reasons why LLL was developed in the first place). Integer factorization is still currently unknown to be in P or not in P. If you see how to use polynomial factoring to factor integers, please let me know. [0] https://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers https://en.wikipedia.org/wiki/Factorization_of_polynomials#F...
paulpauper 5y ago
A simple derivation of such formulas is given here https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3919892 https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3919892 The idea is you begin with an elementary integral that yields the underlying constant, such as pi, and then accelerate its convergence by using a polynomial. Ramanujan-like pi formulas can be derived similar to the Fabrice Bellard one, but with an inverse cosine instead of elliptic integrals. Visually, the formulas look like the Ramanujan pi formulas, but the derivation is elementary and it computes pi, not the reciprocal of pi. The Bellard and Simon formulas use inverse trig functions as well. I think he uses arctan.

Lots and lots and lots of experimentation (experimentation on paper) and looking out for clever ways to find parts of the equation-at-hand that cancel each other out, so that the resulting notation is hopefully as short and practical as the equation is good at being accurate.

abetusk 5y ago

Judicious use of lattice reduction techniques such as LLL [0] or other integer relation algorithms, like PSLQ [1]. The basic idea with LLL is that it's a sort of generalized Euclid's algorithm. Euclid's algorithm can be made to find the smallest integer relation between two numbers that sums to zero (efficiently). You can generalize Euclid's algorithm to more numbers and to use vectors instead of base integers, except now the "divide, take the integer quotient and subtract" becomes "take off the integral component of the projection and subtract, then swap entries to try and make progress". Lattice reduction techniques give a polynomial algorithm to factor polynomials with integral coefficients (does the polynomial factor into other polynomials with integral coefficients). To use lattice reduction techniques, you set up a "lattice basis" that has successive powers of pi (pi^0, pi^1, pi^2 etc) up to a certain accuracy and then tries to find an integer relation between them. Once one is found, it's checked to see if it actually equals pi by other techniques. For an introduction to LLL, I've found Chee Yap's book to be good (see chapter VIII) [2]. Plouffe has a little bit of history about the discovery and how Bailey and Borwein muscled in [3]. [0] https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%... [1] https://en.wikipedia.org/wiki/Integer_relation_algorithm https://en.wikipedia.org/wiki/Integer_relation_algorithm [2] http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental%20Problems%20in%20Algorithmic%20Algebra%201993%20Yap.pdf http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental... [3] http://xahlee.info/math/Simon_Plouffe_pi_formula.html http://xahlee.info/math/Simon_Plouffe_pi_formula.html

phkahler 5y ago
>> Lattice reduction techniques give a polynomial algorithm to factor polynomials with integral coefficients (does the polynomial factor into other polynomials with integral coefficients) Wait, are you saying factorization of polynomials is in P? That doesn't feel right since factoring integers has not been shown to be in P (yet).
- abetusk 5y ago
  Yes, that's what I'm saying. Factoring univariate polynomials with integer coefficients (that is, seeing if a polynomial with integer coefficients has smaller degree polynomial factors with integer coefficients) is in P [0]. Factoring univariate polynomials over the integers has known to be in P since the 1980s (since LLL came out, which is one of the major reasons why LLL was developed in the first place). Integer factorization is still currently unknown to be in P or not in P. If you see how to use polynomial factoring to factor integers, please let me know. [0] https://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers https://en.wikipedia.org/wiki/Factorization_of_polynomials#F...

paulpauper 5y ago

A simple derivation of such formulas is given here https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3919892 https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3919892 The idea is you begin with an elementary integral that yields the underlying constant, such as pi, and then accelerate its convergence by using a polynomial. Ramanujan-like pi formulas can be derived similar to the Fabrice Bellard one, but with an inverse cosine instead of elliptic integrals. Visually, the formulas look like the Ramanujan pi formulas, but the derivation is elementary and it computes pi, not the reciprocal of pi. The Bellard and Simon formulas use inverse trig functions as well. I think he uses arctan.