mailto:[email protected] CarmineDiFiore,FrancescoTudisco,PaoloZelliniDipartimentodiMatematica,Universit`adiRoma“TorVergata” LowertriangularToeplitzmatricesandthesequenceofBernoullinumbers

(1)

Ramanujan Toeplitz systems satisfied by Bernoulli numbers

Lower triangular Toeplitz matrices and the sequence of Bernoulli numbers

Carmine Di Fiore, Francesco Tudisco, Paolo Zellini Dipartimento di Matematica, Universit` a di Roma “Tor Vergata”

mailto: [email protected]

Conference on Matrix Methods in Mathematics and Applications Skolkovo Institute of Science and Technology, Moscow

August 24–28, 2015

(2)

1

Bernoulli numbers

2

Triangular Toeplitz systems satisfied by Bernoulli numbers

3

Ramanujan Toeplitz systems satisfied by Bernoulli numbers

(3)

Bernoulli numbers

B(x + 1) − B(x ) = nx

ⁿ⁻¹

, R

1

0

B(x ) dx = 0, B(x ) polynomial ⇒ B

_n

(x ) degree n Bernoulli polynomial

Note: B

_n⁰

(x ) = nB

n−1

(x ), B

n

(1 − x ) = (−1)

ⁿ

B

n

(x ), B

2j +1

(0) = 0 Bernoulli numbers: B

2j

:= B

2j

(0) = B

2j

(1), j = 0, 1, 2, . . .

1,

¹₆

, −

₃₀¹

,

₄₂¹

, −

₃₀¹

,

₆₆⁵

, −

₂₇₃₀⁶⁹¹

,

⁷₆

, −

³⁶¹⁷₅₁₀

,

⁴³⁸⁶⁷₇₉₈

, −

¹⁷⁴⁶¹¹₃₃₀

,

⁸⁵⁴⁵¹³₁₃₈

, . . . Euler formula P

+∞

k=1 1

k^2j

=

⁽⁻¹⁾^{j −1}_{2(2j )!}^B^2j^(2π)^2j

⇒ |B

_2j

| ≈

^{2(2j )!}

(2π)^2j

. Moreover B

2j

(x )

B

_2j

(0)

[0,1]

→ cos(2πx),

k

X

x =1

x

ⁿ⁻¹

= 1

n [B

n

(k+1)−B

n

(1)].

B

2j

appear in Euler-Maclaurin summation formula and error in the

trapezoidal quadrature rule, in cyclotomic fields and irregular

primes, . . .

(4)

. . . in power series expansions, in particular te

^xt

e

^t

− 1 =

+∞

X

n=0

B

_n

(x )

n! t

ⁿ

⇒ t

e

^t

− 1 = − 1 2 t +

+∞

X

k=0

B

2k

(2k)! t

^2k

,

t = − 1 2 t +

+∞

X

k=0

B

_2k

(2k)! t

^2k

+∞

X

r =0

t

^{r +1}

(r + 1)! , . . . ,

− 1 2 j +

[^{j −1}₂ ]

X

k=0

j

2k B

_2k

= 0, j = 2, 3, 4, 5, . . .

For j even and for j odd the latter equations can be rewritten

respectively as follows:

(5)







2 0

4 0

4

2 6 0

6

2

6

4 8 0

8

2

8

4

8

6 · · · · ·











 B

₀

B

₂

B

4

B

₆

· 





=





 1 2 3 4

· 





, (even)







1 0

3 0

3

2 5 0

5

2

5

4 7 0

7

2

7

4

7

6 · · · · ·











 B

0

B

₂

B

4

B

6

· 





=





 1 3/2 5/2 7/2

· 





. (odd )

(6)

Triangular Toeplitz systems satisfied by Bernoulli numbers

(even) is equivalent to a lower triangular Toeplitz (ltT) system:

Z

a2,a3,a4,...

=





 0 a

2

0 a

3

0 a

4

· · ·







, Z

a²₂,a₃,a₄,...

=





 0

0 0

a

2

a

3

0 0 a

3

a

4

0 ·

a

4

a

5

· ·





 ,

Z

_a^k₂_,a₃_,a₄_,...

=





 0

· 0

0 · 0

a

2

a

3

· a

1+k

0 · ·

a

3

a

4

· a

2+k

0 · · a

4

a

5

· a

3+k

· ·







, Z = Z

a₂,a₃,a₄,...

⇒

[Z

a^k₂,a₃,a₄,...

]

ij

= a

j +1

a

j +2

· a

j +k

if i = k + j , j = 1, 2, 3, . . .

0 otherwise , [Z

^{i −j}

]

_ij

= a

_{j +1}

· · · a

_i

(7)

Y = Z

1,2,3,...

( a

_k

= k − 1 ) ⇒

+∞

X

k=0

1 k! Y

^k

=





 0 0

1 0

1

1 2 0

2

1

2

3

0

3

1

3

2

3

4

0

4

1

4

2

4

3

4

5

0

5

1

5

2

5

3

5

4

5

6

0

6

1

6

2

6

3

6

4

6

5

6

6 · · · · · · · ·







Proof : [

+∞

X

k=0

1 k! Y

^k

]

ij

= 1

(i − j )! [Y

^{i −j}

]

ij

= 1

(i − j )! j · · · (i − 2)(i − 1) = i − 1

j − 1 .

(8)

Φ = Z

2,12,30,56,...

( a

_k

= (2k − 3)(2k − 2) ) ⇒

diag (2, 12, 30, 56, ...)

+∞

X

k=0

1 (2k + 2)! Φ

^k

=





 2 0

4 0

4

2 6 0

6

2

6

4

8

0

8

2

8

4

8

6 · · · · ·







Proof: [ diag (2, 12, 30, 56, ...) P

+∞

k=0 1

(2k+2)!

Φ

^k

]

ij

= 2i (2i − 1) P

+∞

k=0 1 (2k+2)!

φ

^k

ij

= 2i (2i − 1)

(2i −2j +2)!¹

[φ

^{i −j}

]

ij

= 2i (2i − 1)

(2i −2j +2)!¹ (2i −2)!

(2j −2)!

= 2i 2j − 2 . Thus (even) is equivalent to

+∞

X

k=0

2 (2k + 2)! Φ

^k

b = q

^e

, b = [B

0

B

2

B

4

B

6

· · · ]

^T

, q

^e

= [1 1 3

1 5

1 7 · · · ]

^T

.

(9)

D = diag 1,

_2!^x

,

^x_4!²

, · · · ,

_(2n−2)!^xⁿ⁻¹

, · · · , x ∈ R ⇒

DΦD

⁻¹

= xZ , DΦ

^k

D

⁻¹

= (DΦD

⁻¹

)

^k

= x

^k

Z

^k

, Z = Z

1,1,1,...

Thus (even) is equivalent to the following ltT system:

+∞

X

k=0

2x

^k

(2k + 2)! Z

^k

Db = Dq

^e

. (even ltT ) Analogously, (odd) is equivalent to the following ltT system:

+∞

X

k=0

x

^k

(2k + 1)! Z

^k

Db = Dq

^o

, (odd ltT )

q

^o

= [1

¹₂ ¹₂ ¹₂

· · · ]

^T

.

(10)

Ramanujan Toeplitz systems satisfied by Bernoulli numbers





 1

0 1

0 0 1

1

3

0 0 1

0

⁵₂

0 0 1

0 0 11 0 0 1

1

5

0 0

¹⁴³₄

0 0 1

0 4 0 0

²⁸⁶₃

0 0 1

0 0

²⁰⁴₅

0 0 221 0 0 1

1

7

0 0

¹⁹³⁸₇

0 0

³²³⁰₇

0 0 1

0

¹¹₂

0 0

⁷¹⁰⁶₅

0 0

³⁵⁵³₄

0 0 1

· · · · · · · · · · · ·











 B

2

B

4

B

6

B

8

B

10

B

12

B

14

B

16

B

18

B

20

B

22

· 





=







1 6

−

₃₀¹

1 421 45

−

₁₃₂¹

4 4551 120

−

₃₀₆¹

3 6651 231

−

₅₅₂¹

· 



 .

R(Z

^T

b) = Z

^T

f, f = [ f

0

1/6 − 1/30 1/42 1/45 . . .]

^T

[S. Ramanujan, Some properties of Bernoulli numbers, J. Indian

Math. Soc., 3 (1911), 219–234]

(11)

RΛ

⁻¹

= Λ

⁻¹

R, Λ = Z ˜

^T

DZ = diag x

ⁱ

(2i )! : i = 1, 2, 3, . . .

(C ) where R = ^˜

+∞

X

k=0

2x

^3k

(6k + 2)!(2k + 1) Z

^3k

=





 1

0 1

0 0 1

2x³

8!3

0 0 1

0

^2x_8!3³

0 0 1

0 0

^2x_8!3³

0 0 1

2x⁶

14!5

0 0

^2x_8!3³

0 0 1

0

_14!5^2x⁶

0 0

^2x_8!3³

0 0 1 0 0

_14!5^2x⁶

0 0

^2x_8!3³

0 0 1

2x⁹

20!7

0 0

_14!5^2x⁶

0 0

^2x_8!3³

0 0 1

0

_20!7^2x⁹

0 0

_14!5^2x⁶

0 0

^2x_8!3³

0 0 1

· · · · · · · · · · · ·







(12)

REMARK The 11 × 11 upper left submatrix of RΛ

⁻¹

coincides with the 11 × 11 upper left submatrix of Λ

⁻¹

R. ˜

Assuming that (C) is true, we have the equalities R(Z

^T

b) = RΛ

⁻¹

(ΛZ

^T

b) = Λ

⁻¹

R(Z ˜

^T

Db),

and thus the Ramanujan system R(Z

^T

b) = Z

^T

f is equivalent to the following ltT system

R(Z ˜

^T

Db) = Z

^T

Df (Ramanujan ltT ) where, in the coefficient matrix

R = ˜

+∞

X

k=0

2x

^3k

(6k + 2)!(2k + 1) Z

^3k

,

two null diagonals alternate the nonnull ones.

(13)

THEOREM Set b = [B

0

B

2

B

4

· · · ]

^T

, and D = diag

_{(2i )!}^xⁱ

: i = 0, 1, 2, . . . , x ∈ R. Then

L(a) (Db) = Dq, L(a) =

+∞

X

i =0

a

_i

Z

ⁱ

where a = (a

_i

)

^+∞_{i =0}

and q = (q

_i

)

^+∞_{i =0}

can assume the values:

a

₀^o

= q

^o₀

= 1, a

^o_i

= x

ⁱ

(2i + 1)! , q

_i^o

= 1

2 , i = 1, 2, 3, . . . , (o) a

^e_i

= 2x

ⁱ

(2i + 2)! , q

_i^e

= 1

2i + 1 , i = 0, 1, 2, 3, . . . , (e) a

^R_i

= δ

i ≡0

2x

ⁱ

(2i + 2)!(

²₃

i + 1) , q

_i^R

= 1

(2i + 1)(i + 1) (1−δ

i ≡2

3 2 ), i ≥ 0. (R)

In (R) the symbols i ≡ 2 and i ≡ 0 mean i ≡ 2 mod 3 and i ≡ 0 mod 3,

respectively.

(14)

COROLLARY

We have all coefficients of the (not Toeplitz) Ramanujan system RZ

^T

b = Z

^T

f, f = [f

₀

f

₁

f

₂

· · · ]

^T

:

R

_ij

=

(

_{(2i )!}

(2j )!

2

(2i −2j +2)!(²₃(i −j )+1)

i − j ≡ 0, i ≥ j

0 otherwise , i , j = 1, 2, . . . ,

f

_i

=

1 − δ

_{i ≡2} ³₂

− δ

_{i ≡0} 2¹ 3i +1

(2i + 1)(i + 1) , i = 1, 2, 3, . . . . Example: the 12

^th

Ramanujan equation:

506 5 B

6

+ 29716

5 B

12

+ 4807

3 B

18

+ B

24

= 8 2925 ⇒ B

24

= − 236364091

2730 .

(15)

Remarks on the parameter x :

For any choice of x , the coefficients a

_i

and (Dq)

_i

of the ltT systems stated in the Theorem converge to zero as i → +∞.

The rate of convergence of the a

_i^R

( (Dq

^R

)

i

) is greater than the rate of convergence of the a

^e_i

( (Dq

^e

)

_i

), which in turn is greater than the rate of convergence of the a

^o_i

( (Dq

^o

)

_i

).

Instead, the sequence |(Db)

i

| tends to zero, to 2, or to +∞, depending on the value of x .

For instance, the choice x = (2π)

²

would ensure the sequence (Db)

_i

= x

ⁱ

B

_2i

/(2i )! to be bounded; indeed in this case

|(Db)

_i

| → 2 if i → +∞, due to Euler formula.

(16)

Possible application in computing Bernoulli numbers

• The coefficients a

_i

, (Dq)

i

of the three ltT systems are easily computable, in fact

O(n) arithmetic operations for the first n diagonal entries of D:

D

00

= 1, D

ii

= x

ⁱ

(2i )! = x

2i (2i − 1) D

i −1i −1

, i = 1, 2, 3, . . . ; O(n) arithmetic operations to compute the first n entries of a

^o

, a

^e

, a

^R

, Dq

^o

, Dq

^e

, Dq

^R

:

a

^o_i

= 1

2i + 1 D

_ii

, (Dq

^o

)

₀

= 1, (Dq

^o

)

_i

= 1

2 D

_ii

, i > 0, a

^e_i

= 1

(i + 1)(2i + 1) D

_ii

, (Dq

^e

)

_i

= 1 2i + 1 D

_ii

, a

^R_i

= a

^e_i

1

2

3

i + 1 δ

_{i ≡0}

, (Dq

^R

)

_i

= a

^o_i

1 i + 1 (1 − δ

_{i ≡2}

3 2 ).

(17)

• A formula for the nth Bernoulli number:

B

2n−2

= (2n − 2)!

x

ⁿ⁻¹

{Dq}

^T_n

J{L(a)}

⁻¹_n

e

1

, J =





1 · 1





i.e. O(n log n) arithmetic operations to approximate B

_2n−2

in R.

A formula for any vector of n consecutive Bernoulli numbers:

{L(a)}

_N−n

O

{Toe(a)}

_n,N−n

{L(a)}

_n

{Db}

_up

{Db}

_down

:= {L(a)}

N

{Db}

_N

= {Dq}

_N

=:

{Dq}

_up

{Dq}

_down

, {Db}

_down

= {L(a)}

⁻¹_n

{Dq}

_down

− {Toe(a)}

_n,N−n

{Db}

_up

i.e. O(n log n) arithmetic operations to approximate

B

2N−2n

, . . . , B

2N−2

in R (if the vector {Toe(a)}

n,N−n

{Db}

_up

is

known).

(18)

Proof: It is well known that if A ∈ C

^n×n

is ltT and v ∈ C

ⁿ

, then O(n log n) a.o. are sufficient to compute z := Av. Thus

O(n log n) a.o. are sufficient to compute c : Ac = e

₁

(multiply on the left both members of Ac = e

1

by log n suitable sparser and sparser ltT matrices so to nullify the sub-diagonals of the coefficient matrix until obtaining c = A

⁻¹

e

₁

. NOTE: Product of ltT matrices is ltT) O(n log n) a.o. are sufficient to compute z : Az = v

(compute c : Ac = e

1

, call M the ltT matrix with c as first column, and compute z = Mv. NOTE: Inverse of ltT is ltT)

• Once a sufficiently accurate approximation B

_2j^∗

of B

2j

is

available, this approximation and the fact that the denominator of

B

_2j

is known (it is the product of all primes p such that p − 1

divide 2j ) allow to deduce the numerator of B

_2j

.

(19)

References

- S. Ramanujan, Some properties of Bernoulli numbers, J. Indian Math. Soc., 3 (1911), 219–234

- http://www.dima.unige.it/∼dibenede/2gg/home.html

“Due Giorni di Algebra Lineare Numerica 2012” (Genova, 16-17 Febbraio 2012) - http://www.mat.uniroma2.it/∼tvmsscho

http://www.mat.uniroma2.it/∼difiore/perGenova, genova, Bernoulli, RomeMoscow2014, N

Rome-Moscow schools “Matrix Methods and Applied Linear Algebra” 2012 and 2014, Di Fiore lectures

- C. Di Fiore, F. Tudisco, P. Zellini, Lower triangular Toeplitz-Ramanujan

systems whose solution yields the Bernoulli numbers, submitted for publication

- C. Di Fiore, P. Zellini, A matrix formulation of lower triangular Toeplitz

systems solvers, in preparation