User:Wirkstoff/sandbox

Tools

MOSMATH Citation Tools Special Examples

{{{Bernoulli number}}}
{{{images}}}
Algebraic type	France
Numerator	{{{rég}}}
Denominator	{{{dépt}}}
Closed formula	{{{nbcomm}}}
Algorithm	{{{pop}}} hab. (??)
Generating function	{{{dens}}} pop./km²

LinkLable

Arithmetical properties of the Bernoulli numbers

The Bernoulli numbers can be expressed in terms of the Riemann zeta function as B_n = − nζ(1 − n) for integers n ≥ 0 provided for n = 0 and n = 1 the expression − nζ(1 − n) is understood as the limiting value and the convention B₁ = 1/2 is used. This intimately relates them to the values of the zeta function at negative integers. As such, they could be expected to have and do have deep arithmetical properties. For example the Agoh-Giuga conjecture postulates that p is a prime number if and only if pB_p−1 is congruent to −1 mod p. Divisibility properties of the Bernoulli numbers are related to the ideal class groups of cyclotomic fields by a theorem of Kummer and its strengthening in the Herbrand-Ribet theorem, and to class numbers of real quadratic fields by Ankeny-Artin-Chowla.

The Kummer theorems

The Bernoulli numbers are related to Fermat's last theorem (FLT) by Kummer's theorem, which says:

If the odd prime p does not divide any of the numerators of the Bernoulli numbers B₂, B₄, ..., B_p−3 then x^p + y^p + z^p = 0 has no solutions in non-zero integers.

Prime numbers with this property are called regular primes (OEIS: A007703). Another classical result of Kummer are the following congruences.

Let p be an odd prime and b an even number such that p − 1 does not divide b. Then for any non-negative integer k

${\frac {B_{k(p-1)+b}}{k(p-1)+b}}\ \equiv \ {\frac {B_{b}}{b}}\mod p\ .$

A generalization of these congruences goes by the name of p-adic continuity.

p-adic continuity

If b, m and n are positive integers such that m and n are not divisible by p − 1 and $m\equiv n\,{\bmod {\,}}p^{b-1}(p-1)$, then

$(1-p^{m-1}){B_{m} \over m}\equiv (1-p^{n-1}){B_{n} \over n}\,{\bmod {\,}}p^{b}.$

Since B_n = —n ζ(1 — n), this can also be written

$(1-p^{-u})\zeta (u)\equiv (1-p^{-v})\zeta (v)\,{\bmod {\,}}p^{b}\,,$

where u = 1 − m and v = 1 − n, so that u and v are nonpositive and not congruent to 1 mod p − 1. This tells us that the Riemann zeta function, with 1 − p^−s taken out of the Euler product formula, is continuous in the p-adic numbers on odd negative integers congruent mod p − 1 to a particular $a\not \equiv 1\,{\bmod {\,}}p-1$, and so can be extended to a continuous function ζ_p(s) for all p-adic integers $\mathbb {Z} _{p}\,$, the p-adic Zeta function.

Ramanujan's congruences

The following relations, due to Ramanujan, provide a more efficient method for calculating Bernoulli numbers:

$m\equiv 0\,{\bmod {\,}}6\qquad {{m+3} \choose {m}}B_{m}={{m+3} \over 3}-\sum _{j=1}^{m/6}{m+3 \choose {m-6j}}B_{m-6j}$

$m\equiv 2\,{\bmod {\,}}6\qquad {{m+3} \choose {m}}B_{m}={{m+3} \over 3}-\sum _{j=1}^{(m-2)/6}{m+3 \choose {m-6j}}B_{m-6j}$

$m\equiv 4\,{\bmod {\,}}6\qquad {{m+3} \choose {m}}B_{m}=-{{m+3} \over 6}-\sum _{j=1}^{(m-4)/6}{m+3 \choose {m-6j}}B_{m-6j}.$

Von Staudt–Clausen theorem

The von Staudt–Clausen theorem was given by Karl Georg Christian von Staudt and Thomas Clausen independently in 1840. It describes the arithmetical structure of the Bernoulli numbers.

The von Staudt–Clausen theorem has two parts. The first one describes how the denominators of the Bernoulli numbers can be computed. Paraphrasing the words of Clausen it can be stated as:

“The denominator of the 2nth Bernoulli number can be found as follows: Add to all divisors of 2n, 1, 2, a, a', ..., 2n the unity, which gives the sequence 2, 3, a + 1, a' + 1, ..., 2n + 1. Select from this sequence only the prime numbers 2, 3, p, p', etc. and build their product.”

Clausen's algorithm translates almost verbatim to a modern computer algebra program, which looks similar to the pseudocode on the left hand site of the following table. On the right hand side the computation is traced for the input n = 88. It shows that the denominator of B₈₈ is 61410. 

Clausen's algorithm for the denominator of Bn
Clausen: function(integer n)	|	n = 88
S = divisors(n);	|	{1, 2, 4, 8, 11, 22, 44, 88}
S = map(k → k + 1, S);	|	{2, 3, 5, 9, 12, 23, 45, 89}
S = select(isprime, S);	|	{2, 3, 5, 23, 89}
return product(S);	|	61410

The second part of the von Staudt–Clausen theorem is a very remarkable representation of the Bernoulli numbers. This representation is given for the first few nonzero Bernoulli numbers in the next table.

Von Staudt–Clausen representation of Bn
B0	=	1
B1	=	1 − 1/2
B2	=	1 − 1/2 − 1/3
B4	=	1 − 1/2 − 1/3 − 1/5
B6	=	1 − 1/2 − 1/3 − 1/7
B8	=	1 − 1/2 − 1/3 − 1/5
B10	=	1 − 1/2 − 1/3 − 1/11

The theorem affirms the existence of an integer I_n such that

$B_{n}={\frac {I_{n}}{2}}-\sum _{(p-1)|n}{\frac {1}{p}}\quad (n\geq 0)\ .$

The sum is over the primes p for which p − 1 divides n. These are the same primes which are employed in the Clausen algorithm. The proposition holds true for all n ≥ 0, not only for even n. I₁ = 2 and for odd n > 1, I_n = 1.

A consequence of the von Staudt–Clausen theorem is: the denominators of the Bernoulli numbers are square-free and for n ≥ 2 divisible by 6.

Why do the odd Bernoulli numbers vanish?

The sum

$\varphi _{k}(n)=\sum _{i=0}^{n}i^{k}-{\frac {n^{k}}{2}}$

can be evaluated for negative values of the index n. Doing so will show that it is an odd function for even values of k, which implies that the sum has only terms of odd index. This and the formula for the Bernoulli sum imply that B_2k+1−m is 0 for m odd and greater than 1; and that the term for B₁ is cancelled by the subtraction. The von Staudt-Clausen theorem combined with Worpitzky's representation also gives a combinatorial answer to this question (valid for n > 1).

From the von Staudt-Clausen theorem it is known that for odd n > 1 the number 2B_n is an integer. This seems trivial if one knows beforehand that in this case B_n = 0. However, by applying Worpitzky's representation one gets

$2B_{n}=\sum _{m=0}^{n}\left(-1\right)^{m}{\frac {2}{m+1}}m!\left\{{\begin{matrix}n+1\\m+1\end{matrix}}\right\}=0\quad \left(n>1\ {\text{odd}}\right)$

as a sum of integers, which is not trivial. Here a combinatorial fact comes to surface which explains the vanishing of the Bernoulli numbers at odd index. Let S_n,m be the number of surjective maps from {1, 2, ..., n} to {1, 2, ..., m}, then $S_{n,m}=m!\left\{{\begin{matrix}n\\m\end{matrix}}\right\}$. The last equation can only hold if

$\sum _{m=1,3,5,\ldots \leq n}{\frac {2}{m^{2}}}S_{n,m}=\sum _{m=2,4,6,\ldots \leq n}{\frac {2}{m^{2}}}S_{n,m}\quad \left(n>2{\text{ even}}\right).\$

This equation can be proved by induction. The first two examples of this equation are

n = 4 :  2 + 8 = 7 + 3,  n = 6:  2 + 120 + 144 = 31 + 195 + 40.

Thus the Bernoulli numbers vanish at odd index because some non-obvious combinatorial identities are embodied in the Bernoulli numbers.

A restatement of the Riemann hypothesis

The connection between the Bernoulli numbers and the Riemann zeta function is strong enough to provide an alternate formulation of the Riemann hypothesis (RH) which uses only the Bernoulli number. In fact in 1916 M. Riesz proved that the RH is equivalent to the following assertion:

For every ε > 1/4 there exists a constant C_ε > 0 (depending on ε) such that |R(x)| < C_ε x^ε as x → ∞.

Here R(x) is the Riesz function

$R(x)=2\sum _{k=1}^{\infty }{\frac {k^{\overline {k}}x^{k}}{(2\pi )^{2k}\left(B_{2k}/(2k)\right)}}=2\sum _{k=1}^{\infty }{\frac {k^{\overline {k}}x^{k}}{(2\pi )^{2k}\beta _{2k}}}.\$

$n^{\overline {k}}$ denotes the rising factorial power in the notation of D. E. Knuth. The number β_n = B_n/n occur frequently in the study of the zeta function and are significant because β_n is a p-integer for primes p where p − 1 does not divide n. The β_n are called divided Bernoulli number.

The S. C. Woon binary tree representation

The Stirling polynomials σ_n(x) are related to the Bernoulli numbers by B_n = n!σ_n(1). S. C. Woon (Woon 1997) described an algorithm to compute σ_n(1) as a binary tree.

Woon's tree for σn(1)

Woon's recursive algorithm (for n ≥ 1) starts by assigning to the root node N = [1,2]. Given a node N = [a₁,a₂,..., a_k] of the tree, the left child of the node is L(N) =  [-a₁,a₂+1,a₃,...,a_k] and the right child R(N) = [a₁,2,a₂,...,a_k].

Given a node N the factorial of N is defined as

$N!=a_{1}\prod _{k=2...{\text{length}}(N)}a_{k}!\ .$

Restricted to the nodes N of a fixed tree-level n the sum of 1/N! is σ_n(1), thus

$B_{n}=\sum _{N\ {\text{node of tree-level}}\ n}{\frac {n!}{N!}}\ .$

For example B₁ = 1!(1/2!), B₂ = 2!(-1/3!+1/(2!2!)), B₃ = 3!(1/4!-1/(2!3!)-1/(3!2!)+1/(2!2!2!)).

Sum of Powers

Bernoulli's Formula

Closed forms of the sum of powers for fixed values of m

$\ \ S_{m}(n)=\sum _{k=1}^{n}k^{m}=1^{m}+2^{m}+\cdots +{n}^{m}\ \$

are always polynomials in n of degree m + 1. Note that S_m(0) = 0 for all m ≥ 0 because in this case the sum is the empty sum. The coefficients of these polynomials are related to the Bernoulli numbers by Bernoulli's formula:

$S_{m}(n)={1 \over {m+1}}\sum _{k=0}^{m}{m+1 \choose {k}}B_{k}n^{m+1-k}$

Let n ≥ 0. Taking m to be 0 and B₀ = 1 gives the natural number 0,1,2,3,… (sequence OEIS: A001477).

$0+1+1+\cdots +1={\frac {1}{1}}\left(B_{0}n\right)=n.$

Taking m to be 1 and B₁ = 1/2 gives the triangular number 0,1,3,6,… (sequence OEIS: A000217).

$0+1+2+\cdots +n={\frac {1}{2}}\left(B_{0}n^{2}+2B_{1}n^{1}\right)={\frac {1}{2}}\left(n^{2}+n\right).$

Taking m to be 2 and B₂ = 1/6 gives the square pyramidal number 0,1,5,14,… (sequence OEIS: A000330).

$0^{2}+1^{2}+2^{2}+\cdots +n^{2}={\frac {1}{3}}\left(B_{0}n^{3}+3B_{1}n^{2}+3B_{2}n^{1}\right)={\frac {1}{3}}\left(n^{3}+{\frac {3}{2}}n^{2}+{\frac {1}{2}}n\right).$

Although Bernoulli's formula reflects faithfully what Bernoulli has written some authors state Bernoulli's formula in a different way which is neither in accordance with Bernoulli's statement nor has any obvious advantage compared to it. They write:

$S_{m}(n)={1 \over {m+1}}\sum _{k=0}^{m}(-1)^{k}{m+1 \choose {k}}B_{k}n^{m+1-k}$

To avoid a contradiction to the valid formula above these authors have to set B₁ = -1/2. In the next section consequences of the resulting differences will be commented on as they are likely to produce some confusion.

Faulhaber's Formula

Bernoulli's formula is sometimes called Faulhaber's formula. There is no evidence which justifies this nomenclature. Johann Faulhaber found remarkable ways to calculate sum of powers but he never stated Bernoulli's formula.

Faulhaber realized that for odd m, S_m(n) is not just a polynomial in n but a polynomial in the triangular number N = n(n + 1)/2. For example Faulhaber's formulas read as follows:

$1+2+\cdots +n=N;$

$1^{2}+2^{2}+\cdots +n^{2}=N\left(2n+1\right)/3;$

$1^{3}+2^{3}+\cdots +n^{3}=N^{2}.$

To call Bernoulli's formula Faulhaber's formula does injustice to Bernoulli and simultaneously hides the genius of Faulhaber as Faulhaber's formula is in fact more efficient than Bernoulli's formula. According to Knuth (Knuth 1993) a rigorous proof of Faulhaber’s formula was first published by Carl Jacobi in 1834 (Jacobi 1834). Donald E. Knuth's in-depth study of Faulhaber's Formula concludes:

“Faulhaber never discovered the Bernoulli numbers; i.e., he never realized that a single sequence of constants B₀, B₁, B₂, … would provide a uniform

$\quad \sum n^{m}={\frac {1}{m+1}}\left(B_{0}n^{m+1}-{\binom {m+1}{1}}B_{1}n^{m}+{\binom {m+1}{2}}B_{2}n^{m-1}-\cdots +(-1)^{m}{\binom {m+1}{m}}B_{m}n\right)$

for all sums of powers. He never mentioned, for example, the fact that almost half of the coefficients turned out to be zero after he had converted his formulas for $\sum n^{m}$ from polynomials in N to polynomials in n.” (Knuth 1993, p. 14)

Faulhaber's formula was generalized by V. Guo and J. Zeng to a q-analog (Guo & Zeng 2005).

Definitions

Many characterizations of the Bernoulli numbers have been found in the last 300 years, and each could be used to introduce theses numbers. Here only four of the most useful ones are mentioned:

• a recursive equation,
• an explicit formula,
• a generating function,
• an algorithmic description.

For the proof of the equivalence of the four approaches the reader is referred to mathematical expositions like (Ireland & Rosen 1990) or (Conway & Guy 1996).

Unfortunately in the literature the definition is given in two variants: Despite the fact, that Bernoulli defined B₁ = 1/2 some authors set B₁ = —1/2 (more on different conventions below). In order to prevent potential confusions both variants will be described here, side by side.

Recursive definition

The recursive equation is best introduced in a slightly more general form

$B_{m}(n)=n^{m}-\sum _{k=0}^{m-1}{\binom {m}{k}}{\frac {B_{k}(n)}{m-k+1}}\ .$

This equation defines integers B_m(n) for all integers n ≥ 0, m ≥ 0. 0⁰ has to be interpreted as 1. The recursion has its base in B₀(n) = 1 for all n. The two variants now follow by setting n = 0 respectively n = 1. Additionally the notation is simplified by erasing the reference to the parameter n.

n = 0	n = 1
$B_{m}=\left[m=0\right]-\sum _{k=0}^{m-1}{\binom {m}{k}}{\frac {B_{k}}{m-k+1}}$	$B_{m}=1-\sum _{k=0}^{m-1}{\binom {m}{k}}{\frac {B_{k}}{m-k+1}}$

Here the expression [m = 0] has the value 1 if m = 0 and 0 otherwise (Iverson bracket). Whenever a confusion between the two kinds of definitions might arise it can be avoided by refering to the more general definition and by reintroducing the erased parameter: writing B_m(0) in the first case and B_m(1) in the second will unambiguously denote the value in question.

Explicit definition

Starting again with a slightly more general formula

$B_{m}(n)=\sum _{k=0}^{m}\sum _{v=0}^{k}(-1)^{v}{\binom {k}{v}}{\frac {\left(n+v\right)^{m}}{k+1}},$

the choices n = 0 and n = 1 lead to

n = 0	n = 1
$B_{m}=\sum _{k=0}^{m}\sum _{v=0}^{k}(-1)^{v}{\binom {k}{v}}{\frac {v^{m}}{k+1}}\ ,$	$B_{m}=\sum _{k=1}^{m+1}\sum _{v=1}^{k+1}(-1)^{v+1}{\binom {k-1}{v-1}}{\frac {v^{m}}{k}}\ .$

There is a widespread misinformation that no simple closed formulas for the Bernoulli numbers exist. The last two equations show that this is not true. Moreover, already in 1893 Louis Saalschütz listed a total of 38 explicit formulas for the Bernoulli numbers (Saalschütz 1893), usually giving some reference in the older literature.

Generating function

The general formula for the generating function is

${\frac {te^{nt}}{e^{t}-1}}=\sum _{m=0}^{\infty }B_{m}(n){\frac {t^{m}}{m!}}\ .$

The choices n = 0 and n = 1 lead to

n = 0	n = 1
${\frac {t}{e^{t}-1}}=\sum _{m=0}^{\infty }B_{m}{\frac {t^{m}}{m!}}\ ,$	${\frac {t}{1-e^{-t}}}=\sum _{m=0}^{\infty }B_{m}{\frac {t^{m}}{m!}}\ .$

Algorithmic description

Although the above recursive formula can be used for computation it is mainly used to establish the connection with the sum of powers because it is computationally expensive. However, both simple and high-end algorithms for computing Bernoulli numbers exist. A simple one is given in pseudo code below in the text box 'Akiyama-Tanigawa algorithm' and pointers to high-end algorithms are given in another section below.

• Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory, Springer-Verlag

• Saalschütz, Louis (1893), Vorlesungen über die Bernoullischen Zahlen, ihren Zusammenhang mit den Secanten-Coefficienten und ihre wichtigeren Anwendungen, Berlin{{citation}}: CS1 maint: location missing publisher (link)

• Jacobi, C. G. J. (1834), "De usu legitimo formulae summatoriae Maclaurinianae", Journal für die reine und angewandte Mathematik, 12: 263–272

• Guo, Victor J. W.; Zeng, Jiang (2005), "A q-Analogue of Faulhaber's Formula for Sums of Powers", The Electronic Journal of Combinatorics, 11 (2), doi:10.37236/1876, S2CID 10467873

Short table

B_n = 0 for all odd n other than 1. B₁ = 1/2 or −1/2 depending on the convention adopted. The first few Bernoulli numbers are:

n	0	1	2	4	6	8	10	12
Bn	1	±1/2	1/6	-1/30	1/42	-1/30	5/66	-691/2730

More values below.