Grégory Mendousse

SPECIAL FUNCTIONS ASSOCIATED WITH K-TYPES OF DEGENERATE PRINCIPAL SERIES OF Sp(n, C)

Keywords: Primary 22E46, Secondary 33C10, 33C55, 43A75 principal series representations, reductive Lie groups, K-types, non-standard model, special functions

We study K-types of degenerate principal series of Sp(n, C) by using two realisations of these infinite-dimensional representations. The first model we use is the classical compact picture; the second model is conjugate to the non-compact picture via an appropriate partial Fourier transform. In the first case we find a family of K-finite vectors that can be expressed as solutions of specific hypergeometric differential equations; the second case leads to a family of K-finite vectors whose expressions involve Bessel functions.

Introduction

Special functions play a prominent role in mathematics and physics. They are solutions of important equations and come in various forms, in terms of series or integrals. We are interested in the way special functions connect to representation theory. That such a connection exists is well known. Special functions appear in the study of spherical functions (see e.g. [START_REF] Helgason | Groups and geometric analysis -Integral geometry, invariant differential operators and spherical functions[END_REF], Chapter IV), of matrix coefficients of representations (see e.g. [START_REF] Klimyk | Representations of Lie groups and special functions -Volume 1: simplest Lie groups, special functions and integral transforms[END_REF], Section 4.1) and of symmetry breaking operators (see [START_REF] Kobayashi | Conformal symmetry breaking operators for differential forms on spheres[END_REF] and [START_REF] Kobayashi | Differential symmetry breaking operators -I. General theory and F-method[END_REF]). In this work, we focus on the K-types of degenerate principle series of Sp(n, C), looking for K-finite vectors that have explicit formulas in terms of special functions. Here, K refers to Sp(n).

The reason why we choose to work with degenerate principle series of Sp(n, C) is twofold.

First, the geometric setting we choose is motivated by the following sequence of groups of isometries of vector spaces over different number fields:

Sp(n) ⊂ SU (2n)
⊂ SO(4n)

H n C 2n R 4n .
1

This sequence enables us to use a refined version of the classical theory of spherical harmonics. Moreover, the non-commutativity of the skew field H of quaternions adds a rich ingredient to the underlying representation theory and harmonic analysis: see for example [START_REF] Howe | Homogeneous functions on light cones: the infinitesimal structure of some degenerate principal series representations[END_REF], [START_REF] Kobayashi | Singular unitary representations and discrete series for indefinite Stiefel manifolds U(p, q; F)/ U[END_REF], [START_REF] Pasquale | Maximal degenerate representations of SL(n+1, H)[END_REF] and the very recent paper [START_REF] Schlichtkrull | Laplacians on spheres[END_REF].

Second, the degenerate principal series representations of the complex symplectic Lie group Sp(n, C) are "small" in the sense of the Kirillov-Gelfand dimension(see e.g. [START_REF] Vogan | The size of infinite-dimensional representations[END_REF]) amongst infinite-dimensional unitary representations of Sp(n, C). According to the guiding principle "small representation of a group = large symmetries in a representation space" suggested by T. Kobayashi in [START_REF] Kobayashi | Varna lecture on L 2 -analysis of minimal representations, Lie theory and its applications in physics[END_REF], explicit models of such representations are a natural source of information on special functions that arise in this framework as specific vectors. This philosophy has been applied to the analysis of minimal representations of O(p, q) (see [START_REF] Kobayashi | The Schrödinger model for the minimal representation of the indefinite orthogonal group O(p, q)[END_REF] and [START_REF] Kobayashi | Analysis on the minimal representation of O(p, q) -III. Ultrahyperbolic equations on R p-1,q-1[END_REF]) and small principal series representations of the real symplectic group Sp(n, R) (see [START_REF] Kobayashi | Geometric analysis on small unitary representations of GL(n, R)[END_REF]). Here, H 2m+1 C refers to the (2m + 1)-dimensional complex Heisenberg group. We denote the U(1) component of an element m of M by e iθ (m) and the positive real scalar that corresponds to an element a of A by α(a). Now consider for (λ, δ) ∈ R × Z the character χ iλ,δ defined on Q by: χ iλ,δ (man) = e iθ(m) δ α(a)

iλ .

The corresponding induced representation π iλ,δ = Ind G Q χ iλ,δ can be realised on the completion V iλ,δ of the complex vector space

V 0 iλ,δ = f ∈ C 0 C 2n \{0} ∀c ∈ C \{0} : f (c •) = c |c| -δ |c| -iλ-2n f (•)
with respect to the L 2 -norm on S 4n-1 .

Representations π iλ,δ form a degenerate principal series of G. It is proved in [START_REF] Gross | The dual of a parabolic subgroup and a degenerate principal series of Sp(n, C)[END_REF] that π iλ,δ is irreducible if (λ, δ) = (0, 0) and in [START_REF] Clare | On the degenerate principal series of complex symplectic groups[END_REF] that π 0,0 decomposes into a sum of two irreducible subrepresentations. The isotypic decomposition of π iλ,δ K is multiplicity free and given by (see [START_REF] Clare | On the degenerate principal series of complex symplectic groups[END_REF] and [START_REF] Howe | Homogeneous functions on light cones: the infinitesimal structure of some degenerate principal series representations[END_REF]):

(1) π iλ,δ K ⊕ l-l ≥|δ| l-l ≡δ [START_REF] Erdélyi | Higher transcendental functions[END_REF] π l,l .

In this sum, l and l are integers such that l ≥ l ≥ 0 and π l,l is the irreducible representation of K whose highest weight is (l, l , 0, • • • , 0); we denote the irreducible invariant subspace of V iλ,δ (with respect to the left action of K) that corresponds to π l,l by V l,l , calling it a component of V iλ,δ .

Our aim is to describe specific elements of components V l,l in terms of special functions. This will require suitable changes of the carrying space V iλ,δ (together with the action of G) so as to have a clearer view of π iλ,δ , depending on the kind of special functions we have in mind; each point of view is called a picture of π iλ,δ (above definition is the induced picture).

This paper is organised as follows:

• Section 2: in the compact picture, we study the K-type structure, by which we mean the detailed description of the components of V iλ,δ and connections that exist between them (Propositions 2.1, 2.2 and 2.3). • Section 3: we consider the case l = l and use, again in the compact picture, invariance properties with respect to Sp(1) and 1 × Sp(n -1) to exhibit in components V l,l elements which can be seen as solutions of hypergeometric differential equations (Theorem 3.1). • Section 4: we define the non-standard picture of π iλ,δ (which was introduced in [START_REF] Kobayashi | Geometric analysis on small unitary representations of GL(n, R)[END_REF] and followed in [START_REF] Clare | On the degenerate principal series of complex symplectic groups[END_REF]) by applying a certain partial Fourier transform F to the non-compact picture. For a wide class of components, namely components V l,0 (said otherwise, those components such that l = 0), this leads to elements that can be expressed in terms of modified Bessel functions (Theorem 4.1).

Let us put together our most important results:

Theorem (Main results).

Let n ∈ N be such that n ≥ 2 and set m = n -1.

Consider the group G = Sp(n, C), its maximal compact subgroup Sp(n) and the parabolic subgroup (1) For l ∈ N, consider the K-type π l,l . The corresponding subspace V l,l of V iλ,δ contains an element which can be seen as a function of a single variable τ ∈ [0, 1] and the restriction ϕ of this function to ]0, 1[ satisfies the following hypergeometric equation:

Q = M AN U(1)×Sp(m, C)×R × + ×H 2m+1 C . Consider a pair (λ, δ) ∈ R × Z,
τ (1 -τ )ϕ (τ ) + 2(1 -nτ ) ϕ (τ ) + l(l + 2n -1) ϕ(τ ) = 0.
(2) For (l, α, β) ∈ N 3 such that l = α+β and δ = β-α, consider the K-type π l,0 of π iλ,δ . Then, in the non-standard picture, highest weight vectors of π l,0 are proportionnal to a function

ψ : C × C m × C m -→ C whose expression for s = 0 and v = 0 is ψ(s, u, v) = R(s, u, v) Kiλ+δ 2 π 1 + u 2 |s| 2 + 4 v 2
where we set

R(s, u, v) = (-is) α π iλ+β+n 2 iλ+l 2 +1 Γ iλ+l 2 + n   |s| 2 + 4 v 2 π 1 + u 2   iλ+δ 2
and where Kiλ+δ

denotes a modified Bessel function of the third kind (see appendix for definition).

Before we enter the details, let us motivate the use of partial Fourier transforms. For one thing, they have proved useful in the study of Knapp-Stein operators (see [START_REF] Clare | On the degenerate principal series of complex symplectic groups[END_REF], [START_REF] Kobayashi | Geometric analysis on small unitary representations of GL(n, R)[END_REF], [START_REF] Pevzner | Projective pseudo-differential analysis and harmonic analysis[END_REF] and [START_REF] Unterberger | Automorphic pseudodifferential analysis and higher level Weyl calculi[END_REF]). For another, partial Fourier transforms with respect to appropriate Lagrangian subspaces modify the nature of constraints imposed on specific vectors in representation spaces and have been used to find explicit formulas for K-finite vectors in [START_REF] Kobayashi | The Schrödinger model for the minimal representation of the indefinite orthogonal group O(p, q)[END_REF], [START_REF] Kobayashi | Analysis on the minimal representation of O(p, q) -III. Ultrahyperbolic equations on R p-1,q-1[END_REF], and [START_REF] Kobayashi | Geometric analysis on small unitary representations of GL(n, R)[END_REF]. These works establish formulas that involve Bessel functions. This has lead us to apply similar techniques to degenerate principal series of Sp(n, C).

K-type structure

We investiqate the K-type structure of the degenerate principal series

π iλ,δ = Ind G Q χ iλ,δ of Sp(n, C).

Compact picture and general facts.

Let us fix (λ, δ) ∈ R × Z. In the compact picture (see [START_REF] Knapp | Representation theory of semisimple groups -An overview based on examples[END_REF], Chapter VII), the carrying space of π iλ,δ is a subspace of L 2 (G). The natural action of G on C 2n enables one to identify it with the following Hilbert space:

L 2 δ (S 4n-1 ) = f ∈ L 2 (S 4n-1 ) ∀θ ∈ R : f (e iθ •) = e -iδθ f (•) .
The compact picture is the ideal setting to look for irreducible invariant subspaces with respect to the left action of K, because one can benefit from decompositions given by standard harmonic analysis (see e.g. Chapter 9 of [START_REF] Faraut | Analysis on Lie groups: an introduction[END_REF], Chapters IV and V of [START_REF] Knapp | Lie groups beyond an introduction[END_REF] and Chapters 9 and 11 of [START_REF] Klimyk | Representations of Lie groups and special functions -Volume 2: class I representations, special functions and integral transforms[END_REF]).

Denote by H k the complex vector space of polynomial functions f on R 4n that are harmonic and homogeneous of degree k. Let us write Y k = H k S 4n-1 (elements of Y k are called spherical harmonics). Then: • each Y k is invariant under the left action of SO(4n) (this is also true for each H k ); • the representations defined by the left action of SO(4n) on the various spaces Y k are irreducible and pairwise inequivalent;

• L 2 S 4n-1 = k∈N Y k . Consider the identification (x, y) ∈ R 2n × R 2n ←→ z = x + iy ∈ C 2n .
Then:

• functions of the variables x and y (in particular elements of the spaces H k ) can be regarded as functions of the variables z and z; • matrices A + iB of GL(2n, C) (resp. SU(2n)), where A and B denote 2n × 2n real matrices, can be regarded as matrices A -B B A of GL(4n, R) (resp. SO(4n));

• accordingly, the left action L of SU(2n) on functions of z and z is defined by

L(u)f (z, z) = f (u -1 z, u -1 z) = f (u -1 z, t uz).
The Laplace operator can be written ∆ = 4

2n i=1 ∂ 2 ∂z i ∂ zi . For α, β ∈ N,
consider the space H α,β of polynomial functions f of the variables z and z such that f is homogeneous of degree α in z and degree β in z and such that ∆f = 0. Let us write Y α,β = H α,β S 4n-1 . Then: • each Y α,β is invariant under the left action of SU(2n) (this is also true for each H α,β ); • the representations defined by the left action of SU(2n) on the various spaces Y α,β are irreducible and pairwise inequivalent;

• Y k = (α,β)∈N 2 α+β=k Y α,β .
This leads to the Hilbert sum L 2 δ (S 4n-1 ) =

(α,β)∈N 2 δ=β-α
Y α,β . We see that, in order to describe the isotypic decomposition of π iλ,δ K , we need to understand how each Y α,β breaks into irreducible invariant subspaces under the left action of K.

From now on, we consider 3-tuples (k, α, β) ∈ N 3 such that α + β = k and denote by L the left action of K, be it on H k , Y k , H α,β or Y α,β .

Left action of Sp(n).

Recall that the Lie algebra sp(n, C) of G is

g = X = A C B -t A ∈ M(2n, C) / B and C are symmetric
and that the Lie algebra sp(n

) of K is k = X = A -B B A ∈ M(2n, C) / A is skew and B is symmetric .
Consider the complexification g = k⊕ik of k. Let h be the usual Cartan subalgebra of g consisting of diagonal elements of g. If r belongs to {1, ..., n}, denote by L r the linear form that assigns to an element of h its r th diagonal term.

The set ∆ of roots of g (with respect to h) consists of the following linear forms:

• L r -L s and -L r + L s (1 ≤ r < s ≤ n); • L r + L s and -L r -L s (1 ≤ r < s ≤ n); • 2L r and -2L r (1 ≤ r ≤ n).
The corresponding root spaces are respectively generated by:

• U + r,s = E r,s -E n+s,n+r and U - r,s = E s,r -E n+r,n+s ; • V + r,s = E r,n+s + E s,n+r and V - r,s = E n+s,r + E n+r,s ; • D + r = E r,n+r and D - r = E n+r,r . Here, E r,s denotes the elementary 2n × 2n matrix whose coefficients are all 0 except for the one that sits in line r and column s and which is taken to be 1. The set of positive roots is

∆ + = {L r -L s , L r + L s } 1≤r<s≤n ∪ {2L r } 1≤r≤n
and the corresponding root spaces are those generated by the various matrices U + r,s , V + r,s and D + r . Remark. Restriction to the unit sphere S 4n-1 intertwines the left action of SO(4n) on H k (resp. of SU(2n) on H α,β ) and the left action of SO(4n) on Y k (resp. of SU(2n) on Y α,β ). It is therefore equivalent for us to study the left action L of K on polynomials of H k (resp. H α,β ) or on functions of Y k (resp. Y α,β ); for convenience, we will work with polynomials.

The infinitesimal action of K is defined for P ∈ H α,β and X ∈ k by:

dL(X)(P )(z, z) = d dt t=0 P exp(-tX)z, t exp(tX) z .
This formula can be written:

(

2) dL(X)(P )(z, z) = ∂P ∂z (z, z) ∂P ∂ z (z, z) -Xz t X z .
Extend the infinitesimal action dL to g: this complexification is also defined by Formula ( 2), but this time with X ∈ g.

To make polynomial calculations clearer, from now on we change our system of notation for complex variables. Throughout the rest of this paper, we denote by (z 1 , ..., z n , w 1 , ..., w n ) the coordinates of C 2n , or simply by (z, w), in which case it is understood that z = (z 1 , ..., z n ) and w = (w 1 , ..., w n ).

Proposition 2.1. Let (k, α, β) ∈ N 3 be such that k = α + β and consider the left action of K on H α,β . Given any integer γ ∈ [0, min(α, β)], the polynomial

P α,β γ (z, w, z, w) = w α-γ 1 z1 β-γ (w 2 z1 -w 1 z2 ) γ
is a highest weight vector whose highest weight is the linear form

σ k γ = (k -γ)L 1 + γL 2 . Refering to the basis {L 1 , • • • , L n } of h * ,
we will write:

σ k γ = (k -γ, γ, 0, • • • , 0
). We shall denote by V α,β γ the corresponding irreducible invariant subspace of H α,β . One then has:

H α,β = min(α,β) γ=0 V α,β γ .
Proof: Straightforward calculations, using (2), show that P α,β γ is indeed a highest weight vector whose highest weight is σ k γ . Applying Weyl's dimension formula to the highest weight σ k γ , one can check the standard formula for the dimension d k γ of V α,β γ :

d k γ = (k -γ + 2n -2)! (γ + 2n -3)! (k -2γ + 1) (k + 2n -1) (k -γ + 1)! γ! (2n -1)! (2n -3)! .
One can then show by induction that the sum of these dimensions matches the dimension of H α,β , which finishes the proof (due to the Peter-Weyl theorem).

End of proof.

Remark. we have re-established the isotypic decomposition [START_REF] Clare | On the degenerate principal series of complex symplectic groups[END_REF], by identifying the highest weights (l, l , 0, • • • , 0) of ( 1) with the highest weights

(k -γ, γ, 0, • • • , 0) of Proposition 2.1.

Right action of Sp(1).

An interesting relation exists between the various K-types, one that corresponds to a scalar type multiplication by elements of Sp(1) which is inspired by the following decompositions:

L 2 (S 4n-1 ) = L 2 even (S 4n-1 ) ⊕ L 2 odd (S 4n-1 ) L 2 (S 4n-1 ) = δ∈Z L 2 δ (S 4n-1 ).
Above summands are invariant under scalar multiplication of coordinates by unit numbers of respectively R and C; the parameters even/odd and δ correspond to the characters of respectively O(1) and U(1). So two actions seem to rule the decomposition of L 2 (S 4n-1 ): left action of matrices and scalar multiplication by unit numbers. This diagram captures the situation:

O(4n) L 2 (S 4n-1 ) O(1) U(2n) L 2 (S 4n-1 ) U (1).
One would like to add the line

Sp(n) L 2 (S 4n-1 ) Sp (1).
This suggests an interaction between the left action of Sp(n) and a scalar-type action of the group Sp(1).

This action of Sp( 1) is best understood in the quaternionic setting. In this work, quaternions q are written q = a + jb, with (a, b) ∈ C 2 and j 2 = -1. The modulus of a quaternion q is |q| = |a| 2 + |b| 2 and we say that q is a unit quaternion if |q| = 1. The field H of quaternions is not abelian, because of the multiplication rule jz = zj (z ∈ C).

The vector space H n can be seen as a left or right vector space; we choose to regard it as a right one. We find this choice convenient because applying matrices on the left of column vectors commutes with scalar multiplication of coordinates on the right. Vectors h ∈ H n will be written

h = z + jw, with (z, w) ∈ C n × C n ; the norm of such a vector h is then h = z 2 + w 2 .
Objects in the quaternionic setting can be read in the complex setting:

• functions of the variable h ∈ H n can be regarded as functions of the variables z and w; • matrices A + jB of GL(n, H), where A and B denote n × n complex matrices, can be regarded as matrices A -B B A of GL(2n, C). In particular:

the group of linear isometries of H n identifies with Sp(n);

the group of unit quaternions q = a + jb identifies with the group of 2 × 2 complex matrices a -b b a such that

|a| 2 + |b| 2 = 1, that is, the group Sp(1).
The rules of quaternionic multiplication imply, given h = z + jw ∈ H n and q = a + jb ∈ H:

hq = (az -bw) + j(aw + bz).
One can transfer this multiplication to the complex setting. This is what motivates the way we define the right action of Sp(1) on functions:

Definition (Right
R(q)f (z, w) = f (az -bw, aw + bz)
for all q, f, (z, w) ∈ Sp(1) × F × S.

Remark. Action R preserves the space of homogeneous polynomials of degree k;

what follows shows that it preserves the subspace H k .

On the Lie algebra level, by definition:

(3) dR(X)P (z, w) = d dt t=0 R (exp(tX)) P (z, w)

where we take P ∈ H k , X ∈ sp(1) and (z, w) ∈ C n × C n . One extends dR to the complexification sl(2, C) of sp(1) by setting for Z ∈ sl(2, C):

(4) dR(Z) = dR(X) + i dR(Y )
with X and Y in sp(1) and Z = X + iY . Let us consider the complex basis of sl(2, C) that consists of the following matrices:

H = 1 0 0 -1 E = 0 1 0 0 F = 0 0 1 0 . Proposition 2.2. For (α, β, γ) ∈ N 3 such that γ ≤ min(α, β): • dR(H)P α,β γ = (α -β) P α,β γ . • dR(E)P α,β γ = (β -γ) P α+1,β-1 γ if γ < β, 0 if γ = β. • dR(F )P α,β γ = (α -γ) P α-1,β+1 γ if γ < α, 0 if γ = α. Consequently, given (k, γ) ∈ N 2 such that γ ≤ E k 2 (
denoting by E the function that assigns to a real number its integer part), P k-γ,γ γ is a highest weight vector of R whose highest weight is k -2γ.

Proof:

Define the following elements of sp(1):

X = i 0 0 -i Y = 0 i i 0 Z = 0 -1 1 0 .
Write:

H = 0 + i(-X) E = -Z 2 + i -Y 2 F = Z 2 + i -Y 2 .
One then applies ( 3) and ( 4) to obtain the desired formulas. End of proof.

K-type diagram.

V k γ = k-γ α=γ V α,k-α γ .
• A vertical set of thick black dots defines a basis of an irreducible invariant subspace W k γ under the right action of Sp(1):

W k γ = Vect C {P α,k-α γ } α=γ,...,k-γ ⊂ V γ .
• Because the left action of Sp(n) and the right action of Sp(1) commute, applying L to W k γ gives irreducible invariant subspaces of R contained in V k γ ; these subspaces define subrepresentations of R which are equivalent to the restriction of R to W k γ . Using the fact that the left action L of Sp(n) is transitive in each component, we obtain: Proposition 2.3. The isotypic decomposition of the right action R of Sp(1) on the vector space H k is:

R H k ⊕ 0≤γ≤E( k 2 ) d k γ R W k γ .
We see that the multiplicity of R

W k γ is the dimension d k γ of V k-γ,γ γ
(given in the proof of Proposition 2.1).

Remark. The structure of H k , which we have described with respect to the left action of Sp(n) and the right action of Sp(1), appears in

H k Sp(n)×Sp(1) = E( k 2 ) γ=0 V k-γ,γ γ ⊗ W k γ .
Remark. Restriction to the unit sphere intertwines the right action of Sp(1) on H k and the right action of Sp(1) on Y k . Thus the structure of H k shown in Figure 1 is also the structure of Y k under the right action of Sp(1).

Compact picture and hypergeometric equations

The idea here is to consider eigenfunctions of the Casimir operator.

We choose eigenfunctions that have symmetry properties in order to reduce the number of variables. Let us now consider the subgroup 1×Sp(n-1) of Sp(n) that consists of all matrices that can be written 1 0 0 A in the quaternionic setting with A ∈ Sp(n -1).

Definition. Consider any (α, β) ∈ N 2 . A polynomial of H α,β and its corresponding spherical harmonic in Y α,β are said to be bi-invariant if:

• they are invariant under the left action of 1 × Sp(n -1);

• they are also invariant under the right action of Sp(1).

Proposition 3.1.

(1) Consider any (α, β, γ) ∈ N 3 such that γ ≤ min(α, β).

Denote by Inv α,β γ the complex vector space that consists of all polynomials of V α,β γ that are invariant under the left action of 1 × Sp(n -1). Then:

dim C (Inv α,β γ ) = α + β -2γ + 1.

We point out that this dimension is higher than or equal to 1 and that it equals 1 if and only if

α = β = γ. (2) Consider k ∈ N. Existence in H k of a bi-invariant polynomial
implies that k is even. Assuming now that k is even and setting α = k 2 , there exists in H k a unique (up to a constant) bi-invariant polynomial and this polynomial belongs to V α,α α .

Proof:

An invariant polynomial of V α,β γ defines a trivial 1-dimensional representation of 1 × Sp(n -1), whose multiplicity in the left action of 1×Sp(n-1) on V α,β γ is equal to dim C (Inv α,β γ ). Using a classical branching theorem proved by Zhelobenko for Sp(n) and Sp(n -1) (Theorem 9.18 in [START_REF] Knapp | Lie groups beyond an introduction[END_REF]), one can compute this multiplicity and thereby prove Item (1). Item (2) just requires to combine Item (1) and Corollary 3.1.

End of proof.

Given a non-negative even integer k, in order to exhibit the unique (up to a constant) bi-invariant polynomial of H k given by Proposition 3.1, one can concentrate on polynomials of the following type (they are obviously bi-invariant and of total homogeneous degree k):

P (z, w) = A∈A k ν A (z 1 z 1 + w 1 w 1 ) a (z 2 z 2 + • • • + z n z n + w 2 w 2 + • • • w n w n ) b .
where

A k = {(a, b) ∈ N 2 / a + b = k 2 }
and where coefficients ν A denote complex scalars (undetermined at first). We need P to be harmonic, which requires specific values for coefficients ν A ; it is shown in [START_REF] Mendousse | Analyse Harmonique Quaternionique et Fonctions Spéciales Classiques[END_REF] (Section 3.2.3) how to compute them.

Examples. Let us write U

= z 1 z 1 + w 1 w 1 and V = n r=2 z r z r + w r w r .
Then the unique bi-invariant polynomial (up to a contant) of H k is:

• (1 -n) U + V , when k = 2; • (2n-1)(n-1) 3 U 2 + (1 -2n) U V + V 2 , when k = 4.

Casimir operator of Sp(n).

We consider the inner-product defined on k by:

(X, Y ) -→ - 1 2 Tr(XY ).
where Tr denotes the trace form. Taking r and s to denote integers that belong to {1, ..., n}, define:

• A r = iE r,r -iE n+r,n+r ; • B r,s = E r,s -E s,r + E n+r,n+s -E n+s,n+r (r = s); • C r,s = iE r,s + s,r -iE n+r,n+s -iE n+s,n+r (r = s); • D r = E n+r,r -E r,n+r ; • E r = iE n+r,r + iE r,n+r ; • F r,s = E n+r,s + E n+s,r -E r,n+s -E s,n+r (r = s); • G r,s = iE n+r,s + iE n+s,r + iE r,n+s + iE s,n+r (r = s). One can check that the set B k = {A r , D r , E r } r∈{1,...,n} ∪ B r,s √ 2 , C r,s √ 2 , F r,s √ 2 , G r,s √ 2 1≤r<s≤n
is an orthonormal basis of k. One can apply to elements of H k any sequence of operators dL(X) (taking X ∈ k). In particular, let us consider the Casimir operator Ω L , which can be defined by:

(5)

Ω L = X∈B k dL(X) 2 .
This operator commutes with L. So Schur's lemma implies that Ω L is equal to a scalar multiple of the identity map when restricted to an irreducible invariant subspace. This scalar can be computed (see [START_REF] Mendousse | Analyse Harmonique Quaternionique et Fonctions Spéciales Classiques[END_REF], Corolloray 3.3): Proposition 3.2. Consider the left action L of K on V α,β γ . Denoting by Id the identity map:

Ω L = -(k -γ) 2 + 2nk + γ 2 -2γ Id.

From bi-invariance to hypergeometric equations.

In this section, we consider the quaternionic projective space P n-1 (H), whose elements we define with respect to right-multiplication: given x ∈ H n , the quaternionic line through x is the subspace

x H = {xh / h ∈ H}.
Quaternionic matrices act naturally on quaternionic lines: an invertible matrix M ∈ GL(n, H) assigns to a line x H the line (M x) H. We now study the orbits under the restriction of this action to 1 × Sp(n -1). Given x H ∈ P n-1 (H), we denote by O(x H) the orbit of x H. We show in the next proposition that the orbits can be parametrised by a single real variable. Proposition 3.3. Consider any x = (x 1 , ..., x n ) ∈ H n . There exists a unique θ ∈ 0, π 2 such that, writing x(θ) = (cos θ, 0, ..., 0, sin θ) ∈ H n , the quaternionic line x(θ) H belongs to O(x H). Moreover, θ is explicitly given by the following formulas ( • denotes the norm of H n-1 ):

• if x 1 = 0, then θ = arctan ( x ), taking x = x 2 x 1 , ..., xn x 1 ; • if x 1 = 0, then θ = π 2 . Proof: Suppose first that x 1 = 0. Then, writing x = x 2 1 x 1 , ..., x n 1
x 1 , we have x H = (1, x )H. Because Sp(n -1) acts transitively on spheres of H n-1 , the group 1 × Sp(n -1) contains an element that takes (1, x )H onto (1, 0, ..., 0, x ) H. One then chooses θ ∈ 0, π 2 such that: (1, 0, ..., 0, x ) H = (cos θ, 0, ..., 0, sin θ) H . Suppose now that x 1 = 0. Then x = 1 and one can choose an element of 1 × Sp(n -1) that carries x H onto (0, ...0, 1) H, leading to θ = π 2 . This establishes existence and formulas for the parameter θ; proof of uniqueness is straightforward.

End of proof.

Let us assume, throughout this section that k is even and set α = k 2 . Consider the space H k and its unique, up to a constant, bi-invariant polynomial P , which in fact belongs to V α,α α ⊂ H α,α (see Proposition 3.1). Denote by f P the spherical harmonic that corresponds to P , that is:

f P = P | S 4n-1 ∈ Y α,α .
Invariance under the right action of Sp(1) enables f P to descend to a function f on P n-1 (H):

f : P n-1 (H) -→ C x H → f P (x), where x is chosen in S 4n-1 .
Transferring, in the way one expects, the left action of K on spherical harmonics to a left action, also denoted by L, of K on complex-valued functions defined on P n-1 (H), we write:

L(k)f (xH) = f (k -1 x)H
for all (k, x) ∈ K × S 4n-1 . Invariance of f P under the left action of 1 × Sp(n -1) implies that f descends to a function on the classifying set O of orbits, leading in turn to the following new function (via Proposition 3.3):

F : 0, π 2 -→ C θ → F (θ) = f x(θ)H = f P x(θ) .
The following theorem establishes the first part of our "Main results" theorem (stated in the introduction):

Theorem 3.1. Fix any even non-negative integer k. Consider the unique (up to a constant) bi-invariant spherical harmonic f P of Y k and the corresponding function F (as introduced above).

• The restriction of F to the open interval 0, π 2 satisfies the following hypergeometric differential equation:

F (θ) + 6 tan(2θ) + 4n -8 tan θ F (θ) + k(k + 4n -2) F (θ) = 0.
• Consider the following smooth diffeomorphism (onto):

ψ : 0, π 2 -→ ]0, 1[ θ -→ cos 2 θ.
Then ϕ = F • ψ -1 satisfies the following hypergeometric differential equation:

τ (1 -τ ) ϕ (τ ) + 2(1 -nτ ) ϕ (τ ) + k 2 k 2 + 2n -1 ϕ(τ ) = 0.

Proof:

The Casimir operator Ω L of L is given by formula [START_REF] Gross | The dual of a parabolic subgroup and a degenerate principal series of Sp(n, C)[END_REF]. Given an element x ∈ S 4n-1 , we have:

Ω L (f P )(x) = X∈B k ∂ 2 ∂t 2 t=0 f P exp(-tX)x . Proposition 3.2 tells us that V α,α α is associated to the eigenvalue = -2α 2 + (4n -2)α of Ω L : Ω L (f P )(x) = f P (x).
Given θ ∈ 0, π 2 , one can apply this equation to x = x(θ):

(6) X∈B k ∂ 2 ∂t 2 t=0 f P exp(-tX)x(θ) = f P x(θ) .
One can convert this into a differential equation satisfied by the function F of the real variable θ. But this requires to know for each X ∈ B k and each t ∈ R, which parameter ξ X,θ (t) ∈ 0, π 2 labels the orbit of exp(-tX)x(θ)H under the left action of 1 × Sp(n -1). Proposition 3.3 gives us the value of ξ X,θ (t). Then ( 6) can be written ( 7)

X∈B k ∂ 2 ∂t 2 t=0 F ξ X,θ (t) = F (θ).
Because f P is invariant under the left action of 1 × Sp(n -1), the only elements of B k that actually contribute to ( 7) are (taking 2 ≤ r ≤ n):

A 1 , D 1 , E 1 , B 1,r √ 2 , C 1,r √ 2 , F 1,r √ 2 , G 1,r √ 2 .
Denote by B k the set of these matrices. Using the differentiation chain rule, (7) becomes:

X∈B k F ξ X,θ (0) ξ X,θ (0) 2 + F ξ X,θ (0) ξ X,θ (0) = F (θ).
Finally, all we have to do now is determine the coordinates of the various exp(-tX)x(θ) and deduce the terms ξ X,θ (0), ξ X,θ (0) and ξ X,θ (0). Long-winded calculations (see [START_REF] Mendousse | Analyse Harmonique Quaternionique et Fonctions Spéciales Classiques[END_REF] for details) finally lead to the first hypergeometric differential equation; it is then straightforward to establish the second.

End of proof.

Non-standard picture and modified Bessel functions

As mentionned in the introduction, the non-standard picture relies on a certain partial Fourier transform, which we introduce below (following [START_REF] Kobayashi | Geometric analysis on small unitary representations of GL(n, R)[END_REF] and [START_REF] Clare | On the degenerate principal series of complex symplectic groups[END_REF]). Such transforms reveal new aspects of functions, because they swap the roles of two fundamental operators: multiplication by coordinates and differentiation with respect to those coordinates. Also, integral formulas that result from applying partial Fourier transforms can lead to classical integrals which may be computed in terms of special functions.

4.1. Non-compact picture and complex Heisenberg group.

The general theory of induced representations, as presented in [START_REF] Knapp | Representation theory of semisimple groups -An overview based on examples[END_REF] (Chapter VII), includes, beside the induced and compact pictures of π iλ,δ , a so-called non-compact picture. Its carrying space is L 2 (N ), where, in our case, N = { t n / n ∈ N } ( t n denotes the transpose of n). We will realise this carrying space in the geometric setting of C 2n . In order to do so, let us first describe our parabolic subgroup explicitely (we are aware that m and n refer to elements of subgroups as well as dimensions; context makes intended meanings clear):

• M consists of matrices m =      e iθ(m) 0 0 0 0 A 0 C 0 0 e -iθ(m) 0 0 B 0 D      such that θ(m) ∈ R and A C B D ∈ Sp(m, C), where A, B, C, D denote m × m complex matrices; • A consists of matrices a =      α(a) 0 0 0 0 I m 0 0 0 0 α(a) -1 0 0 0 0 I m     
such that α(a) > 0 (I m denotes the m-dimensional identity matrix);

• N consists of matrices n =     1 t u 2s t v 0 I m v 0 0 0 1 0 0 0 -u I m     such that s ∈ C and u and v both belong to C m . Then Q = M AN is indeed a parabolic subgroup of G.
We regard the (2m + 1)-dimensional complex Heisenberg group H 2m+1 C as C × C m × C m equipped with the following product:

(s, u, v)(s , u , v ) = s + s + v, u -u, v 2 , u + u , v + v .
Here, •, • is defined for elements (x, y) ∈ C m × C m by:

x, y = m i=1

x i y i .

We point out that, later on, this sum will be denoted by x • y instead of x, y when we consider (x, y) ∈ R m × R m .

We use the following sequence of identifications (with n as above):

H 2m+1 C N H (s, u, v) -→ t n -→ (1, u, 2s, v).
where H = {1} × C m × C × C m is regarded as a complex hyperplane of C 2n . The first identification map is a group isomorphism (one can also prove that H 2m+1 C N ) and the second identication results from the natural action of N on C 2n (applied to the element (1, 0,

• • • , 0) of C 2n ).
One can now identify L 2 (N ) with L 2 (H 2m+1

C

) and, given f ∈ V 0 iλ,δ (in the induced picture), regard the restriction f | H as an element of L 2 (H 2m+1

C

).

From now on, we write C 2m+1 instead of H 2m+1 C .

Definition of the non-standard picture.

We first define two partial Fourier transforms

F τ : L 2 (C 2m+1 ) -→ L 2 (C 2m+1 ) F ξ : L 2 (C 2m+1 ) -→ L 2 (C 2m+1 )
by setting for functions g ∈ L 2 (C 2m+1 ) that fulfill integrability conditions:

F τ (g)(s, u, v) = C g(τ, u, v) e -2iπRe(sτ ) dτ F ξ (g)(s, u, v) =
C m g(s, u, ξ) e -2iπRe v,ξ dξ. We then define the partial Fourier transform on which is based the non-standard picture:

F = F τ • F ξ .
Definition. The non-standard picture of π iλ,δ has L 2 (C 2m+1 ) as carrying space. The action of G is then the conjugate under F of the action of G in the non-compact picture; in other words, F intertwines the action of G in the non-compact picture and the action of G in the non-standard picture. Because we intend to use the right action of Sp(1), we consider an entire space H k of harmonic polynomials. We restrict our attention to those components of Proposition 2.1 that are labelled by γ = 0 and are subspaces of H k , namely the components V α,β 0 with α + β = k; the corresponding highest weight vectors are the polynomials

P α,β 0 (z, w, z, w) = w α 1 z1 β .
We denote by g α,β the restriction of P α,β 0 to the unit sphere S 4n-1 . Let us call g the function in the induced picture that corresponds to g α,β . It extends g α,β , meaning that g | S 4n-1 = g α,β . By definition of the induced picture, g must satisfy for all non-zero complex numbers c:

g(c •) = c |c| -δ |c| -iλ-2n g.
We define

a(s, u) = 1 + 4|s| 2 + u 2 r(s, u, v) = a 2 (s, u) + v 2 .
By restricting g to the complex hyperplane H C 2m+1 , we get a function G α,β defined on C 2m+1 by: (s, u, v) .

G α,β (s, u, v) = g(1, u, 2s, v) = 1 r(s, u, v) iλ+2n g α,β 1 r(s, u, v) , u r(s, u, v) , 2s r(s, u, v) , v r
Finally, due to the total homogeneity degree k of P α,β 0 :

G α,β (s, u, v) = (2s) α (a 2 (s, u) + v 2 ) iλ+k 2 +n
.

We call G α,β the non-compact form of P α,β 0 . The aim of the rest of Section 4 is to determine the non-standard form of P α,β 0 , that is, F(G α,β ). We apply F ξ in Section 4.3.2 and F τ in Section 4.3.3. Calculations involve Bessel functions and various formulas that we have gathered in the appendix.

First transform.

By definition (integrability condition is fulfilled):

(8) F ξ (G α,β )(s, u, v) = C m (2s) α (a 2 (s, u) + ξ 2 ) iλ+k 2 +n
e -2iπRe v,ξ dξ.

In real coordinates, writing ξ = x + iy and v = a + ib (elements x, y, a, b each belong to R m ) and identifying ξ and v with the elements (x, y) and (a, b) of R m × R m , formula (8) reads:

(9) F ξ (G α,β )(s, u, v) = R m × R m (2s) α (a 2 (s, u) + x 2 + y 2 ) iλ+k 2 +n
e -2iπ(a•x-b•y) dxdy. 2π(rr ) 1-m J m-1 (2πrr )r 2m-1 dr.

Because r = v , (12) becomes:

(13) 2 α+1 πs α v 1-m ∞ 0 r m (a 2 (s, u) + r 2 ) iλ+k 2 +n
J m-1 (2π v r)dr.

We now want to apply Proposition 5.2. But it uses another notation system than ours. To understand how to switch from one system of notation to the other, let us define new variables x, y, µ:

x = r ; y = 2π v ; µ = iλ + k 2 + n -1 ; ν = m -1.
Then (13) becomes:

2 α+1 πs α v 1-m y -1 2 ∞ 0 x ν+ 1 2 (a 2 (s, u) + r 2 ) µ+1 J m-1 (xy) √ xydx.
Proposition 5.2 (first formula) now gives (as long as v > 0)

2 α+1 πs α v 1-m y -1 2 a ν-µ y µ+ 1 2 K ν-µ (ay) 2 µ Γ(µ + 1)
which, back to our own notation choices, is equal to

2 α+1 s α π iλ+k 2 +n Γ iλ+k 2 + n v a(s, u) iλ+k 2 +1 K -( iλ+k 2 +1) (2πa(s, u) v ).
To make formulas lighter, from now on we will write:

Λ = iλ + k 2 .
Because K -(Λ+1) = K Λ+1 , we have proved:

(s, u, v) in C × C m × C m such that v = 0: F ξ (G α,β )(s, u, v) = 2 α+1 s α π Λ+n Γ (Λ + n) v a(s, u) Λ+1 K Λ+1 (2πa(s, u) v ). 4.3.3. Second transform. Consider any (s, u, v) ∈ C × C m × C m such that s = 0 and v = 0. We want to compute: (14) F τ F ξ (G α,β ) (s, u, v) = C F ξ (G α,β )(τ, u, v) e -2iπRe (
2 α+1 τ α π Λ+n Γ (Λ + n) v a(τ, u) Λ+1 K Λ+1 (2πa(τ, u) v ) e -2iπ(ax-by) dxdy which can be re-organised as (15) 2 α+1 π Λ+n v Λ+1 Γ (Λ + n) R 2 τ α K Λ+1 (2πa(τ, u) v ) a(τ, u) Λ+1
e -2iπ(ax-by) dxdy.

Let us again use polar coordinates (outside the origin):

• (x, y) = rv θ with r > 0, θ ∈ R and v θ = (cos θ, sin θ); thus, τ = re iθ . • (a, -b) = r v θ with r > 0, θ ∈ R and v θ = (cos θ , sin θ ); thus, s = r e iθ . Let us write a(r, u) instead of a(τ, u): a(r, u) = 1 + 4r 2 + u 2 .
Integral (15) can now be written:

(16) 2 α+1 π Λ+n v Λ+1 Γ (Λ + n) ∞ 0 r α K Λ+1 (2πa(r, u) v ) a(r, u) Λ+1 2π 0
e iαθ e -2iπrr (cos θ cos θ +sin θ sin θ ) dθ rdr.

Following Proposition 5.1, the inner integral 2π 0 e iαθ e -2iπrr (cos θ cos θ + sin θ sin θ ) dθ is equal to:

(17) 2πe iα(θ -π 2 ) J α (2πrr ). Because r = |s| and θ = Arg(s), ( 17) is equal to: 2πe iα(Arg(s)-π 2 ) J α (2πr|s|). This turns (16) into:

(18) 2 α+2 π Λ+n+1 v Λ+1 e iα(Arg(s)-π 2 ) Γ (Λ + n) ∞ 0 r α+1 K Λ+1 (2πa(r, u) v ) a(r, u) Λ+1 J α (2πr|s|) dr.
We can now apply the second formula of proposition 5.2. To help follow notation choices made in this proposition, we set:

• x = 2r, dx = 2dr and β = 1 + u 2 > 0;

• a = 2π v > 0 (careful: this variable a is not what we have denoted a(r, u)); • y = π|s| > 0, ν = α and µ = Λ + 1. Plugging these expressions in (18) and using Proposition 5.2, we finally obtain:

F(G α,β )(s, u, v) = C × C m (2τ ) α (1 + 4|τ | 2 + u 2 + ξ 2 ) iλ+k 2 +n e -2iπRe(sτ + v,ξ ) dτ dξ = R(s, u, v) Kiλ+δ 2 π 1 + u 2 |s| 2 + 4 v 2
where we set

R(s, u, v) = (-i s) α π iλ+β+n 2 iλ+k 2 +1 Γ iλ+k 2 + n   |s| 2 + 4 v 2 π 1 + u 2   iλ+δ 2 .
This theorem establishes the second part of our "Main results" theorem (stated in the introduction).

Side remarks.

• The partial Fourier transform F changes, up to a constant -1 iπ , multiplication by the s coordinate into differentiation with respect to s. This implies [START_REF] Mendousse | Analyse Harmonique Quaternionique et Fonctions Spéciales Classiques[END_REF] for β ≥ 2 (due to integrability issues).

F(G α+1,β-1 ) = 2 -iπ ∂ ∂s F(G α,β ) , which is in fact proved in
• One inevitably notices in the formula of Theorem 4.1 a structure in two variables. Indeed, the particular value α = 0 and the square root terms lead us to study the functions

ψ ν : ]0, +∞[×]0, +∞[ -→ C (x, y) -→ x y ν K ν (xy)
where the parameter ν is a complex number. Fix ν ∈ C, x 0 > 0 and define the function ϕ x 0 ,ν : ]0, +∞[ -→ C y -→ ψ ν (x 0 , y).

One can show:

ϕ x 0 ,ν (y) + (1 + 2ν) y ϕ x 0 ,ν (y) -x 2 0 ϕ x 0 ,ν (y) = 0.

This equation belongs to the family of Emden-Fowler equations (or Lane-Emden equations) and its solutions can be written as the following combinations of Bessel functions of the first and second kind:

u(t) = C 1 t -ν J ν (-itx 0 ) + C 2 t -ν Y ν (-itx 0 ) .
Similar conclusions hold if one fixes y 0 instead of x 0 .

Appendix: Bessel functions

In these definitions, following for instance [START_REF] Lebedev | Special functions & their applications[END_REF] (sections 5.3 and 5.7), we take ν ∈ C and z ∈ C \{0} such that -π < Arg(z) < π:

(1) The Bessel function of the first kind is the function J ν defined by: As a consequence of Formula (2) of Section 7.3.1 in Chapter VII of [START_REF] Erdélyi | Higher transcendental functions[END_REF]: Proposition 5.1 (An integral representation of Bessel functions). Given ν ∈ N, ρ > 0 and a > 0:

J ν (z) = ∞ k=0 (-1) k Γ(k + 1)Γ(k + ν + 1)
J ν (ρ) = 1 2πe iν(a-π 2 )
2π 0

e iνθ e -iρ(cos a cos θ + sin a sin θ) dθ.

Formulas in the next proposition are stated in [START_REF] Erdélyi | Tables of integral transforms[END_REF] (Chapter VIII: Formula (20) of Section 8.5 and Formula (35) of Section 8.14):

Proposition 5.2 (Two integral formulas involving Bessel functions).

• For any real number y > 0 and any complex numbers a, ν, µ such that Re(a) > 0 and -1 < Re(ν) < 2Re(µ) + 3 2 , one has:

∞ 0 x ν+ 1 2
x 2 + a 2 -µ-1 J ν (xy) √ xy dx = a ν-µ y µ+ 1 2 K ν-µ (ay) 2 µ Γ(µ + 1) .

• For any real number y > 0 and any complex numbers a, β, ν, µ such that Re(a) > 0, Re(β) > 0 and Re(ν) > -1, one has:

∞ 0 x ν+ 1 2 x 2 + β 2 -µ 2 K µ a(x 2 + β 2 ) 1 2 J ν (xy) √ xy dx = a -µ β ν+1-µ y ν+ 1 2 (a 2 + y 2 ) µ 2 -ν 2 -1 2 K µ-ν-1 β(a 2 + y 2 ) 1 2
.

One can find the next formula in [START_REF] Erdélyi | Higher transcendental functions[END_REF] (Section 7.4.1, Formula (4)):

Proposition 5.3 (Asymptotic expansion for modified Bessel functions). For any fixed P ∈ N \{0} and ν ∈ C:

K ν (z) = π 2z 1 2 e -z     P -1 p=0 Γ 1 2 + ν + p p! Γ 1 2 + ν -p (2z) -p   + O |z| -P   .
The following proposition can be derived from Section 9.6 in [START_REF] Faraut | Analysis on Lie groups: an introduction[END_REF]:

Proposition 5.4 (Bochner formula). Consider any integer p ≥ 2. For ξ ∈ S p-1 and s > 0:

S p-1 e -2iπsξ•ξ dσ(ξ) = 2πs 1-p 2 J p 2 -1 (2πs) where dσ denotes the Euclidean measure of S p-1 and ξ • ξ denotes the Euclidean scalar product of R p applied to the elements of the sphere ξ and ξ seen as elements of R p .

Contact information.

Université de Reims Champagne-Ardenne Laboratoire de Mathématiques FRE 2011 CNRS UFR Sciences Exactes et Naturelles, Moulin de la Housse -BP 1039 51687 REIMS Cedex 2, FRANCE gregory.mendousse@univ-reims.fr

Fix an integer n ≥ 2 ,

 2 set m = n -1 and write G = Sp(n, C) and K = Sp(n). The representations we work with are defined by parabolic induction with respect to a maximal parabolic subgroup Q of G whose Langlands decomposition is Q = M AN (see Section 4.1 for explicit description) with: M U(1) × Sp(m, C), A R × + and N H 2m+1 C .

  together with the character χ iλ,δ defined by χ iλ,δ (man) = e iθ(m) δ α(a) iλ and the degenerate principal series representations π iλ,δ = Ind G Q χ iλ,δ of G.

Figure 1

 1 Figure 1 captures the contents of Propositions 2.1 and 2.2. In this diagram, the thick black dots represent highest weight vectors P α,β γ of L (again, α + β = k). Let us take a closer look at Figure 1. For any fixed integer γ such that 0 ≤ γ ≤ E k 2 : • The arrow beneath a value of γ points to a vertical set of components whose direct sum defines an invariant subspace V k γ (obviously not irreducible) under the left action of Sp(n):

Figure 1 .

 1 Figure 1. K-type diagram

4. 3 . 4 . 3 . 1 .

 3431 Connection with modified Bessel functions. Selected components.

(a 2 (a 2

 22 Switch to polar coordinates by writing (x, y) = rM and (a,-b) = r M , with M and M in S 2m-1 ⊂ R 2m , r = x 2 + y 2 = ξ and r = a 2 + (-b) 2 = v . Then the integral in Formula ((s, u) + r 2 ) iλ+k 2 +n e -2iπrr M •M dσ(M )   r 2m-1 drwhere M • M now denotes the Euclidean scalar product of R 2m applied to the points M and M of the sphere S 2m-1 seen as vectors of R 2m . Integral (10) can be written:(11)∞ 0 (2s) α (a 2 (s, u) + r 2 ) iλ+k 2 +n S 2m-1 e -2iπrr M •M dσ(M ) r 2m-1 dr. (s, u) + r 2 ) iλ+k 2 +n

Proposition 4 . 1 .

 41 Given any λ ∈ R and any (k, α, β) ∈ N 3 such that α + β = k, consider the non-compact form G α,β of the highest weight vector P α,β 0 . Then for all

Theorem 4 . 1 .

 41 Given any λ ∈ R and any (k, α, β) ∈ N 3 such that α + β = k, consider the non-compact form G α,β of the highest weight vector P α,β 0 . Then for all (s, u, v) in C × C m × C m such that s = 0 and v = 0:

z 2 ν+2k .( 2 )( 3 ).( 4 ) 2 I

 ν+2k2342 The Bessel function of the second kind is the function Y ν defined by:Y ν (z) = J ν (z) cos(νπ) -J -ν (z) sin(νπ) when ν / ∈ Z and, when ν ∈ Z, by Y ν (z) = lim →ν 0<| -ν|<1Y (z). The modified Bessel function of the first kind is the function I ν defined by: The modified Bessel function of the third kind is the function K ν defined byK ν (z) = π -ν (z) -I ν (z) sin(νπ)when ν / ∈ Z and, when ν ∈ Z, byK ν (z) = lim →ν 0<| -ν|<1 K (z).

  Then Re(sτ ) = ax -by and (14) becomes

	R 2

sτ ) dτ. Using propositions 4.1 and 5.3, one shows that τ -→ F ξ (G α,β )(τ, u, v) is indeed integrable. Let us use letters a, b, x, y again, this time taking them to refer to real numbers: s = a + ib and τ = x + iy.


Tristan Roussillon
email: tristan.roussillon@liris.cnrs.fr

Laure Tougne
email: laure.tougne@liris.cnrs.fr

Isabelle Sivignon
email: isabelle.sivignon@liris.cnrs.fr

Computation of Binary Objects Sides Number using Discrete Geometry, Application to Automatic Pebbles Shape Analysis

Keywords: Tristan Roussillon, Laure Tougne, Isabelle

Introduction

We are working in collaboration with geographers. Their objective is to establish a set of quantitative characteristics of pebbles sedimented in a river bed. The basic assumption in these studies is that pebbles size and shape are determined by lithology, distance of transport, abrasion, river * Supported by a grant from the french DGA (Jacques Blanc-Talon).

behavior, etc. The automatic computation of this set of quantitative characteristics by digital image analysis allows a minimization of the time spent on the field and a minimization of the inter-and intra-operator variability. Among the characteristics expected, there is pebble sides number. For geographers, pebble sides number is intuitively defined as shown in Fig 1 . We can see that this number results from a thick polygonalisation of pebbles contour.

Decomposition of digital curves into piecewise straight segments, splines, quadratic arcs or elliptical arcs is one of the contour-based techniques used in shape analysis, especially for a structural approach. See [START_REF] Loncaric | A survey of shape analysis techniques[END_REF] or [START_REF] Zhang | Review of shape representation and description techniques[END_REF] for a review of shape representation and description techniques.

Digital straight segments (or discrete segments) are now well known and understood objects. See [START_REF] Klette | Digital straitghness -a review[END_REF] for a review of the concept of digital straightness. A linear time algorithm for decomposition of digital curves into digital straight segments has been proposed more than ten years ago [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF]. Discrete geometry provides effective algorithms, which deal with integers, and permits perfect representations or reconstructions of discrete curves. However, the number of digital straight segments obtained is too large for irregular curves. To cope with this problem, Debled-Rennesson et al. [START_REF] Debled-Rennesson | Optimal blurred segments decomposition in linear time[END_REF][START_REF] Debled-Rennesson | Optimal blurred segments decomposition of noisy shapes in linear time[END_REF][START_REF] Debled-Rennesson | Linear segmentation of discrete curves into blurred segments[END_REF] have introduced the concept of blurred segment as an extension of the arithmetical approach of Reveilles [START_REF] Reveillès | Géométrie Discrète, calculs en nombres entiers et algorithmique[END_REF] and derived a polygonalisation algorithm linear in time. Another concept, called α-thick digital line arc, and the polygonalisation algorithm which results from this concept [START_REF] Buzer | An elementary algorithm for digital line recognition in the general case[END_REF], are very similar to Debled et al.'s ones. Their algorithms seem to be well adapted, because they produce an edge-based polygonalisation (the goal is to find a sequence of sets of 8-connected points that may stand for the edges), contrary to most of the classical methods which are vertex-based ones (the goal is to find a subset of dominant points as stated in [START_REF] Rosin | Techniques for assessing polygonal approximation of curves[END_REF]). Moreover classical methods that are available in libraries like Teh and Chin detection of dominant points or Hough Transform were used and gave too many sides than expected. However the algorithms presented in [START_REF] Buzer | An elementary algorithm for digital line recognition in the general case[END_REF] and [START_REF] Debled-Rennesson | Optimal blurred segments decomposition in linear time[END_REF] assume that the points are added with increasing x-coordinate or y-coordinate. This hypothesis is restrictive if one wants to deal with very noisy curves or if one wants to capture geometry at a coarse scale. In the present paper, we show that we can remove this hypothesis, while keeping the linearity of the algorithm, and as a consequence, deal with any noisy digital curves, with any maximal acceptable width.

The paper is organised as follows. In section 2, we recall some definitions and describe the algorithm presented in [START_REF] Debled-Rennesson | Optimal blurred segments decomposition in linear time[END_REF]. In section 3, we describe and prove our algorithm. Assessments and experiments are given in section 4 with synthetical and real images. The paper ends with some conclusions and future works in section 5.

Blurred Segments

Definitions

The notions of blurred segments and strictly bounding line rely on the arithmetical definition of discrete lines [START_REF] Reveillès | Géométrie Discrète, calculs en nombres entiers et algorithmique[END_REF].

A set Σ of integer points belongs to the digital straight line D(a, b, µ, ω) with slope a b , lower bound µ and thickness ω (with a, b, µ and ω being integer such that gcd(a, b) = 1) if and only if all integer points (x, y) of Σ verify the Diophantine inequalities : µ ≤ axby < µ + ω. The real lines axby = µ + ω -1 and axby = µ are, respectively, called the upper and lower leaning lines of D(a, b, µ, ω) [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF]. The integer points of the leaning lines are called leaning points [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF]. If ω < max(|a|, |b|), the digital straight line is disconnected. If ω = max(|a|, |b|), the digital straight line is 8-connected (it is named naive line). Increasing ω makes the digital straigth line thicker [START_REF] Reveillès | Géométrie Discrète, calculs en nombres entiers et algorithmique[END_REF]. See Fig. 2 for an example. The digital straight line is depicted with black disks. It is a set of integer points located between two leaning lines (straight lines) passing through some leaning points (circles). In the following, as a simplification, we assume that 0 ≤ y ≤ x. This hypothesis can be done without loss of generality due to symmetries with respect to Ox, Oy and the real line x = y.

Definition 1 [START_REF] Debled-Rennesson | Linear segmentation of discrete curves into blurred segments[END_REF] Let us consider a set of 8-connected points S. A discrete line D(a, b, µ, ω) is said bounding, if all points of S belong to D.

Definition 2 [4] A bounding line of S is said optimal if its vertical distance is minimal, i.e. if the vertical distance of S equals the vertical distance of its convex hull denoted by conv(S).

Definition 3 [START_REF] Debled-Rennesson | Optimal blurred segments decomposition of noisy shapes in linear time[END_REF] A set S is a blurred segment of width ν if and only if its optimal bounding line has a vertical distance less than or equal to ν. See Fig. 3 for an example. The blurred segment S is depicted with black disks. The convex hull conv(S) of S is depicted with dotted lines. The vertical width of conv(S) (double arrow) is computed from the leaning points (circles) and leaning lines (straight lines). The optimal bounding line (which is a thick digital straight line) is drawn with squares on the right. d @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ T c The recognition of blurred segments with width ν is thus equivalent to the computation of the vertical (or horizontal) width of the convex hull conv(S) [START_REF] Debled-Rennesson | Optimal blurred segments decomposition of noisy shapes in linear time[END_REF]. Because of the incremental property of the algorithm, the polygonalisation is very simple: add points until the vertical (or horizontal) width computed is strictly higher than the threshold value ν. The current blurred segment ends and a new blurred segment begins.

It should be noticed that due to symmetry, we only have to know how to compute the vertical width of the convex hull for maintaining both vertical and horizontal width simultaneously and always choose the minimal value as the width of the convex hull [START_REF] Debled-Rennesson | Optimal blurred segments decomposition of noisy shapes in linear time[END_REF]. Thus, in the following, as a simplification, we focus on the computation of the vertical width.

It should be noticed that this definition of width is different from the one usually used in Computational Geometry, which is generally not computed with respect to Ox or Oy [START_REF] Buzer | An elementary algorithm for digital line recognition in the general case[END_REF] (see Fig. 4). However, basic ideas used to compute this width are really close to the ones used in Computational Geometry for the rotating calipers algorithm [START_REF] Preparata | Computational geometry : an introduction[END_REF]. The vertical width of a convex polygon P is the maximal length of the intersection of P with a vertical line. The width function width(i) is the length of the intersection of P with a vertical line given by x = i. It is clear that the width function is concave (see Fig. 5).

E T x y O d $ $ $ $ d d g g g g y g g g g $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ U L U R L c c c E T x y O d $ $ $ $ d d T c $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ U L U R L c c c
E T x y O d $ $ $ $ d d T c $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ E T x width(x) O T c ¡ ¡ 7 7 2 2 e e v v v

Restriction

A linear time incremental algorithm of segmentation into blurred segments with width ν is given in [START_REF] Debled-Rennesson | Optimal blurred segments decomposition of noisy shapes in linear time[END_REF]. For each added point, there are two steps.

The first step consists in maintaining the convex hull conv(S) of S with Melkman's algorithm [START_REF] Melkman | On-line construction of the convex hull of simple polygon[END_REF]. This is an incremental and linear algorithm which assumes that added points form a simple polyline (which does not intersect itself). For us, this hypothesis is not restrictive since we deal with binary objects boundaries.

The second step consists in computing the vertical width of the convex hull conv(S). As written in [START_REF] Debled-Rennesson | Optimal blurred segments decomposition of noisy shapes in linear time[END_REF], we can consider three cases (edge, vertex), (vertex, edge) and (vertex, vertex) where the first element is located on the lower part of the convex hull and the second element is located on the upper part (see Fig. 4). We call U L and U R the left and right extremities of the edge and L the vertex because the two first cases are symmetrics. The third case is comparable with a case (edge-vertex) or (vertex-edge) where the edge is reduced to a single vertex. The edge and its parallel passing through the vertex (called supporting lines in Computational Geometry [START_REF] Preparata | Computational geometry : an introduction[END_REF]) define exactly the lower and upper leaning lines of an optimal bounding line for S [START_REF] Debled-Rennesson | Optimal blurred segments decomposition of noisy shapes in linear time[END_REF]. Thus, from U L , U R and L, we can compute the vertical width of S. Comparing this value to ν, we can then decide if S is a blurred segment of width ν or not.

The key point consists in updating the position of the leaning points. The algorithm described in [START_REF] Debled-Rennesson | Optimal blurred segments decomposition in linear time[END_REF] is incremental and linear, but it is unusable for a computation of the pebbles sides number because it assumes that the points are added with increasing x-coordinate or y-coordinate. The more the digital curve is noisy and the more ν (the maximal acceptable width) is high, the less this hypothesis is fulfilled. Hence, we obtain too much sides by running this algorithm. In Fig. 6 (which is drawn from figure 7 in [START_REF] Debled-Rennesson | Optimal blurred segments decomposition of noisy shapes in linear time[END_REF]), the points are neither added with increasing x-coordinate, nor with increasing y-coordinate. As a consequence, the blurred segment of width ν = 3.9 (the extremities of which are the grey squares) is shorter than expected.

Our algorithm

Description

Let us consider that we add a new point M to S, S = S ∪ M .

At a first level, there are three cases (see Fig. 7). If M belongs to D, the position of U L , U R and L do not change after the application of Melkman's algorithm. So S remains a blurred segment with the same vertical width and with the same optimal bounding line D. In the other cases, M is above or below D, the position of U L , U R and L change and the vertical width has to be recomputed. At a second level, for both cases where M does not belong to D, there are several cases again.

E T x y O d $ $ $ $ d d T c $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ U L U R L c
Let us called U L , U R and L , the new leaning points after the update. Given a point P of the convex hull conv(S), we denote next(P ) (resp. prev(P )) the functions which return the point after (resp. before) P in a trigonometric orientation.

• First, suppose that M is above D.

Let us suppose that M is after L (i.e. the x-coordinate of M is strictly higher than the x-coordinate of L). See case a) in Fig. 8.

We start by setting U L and U R to the two convex hull points that are neighbors of M . In Fig. 8, case a), U L and U R are, respectively set to U L and U R .

As M is above D, the slope of (U L M ) is greater than the slope of (U L U R ). As a consequence, the width function increases from U L to L.

E T x y O T c U L U R L q q q M b p p p p p p p p p p p p E T x y O T c d U L L = L q q q q M = U R q p p p p p p p p p p p p a) b) E T x y O T c d ÜL L q q q q q q M = U R q p p p p p p p p p p p p E T x y O T c $ $ $ $ d U R U L q q q q q M = L q p p p p p p p p p c) d)
Figure 8. What may happen if M is above (U L U R ) and after L.

If the slope of the edge [L next(L)] is greater than the slope of (U L M ), the width function decreases from L to M (see case b) in Fig. 8). U R is set to M and L is set to L. We can compute the vertical width from U L , U R and L .

If the slope of the edge [L next(L)] is lower than the slope of (U L M ) and if next(L) is before M , the width function increases from L to next(L). In this case, L moves along the lower part of the convex hull.

As a matter of fact, L is moving until next (L) such that slope(next(L), next (L)) > slope(U L , M ).

-If next (L) is before M , then U R = M and L = next (L) (see case c) in Fig. 8).

-If next (L) is after M , then U L = next(L), U R = next (L) and L = M (see case d) in Fig. 8). The configuration is reversed because the vertical width is given by an edge from the lower part of the convex hull and by a vertex from the upper part of the convex hull.

The case where M is before L is symmetric to the previous case.

The particular case where M and L have a same xcoordinate is straightforward. Both U L and U R move to M . The vertical width is the length of

[U L L] or [U R L].
The slope of D is equal to zero.

• Next, suppose that M is below D.

The case where M is after U R is identical to the case where M is above D and after L, but the configuration is reversed. It is enough to exchange the leaning points to have M above D and after L.

The case where M is before U L is symmetric to the previous case, i.e. comparable with the case where M is above D and after L.

The particular case where M is between U L and U R is straightforward. As the width function increases until M and decreases from M , we set

L to M , U L to U L and U R to U R .
Given a digital curve which does not intersect itself, there is an incremental algorithm which maintains the convex hull of the digital curve thanks to the Melkman's algorithm and which computes the vertical width of the convex hull thanks to the algorithm above.

Complexity

To study the algorithm complexity, the idea is to study leaning points displacements. It is enough to focus on the lower leaning point because the upper leaning points are the extremities of the edge in which L project vertically. The algorithm described in the previous section has two interesting properties about the lower leaning point straightforwardly deduced from the different cases studied in section 3.1.

Property 1 For each added point M , the lower leaning point does not move or moves towards M .

Property 2 For each added point M , the lower leaning point never goes beyond M .

M moves along the digital curve and L always moves towards M without going beyond it. Thus, in case of connected points as input (what is not a restrictive hypothesis for us), L moves are bounded by M moves, i.e. the update of L for the insertion of n connected points do not require more than the test of n points. We can conclude that the overall complexity of the algorithm is O(n) in that case.

Experiments

We implemented our algorithm. It takes as input, chain code, extracted from objects boundary by contour tracking. The starting point is first an extremal point (i.e. with minimal x-coordinate and y-coordinate). We shift then the starting point to the last point of the first blurred segment recognized in order to avoid over-segmentation. In addition to the chain code, our algorithm takes as input, ν, the maximal acceptable width. We studied the behavior of our algorithm both with synthetical images and real images.

Synthetical images

We drew 48 binary objects with a raster graphics editor. We first drew 27 objects with the polygon function. These objects were (convex or concave) polygons (see a) in Fig. 9). Then, we sketched 21 objects with the pencil function while trying to imitate the previously drawn polygons. As a result, these objects look like noisy polygons (see b) in Fig. 9). The points number of the set of objects is ranging from 371 to 2870 and the sides number of the set of objects is ranging from 3 to 26. For each object, we performed polygonalisations with width ν ranging from 0.5 to 15, with a step of 0.1. Objects sides number was deduced from the polygonalisations by counting the blurred segments obtained. We focused on the minimal width denoted by ν * from which we found the true sides number (see Fig. 9). Binary objects drawn with the polygon function, called standard objects, are used as ground truth.

For standard objects, the minimal width average is 1.87 (ν * ranging from 1 to 2.7), while for noisy objects, the minimal width average is 7.77 (ν * ranging from 4.7 to 13.7). See Tab. As object sides number is rather stable with respect to the increase of ν beyond ν * , we reach a perfect prediction rate (i.e. 100%) with ν = 3 for standard objects and with ν = 14 for noisy objects. However, there is no value, which allows to reach a perfect prediction rate for both standard and noisy objects. With ν = 14, we found one side less than expected for 4 standard objects (the predection rate is 44/48). Indeed, even if object sides number is rather stable with respect to the increase of ν, it decreases and tends to 1 for sufficiently large ν (one optimal bounding line D contains S).

Real images

We used our algorithm in order to study pebbles digital images. Twenty samples of pebbles taken in the bed of an Indonesian river at various distances from the sea were photographed. We have approximately 1500 pebbles contours of about 350 pixels to analyze. In a first step we detected pebbles with clustering methods, transforming the original color image into a binary image as shown in Fig. 10). In a second step, we extracted chain codes from pebbles boundaries. In a third step we computed the number of sides. The input parameter ν was set up at 13 by trial and error.

Pebbles size variation is very small in both real world and images. Acquisition process and digitization are identical for all images. According to previous study with synthetical images, it seems that ν * depends on size and noise. It was thus relevant to set up the value of ν, once for all. Statistical and geographical analysis are under progress. An exemple of polygonalisation is shown in Fig. 11 and some pebbles with their sides number are gathered in Fig. 12.

Conclusion and perspectives

The objective was to compute the number of sides that pebbles have. We opted for an edge-based polygonalisation which is exactly the geographers' intuitive definition (see Fig. 1 and Fig. 11). We proposed an incremental and linear algorithm, free of restrictive hypothesis, contrary to what we can read in the litterature [START_REF] Buzer | An elementary algorithm for digital line recognition in the general case[END_REF][START_REF] Debled-Rennesson | Optimal blurred segments decomposition in linear time[END_REF][START_REF] Debled-Rennesson | Optimal blurred segments decomposition of noisy shapes in linear time[END_REF][START_REF] Debled-Rennesson | Linear segmentation of discrete curves into blurred segments[END_REF]. We assessed our algorithm with synthetical images. It turns out that the input parameter ν controls the polygonalisation according to noise, the objects size and the study scale. We experimented our algorithm with real pebbles images too. Pebble sides number seems to be an interesting feature.

For the future, we think about fixing the input parameter in an automatic way (once for all) or in a dynamic way (tuning it during the process). We need a framework for assessing thick polygonalisations which are different of thoroughly studied polygonal approximations [START_REF] Rosin | Techniques for assessing polygonal approximation of curves[END_REF]. To end the paper, an interesting way of investigation is the extension to the concept of blurred tangent in order to compute robust curvature estimators (see [START_REF] Debled-Rennesson | Estimation of tangents to a noisy discrete curve[END_REF] for a first attempt) or to determine the minimal number of necessary blurred segments for a thick polygonalisation (like the min-DSS problem [START_REF] Feschet | On the min dss problem of closed discrete curves[END_REF]).

Figure 1 .

 1 Figure 1. Pebble sides number.

Figure 2 .

 2 Figure 2. The naive line D(2, 5, 0, 5) (left) and the thick line D(2, 5, 0, 10) (right) with their leaning points and leaning lines.

Figure 3 .

 3 Figure 3. The optimal bounding line D(1, 6, 0, 11) (squares) of a blurred segment S (black disks) of width ν = 2.

Figure 4 .

 4 Figure 4. The common (left) and vertical (right) width computed from U L , U R and L.

Figure 5 .

 5 Figure 5. Vertical width and width function.

Figure 6 .

 6 Figure 6. The problem of the algorithm in [4].

Figure 7 .

 7 Figure 7. The three cases while adding M .

Figure 9 .

 9 Figure 9. Results for two triangles.

Figure 10 .

 10 Figure 10. Pebbles images. The 3-sides pebble located in the center of the images was processed in Fig 11.

Figure 11 .

 11 Figure 11. Pebble polygonalisation with ν = 13. The number of sides found is 3.

Figure 12 .

 12 Figure 12. Some pebbles sides number.

Table 1 . The minimal width ν * from which we found the true sides number for each object.

 1

	1.
	objects	min max average
	standard objects	1	2.7	1.87
	noisy objects	4.7 13.7	7.77


Isabelle Sivignon

David Coeurjolly

Minimal Decomposition of a Digital Surface into Digital Plane Segments is NP-Hard

This paper deals with the complexity of the decomposition of a digital surface into digital plane segments (DPS for short). We prove that the decision problem (does there exist a decomposition with less than k DPS ?) is NP-complete, and thus that the optimisation problem (finding the minimal number of DPS) is NP-hard. The proof is based on a polynomial reduction of any instance of the well-known 3-SAT problem to an instance of the digital surface decomposition problem. A geometric model for the 3-SAT problem is proposed.

Introduction

Digital objects are defined as sets of grid points in Z n . Those objects carry redundant geometrical information due to their discrete structure: an object is represented as a set of elementary cells (called pixels in 2D, voxels in 3D). The definition of digital linear structures like digital lines [START_REF] Rosenfeld | Digital straightness[END_REF] and digital planes [START_REF] Klette | Digital Geometry: Geometric Methods for Digital Picture Analysis[END_REF][START_REF] Brimkov | Digital planarity -a review[END_REF] originated a lot of works dealing with the decomposition of the contour of a digital object into digital linear primitives. Such a decomposition actually apprehends global geometrical properties of those objects. Many decomposition strategies may be designed and the number of parts computed by the algorithms may be a first criterion to compare the results. In this work, we focus on the complexity of the optimal (minimal number of parts) decomposition problem. In the 2D case, it has been shown that the minimal decomposition of a digital curve into digital line segments can be computed in linear time [START_REF] Feschet | On the min dss problem of closed discrete curves[END_REF]. In the 3D case of surfaces, many decomposition algorithms have been proposed [START_REF] Françon | Polyhedrization of the boundary of a voxel object[END_REF][START_REF] Debled-Rennesson | Etude et reconnaissance des droites et plans discrets[END_REF][START_REF] Sivignon | Decomposition of a three-dimensional discrete object surface into discrete plane pieces[END_REF][START_REF] Sivignon | Reversible polygonalization of a 3D planar discrete curve: Application on discrete surfaces[END_REF], offering comparisons on the number of faces recognised by different algorithms. Nevertheless, no optimality results exist, and no complexity study has been carried out. Related results have been recently proposed in [START_REF] Brimkov | Discrete volume polyhedrization is srongly NP-hard[END_REF] concerning the NP-completeness of the construction of an integer lattice polyhedron P with minimal number of convex facets such that P ∩ Z 3 corresponds to the input 3D digital object.

In computational geometry, the decomposition of a shape (e.g. a polygon) into a minimal number of elements (e.g. convex polygons) usually leads to NPcomplete problems [START_REF]Handbook of Discrete and Computational Geometry[END_REF]. A problem is in the NP class of algorithms if it can only be solved in polynomial time by a non-deterministic machine [START_REF] Cormen | Introduction to Algorithms[END_REF]. As a corollary, the problem is in NP if a solution to the decision problem can be verified in polynomial time on a deterministic machine. A problem is said to be NP-complete if it is at least as difficult as any NP problem. In other words, if a problem is NP-complete, an old conjecture is that no time efficient solution exists to solve it. The remaining option is to consider approximation algorithms with or without heuristics.

Prior to a complexity study, the problem has to be formalised. In the sequel, we consider 6-connected sets of voxels which surface S is defined as the set of object voxels sharing a face with the background. The surface is a set of 18connected voxels, and maximal digital naive planes [START_REF] Reveillès | Géométrie discrète, calcul en nombres entiers et algorithmique[END_REF][START_REF] Andres | Discrete analytical hyperplanes[END_REF][START_REF] Klette | Digital Geometry: Geometric Methods for Digital Picture Analysis[END_REF][START_REF] Brimkov | Digital planarity -a review[END_REF] are used for the decomposition. A digital plane segment (DPS for short) is maximal if no surface voxel may be added to it. In the following, we consider a sequential decomposition algorithm: given a voxel on the surface (called a seed ), we construct the maximal digital naive plane segment adding iteratively voxels that are 18-connected to the DPS initialised with the seed. Then, a new seed is considered from the set of remaining voxels in S. In this algorithm, both the propagation process during the DPS growing and the initialisation of seeds must be taken into account.

The optimisation problem we consider is defined as follows:

Min-DSD (Digital Surface Decomposition): Given a digital object surface S, find the minimal decomposition of S into maximal digital naive plane segments using a sequential algorithm.

In order to study the complexity of an optimisation problem, the related decision problem has to be considered: k-DSD: Given a digital object surface S and a number k ∈ N * , does there exist a decomposition of S into k maximal digital naive plane segments using a sequential algorithm ?

In this article, we prove that k-DSD is NP-complete whatever the propagation heuristic. Furthermore, the only requirement on the digital plane segments topology is connectivity.

To prove that a problem P is NP-complete, a classical scheme is to exhibit a polynomial reduction of any instance of a classical NP-complete problem, denoted P N P into an instance of P. Then, we have to prove that a solution of P also leads to a solution of P N P . Since P N P is known to be NP-complete, we could conclude that P is also NP-complete [START_REF] Cormen | Introduction to Algorithms[END_REF]. In the literature, the Boolean Satisfiability Problem (SAT) is a decision problem classically used in complexity theory since it was the first known NP-complete problem. An instance of SAT is a boolean expression written using only and, or, not, variables and parentheses. The decision problem is: given an expression, is there an assignment of the variables such that the expression is true ? The problem remains NP-complete even if the expression is written in conjunctive normal form with three variables per clause, yielding the 3-SAT problem. An expression φ has the form:

(x 1 ∨ x 2 ∨ ¬x 3 ) ∧ (¬x 1 ∨ x 4 ∨ x 5 ) ∧ (¬x 6 ¬ ∨ x 3 ∨ ¬x 5 ) ∧ . . . , (1)
where each x i is a binary variable (and ¬x i its negation) that can appear several times in the expression.

In the following we define a polynomial reduction of any instance of the 3-SAT problem to an instance of the k-DSD problem. The construction process, defining geometrical objects for variables, variable instances and clauses, is presented in Section 2, while the NP-completeness proof derived from this construction is given in Section 3.

A Geometric Model for 3-SAT

Given a 3-SAT expression φ, we show how to construct a geometric discrete object. This construction is a two steps process: after defining geometric elements for variables, instances of variables and clauses, we see how these basic components are organised and linked together in the 3D space.

General Considerations

All the basic elements we define further are composed of two parts:

-idle part: the surface of this part will be made of planes parallel to axis planes and only aims at defining a 6-connected object. The minimal number of DPS needed to cover the idle part will be fixed for each basic element, and any decomposition of this part into maximal DPS will exactly cover the same voxels, with no possible extension. This part is not used in the encoding of a 3-SAT expression; -active part: this part consists of the remaining voxels after the decomposition of the idle part. It takes advantage of digital planes properties to geometrically encode the 3-SAT elements.

For each basic element, we provide an illustration1 of an example set of seeds (black voxels) which may be used in a decomposition algorithm. Moreover, those sets have the remarkable property that any two seeds cannot be covered by a single DPS.

The underlying basic idea for this construction is the following: the optimal decomposition chosen for a variable object generates a "signal" sent to clause objects through "wires" representing instances of variables. This kind of geometric construction of 3-SAT is a classic way to prove NP-completeness of geometric problems (see [START_REF] Worman | Decomposing polygons into diameter bounded components[END_REF][START_REF] Chazelle | Strategies for polyhedral surface decomposition: An experimental study[END_REF] for instance). The construction of basic elements relies on several properties of digital planes structure that we set forth here (Figure 1): Property 1. For the four configurations (a), (b), (b') and (c) represented in Figure 1, one DPS cannot simultaneously cover the two light-coloured voxels and all the other ones. In the configuration represented in Figure 1(d), the three voxels cannot be covered by one DPS, but any two voxels can.

Proof. The proofs of these properties are straight forward using either digital naive plane structural basic properties or their arithmetical definition [START_REF] Reveillès | Géométrie discrète, calcul en nombres entiers et algorithmique[END_REF][START_REF] Debled-Rennesson | Etude et reconnaissance des droites et plans discrets[END_REF][START_REF] Klette | Digital Geometry: Geometric Methods for Digital Picture Analysis[END_REF].

In the following, we refer to these configurations as Property 1(a), (b), (b'), (c) and (d). ). Actually, any other decomposition is either not optimal or not composed of maximal DPS. We set that these two possibilities respectively encode true and false assignments of the variable. From these decomposition schemes and Property 1(b), seven seeds can be defined on each variable object.

Variable elements are linked to clauses thanks to wires that are connected on the area circled in red on Figure 2(a). The first part of these wires, described in details in Section 2.3, aims at generating a "signal" encoding the assignment of the variable. This signal is then "sent" to clause objects (see Section 2.3 for the transmission process). Figure 3 illustrates the signal generation: the number of voxels covered by the two active DPS differ by one according to the truth value of the variable -in the case of a true value, one more voxel is covered.

For a positive instance of variable, the wire is connected to the variable on the right-hand side of the variable, as depicted on Figure 3: the signal corresponding to the value of the variable is generated. For a negative instance of variable, the wire is connected on the left-hand side of the variable: in this case, the signal corresponding to the negated value of the variable is generated.

Finally, and to handle multiple instances of the same variable in a boolean expression, the length (along y axis) of the variable v depends on the maximum number of positive or negative instances of v in an expression, so that all the connections can be made. Note that the length of the variable does not change the optimal number of DPS required for the decomposition. A clause element is depicted in Figure 4. It is composed of a transversal rectangular parallelepiped on which three terminals are plugged. Since each clause has three literals (recall that 3-SAT is considered), each clause element has three incoming wires. The active part consists of the upper part of the object as depicted in Figure 4. Five idle DPS are required in order to decompose five out of the six faces of the rectangular parallelepiped. Idle planes related to the three terminals will be taken into account in the wire definition.

The active part of a clause can be entirely covered by a single DPS, except one out of the three terminal extremities (see Figure 4(b)): indeed, following Property 1(d), the three terminal extremities cannot be covered by a single DPS whereas any couple of terminals can be entirely covered by a single DPS. To sum up, if one terminal extremity can be covered by a DPS of the wires active part, then only one DPS is required to cover the clause active part. Otherwise, two DPS are necessary. The link between a boolean clause and the geometric object we propose can be drawn up as follows: a boolean clause is true if and only if at least one literal is true; one DPS is enough to cover the whole active part of a clause if and only if one terminal extremity is covered by another DPS. From the optimal decomposition, six seeds can be defined on the surface of each clause object. The wires linking variable elements to a clause are plugged on the areas circled in red on Figure 4(a), one on each terminal extremity. To end with the variable and clause geometric objects, Figure 5 illustrates how these objects are put together in the 3D space when many objects are involved in a boolean expression: variables and clauses are lined up on two axis parallel to the y axis. The definition of wires connecting variables and clauses relies on this spatial construction.

Linking Variables and Clauses

Variable elements are connected to clause elements through wires, that represent variable instances: if a variable v appears in a clause c, a wire links the geometric elements of v and c. Those wires aim at "transmitting" the truth value of a variable to the clause it belongs to. Before defining the geometric construction of wires, we describe the transmission process.

Figure 6 illustrates how the truth value of a variable is transmitted to a clause through a wire. This Figure represents a vertical cut of the active part of a variable, a wire and a clause terminal. Figure 6(a) illustrates the propagation of a true value while Figure 6(b) shows how a false value is transmitted to a clause. From the construction we propose, the vertical cut of a variable-wireclause connection can be thought of as a 2D digital curve that we decompose in digital straight segments, using their properties.

We call "transmission voxels" the two voxels circled in red in Figure 6 (intermediate transmission voxels are circled in black). We consider an optimal decomposition of the surface into DPS. The left transmission voxel actually corresponds to the generation of the signal encoding the truth value of the variable (see Figure 3 for a 3D representation of a variable and a "plateau"). Using Property 1(a) and (b'), if the left transmission voxel is covered by a variable DPS, then the right transmission voxel (which is at the same time an extremity of a clause terminal) is covered by a wire DPS. On the contrary, if the left transmission voxel is not covered by a variable DPS, then the right transmission voxel is not covered by a wire DPS. Note that for the plateau, descent and ascent parts, the relative length of the steps are the key point of this transmission process: for instance, a single DPS cannot cover both the first and last voxel of the descent.

Since the left transmission voxel is covered by a variable DPS if and only if the variable instance is set to the value "true" (Property 1(a)), the clause terminal extremity is covered by a wire DPS if and only if the variable instance is set to the value "true". Following the spatial arrangement of variable and clause elements (see Figure 5), and the rules defined for the connections of negative and positive instances of variables (Section 2.2), wires standing for positive instances are plugged on the variable side closest to clauses, while wires corresponding to negative instances are plugged on the opposite side. We see that in the case of a negative wire, a U-turn towards clause objects is required. As depicted in 2D in Figure 6, wires are basically composed of four parts, that are depicted in 3D in Figure 7(a) for a positive wire:

a plateau (blue) generates the "signal" corresponding to the truth value of the variable; -a descent (green) to a given level L: two distinct variable instances descend on two different levels to ensure an intersection free construction; -a shift movement (red) on the level L to reach the clause position; -an ascent (yellow) from the level L to the clause terminal extremity. The optimal decomposition of the plateau is made of one DPS only, for the idle part (bottom of the plateau). Indeed, the sides are covered with descent idle DPS, and the upper part (active) is covered by a DPS coming from the variable decomposition. Figure 7(e) illustrates how a wire is connected to a variable.

Concerning the descent and ascent parts, optimal decompositions are depicted in Figure 7(b) and(c). Seven idle and one active DPS are required for both positive and negative wires. Moreover, the active part is a three steps surface such that the first step is k voxels long (k ≥ 3), the second one is k -2 voxels long and the third one is made of one voxel. In addition to the function of this construction in the transmission process (see previous paragraph), the parameter k is used to ensure that every wire descend on a different level so that wires do not intersect.

The shift parts of positive and negative wires are different. In the case of a positive wire, only one DPS covers the active part (upper part). Five more idle planes are necessary for a negative wire, and two DPS are needed to cover the active part (see Figure 7(d)). The transmission of the truth value through the U-turn part of a negative wire is ensured thanks to the small "bump" on the shift part and Property 1(c).

All in all, optimal decomposition of wires leads to the definition of 11 seeds (eight for the idle part, three for the active part) for each positive wire and 17 (13 for the idle part, four for the active part) for each negative wire (see Figure 7(b), (c) and(d)).

To summarise the construction, we have proposed a polynomial reduction of any instance of the 3-SAT problem into an instance of the k-DSD problem. This reduction is based on the definition of variable and clause objects linked together through wires which pass the truth value of a variable on to clauses. Section 3 is dedicated to the proof of the relation between the two problems.

NP-Completeness Proof

Let us consider a boolean 3-SAT expression φ and the corresponding discrete object surface S. We denote c, v, v p and v n the number of clauses, variables, positive instances and negatives instances of variables in φ respectively. Proposition 1. k-DSD is in NP.

Proof. Given a digital surface S and solution D, verifying that |D| ≤ k and that it actually covers all the voxels of S can easily be done in linear time in the number of voxels S.

Proposition 2. The size of S is linear in the size of φ.

Proof. The proof is straight forward considering the construction.

We shall now prove that the construction is a reduction of 3-SAT to k-DSD, i.e. that the expression φ is satisfiable if and only if S admits a decomposition with k maximal DPS. We prove the two implications one after the other. Lemma 1. If the expression φ is satisfiable, then S admits a decomposition with k maximal DPS.

Proof. Assume that φ is satisfiable under some truth assignment T . The following algorithm builds a decomposition of the surface of S into k maximal DPS:

1. label all the voxels belonging to a construction DPS regardless of T : 5v + 5c + 8v p + 13v n DPS are used to cover the entire idle part of S;

2. decompose each variable according to its truth assignment in T : this decompositions requires 2v DPS; 3. use 3v p and 4v n DPS to decompose the wires active parts, which may leave the tips of some wires (which are also the clause terminal extremities) uncovered; 4. since T satisfies φ, every clause has at least one incoming wire with a covered tip. Thus, every clause has at least one covered terminal extremity. Consequently, each clause active part can be covered with one single DPS.

All in all, (5v + 5c + 8v p + 13v n ) + 2v + 3v p + 4v n + c = 7v + 6c + 11v p + 17v n = k DPS are used in this decomposition.

In order to prove the reverse implication, we need to show that there is only one way of decomposing S into k DPS. Next, we show that this unique solution leads to a satisfactory assignment of φ's variables.

(v -1) + |D v | + 6c + 11v p + 17v n > k, which is a contradiction.
Now suppose that extra DPS are used for the active part. With these DPS, one can at best ensure that the "true" value is transmitted to every clause objects linked to this variable. Nevertheless, the number of DPS required to cover wires and clauses does not change, and we still have |D| = 7(v -1) + |D v | + 6c + 11v p + 17v n > k, which is a contradiction.

On the contrary, if less than seven DPS are used to cover a variable object, it is easy to check that some voxels will remain uncovered even if more DPS are used for wires or clause objects. Similar arguments can be used to show that positive and negative wires, and clause decompositions have to be composed of 11, 17 and 6 DPS. Lemma 3. If S admits a decomposition into k maximal DPS, then φ is satisfiable.

Proof. Suppose that S admits a decomposition D with k DPS. Since |D| = k, from Lemma 2 the decomposition of every variable object is made of seven DPS. Variable objects can only be decomposed two ways into seven DPS, each of which encodes a truth assignment. This decomposition is made of 5 DPS for the idle part and 2 DPS for the active part (regardless of the algorithm used). Thus, covering all variables requires 7v DPS. In the same way, using Lemma 2 covering wires uses 11v p + 17v n DPS. All in all, k -7v -11v p -17v n = 6c DPS remain for covering clause objects. The idle part of clause objects requires 5 DPS regardless of the rest of the decomposition. Thus c DPS remain to cover the clauses active parts. Since there are c clause objects, and c DPS remain, we know that the clause active parts are covered by one DPS only in D. This is possible if and only if every clause is satisfied, and thus φ is satisfied too.

Theorem 1. k-DSD is a NP-complete problem.

Proof. The result is derived from Lemma 1 and 3. This theorem proves that the decision problem associated to Min-DSD is NP-complete. Thus, according to the theory of complexity, Min-DSD is said to be NP-hard.

Example

A software that generates a 3D object from a 3-SAT boolean expression is available on http://liris.cnrs.fr/isabelle.sivignon/code.html. This program also generates the seeds of the object, and a simple surface decomposition algorithm into maximal DPS is also provided to compute the decomposition derived from those seeds.

Figure 8 is an illustration of the digital surface encoding the expression φ = (a ∨ ¬b ∨ c). The optimal decomposition into maximal DPS is composed of 49 idle DPS and 17 active DPS. In Figure 8(a), the variable objects encode the assignment (a = true, b = true, c = f alse), and the optimal decomposition is represented. In Figure 8(b), the variable objects encode the assignment (a = f alse, b = true, c = f alse): in this case, since φ is not satisfied, the optimal decomposition cannot be achieved, and an extra DPS (in red) is added. In this article, we have proved that the decomposition of a digital object surface into a minimal number of maximal DPS using a sequential algorithm is NPcomplete. This theoretical result concludes an important open problem in the discrete geometry community: no efficient algorithms exist to solve the Min-DSD problem. A logical consequence of this answer is that only heuristics can be used. Among possible heuristics, important theoretical future works exist: does there exist a polynomial-time approximation scheme for the Min-DSD problem ? More precisely, is there a polynomial in time approximation of Min-DSD that produces a solution that is within ǫ factor of the optimal solution ? By construction of variables, clauses and links, the genus of the obtained binary object depends on the number of cycle in the 3-SAT instance. Is k-DSD still NP-complete, and thus Min-DSD still NP-hard for hole-free objects ?

Fig. 1 .

 1 Fig. 1. Five configurations used for the reduction process

Fig. 2 .Fig. 3 .

 23 Fig. 2. Geometric discrete object encoding a variable: (a) general view with wire plugging area, (b) truth assignment, (c) false assignment

Fig. 4 .

 4 Fig. 4. Geometric discrete object encoding a clause: (a) general view, (b) optimal decomposition

Fig. 5 .

 5 Fig. 5. Positions of (four) variables and (two) clauses objects in the 3D space

Fig. 6 .

 6 Fig.6. Vertical cut illustration of the transmission of a truth assignment through a wire: (a) the value "true" is transmitted; (b) the value "false" is transmitted

Fig. 7 .

 7 Fig. 7. Wire between a variable and a clause: (a) case of a positive variable instance, with zooms on (b) the descent and (c) ascent parts; (d) case of a negative variable instance

Lemma 2 .

 2 Consider a decomposition of S with k DPS. Then the decompositions of variable, positive wire, negative wire and clause objects are respectively covered by 7, 11, 17, 6 DPS. Proof. Consider a decomposition D of S with |D| = k. Suppose that there exist a variable object with a decomposition D v such that |D v | > 7. Extra DPS are either idle or active. Using more than five idle DPS has no effect on the number of DPS required to cover other variables, wires and clauses. Thus, |D| = 7

Fig. 8 .

 8 Fig. 8. Discrete object encoding the expression φ = (a ∨ ¬b ∨ c): (a) optimal decomposition corresponding to the satisfaction of φ; (b) φ is not satisfied and one more DPS is required to achieve a complete decomposition

Most illustrations of this paper are originally colour artworks. To make the understanding of the paper easier from B&W printings, colour images are available on http://liris.cnrs.fr/isabelle.sivignon/SatDSD.html