More Examples

There is a growingly vast number of results in which discoveries by integer relation algorithms played an important role. We briefly list three more of these. In all cases, developing the right model (i.e., the form of the relations to be searched for) was absolutely key, but the machine discovery of relations holding in the model was an equally essential prerequisite to success.

1. Borwein and Bradley [10,11] considered the well-known formula for $\zeta(3)$, used by Apéry in his irrationality proof, and recalled that there are no immediately analogous formulae for $\zeta(5),\zeta(7),\ldots$ . In other words, if there are relatively prime integers p and qsuch that

$$\zeta(5)={p\over q}\sum_{k=1}^\infty {{(-1)^{k+1}}\over{k^5{{2k}\choose k}}},$$

then q is astronomically large.

However, a less known formula for $\zeta(5)$ due to Koecher [30] suggested generalizations for $\zeta(7),\zeta(9),\ldots$, with the coefficients in these formulae determined by an LLL integer relation algorithm. For example,

 

$$\zeta(7)={5\over 2}\sum_{k=1}^\infty {{(-1)^{k+1}}\over{k^7{{2k}\... ...}^\infty {{(-1)^{k+1}}\over{k^3{{2k}\choose k}}} \sum_{j=1}^{k-1}{1\over{j^4}}.$$ (14)

(It is interesting to note that (14) is similar to, but simpler than, the formula for $\zeta(7)$ in [30].) The authors were able--by finding LLL based relations for $n=1,2,\ldots,10$--to encapsulate the formulae for $\zeta(4n+3)$in a single conjectured generating function [10,11]: For any complex z, we have

 

$$\sum_{n=1}^\infty \zeta(4n+3)z^{4n} \sum_{k=1}^\infty {1\over{k^3(1-z^4/k^4)}}$$ =

$${5\over 2}\sum_{k=1}^\infty {{(-1)^{k-1}}\over{k^3{{2k}\choose k}}} {1\over{(1-z^4/k^4)}} \prod_{m=1}^{k-1}{{1+4z^4/m^4}\over{1-z^4/m^4}}.$$ = (15)

Borwein and Bradley found many reformulations of (15), including a finite sum:

$$\sum_{k=1}^n{{2n^2}\over{k^2}} { {\prod_{i=1}^{n-1}(i^4+4k^4)} \over {\prod_{i=1,\:i\neq k}^{n}(k^4-i^4)} } = {{2n}\choose n}.$$

This identity was subsequently proved by Almkvist and Granville [1], thus finishing the proof of (15) and giving a rapidly converging series for any $\zeta(4n+3)$ where n is positive integer.

2. Bailey, Borwein and Plouffe  [3] discovered a new series for $\pi$ (and for some other polylogarithmic constants) which allows one to compute hexadecimal digits of $\pi$ without computing the previous digits. The algorithm needs very little memory, does not need multiple precision and the running time grows only slightly faster than linearly in the order of the digit being computed. The key formula, discovered using the PSLQ algorithm, is  [3]

 

$$\pi=\sum_{k=0}^\infty \left({1\over{16}}\right)^k \left({4\over{8k+1}}-{2\over{8k+4}}-{1\over{8k+5}}-{1\over{8k+6}}\right).$$ (16)

The authors knew that an algorithm would follow from such a formula and spent several months hunting for one. In 1997, F. Bellard [6] used a variant formula to compute 152 binary digits of $\pi$, starting at the trillionth position (10¹²), and in 1998 C. Percival [35] used Bellard's formula to compute 80 binary digits of $\pi$, starting at the five trillionth position. These computations both used dozens of workstations working in parallel over the Internet.

3. The Catalan constant is defined by

$$G=\sum_{k=0}^\infty {{(-1)^k}\over{(2k+1)^2}}.$$ (17)

Bradley [16] considered the following series for the Catalan constant, due to Ramanujan (see [7], p. 386)

$$G={\pi\over 8}\log(2+\sqrt{3}) +{3\over 8}\sum_{k=0}^\infty{1\over{(2k+1)^2{{2k}\choose k}}}$$

and showed that this series is a member of an entire family of expansions accelerating (17). Another example of a series from this family is

$$G={\pi\over 8} \log \left( { {10+\sqrt{50-22\sqrt{5}}} \over... ...r 8}\sum_{k=0}^\infty{{L(2k+1)}\over{(2k+1)^2{{2k}\choose k}}}$$ (18)

where L(n) are the Lucas numbers: L(1)=1, L(2)=3 and L(n)=L(n-1)+L(n-2) for n>2. At the heart of proving the general formula for this family of series are certain transformations for log tangent integrals, discovered by an LLL integer relation algorithm. For example, the expansion (18) is proved using the transformation

$$2\int_0^{\pi/4} \log(\tan \theta)\,d\theta = 5\int_0^{3\pi/20... ...theta)\,d\theta - 5\int_0^{\pi/20} \log(\tan \theta)\,d\theta.$$

In contrast to the original series, it is easy to hunt numerically for relations between different $\int_0^{\frac {p}{q} \pi} \log(\tan \theta)\,d\theta$.

Using Bailey's fast implementation of PSLQ (Section 2.2), Broadhurst [18] found the following series for the Catalan constant:

 

$$3\sum_{k=0}^\infty {1\over{2\cdot 16^k}} \Big( {1\over{(8k+1)^2}} - {1\over{(8k+2)^2}} + {1\over{2(8k+3)^2}}$$ G =

$$\phantom{3\sum_{k=0}^\infty {1\over{2\cdot 16^k}} \Big( } - {1\over{2^2(8k+5)^2}}+ {1\over{2^2(8k+6)^2}}- {1\over{2^3(8k+7)^2}} \Big)$$

$$-2\sum_{k=0}^\infty {1\over{8\cdot 16^{3k}}} \Big( {1\over{(8k+1)^2}} + {1\over{2(8k+2)^2}} + {1\over{2^3(8k+3)^2}}$$

$$\phantom{-2\sum_{k=0}^\infty {1\over{2\cdot 16^{3k}}} \Big( } - {1\over{2^6(8k+5)^2}}- {1\over{2^7(8k+6)^2}}- {1\over{2^9(8k+7)^2}} \Big)$$ (19)

This series is similar to (16) in structure and purpose; it allows one to compute remote binary digits of G fast and in little memory, without computing the previous digits.