Bernoulli, Ramanujan, Toeplitz and the triangular matrices

Carmine Di Fiore, Francesco Tudisco, Paolo ZelliniarXiv 2013 · DOI · arXiv

Abstract

By using one of the definitions of the Bernoulli numbers, we prove that they solve particular odd and even lower triangular Toeplitz (l.t.T.) systems of equations. In a paper Ramanujan writes down a sparse lower triangular system solved by Bernoulli numbers; we observe that such system is equivalent to a sparse l.t.T. system. The attempt to obtain the sparse l.t.T. Ramanujan system from the l.t.T. odd and even systems, has led us to study efficient methods for solving generic l.t.T. systems. Such methods are here explained in detail in case $n$, the number of equations, is a power of $b$, $b=2,3$ and $b$ generic.

Introduction

Bernoulli numbers ($B_n$) are fundamental constants in number theory, appearing in diverse mathematical contexts such as the Euler-Maclaurin formula, the values of the Riemann Zeta function, and the coefficients of the power series expansion of trigonometric functions. Despite their importance, computing $B_n$ for large $n$ is a significant challenge. Their numerators grow at an enormous rate, necessitating high-precision arithmetic and algorithms that can handle the computational load efficiently.

Historically, identities for Bernoulli numbers have been recursive or involved infinite sums. This paper bridges the gap between classical number theory and modern computational linear algebra by exploiting the algebraic structure of lower triangular Toeplitz (l.t.T.) matrices. By framing the computation of Bernoulli numbers as a problem of solving structured linear systems, the authors develop algorithms with $O(n \log n)$ complexity.

The Toeplitz Connection

A Toeplitz matrix is defined by having constant entries along its diagonals. The authors demonstrate that the set of all l.t.T. matrices forms a commutative algebra. This property is crucial because it implies that solving l.t.T. systems is essentially equivalent to performing polynomial arithmetic, which can be highly optimized using transform-based methods.

The paper proves that Bernoulli numbers satisfy specific "even" and "odd" l.t.T. systems derived from the power series expansion of $t/(e^t - 1)$. This structured approach allows for the simultaneous computation of the first $n$ Bernoulli numbers by inverting the coefficient matrix of these systems.

Ramanujan’s Sparse System

A central inspiration for this work is a sparse system of 11 equations proposed by Srinivasa Ramanujan in 1911. The authors analyze this system and prove its equivalence to a sparse l.t.T. system where two out of every three diagonals are zero.

This discovery suggests that Ramanujan’s approach was not merely a clever shortcut but a rigorous exploitation of matrix sparsity. The Ramanujan-Toeplitz system is shown to be more efficient than standard even or odd systems because its sparsity pattern—alternating one non-null diagonal with two null ones—reduces the number of required operations.

Algorithmic Innovation: Diagonal Nullification

To solve these l.t.T. systems, the authors propose a "Diagonal-Nullifying" algorithm. Unlike standard Gaussian elimination, which focuses on eliminating columns, this recursive strategy transforms the l.t.T. matrix into the identity matrix by nullifying diagonals.

For a system of size $n = b^s$, the algorithm uses a divide-and-conquer approach. When integrated with the Fast Fourier Transform (FFT) for matrix-vector products, the overall computational complexity is reduced to $O(n \log_b n)$. Interestingly, while base-2 ($b=2$) is the standard in computer science, the authors show that a base-3 ($b=3$) approach is more natural for Ramanujan-type systems, as it aligns perfectly with the "two null diagonals" pattern found in his sparse formulation.

Key Results and Unifying Theorem

The paper culminates in a "Unifying Theorem" that presents six distinct l.t.T. systems (categorized as types I and II for even, odd, and Ramanujan versions) that Bernoulli numbers satisfy. Key findings include:

  • Computational Efficiency: The proposed algorithms achieve a cost of $O(n \log n)$ for computing the first $n$ Bernoulli numbers.
  • Direct Solvers: The approach provides a direct path to the inverse of the coefficient matrix, avoiding some of the pitfalls of purely recursive formulas.
  • Sparsity Advantage: The Ramanujan-Toeplitz system is identified as a superior candidate for fast solvers due to its high degree of sparsity.

Limitations and Future Directions

While the mathematical framework is robust, the paper notes areas for further exploration. A rigorous numerical stability analysis for extremely large $n$ (e.g., millions of digits) is not provided, though the authors suggest parameters to keep sequences bounded. Additionally, while the algorithms are theoretically suited for parallel computing, empirical benchmarks against existing specialized software like calcbn remain a task for future implementation studies. The exploration of general bases $b$ for the diagonal-nullifying algorithm also offers a fertile ground for further algorithmic refinement.

Summary updated

Abstract

By using one of the definitions of the Bernoulli numbers, we prove that they solve particular odd and even lower triangular Toeplitz (l.t.T.) systems of equations. In a paper Ramanujan writes down a sparse lower triangular system solved by Bernoulli numbers; we observe that such system is equivalent to a sparse l.t.T. system. The attempt to obtain the sparse l.t.T. Ramanujan system from the l.t.T. odd and even systems, has led us to study efficient methods for solving generic l.t.T. systems. Such methods are here explained in detail in case n, the number of equations, is a power of b, b=2,3 and b generic.
BibTeX
@misc{fiore2013bernoulli,
  author = {Carmine Di Fiore and Francesco Tudisco and Paolo Zellini},
  title = {{Bernoulli, Ramanujan, Toeplitz and the triangular matrices}},
  year = {2013},
  eprint = {1307.3108},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1307.3108},
}
Figure