Laurence Grammont
email: laurence.grammont@univ-st-etienne.fr

Hanane Kaboul
email: hanane.kaboul@univ-st-etienne.fr

An improvement of the product integration method for a weakly singular Hammerstein equation

Keywords: Nonlinear equations, Newton-like methods, Product integration method, Integral equations AMS Classification: 65J15, 45G10, 35P05

We present a new method to solve nonlinear Hammerstein equations with weakly singular kernels. The process to approximate the solution, followed usually, consists in adapting the discretization scheme from the linear case in order to obtain a nonlinear system in a finite dimensional space and solve it by any linearization method. In this paper, we propose to first linearize, via Newton method, the nonlinear operator equation and only then to discretize the obtained linear equations by the product integration method. We prove that the iterates, issued from our method, tends to the exact solution of the nonlinear Hammerstein equation when the number of Newton iterations tends to infinity, whatever the discretization parameter can be. This is not the case when the discretization is done first: in this case, the accuracy of the approximation is limited by the mesh size discretization. A Numerical example is given to confirm the theorical result.

Introduction

The general framework of this paper is the following. Let X be a complex Banach space and K : O ⊆ X → X a nonlinear Fréchet differentiable integral operator of the Hammerstein type defined on a nonempty open set O of X :

K(x)(s) := b a
H(s, t)L(s, t)F (t, x(t)) dt, for all x ∈ Ω, [START_REF] Ahues | Spectral Computations for Bounded Operators[END_REF] where H is the singular part of the kernel, L is the regular part of the kernel and F , the nonlinear part of the operator, is a real-valued function of two variables :

(t, u) ∈ [a, b]×R → F (t, u) ∈ R,
with enough regularity so that K is twice Fréchet-differentiable on O. The problem is a nonlinear Fredholm integral equation of the second kind:

Find ϕ ∈ O : ϕ -K(ϕ) = y, (2)
for a given function y ∈ X . Let T := K denote the Fréchet derivative of K, i.e., for all x ∈ O,

T (x)h(s) = b a H(s, t)L(s, t) ∂F ∂u (t, x(t))h(t) dt, h ∈ X , s ∈ [a, b]. (3)
In the following, X will be the space of the real valued continuous functions over a real interval [a, b], C 0 ([a, b], R), equiped with the supremum norm . .

If we consider a singular kernel such as H(s, t) := log(|s-t|) or |s-t| α , 0 < α < 1, an approximation based on standard numerical integrations is a poor idea. The main idea of the product integration method is introduced by Atkinson for linear integral equations ( [START_REF] Atkinson | Extensions of the Nyström Method for the Numerical Solution of Integral Equations of the Second Kind[END_REF], [START_REF] Atkinson | The Numerical Solution of Integral Equations of the Second Kind for nonlinear integral equation[END_REF] and [START_REF] Atkinson | The Numerical Solution of Integral Equations of the Second Kind[END_REF]) and is motivated by Young [START_REF] Young | The application of approximate product integration to the numerical solution of integral equations[END_REF]. The product integration method consists in performing a piecewise polynomial linear interpolation of the smooth part of the kernel times the function involving the unknown. This method is called product trapezoidal rule when the interpolation is linear. The solution of a second kind Fredholm integral equation with weakly singular kernel is typically nonsmooth near the boundary of the domain of integration. In order to obtain a high order of convergence, taking into account the singular behaviour of the exact solution, polynomial spline on graded mesh are developped (among other authors, Brunner, Pedas, Vainikko, Schneider [START_REF] Brunner | The piecewise polynomial collocation method for nonlinear weakly singular Volterra Equations[END_REF], [START_REF] Pedas | Superconvergence of piecewise polynomial collocations for nonlinear weakly singular integral equations[END_REF] and [START_REF] Schneider | Product integration for weakly singular integral equations[END_REF]). In [START_REF] Kaneko | Numerical solution for Weakly Singular Hammerstein Equations And Their Superconvergence[END_REF], Kaneko, Noren and Xu discuss a standard product integration method with a general piecewise polynomial interpolation for weakly singular Hammerstein equation and indicate its superconvergence properties. Under particular assumptions on the right hand side y, on the function F defining the nonlinearity and on the regularity of the exact solution of (2), they give an error estimation involving n the discretization paramater and the degree m of the piecewise polynomial interpolation. Hence the error depends on n and m.

In the 1950's, the major theme in the domain of theoretical numerical analysis was the developement of general frameworks in the domain of functional analysis to build and analyze numerical methods. A particular important contribution in this context is the paper of Kantorovich [START_REF] Kantorovich | Functional analysis and applied mathematics Uspehi Mat[END_REF] and later [START_REF] Kantorovich | Functional analysis in normed spaces[END_REF]. It proposes a generalization of Newton's method for solving nonlinear operator equations on Banach spaces. This idea is used everywhere when dealing with integral equations or partial differential equations. In [START_REF] Anselone | Collectively Compact Operator Approximation Theory and Application to Integral Equations[END_REF], chapter 6, Anselone studies the Newton method to approximate solutions of nonlinear equations P (x) = 0 where P is a nonlinear differentiable operator from a Banach space into itself. When dealing with the convergence of approximate solutions, these are defined as the solution of P n (x) = 0 where P n is an approximation of P . The Newton method is then applied to the functional equation P n (x) = 0. The philosophy of most of the papers dealing with the numerical approximation of nonlinear integral operator equation consists in defining an approximate operator P n to P and then apply Newton method ( [START_REF] Ansorge | Convergence of Discretizations of Nonlinear Problems. A General Approach[END_REF], [START_REF] Atkinson | Projection and iterated projection methods for nonlinear integral equations[END_REF], [START_REF] Atkinson | The discrete collocation method for nonlinear integral equation[END_REF], [START_REF] Atkinson | A Survey of Numerical Methods for Solving Nonlinear Integral Equation[END_REF], [START_REF] Brunner | The piecewise polynomial collocation method for nonlinear weakly singular Volterra Equations[END_REF], [START_REF] Dellwo | Accelerated projection and iterated projection methods with applications to nonlinear integral equations[END_REF], [START_REF] Grammont | Modified projection and the iterated modified projection methods for nonlinear integral equations[END_REF], [START_REF] Grammont | Modified projection method for Urysohn integral equations with non smooth kernels[END_REF], [START_REF] Kaneko | Numerical solution for Weakly Singular Hammerstein Equations And Their Superconvergence[END_REF], [START_REF] Krasnoselskii | Geometrical Methods of Nonlinear Analysis[END_REF], [START_REF] Krasnoselskii | Approximate Solution of Operator Equations[END_REF], [START_REF] Pedas | Superconvergence of piecewise polynomial collocations for nonlinear weakly singular integral equations[END_REF] and [START_REF] Vainikko | Galerkin's perturbation method and general theory of approximate methods for nonlinear equations[END_REF]).

We propose to apply Newton's method directly to the operator equation P (x) = 0 and then to discretize the linear operator equations, issued from the Newton's iterations, by a product integration method. We will prove that the approximate iterates tend to the exact solution of the operator equation as the number of iterations tends to infinity. The important fact is that the convergence holds whatever the discretization parameter, defining the size of the linear system to be solved, can be. As we do not need the solution of each Newton iteration to be particularly accurate, we chose to apply the classical trapezoidal product integration method.

Section 2 is devoted to the description of our method (linearization via Newton's method followed by discretization by the product integration method). In Section 3, the convergence result is proved. In the last section, the classical method (discretization followed by linearization) is recalled and we compare it with our method through a numerical example.

Description of the new method

To solve the problem (2) for a given function y in C 0 ([a, b], R), we propose to first apply the Newton method to the equation ϕ -K(ϕ) = y. It leads to the sequence (ϕ (k) ) k≥0 ∈ O:

(4) ϕ (0) ∈ O, (I -T (ϕ (k) ))(ϕ (k+1) -ϕ (k) ) = -ϕ (k) + K(ϕ (k) ) + y, k ≥ 0.
Then we discretize this equation with the product integration method associated to the piecewise linear interpolation. Let ∆ n , defined by

(5) a =: t n,0 < t n,1 < • • • < t n,n := b, be the uniform grid of [a, b] with mesh h n := b -a n .
Setting

f x (t) := ∂F ∂u (t, x(t)), [L(s, t)f x (t)h(t)] n denotes the piecewise linear interpolation of L(s, t)f x (t)h(t) : ∀s ∈ [a, b], ∀i = 1, . . . , n: [L(s, t)f x (t)h(t)] n := 1 h n (t n,i -t)L(s, t n,i-1 )f x (t n,i-1 )h(t n,i-1 ) + 1 h n (t -t n,i-1 )L(s, t n,i )f x (t n,i ))h(t n,i ) for t ∈ [t n,i-1 , t n,i ].
We define the approximate operator T n by

T n (x)(h)(s) := b a H(s, t)[L(s, t)f x (t)h(t)] n dt, x ∈ O, h ∈ X , s ∈ [a, b]. (6)
Then the approximate problem is:

Find ϕ (k+1) n ∈ X : (I -T n (ϕ (k) n ))(ϕ (k+1) n -ϕ (k) n ) = -ϕ (k) n + K(ϕ (k) n ) + y. (7)
We have

T n (x)(h)(s) := n j=0 w n,j (s)L(s, t n,j )f x (t n,j )h(t n,j ), w n,0 (s) := 1 h n t n,1 t n,0 H(s, t)(t n,1 -t)dt, w n,n (s) := 1 h n tn,n t n,n-1 H(s, t)(t -t n,n-1 )dt,
and for 1 ≤ j ≤ n -1,

w n,j (s) := 1 h n t n,j t n,j-1 H(s, t)(t -t n,j-1 )dt + 1 h n t n,j+1
t n,j H(s, t)(t n,j+1 -t)dt.

Hence [START_REF] Atkinson | Extensions of the Nyström Method for the Numerical Solution of Integral Equations of the Second Kind[END_REF] can be rewritten as

ϕ (k+1) n (s) - n j=0 w n,j (s)L(s, t n,j )f k (t n,j )ϕ (k+1) n (t n,j ) (8) = K(ϕ (k) n )(s) + y(s) - n j=0 w n,j (s)L(s, t n,j )f k (t n,j )ϕ (k) n (t n,j ), (9)
where

f k (t n,j ) := ∂F ∂u (t n,j , ϕ (k) n (t n,j )). Setting x (k+1) n (j) := ϕ (k+1) n (t n,j ),
From the evaluations of equation ( 26) at the nodes of the grid, it is straightforward that the vector x (k+1) n is the solution of the linear system [START_REF] Atkinson | Projection and iterated projection methods for nonlinear integral equations[END_REF] (I -

A (k) n )x (k+1) n = b (k) n ,
where

A (k) n (i, j) := w n,j (t n,i )L(t n,i , t n,j )f k (t n,j ), b (k) n := K(ϕ (k) n )(t n,i ) + y(t n,i ) -A (k) n x (k) n . ϕ (k+1) n
is recovered from equation ( 26) :

ϕ (k+1) n (s) = n j=1 w n,j (s)L(s, t n,j )f k (t n,j ) x (k+1) n (t n,j ) -x (k) n (t n,j ) + K(ϕ (k) n )(s) + y(s).

Convergence property of the new method

Existence, uniqueness and regularity properties of the solution of equation ( 2) have been already considered (for example by Kaneko, Noren and Xu [START_REF] Kaneko | Regularity of the Solution of Hammerstein Equations With Weakly Singular Kernel[END_REF] or Pedas and Vainikko [START_REF] Pedas | The smoothness of solutions to nonlinear weakly singular integral equations[END_REF]). In this section, we are only interested by the proof of the convergence of ϕ

(H3) ϕ ∈ O is an isolated solution of ϕ -K(ϕ) = f . (H4) I -T (ϕ) is invertible.
These assumptions ensure that equations (2),( 7) and [START_REF] Schneider | Product integration for weakly singular integral equations[END_REF] for n large enough, are uniquely solvable (see [START_REF] Atkinson | The Numerical Solution of Integral Equations of the Second Kind[END_REF]).

M 2 (a) := sup t∈[a,b],|u|≤a+ ϕ | ∂ 2 F ∂u 2 (t, u)|.
The proof of convergence relies on the successive approximations convergence result (see [START_REF] Krasnoselskii | Approximate Solution of Operator Equations[END_REF] Theorem 2.3. pp 21). Let us recall this result (in a form slicely different from [START_REF] Krasnoselskii | Approximate Solution of Operator Equations[END_REF]).

Proposition 1 Consider a nonlinear operator A from a Banach space X into itself, defined on an open set V. Let x * ∈ V be a fixed point of A. Let the operator A be Fréchet differentiable at the point x * . Let us assume that the following condition is fulfilled

(11) ρ 0 := ρ(A (x * )) < 1,
where ρ denotes the spectral radius and A denotes the Fréchet derivative of A.

Then, for all ε > 0 such that ρ 0 +ε < 1, there exist r ε > 0 and r ε > 0 such that B(x * , r ε ) ⊂ V and B(x * , r ε ) ⊂ V and such that for x (0) in B(x * , r ε ), the successive approximations x (k) defined by

x (k+1) = A(x (k) ), k ∈ N,
remain in B(x * , r ε ) for all k ∈ N, and the sequence (x (k) ) k≥0 converges to x * . Moreover,

x (k) -x * ≤ r ε (ρ 0 + ε) k .
The following four lemmas are needed to prove our main result.

Lemma 1 For all a > 0 such that B(ϕ, a) ⊂ O, for all x ∈ B(ϕ, a), Proof : From the mean value theorem applied to ∂F ∂u , for all t, there exist a real number c(t) between ϕ(t) and x(t) such that

T (x) -T (ϕ) ≤ c H c L M 2 (a) x -ϕ , (12)
∂F ∂u (t, x(t)) - ∂F ∂u (t, ϕ(t)) = ∂ 2 F ∂u 2 (t, c(t))(x(t) -ϕ(t)). As ∀t ∈ [a, b], |c(t)| ≤ r + ϕ , T (x) -T (ϕ) ≤ x -ϕ sup s∈[a,b] b a |H(s, t)||L(s, t)|| ∂ 2 F ∂u 2 (t, c(t))|dt (13) ≤ c H c L M 2 (a) x -ϕ . (14)
Hence ( 13) is deduced. Now a is fixed such that B(ϕ, a) ⊂ O.

Lemma 2 There is a positive number r < a such that for all x ∈ B(ϕ, r), I -T (x) is invertible and

(I -T (x)) -1 ≤ 2µ, ( 15
)
where µ := (I -T (ϕ)) -1 . Moreover, for all x ∈ B(ϕ, r), for n large enough, I -T n (x) is invertible and there exists a constant c x > 0, independent of n, such that

(I -T n (x)) -1 ≤ c x . ( 16
)
Proof : Let 0 < r < a be such that r ≤ 1 2µc H c L M 2 (a)
.

For all x ∈ B(ϕ, r),

I -T (x) = I -T (ϕ) + T (ϕ) -T (x) = (I -T (ϕ))[I + (I -T (ϕ)) -1 (T (ϕ) -T (x))]. Since (I -T (ϕ)) -1 (T (ϕ) -T (x)) ≤ µ T (ϕ) -T (x) ≤ µc H c L M 2 (a)r ≤ 1 2 ,
we conclude that I -T (x) is invertible and that its inverse is uniformly bounded on B(ϕ, r). In fact (I -T (x))

-1 = I + (I -T (ϕ)) -1 (T (ϕ) -T (x)) -1 (I -T (ϕ)) -1 , so (I -T (x)) -1 ≤ µ ∞ k=0 (I -T (ϕ)) -1 (T (ϕ) -T (x)) k ≤ 2µ. The function (s, t) → L(s, t) ∂F ∂u (t, x(t)) is in C 0 ([a, b] × [a, b], R).
Hence, according to [START_REF] Atkinson | The Numerical Solution of Integral Equations of the Second Kind[END_REF] or [START_REF] Anselone | Collectively Compact Operator Approximation Theory and Application to Integral Equations[END_REF],

T n (x) p -→ T (x), where p -→ denotes the pointwise convergence, and the sequence (T n (x)) n≥0 is collectively compact.

For all x ∈ B(ϕ, r), T n (x) is a collectively compact approximation of T (x) (see [START_REF] Anselone | Collectively Compact Operator Approximation Theory and Application to Integral Equations[END_REF]). Hence for n large enough, I -T n (x) is invertible and (I -T n (x)) -1 is uniformly bounded in n. This means that there is a constant c x such that for n large enough,

(I -T n (x)) -1 ≤ c x .
This ends the proof.

Let A n be the operator defined on B(ϕ, r) by

A n (x) := x + S n (x) (K(x) + y -x) , (17)
where

S n (x) := (I -T n (x)) -1 . (18)
Notice that we have

A n (ϕ) = ϕ. ( 19
)
Lemma 3 The operator S n is Fréchet differentiable at ϕ.

Proof : As for all h ∈ X , T n (x)(h)(s) = n j=0
w n,j (s)L(s, t n,j ) ∂F ∂u (t n,j , x(t n,j ))h(t n,j ), the operator

x → T n (x) is differentiable at ϕ, and we have for all h ∈ X and δ ∈ X ,

T n (x)(δ, h)(s) = n j=0 w n,j (s)L(s, t n,j ) ∂ 2 F ∂u 2 (t n,j , x(t n,j ))δ(t n,j )h(t n,j ).
As, at the first order, (

L + E) -1 -(L) -1 -(L) -1 E(L) -1 , we have S n (ϕ + δ) -S n (ϕ) = (I -T n + δ)) -1 -(I -T n (ϕ)) -1 = (I -T n (ϕ) -T n (ϕ)δ + O(δ 2 ))) -1 -(I -T n (ϕ)) -1
S n (ϕ)T n (ϕ)δS n (ϕ), so that S n is Fréchet differentiable at ϕ and

S n (ϕ)δ = S n (ϕ)T n (ϕ)δS n (ϕ).

Lemma 4

The operator A n is Fréchet differentiable at ϕ. For n large enough,

ρ(A n (ϕ)) < 1. ( 20
) Proof : Notice that A n (ϕ) = ϕ, hence A n (ϕ + h) -A n (ϕ) = ϕ + h + S n (ϕ + h) (K(ϕ + h) + y -ϕ -h) -ϕ = h + S n (ϕ + h) K(ϕ) + T (ϕ)h + O(h 2 ) + y -ϕ -h = h + S n (ϕ + h) (T (ϕ) -I)h + O(h 2 ) , hence A n is differentiable at ϕ and A n (ϕ) = I -S n (ϕ)(I -T (ϕ)). ( 21
)
We have

ρ (I -S n (ϕ)(I -T (ϕ))) = inf n (I -S n (ϕ)(I -T (ϕ))) n 1 n (22) ≤ (I -S n (ϕ)(I -T (ϕ))) 2 1 2 . (23) Since (I -S n (ϕ)(I -T (ϕ))) = S n (ϕ) (T (ϕ) -T n (ϕ)), (I -S n (ϕ)(I -T (ϕ))) 2 = S n (ϕ) (T (ϕ) -T n (ϕ)) S n (ϕ) (T (ϕ) -T n (ϕ)) ≤ S n (ϕ) (T (ϕ) -T n (ϕ)) S n (ϕ) (T (ϕ) -T n (ϕ)) ≤ c ϕ (T (ϕ) -T n (ϕ)) S n (ϕ) (T (ϕ) -T n (ϕ)) .
As S n (ϕ) is uniformly bounded (see Lemma 2) and (T (ϕ) -T n (ϕ)) is collectively compact, the closure of the set

S := ∪ n {S n (ϕ)(T (ϕ) -T n (ϕ))x, x ≤ 1} is compact so that (I -S n (ϕ)(I -T (ϕ)) 2 ≤ c ϕ sup x∈S (T (ϕ) -T n (ϕ)) x -→ n→∞ 0. Then ρ(A n (ϕ)) -→ n→∞ 0.
This ends the proof.

Theorem 1 Under assumptions (H0) to (H4), there exists r > 0 such that, for a fixed n large enough to have

ρ n := ρ A n (ϕ) < 1,
and for any ε > 0 such that ρ n +ε < 1, there exist B(ϕ, r n,ε ) ⊂ B(ϕ, r) and B(ϕ, r n,ε ) ⊂ B(ϕ, r)

such that, if ϕ (0)
n ∈ B(ϕ, r n,ε ), then the sequence (ϕ

(k) n ) k≥0 solution of (I -T n (ϕ (k) n ))(ϕ (k+1) n -ϕ (k) n ) = -ϕ (k) n + K(ϕ (k) n ) + f,
is defined, belongs to B(ϕ, r n,ε ) and

ϕ (k) n -→ k→∞ ϕ.
Moreover, the following estimation holds:

(24) ϕ (k) n -ϕ ≤ r n,ε (ρ n + ε) k .
Proof : The exact solution ϕ of the nonlinear problem (2) is a fixed point of A n (see [START_REF] Kaneko | Numerical solution for Weakly Singular Hammerstein Equations And Their Superconvergence[END_REF]). From Lemma 4, A n is Fréchet differentiable at ϕ and for n large enough ρ(A n (ϕ)) < 1. The conditions needed to apply Proposition 1 to the operator A n are satisfied so that Proposition 1 gives the result.

4 Numerical evidence

The classical product integration method

Let us recall the classical product integration method applied to nonlinear operators (see [START_REF] Kaneko | Numerical solution for Weakly Singular Hammerstein Equations And Their Superconvergence[END_REF]). The classical product integration approximation ψ n solves the nonlinear equation

ψ n (s) - b a H(s, t)[L(s, t)F (t, ψ n (t))] n dt = y(s),
where

Set

Y n (i) := y(t n,i ),

A n (i, j) := = w n,j (t n,i )L(t n,i , t n,j ),

X n :=    ψ n (t n,0 ) . . . ψ n (t n,n )    , F(X n ) :=    F (t n,0 , ψ n (t n,0 )) . . . F (t n,n , ψ n (t n,n ))    .
Evaluating the equation ( 25) at the nodes t n,i , i = 0, . . . , n, the following non linear system is obtained:

(26) X n -A n F(X n ) = Y n ,
which we can solve by the classical finite dimensional Newton method ( [START_REF] Argyros | Convergence and Applications of Newton-type Iterations[END_REF] and [START_REF] Argyros | Some methods for finding errors bounds for Newton-like methods under mild differentiability conditions[END_REF]). Notice that the Newton's iterates tends to ψ n when k → ∞ and not to ϕ, the exact solution. It means that the accuracy of the approximate solution is limited by n.

The classical discretization-linearization method can not be accurate if it is performed on a coarse grid (n = 50). We obtain the approximate solution ψ n of ϕ and the error is constant with the number of iterations. On the other hand, our linearization-discretization method approaches the exact solution ϕ even if the discretization is done with a coarse grid. It confirms the theoretical result. When n increases, the number of Newton's iterations needed to reach a fixed accuracy decreases. It can be useful to apply higher order product integration methods (see the idea of Diogo, Franco and Lima in [START_REF] Diogo | High Order Product Integration Method for a Volterra Integral Equation with Logarithmic singular Kernel[END_REF]), instead of the product trapezoidal rule, to reduce the number of Newton's iterations and therefore the computational cost of the method. An high order product integration approximation, adapted to a Fredholm equation, can also be a good starting point for the Newton's iterations of our method.

n

  towards ϕ when k → ∞. Hypotheses: (H0) F , defined in (1), is twice continuously differentiable on [a, b] × R. (H1) L ∈ C 0 ([a, b] × [a, b], R). (H2) H verifies: (H2.1) c H := sup s∈[a,b] b a |H(s, t)|dt < +∞. (H2.2) lim h→0 ω H (h) = 0, where ω H (h) := sup |s-τ |≤h, s,τ ∈[a,b] b a |H(s, t) -H(τ, t)|dt.

  Let a > 0 such that B(ϕ, a) ⊂ O, where B(ϕ, a) denotes the open ball in C 0 ([a, b], R) centered in ϕ and of radius a. As ϕ ∈⊂ C 0 ([a, b], R), ϕ is bounded. As F is twice continuously differentiable, the following constant exists:

  where c L := max s,t∈[a,b]|L(s, t)|.

Figure 2 :

 2 Figure 2: errors of the linearization-discretization method for increasing values of n

  [L(s, t)F (t, ψ n (t))] n denotes the piecewise linear interpolant of t → L(s, t)F (t, ψ n (t)).

	Using the uniform grid ∆ n , we obtain
	(25)		ψ n (s) -
	where
	w n,0 (s) :=	1 h n	t n,1 t n,0	H(s, t)(t n,1 -t)dt,
	w n,j (s) :=	1 h n	t n,j t n,j-1	H(s, t)(t -t n,j-1 )dt +	1 h n	t n,j+1 t n,j
	w n,n (s) :=	1 h n	tn,n t n,n-1

n j=0 w n,j (s)L(s, t n,j )F (t n,j , ψ n (t n,j )) = y(s), H(s, t)(t n,j+1 -t)dt, j = 1, . . . , n -1,

H(s, t)(t -t n,n-1 )dt.

Acknowledgements

The first author is partially supported by the Indo-French Centre for Applied Mathematics (IFCAM).

Numerical Illustration

Numerical experiments are now carried out to illustrate the accuracy of our method. Let us consider in X := C 0 ([0, 1], R), the operator

with the real valued kernel function κ :

Implementation remark : To solve the linear system at each Newton iteration, the integral b a log(|s -t|) sin(ϕ (k) n (t))dt needs to be evaluated. To evaluate it, we use the singularity subtraction technique ([3] and also [START_REF] Ahues | Spectral Computations for Bounded Operators[END_REF]).

In the following, our method is called the linearization-discretization method and the classical one is called the discretization-linearization method. We compare them.


Edward G Belaga
email: belaga@math.u-strasbg.fr

Cobordism as a Basic Topological Paradigm of Virtual Computer Animation

Keywords: Shape Deformation -Cobordism -Virtual, or Implicit, Animation -Manifold -Isomorphism -Isotopy -Immersion -Homotopy

We customize here, for the purposes of precomputed and interactive deformation and animation techniques, some basic concepts and deformation methods of differential topology related to Cobordism Theory.

Introduction

This paper is a part of our programme [START_REF] Belaga | Computer Animation Strategies and Basic Topological Paradigms[END_REF][START_REF] Belaga | Plot-and-Patterning Theory in Computer Graphics and Computer Animation[END_REF][START_REF] Belaga | Topology-Sensitive Computer Animation Scenarios : Cobordisms and Resolution of Singularities[END_REF] to bridge the gap between, on the one hand, computer animation heuristics (such as the popular 2D deformation morphing, or the less known space-time deformation method) and, on the other hand, computer visualization artifacts built around strict mathematical methods and theorems (such as sphere eversions [START_REF] Maxwell | Symmetry and Insight : The Saga of Sphere Eversions[END_REF], or 3D and 4D immersions of Klein bottle [START_REF] Hanson | Interactive Methods for Visualizable Geometry[END_REF]). The purpose of the present paper is triple.

First, and foremost, it attempts to customize, for the needs of Computer Animation, some methods of differential topology related to Cobordism Theory. Cobordism, interpreted here as deformation, is a more powerful and versatile tool than any other type of topological deformation acquired up to date in Computer Graphics. Its main, and novel, feature is its shapewise character, in contradistinction to known pointwise deformations which trace the deformation of a shape by tracing the destination of every one of its individual points. The ensuing broadening of the visualization panorama leads to the concept of virtual, or implicit animation, as an intrinsically defined deformation which, to become "real"animation, needs to be subsequently visualized on a "screen", by its sinking into a visualizable ambient space.

Second, and in the opposite direction, the paper intends to make manifest deep mathematical intuitions hidden, all unknowingly even to their inventors, behind the facade of some animation heuristics, -with the subsequent goal to either shore up these heuristics with new rigorous technical means, or even to completely incorporate them, on the theoretical level, into a corresponding mathematical framework.

Finally, our third goal is to expose some mathematical problems arising from attempts to interpret, explain, and rigorously justify needs of, and related experimental phenomena observed in, Computer Animation.

Cobordism as a Deformation

Figure 1 demonstrates that two isomorphic objects (cf. the sign ≈ between two adjacent shapes) could create quite different, if not outright opposite, visual impressions. Hence, one of the primary concerns of Topology is the problem of recognizing when shapes ( in topological parlance, manifolds) "looking"differently are really different or, in fact, are "the same", or equivalent. To this end, a whole gamut of equivalence notions has been created, from isomorphic (diffeomorphic or homeomorphic) to cobordant to homotopic, together with corresponding sets of tools for deciding when two manifolds are homeomorphic, diffeomorphic, cobordant, etc. [START_REF] Hirsch | Differential Topology[END_REF]. Some of these equivalence notions are explicitly defined deformations (homeotopies, isotopies, immersions) well-known in Computer Visualization [START_REF] Hanson | Interactive Methods for Visualizable Geometry[END_REF]. Not so with cobordism which, by definition, is a manifold with two "brims"(see Figure 2 (Left) and §3), not a deformation.

However, any cobordism can be interpreted as an implicit deformation, since it can be always supplied by a suitable Morse function [START_REF] Hirsch | Differential Topology[END_REF] which cuts it into "slices"(cf. Figure 2 (Left)), in such a way that :

(i) the two outermost slices are the brims themselves;

(ii) the Morse function interpreted as time, the cobordism becomes a reversible deformation (i. e., a 1D-dimensional collection of slices) of one of its brims into the second one.

Cobordism surpasses in its versatility other types of topological deformations. Thus, for example, a circle is cobordant, but neither isotopic, nor homotopic to two disjoint circles : cf. Figure 2 (Left). In this case, the deformation transforms the circle into the The versatility of cobordism as deformation is a by-product of its another attractive and important quality. By contrast with other known topological deformations which could be described as pointwise, cobordism is a shapewise, or pointless, deformation which does not trace the trajectories of individual points of shapes : see for details § §3, 7.

Finally, in the most important for Computer Graphics interval of dimensions, 1 ≤ dim ≤ 4, the cobordism deformation technique has the advantage of theoretical predictability : given two manifolds of the same dimension, M 0 and M 1 , one can, at least theoretically, decide whether there exists a cobordism deforming M 0 into M 1 . An efficient construction of such a cobordism is another matter : see for details § §5, 7.

We work here with only smooth cobordisms which generate deformations without, or with only a finite number of isolated non-degenerated singularities. This restriction is important : folding and shrinking (Figure 2 (Right) : a circle is homotopic but neither isotopic, nor cobordant to a point) are, for example, out of reach for smooth cobordisms. And so are all deformations producing shapes with singular curves, as in the case of Figure 3, where a torus detaches itself from a plane through a circle (see for details §6).

Cobordisms with singularities [START_REF] Yu | On Thom Spectra, Orientability, and Cobordism[END_REF], which are the subject of our forthcoming paper [START_REF] Belaga | Topology-Sensitive Computer Animation Scenarios : Cobordisms and Resolution of Singularities[END_REF], are powerful enough to imitate deformations with isolated singular sub-manifolds (see for details § §6, 7). Still, even such cobordisms cannot be held accountable for all "meaningful"piecewise-smooth deformations emerging in Computer Animation.

The truth is, a "realistic"animation scenario might involve such complicated selfintersections, foldings, and other "wild"singularities, that it becomes impossible to formally and exhaustively treat it with any available to date topological methods, cobordisms included (see for details §7).

Theory of Cobordisms without Singularities at Glance : Basic Definitions

To be more (topologically) specific, manifold X will mean throughout the paper a compact, smooth, orientable or non-orientable n-dimensional (nD, for short; n ≥ 1) manifold, with boundaries, ∂X = Y = ∅, dimY = dimX -1, or without boundaries (closed manifold), ∂X = ∅.

Thus, the left (respectively, right) brim of the cobordism of Figure 2 (Left) is a compact, smooth, closed orientable 1D manifold with one (respectively, two) component(s). Smoothness of a manifold is permitted to be disrupted by a finite number of isolated non-degenerate singularities.

Two smooth closed manifolds

M 0 = M n 0 , M 1 = M n 1 of the same dimension n are cobordant, if their disjoint union is diffeomorphic to the boundary of a compact smooth manifold M = M n+1 , called cobordism : M 0 ∪ M 1 ∼ = ∂M.
If M 0 , M 1 are cobordant, then there exists on M a Morse function f , such that

f : M → [0, 1], f (M 0 ) = 0, f (M 1 ) = 1.
Since (by definition of Morse function) f has neither degenerate singularities, nor critical multiple values, all "slices"

M t = f -1 (t), 0 ≤ t ≤ 1,
of the manifold M are smooth (sub-)manifolds, with the possible exception of a finite number of slices M t k with a single non-degenerate singularity corresponding to a critical value t, 0 < t 1 < ... < t r < 1.

Defintion : Cobordism as a Shapewise, or Implicit, Deformation.

(1) We interpret the one-parameter family

{M t , 0 ≤ t ≤ 1}
as a shapewise (or pointless) deformation of M 0 into M 1 which does not, and has no standard intrinsic means to, trace the trajectories of individual points of shapes.

(2) Compare this deformation to pointwise deformation of, say, isotopy [START_REF] Hirsch | Differential Topology[END_REF]. A shapewise deformation achieves the similarity of neighbouring shapes M t and M t+ not because of the proximity in M t+ of images of proximate points in M t , but because of the proximity of two shapes in the ambient manifold M of the cobordism.

Virtual, or Implicit, Animation Paradigm

Traditionally, a computer animation scenario is understood as a continuous, temporally arranged collection of deformations of a (typically, but not necessary, 2D) shape "floating"in an ambient (typically, 3D) space. In the light of the cobordism deformation techniques, this vision lends itself to the following far reaching generalization :

Virtual, or Implicit, Animation Paradigm : Pulling a Source into a Target along a Deformation Scene.

(1) The topological formalism and problem. Given two intrinsically or extrinsically defined manifolds S and T (called source and target), and a manifold M , (called deformation scene), with two sub-manifolds S r , T r ⊂ M (called source and target receivers), find (i) immersions g : S =⇒ S r ; h : T T r ;

(ii) and a deformation deform, carrying (or, if one prefers, pulling) the embedded source S = g(S) ⊆ S r into the embedded target T = h(T ) ⊆ T r through (respectively, along) M .

A cobordism-related solution of this problem in low (one to four ) dimensions is discussed in §5. See below Claim : Virtual Animations are Cobordisms.

(2) Visually explicit deformations. The collection B of all shapes created by deform on its way from S to T , these two shapes including, is called deformation body. The deformation is visually explicit if the source, target, and deformation scene are defined as manifolds in an ambient "screen"space R n . An heuristically created sample of a visually explicit deformation [START_REF] Bechmann | Animation by Deformation of Space-Time Objects[END_REF] is discussed below, §6.

(3) The visualization stage of the paradigm. Suppose the mathematical part of the problem has been successfully resolved. If the constructed deformation is not visually explicit, one needs to meaningfully visualize S, T , M , S r , T r , g, h, deform, B, by sinking them into an ambient "screen"space, with the whole gamut of options, from pure theoretical observations to computer implementation.

Claim : Virtual Animations are Cobordisms. Any virtual animation carrying a shape S into a shape T , can be viewed as a cobordism supplied with a Morse function induced by the animation. And vice versa, a pair (cobordism, Morse function), with the brims of the cobordism "cut off", respectively, by the values 0 and 1 of the Morse function, gives rise to a virtual animation carrying the shape of the 0-brim into the shape of the 1-brim.

Theory of Cobordisms without Singularities at Glance : Problem of Cobordants

In the formal framework of Cobordism Theory, realization of the above Virtual Animation Paradigm becomes Problem of Cobordants. Given two shapes (compact, smooth, closed manifolds) M 0 and M 1 , determine whether they are cobordant. If the answer is positive, find the cobordism, its Morse function, and the corresponding shapewise deformation.

If dim(M 0 ) = dim(M 1 ) ≥ 5, no general answer to the problem is known, apart from a beautiful reduction of this "differentiable"problem to the open combinatorial problem of computing homotopy groups of the manifold [START_REF] Hirsch | Differential Topology[END_REF], [START_REF] Novikov | Topology I: General Survey[END_REF].

Fortunately for us, visualizing mostly one-to four-dimensional shapes [START_REF] Banchoff | Beyond the Third Dimension : Geometry, Computer Graphics, and Higher Dimensions[END_REF], the solution of the problem of cobordants in the dimensions below 5 is at a much more advanced stage.

Problem of Cobordants in Low Dimensions. dim = 1. 1D manifolds without boundaries are finite collections of disjoint circles, the number of circles (components of the manifold) being the only and full characteristics (or invariant) of a 1D manifold [START_REF] Hirsch | Differential Topology[END_REF]. Why two different 1D manifolds are cobordant, and how to build their cobordism, with an associated Morse function, can be easily surmised from Figure 2 (Left), where a circle is demonstrated to be cobordant to two circles. dim = 2. A compact, smooth, closed surface is either orientable, -and then diffeoporphic to the sphere S 2 with a finite number of handles, or non-orientable, -and then diffeomorphic to the projective plane RP 2 with a finite number of handles [START_REF] Hirsch | Differential Topology[END_REF]. It is not difficult to see, extending the device of Figure 2 (Left) to the two-dimensional case, why any two orientable (respectively, non-orientable) surfaces are cobordant, and how to effectively build a cobordism and an associated Morse function which attaches (or, in the opposite direction, removes) a new handle. On the other hand, RP 2 is not cobordant to S 2 , and any deformation of RP 2 into S 2 , and vice versa, necessarily passes by a stage with a "wild"singularity. dim = 3. Using complicated and tricky geometry, Vladimir Rokhlin has proved in 1951 that any two 3D compact, smooth, closed manifolds are cobordant [START_REF] Hirsch | Differential Topology[END_REF], [START_REF] Rokhlin | A Three-Dimensional Manifold Is the Boundary of a Four-Dimensional One (Russian)[END_REF]. The problem of effective procedure for this and the following, dim = 4, existence theorem is discussed below, §7. dim = 4. Orientable case (Rokhlin, 1952 [8], [START_REF] Rokhlin | New Results in the Theory of Four-Dimensional Manifolds (Russian)[END_REF]). There exists an infinite series of 4D compact, smooth, closed, orientable manifolds without boundaries which are mutually not cobordant [START_REF] Kirby | The Topology of 4-Manifolds[END_REF], with any other 4D manifold of this type being cobordant to some manifold from the series.

Space-Time Deformations and Cobordisms

Two known heuristic deformation techniques,morphing and space-time deformation method), incorporate, unknowingly to their inventors, some features of the above deformation scheme. We illustrate here, on the example of the space-time deformation method, or ST DM [START_REF] Bechmann | Animation by Deformation of Space-Time Objects[END_REF], why and how these popular heuristic animation models might benefit from an "infusion"of cobordisms-related methods.

The central idea of ST DM is to see as the principal object of study and manipulation not a shape by itself but its image in the space-time or, in our terminology, §4, its deformation body. Take first the space-time image of a motionless shape M sinked into an ambient space R n , n = dim(M ) + 2. This image is the cylinder M × I, with I being the time interval, I = [0, 1]. Start to deform M × I in R n , in one or another acceptable way. The time cross-sections of the deformed cylinder generate a continuous transformation of M .

One immediately recognizes in the ST DM strategy some formal components of the above definitions of cobordism, §3, and virtual animation, §4. Since ST DM does not care about singularities (cf. the "flying"torus of Figure 3), its adequate interpretation would need cobordisms with singularities.

Figure 3. A ST DM deformation with a singular circle; the picture is borrowed from [START_REF] Bechmann | Animation by Deformation of Space-Time Objects[END_REF].

On the other hand, from a theoretical point of view, ST DM , being a particular case of what is called above visually explicit deformation is considerably weaker than the cobordism deformation method. As a result, ST DM lacks theoretical predictability of cobordism deformations, § §3, 7. The last drawback is typical for other heuristic techniques as well. It considerably restricts the purposefulness of the search for new non-trivial artifacts : in many interesting cases, such artifacts are "stumbled upon"almost accidentally.

Open Mathematical Tool-Box

In this section, we list open problems suggested by the above exposition of the cobordism deformation method.

Problem 1. (Cf. the remark at the end of §2.) Is there a more general than cobordism topological concept of deformation, suitable for the needs of Computer Visualization ? The question is neither intuitively straightforward, nor easy. We address it our forthcoming paper [START_REF] Belaga | Topology-Sensitive Computer Animation Scenarios : Cobordisms and Resolution of Singularities[END_REF].

Problem 2. (Cf. §3, Defintion of spacewise deformations.) Is there a "natural"parametrization of a cobordism transforming it into a pointwise deformation ? Such a parametrization should handle splitting of points and of sub-manifolds, as it is clear from Figure 2 (Left) and the related remark in §2.

Problem 3. (Cf. the remarks at the end of §2 and §7.) Is there an extension of Smooth Cobordism Theory to manifolds with "wild"singularities, suitable for the needs of Computer Visualization ? The answer is yes : cobordisms with singularities are studied since the late sixties [START_REF] Yu | On Thom Spectra, Orientability, and Cobordism[END_REF]. Unfortunately, the theory in question, as it stands now, is built in a too abstract setting to be easily exposed and applied in Computer Visualization [START_REF] Belaga | Topology-Sensitive Computer Animation Scenarios : Cobordisms and Resolution of Singularities[END_REF].

Problem 4. (Cf. §5, Problem of Cobordants in Low Dimensions, dim = 2, and §6.) In particular, is there a 2D theory of cobordisms with singularities which could effectively simulate deformation of surfaces with "wild"singularities ? The answer is yes : see for details our forthcoming paper [START_REF] Belaga | Topology-Sensitive Computer Animation Scenarios : Cobordisms and Resolution of Singularities[END_REF].

Problem 5. (Cf. §5, Problem of Cobordants in Low Dimensions, dim = 3, 4.) Is there an algorithmic procedure which, for a given pair of 3D (respectively, 4D) manifolds, can effectively decide whether they are cobordant or not ? The difficulty of the problem is apparent from the pioneering work [START_REF] Matveev | A Basic Course in Algorithmic and Computer Methods in Three-Dimensional Topology (Russian)[END_REF]. There is a hope that Rokhlin's pure geometric and semi-constructive proof [START_REF] Rokhlin | A Three-Dimensional Manifold Is the Boundary of a Four-Dimensional One (Russian)[END_REF] can be made fully constructive. This direction is especially promising for Computer Visualization, since any progress here depends on, and seems likely to considerably improve, our techniques of modelling and manipulating 3D and 4D manifolds.

Figure 1 .

 1 Figure 1. Visual versus topological equivalences; the picture is borrowed from [9].

Figure 2 .

 2 Figure 2. Left: A circle is cobordant to two circles. Right: A circle is homotopic but neither isotopic, nor cobordant to a point.


E G Belaga

Mod 3 Arithmetic on Triangulated Riemann Surfaces *

Keywords: Riemann surface, triangulation graph, four-colouring, Heawood vector

Let T be a triangulation of a Riemann surface, orientable or nonorientable and of an arbitrary genus. Suppose, a labelling of the vertices of T by three labels 0, +1, and -1 is fixed. The present paper deals with the following problem : find the number of labellings of the faces of T by two labels +1 and -1, in such a way that the sum of the labels of the faces around any vertex is equal modulo 3 to the given label of the vertex. If T is a planar triangulation and all labels of vertices are zeros, then the problem of existence of such a labelling of faces is equivalent, according to P. J. Heawood, to the four-colour problem for planar triangulations, and the corresponding counting problem is equivalent to that of counting the number of all proper four-colourings of T .

Dedicated to the memory of Percy John Heawood, 1861 -1955, on the occasion of the first centenary of his seminal paper [START_REF] Heawood | On the four-colour map theorem[END_REF].

Introduction.

During his early days at Durham while he was teaching a class of divinity students mathematics, one of them asked "You have taught us to cast out nines, can you cast out devils ?""Yes, I can," replied Heawood, "get out at once !" [START_REF] Dirac | [END_REF], p. 266 Percy John Heawood has had both the privilege and stamina to almost single-handedly create the field of graph colourings and to actively participate in its developments over a computing at w = - 1 2 the number of solutions of Problem 1.3 (the formula [START_REF] Belaga | On Heawood vectors of pseudotriangulations[END_REF]). It is the present author's hope that this polynomial and other formulae introduced hereby shall prove themselves useful instruments in studying graphs of triangulations. To substantiate these expectations, intensive calculations were carried out; their results will appear elsewhere.

Our graph-theoretical terminology is that of [START_REF]Handbook of Combinatorics[END_REF], with popular notational deviations indicated, and with a couple of our own notations when [START_REF]Handbook of Combinatorics[END_REF] is silent on the subject. As to the topological prerequisites, they can be found in [START_REF] Bloch | A First Course in Geometric Topology and Differential Geometry[END_REF], Chapter III.

Historical Background and Motivations.

The 4C problem has appeared first as a naive enquiry addressed by a student in London, in 1852, to his brother, also a student, who passed the question to his professor of mathematics, Augustus De Morgan. Unable to answer an apparently trivial question, De Morgan circulated it among London mathematicians. Finally, in 1878, Arthur Cayley submitted the problem to the London Mathematical Society.

Within a year, Alfred Bray Kempe has published a simple and elegant solution [START_REF] Kempe | On the geographical problem of the four-colors[END_REF] which satisfied everybody for at least ten years. Then, Percy John Heawood pointed out a fatal flow in Kempe's argument [START_REF] Heawood | Map colour theorem[END_REF] and proposed his own and, for that matter, a very successful programme of studying 4CP and related problems [START_REF] Heawood | Map colour theorem[END_REF], [START_REF] Heawood | On the four-colour map theorem[END_REF] (both, Kempe and Heawood, deal with planar triangulations and colour vertices). As to Kempe's modest attempt, it became just a popular historical anecdote, -or it seemed so to the general mathematical public : cf. any introduction to graph theory published before 1970.

Kempe's approach was reductive, i. e., inductive and local. Heawood's attitude was synthetic, i. e., global and easily lending itself to generalizations to triangulations of arbitrary Riemann surfaces, as in [START_REF] Heawood | Map colour theorem[END_REF], with its map colour formula [START_REF] Ringel | Map Color Theorem[END_REF], or, in a different way, in the present paper.

Ironically, Kempe's faulty proof gave rise to a method [START_REF] Birkhoff | The reducibility of maps[END_REF] which finally produced a computer-assisted solution of 4CP [START_REF] Appel | The four color proof suffices[END_REF], [START_REF] Appel | Every Planar Graph is Four Colorable[END_REF], whereas Heawood's approach, the brilliant offshoots for Riemann surfaces of non-zero genus notwithstanding [START_REF] Ringel | Map Color Theorem[END_REF], is still waiting its successful 4CP realization.

But does it really matter ? Why should somebody bother to find a [START_REF] Heawood | On the four-colour map theorem[END_REF]-inspired solution of 4CP ? We submit here three major reasons, one "negative"and two "positive", why it should be worth one's while to look for a realization in question.

First, there exists a widespread disappointment with the Kempe-inspired solution of 4CP . Attested by the authors of the solution themselves, the disappointment goes deeper than they are willing to admit, and not exactly as suggested in [START_REF] Appel | Every Planar Graph is Four Colorable[END_REF], p. 1 : "One can never rule out the chance that a short proof of the Four-Color Theorem might some day be found, perhaps by the proverbial high-school student. ".

Indeed, the problem is not so much with the "length"or "computerization"of the proof, but with its intelligibility and instructiveness. Here is a more to the point assessment : "Even if the Appel and Haken solution is perfectly correct ... , it is painfully obvious that it is not an adequate solution to the problem. For one thing it fails to explain why four is the final answer. In mathematics a decent proof is at least an explanation why the result is true." [START_REF] Cohen | On the four color problem[END_REF], p. 6.

The authors themselves submit a tentative, very intuitive, and, to our taste, not very convincing a posteriori elucidation of the "number four"mystery, [START_REF] Cohen | On the four color problem[END_REF], pp. 61-62. And even the masterfully written update [START_REF] Thomas | An update on the four-color theorem[END_REF] of the original proof leaves the mystery unresolved.

Second, Heawood's theorem (Theorem 1.1 above) lends itself to a most natural and elegant topological a priori explanation "why"four colours suffice [START_REF] Belaga | A new interpretation of the four-colour problem[END_REF] (cf. Appendix). Sure, there is no guarantee that such an "explanation"can be translated into an edifying proof * . But its existence greatly encourages the search for such a proof.

Third, the generalization of Heawood's modulo 3 interpretation of 4CP to triangulations of arbitrary Riemann surfaces promises to shed a new light into their "arithmetical "structure. In fact, thanks to [START_REF] Appel | Every Planar Graph is Four Colorable[END_REF], we know that, in the planar case, there exists a positive solution of the Problem 1. [START_REF] Belaga | A new interpretation of the four-colour problem[END_REF]. In what non-planar cases does it exists, too, and if not, "why"?

The Counting Formula.

As it was clear already to Heawood [START_REF] Heawood | On the four-colour map theorem[END_REF], Problem 1.3 is about the existence of solutions of a system of linear equations over the Galois field of cardinality three, F 3 , with a nonlinear condition on the unknown variables : only solutions with non-zero components are admitted. Here is the version of Problem 1.3 which will be the formal subject of the present study :

Problem 3.1. Let T = T p,r (S g ) be a triangulation of a Riemann surface S g (orientable or non-orientable) of the genus g, with p vertices, r faces, and let M T be its incidence matrix vertex-face. Suppose the vertices of T are assigned fixed labels a = (a 1 , ..., a p ) from F 3 . We are looking for the number λ(a, T ) of different labellings x = (x 1 , ..., x r ) of the faces of T by the numbers +1 and -1, satisfying the following system of linear equations over F 3 :

M T • x = a; a ∈ (F 3 ) p = A, x ∈ {+1, -1} r = (F * 3 ) r = X . (1)
Remark 3.2. (1) Notice that, for any a, if

M T • x = a then M T • (-x) = -a.
This implies that λ(a, T ) = λ(-a, T ) and that λ(0, T ) ≥ 0 is even. The case a = 0 will be sometimes referred to as homogeneous.

(2) In particular, when T is a planar triangulation and a = 0, the number 1 2 λ(0, T ) is equal to the number of different proper four-colourings of vertices of T , up to an arbitrary permutation of colours. This fact establishes a link between Problem 3.1 and the 4C problem, of which Problem 3.1 becomes a far reaching generalization.

(3) Notice also that * As Kenneth I. Appel and Wolfgang Haken rightly point out, "But it is also conceivable that no such proof is possible. In this case a new and interesting type of theorem has appeared, one which has no proof of the traditional type." [START_REF] Appel | The four color proof suffices[END_REF] ∀a∈A λ(a, T ) = #X = 2 r .

(2)

Our main result will be a counting formula for λ(a, T ), Theorem 3.4 below. To describe it, we need few standard notations.

Notations 3.3. (1) Let T = T p,r (S g ) = {V, E, F } be a triangulation of a Riemann surface, as above, with, respectively, sets of vertices V , edges E, and faces F ,

V = {v 1 , . . . , v p }, E = {e 1 , . . . , e q }, F = {f 1 , . . . , f r } .
Euler's theorem for graphs on surfaces states that pq + r = 2 -2g, which in the case of a triangulation implies 2q = 3r and

r = 2p + 4g -4 ≥ 2p.
(2) If a vertex v ∈ V belongs, or is adjacent to a face f ∈ F , we shall write v ∈ f . The number α(v) of the faces adjacent to a vertex v is called the degree of v (instead of degree, some use the term valence [START_REF] Ringel | Map Color Theorem[END_REF]). For a subset V of vertices, ∅ ⊆ V ⊆ V , we define its broad neighbourhood complex, or shell for short, t(V ) (respectively, its narrow neighbourhood complex, or core for short, t(V )), as the sub-triangulation of T generated by the sub-sets of faces (f (V ) and f (V ), respectively) which meet at least one (respectively, two) vertices of V .

Since

f (∅) = f (∅) = ∅, we assume that t(∅) = t(∅) = ∅, too.
The terms broad and narrow concur obviously with the inclusions :

f (V ) ⊇ f (V ); t(V ) ⊇ t(V ).
We shall also use the notations

r = α(V ) = #f (V ), s = β(V ) = #f (V ), with r ≥ s and α(V ) = β(V ) = r = #F.
The last α-notation is compatible with the above degree notation :

α(v) = α({v}) = #f ({v}).
(3) We use arithmetical operations over both the ring Z of integers and the Galois field F 3 . When it does not lead to confusion, we use the numbers 0, +1, and -1 as elements of F 3 and the standard arithmetical notations for operations over both integers and the "numbers"0, +1, and -1. Otherwise, the qualifier (mod 3) is added.

Theorem 3.4. Let T be a triangulation of a Riemann surface, as above; let ω = -1 2 . Then the number λ(a, T ) of solutions of the system (1) is given by the following counting formula :

λ(a, T ) = 2 r • 3 -p+1 • ∅⊆V ⊆V \v p ω r • θ a | V , t(V ) = 2 r • 3 -p+1 • 1 + v∈V \v p ω α(v) • θ 1 (a v ) (3) + v,v ∈V \v p ω α({v,v }) • θ 2 a v , a v ; t({v, v }) + . . . ,
where θ a | V , t(V ) are integer functions depending only on the restriction a | V of the vector a to V and on the core t(V ), i. e., on the narrow neighbourhood complex of V (and not on its broad neighbourhood complex t(V ). (The exclusion V \ v p in the above and below, (5), summations is explained below, Theorem 4.1, Assumption 4.3). Note 3.5. (1) The functions θ(. . .) are defined below, Definition 5.3(2), [START_REF] Bouchet | Constructions of covering triangulations with folds[END_REF].They are calculated iteratively, from smaller subsets of vertices (and the corresponding subtriangulations) to bigger ones. The proof of Theorem 3.4 will be given below, §5. A farreaching combinatorial generalization of the above formula and of the narrow dependency property has been announced in [START_REF] Belaga | F 3 -arithmetic over triangulations of Riemann surfaces[END_REF] and will be proved elsewhere.

(2) The main idea behind the formula ( 3) is to re-construct the number λ(a, T ) from numbers of partial solutions of the system (1) : first, one evaluates the numbers of solutions of a void system of equation, then of a one equation of the system, then of two equations, etc. Finally, the functions θ(. . .) are reconstructed (see §5) with the help of Möbius inversion formula [START_REF] Comtet | Advanced Combinatorics[END_REF]. (Compare this including-excluding procedure with that, almost sixty years old, of H. Whitney [START_REF] Whitney | A logical expansion in mathematics[END_REF].)

(3) It is the narrow dependency property that makes the claim (3) nontrivial, its proof rather invloved, and the functions θ(. . .) so interesting invariants of respective subtriangulations. In fact, it is the inclusion-exclusion procedure which "distils"the narrow dependency property from its broad version : cf. Theorem 5.5(2) and Remark 5.6.

(4) To give the first inkling of the structure of the summation formula (3), let us compute its lowest terms. The first summand in (3) is the ∅-approximation of λ(a, T ). To calculate it, denote by A 0 the hyperplane of the vector space A (1) cut off by the equation

a 1 + . . . + a p = 0.
According to Theorem 4.1 below, the system (1) has no solutions if a / ∈ A 0 . Thus, according to (2),

λ 0 (a, T ) = #X #A 0 = 2 r • 3 -p+1
is the average number of solutions when a is varied and T is fixed (in contradistinction to the way, in a similar context, the average is defined in [START_REF] Tutte | On the enumeration of four-colored maps[END_REF]).

(5) Restricting ourselves to ∅and one-vertex-approximations, we take into account the impact of vertices and their neighbourhoods on λ(a, T ), but disregard the influence of edges and more complicated sub-graphs of T , etc.

(6) Proceeding in this way, we calculate, for example :

θ 0 = θ a | ∅ , t(∅) = 1; θ 1 (ξ) = θ 1 (a j ) | a j =ξ = θ a | {v j } , t({v j }) = 2 -3 • ξ 2 ; θ 2 (ξ, η) = . . . = θ 1 (ξ) • θ 1 (η) + 3 • θ 1 (ξ -η), if {v j , v k }is an edge in T ; θ 1 (ξ) • θ 1 (η), otherwise. (4)
The above formula for θ 2 (ξ, η) is "weakly multiplicative ". This property of functions θ is the subject of Theorem 5.5(3).

(7) Note that the above "small"coefficients θ(. . .) are positive when a = 0 (which, in particular, is the case of 4CP for planar triangulations). This phenomenon, which can be verified for #V = 3, 4 as well, remains an enigma : cf. Conjecture 6.4 below.

Definition 3.6. Let T be a triangulation of a Riemann surface, as above. Assign to each face f j a formal variable w j , 1 ≤ j ≤ r. Proceeding from the formula (3), define the polynomial

L(W ; a, T ) = ∅⊆V ⊆V \v p θ a | V , t(V ) • f j ∈ f (V ) w j , (5)
We also define

L(w; a, T ) = L(W ; a, T ) | w 1 =...=w r =w so that, obviously, λ(a, T ) = 2 r • 3 -p+1 • L(-1 2 ; a, T ). ( 6
)
4. Rank of the Incidence Matrix.

Let M T be the incidence vertex-face matrix of a triangulation T of a Riemann surface S, as above, Problem 3.1. Attempting to solve the system (1), one has first to eliminate one trivial obstruction : Theorem 4.1. (In the planar case, g = 0, [START_REF] Heawood | On the four-colour map theorem[END_REF]; for Riemann surfaces of arbitrary genus g ≥ 0, [START_REF] Belaga | On Heawood vectors of pseudotriangulations[END_REF]).

(1) Since each face of M T is a triangle, all but three entries of any column of M T are zeros. This means that the sum of all rows of M T is zero in F r 3 ,

1 p × M T = 0 r
which implies : (a) the system (1) has no solutions if the free-term vector a does not belong to A 0 (cf. Note 3.5(4)) :

(1 p , a) = 0 =⇒ ∀x ∈ X. M T • x = a;

(b) the inequality holds :

rank F 3 (M T ) ≤ p -1.
(2) If rank F 3 (M T ) = p -1, then, according to the inequality (Euler's formula, cf. (3) The inequality holds :

rank F 3 (M T ) ≥ p -2. ( 4
)
The following two properties are equivalent :

(i) rank F 3 (M T ) = p -2 ,
(ii) the triangulation T has a proper three-colouring of its vertices; such a colouring is unique up to a permutation of the colours.

Note 4.2. In the planar case, g = 0, the above two properties are equivalent to the third one : a proper three-colouring exists iff all vertices of T have even degrees, see Theorem 1.4 above. Two examples of triangulations of a torus, Figure 1, with all vertices of even degrees, and with the chromatic numbers 5 and 7, respectively, demonstrate that in the case g > 0 the "if"condition ceases to be true. A,P,b,c,d,e , all of even degree (respectively, 4, 8, 6, 6, 6, 6) , which is not three-colourable (cf. Theorem 1.4). Albeit there exists (as displayed on the diagramme above) a ±1 labelling of faces of the triangulation with sums around vertices equal to 0 modulo 3, it is not four-but five-colourable (cf. Theorem 1.1).

Lemma 5.2. The function λ(a, V ) has integer values and substantially depends only on (this means : is completely determined by) the sub-vector a | V and the shell t(V ) of V in T 0 .

Proof. The values x j corresponding to those faces f j which are not adjacent to one of the vertices of V , do not contribute to the summation and can be chosen arbitrary. The number of such faces is rr .

Instead of λ(a, V ), we shall sometimes use the explicit notations λ a | V , t(V ) . Definition 5.3. ( 1) For any a ∈ A 0 and any V , ∅ ⊆ V ⊆ V 0 , define the function

ζ(a, V ) = ζ a | V , t(V )
inductively, as follows :

ζ(a, ∅) = 1; ∀V , ∅ = V ⊆ V 0 . ζ(a, V ) = 2 -r • 3 p • λ a | V , t(V ) - ∅⊆V ⊆V ζ a | V , t(V ) . (9)
(2) For any a ∈ A 0 and any V , ∅ ⊆ V ⊆ V 0 , define the function θ(a, V ), as follows :

θ(a, V ) = θ a | V , t(V ) = (-2) -r • ζ a | V , t(V ) ; ζ(a, V ) = ω r • θ(a, V ), where ω = - 1 2 . (10) Lemma 5.4.
(1) According to [START_REF] Birkhoff | The reducibility of maps[END_REF], for any V , ∅ ⊆ V ⊆ V 0 , one has, tautologically,

λ(a, V ) = 2 r • 3 -p • ∅⊆V ⊆V ζ(a, V ).
(2) Applying Möbius inversion formula [START_REF] Comtet | Advanced Combinatorics[END_REF], we have :

ζ(a, V ) = ∅⊆V ⊆V (-1) p -p • 2 -r • 3 p • λ(a, V ). (11)
(3) Thus (cf. ( 8)),

λ(a, V ) = 2 r • 3 -p • ∅⊆V ⊆V ω r • θ(a, V ), λ(a, V ) = 2 r • 3 -p • ∅⊆V ⊆V ω r • θ(a, V ).
Theorem 5.5. (1) The functions θ(. . .) defined in [START_REF] Bloch | A First Course in Geometric Topology and Differential Geometry[END_REF] are integer-valued.

(2) These functions substantially depend only on the sub-vector a | V and the core t(V ) of V in T 0 (and not on the shell, as in ( 9), [START_REF] Bloch | A First Course in Geometric Topology and Differential Geometry[END_REF]) :

θ(a, V ) = θ a | V , t(V ) .
(3) The functions λ(. . .) (8) and θ(. . .) [START_REF] Bloch | A First Course in Geometric Topology and Differential Geometry[END_REF] are weakly multiplicative, in the following sense :

∀V , V (∅ ⊆ V , V ⊆ V 0 ). t(V ) ∩ t(V ) = ∅ =⇒ λ(a, V ∪ V ) = λ(a, V ) • λ(V ), θ(a, V ∪ V ) = θ(a, V ) • θ(V ).
(The low part of the formula for θ 2 in (4) is a special case of the general formula for

θ(a, V ∪ V ), when #V = #V = 1 and #(V ∪ V ) = 2.) (4) Let ∅ ⊆ V ⊆ V ⊆ V 0 , V = {v i 1 , . . . , v i p }, 1 ≤ i 1 < i 2 < . . . < i p ≤ p -1.
Then

α=(α 1 ,...,α p )∈F p 3 λ(a | a i 1 =α 1 ,...,a i p =α p , V ) = 2 d • λ(a, V \ V ), d = # f (V ) \ f (V \ V ) . (5) Let ∅ ⊆ V , V ⊆ V 0 , V ∩ V = ∅, V = {v i 1 , . . . , v i p }, 1 ≤ i 1 < i 2 < . . . < i p ≤ p -1.
Then

α=(α 1 ,...,α p )∈F p 3 λ(a | a i 1 =α 1 ,...,a i p =α p , V ) = 3 p • λ(a, V ) (6) Respectively, ∀k, 1 ≤ k ≤ p . α∈F 3 θ(a, V ) | a i k =α = θ(a, V ) | a i k =0 +θ(a, V ) | a i k =1 +θ(a, V ) | a i k =-1 = 0.
Remark 5.6. Whereas the claims (1), ( 3), (5) of the above theorem can be proved relatively easily, as simple formal corollaries of Definitions 5.1, 5.3, the proofs of the statements (4), ( 6) are less evident, and that of the statement (2) is definitely more involved. (It will be given elsewhere.) This is because the property of "narrow dependency "is neither true for the functions λ(. . .), no can it be imposed in a straightforward manner. In fact, it is the inclusion-exclusion procedure (9), [START_REF] Bloch | A First Course in Geometric Topology and Differential Geometry[END_REF] which "distils "the narrow dependency property from its broad brand of Lemma 5.2; cf. Note 3.5(3).

Enquiries and Conjectures.

Calculations, both theoretical and based on examples, with respect to the Problem 1.2, suggest several conjectures concerning the system (1) and the counting function λ(a, T ). Three of these conjectures, if true, imply the positive answer to 4CP . The logic of justification of theses conjectures and the insights involved therein are rather intricate, and are somewhat similar to those explicated in [START_REF] Cohen | On the four color problem[END_REF] with respect to a version of the proof [START_REF] Appel | Every Planar Graph is Four Colorable[END_REF] of 4CP .

Conjecture 6.1 : Weak Homogeneity Conjecture. In the homogeneous case, a = 0, the counting function λ is positive : ∀S ∀T. λ(0, T ) > 0 Conjecture 6.2 : Strong Homogeneity Conjecture. The counting function λ(a, T ) attains its maximum in the homogeneous case, a = 0 : ∀S ∀T ∀a ∈ F p 3 . λ(0, T ) ≥ λ(a, T ). Conjecture 6.3 : "Big Triangulations"Conjecture.

(1) Strong (or Global) Version. If the triangulation T is "big enough", then the system (1) has a solution for any a : ∃P > 0. ∀p > P. ∀S ∀T = T p,r (S) ∀a ∈ F p 3 . λ(a, T ) > 0.

(2) Weak (or Local) Version. If, for a given Riemann surface S g , the triangulation T = T p,r (S g ) is "big enough", then the system (1) has a solution for any a :

∀S. ∃P = P (S) > 0. ∀p > P. ∀T = T p,r (S). ∀a ∈ F p 3 . λ(a, T ) > 0. Conjecture 6.4 : Local Homogeneity Conjecture. (Cf. the formulae (4).) The functions θ are positive in the homogeneous case :

∀S ∀T ∀V ⊆ (V \ v p ). θ = θ 0 | V , t(V ) > 0.
Mock Conjecture 6.5. The above Local Homogeneity Conjecture implies the Weak Homogeneity Conjecture (Conjecture 6.1) and is "its real reason and explanation". 7. Appendix. . Heawood's theorem (Theorem 1.1 above) has an elegant geometric interpretation via a folding of a planar triangulation into a tetrahedron. This "folding"interpretation [START_REF] Belaga | A new interpretation of the four-colour problem[END_REF], [START_REF] Belaga | Arithmetic of colorings of planar graphs[END_REF] lends itself naturally to a generalization to a n-dimensional case [START_REF] Belaga | On coloring the graph of a triangulation of an n-sphere[END_REF] :

(1) Construction 1 : 4C-tetrahedron. Identify the four colours with four vertices of a 3D simplex; call it the four-colour (4C-) tetrahedron. Then interpret four colouring of vertices of a planar triangulation as a mapping of the set of these vertices into the set of four vertices of the 4C-tetrahedron.

(2) Construction 2 : Extending a Proper Four Colouring to the Tetra-Colouring. A four colouring of a triangulation is proper iff the above mapping can be naturally extended to the mapping of the set of edges of the triangulation into the set of edges of the 4C-tetrahedron, and then to the mapping of the respective sets of faces. Call such mapping a tetra-colouring of the triangulation.

(3) Heawood's Theorem : "Only If ". Given a planar triangulation, fix orientations on it and on the 4C-tetrahedron. Given a proper four-colouring of the triangulation, construct its tetra-colouring extension and assign to each of the faces of the triangulation the label +1 or -1, according to whether the tetra-colouring preserves or not the chosen orientations. We call this labelling a Heawood vector over the triangulation. Then the sum of the labels of the faces around any vertex is equal to the local multiplicity of the mapping [START_REF] Wolf | Spaces of Constant Curvature[END_REF] times 3 (= the number of faces around a vertex in the tetrahedron) : cf. Figure 2. Thus, this sum is 0 modulo 3 ! Figure 2. A proper four-colouring of a sub-triangulation (on the left), with six vertices A -F. Four colours are identified with four vertices of the 4C-tetrahedron (on the right). All edges and faces of the tetrahedron have their numerical labels, respectively, 1-6 and 1 -4 (including the sole invisible face labelled 4 ). The coulouring of vertices of the sub-triangulation induces its mapping on the upper side of the tetrahedron, with the corresponding labellings of its edges and faces. The foldings occur along the edges AB, AF, and AC. The local multiplicity of the mapping at A is equal to +1.

(4) Heawood's Theorem : "If ". As above, for a given planar triangulation and the 4C-tetrahedron, fix orientations. Suppose a labelling of the faces of the triangulation by +1 and -1 is given, with the property that the sum of the labels of the faces around any vertex is 0 modulo 3, (0 modulo 3 property for short). Choose a pair of faces, one from the triangulation, another from the 4C-tetrahedron, and map the first face on the second one in such a manner that the orientation of the face would be preserved if the face is labelled by +1, and would be inverted otherwise. Then the 0 modulo 3 property guarantees that the mapping can be extended in a unique way on all faces of the triangulation defining its tetra-colouring.

(5) Corollary. Suppose a labelling of the faces of the triangulation by +1 and -1 is given, satisfying the above 0 modulo 3 property. Then the sum of the labels of all faces is equal to the global multiplicity of the corresponding tetra-colouring times 4 ( = the number of faces in the tetrahedron); thus, this sum is 0 modulo 4 [START_REF] Belaga | A new interpretation of the four-colour problem[END_REF].

(6) Generalization to the n-dimensional case. Heawood vector can be defined for any proper (n + 2)-colouring, n ≥ 2, of a graph corresponding to a n -dimensional simplicial complex T , and the corresponding congruences mod n + 3dim(s) can be conjectured and proved for any simplex s of T , -1 ≤ dim(s) ≤ n + 1. Here too, as in the two-dimensional case (Remark 1.3), we work within the most general interpretation of a n-dimensional simplicial complex [START_REF] Belaga | On Heawood vectors of pseudotriangulations[END_REF].

  Notations 3.3(1)) r = 2p + 4g -4 ≥ 2p, any ((p -1) × r)-sub-matrix of M T has the rank p -1.

Figure 1 .

 1 Figure 1. Left. Triangulation of a torus with six vertices, A, P, b,c, d, e, all of even degree (respectively, 4, 8, 6, 6, 6, 6) , which is not three-colourable (cf. Theorem 1.4). Albeit there exists (as displayed on the diagramme above) a ±1 labelling of faces of the triangulation with sums around vertices equal to 0 modulo 3, it is not four-but five-colourable (cf. Theorem 1.1).

Right. Triangulation of a torus with seven vertices, A, P, Q, b, c, d, e , all of even degree (respectively, [START_REF] Bloch | A First Course in Geometric Topology and Differential Geometry[END_REF][START_REF] Biggs | Graph Theory : 1736 -1936[END_REF][START_REF] Biggs | Graph Theory : 1736 -1936[END_REF][START_REF] Belaga | Arithmetic of colorings of planar graphs[END_REF][START_REF] Belaga | Arithmetic of colorings of planar graphs[END_REF][START_REF] Belaga | Arithmetic of colorings of planar graphs[END_REF][START_REF] Belaga | Arithmetic of colorings of planar graphs[END_REF], with a ±1 labelling of faces having the above 0 modulo 3 property. The sub-graph of this triangulation with seven vertices and double-lined edges is the complete graph K 7 ; thus, the triangulation is seven-colourable. Assumption 4. [START_REF] Belaga | A new interpretation of the four-colour problem[END_REF]. In what follows, we assume (without much loss of generality, according to Theorem 4.1(4)) that

Thus, one of the equations of the system (1) can be disregarded, and according to Theorem 4.1(2), it can be any of the equations; in what follows, it will be the equation corresponding to the vertex v p . This fact accounts for the exclusion V \ v p in the summations (3) and (5).

Partial Counting Functions and Formulae.

Henceforth, the triangulation T is fixed and does not appear in the notations of objects associated with it. Removing from T the vertex v p , one gets the (sub-)triangulation T 0 with the set of vertices V 0 = V \v p . Replace now the system (1) with its truncated version,

with the ((p -1) × r) matrix M 0 being the sub-matrix of the incidence vertex-face matrix M T , as above, whose last row (corresponding to v p ) is omitted.

As it was suggested above (Note 3.5(2)), along with the system [START_REF] Belaga | F 3 -arithmetic over triangulations of Riemann surfaces[END_REF], one needs to study all its sub-systems : Definition 5.1. For any a ∈ A 0 and any subset V of V 0 , ∅ ⊆ V ⊆ V 0 , define the functions λ(a, V ) and λ(a, V ) as follows :

(i) either V = ∅, and then λ(a, ∅)

and then (Notations 3.3)

λ(a, V ) = 2 r-r • λ(a, V ), where r = #f (V ) .