Verified computations for hyperbolic 3-manifolds

Verified computations for hyperbolic 3-manifolds

Neil Hoffman (U. Melbourne) Kazuhiro Ichihara (Nihon U.) Masahide Kashiwagi (Waseda U.) Hidetoshi Masai (U. Tokyo) Shin’ichi Oishi (Waseda U.) Akitoshi Takayasu (Waseda U.) A Satellite Conference of Seoul ICM 2014

Knots and Low Dimensional Manifolds August 22, 2014. BEXCO, Busan, Korea

Classification of 3-manifolds

Every closed orientable 3-manifold is;

▶

Reducible

▶

Toroidal

▶

Seifert fibered

▶

Hyperbolic (

Riem.metric of curv. − 1).

as a consequence of the Geometrization Conjecture including famous Poincar´ e Conjecture (1904)

conjectured by Thurston (late ’70s)

established by Perelman (2002-03)

Question:

Classification of 3-manifolds

Every closed orientable 3-manifold is;

▶

Reducible

▶

Toroidal

▶

Seifert fibered

▶

Hyperbolic (

Riem.metric of curv. − 1).

as a consequence of the Geometrization Conjecture including famous Poincar´ e Conjecture (1904)

conjectured by Thurston (late ’70s) established by Perelman (2002-03) Question:

How to prove a given 3-manifold is really hyperbolic?

Thurston’s Idea

[W. Thurston]

∀ M : triangulated 3-manifold, possibly with torus boundary.

∃ equation s.t. whose solution (IF ANY) gives rise to a hyperbolic structure on M . (Gluing equation)

∏

j=1

(z

)

· (1 − z

)

=

∏

j=1

( − 1)

for m = 1, · · · , n + 2k + h and

∑n

j=1

arg((zj)^{(aj,m−cj,m)}) + arg((1−zj)^{(−bj,m+cj,m)}) =ϵm−

∑n

j=1

cj,m·πi.

Thurston’s Idea

[W. Thurston]

∀ M : triangulated 3-manifold, possibly with torus boundary.

∃ equation s.t. whose solution (IF ANY) gives rise to a hyperbolic structure on M . (Gluing equation)

∏

j=1

(z

)

· (1 − z

)

=

∏

j=1

( − 1)

for m = 1, · · · , n + 2k + h and

∑n

j=1

arg((zj)^{(aj,m−cj,m)}) + arg((1−zj)^{(−bj,m+cj,m)}) =ϵm−

∑n

j=1

cj,m·πi.

How to solve? ⇒ Use Computer!

Weeks’ Software

[J. Weeks] SnapPea:

a computer program to make/solve glueing equations.

[M. Culler - N. Dunfield] SnapPy: ”SnapPea on python”

SnapPea uses Newton’s method.

▶

floating point error?

▶

finitely many calculations can ensure convergece?

Newton’s iteration converges but...

Exact solution?

▶

In numerical computations, there are truncation errors when stopping an infinite series, e.g.

sin x ≈ x − x

3! + x

5! − x

7! + x

9! − x

11!

Influence of rounding error?

▶

It is well-known that a rounding error occurs in every floating-point operation.

1

10 ≈

Newton’s iteration converges but...

Exact solution?

▶

In numerical computations, there are truncation errors when stopping an infinite series, e.g.

sin x ≈ x − x

3! + x

5! − x

7! + x

9! − x

11!

Influence of rounding error?

▶

It is well-known that a rounding error occurs in every floating-point operation.

1

10 ≈

Moser’s Proposal

H. Moser,

Proving a manifold to be hyperbolic once it has been approximated to be so,

Algebraic & Geometric Topology, 9 (2009), 103–133.

The literature says that Kantorovich’s convergence theorem guarantees the convergence of Newton’s method. There is an exact solution in the neighborhood of an approximate solution.

Can you believe this computer-aided procedure?

(In particular, rounding error in floating-point operations.)

Moser’s Proposal

H. Moser,

Proving a manifold to be hyperbolic once it has been approximated to be so,

Algebraic & Geometric Topology, 9 (2009), 103–133.

The literature says that Kantorovich’s convergence theorem guarantees the convergence of Newton’s method. There is an exact solution in the neighborhood of an approximate solution.

Can you believe this computer-aided procedure?

(In particular, rounding error in floating-point operations.)

To prove the hyperbolicity (our approach)

Truncation error

Krawczyk’s test

Rounding error

Interval analysis

⇒ We develop a python module: HIKMOT.

Our package performs a rigorous numerical existence test for

solutions of gluing equations.

To prove the hyperbolicity (our approach)

Truncation error

Krawczyk’s test

Rounding error

Interval analysis

⇒ We develop a python module: HIKMOT.

Our package performs a rigorous numerical existence test for

solutions of gluing equations.

To prove the hyperbolicity (our approach)

Truncation error

Krawczyk’s test

Rounding error

Interval analysis

⇒ We develop a python module: HIKMOT.

Our package performs a rigorous numerical existence test for

solutions of gluing equations.

Interval analysis

Basic idea of interval analysis

A computer cannot deal with √

2 as an exact number, it can compute

1.41421356 ≈ √

2 ∈ [1.41421356, 1.41421357]

We write an interval

X := { x ∈ R : x ≤ x ≤ x, x, x ∈ R} = [x, x].

▶

IR : the set of such intervals.

Interval arithmetic

To calculate four basic operations ˜ ◦ ∈ { +, − , · , / } , the interval arithmetic can be executed by

X + Y = [

x + y, x + y ] X − Y = [

x − y, x − y ] X · Y = [

min { x · y, x · y, x · y, x · y } , max { x · y, x · y, x · y, x · y } ] X/Y = X ·

[ 1 y , 1

y ]

, (0 ̸∈ Y )

for X = [x, x] and Y = [y, y].

Krawczyk’s mapping

The gluing equation can be rewritten as Find x ∈ R

s.t. f (x) = 0,

where f : R

→ R

is a differentiable nonlinear real mapping. Set m = 2n.

Krawczyk’s mapping K : IR

→ IR

is defined by K (X) := c − Rf (c) + (I − Rf

(X))(X − c),

where I ∈ R

is a unit matrix, R ∈ R

a certain matrix to be an approximate inverse of f

(c) and c ∈ X is an

approximate solution of f(x) = 0.

Krawczyk’s mapping

The gluing equation can be rewritten as Find x ∈ R

s.t. f (x) = 0,

where f : R

→ R

is a differentiable nonlinear real mapping. Set m = 2n.

Krawczyk’s mapping K : IR

→ IR

is defined by K (X) := c − Rf (c) + (I − Rf

(X))(X − c),

where I ∈ R

is a unit matrix, R ∈ R

a certain matrix

to be an approximate inverse of f

(c) and c ∈ X is an

Theorem (Krawczyk’s test)

For a given interval X ∈ IR

, let int(X) be the interior of X.

If the condition

K(X) ⊂ int(X)

holds, then there uniquely exists an exact solution x

in X.

Furthermore, it is also shown that R and all matrices C ∈ f

(X) including f

(x

) are nonsingular.

R. Krawczyk, Newton-Algorithm zur Bestimmung von

Nullstellen mit Fehlerschranken, Computing 4(1969), 187–201.

Advantages of interval arithmetic

▶

Fast (especially compared to exact arithmetic)

▶

Uses less memory

▶

Overwrites the basic four operations (+, − , × , ÷ )

▶

Extends to functions naturally

▶

Accumulates numerical error by itself

Further techniques to implement

▶

Automatic differentiation

▶

Complex arithmetic

▶

Verified computations for arg(z) (atan2 function)

Advantages of interval arithmetic

▶

Fast (especially compared to exact arithmetic)

▶

Uses less memory

▶

Overwrites the basic four operations (+, − , × , ÷ )

▶

Extends to functions naturally

▶

Accumulates numerical error by itself

Further techniques to implement

▶

Automatic differentiation

▶

Complex arithmetic

▶

Verified computations for arg(z) (atan2 function)

HIKMOT

Hoffman, Ichihara, Kashiwagi, Masai, Oishi, & Takayasu, Verified computations for hyperbolic 3-manifolds,

submitted (arXiv:1310.3410), 2013.

The python module is available on

http://www.oishi.info.waseda.ac.jp/~takayasu/hikmot/

Thank you for kind attention!

HIKMOT

Hoffman, Ichihara, Kashiwagi, Masai, Oishi, & Takayasu, Verified computations for hyperbolic 3-manifolds,

submitted (arXiv:1310.3410), 2013.

The python module is available on

http://www.oishi.info.waseda.ac.jp/~takayasu/hikmot/

Thank you for kind attention!