Houssam Khalil
email: khalil@math.univ-lyon1.fr

Bernard Mourrain
email: mourrain@sophia.inria.fr

AND Michelle Schatzman

TOEPLITZ AND TOEPLITZ-BLOCK-TOEPLITZ MATRICES AND THEIR CORRELATION WITH SYZYGIES OF POLYNOMIALS

Keywords: Toeplitz matrix, rational interpolation, syzygie

In this paper, we re-investigate the resolution of Toeplitz systems T u = g, from a new point of view, by correlating the solution of such problems with syzygies of polynomials or moving lines. We show an explicit connection between the generators of a Toeplitz matrix and the generators of the corresponding module of syzygies. We show that this module is generated by two elements of degree n and the solution of T u = g can be reinterpreted as the remainder of an explicit vector depending on g, by these two generators.

This approach extends naturally to multivariate problems and we describe for Toeplitz-block-Toeplitz matrices, the structure of the corresponding generators.

1. Introduction. Structured matrices appear in various domains, such as scientific computing, signal processing, . . . They usually express, in a linearize way, a problem which depends on less parameters than the number of entries of the corresponding matrix. An important area of research is devoted to the development of methods for the treatment of such matrices, which depend on the actual parameters involved in these matrices.

Among well-known structured matrices, Toeplitz and Hankel structures have been intensively studied [START_REF] Heinig | Algebraic methods for Toeplitz-like matrices and operators[END_REF][START_REF] Kailath | Displacement structure: theory and applications[END_REF]. Nearly optimal algorithms are known for the multiplication or the resolution of linear systems, for such structure. Namely, if A is a Toeplitz matrix of size n, multiplying it by a vector or solving a linear system with A requires Õ(n) arithmetic operations (where Õ(n) = O(n log c (n)) for some c > 0) [START_REF] Bitmead | Asymptotically fast solution of Toeplitz and related systems of equations[END_REF][START_REF] Van Barel | A stabilized superfast solver for nonsymmetric Toeplitz systems[END_REF]. Such algorithms are called super-fast, in opposition with fast algorithms requiring O(n 2 ) arithmetic operations.

The fundamental ingredients in these algorithms are the so-called generators [START_REF] Kailath | Displacement structure: theory and applications[END_REF], encoding the minimal information stored in these matrices, and on which the matrix transformations are translated. The correlation with other types of structured matrices has also been well developed in the literature [START_REF] Pan | Structured matrices and polynomials[END_REF][START_REF] Pan | Nearly optimal computations with structured matrices[END_REF], allowing to treat so efficiently other structures such as Vandermonde or Cauchy-like structures.

Such problems are strongly connected to polynomial problems [START_REF] Fuhrmann | A polynomial approach to linear algebra[END_REF][START_REF] Bini | Polynomial and matrix computations[END_REF]. For instance, the product of a Toeplitz matrix by a vector can be deduced from the product of two univariate polynomials, and thus can be computed efficiently by evaluation-interpolation techniques, based on FFT. The inverse of a Hankel or Toeplitz matrix is connected to the Bezoutian of the polynomials associated to their generators.

However, most of these methods involve univariate polynomials. So far, few investigations have been pursued for the treatment of multilevel structured matrices [START_REF] Tyrtyshnikov | Fast algorithms for block Toeplitz matrices[END_REF], related to multivariate problems. Such linear systems appear for instance in resultant or in residue constructions, in normal form computations, or more generally in multivariate polynomial algebra. We refer to [START_REF] Mourrain | Multivariate polynomials, duality, and structured matrices[END_REF] for a general description of such correlations between multi-structured matrices and multivariate polynomials. Surprisingly, they also appear in numerical scheme and preconditionners. A main challenge here is to devise super-fast algorithms of complexity Õ(n) for the resolution of multi-structured systems of size n.

In this paper, we consider block-Toeplitz matrices, where each block is a Toeplitz matrix. Such a structure, which is the first step to multi-level structures, is involved in many bivariate problems, or in numerical linear problems.We re-investigate first the resolution of Toeplitz systems T u = g, from a new point of view, by correlating the solution of such problems with syzygies of polynomials or moving lines. We show an explicit connection between the generators of a Toeplitz matrix and the generators of the corresponding module of syzygies. We show that this module is generated by two elements of degree n and the solution of T u = g can be reinterpreted as the remainder of an explicit vector depending on g, by these two generators. This approach extends naturally to multivariate problems and we describe for Toeplitz-block-Toeplitz matrices, the structure of the corresponding generators. In particular, we show the known result that the module of syzygies of k non-zero bivariate polynomials is free of rank k -1, by a new elementary proof.

Exploiting the properties of moving lines associated to Toeplitz matrices, we give a new point of view to resolve a Toeplitz-block-Toeplitz system.

In the next section we studie the scalar Toeplitz case. In the chapter 3 we consider the Toeplitzblock-Toeplitz case.

Let

R = K[x].
For n ∈ N, we denote by K[x] n the vector space of polynomials of degree ≤ n. Let L = K[x, x -1 ] be the set of Laurent polynomials in the variable x. For any polynomial p = n i=-m p i x i ∈ L, we denote by p + the sum of terms with positive exponents: p + = n i=0 p i x i and by p -, the sum of terms with strictly negative exponents:

p -= -1 i=-m p i x i . We have p = p + + p -.
For n ∈ N, we denote by U n = {ω; ω n = 1} the set of roots of unity of order n.

2. Univariate case. We begin by the univariate case and the following problem:

problem 2.1. Given a Toeplitz matrix T = (t i-j ) n-1 i,j=0 ∈ K n×n (T = (T ij ) n-1 i,j=0 with T ij = t i-j ) of size n and g = (g 0 , . . . , g n-1 ) ∈ K n , find u = (u 0 , . . . , u n-1 ) ∈ K n such that T u = g.
(2.1)

Let E = {1, . . . , x n-1 }, and Π E be the projection of R on the vector space generated by E, along x n , x n+1 , . . . . Definition 2.2. We define the following polynomials:

• T (x) = n-1 i=-n+1 t i x i , • T (x) = 2n-1 i=0 ti x i with ti = t i if i < n t i-2n if i ≥ n , • u(x) = n-1 i=0 u i x i , g(x) = n-1 i=0 g i x i .
Notice that T = T + + x 2 n T -and T (w) = T (w) if w ∈ U 2 n . We also have (see [START_REF] Mourrain | Multivariate polynomials, duality, and structured matrices[END_REF])

T u = g ⇔ Π E (T (x)u(x)) = g(x).
For any polynomial u ∈ K[x] of degree d, we denote it as u(x) = u(x) + x n u(x) with deg(u) ≤ n -1 and deg(u) ≤ dn if d ≥ n and u = 0 otherwise. Then, we have

T (x) u(x) = T (x)u(x) + T (x)x n u(x) = Π E (T (x)u(x)) + Π E (T (x)x n u(x)) +(α -n+1 x -n+1 + • • • + α -1 x -1 ) +(α n x n + • • • + α n+m x n+m ) = Π E (T (x)u(x)) + Π E (T (x)x n u(x)) +x -n+1 A(x) + x n B(x), (2.2)
with m = max(n -2, d -1),

A(x) = α -n+1 + • • • + α -1 x n-2 , B(x) = α n + • • • + α n+m x m . (2.3)
See [START_REF] Mourrain | Multivariate polynomials, duality, and structured matrices[END_REF] for more details, on the correlation between structured matrices and (multivariate) polynomials.

2.1. Moving lines and Toeplitz matrices. We consider here another problem, related to interesting questions in Effective Algebraic Geometry. problem 2.3. Given three polynomials a, b, c ∈ R respectively of degree < l, < m, < n, find three polynomials p, q, r ∈ R of degree < νl, < νm, < νn, such that a(x) p(x) + b(x) q(x) + c(x) r(x) = 0.

(2.4)

We denote by L(a, b, c) the set of (p, q, r) ∈ K[x] 3 which are solutions of (2.4). It is a K

[x]-module of K[x] 3 . The solutions of the problem (2.3) are L(a, b, c) ∩ K[x] ν-l-1 × K[x] ν-m-1 × K[x] ν-n-1 .
Given a new polynomial d(x) ∈ K[x], we denote by L(a, b, c; d) the set of (p, q, r) ∈ K[x] 3 such that a(x) p(x) + b(x) q(x) + c(x) r(x) = d(x).

Theorem 2.4. For any non-zero vector of polynomials (a, b, c)

∈ K[x] 3 , the K[x]-module L(a, b, c) is free of rank 2.
Proof. By the Hilbert's theorem, the ideal I generated by (a, b, c) has a free resolution of length at most 1, that is of the form:

0 → K[x] p → K[x] 3 → K[x] → K[x]/I → 0.
As I = 0, for dimensional reasons, we must have p = 2.

Definition 2.5. A µ-base of L(a, b, c) is a basis (p, q, r), (p ′ , q ′ , r ′ ) of L(a, b, c), with (p, q, r) of minimal degree µ.

Notice if µ 1 is the smallest degree of a generator and µ 2 the degree of the second generator (p ′ , q ′ , r ′ ), we have

d = max(deg(a), deg(b), deg(c)) = µ 1 + µ 2 . Indeed, we have 0 → K[x] ν-d-µ1 ⊕ K[x] ν-d-µ2 → K[x] 3 ν-d → K[x] ν → K[x] ν /(a, b, c) ν → 0,
for ν >> 0. As the alternate sum of the dimension of the K-vector spaces is zero and

K[x] ν /(a, b, c) ν is 0 for ν >> 0, we have 0 = 3 (d -ν -1) + ν -µ 1 -d + 1 + ν -µ 2 -d + 1 + ν + 1 = d -µ 1 -µ 2 .
For L( T (x), x n , x 2n -1), we have µ 1 + µ 2 = 2 n. We are going to show now that in fact µ 1 = µ 2 = n: Proposition 2.6. The K[x]-module L( T (x), x n , x 2n -1) has a n-basis.

Proof. Consider the map

K[x] 3 n-1 → K[x] 3n-1 (2.5)
(p(x), q(x), r(x)) → T (x)p(x) + x n q(x) + (x 2n -1)r(x) which 3n × 3n matrix is of the form

S :=   T 0 0 -I n T 1 I n 0 T 2 0 I n   . (2.6)
where T 0 , T 1 , T 2 are the coefficient matrices of ( T (x), x T (x), . . . , x n T (x)), respectively for the list of monomials (1, . . . , x n-1 ), (x n , . . . , x 2n-1 ), (x 2n , . . . , x 3n-1 ). Notice in particular that T = T 0 + T 2 Reducing the first rows of (T 0 |0| -I n ) by the last rows (T 2 |0|I n ), we replace it by the block (T 0 + T 2 |0|0), without changing the rank of S. As T = T 0 + T 2 is invertible, this shows that the matrix S is of rank 3n. Therefore, there is no syzygies in degree n -1. As the sum 2n = µ 1 + µ 2 and µ 1 ≤ n, µ 2 ≤ n where µ 1 , µ 2 are the smallest degree of a pair of generators of L( T (x), x n , x 2n -1) of degree ≤ n, we have µ 1 = µ 2 = n. Thus there exist two linearly independent syzygies (u 1 , v 1 , w 1 ), (u 2 , v 2 , w 2 ) of degree n, which generate L( T (x), x n , x 2n -1).

A similar result can also be found in [START_REF] Van Barel | A stabilized superfast solver for nonsymmetric Toeplitz systems[END_REF], but the proof much longer than this one, is based on interpolation techniques and explicit computations. Let us now describe how to construct explicitly two generators of L( T (x), x n , x 2n -1) of degree n (see also [START_REF] Van Barel | A stabilized superfast solver for nonsymmetric Toeplitz systems[END_REF]).

As T (x) is of degree ≤ 2 n -1 and the map (2.5) is a surjective function, there exists (u, v, w)

∈ K[x] 3 n-1 such that T (x)u(x) + x n v(x) + (x 2 n -1) w = T (x)x n , (2.7)
we deduce that (u

1 , v 1 , w 1 ) = (x n -u, -v, -w) ∈ L( T (x), x n , x 2n -1). As there exists (u ′ , v ′ , w ′ ) ∈ K[x] 3 n-1 such that T (x)u ′ (x) + x n v ′ (x) + (x 2 n -1) w ′ = 1 = x n x n -(x 2 n -1) (2.8) we deduce that (u 2 , v 2 , w 2 ) = (-u ′ , x n -v ′ , -w ′ -1) ∈ L( T (x), x n , x 2n -1). Now, the vectors (u 1 , v 1 , w 1 ), (u 2 , v 2 , w 2 ) of L( T (x),
x n , x 2n -1) are linearly independent since by construction, the coefficient vectors of x n in (u 1 , v 1 , w 1 ) and (u 2 , v 2 , w 2 ) are respectively (1, 0, 0) and (0, 1, 0).

Proposition 2.7. The vector u is solution of (2.1) if and only if there exist v(x)

∈ K[x] n-1 , w(x) ∈ K[x] n-1 such that (u(x), v(x), w(x)) ∈ L( T (x), x n , x 2n -1; g(x))
Proof. The vector u is solution of (2.1) if and only if we have

Π E (T (x)u(x)) = g(x). As u(x) is of degree ≤ n-1, we deduce from (2.2) and (2.3) that there exist polynomial A(x) ∈ K[x] n-2 and B(x) ∈ K[x] n-1 such that T (x)u(x) -x -n+1 A(x) -x n B(x) = g(x)
.

By evaluation at the roots ω ∈ U 2n , and since ω -n = ω n and T (ω) = T (ω) for ω ∈ U n , we have

T (ω)u(ω) + ω n v(ω) = g(ω), ∀ω ∈ U 2n (ω), with v(x) = -x A(x) -B(x) of degree ≤ n -1. We deduce that there exists w(x) ∈ K[x] such that T (x)u(x) + x n v(x) + (x 2n -1)w(x) = g(x). Notice that w(x) is of degree ≤ n -1, because (x 2n -1) w(x) is of degree ≤ 3n -1.
Conversely, a solution (u(x), v(x), w(x)) ∈ L( T (x), x n , x 2n -1; g(x)) ∩ K[x] 3 n-1 implies a solution (u, v, w) ∈ K 3 n of the linear system:

S   u v w   =   g 0 0  
where S is has the block structure (2.6), so that T 2 u + w = 0 and T 0 uw = (T 0 + T 2 )u = g. As we have T 0 + T 2 = T , the vector u is a solution of (2.1), which ends the proof of the proposition.

Euclidean division.

As a consequence of proposition 2.6, we have the following property:

Proposition 2.8. Let {(u 1 , v 1 , w 1 ), (u 2 , v 2 , w 2 )} a n-basis of L( T (x), x n , x 2n -1), the remainder of the division of   0 x n g g   by   u 1 u 2 v 1 v 2 w 1 w 2 
 is the vector solution given in the proposition (2.7).

Proof. The vector

  0 x n g -g   ∈ L( T (x), x n , x 2 n -1; g) (a particular solution). We divide it by   u 1 u 2 v 1 v 2 w 1 w 2   we obtain   u v w   =   0 x n g g   -   u 1 u 2 v 1 v 2 w 1 w 2   p q (u, v, w) is the remainder of division, thus (u, v, w) ∈ K[x] 3 n-1 ∩ L( T (x), x n , x 2 n -1; g). However (u, v, w) is the unique vector ∈ K[x] 3 n-1 ∩ L( T (x), x n , x 2 n -1; g) because if there is an other vector then their difference is in L( T (x), x n , x 2 n -1) ∩ K[x] 3
n-1 which is equal to {(0, 0, 0)}. problem 2.9. Given a matrix and a vector of polynomials e(x) e ′ (x) f (x) f ′ (x) of degree n, and

p(x) q(x) of degree m ≥ n, such that e n e ′ n f n f ′ n is invertible; find the remainder of the division of p(x) q(x) by e(x) e ′ (x) f (x) f ′ (x) .
Proposition 2.10. The first coordinate of remainder vector of the division of 0 x n g by u u ′ r r ′ is the polynomial v(x) solution of (2.1).

We describe here a generalized Euclidean division algorithm to solve problem (2.9).

Let E(x) = p(x) q(x) of degree m, B(x) = e(x) e ′ (x) f (x) f ′ (x) of degree n ≤ m. E(x) = B(x)Q(x) + R(x) with deg(R(x)) < n, and deg(Q(x)) ≤ m -n. Let z = 1 x E(x) = B(x)Q(x) + R(x) ⇔ E( 1 z ) = B( 1 z )Q( 1 z ) + R( 1 z ) ⇔z m E( 1 z )= z n B( 1 z )z m-n Q( 1 z ) + z m-n+1 z n-1 R( 1 z ) ⇔ Ê(z) = B(z) Q(z) + z m-n+1 R(z) (2.9)
with Ê(z), B(z), Q(z), R(z) are the polynomials obtained by reversing the order of coefficients of polynomials E(z), B(z), Q(z), R(z).

(2.9) ⇒ Ê(z)

B(z) = Q(z) + z m+n-1 R(z) B(z) ⇒ Q(z) = Ê(z) B(z) mod z m-n+1 1 B(z)
exists because its coefficient of highest degree is invertible. Thus Q(z) is obtained by computing the first mn + 1 coefficients of Ê(z) B(z) .

To find

W (x) = 1 B(x)
we will use Newton's iteration: Let

f (W ) = B -W -1 . f ′ (W l ).(W l+1 -W l ) = -W -1 l (W l + 1 -W l )W -1 l = f (W l ) = B -W -1 l , thus W l+1 = 2W l -W l BW l .
and W 0 = B-1

0 which exists. W -W l+1 = W -2W l + W l BW l = W (I 2 -BW l ) 2 = (W -W l ) B(W -W l )
Thus W l (x) = W (x) mod x 2l for l = 0, . . . , ⌈log(mn + 1)⌉. Proposition 2.11. We need O(n log(n) log(mn) + m log m) arithmetic operations to solve problem (2.9)

Proof. We must do ⌈log(mn + 1)⌉ Newton's iteration to obtain the first mn + 1 coeficients of 1 B = W (x). And for each iteration we must do O(n log n) arithmetic operations (multiplication of polynimials of degree n). And then we need O(m log m) aritmetic operations to do the multiplication Ê.

1 B .

Construction of the generators. The canonical basis of K[x]

3 is denoted by σ 1 , σ 2 , σ 3 . Let ρ 1 , ρ 2 the generators of L( T (x), x n , x 2n -1) of degree n given by

ρ 1 = x n σ 1 -(u, v, w) = (u 1 , v 1 , w 1 ) ρ 2 = x n σ 2 -(u ′ , v ′ , w ′ ) = (u 2 , v2 , w 2 ) (2.10)
with (u, v, w), (u ′ , v ′ , w ′ ) are the vector given in (2.7) and (2.8).

We will describe here how we compute (u 1 , v 1 , w 1 ) and (u 2 , v 2 , w 2 ). We will give two methods to compute them, the second one is the method given in [START_REF] Van Barel | A stabilized superfast solver for nonsymmetric Toeplitz systems[END_REF]. The first one use the Euclidean gcd algorithm:

We will recal firstly the algebraic and computational properties of the well known extended Euclidean algorithm (see [START_REF] Zur Gathen | Modern computer algebra[END_REF]): Given p(x), p ′ (x) two polynomials in degree m and m ′ respectively, let

r 0 = p, r 1 = p ′ , s 0 = 1, s 1 = 0, t 0 = 0, t 1 = 1.
and define

r i+1 = r i-1 -q i r i , s i+1 = s i-1 -q i s i , t i+1 = t i-1 -q i t i ,
where q i results when the division algorithm is applied to r i-1 and r i , i.e. r i-1 = q i r i + r i+1 . deg r i+1 < deg r i for i = 1, . . . , l with l is such that r l = 0, therefore r l-1 = gcd(p(x), p ′ (x)). Proposition 2.12. The following relations hold:

s i p + t i p ′ = r i and (s i , t i ) = 1 for i = 1, . . . , l and
             deg r i+1 < deg r i , i = 1, . . . , l -1 deg s i+1 > deg s i and deg t i+1 > deg t i , deg s i+1 = deg(q i .s i ) = deg v -deg r i , deg t i+1 = deg(q i .t i ) = deg u -deg r i .
Proposition 2.13. By applying the Euclidean gcd algorithm in p(x) = x n-1 T and p ′ (x) = x 2n-1 in degree n -1 and n -2 we obtain ρ 1 and ρ 2 respectively Proof. We saw that T u = g if and only if there exist A(x) and B(x) such that

T (x)u(x) + x 2n-1 B(x) = x n-1 b(x) + A(x)
with T (x) = x n-1 T (x) a polynomial of degree ≤ 2n -2. In (2.7) and (2.8) we saw that for g(x) = 1 (g = e 1 ) and g(x) = x n T (x) (g = (0, t -n+1 , . . . , t -1 ) T ) we obtain a base of L( T (x), x n , x 2n -1).

T u 1 = e 1 if and only if there exist

A 1 (x), B 1 (x) such that T (x)u 1 (x) + x 2n-1 B 1 (x) = x n-1 + A 1 (x) (2.11)
and T u 2 = (0, t -n+1 , . . . , t -1 ) T if and only if there exist A 2 (x), B 2 (x) such that

T (x)(u 2 (x) + x n ) + x 2n-1 B 2 (x) = A 2 (x) (2.12) with deg A 1 (x) ≤ n -2 and deg A 2 (x) ≤ n -2.
Thus By applying the extended Euclidean algorithm in p(x) = x n-1 T and p ′ (x) = x 2n-1 until we have deg r l (x) = n -1 and deg r l+1 (x) = n -2 we obtain

u 1 (x) = 1 c 1 s l (x), B 1 (x) = 1 c 1 t l (x), x n-1 + A 1 (x) = 1 c 1 r l (x)
and

x n + u 2 (x) = 1 c 2 s l+1 (x), B 2 (x) = 1 c 2 t l+1 (x), A 2 (x) = 1 c 2 r l+1 (x)
with c 1 and c 2 are the highest coefficients of r l (x) and s l+1 (x) respectively, in fact: The equation (2.11) is equivalent to

n n-1 n -1 n    n -1                 t -
t n-1 1                       u 1 B 1       =            A 1 1 0 . . . 0           
since T is invertible then the (2n -1) × (2n -1) block at the bottom is invertible and then u 1 and B 1 are unique, therefore u 1 , B 1 and A 1 are unique. And, by proposition (2.12), deg

r l = n -1 (r l = c 1 (x n + A 1 (x)) then deg s l+1 = (2n -1) -(n -1) = n and deg t l+1 = (2n -2) -(n -1) = n -1 thus, by the same proposition, deg s l ≤ n -1 and deg t l ≤ n -2. Therfore 1 c1 s l = u 1 and 1 c1 t l = B 1 . Finaly, T u = e 1 if and only if there exist v(x), w(x) such that T (x)u(x) + x n v(x) + (x 2n -1)w(x) = 1 (2.13) T (x) = T + + x 2n T -= T + (x 2n -1)T -thus T (x)u(x) + x n v(x) + (x 2n -1)(w(x) + T -(x)u(x)) = 1 (2.14)
of a other hand T (x)u(x)-x -n+1 A 1 (x)+x n B 1 (x) = 1 and x -n+1 A 1 (x) = x n (xA 1 )-x -n (x 2n -1)xA 1 thus

T (x)u(x) + x n (B(x) -xA(x)) + (x 2n -1)x -n+1 A(x) = 1 (2.15)
By comparing (2.14) and (2.15), and as 1 = x n x n -(x 2n -1) we have the proposition and we have

w(x) = x -n+1 A(x) -T -(x)u(x) + 1 which is the part of positif degree of -T -(x)u(x) + 1.
Remark 2.14. A superfast euclidean gcd algorithm, wich uses no more then O(nlog 2 n), is given in [START_REF] Zur Gathen | Modern computer algebra[END_REF] chapter 11.

The second methode to compute (u 1 , v 1 , w 1 ) and (u 2 , v 2 , w 2 ) is given in [START_REF] Van Barel | A stabilized superfast solver for nonsymmetric Toeplitz systems[END_REF]. We are interested in computing the coefficients of σ 1 , σ 2 , the coefficients of σ 3 correspond to elements in the ideal (x 2n -1) and thus can be obtain by reduction of ( T (x)

x n ).B(x) by x 2n -1, with B(x) = x n -u 0 -v 0 -u 1 x n -v 1 = u(x) v(x) u ′ (x) v ′ (x) .
A superfast algorithm to compute B(x) is given in [START_REF] Van Barel | A stabilized superfast solver for nonsymmetric Toeplitz systems[END_REF]. Let us describe how to compute it. By evaluation of (2.10) at the roots ω j ∈ U 2n we deduce that (u(x) v(x)) T and (u ′ (x) v ′ (x)) T are the solution of the following rational interpolation problem:

T (ω j )u(ω j ) + ω n j v(ω j ) = 0 T (ω j )u ′ (ω j ) + ω n j v ′ (ω j ) = 0 with u n = 1, v n = 0 u ′ n = 0, v ′ n = 1
Definition 2.15. The τ -degree of a vector polynomial w(x) = (w 1 (x) w 2 (x)) T is defined as

τ -deg w(x) := max{deg w 1 (x), deg w 2 (x) -τ } B(x)
is a n-reduced basis of the module of all vector polynomials r(x) ∈ K[x] 2 that satisfy the interpolation conditions f T j r(ω j ) = 0, j = 0, . . . , 2n -1

with f j = T (ω j ) ω n j .
B(x) is called a τ -reduced basis (with τ = n) that corresponds to the interpolation data (ω j , f j ), j = 0, . . . , 2n -1.

Definition 2.16. A set of vector polynomial in K[x] 2 is called τ -reduced if the τ -highest degree coefficients are lineary independent.

Theorem 2.17. Let τ = n. Suppose J is a positive integer. Let σ 1 , . . . , σ J ∈ K and φ 1 , . . . , φ J ∈ K 2 wich are = (0 0) T . Let 1 ≤ j ≤ J and τ J ∈ Z. Suppose that B j (x) ∈ K[x] 2×2 is a τ J -reduced basis matrix with basis vectors having τ J -degree δ 1 and δ 2 , respectively, corresponding to the interpolation data {(σ i , φ i ); i = 1, . . . , j}.

Let τ j→J := δ 1 -δ 2 . Let B j→J (x) be a τ j→J -reduced basis matrix corresponding to the interpolation data {(σ i , B T j (σ j )φ i ); i = j + 1, . . . , J}. Then B J (x) := B j (x)B j→J (x) is a τ J -reduced basis matrix corresponding to the interpolation data {(σ i , φ i ); i = 1, . . . , J}.

Proof. For the proof, see [START_REF] Van Barel | A stabilized superfast solver for nonsymmetric Toeplitz systems[END_REF]. When we apply this theorem for the ω j ∈ U 2n as interpolation points, we obtain a superfast algorithm (O(n log 2 n)) wich compute B(x). [START_REF] Van Barel | A stabilized superfast solver for nonsymmetric Toeplitz systems[END_REF] We consider the two following problems:

3. Bivariate case. Let m ∈ N, m ∈ N.
In this section we denote by

E = {(i, j); 0 ≤ i ≤ m -1, 0 ≤ j ≤ n -1}, and R = K[x, y].
We denote by K[x, y]m n the vector space of bivariate polynomials of degree ≤ m in x and ≤ n in y.

Notation 3.1. For a block matrix M , of block size n and each block is of size m, we will use the following indication :

M = M (i1,i2),(j1,j2) 0≤i1,j1≤m-1 0≤i2,j2≤n-1 = (M αβ ) α,β∈E . (3.1)
(i 2 , j 2 ) gives the block's positions, (i 1 , j 1 ) the position in the blocks. problem 3.2. Given a Toeplitz block Toeplitz matrix T = (t α-β ) α∈E,β∈E ∈ K mn×mn (T = (T αβ ) α,β∈E with T αβ = t α-β ) of size mn and g = (g α ) α∈E ∈ K mn , find u = (u α ) α∈E such that

T u = g (3.2)
Definition 3.3. We define the following polynomials:

• T (x, y) := (i,j)∈E-E t i,j x i y j , • T (x, y) := 2n-1,2m-1 i,j=0
ti,j x i y j with ti,j :=

       t i,j si i < m, j < n t i-2m,j si i ≥ m, j < n t i,j-2n si i < m, j ≥ n t i-2m,j-2n si i ≥ m, i ≥ n , • u(x, y) := (i,j)∈E u i,j x i y j , g(x, y) := (i,j)∈E g i,j x i y j .
3.1. Moving hyperplanes. For any non-zero vector of polynomials a = (a 1 , . . . , a n ) ∈ K[x, y] n , we denote by L(a) the set of vectors (h 1 , . . . , h

n ) ∈ K[x, y] n such that n i=1 a i h i = 0. (3.3) It is a K[x, y]-module of K[x, y] n .
Proposition 3.4. The vector u is solution of (3.2) if and only if there exist h 2 , . . . , h 9 ∈ K[x, y] m-1 n-1 such that (u(x, y), h 2 (x, y), . . . , h 9 (x, y)) belongs to

L( T (x, y), x m , x 2 m -1, y n , x m y n , (x 2 m -1) y n , y 2 n -1, x m (y 2 n -1), (x 2 m -1) (y 2 n -1)). Proof. Let L = {x α1 y α2 , 0 ≤ α 1 ≤ m -1, 0 ≤ α 2 ≤ n -1},
and Π E the projection of R on the vector space generated by L. By [START_REF] Mourrain | Multivariate polynomials, duality, and structured matrices[END_REF], we have

T u = g ⇔ Π E (T (x, y) u(x, y)) = g(x, y) (3.4)
which implies that

T (x, y)u(x, y) = g(x, y) + x m y n A 1 (x, y) + x m y -n A 2 (x, y) + x -m y n A 3 (x, y) + x -m y -n A 4 (x, y) + x m A 5 (x, y) + x -m A 6 (x, y) + y n A 7 (x, y) + y -n A 8 (x, y), (3.5)
where the A i (x, y) are polynomials of degree at most m -1 in x and n -1 in y. Since

ω m = ω -m , υ n = υ -n , T (ω, υ) = T (ω, υ) for ω ∈ U 2 m , υ ∈ U 2 n , we deduce by evaluation at the roots ω ∈ U 2 m , υ ∈ U 2 n that R(x, y) := T (x, y)u(x, y) + x m h 2 (x, y) + y n h 4 (x, y) + x m y n h 5 (x, y) -g(x, y) ∈ (x 2 m -1, y 2 n -1) with h 2 = -(A 5 + A 6 ), h 4 = -(A 7 + A 8 ), h 5 = -(A 1 (x, y) + A 2 (x, y) + A 3 (x, y) + A 4 (x, y)).
By reduction by the polynomials x 2 m -1, y 2 n -1, and as R(x, y) is of degree ≤ 3m -1 in x and ≤ 3n -1 in y, there exist h 3 (x, y), h 6 (x, y), . . . , h 8 (x, y) ∈ K[x, y] m-1 n-1 such that T (x, y)u(x, y) + x m h 2 (x, y) + (x 2m -1)h 3 (x, y) + y n h 4 (x, y) + x m y n h 5 (x, y) + (3.6) (x 2m -1)y n h 6 (x, y) + (y 2n -1)h 7 (x, y) + x m (y 2m -1)h 7 (x, y) + (x 2n -1)(y 2n -1)h 8 (x, y) = g(x, y).

Conversely a solution of (3.6) can be transformed into a solution of (3.5), which ends the proof of the proposition.

In the following, we are going to denote by T the vector T = ( T (x, y), x m , x 2 m -1, y n , x m y n , (x 2 m -1) y n , y 2 n -1, x m (y 2 n -1), (x 2 m -1) (y 2 n -1)).

Proposition 3.5. There is no elements of K[x, y] m-1 n-1 in L(T).

Proof. We consider the map

K[x, y] 9 m-1 n-1 → K[x, y] 3m-1 3n-1 (3.7)
p(x, y) = (p 1 (x, y), . . . , p 9 (x, y)) → T.p (3.8) (3.9) which 9mn × 9mn matrix is of the form

S :=                  T 0 E 21 -E
E 1n E 2n -E 1n + E 3n                  (3.10)
with E ij is the 3m × mn matrix e ij ⊗ I m and e ij is the 3 × n matrix with entries equal zero except the (i, j)th entrie equal 1. And the matrix

  T 0 T 1 T 2   is the following 9mn × m matrix                          t 0 0 . . . 0
0 . . . . . . 0                         
For the same reasons in the proof of proposition (2.6) the matrix S is invertible. Theorem 3.6. For any non-zero vector of polynomials a = (a i ) i=1,...,n ∈ K[x, y] n , the K[x, y]module L(a 1 , . . . , a n ) is free of rank n -1.

Proof. Consider first the case where a i are monomials. a i = x αi y βi that are sorted in lexicographic order such that x < y, a 1 being the biggest and a n the smallest. Then the module of syzygies of a is generated by the S-polynomials:

S(a i , a j ) = lcm(a i , a j )( σ i a i - σ j a j ),
where (σ i ) i=1,...,n is the canonical basis of K[x, y] n [START_REF] Eisenbud | Commutative algebra[END_REF]. We easily check that S(a i , a k ) = lcm(ai,a k ) lcm(ai,aj ) S(a i , a j )lcm(ai,a k ) lcm(aj ,a k ) S(a j , a k ) if i = j = k and lcm(a i , a j ) divides lcm(a i , a k ). Therefore L(a) is generated by the S(a i , a j ) which are minimal for the division, that is, by S(a i , a i+1 ) (for i = 1, . . . , n -1), since the monomials a i are sorted lexicographically. As the syzygies S(a i , a i+1 ) involve the basis elements σ i , σ i+1 , they are linearly independent over K[x, y], which shows that L(a) is a free module of rank n -1 and that we have the following resolution:

0 → K[x, y] n-1 → K[x, y] n → (a) → 0.
Suppose now that a i are general polynomials ∈ K[x, y] and let us compute a Gröbner basis of a i , for a monomial ordering refining the degree [START_REF] Eisenbud | Commutative algebra[END_REF]. We denote by m 1 , . . . , m s the leading terms of the polynomials in this Gröbner basis, sorted by lexicographic order.

The previous construction yields a resolution of (m 1 , . . ., m s ):

0 → K[x, y] s-1 → K[x, y] s → (m i ) i=1,...,s → 0.
Using [START_REF] Möller | New constructive methods in classical ideal theory[END_REF] (or [START_REF] Eisenbud | Commutative algebra[END_REF]), this resolution can be deformed into a resolution of (a), of the form

0 → K[x, y] p → K[x, y] n → (a) → 0,
which shows that L(a) is also a free module. Its rank p is necessarily equal to n -1, since the alternate sum of the dimensions of the vector spaces of elements of degree ≤ ν in each module of this resolution should be 0, for ν ∈ N.

Generators and reduction.

In this section, we describe an explicit set of generators of L(T). The canonical basis of K[x, y] 9 is denoted by σ 1 , . . . , σ 9 .

First as T (x, y) is of degree ≤ 2 m-1 in x and ≤ 2 n-1 in y and as the function (3.7) in surjective, there exists

u 1 , u 2 ∈ K[x, y] 9 m-1 n-1 such that T • u 1 = T (x, y)x m , T • u 2 = T (x, y)y n . Thus, ρ 1 = x m σ 1 -u 1 ∈ L(T), ρ 2 = y n σ 1 -u 2 ∈ L(T).
We also have u

3 ∈ K[x, y] m-1 n-1 , such that T • u 3 = 1 = x m x m -(x 2 m -1) = y n y n -(y 2 n -1). We deduce that ρ 3 = x m σ 2 -σ 3 -u 3 ∈ L(T), ρ 4 = y n σ 4 -σ 7 -u 3 ∈ L(T).
Finally, we have the obvious relations: . Thus, T (x, y)h 1 +x m h 2 +y n h 4 +x m y n h 5 ∈ (x 2 n -1, y 2 m -1). As this polynomial is of degree ≤ 3 m -1 in x and ≤ 3 n -1 in y, by reduction by the polynomials, we deduce that the coefficients h 3 , h 6 , . . . , h 9 are in K[x, y] m-1 n-1

ρ 5 = y n σ 2 -σ 5 ∈ L(T), ρ 6 = x m σ 4 -σ 5 ∈ L(T), ρ 7 = x m σ 5 -σ 6 + σ 4 ∈ L(T), ρ 8 = y n σ 5 -σ 8 + σ 2 ∈ L(T).
. By proposition 3.5, there is no non-zero syzygy in K[x, y] 9 m-1 n-1

. Thus we have h = 0 and every element of L(T) can be reduced to 0 by the previous relations. In other words, ρ 1 , . . . , ρ 8 is a generating set of the K[x, y]-module L(T). By theorem 3.6, the relations ρ i cannot be dependent over K[x, y] and thus form a basis of L(T).

Interpolation.

Our aim is now to compute efficiently a system of generators of L(T). More precisely, we are interested in computing the coefficients of σ 1 , σ 2 , σ 4 , σ 5 of ρ 1 , ρ 2 , ρ 3 . Let us call B(x, y) the corresponding coefficient matrix, which is of the form: Notice that the other coefficients of the relations ρ 1 , ρ 2 , ρ 3 correspond to elements in the ideal (x 2 m -1, y 2 n -1) and thus can be obtained easily by reduction of the entries of ( T (x, y), x m , y n , x m y n )•B(x, y) by the polynomials x 2 m -1, y 2 n -1.

Notice also that the relation ρ 4 can be easily deduced from ρ 3 , since we have ρ 3x m σ 2 + σ 3 + y n σ 4σ 7 = ρ 4 . Since the other relations ρ i (for i > 4) are explicit and independent of T (x, y), we can easily deduce a basis of L(T) from the matrix B(x, y).

As in L(T)∩K[x, y] m-1 n-1

there is only one element, thus by computing the basis given in proposition which gives us the solution of T u = g. We can give a fast algorithm to do these two step, but a superfast algorithm is not available.

Conclusions.

We show in this paper a correlation between the solution of a Toeplitz system and the syzygies of polynomials. We generalized this way, and we gave a correlation between the solution of a Toeplitz-block-Toeplitz system and the syzygies of bivariate polynomials. In the univariate case we could exploit this correlation to give a superfast resolution algorithm. The generalization of this technique to the bivariate case is not very clear and it remains an important challenge.

Proposition 3 . 7 .

 37 The relations ρ 1 , . . . , ρ 8 form a basis of L(T). Proof. Let h = (h 1 , . . . , h 9 ) ∈ L(T). By reduction by the previous elements of L(T), we can assume that the coefficients h 1 , h 2 , h 4 , h 5 are in K[x, y] m-1 n-1

( 3 . 7 )

 37 and reducing it we can obtain this element in L(T) ∩ K[x, y] m-1 n-1


Kathy Rousselet

Orthodox churches in the war in Ukraine -English version

More than two months ago, Vladimir Putin declared war on Ukraine. On February 21, he recognised the independence of the two separatist Donetsk and Luhansk "people's republics". On February 24, he ordered Russian troops to enter Ukraine to "maintain peace", yet the war has already claimed thousands of lives. The Russian army is bombing the birthplace of Rus' Christianity, the origin of today's Ukraine and Russia. It was in the Rus', that the Grand Prince of Kiev, Vladimir, was baptised in 988.

Much has already been written about the rhetoric surrounding this war. For years it has been fuelled by political and religious circles in Russia who affirm that Ukrainians and Russians are a single people that the West seeks to divide. Even before the canonization of Nicholas II in 2000, nationalist narratives imbued with tsarist nostalgia were intertwining the history of the imperial Russian state with that of the Russian Orthodox Church, and laying them over Soviet representations. The "Russia My History" historical parks in twenty-three towns in Russia, designed by Metropolitan Tikhon Shevkunov, a member of Putin's inner circle, is a flagrant example of this. As for Patriarchs Aleksii II (1929-2008) and Kirill (1946-elected Patriarch on January 27, 2009), they have continued to defend the canonical territory of the Moscow Patriarchate, which was shaken by the collapse of the Soviet Union and the emergence of new nation-states [1] . Since 1991, the church has emphasised the unity of Orthodox Christians of the Rus', beyond political borders. Kirill has constantly sought to increase the power of his church.

The idea of "Russian world", which appears to be one of the foundations of this tragic war, has been understood in various ways since the 1990s, initially within groups distant from the church. Such ideas circulated between Russian religious, political, military, scientific, and cultural elites, particularly within the World Russian People's Council [2] , created in 1993 by Kirill who was then head of the Department for External Church Relations of the Moscow Patriarchate. In the early 2000s, Kirill wrote several texts opposing unipolarity in international relations, and the globalisation of liberal values. He defended the idea of a cohabitation of civilisations, inspired by but distinct from Samuel Huntington's "Clash of Civilisations" thesis. In 2007, he discussed and defended the Russian Doctrine, within the World Russian People's Council, developed by a group of conservative thinkers who defended the restoration of empire. Chapter 6 of the third part of this Doctrine concerns national military doctrine and states:

"The goal of the new Russian empire is to prevent a unipolar world (American or Chinese hegemony), to defend its independence, protect its spheres of vital interest (at least within URSS borders) and to advocate for the recreation of an empire [3] ."

Among those who contributed to this text was Aleksandr Borodai, who was prime minister of the self-proclaimed republic of Donetsk between May 16 and August 7, 2014.

Kirill, who became Patriarch in 2009, has nevertheless always denied that he considers the "Russian world" a political project. He has always promoted the civilisational approach, presenting it in opposition to the de-Christianised decadence of the West. After the conservative turn in 2012, this rhetoric would become increasingly present in Russian political space. The definition of the Russian world and Russian civilisation would be constantly debated within traditionalist factions of the church. More than once, Kirill confused Rus' with Russia, for example during his speech at the World Russian People's Council in 2013, dedicated to Russia as a "state-civilisation".

Alongside this, an eschatological religious rhetoric developed, situating Holy Russia, also descending from the Rus', within salvation history. In 2009, Kirill described the Russian people as "bearing God," baptised in Kiev, and fed on a tradition of a multitude of saints (hierarchical, boyars, princes, priests, monks, laymen), a particular lifestyle, and "spiritual" values. These saints "taught our people to love God and their neighbours, to fear sin and evil, and aspire to good, holiness, and truth [4] ", he added. The idea of a people "bearing God" can be traced back at least to the 19 th century and Dostoevsky. It refers to a suffering people, who are abandoned by all, and who are attached through history to Christ himself [5] .

As for Ukraine, it progressively chose its own political path, but also its religious one. Alongside the Ukrainian Orthodox Church, which is dependent on Moscow, self-proclaimed autocephalous churches (re)emerged at the end of the 1980s and the beginning of the 1990s. Part of the Ukrainian Orthodox Church begged Moscow to grant it autocephaly, but in vain. Finally, in autumn of 2018, the Orthodox Church of Ukraine was created with support from the Ukrainian president of the time, Petro Poroshenko, and the status of autocephaly was granted by the Constantinople Patriarch. This religious conflict also revealed memorial divergences and provoked major upheavals in the Communion of Orthodox Churches, with some siding with Moscow, and others following Constantinople [6] . Its repercussions reverberated across Europe and now into Africa. The new Orthodox Church of Ukraine, led by the Metropolitan Epiphanius, saw the number of members increase, to the detriment of the Ukrainian Orthodox Church (Moscow Patriarchate), which has been led by the Metropolitan Onufrii since 2014. According to the Razumkov Centre, in November 2021, 24.1% of Ukrainians and 39.8% of those who say they are Orthodox belonged to the Ukrainian Orthodox Church (Moscow Patriarchate). A law passed by the Ukrainian parliament in 2018 obliges this church to explicitly mention in its name that it belongs to the Russian Orthodox Church. The hierarchs of this church have constantly criticised the law as unconstitutional. In December last year, they still collected signatures of support from within the church, but also from among Polish and Serbian Orthodox churches. In his speech on February 21, Vladimir Putin mentioned, among his grievances against the Ukrainian state, its alleged support for the "schism" that now divides the Ukrainian people. He mentioned the discrimination the Ukrainian Orthodox Church (Moscow Patriarchate) is allegedly subject to. The "schism" is considered an integral part of the political conflict.

The position of Patriarch Kirill is the same as that of the President of the Russian Federation. In 2019, he declared: "We must not allow our enemies to divide the people, a single Orthodox people of united Holy Russia. And this is not a geopolitical task, nor an imperial idea that comes from Moscow -it is a spiritual idea. Because our unity in spirit and truth, our unity in the Orthodox Church is the most important factor that influences the destiny of Europe and, in a sense, the destiny of the world. We cannot allow ourselves to be divided on the most important point in our faith, in our understanding of the objectives and the tasks our Slavic world is confronted with [7] ."

He considered the recognition of the independence of the Orthodox Church of Ukraine by Patriarch Bartholomew I (Constantinople) to be due to the influence of the United States. During a press conference on January 14 2022, the Minister for Foreign Affairs Sergei Lavrov explained that the United States played a "direct role in the current orthodoxy crisis".

As though echoing these statements, on January 18 Kirill referred to external forces totally unconnected from the church, which could provoke a schism within global orthodoxy [8] . Although his speech on February 24 advocated avoiding civilian casualties in the Ukraine conflict, that of February 27 was once again marked by anti-Western rhetoric, describing the "forces of evil who have always fought against the unity of Rus' and the Russian Church". On March 3, a circular within the Patriarchate called for prayers for peace. They also prayed for the downfall of foreign plans against Holy Russia. On Forgiveness Sunday, Kirill considered that the conflict had a "metaphysical" component, and clearly presented the war as eschatological, a war against the "values that are promoted by those who claim world power", and against the "sin that the so called pride marches propagandize [9] ". With this expression, which shocked observers across the board, he transformed this conflict into a "cosmic war" to use the expression of Mark Juergensmeyer, i.e an imaginary battle between good and evil transcending the political conflict. Yet he did not deny the political nature of the war. In a letter on March 10, Patriarch Kirill of Moscow and all Russia responded to a letter sent on March 2 by the acting general secretary of the World Council of Churches (WCC) Rev. Prof. Dr Ioan Sauca, and explained that the origins of the war lay in NATO's pressure on Russia's borders and "the attempt (of political forces) to "re-educate," to mentally transform Ukrainians and Russians living in Ukraine into enemies of Russia [10] ."

Within Ukraine, Onufrii tried to keep his distance from politics, defending the autonomy and Ukrainian nature of his church, while also displaying his loyalty to the Moscow Patriarch. He has never subscribed to the rhetoric of the "Russian world", which seemed like an obstacle to the very existence of his church in Ukraine. In 2015, he considered the conflict in the Donbass a civil war [11] -a controversial term in Ukraine -with priests and bishops from his church on both sides. According to a sociological study published in 2014, only 30% of the Orthodox clergy defended a pro-Russian position [12] . Onufrii did not participate in the religious ceremony of February 16 at the Saint Sophia Cathedral in Kiev where religious leaders prayed for the protection of Ukraine against the threat of Russian invasion; he sent a representative. But on February 22, in keeping with his pronouncements after the annexation of Crimea [13] , he declared that the Ukrainian Orthodox Church would always defend the territorial integrity of the country. He begged "state leaders, and all those in power, to not allow another war… a great sin in the eyes of God [14] ." On February 24, he addressed Vladimir Putin directly, reiterating these comments and describing the war as the "repetition of Cain's sin in killing his brother." He restated that his church would always side with its people and that it would continue to defend the sovereignty and integrity of Ukraine. On February 28, the Synod of this church exhorted Patriarch Kirill to come out against this fratricidal war and ask Vladimir Putin to call off the assault. On March 3, it was the Holy Dormition of Pochayiv Lavra, the second largest monastery in Ukraine that asked Kirill to beg Russian power to stop the war. Faced with the fact that the Patriarch Kirill had not explicitly condemned the war, many priests from the Ukrainian Orthodox Church, including at the Holy Dormition Kyiv-Pechersk Lavra (the Caves Monastery), decided to no longer mention Kirill in their prayers [15] . An increasing number of eparchies now openly say they have stopped praying for him. The Moscow Patriarch accuses them of taking schismatic positions.

It is difficult to know how many of these religious leaders have left the Ukrainian Orthodox Church for the Orthodox Church of Ukraine. Certain sources claim that at least some of those who no longer mention Kirill in their prayers nevertheless wish to remain in their church, which they consider the only one canonically valid, and express their support for Metropolitan Onufrii. In several eparchies, including Lviv, priests have asked for autocephaly for the Ukrainian Orthodox Church. Voices have called for these priests to join the Orthodox Church of Ukraine. Other priests have asked that Kirill be tried by a synaxis of Primates from local Orthodox churches, and that he be removed from the throne of the patriarchate. At the same time, the Ukrainian Church fears for its very existence in Ukraine, given that a bill aiming to outlaw its activities within Ukrainian territory was brought before the Ukrainian parliament at the end of March.

For the Orthodox Church of Ukraine, it has been unreservedly committed to defending Ukrainian territory. On January 25, Metropolitan Epiphanius asked the Ukrainian people to unite in the face of aggression from the Russian Federation, and to defend Ukrainian territory. In bellicose tones, he declared that the task of Ukrainians was to "prove to Russian leaders that it is not possible to vanquish Ukraine, that we will fight, that we will defend ourselves, we will defend our native land until victory is ours [16] ." On February 18, in a Facebook post, he gave five pieces of advice on how to overcome fear of the enemy [17] . And on February 22 and 28 he called on the Ukrainian people to defend themselves against the Russian aggressor. On February 27 he also sent a particularly virulent letter to Kirill, accusing him of not condemning the aggression and calling on him to at least help retrieve the bodies of the Russian soldiers who had died for the idea of the "Russian World", promoted by Kirill and Vladimir Putin. On March 2, anticipating the expansion of the war, he asked the Belarusians to do everything possible to avoid their soldiers being sent to die.

Patriarch Kirill supports Vladimir Putin, and draws on his rhetoric [18] . His attitude to this fratricidal war, in which he has already lost much, is a sign of his lack of power to influence the political body in Russia and his weakness. In Russia any counter powers have now been abolished. Orthodox religion is only legitimate in that it feeds the "spiritual and moral values" authorised by Russian authorities. The Bases of the Social Concept of the Russian Orthodox Church, written under Kirill's supervision and adopted in 2000, foresees the possibility of acts of civil disobedience by the church:

The Church remains loyal to the state, but God's commandment to fulfil the task of salvation in any situation and under any circumstances is above this loyalty. If the authority forces Orthodox believers to apostatise from Christ and His Church and to commit sinful and spiritually harmful actions, the Church should refuse to obey the state. The Christian, following the will of his conscience, can refuse to fulfil the commands of state forcing him into a grave sin. If the Church and her holy authorities find it impossible to obey state laws and orders, after a due consideration of the problem, they may take the following action: enter into direct dialogue with authority on the problem, call upon the people to use the democratic mechanisms to change the legislation or review the authority's decision, apply to international bodies and the world public opinion and appeal to her faithful for peaceful civil disobedience [19] .

Yet Kirill positions his church in the heritage of sovietism, when patriotism, linked to "sergianism" [20] , was the only guarantee of ecclesiastical survival. His homily on April 3rd in the main cathedral of the Russian armed forces is a good illustration of this [21] . Over the course of the 1960s and 70s, the church worked actively in the ecumenical movement, emerging from its isolation to defend the ideological interests of the country. Today, in the context of war, Russian ecclesiastical diplomacy, in the figure of metropolitan Ilarion Alfeiev, head of the Department for External Church Relations, remains intense.

In addition to Soviet patterns, Kirill's attitude can also be explained by the fact that the wealth of the Russian Orthodox Church largely depends on its relationship with the state. Kirill, who has lost all authority among the Russian population [22] , is also in competition with those who are more nationalist than he is. A large number of the hierarchs support Vladimir Putin's policies, some out of an ideological belief that the war is just (relations between the armed forces and ultra-nationalists and traditionalists in the Church are close), and others out of fear. Still others support him out of fear of losing the numerous assets they have gained. Among the most influent hierarchs in the church, only metropolitan Ilarion Alfeiev has indirectly demonstrated his opposition to the war, probably because of his diplomatic activity.

The hierarchs have called for prayers and solidarity with the populations fleeing the bombs. Yet it has become dangerous to condemn the war. A petition against the war began to circulate on March 1, but according to a well-informed source, some of the 300 signatories who included well known priests were called to order by their superiors. This says much about the functioning of the Russian Orthodox Church in which the plurality at the parish level is hampered by vertical ecclesiastical power established by Patriarch Kirill. Others have dared to condemn the war during their homilies and been denounced by their parishioners; some are removed from parish responsibilities or choose to leave themselves. Others have lost the economic support of their patrons. Western parishes belonging to the Russian Orthodox Church, which include as many Ukrainians as Russians, are fraught with tension. Some believers in Russia or elsewhere express their disquiet on social media, while others continue to obey their spiritual guide whatever his position. Some have raised the question of the collective responsibility of the Russian people and of repentance. Orthodox theologians, including some Russian theologians, have taken a stance against the "Russian world" by presenting it as ecclesiastic nationalism and therefore heresy. More specifically, it is the close relationship between the state and the national church seen throughout the orthodox world that have been thrown into question. Finally, it is the integrity of the Russian Orthodox Church itself that is now in question, if we believe the comments of metropolitan Ilarion in the introduction to the 4 th issue of the Journal of the Moscow Patriarchate:

What side should believers be on? This is a question that is both simple and complex. We must understand that today, in a situation of great division within society, our faith is challenged. The unity of the church in particular requires a deep understanding of the meaning of its hierarchical structure. In the difficult periods of the 20th century, it was through the unity of the episcopate and the faithful that the Russian church survived. "Where there is no bishop there is no church": these words of the holy martyr Ignatius Theophorus were spoken nearly 2000 years ago but they still very clearly define the meaning and vocation of the bishop. Loyalty towards the bishop and more generally towards the Holy Patriarch is an important factor in preserving the integrity of our church [23] .

The Synod of Bishops scheduled to be held in Moscow at the end of May has been postponed. ↑2 For an analysis of recent developments related to this organisation see J. Faure, « Konstantin Malofeev veut tr Conseil mondial du peuple russe en assemblée "constituante", Observatoire international du fait religieux, bul september 2019, https://www.sciencespo.fr/ceri/fr/oir/konstantin-malofeev-veut-transformer-le-conseil-mon peuple-russe-en-assemblee-constituant

(

  English version completed May 6 2022 ; Translated from the French by Katharine Throssell) Notes Notes ↑1 See also K. Rousselet, « L'Eglise orthodoxe russe et la question des frontières. Sainte Russie, monde russe et te canonique, » Les Etudes du CERI, 2, 2017, pp. 49-53, https://spire.sciencespo.fr/hdl:/2441/6gbpjqstm482cp9ri3qbabd8pg/resources/rousselet-etude-228-229.p