Jump to content

User:Wirkstoff/sandbox

From Wikipedia, the free encyclopedia

Tools

[edit]

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

[edit]

The Bernoulli numbers can be expressed in terms of the Riemann zeta function as Bn = − 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 B1 = 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 pBp−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

[edit]

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 B2, B4, ..., Bp−3 then xp + yp + zp = 0 has no solutions in non-zero integers.

Prime numbers with this property are called regular primes (OEISA007703). 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

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

p-adic continuity

[edit]

If b, m and n are positive integers such that m and n are not divisible by p − 1 and , then

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

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 − ps 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 , and so can be extended to a continuous function ζp(s) for all p-adic integers , the p-adic Zeta function.

Ramanujan's congruences

[edit]

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

Von Staudt–Clausen theorem

[edit]

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, aa', ..., 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, pp', 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 B88 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(kk + 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 In such that

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. I1 = 2 and for odd n > 1, In = 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?

[edit]

The sum

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 B2k+1−m is 0 for m odd and greater than 1; and that the term for B1 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 2Bn is an integer. This seems trivial if one knows beforehand that in this case Bn = 0. However, by applying Worpitzky's representation one gets

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 Sn,m be the number of surjective maps from {1, 2, ..., n} to {1, 2, ..., m}, then . The last equation can only hold if

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

[edit]

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

denotes the rising factorial power in the notation of D. E. Knuth. The number βn = Bn/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

[edit]

The Stirling polynomials σn(x) are related to the Bernoulli numbers by Bn = nn(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 = [a1,a2,..., ak] of the tree, the left child of the node is L(N) =  [-a1,a2+1,a3,...,ak] and the right child R(N) = [a1,2,a2,...,ak].

Given a node N the factorial of N is defined as

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

For example B1 = 1!(1/2!), B2 = 2!(-1/3!+1/(2!2!)), B3 = 3!(1/4!-1/(2!3!)-1/(3!2!)+1/(2!2!2!)).

Sum of Powers

[edit]

Bernoulli's Formula

[edit]

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

are always polynomials in n of degree m + 1. Note that Sm(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:

Let n ≥ 0. Taking m to be 0 and B0 = 1 gives the natural number 0,1,2,3,… (sequence OEISA001477).

Taking m to be 1 and B1 = 1/2 gives the triangular number 0,1,3,6,… (sequence OEISA000217).

Taking m to be 2 and B2 = 1/6 gives the square pyramidal number 0,1,5,14,… (sequence OEISA000330).

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:

To avoid a contradiction to the valid formula above these authors have to set B1 = -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

[edit]

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, Sm(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:

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 B0, B1, B2, … would provide a uniform

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 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

[edit]

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 B1 = 1/2 some authors set B1 = —1/2 (more on different conventions below). In order to prevent potential confusions both variants will be described here, side by side.

Recursive definition

[edit]

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

This equation defines integers Bm(n) for all integers n ≥ 0, m ≥ 0. 00 has to be interpreted as 1. The recursion has its base in B0(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

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 Bm(0) in the first case and Bm(1) in the second will unambiguously denote the value in question.

Explicit definition

[edit]

Starting again with a slightly more general formula

the choices n = 0 and n = 1 lead to

n = 0 n = 1

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

[edit]

The general formula for the generating function is

The choices n = 0 and n = 1 lead to

n = 0 n = 1

Algorithmic description

[edit]

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
  • Jacobi, C. G. J. (1834), "De usu legitimo formulae summatoriae Maclaurinianae", Journal für die reine und angewandte Mathematik, 12: 263–272

Short table

[edit]

Bn = 0 for all odd n other than 1. B1 = 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.