Fabien Mathieu

P2P Live Seeding: Efficiency of Seeders in P2P Live Streaming

Keywords: P2P Live Streaming, Seeders, Efficiency

En pair-à-pair, l'utilisation de seeders (pairs contributeurs sans être demandeurs) permet de créer un effet de levier qui améliore considérablement les performances du système. Naturel dans le contexte du partage de fichiers ou de vidéo-àla-demande, le concept de seeding peut sembler contre-intuitif en Live Streaming. Cet article vise à étudier la faisabilité et les performances théoriques que l'on peut attendre d'un système de diffusion en temps réel utilisant le seeding. Notre approche consiste à partir d'un modèle simple que l'on va complexifier pour le rendre de plus en plus réaliste. Pour un système idéal où le nombre de connexions est illimité et leur coût nul, nous montrons que le surcoût dû à l'utilisation de seeders est marginal. Nous étudions ensuite l'impact d'une connectivité limitée sur l'efficacité des seeders. Enfin, à partir d'un modèle affine de coût des connexions, nous donnons une formule simple décrivant l'efficacité des seeders, nous permettant d'avoir un modèle réaliste de dimensionnement d'un système de Live Streaming.

Introduction

Bandwidth may be the most critical resource in P2P content distribution. In order to increase the available resources, a standard technique is to leverage the capacity of the system by using seeders, i.e. peers that contribute to the system but are (currently) not needing anything. Using seeders is a natural idea when considering file-sharing or Video-on-Demand systems (after a peer has downloaded its file/video-on-demand, it becomes a potential seeder for that content), but it may be counter-intuitive for Live Streaming systems, where the content cannot have been pre-fetched to some seeders before others ask for it : even if they are willing to contribute, seeders have no access to the live content unless something specific is done about that. The goal of this paper is to describe the feasibility and performance one can expect from P2P Live Seeding.

We propose to start from a very simple model, and to increase progressively its realism : in Section 3, we show that for an ideal P2P system where unlimited connections can be spawned at no cost, Live Seeding can be deployed for a marginal cost compared to the theoretical performance given by the Bandwidth Conservation Law (BCL) ; Section 4 introduces a more realistic model where connectivity has an implicit cost and must be limited ; then that cost is explicitly considered in Section 5, where we use a simplified overhead model to derive the optimal efficiency of seeders. This results in a realistic model for dimensioning Live Streaming systems that use seeders, which is illustrated by a small example in Section 6.

The next Section presents the model and existing results used in this paper.

Model and related work

We consider a live content of constant streamrate r, and a P2P live streaming system used to deliver that content. We classify the nodes of the system into three categories : Servers are in charge of injecting initial copies of the stream into the system. We assume they have a cumulated capacity U C = rN C , with N C ≥ 1, so at least one copy of the stream can be injected. Leechers are the nodes that want to watch the live content. Seeders are idle nodes that do not want to watch the live content, but can provide bandwidth to the system ‡ . † This work has been supported by the Collaborative Research Contract Mardi II between INRIA and Orange Labs, and by the European Commission through the NAPA-WINE Project, ICT Call 1 FP7-ICT-2007-1, Grant Agreement no.: 214412.

‡. Keeping seeders in a P2P content distribution system is a standard issue, as they have no direct incentive to stay in the system. Experience from filesharing and VoD tells us that if the altruistic behavior of the users is not enough, share-ratio policies can be deployed to ensure a fair population of seeders. We denote by C, L and S the sets of servers, leechers and seeders respectively. The number of leechers (resp. seeders) is denoted by N L (resp. N S ). Every peer n in L or S has an upload capacity u n devoted to the service and a download rate of at least r (the download capacity is not a bottleneck for the broadcast of the live content). U X and ūX are respectively the total and average upload bandwidths of set X ( ūX = U X N X ). According to BCL [BMHP08], if all available bandwidth resources can be used to useful content transfer, then Live Streaming feasibility is given by

α L + βα S + N C N L ≥ 1, with α X = ūX r , β = N S N L .
(1)

Of course, in real systems, not all available bandwidth can be used, because : some overhead is required ; bandwidth may be wasted to data transfers that are not directly useful ; some nodes may not be able to fully use their upload bandwidth.

For BitTorrent-like file-sharing systems, Qiu and Srikant proposed to introduce an efficiency parameter η ∈ [0, 1] that takes these issues into account [QS04]. Formally, we define the efficiency of a node (or set of nodes) as the ratio between the maximal effective bandwidth it can add to the system and its bandwidth capacity. Transposed to our live streaming system, this gives the feasibility condition

η L α L + η S βα S + η C N C N L ≥ 1
, where η X is the efficiency of set X.

(2)

For peer-assisted live streaming (systems with no seeders, i.e. β = 0), it has been shown that if we don't take overhead into account, then one can have η L = η C = 1, i.e. a perfect use of available bandwidth can be achieved [LZSJ + 08]. In the rest of this paper, we study what η S can be, or in other words how efficient seeders can be in a P2P live streaming system.

Live seeding for ideal systems

Following [LZSJ + 08], we first consider an ideal system that we define by the following properties : -no overhead, so in the bandwidth budget we only consider the effective data transfer (goodput) ; -unlimited connectivity, so one peer can send data to all others if it has the necessary upload bandwidth ; -stream continuity : the live stream can be divided into arbitrary small substreams of constant rate.

Theorem 1 The feasibility condition for an ideal P2P live streaming system with seeders is

α L + βα S + N C N L ≥ 1 + min(βα S , 1) N L . ( 3
)
Sketch of proof If (3) is verified, one can construct a working live streaming system by giving to each seeder s a distinct substream of rate u s N L (if α S β ≤ 1) or u s U S r (otherwise). s is in charge of broadcasting its own substream to the N L leechers. The remaining rate, if any, is served by the leechers and the remaining capacity of servers following a perfect peer-assisted diffusion [LZSJ + 08]. The cost of using seeders is the rate received by S, which is r min(βα S , 1) and corresponds to the right term in (3). Reciprocally, if (3) is not verified, one can check that the maximal bandwidth usable by leechers is less than required.

2 The efficiency of S, measured when seeders are used at their full capacity (case α S β ≤ 1) by comparing Equations ( 2) and (3), is

η S = 1 - 1 N L . ( 4
)
In other words, seeders are asymptotically optimal in an ideal P2P live streaming system, as the only bandwidth indirect cost relies in at most one streamrate redirected to S for replication. Many dimensioning rules can then be derived by using our proposed formulas. For instance, determining if the system is scalable would consist in checking if η L α L + η S βα S ≥ 1. If we assume here for simplicity homogeneous bandwidth u, η S = η s (u) (neglecting quantification issues), and optimal leechers' efficiency η L = r R , one can derive the relationship that u and β must verify for the system to be scalable :

β ≥ η s (u)( r u - r R ). (8)
If β, which indicates the ratio between idle (seeders) and active (leechers) users, is a given parameter of the system, Equation ( 8) can be used to derive the bandwidth u that is required for the system to be scalable. This is illustrated by Figure 1c (the performance of the ideal system, i.e. a = b = 0, is also plotted for comparison). Notice how even little values of β (less than 1) can give significant decrease of the required bandwidth, which is R for a seedless system with perfectly efficient leechers.

Conclusion

In this paper, we gave the keys to understand why seeding should be used in P2P live streaming if idle peers are present, and how efficient Live Seeding can be. After introducing ideal and limited-connectivity systems, we used a linear overhead model to give realistic formulas. Although this is a preliminary study, we believe that the results presented here are significant for the design and dimensioning of live streaming systems with seeding. In a future work, we plan on considering more carefully the quantification issues that appear in the limited-connectivity and linear-overhead models in order to refine our efficiency formulas. We also intend to apply the linear overhead approach to file-sharing and VoD systems.

R éf érences

[BMHP08] Farid Benbadis, Fabien Mathieu, Nidhi Hegde, and Diego Perino. Playing with the bandwidth conservation law. In IEEE P2P, 2008.

[CNM08] Damiano Carra, Giovanni Neglia, and Pietro Michiardi. On the impact of greedy strategies in bittorrent networks : The case of bittyrant. In IEEE P2P, pages 311-320, 2008.

[LZSJ + 08] Shao Liu, Rui Zhang-Shen, Wenjie Jiang, Jennifer Rexford, and Mung Chiang. Performance bounds for peer-assisted live streaming. SIGMETRICS Perform., 36(1) :313-324, 2008.

[QS04] Dongyu Qiu and R. Srikant. Modeling and performance analysis of bittorrent-like peer-to-peer networks. SIGCOMM Comput. Commun. Rev., 34(4) :367-378, October 2004.

. The efficiency of leechers should take into account the number of outgoing connections like we did for the seeders. However, η L is not the main matter of this paper, so we assume without remorse perfect efficiency r R .

  ratio β Required bandwidth u (in KBytes/s) b = 1.7 KBytes/s b = 25 KBytes/s Ideal system (a = b = 0) (c) Bandwidth required for scalability

FIGURE 1 :

 1 FIGURE 1: c = f (u), η = f (u) and u = f (β) for a system with r = 100 Kbytes/s, a = 0.1.

r

  Streamrate of the content (constant) α upload/streamrate ratio u n Available upload bandwidth of peer n β Seeders/Leechers ratio U X / ūX Total/average upload capacity of population X η Efficiency coefficient N L (resp. N S ) Number of leechers (resp. seeders) a Proportional cost of a connection N

C Normalized capacity of servers (U C = N C r) b Constant cost of a connection

TABLE 1 :

 1 Table of notation

Limited connections

We now propose a more realistic model where overhead is indirectly taken into account by assuming that each seeder s has a limit c s on the number of connections it can maintain. Theorem 2 The efficiency of a seeder s with limited connections c s is

).

(5)

Sketch of proof The most bandwidth-efficient way to use s is to feed it with a substream of rate min(r, u s c s ) that will be usefully sent to c s other peers (leechers or further relaying seeders). This will "cost" the input rate min(r, u s c s ), as it will not be directly used by leechers, leading to the result. 2 Equation (5) naturally extends (4). However, summing it over S, which gives

is no longer the real value of S' efficiency, but an upper approximation § .

Modeling the overhead

In real systems, connectivity is not arbitrarily limited. We propose to model the bandwidth cost of a connection that sends content at a rate e to a peer by a linear function ae + b. a is the proportional cost (for instance negotiation messages exchanged anytime a given quantity of data has been sent) and b the additive cost (like periodic messages). We assume for simplicity that the overhead cost is supported only by the sender. Also, let R := (1 + a)r + b be the bandwidth required for sending one copy of the stream through a single connection (one can easily check that r R is the maximal efficiency achievable in our model). Theorem 3 If the overhead follows a linear function, then the efficiency of a seeder s is

otherwise.

(7)

Sketch of proof In order to be useful, a seeder must have c ≥ 2, which implies u s > 2b. Then, the input content rate that a seeder of bandwidth u maintaining c connections can sustain is i = min(r, us c -b 1+a ), corresponding to an efficiency η = (c -1) i u s . For u s ≤ R 2 b , the optimal value for c is u s b ¶ , which corresponds to

. Otherwise, we should take c = u s R , which leads to η = r R -r u s . 2 Theorem 3 and proof lead to two interesting remarks.

-For bandwidths lower than R 2 b , the optimal number of connections and efficiency are functions of u, a, and b, but not of r. Moreover, the formula for the number of connections, u b , is similar to the empirical formula used in the current BitTorrent mainline, √ 0.6u [CNM08]. In fact, our model could explain the formula used in BitTorrent, assuming an additive connection cost b ≈ 1.7 KBytes/s. -For high bandwidths, the asymptotic efficiency is r R , which is the maximal feasible efficiency given the overhead : super seeders are nearly optimal in a live streaming system.

6 Application : dimensioning a scalable Live streaming system

In order to illustrate the interest of our work, consider a live streaming system with r = 100 KBytes/s, a proportional overhead of 10% (a = 0.1), and an additive cost that can be small (b = 1.7 KBytes/s) or large (b = 25 KBytes/s). Figure 1a and 1b indicates how many connections seeders should have as a function of their bandwidth, and the corresponding efficiency. §. The exact computation of the gap between the actual value of η S and the one given by ( 6) is complex, as it must take into account quantifications issues in the complete diffusion process (for instance, if one seeder has to redirect one of its output rate to a seeder of lesser input capacity, some additional bandwidth has to be wasted in the process). Such work could be done in a future work by adapting techniques from [LZSJ + 08], but for now we argue that the loss due to quantification can be neglected compared to the loss due to limited connectivity, especially for large systems.

¶. As this may not be an integer, we should in fact take the closest integer maximizing the efficiency. For simplicity, we do not take this quantification into account, as it makes the writing more complex while not drastically changing the results presented here.


Abdallah Badra
email: abdallah.badra@math.univ-bpclermont.fr

Martine Picavet-L'hermitte

SOME DIOPHANTINE EQUATIONS ASSOCIATED TO SEMINORMAL COHEN-KAPLANSKY DOMAINS

Keywords: 2000 Mathematics Subject Classification. Primary 11D04, 1315; Secondary 13A05, 20M14 CK domain, half-factorial, seminormal, t-closed, diophantine equations

A Cohen-Kaplansky domain (CK domain) R is an integral domain where every nonzero nonunit element of R is a finite product of irreducible elements and such that R has only finitely many nonassociate irreducible elements. In this paper, we investigate seminormal CK domains and obtain the form of their irreducible elements. The solutions of a system of diophantine equations allow us to give a formula for the number of distinct factorizations of a nonzero nonunit element of R, with an asymptotic formula for this number.

Introduction

Let R be an atomic integral domain, that is, each nonzero nonunit element of R can be written as a finite product of irreducible elements (or atoms). The simplest situation is when R has only a finite number of (nonassociate) atoms. Such a domain R was called a Cohen-Kaplansky domain (CK domain) by D.D. Anderson and J.L. Mott in [START_REF] Anderson | Cohen-Kaplansky domains: Integral domains with a finite number of irreducible elements[END_REF] who obtained many conditions equivalent to R being a CK domain, after I.S. Cohen and I. Kaplansky [START_REF] Cohen | Rings with a finite number of primes I[END_REF] inaugurated the study of CK domains. In Section 2 we recall and give basic results on CK domains.

An atomic domain R is called a half-factorial domain (HFD) if each factorization of a nonzero nonunit element of R into a product of atoms has the same length (Zaks [15]). A ring R is called seminormal if whenever x, y ∈ R satisfy x 3 = y 2 , there is a ∈ R with x = a 2 , y = a 3 [START_REF] Swan | On seminormality[END_REF]. Section 3 is devoted to the study of seminormal CK domains. In particular, we show that a seminormal CK domain is half-factorial and obtain some equivalent conditions for a CK domain to be seminormal. As factorization properties of CK domains and seminormality are preserved by localization, we consider a local seminormal CK domain R. Let R be its integral closure. Then R is a DVR with maximal ideal Rp, which is also the maximal ideal of R. Moreover the atoms of R are of the form vp, where v is a unit of R. If U ( R) (resp. U (R)) is the group of units of R (resp. R), the factor group U ( R)/U (R) is a finite cyclic group. Let ū be a generator of U ( R)/U (R) and n the order of ū. If x = vp k is a nonzero nonunit element of R with v = ūr , r ∈ {0, . . . , n -1}, in U ( R)/U (R), the distinct factorizations of x in R into atoms are deduced from the system of diophantine equations in (a 1 , . . . , a n ) ∈ n : (S)

             n i=1 a i = k n i=1 ia i = r in ¡ /n¡
The calculation of the number of solutions of this system is the object of Section 4. If we denote by η(x) the number of non-associated irreducible factorizations of x into atoms, we get that η(x) is the number of solutions of the system (S).

Section 5 ends this paper with the asymptotic behaviour of the function η where we use the following result by F. Halter-Koch : Theorem 1.1. [6, Theorem 1]. Let H be an atomic monoid such that each nonunit x has finitely many non-associated factorizations into irreducibles. Suppose that there are only finitely many irreducible elements of H which divide some power of x. There exists two constants A ∈ ¢ and d ∈ , A > 0 such that η(x n ) = An d + O(n d-1 ).

An explicit value for A and d is obtained for a local seminormal CK domain.

For a ring R, we denote by Max(R) the set of maximal ideals of R and by U (R) its group of units. Let x, y ∈ R. We say that x and y are associates (x ∼ y) if there exists u ∈ U (R) such that x = uy. For an integral domain R, we denote by R its integral closure. The conductor [R : R] of an integral domain R in its integral closure is called the conductor of R. For a finite set S, we denote by |S| the number of elements of S. For x ∈ £ , we set [x] = sup{n ∈ ¡ | n ≤ x}.

Basic results on CK domains

We first recall some of useful results concerning CK domains.

Theorem 2.1. [2, Theorem 4.3] For an integral domain R, the following statements are equivalent.

1. R is a CK domain. 2. R is a semilocal PID with R/[R : R] finite and | Max(R)| = | Max( R)|. 3. R is a one-dimensional semilocal domain with R/M finite for each nonprin- cipal maximal ideal M of R, R is a finitely generated R-module (equivalently, [R : R] = 0), and | Max(R)| = | Max( R)|.
This theorem implies the following properties.

∈ R. 2. U ( R)/U (R) is a finite group. 3. R M is a CK domain for each maximal ideal M of R.
In particular, RM is a DVR. 4. Let T be an overring of R. Then T is also a CK domain. 5. The atoms of R are primary. D.D. Anderson and J.L. Mott [START_REF] Anderson | Cohen-Kaplansky domains: Integral domains with a finite number of irreducible elements[END_REF] say that a pair of rings R ⊂ S is a root extension if for each s ∈ S, there exists an n = n(s) ∈ ¤ * with s n ∈ R. For such an extension we have Since D/I is finite, there are finitely many subrings of D/I, and so finitely many R ∈ E. Let R and S ∈ E and set T = R ∩ S. By Proposition 2.3, T is a CK domain with conductor J ⊃ I. But T ⊂ R implies J ⊂ I, so that J = I and T ∈ E. Therefore the intersection of all elements of E is a CK domain with conductor I and integral closure D and is the least element of E.

| Max(R)| = | Max(S)|. Hence R ⊂ R is a root extension when R is a CK domain. Proposition 2.3. Let R 1 and R 2 be two CK domains with the same integral closure R . Then R = R 1 ∩ R 2 is a CK domain with integral closure R . Proof. Set R = R 1 ∩ R 2 . Define I 1 = [R 1 : R ], I 2 = [

Characterization of seminormal CK domains

Let R be an integral domain with quotient field K. We say that R is t-closed if whenever x ∈ K and x 2rx, x 3rx 2 ∈ R for some r ∈ R, then x ∈ R [START_REF] Picavet | Anneaux t-clos[END_REF]. A t-closed integral domain is seminormal. Recall that an integral domain R is said to be a pseudo-valuation domain (PVD) if there exists a valuation overring V of R such that Spec(R) = Spec(V ) [START_REF] Hedstrom | Pseudo-valuation domains[END_REF] and an integral domain R is said to be a locally pseudo-valuation domain (locally PVD) if each of its localizations at a prime ideal is a PVD [START_REF] Dobbs | Locally pseudo-valuation domains[END_REF]. Proposition 3.1. Let R be a one-dimensional Noetherian integral domain such that its integral closure R is a finitely generated R-module. The following conditions are equivalent :

1. R is seminormal and the canonical map Spec( R) → Spec(R) is bijective.

2. R is t-closed. 3. R is a locally PVD. 4. The conductor I of R is a radical ideal in R and | Max(R)| = | Max( R)|.
In

( R)p ⊂ R. Proof. Assume that R is seminormal. By Proposition 3.1 (4), Rp is the conductor of R, so that U ( R)p ⊂ Rp ⊂ R.
Conversely, if U ( R)p ⊂ R, we get that U ( R)p n ⊂ R for any integer n and Rp ⊂ R gives that Rp is the conductor of R so that R is seminormal.

In the nonlocal case, this condition is not fulfilled : Proof. Let R be a seminormal proper underring of D. Since its conductor is a radical ideal of D, it has to be M , a maximal ideal in R so that R/M is a subfield of the finite field D/M . But the set of subfields of D/M is linearly ordered.

Corollary 3.3. Let R be a CK domain with integral closure R = R. Let Rp i , i = 1, . . . , n, be the maximal ideals of R. Then U ( R)p i ⊂ R for any i = 1, . . . , n, implies that R is seminormal and n = 1. Proof. The case n = 1 is the previous Corollary. Assume n > 1. Any nonunit of R is in R. Moreover, Rp 1 and Rp 2 are comaximal ideals of R. For any u ∈ U ( R), there exists v, w ∈ R such that u = vp 1 + wp 2 ∈ R. Then R = R, a contradiction.
Let R 1 , R 2 be two seminormal proper underrings of D with integral closure D. Their conductor is M and we have, for instance,

R 1 /M ⊂ R 2 /M , which gives R 1 ⊂ R 2 .
Here is a fundamental link between seminormal CK domains and factorization. The following theorem gives the additional condition necessary for a CK halffactorial domain to be seminormal.

Theorem 3.6. Let R be a CK domain with integral closure R. Let Rp i , i = 1, . . . , n, be the maximal ideals of R. Then R is seminormal if and only if R is a HFD and U ( R)p 1 • • • p n ⊂ R. Moreover, if these conditions are satisfied, we can choose p i ∈ R for each i = 1, . . . , n.
Proof. We can assume R = R (the case R = R is trivial).

Let R be a seminormal CK domain. Then R is a HFD by the previous Proposition and the conductor I of R is a product of some of the Rp i . It follows that

U ( R)p 1 • • • p n ⊂ R.
Conversely, assume that R is a HFD and U ( R)p 1 • • • p n ⊂ R and let I be the conductor of R. For each i = 1, . . . , n, set

P i = R ∩ Rp i , R i = R Pi and R i = R Pi = RPi .
First, we show that we may assume p i ∈ R for each i = 1, . . . , n.

-

If P i is comaximal with I, then R i = R i and p i /1 is an atom in R i [2, Theorem 2.1 (2)].
Then there exists a P i -primary atom p ∈ R and s ∈ R \ P i such that sp i = p, which implies s ∈ U ( R), so that Rp i = Rp.

-Let P i be non comaximal with I and let x be a P i -primary atom in R. There exist u ∈ U ( R) and an integer k such that x = up k i since x ∈ P j for any j = i. But R i is a HFD, which implies that x/1 p i /1 in R i [2, Theorem 6.3] and so k = 1. Then x p i in R.

The assumption can be rewritten

U ( R)p 1 • • • p n ⊂ R with p i ∈ R for each i = 1, . . . , n. This gives finally Rp 1 • • • p n ⊂ I ⊂ R and I is a radical ideal in R. Moreover, R being a CK domain, we get | Max(R)| = | Max( R)| and thus R is seminormal by Proposition 3.1 (4).
In the local case, we obtain another characterization for a CK half-factorial domain to be seminormal. Proof. We can assume R = R (the case R = R is trivial).

Let R be seminormal. Then R is a HFD by the previous Theorem. Let Rp be the maximal ideal of R and let a 1 , . . . , a n be the nonassociate atoms of R. They are of the form a i = u i p, u i ∈ U ( R) by [START_REF] Anderson | Cohen-Kaplansky domains: Integral domains with a finite number of irreducible elements[END_REF]Theorem 6.3 (3)]. But since R is seminormal, its conductor is Rp. It follows that up ∈ R for any u ∈ U ( R). Let up, vp be two atoms of R, where u, v ∈ U ( R). Then up and vp are associates in R if and only if there exists w ∈ U (R) such that up = wvp, which is equivalent to ū = v in U ( R)/U (R). Hence two atoms up, vp of R, with u, v ∈ U ( R), are nonassociates in R if and only if ū = v in U ( R)/U (R). Then R has |U ( R)/U (R)| nonassociate atoms (see also [START_REF] Anderson | Cohen-Kaplansky domains: Integral domains with a finite number of irreducible elements[END_REF]Corollary 5.6]).

Conversely, let R be a HFD with n = |U ( R)/U (R)| nonassociate atoms. They are of the form a i = u i p, u i ∈ U ( R), i = 1, . . . , n and {ū 1 , . . . , ūn } = U ( R)/U (R). It follows that up ∈ R for any u ∈ U ( R). In particular, p ∈ R so that p n ∈ R for any integer n > 0 and we get that Rp ⊂ R. Then Rp is the conductor of R and R is seminormal.

A seminormal CK domain has a property which is not too far from unique factorization. In [START_REF] Chapman | Inside factorial monoids and integral domains[END_REF], S.T. Chapman, F. Halter-Koch and U. Krause defined an integral domain R to be inside factorial with Cale basis Q, if, for every nonzero nonunit x ∈ R, there exists some n ∈ ¥ * such that x n has a unique factorization, up to units, into elements of Q. Proposition 3.8. Let R be a seminormal CK domain with integral closure R. Then R is inside factorial with Cale basis {p 1 , . . . , p n }, where the Rp i are the maximal ideals of R with p i ∈ R for i = 1, . . . , n.

Proof. We have seen in Theorem 3.6 that we can choose p i in R, where the Rp i are the maximal ideals of R. The atoms of R are of the form u ij p i , with

u ij ∈ U ( R), i = 1, . . . , n [2, Theorem 2.1 (2)]. Let r = |U ( R)/U (R)|. Then u r ∈ R for any u ∈ U ( R). Let x be a nonzero nonunit of R.
As an element of R, it can be written x = u p αi i , u ∈ U ( R). Then x r = u r p rαi i with u r ∈ U (R) and this factorization into the p i is obviously unique.

Remark 3.9. Under assumptions of the previous Proposition, let e be the exponent of the factor group U ( R)/U (R). Then e is the least integer r such that x r has a unique factorization, up to units, into elements of {p 1 , . . . , p n }, for every nonzero nonunit x ∈ R. Indeed, e is the least integer r such that u r ∈ U (R) for any u ∈ U ( R).

We can calculate this exponent. D.D. Anderson, D.F Anderson and M. Zafrullah call in [START_REF] Anderson | Atomic domains in which almost all atoms are prime[END_REF] an atomic domain with almost all atoms prime a generalized CK domain. A CK domain is obviously a generalized CK domain. We can still assume R = R. Then, if I is the conductor of R, we have the isomorphism U ( R)/U (R) U ( R/I)/U (R/I) by [START_REF] Picavet-L'hermitte | Factorization in some orders with a PID as integral closure, Algebraic Number Theory and Diophantine Analysis[END_REF]Theorem 2] (the result was obtained for algebraic orders but a generalization to one-dimensional Noetherian domains R with integral closure which are finitely generated R-modules can be easily made). Since R is seminormal,

I is a radical ideal in R. After a reordering, write I = m i=1 Rp i . Then U ( R)/U (R) m i=1 U ( R/ Rp i )/U (R/P i ) , where P i = R ∩ Rp i since I = m i=1 P i as an ideal of R.
Set q i = |R/P i | and k i = [ R/ Rp i : R/P i ]. Then e i = (q ki i -1)/(q i -1) is the order (and the exponent) of the finite cyclic group U ( R/ Rp i )/U (R/P i ) and e = lcm(e 1 , . . . , e m ).

We are now able to obtain all the factorizations into atoms of a nonzero nonunit element of a seminormal CK domain with the number of distinct factorizations into atoms. We can restrict to the local case by the following proposition. Proposition 3.10. Let R be a CK domain with maximal ideals P 1 , . . . , P n . Set R i = R Pi and define η i (z) to be the number of distinct factorizations into atoms of

R i of a nonzero z ∈ R i . Then η(x) = n i=1 η i (x/1) for a nonzero x ∈ R.
Proof. By [2, Theorem 2.1 (2)], the atoms of R are primary and the atoms of R i are the P i -primary atoms of R. Moreover, if x is a nonzero nonunit element of R, then x is written in a unique way x = x 1 • • • x n , where x i is a P i -primary element of R for each i = 1, . . . , n [7, Corollary 1.7]. Indeed, by [1, Corollary 5], a CK domain is weakly factorial (such that every nonunit is a product of primary elements), and a weakly factorial domain is a weakly factorial monoid for the multiplicative structure. So, we get η(x) = n i=1 η(x i ) and η(x i ) = η i (x i /1) for each i by [2, Theorem 2.1 (2)] since a factorization of x i into atoms of R leads to a factorization of x i /1 into atoms of R i and conversely.

To end, we give the form of atoms in a local seminormal CK domain.

Theorem 3.11. Let R be a local seminormal CK domain with integral closure R. Let Rp be the maximal ideal of R, with p ∈ R. Set n = |U ( R)/U (R)| and choose u ∈ U ( R) such that ū is a generator of the cyclic group U ( R)/U (R). Then

1. A set of all nonassociate atoms of R is {u i p | i = 0, . . . , n -1}. 2. Let x = vp k , k ∈ ¦ * , v ∈ U ( R). Let r ∈ {0, . . . , n -1} be such that v = ūr .
The number of nonassociated factorizations of x into atoms of R is equal to the number of solutions (a 1 , . . . , a n ) ∈ ¦ n of the system of diophantine equations :

(S)

             n i=1 a i = k n i=1 ia i = r in § /n § Proof.
As above, we can assume R = R. Then Rp is the conductor of R so that R/ Rp is a finite field by Theorem 2.1 (3) and U ( R/ Rp) is a finite cyclic group. It follows that U ( R)/U (R) U ( R/ Rp)/U (R/ Rp) (Remark 3.9) is also a finite cyclic group. Let u ∈ U ( R) be such that ū is a generator of U ( R)/U (R).

(1) In view of Proposition 3.7, we can choose A = {u i p}, i = 1, . . . , n, as a set of nonassociate atoms of R since the u i are the representatives of the elements of U ( R)/U (R) and u n p is an associate of p in R.

(2) Set p i = u i p, i = 1, . . . , n, and let x be a nonzero nonunit element of R which is not an atom. Then x = vp k , k > 1 with a unique v ∈ U ( R). A factorization of ia i in § /n § . Then (a 1 , . . . , a n ) ∈ ¦ n is a solution of the system (S). Conversely, let (a 1 , . . . , a n ) ∈ ¦ n satisfying (S).

Set x = n i=1 p a i i = n i=1 (u i p) a i = u a 1 +2a 2 +•••+na n p a 1 +a 2 +•••+a n . But n i=1 ia i = r + sn, s ∈ ¨, gives x = u r (u n ) s p k and v = ūr implies u r = w v,
where w ∈ U (R). So we get x = w (u n ) s vp k = w (u n ) s x, with w (u n ) s ∈ U (R) and x ∼ x in R. We deduce that two distinct solutions of (S) give two distinct factorizations of x into atoms of R and the number of nonassociated factorizations of x into atoms of R is equal to the number of solutions (a 1 , . . . , a n ) ∈ © n of (S).

We are going to calculate the number of solutions of such a system in the next section.

On the number of solutions of a system of two special diophantine equations

In this section, we use the following notation. Let n, r ∈ © , k, s ∈ ¨with n > 0 and 0 ≤ r ≤ n -1. We consider the following systems of diophantine equations in (a 1 , . . . , a n ) ∈ © n :

S(n, k, r)              n i=1 a i = k n i=1 ia i = r in ¨/n ¨and S (n, k, s)              n i=1 a i = k n i=1 ia i = s
We denote respectively by N (n, k, r) and p(n, k, s) the numbers of solutions (a 1 , . . . , a n ) ∈ © n of S(n, k, r) and S (n, k, s). Obviously, we have N (n, k, r) = p(n, k, r) = 0 for k < 0. It is easy to see that

N (n, k, r) = i≥0 p(n, k, r + in) = [k-r n ] i=[ k-r n ]
p(n, k, r + in)

At last, for n, k ∈ © , k > 0, we set :

F (n, k, x) = x k (1 -x n+k-1 )(1 -x n+k-2 ) • • • (1 -x n ) (1 -x)(1 -x 2 ) • • • (1 -x k )
where x is a variable.

b j ∈ © such that 1 ≤ b 1 ≤ • • • ≤ b k ≤ n.
Proposition 4.2. With the previous notation, for k > 0, we have

F (n, k, x) = s≥0 p(n, k, s)x s . Moreover, F (n, k, x) is a polynomial in x.
Proof. The generating function for the numbers p(n, k, s) is the two-variable series

ϕ(x, y) = s,k≥0 p(n, k, s)x s y k = 1 (1 -yx)(1 -yx 2 ) • • • (1 -yx n ) because of 1 (1 -yx)(1 -yx 2 ) • • • (1 -yx n ) = n i=1   ai≥0 y ai x iai   = a1≥0,... ,an≥0 y a1+•••+an x a1+2a2+•••+nan = k≥0,s≥0 p(n, k, s)y k x s
We can write ϕ(x, y)

= k≥0 ϕ k (x)y k with ϕ k (x) = s≥0 p(n, k, s)x s , for all k ≥ 0.
We can easily check that (1

-yx n+1 )ϕ(x, xy) = (1 -yx)ϕ(x, y), which implies (1 -x k )ϕ k (x) = (x -x n+k )ϕ k-1 (x) for k > 0, so that ϕ k (x) = (x -x n+k )(x -x n+k-1 ) • • • (x -x n+1 ) (1 -x k )(1 -x k-1 ) • • • (1 -x) ϕ 0 (x), for k > 0. But ϕ 0 (x) = 1. Hence ϕ k (x) = F (n, k, x) for k > 0.
To end, F is a polynomial in x since p(n, k, s) = 0 for large s.

We can now calculate N (n, k, r).

Theorem 4.3. With the previous notation, for k > 0, let F 0 , . . . , F n-1 be the n-

components of F (n, k, x), i.e. F (n, k, x) = n-1 r=0 x r F r (x n ). Then N (n, k, r) = F r (1). Proof. Write F (n, k, x) = j≥0 f j x j , f j ∈ . Then F r (x n ) = i≥0 f r+in x ni = i≥0 p(n, k, r + in)x ni and F r (1) = i≥0 p(n, k, r + in) = N (n, k, r).
The value of F r (1) gives then the value of N (n, k, r). Then

N (n, k, r) = 1 n n + k -1 k + 1 k d-1 l=1   cos 2lrπ d 1≤j≤k-1,d|jl n + j j   In particular, N (n, k, r) = 1 n n + k -1 k for any r ∈ {0, . . . , n -1} when d = 1.
Proof. We use the relation

F (n, k, x) = n-1 t=0 x t F t (x n ). We set α = e 2iπ n . For all r, m ∈ {0, . . . , n -1}, we have α -rm F (n, k, α m ) = n-1 t=0 α tm-rm F t (α nm ) = n-1 t=0 α (t-r)m F t (1).
Summing on m we get

n-1 m=0 α -rm F (n, k, α m ) = n-1 m=0 n-1 t=0 α (t-r)m F t (1) = n-1 t=0 n-1 m=0 α (t-r)m F t (1) = n-1 t=0 F t (1) n-1 m=0 α (t-r)m = n-1 t=0 F t (1)nδ rt = nF r (1) So we obtain F r (1) = 1 n n-1 m=0 α -rm F (n, k, α m ).
Now, we have to calculate u m = F (n, k, α m ) , where

F (n, k, x) = x k (1 -x n+k-1 )(1 -x n+k-2 ) • • • (1 -x n+1 )(1 -x n ) (1 -x k-1 )(1 -x k-2 ) • • • (1 -x)(1 -x k ) = x k x n -1 x k -1 k-1 j=1 x n+j -1 x j -1
which is a polynomial in x, so that F (n, k, α m ) has a sense.

Using L'Hopital's rule, we are going to calculate the values of x n -1

x k -1 and

x n+j -1 x j -1 for j = 1, . . . , k -1, at x = α m , m = 0, 1, . . . , n -1. • If n | mk, then α mn -1 α mk -1 = 0. If n|mk, then x n -1 x k -1 x=α m = lim x→α m nx n-1 kx k-1 = n k
. Moreover, in this case,

α mk = 1. Let j ∈ {1, . . . , k -1}. • If n | mj, then α m(n+j) -1 α mj -1 = 1. If n|mj, then x n+j -1 x j -1 x=α m = lim x→α m (n + j)x n+j-1 jx j-1 = n + j j .
To sum up, we obtain u m = 0 if n |mk and

u m = n k 1≤j≤k-1,n|jm n + j j if n|mk.
In particular,

u 0 = n k k-1 j=1 n + j j = n(n + 1) • • • (n + k -1) 1 • • • (k -1)k = n + k -1 k . Set d = gcd(n, k) and n = n d, k = k d so that gcd(n , k ) = 1. Then n|mk ⇔ n |mk ⇔ n |m. If n |m, then u m = 0 If n |m, set m = ln .
Then n|mj ⇔ n d|ln j ⇔ d|lj so that u ln = n k 1≤j≤k-1,d|lj n + j j .

This implies

N (n, k, r) = 1 n n + k -1 k + 1 n d-1 l=1 α -rln u ln = 1 n n + k -1 k + 1 n n k d-1 l=1   α -rln 1≤j≤k-1,d|jl n + j j   = 1 n n + k -1 k + 1 k d-1 l=1   e -2iπrln n 1≤j≤k-1,d|jl n + j j   which is a real number. So, we get N (n, k, r) = 1 n n + k -1 k + 1 k d-1 l=1   cos 2lrπ d 1≤j≤k-1,d|jl n + j j   .
In particular, if d = 1, we get N (n, k, r) = 1 n n + k -1 k since we have an empty sum.

By the way, keeping the same notation, the following corollary results : Proof. We use the formula of Theorem 4.4

N (n, k, r) = 1 n n + k -1 k + 1 k d-1 l=1   cos 2lrπ d 1≤j≤k-1,d|jl n + j j  
where d = gcd(n, k). If n = k, there is nothing to prove. So, assume n = k.

• It is easily seen that

1 n n + k -1 k = 1 k k + n -1 n .
• The result is gotten if we prove that

1 k 1≤j≤k-1,d|jl n + j j = 1 n 1≤j≤n-1,d|jl k + j j for any l ∈ such that 1 ≤ l ≤ d -1.
For such an l and a, b ∈ , set A(a, b) = {j ∈ | a ≤ j ≤ b and d|jl}. We may assume n > k. Then

1 n 1≤j≤n-1,d|jl k + j j = 1 n j∈A(1,n-1) k + j j = 1 n j∈A(1,n-1) (k + j) j∈A(1,n-1) j But A(1, n -1) = A(1, n -k -1) ∪ A(n -k + 1, n -1) ∪ {n -k} = A(k + 1, n -1) ∪ A(1, k -1) ∪ {k} It follows that j∈A(1,n-1) (k + j) = n   j∈A(1,n-k-1) (k + j)     j∈A(n-k+1,n-1) (k + j)   and j∈A(1,n-1) j = k   j∈A(k+1,n-1) j     j∈A(1,k-1) j   Moreover, j ∈ A(1, n -k -1) ⇔ k + j ∈ A(k + 1, n -1) since d|jl ⇔ d|(k + j)l.

So we get

j∈A(1,n-k-1)

(k + j) = j∈A(k+1,n-1)
j.

In the same way, we have j ∈ A(n

-k + 1, n -1) ⇔ t = k + j -n ∈ A(1, k -1) since d|jl ⇔ d|(k + j -n)l.
So we get j∈A(n-k+1,n-1)

(k + j) = t∈A(1,k-1) (n + t) = j∈A(1,k -1)
(n + j).

It follows that

1 n j∈A(1,n-1) k + j j = n   j∈A(k+1,n-1) j     j∈A(n-k+1,n-1) (k + j)   nk   j∈A(k+1,n-1) j     j∈A(1,k-1) j   = 1 k j∈A(n-k+1,n-1) (k + j) j∈A(1,k-1) j = 1 k j∈A(1,k-1) (n + j) j∈A(1,k-1) j = 1 k j∈A(1,k-1)
n + j j and we are done.

When gcd(n, k) > 1, we obtain a simpler evaluation for N (n, k, r). Then

N (n, k, r) = 1 n n + k -1 k + 1 k 1<δ≤d,δ|d ϕ(δ)µ(δ/ gcd(r, d)) ϕ(δ/ gcd(r, d)) n δ + k δ -1 n δ
where ϕ and µ are respectively the Euler function and the Möbius function.

In particular, we have 5. On the asymptotic behaviour of the number of distinct factorizations into atoms in a seminormal CK domain

N (n, k, 0) = 1 n n + k -1 k + 1 k 1<δ≤d,δ|d ϕ(δ) n δ + k δ -1 n δ and N (n, k, r) = 1 n n + k -1 n + 1 k 1<δ≤d,δ|d µ(δ) n δ + k δ -1
≤ j ≤ k ⇔ d δ divides j l δ and 1 ≤ j ≤ k ⇔ δ divides j and 1 ≤ j ≤ k ⇔ j = iδ and 1 ≤ i ≤ k δ . It follows that 1≤j≤k-1,d|jl n + j j = 1≤i≤ k δ -1 n δ + i i = n δ + k δ -1 n δ and σ δ = n δ + k δ -1 n δ 1≤l≤d -
As we saw in Section 3, we can restrict to the local case to evaluate the number of distinct factorizations into atoms of an element of a CK domain. To calculate this number for some special elements, we use results of Section 4. In particular, if x is an atom of R, then η(x m ) = 1 n! m n-1 + O(m n-2 ).

Proof. We can use Theorem 1.1 since its assumptions are satisfied by a CK domain. So η(x m ) is of the form η(x m ) = Am d + O(m d-1 ) for m ∈ * , where A ∈ , d ∈ , A > 0. Then, it is enough to find an equivalent of η(x m ). For any m ∈ n , we have v m ∈ U (R) and x m is associated to p mk , so that we can assume that n divides m to get A and d. In view of Theorem 3.11, we are led to calculate the number N (n, km, 0) = η(x m ) of solutions (a 1 , . . . , a n ) ∈ n of the system gotten in Theorem 4.4 :

(S) Because of l ≤ n -1 < n, we cannot have n|l, so that j = 1 and we have at most n -2 factors in the product.

             n i=1 a i = km (1)

It follows that

1≤j≤n-1,n|jl mk + j j ≤ (mk + n) n-2 = O(m n-2 ). As we have a sum of n -1 terms, we get that η(x m ) ∼ k n-1 n! m n-1 .

R 2 :

 2 R ] and I = [R : R ]. Then I 1 ∩ I 2 is a common ideal of R and R contained in I so that I = 0. Let a, b ∈ R with b = 0 and i a nonzero element of I. Then ia and ib are in R and hence a/b = ia/ib shows that R has the same quotient field as R . Moreover, R ⊂ R is a root extension. Then R is obviously the integral closure of R and is a semilocal PID. Since R /I 1 and R /I 2 are finite, this gives that R /(I 1 ∩ I 2 ) is also finite because isomorphic to a subring of R /I 1 × R /I 2 , so that R /I is finite. Moreover, we have | Max(R)| = | Max(R )| because R ⊂ R is a root extension. Applying Theorem 2.1, (2), we get that R is a CK domain with integral closure R . Corollary 2.4. Let D be a DVR with maximal ideal M such that D/M is finite. Let I be a nonzero ideal of D. The set of underrings of D with integral closure D and with conductor I has a least element and all these underrings are CK domains. Proof. Set E = {R underring of D | R = D, [R : D] = I}. Since D/M is finite, so is D/I. Indeed, if M = Dp for some atom p ∈ D, then I = Dp n , for some integer n and an obvious induction shows that |D/I| = |D/M | n . Consider R ∈ E. Then the finiteness of D/I implies the finiteness of R/I. So D is a finitely generated R-module because D/I is a finitely generated R/I-module. It follows that | Max(R)| = 1 and R is a CK domain by Theorem 2.1, (2).

Corollary 2 .

 2 4 has a new formulation in the seminormal case. Corollary 3.4. Let D be a DVR with maximal ideal M such that D/M is finite. The set of seminormal underrings of D with integral closure D is linearly ordered.

Proposition 3 . 5 .

 35 A seminormal CK domain is half-factorial. Proof. Let R be a seminormal CK domain and P ∈ Max(R). Then R P is a PVD by Proposition 3.1 and a CK domain by Proposition 2.2 (3). So R P is a HFD for any P ∈ Max(R) [2, Theorem 6.2]. The same holds for R [2, Theorem 6.1].

Proposition 3 . 7 .

 37 Let R be a local CK domain with integral closure R. Then R is seminormal if and only if R is a HFD and has |U ( R)/U (R)| nonassociate atoms.

xiu

  into elements of A is of the form x = w n i=1 p ai i , w ∈ U (R), a i ∈ ¦ . This gives x = w n i=1(u i p) ai = vp k ( * ), which implies, by identification in R, the equalities , w ∈ U (R), a i ∈ ¦ . We get then ia i . These two factorizations coincide if and only if a i = a i for each i. In this case, we have w = w .In U ( R)/U (R) we have the relation v = n i=1 ūiai = ūr where r ∈ {0, . . . , n -1} by ( * * ), that is r ≡ n i=1 ia i (mod n), or equivalently, r = n i=1

Remark 4 . 1 .

 41 It follows that p(n, k, s) is also the number of partitions of s into k summands

Theorem 4 . 4 .

 44 With the previous notation, set d = gcd(n, k) for k, n > 0.

Corollary 4 . 5 . 1 r=0NF

 451 With the previous notation, we haven-(n, k, r) = n + k -1 k .Proof. It is enough to sum the formula of Theorem 4.4. We can also get it in viewof r (1) = F (n, k, 1) = n + k -1 k . Remark 4.6. N (n, k, r) is a d-periodic function in r.Corollary 4.7. With the previous notation, we have N (n, k, r) = N (k, n, r).

Theorem 4 . 8 .

 48 With the previous notation, set d = gcd(n, k) for k, n > 0 and assume d > 1.



  For δ = gcd(l, d), we have d|jl and 1

  τ δ is also the real part of the Ramanujan sum c(r, δ) = 1≤l ≤δ-1,gcd(l ,δ)=1 e 2il rπ δ We have an explicite representation for c(r, δ) due to Hölder (see [13, Theorem 7.37, chapter 7, page 464]) by c(r, δ) = ϕ(δ)µ(m) ϕ(m) , where ϕ and µ are respectively the Euler function and the Möbius function, and where m = d/ gcd(d, rδ ) = δ/ gcd(r, δ).Since c(r, δ) is a real number, we obtain τ δ = c(r, δ) and the result is gotten.In particular, we have the following two special cases • r = 0 gives τ δ = ϕ(δ) and • gcd(r, d) = 1 with r > 0 gives τ δ = µ(δ).

Example 4 . 9 .

 49 We are going to find the distinct factorizations into atoms of an element of a local seminormal CK domain. Let ω = (1 + √ 5)/2 and consider the PID [ω]. Since 2 is inert in [ω], the ring S = [2ω] is weakly factorial and t-closed, and so is a generalized CK domain with conductor 2 [ω], a maximal ideal in [ω] [11, Theorem 2] and [12, Example (2), page 177]. Set R = S 2 [ω] , which is a local seminormal CK domain and 2 is an atom in R and R. In view of [12, Theorem 1.2, Proposition 2.1 and Proposition 3.1], we have |U ( R)/U (R)| = 3. Set x = 32 = 2 5 . By Theorems 3.11 and 4.4, we get ηgcd(3, 5) = 1. As ω is the fundamental unit of [ω], its class generates the cyclic group U ( R)/U (R). We can choose p = 2, p = 2ω, p = 2ω 2 for the nonassociate atoms of R. The different nonassociated factorizations of x into atoms of R are the following: x = p 5 = ω -3 p 3 p p = ω -3 p 2 p 3 = ω -6 p 2 p 3 = ω -6 pp 2 p 2 = ω -6 p 4 p = ω -9 p p 4 .

Theorem 5 . 1 .

 51 Let R be a local seminormal CK domain with integral closure R. Let Rp be the maximal ideal of R, with p ∈ R. Set n = |U ( R)/U (R)|. Let x = vp k , k ∈ * , v ∈ U ( R). The number of nonassociated factorizations of x m , m ∈ * into atoms of R is of the form η(x m ) = k n-1 n! m n-1 + O(m n-2 ).

  But, by Corollary 4.7, we have, since n = gcd(n, mk) N (n, km, 0) = N (km, n,

  particular, a CK domain R is seminormal if and only if R is t-closed. Let R be a local CK domain with integral closure R = R. Let Rp be the maximal ideal of R. Then R is seminormal if and only if U

	Proof. (1) ⇔ (2) is [9, Proposition 3.7]. (2) ⇔ (3) is [10, Corollary 3.4]. (2) ⇔ (4) comes from [9, Corollary 3.8 and Proposition 2.8]. Indeed, for any P ∈ Max(R), the conductor of R P is I P .
	We obtain as a corollary a first characterization of local seminormal (or t-closed)
	CK domains.
	Corollary 3.2.


Abdallah Badra
email: abdallah.badra@math.univ-bpclermont.fr

FROBENIUS NUMBER OF A LINEAR DIOPHANTINE EQUATION

We denote by N0 the set of nonnegative integers. Let d ≥ 1 and A = {a1, . . . , a d } a set of positive integers. For every n ∈ N0, we write s(n) for the number of solutions (x1, . . . ,

the Frobenius number of A. Let S(A) be the subsemigroup of (N0, +) generated by A. We set S ′ (A) = N0\S(A), N ′ (A) = CardS ′ (A) and N (A) = Card S(A)∩{0, 1, .., g(A)}. Let p be a multiple of lcm(A) and Fp(t) = d i=1 p a i -1 j=0 t ja i . We give an upper bound for g(A) and reduction formulas for g(A), N ′ (A) and N (A). Characterizations of these invariants as well as numerical symmetric and pseudo-symmetric semigroups in terms of Fp(t), are also obtained.

INTRODUCTION

We denote by N 0 (resp. N) the set of nonnegative (resp. positive) integers. Let d ∈ N and A = {a 1 , . . . , a d } ⊂ N. We set ρ = gcd(A) and l =lcm(A). For every n ∈ N 0 , we write s(n) for the number of solutions (x 1 , . . . , x d ) ∈ N d 0 of the equation a 1 x 1 +• • •+a d x d = n. We set g(A) = sup{n | s(n) = 0}∪{-1} the Frobenius number of A. Let S(A) be the subsemigroup of (N 0 , +) generated by A, S ′ (A) = N 0 \ S(A), N ′ (A) = Card S ′ (A) and N (A) = Card S(A) ∩ {0, 1, .., g(A)}. We say that S(A) is symmetric (resp. pseudo-symmetric) if gcd(A) = 1 and N ′ (A) = N (A) (resp. N ′ (A) = N (A) + 1). The generating function of the s(n) is

Φ(t) = 1 d i=1 (1 -t ai )
.

Indeed, we have

1 d i=1 (1 -t ai ) = d i=1 j≥0 t jai = n∈S(A) s(n)t n .
0 2000 mathematics subject classification 11D04, 13D40, 20M99

For p ∈ lN, we define the Frobenius polynomial

F p (t) = d i=1 p a i -1 j=0 t jai = (1 -t p ) d d i=1 (1 -t ai )
and we write

Φ(t) = F p (t) (1 -t p ) d . (1)
In theorem 3.1 we give formulas for g(A), N ′ (A) and N (A) in terms of F p (t). As a consequence we obtain an upper bound for the Frobenius number (corollary 3.2) which improves the upper bound given by Chrzastowski-Wachtel and mentioned in [START_REF] Raczunas | A Diophantine problem of Frobenius in terms of the least common multiple[END_REF]. A characterization of numerical symmetric and pseudo-symmetric semigroups (corollary 3.4) is also obtained. In theorem 3.7 we prove reduction formulas for g(A), N ′ (A) and N (A). The first one generalizes a Raczunas and Chrzastowski-Wachtel theorem [START_REF] Raczunas | A Diophantine problem of Frobenius in terms of the least common multiple[END_REF]. As a consequence (corollary 3.10) we obtain a generalization of a Rödseth formula [START_REF] Rödseth | On a linear Diophantine problem of Frobenius[END_REF]. It is known that the Hilbert function of a graded module over a polynomial graded ring as well as s(n) are numerical quasi-polynomial functions. In examples 4.9 and 4.10 we give a description of these functions in terms of the Frobenius polynomial.

PRELIMINARIES

Given Q(t) = j q j t j ∈ Q[t, t -1 ] and an integer p ≥ 1, there exists a unique sequence Q

0 , . . . , Q p-1 ∈ Q[t, t -1 ] such that Q(t) = p-1 r=0 t r Q r (t p ). Namely, Q r (t) =
k q r+pk t k . The Q r are called the p-components of Q. We denote by ω(Q) = inf{j | q j = 0} the valuation of Q and deg(Q) = sup{j | q j = 0} the degree of Q, with ω(0) = +∞ and deg(0) = -∞. The following invariants will be associated with

Q ω p (Q) = sup{ω(t r Q r (t p )) | 0 ≤ r ≤ p -1} the p-valuation of Q. δ p (Q) = inf{deg(t r Q r (t p )) | 0 ≤ r ≤ p -1} the p-degree of Q. Ω p (Q) = p-1 r=0 ω(Q r ). ∆ p (Q) = p-1 r=0 deg(Q r ).

Thus we have

ω p (Q) = +∞ = Ω p (Q) and δ p (Q) = -∞ = ∆ p (Q) if Q r = 0 for some r.
We fix an integer n ∈ Z and we set

Q(t) = t n Q(t -1 ). So we have Q = Q and deg(Q) + ω( Q) = n = deg( Q) + ω(Q) if Q = 0. ( 2
)
The p-components Q r of Q can be deduced from the p-components of Q. Namely, we write n = pλ + γ with 0 ≤ γ < p, so we get

Q(t) = p-1 r=0 t pλ+γ-r Q r (t -p ) = γ r=0 t γ-r (t p ) λ Q r (t -p ) + p-1 r=γ+1 t p+γ-r (t p ) λ-1 Q r (t -p ).
It follows from the uniqueness of the p-components that

Q r (t) = t λ Q γ-r (t -1 ) for 0 ≤ r ≤ γ (3) and Q r (t) = t λ-1 Q p+γ-r (t -1 ) for r > γ. (4)
So we obtain

Q r = 0 ⇔ Q γ-r = 0 for 0 ≤ r ≤ γ (5)
and

Q r = 0 ⇔ Q p+γ-r = 0 for r > γ. (6)
If Q r = 0, we also deduce from ( 2)-( 4) that

λ = deg( Q r ) + ω(Q γ-r ) when 0 ≤ r ≤ γ (7)
and

λ -1 = deg( Q r ) + ω(Q p+γ-r ) when r > γ. (8)
Moreover, writing

n = pλ + r + (γ -r) = p(λ -1) + r + (p + γ -r) we get n = deg(t r Q r (t p )) + ω(t γ-r Q γ-r (t p )) for 0 ≤ r ≤ γ and n = deg(t r Q r (t p )) + ω(t p+γ-r Q p+γ-r (t p )) for r > γ. Hence n = δ p ( Q) + ω p (Q) = δ p (Q) + ω p ( Q). (9)
Furthermore, using [START_REF] Fröberg | The Frobenius number of some semigroups[END_REF] and ( 8) we get

γ r=0 deg( Q r ) + ω(Q γ-r ) + p-1 r=γ+1 deg( Q r ) + ω(Q p+γ-r ) = (γ + 1)λ + (p -γ -1)(λ -1) = n -p + 1.
It follows that

∆ p ( Q) + Ω p (Q) = n -p + 1 = ∆ p (Q) + Ω p ( Q). (10)
Given m, j ∈ Z, we consider the following polynomials

N m,j (t) = 1 (m -1)! m-1 i=1 (t -j + i) if m > 1, N m,j (t) = 0 if m ≤ 0 and N 1,j (t) = 1. For Q(t) = j q j t j ∈ Q[t, t -1 ] such that Q(1) = 0, we define V m (Q, t) = j q j N m,j (t). Furthermore, let Q 0 , . . . , Q p-1 ∈ Q[t, t -1 ]
be the p-components of Q. We consider the polynomials U 0 , . . . , U p-1 ∈ Q[t, t -1 ] defined as follows U r = 0 if Q r = 0 and Q r (t) = (1t) ir U r (t) with U r (1) = 0 otherwise. For all 0 ≤ r ≤ p -1, we put m r = mi r and we define the function

H m (Q, .) : Z → Q by H m (Q, r + pk) = V mr (U r , k).
In order to illustrate these definitions we give the following examples.

EXAMPLE 2.1 Let Q(t) = F 12 = (1-t 12 ) 2 (1-t 2 )(1-t 3 ) = 1 + t 2 +
(t) = Q 2 (t) = Q 3 (t) = Q 4 (t) = Q 5 (t) = Q 7 (t) = (1 + t), Q 1 (t) = 2t and Q 6 (t) = Q 8 (t) = Q 9 (t) = Q 10 (t) = Q 11 (t) = 2.
We also have

Q(t) = t 19 Q(t -1 ) = Q(t). ω 12 (Q) = 13, δ 12 (Q) = 6, Ω 12 (Q) = 1, ∆ 12 (Q) = 7. N 2,0 (t) = t + 1, N 2,1 (t) = t. U r = Q r for all r.
V 2 (U r , t) = 2t + 1 for r ∈ {0, 2, 3, 4, 5, 7}, V 2 (U 1 , t) = 2t and V 2 (U r , t) = 2(t + 1) for r ∈ {6, 8, 9, 10, 11}. We obtain H 2 (Q, 12k + r) = 2k + 1 for r ∈ {0, 2, 3, 4, 5, 7}, H 2 (Q, 12k + 1) = 2k and H 2 (Q, 12k + r) = 2(k + 1) for r ∈ {6, 8, 9, 10, 11}.

EXAMPLE 2.2 Let Q(t) = F 6 (t) = 1 + t 2 + t 3 + t 4 + t 5 + t 7 = (1-t 6 ) 2
(1-t 2 )(1-t 3 ) . We take p = 6, n = 7 and m = 2. We obtain

ω 6 (Q) = 7, δ 6 (Q) = 0, Ω 6 (Q) = 1, ∆ 6 (Q) = 1. U r = Q r for all r. N 2,0 (t) = t + 1, N 2,1 (t) = t. V 2 (U r , t) = t + 1 for r ∈ {0, 2, 3, 4, 5} and V 2 (U 1 , t) = t. H 2 (Q, 6k + r) = k + 1 for r ∈ {0, 2, 3, 4, 5} and H 2 (Q, 6k + 1) = k. We observe that H 2 (F 6 , .) = H 2 (F 12 , .). Given Φ(t) ∈ Q[[t, t -1 ]], we write Φ(t) = n ϕ(n)t n and we introduce g(Φ) = sup{n | φ(n) = 0}. S ′ (Φ) = {n ≥ 0 | ϕ(n) = 0}. S(Φ) = {0 ≤ n ≤ g(Φ) | ϕ(n) = 0}. N ′ (Φ) = Card S ′ (Φ). N (Φ) = Card S(Φ). LEMMA 2.3 Given m ∈ Z and Q(t) = j q j t j ∈ Q[t, t -1 ] such that Q(1) = 0, we consider Φ(t) = n ϕ(n)t n the expansion of (1 -t) -m Q(t)
as a formal power series. Then, the following conditions hold

1. ϕ(n) = V m (Q, n) for all n > deg(Q) -m.
2. We suppose that m > 0 and Q(t) has nonnegative coefficients. Then,

(a) ϕ(n) = 0 ⇔ n < ω(Q). (b) g(Φ) = ω(Q) -1. (c) N ′ (Φ) = max{ω(Q), 0}. In particular, N ′ (Φ) = ω(Q) if Q(t) ∈ Q[t]. PROOF. 1. Suppose m > 0. We have Φ(t) = (1-t) -m Q(t) = ( j q j t j ) j≥0 j+m-1 m-1 t j . So ϕ(n) = n j=ω(Q) q j n-j+m-1 m-1
. Moreover, we have

n -j + m -1 m -1 = 1 (m -1)! m-1 i=1 (n -j + i) if n ≥ j. Hence ϕ(n) = V m (Q, n) if n ≥ deg(Q), in particular, the statement is true for m = 1. Now, suppose m > 1 and deg(Q) -m < n < deg(Q) then -m < n -deg(Q) ≤ n-j < 0 for all j such that n < j ≤ deg(Q). It follows that there exists 1 ≤ i ≤ m-1 such that n -j + i = 0 thus N m,j (n) = 0. So we can write V m (Q, n) = n j=ω(Q) q j N m,j (n) = n j=ω(Q) q j n -j + m -1 m -1 = ϕ(n). Furthermore, if m ≤ 0 then ϕ(n) = 0 for n > deg(Q) -m because Φ(t) ∈ Q[t, t -1 ] and deg(Q) -m = deg Φ(t). 2. Follows from the fact that ϕ(n) = n j=ω(Q) q j n-j+m-1 m-1 > 0 if n ≥ ω(Q) and ϕ(n) = 0 if n < ω(Q) THEOREM 2.4 Let m ∈ Z and p ∈ N. Given Q(t) = j q j t j ∈ Q[t, t -1 ] such that Q(1) = 0, we consider Φ(t) = n ϕ(n)t n the expansion of (1 -t p ) -m Q(t)
as a formal power series. Then the following conditions hold

1. ϕ(n) = H m (Q, n) for all n > deg(Q) -mp.
2. We suppose that m > 0 and Q(t) has nonnegative coefficients. Then,

(a) ϕ(pk + r) = 0 ⇔ k < ω(Q r ). (b) g(Φ) = ω p (Q) -p = deg(Q) -p -δ p ( Q) where Q(t) = t deg(Q) Q(t -1 ). (c) N ′ (Φ) = p-1 r=0 max{ω(Q r ), 0}. In particular, N ′ (Φ) = Ω p (Q) if Q(t) ∈ Q[t]. PROOF. We write Φ(t) = p-1 r=0 t r (1 -t p ) -m Q r (t p ) = p-1 r=0 t r (1 -t p ) -mr U r (t p ) = p-1 r=0 t r Φ r (t p ) where Φ r (t) = (1 -t p ) -mr U r (t p ) = k ϕ r (k)t k . It follows from lemma 2.3.1, that ϕ(pk + r) = ϕ r (k) = V mr (U r , k) for all k > deg(U r ) -m r . There- fore, ϕ(n) = H m (Q, n) for n > deg(Q) -pm because n = pk + r > deg(Q) -pm ≥ p(deg(Q r ) -m) + r ⇒ k > deg(Q r ) -m = deg(U r ) -m r . 2 (a) follows from lemma 2.3.2 (a). b) We have g(Φ) = max{pg(Φ r ) + r | 0 ≤ r ≤ p -1} = max{p(ω(Q r ) -1) + r | 0 ≤ r ≤ p -1} = ω p (Q) -p. Moreover, if Q r = 0 for all r we have ω p (Q) -p = deg(Q) -p -δ p ( Q) by (9). Since ω p (Q) = +∞ = -δ p ( Q) if Q r =
0 for some r, the equality is still true in this case. c) Follows from lemma 2.3.2 (c) LEMMA 2.5 Let ξ = e 2iπ p be a primitive p-th root of unity and

Q(t) = p-1 r=0 t r Q r (t p ) ∈ Q[t, t -1 ].
Then, the following conditions are equivalent

1. Q(ξ j ) = 0 for 0 < j < p. 2. Q(1) = pQ r (1) for 0 ≤ r ≤ p -1. PROOF. By successive substitutions of 1, ξ, . . . , ξ p-1 for t in Q(t) = p-1 r=0 t r Q r (t p ) we obtain a Vandermonde linear system p-1 r=0 ξ rj Q r (1) = Q(ξ j ) for j = 0, . . . , p-1. If Q(ξ) = • • • = Q(ξ p-1 ) = 0, the unique solution is Q r (1) = 1 p Q(1) for ev- ery 0 ≤ r ≤ p -1. Conversely, if Q(1) p is the common value of the Q r (1) then Q(1) p p-1 r=0 ξ rj = 0 = Q(ξ j ) for j = 1, . . . , p -1 LEMMA 2.
6 Let p, q, u be positive integers and

Q(t), K(t) ∈ Q[t, t -1 ] such that p = qu and K(t u ) = Q(t).
We denote by Q r (resp. K s ) the p-components of Q (resp. the q-components of K). Then,

1. Q su = K s and Q r = 0 for all r / ∈ uZ.
2. We set ξ = e 2iπ p , then the following conditions are equivalent (a) Q(ξ j ) = 0 for 0 < j < q.

(b) Q(ξ q ) = qQ r (1) = K(1) for all r ∈ uZ.

PROOF. We can write

Q(t) = K(t u ) = q-1 s=0 t us K s (t p ). It follows from the unique- ness of the Q r that Q su = K s for 0 ≤ s < q. Now, Q(ξ q ) = K(1) and Q(ξ j ) = K(α j ) with α = e 2iπ q
= ξ u . We apply lemma 2.5

For every p ∈ lN, we set

F p (t) = d i=1 p a i -1
j=0 t jai the Frobenius polynomial of A. We write F p,r for the p-components of F p . It is easy to see that for n = deg

(F p ) = pd - d i=1 a i , we have F p (t) = t n F p (t -1 ) = F p (t).
Let us write p = qρ and a i = b i ρ for all 1 ≤ i ≤ d, where ρ = gcd(A). So we can write F p (t) = K(t ρ ) with

K(t) = (1 -t q ) d d i=1 (1 -t bi )
.

Moreover, for 0 < j < q the number ξ j = e 2ijπ q is a root of d i=1 (1t bi ) of multiplicity < d because gcd(b 1 , .., b d ) = 1 whereas ξ j is a root of (1t q ) d of multiplicity = d, then K(ξ j ) = 0. It follows from lemma 2.6 that F p,r = K r ρ if r ∈ ρZ and F p,r = 0 otherwise. We also deduce that F p,r (1) = 1 q K(1)

= ρp d-1 d i=1 ai if r ∈ ρZ

FROBENIUS NUMBER AND NUMERICAL SEMIGROUPS

In the case of the Frobenius polynomial

F p we set ω p (F p ) = ω p (A), δ p (F p ) = δ p (A), Ω p (F p ) = Ω p (A), ∆ p (F ) = ∆ p (A).
THEOREM 3.1 For every p ∈ lN, we have

1. g(A) = ω p (A) -p = p(d -1) - d i=1 a i -δ p (A) = l(d -1) - d i=1 a i -δ l (A). 2. N ′ (A) = Ω p (A) = Ω l (A). 3. N (A) = ∆ p (A) -δ p (A) = ∆ l (A) -δ l (A).
PROOF. We see that for every p ∈ lN, the function proved by Chrzastowski-Wachtel and mentioned in [START_REF] Raczunas | A Diophantine problem of Frobenius in terms of the least common multiple[END_REF]. COROLLARY 3.4 Suppose gcd(A) = 1. Then the following conditions hold

Φ(t) = (1 -t p ) -d F p (t) = n s(n)t n is the generating function of the s(n) so g(A) = g(Φ).
1. S(A) is symmetric ⇔ ∆ p (A) = Ω p (A) + δ p (A) for some p ∈ lN ⇔ ∆ p (A) = Ω p (A) + δ p (A) for all p ∈ lN. 2. S(A) is peudo-symmetric ⇔ ∆ p (A) + 1 = Ω p (A) + δ p (A) for some p ∈ lN ⇔ ∆ p (A) + 1 = Ω p (A) + δ p (A) for all p ∈ lN.
We suppose gcd(A) = 1. Let q 1 , .., q d be positive integers such that for all 1 ≤ i ≤ d, q i is a divisor of gcd(a 1 , .., a i-1 , a i+1 , .., a d ). So gcd(q i , q j ) = 1 for i = j because gcd(A) = 1. We set q = d j=1 q j , qi = j =i q j , a i = b i qi and B = {b 1 , .., b d }. We have gcd(B) = 1 and l = lcm(A) = qlcm(B). For p ∈ lN, we write p = qu with u ∈ lcm(B)N. THEOREM 3.5 The following formulas hold

1. δ p (A) = qδ u (B). 2. ω p (A) = qω u (B) + d i=1 (q i -1)a i . 3. Ω p (A) = qΩ u (B) + 1 2 d i=1 (q i -1)a i -q + 1 . 4. ∆ p (A) = q∆ u (B) + 1 2 d i=1 (q i -1)a i -q + 1 .
In order to prove this theorem we need a lemma. LEMMA 3.6 Let q and c be two positive integers, B = {b 1 , .., b d-1 , c}, and A = {a 1 , .., a d-1 , c} where a 1 = qb 1 , .., a d-1 = qb d-1 . Suppose gcd(A) = 1 and choose p ∈ lcm(B)N so gcd(q, c) = 1 and qp ∈ lcm(A)N. Then, the following formulas hold

1. δ qp (A) = qδ p (B).
2. ω qp (A) = qω p (B) + (q -1)c. [START_REF] Bourbaki | Algèbre commutative. Chapitre[END_REF]. Ω qp (A) = qΩ p (B) + 1 2 (q -1)(c -1). 4. ∆ qp (A) = q∆ p (B) + 1 2 (q -1)(c -1).

PROOF. We denote by

F (t) = F p (t) = (1 -t p ) d (1 -t c ) d-1 i=1 (1 -t bi ) = p-1 r=0 t r F r (t p )
the Frobenius polynomial associated with B and

G(t) = G qp (t) = (1 -t qp ) d (1 -t c ) d-1 i=1 (1 -t ai ) = qp-1 s=0 t s G s (t qp )
the Frobenius polynomial associated with A. We see that

G(t) = (1 + t c + .. + t (q-1)c )F (t q ) = (1 + t c + .. + t (q-1)c ) p-1 r=0 t q r F r (t qp ).
So we obtain

G(t) = k=ic+jq 0≤i≤q-1 t k F j (t qp ) = 0≤k=ic+jq≤qp-1 0≤i≤q-1 t k F j (t qp ) + k>qp-1 0≤i≤q-1 t k-qp t qp F j (t qp )
By identification we deduce that G s (t qp ) = F j (t qp ) when s = ic + jq and G s (t qp ) = t qp F j (t qp ) when s = ic + jqqp = ic -(pj)q. In particular, we have deg(G s ) = deg(F j ) and ω(G s ) = ω(F j ) when s = ic + jq and deg(G s ) = 1 + deg(F j ) and ω(G s ) = 1 + ω(F j ) when s = ic + jqqp. Therefore, for all s which can be written in the form s = ic + jq we get deg(t s G s (t qp )) = ic + jq + qp deg(F j ) and ω(t s G s (t qp )) = ic + jq + qpω(F j ). For all s which can be written in the form s = ic + jqqp, we get deg

(t s G s (t qp )) = ic + jq -qp + qp(1 + deg(F j )) = ic + jq + qp deg(F j ) and ω(t s G s (t qp )) = ic + jq -qp + qp(1 + ω(F j ). It follows that δ qp (G) = min{ic + jq + qp deg(F j )} = q min{j + p deg(F j )} = qδ p (F ) and ω qp (G) = max{ic+jq+qpω(F j ) } = (q-1)c+q max{j+pω(F j ) } = qω p (F )+(q-1)c.
We also have

Ω qp (G) = s=ic+jq ω(G s ) + s=ic+jq-qp ω(G s ) = s=ic+jq ω(F j ) + s=ic-jq (ω(F j ) + 1) = qΩ p (F ) + N ′ (c, q) = qΩ p (F ) + 1 2 (q -1)(c -1). It follows that ∆ qp (G) = Ω qp (G) + δ qp (G) = q(Ω p (F ) + δ p (F )) + 1 2 (q -1)(c -1)
PROOF OF THEOREM 3.5. By induction on the number h = dk + 1 such q 1 = q 2 = .. = q k-1 = 1. If h = 1 the result is given by lemma 3.6. Suppose that the result is true when q 1 = q 2 = .. = q k-1 = 1. We choose p ∈lcm(A)N and we set v = p q k , t i = q i for i = k and t k = 1. Then, we get ti = qi q k for all i = k, tk = qk and t = q q k . We also have ai q k = bi qi q k = b i ti for all i = k and a k = b k tk . We put c i = b i ti for all i and C = {c 1 , .., c d }, thus a i = q k c i for all i = k and a k = c k . It follows from lemma 3.6 and the induction hypothesis that 1)

δ p (A) = q k δ v (C) = q k tδ u (B) = qδ u (B). 2) ω p (A) = q k ω v (C) + (q k -1)c k = q k { tω u (B) + d i=1 (t i -1)c i } + (q k -1)c k = qω u (B) + d i=1 (q i -1)a i . 3)Ω p (A) = q k Ω v (C) + 1 2 (q k -1)(a k -1) = q k { tΩ u (B) + 1 2 ( d i=1 (t i -1)c i -t + 1)} + 1 2 (q k -1)(a k -1) = qΩ u (B) + 1 2 d i=1 (q i -1)a i -q + 1 . 4) ∆ p (A) = Ω p (A) + δ p (A) = q∆ u (B) + 1 2 d i=1 (q i -1)a i -q + 1 THEOREM 3.7
The following formulas hold

1. g(A) = qg(B) + d i=1 (q i -1)a i . 2. N ′ (A) = qN ′ (B) + 1 2 d i=1 (q i -1)a i -q + 1 . 3. N (A) = qN (B) + 1 2 d i=1 (q i -1)a i -q + 1 .
REMARK 3.8 In formula 1) if we take q 1 = .. = q d-1 = 1 then we obtain a Brauer and Shockley formula [START_REF] Brauer | On a problem of Frobenius[END_REF] and if we take q i = gcd(A\{a i }) for all i, we obtain a Raczunas and Chrzastowski-Wachtel formula [START_REF] Raczunas | A Diophantine problem of Frobenius in terms of the least common multiple[END_REF]. Moreover formula 2) is a generalization of a Rödseth formula [START_REF] Rödseth | On a linear Diophantine problem of Frobenius[END_REF] which is obtained for q 1 = .. = q d-1 = 1. THEOREM 3.9 The following conditions hold 1. S(A) is symmetric if and only if S(B) is symmetric.

2. If q > 1 then S(A) is not pseudo-symmetric. COROLLARY 3.10 Suppose there exists i such that b i = 1 (i.e. a i = qi ). Then, S(A) is symmetric and we have

1. (a) g(A) = d i=1 (q i -1)a i -q. (b) N (A) = N ′ (A) = 1 2 ( d i=1
(q i -1)a iq + 1). 2. Suppose, in addition, that b i = 1 (i.e. a i = qi ) for all i. Then, we have

(a) g(A) = l(d -1) -d i=1 a i . (b) N (A) = N ′ (A) = 1 2 (l(d -1) - d i=1 a i + 1). PROOF. Since 1 ∈ B, we have S(B) = N 0 then g(B) = -1 and N (B) = N ′ (B) = 0. So 1.
follows from theorem 3.7. To prove 2., we observe that q i a i = q = l = lcm(A) if a i = qi for all i

COROLLARY 3.11 Let b, d, h, v be positive integers such that b ≥ d ≥ 2 and gcd(b, v) = 1. Let B = {b, hb + v, .., hb + (i -1)v, .., hb + (d -1)v}, ((b 1 , .., b d ) is called an "almost" arithmetic sequence). Then, S(A) is symmetric ⇔ S(B) is symmetric ⇔ d = 2 or b ≡ 2 mod(d -1).
PROOF. We write b -1 = β(d -1) + α with 0 ≤ α < d -1, and we use the following known formulas g

(B) = h b-2 d-1 + h -1 b + bv -v [8] and N ′ (B) = 1 2 {(b -1)(hβ + v + h -1) + hα(β + 1)} [11]
P r ∈ Q[t] such that d = sup{deg(P r ) | 0 ≤ r ≤ p -1}.
A quasi-polynomial P is said to be uniform if all the P r have the same degree d and the same leading coefficient c(P ). Given a function h : Z → Q and r ∈ Z, we define h r : Z → Q, k → h(pk + r). We say that h is a quasi-polynomial function if there exists a quasi-polynomial P = (P 0 , . . . , P p-1 ) such that h r (k) = P r (k) for all k ≫ 0 and 0 ≤ r ≤ p. We also say that h is P -quasi-polynomial. It is easily seen that a quasi-polynomial function h has a minimal period and every period of h is a multiple of this minimal period. Furthermore, for a fixed period p, h is a P -quasi-polynomial for a unique sequence P = (P 0 , . . . , P p-1 ). A P -quasipolynomial h is said to be uniform if P is uniform. We write deg(h) = deg(P ) and c(h) = c(P ). We denote by F (Z) the set of all functions h : Z → Q. For every integer i ≥ 0 we consider the operators E i and ∆ i , which act as follows:

(E i h)(n) = h(n + i), (∆ i h)(n) = h(n + i) -h(n).
We set E 0 = I, E 1 = E and ∆ 1 = ∆ so ∆ = E -I, ∆ 0 = 0 and ∆ i = E i -I. For a ≥ 0 and n ≥ 1, we have

(I + E a + • • • + E (n-1)a ) • (E a -I) = E na -I = ∆ na .
LEMMA 4.2 Given h ∈ F (Z), then the following identities hold

1. (E pi h) r = E i h r for i ≥ 0. 2. (∆ m p h) r = ∆ m h r for m ≥ 0. PROOF. 1. We write (E pi h) r (k) = (E pi h)(pk + r) = h(p(k + i) + r) = h r (k + i) = (E i h r )(k). 2. We have ∆ m p = (E p -I) m = m i=0 (-1) m-i m i E pi . Therefore, (∆ m p h) r = m i=0 (-1) m-i m i (E pi h) r = m i=0 (-1) m-i m i E i h r = (E -I) m h r = ∆ m h r PROPOSITION 4.3 A function h ∈ F (Z)
is quasi-polynomial of period p and degree d if and only if there exists (c 0 , . . . , c p-1 ) = (0, . . . , 0) such that (∆ d p h) r (k) = c r for all k ≫ 0 and 0 ≤ r ≤ p -1.

PROOF. Follows from lemma 4.2 and [6, lemma 4.

1.2] COROLLARY 4.4 For h ∈ F (Z) , if d i=1 (E ai -I)(h)(n) = 0 for n ≫ 0, then h is quasi-polynomial of period p ∈ lN and degree < d. PROOF. Follows from ∆ d p = (E p -I) d = ( d i=1 ( p a i -1 j=0 E jai )) • ( d i=1 (E ai -I) EXAMPLE 4.5 Given m ∈ Z and Q(t) ∈ Q[t, t -1 ] such that Q(1) = 0. The function H m (Q, .
) associated with Q is a P -quasi-polynomial of period p, where P = (P 0 , .., P p-1 ) is given by P r = V mr (U r , .).

REMARK 4.6 Suppose m > 0. Then, we have

1. deg(H m (Q, .)) = m -1.
2. m r > 0 ⇒ deg(P r ) = m r -1 and c(P r ) = Ur(1) (mr-1)! .

If

Q(1) = pQ r (1) = 0 for all 0 ≤ r ≤ p -1, then H m (Q, .) is uniform of degree m -1 and its leading coefficient is c(H m (Q, .)) = Qr (1) (d-1)! = Q(1) p(d-1)! .
4. Suppose p = qu and there exists

K(t) ∈ Q[t, t -1 ] such that K(t u ) = Q(t), we set ξ = e 2iπ p .
If Q(ξ j ) = 0 for 0 < j < q and Q(ξ q ) = 0. Then, the following conditions hold (a) P r = 0 if r / ∈ uZ.

(b) deg(P r ) = m -1 and c(P r ) = Qr (1) (m-1)! = Q(ξ q ) p(m-1)! if r ∈ uZ.
PROPOSITION 4.7 Let m > 0 be an integer and h ∈ F (Z) be a function satisfying h(n) = 0 for n ≪ 0. We consider Φ(t) = n h(n)t n . Then, the following conditions are equivalent 1. h is quasi-polynomial of period p and of degree m -1.

(1t

p ) m Φ(t) = Q(t) ∈ Z[t, t -1 ] and there exists a p-component Q r of Q such that Q r (1) = 0.
3. There exists a unique

Q(t) ∈ Z[t, t -1 ] such that degH m (Q, .) = m -1 and H m (Q, n) = h(n) for n > deg(Q) -pm.
In particular, h is a uniform quasi-polynomial function of period p and degree m-1 if and only if there exists a unique For instance, the number of solutions of the equation 2x 1 + 3x 2 = n is s(n) = H 2 (F 6 , n) (see example 2.2). EXAMPLE 4.10 Let R 0 be a commutative ring and R = R 0 [t 1 , . . . , t d ]. Suppose that R is Z-graded in such a way that every element of R 0 is homogeneous of degree zero and each t i is homogeneous of degree a i . Let M = ⊕ n∈Z M n be a finitely generated graded R-module such that the length l R0 (M n ) of each M n as an R 0 -module is finite. The numerical function H 0 (M, .) : Z → Z, n → l R0 (M n ) is called the Hilbert function of M . The iterated cumulative Hilbert functions are defined by H j+1 (M, n) = n i=0 H j (M, i). The Poincaré series of M is denoted by P M (t) = n H 0 (M, n)t n . By the Hilbert-Samuel theorem [3, 4.2 Theorem 1] there exists Q M (t) ∈ Z[t, t -1 ] such that Q M (1) = 0 and P M (t) = QM (t) d i=1 (1-t a i ) . Moreover, it is known that H 0 (M, .) is quasi-polynomial [START_REF] Bavula | Identification of the Hilbert function and Poincaré series, and the dimension of modules over filtred rings[END_REF]. Given p ∈ lN and j ≥ 1 we set a d+1 = • • • = a d+j = 1. So the generating function of the H j (M, .) is

Q(t) ∈ Z[t, t -1 ] such that Q(1) = 0, Q(e j 2iπ p ) = 0 for all 0 < j < p and H m (Q, n) = h(n) for n > deg(Q) -pm. In this case, the leading coefficient is c(h) = Q(1) p(m-1)! . PROOF. Assume 1. and set Φ r (t) = n h r (n)t n for all 0 ≤ r ≤ p -1. It follows from [6, 4.1.7] that (1 -t) m Φ r (t) = Q r (t) ∈ Z[t, t -1 ]. Since deg(h) = m -1 ≥ 0, there exists 0 ≤ r ≤ p -1 such that Q r (1) = 0. Setting Q(t) = p-1 r=0 t r Q r (t p )
n H j (M, n)t n = P M (t) (1 -t) j = Q M (t) d+j i=1 (1 -t ai )
.

It follows from corollary 4.8 that H j (M, n) = H d+j (Q M F p , n) for all j ≥ 0 and n > deg(Q M )a i . Moreover, if j > 0 or j = 0 and gcd(A) = 1 then H j (M, .) is a uniform quasi-polynomial function of degree d + j -1 and of leading coefficient c(H j (M, n)) = QM (1)p d+j-1

(d+j-1)! d i=1 ai .

1 . 3 . 4 .

 134 1. follows from theorem 2.4.2 (b). 2. follows from theorem 2.4.2 (c). 3. is a consequence of (10) COROLLARY 3.2 For every p ∈ lN, we haveg(A) = p(d -1) -d i=1 a i if and only if δ p (A) = 0.2. g(A) = +∞ if and only if ρ > 1. If ρ = 1, we have the following upper bound for the Frobenius number g(A) ≤ l(d -1) -If there exists h such that 1 ≤ h ≤ d and gcd(a 1 , . . . , a h ) = 1 then g(A) ≤lcm(a 1 , . . . , a h )(h -1) -h i=1 a i . REMARK 3.3 The upper bound we give in 3) improves the following inequality g(A) ≤ l(d -1)

EXAMPLE 3 .

 3 12 Let A = {150, 462, 840, 1365} = {5(2 × 3 × 5), 11(2 × 3 × 7), 12(2 × 5 × 7), 13(3 × 5 × 7)}. We set q 1 = 7, q 2 = 5, q 3 = 3, q 4 = 2 and B = {5, 11, 12, 13}. This is an almost arithmetic sequence with b = 5, v = 1, h = 2, d = 4. We see that b ≡ 2 mod(d -1) hence S(B) is symmetric and we have g(B) = 19, N ′ (B) = N (B) = 10. Moreover, it follows from theorem 3.9 that S(A) is symmetric. Using theorem 3.7 we obtain g(A) = 210 × 19 + 6 × 150 + 4 × 462 + 2 × 840 + 1365 = 9783. N ′ (A) = N (A) = 210 × 10 + 1 2 (6 × 150 + 4 × 462 + 2 × 840 + 1365 -210 + 1) = 4892. 4 QUASI-POLYNOMIALS DEFINITION 4.1 A quasi-polynomial P of period p and degree d is a sequence P = (P 0 , . . . , P p-1 ) with

d i=1 ( 1 -

 1 t ai ) = (1t p ) -d N (t)F p (t)as a formal Laurent series. Then,h(n) = H d (N F p , n) for n > deg(N ) -d i=1 a i . Moreover, if in addition gcd(A) = 1, then h = H d (N F p , .) is uniform of degree d -1and its leading coefficient is c(h) = N (1)p d-1 (d-1)! d i=1 ai . EXAMPLE 4.9 We write s(n) for the number of solutions of the equation a 1 x 1 + .. + a d x d = n in nonnegative integers we get s(n) = H d (F p , n) for all n ≥ 0 where p ∈ lN. In particular, if gcd(A) = 1 then n → s(n) is a uniform quasi-polynomial function of degree d -1 and of leading coefficient c(s) = p d-1 (d-1)! d i=1 ai .

  t 3 + t 4 + t 5 + 2t 6 + t 7 + 2t 8 + 2t 9 + 2t 10 + 2t 11 + t 12 + 2t 13 + t 14 + t 15 + t 16 + t 17 + t 19 . We take p = 12, n = 19 and m = 2. We write Q(t) = (1 + t 12 ) + t(2t 12 ) + t 2 (1 + t 12 ) + t 3 (1 + t 12 ) + t 4 (1 + t 12 ) + t 5 (1 + t 12 ) + 2t 6 + t 7 (1 + t 12 ) + 2t 8 + 2t 9 + 2t 10 + 2t 11 . We see that the 12-components of Q(t) are Q 0

  we deduce 2. 2. ⇒ 3. follows from theorem 2.4. 3. ⇒ 1. follows from the definition of H m . The particular case follows from lemma 2.6 and remark 4.6 COROLLARY 4.8 Let N (t) be an element of Z[t, t -1 ] such that N (1) = 0 and p ∈ lN. We set Φ(t) = n h(n)t n the expansion of

	N (t)


Fabien Lotte
email: fprlotte@i2r.a-star.edu.sg

Cuntai Guan
email: ctguan@i2r.a-star.edu.sg

Spatially Regularized Common Spatial Patterns for EEG Classification

In this paper, we propose a new algorithm for Brain-Computer Interface (BCI): Spatially Regularized Common Spatial Patterns (SRCSP). SRCSP is an extension of the famous CSP algorithm which includes spatial a priori in the learning process, by adding a regularization term which penalizes spatially non smooth filters. We compared SRCSP and CSP algorithms on data of 14 subjects from BCI competitions. Results suggested that SRCSP can improve performances, around 10% more in classification accuracy, for subjects with poor CSP performances. They also suggested that SRCSP leads to more physiologically relevant filters than CSP.

Introduction

Brain-Computer Interfaces (BCI) are communication systems which enable users to send commands to computers by using brain activity only, this activity being generally measured by ElectroEncephaloGraphy (EEG) [START_REF] Pfurtscheller | Motor imagery and direct brain-computer communication[END_REF]. Most BCI are designed according to a pattern recognition approach, i.e., by extracting features from EEG, and by classifying these features to identify the user's mental state [START_REF] Pfurtscheller | Motor imagery and direct brain-computer communication[END_REF]. Common Spatial Patterns (CSP) is a feature extraction method to learn spatial filters maximizing the discriminability of two classes [START_REF] Blankertz | Optimizing spatial filters for robust EEG single-trial analysis[END_REF]. CSP has been proven to be one of the most efficient algorithms for BCI, notably during BCI competitions [START_REF] Blankertz | The BCI competition III: Validating alternative approaches to actual BCI problems[END_REF].

However, CSP is known to be highly non-robust to noise and outliers [START_REF] Grosse-Wentrup | Beamforming in noninvasive braincomputer interfaces[END_REF][START_REF] Reuderink | Robustness of the common spatial patterns algorithm in the BCI-pipeline[END_REF]. Moreover, despite being a spatial filter, CSP completely ignores the spatial location of the EEG electrodes. To overcome these drawbacks, Grosse-Wentrup et al have proposed to use beamforming in order to learn CSP-like spatial filters which maximize the variance of the signals originating from a predefined Region Of Interest (ROI) while minimizing the variance of the signals originating outside this ROI [START_REF] Grosse-Wentrup | Beamforming in noninvasive braincomputer interfaces[END_REF]. Despite the good results obtained, this method has a major limitation: it requires a strong a priori with the loca-tion and extent of the ROI involved.

In this paper, we propose a Spatially Regularized CSP (SRCSP) which incorporates spatial information in a generic way. Contrary to beamforming, SRCSP does not require additional a priori and can be used to classify any kind of mental states. SRCSP aims at regularizing the CSP objective function by penalizing filters which are not spatially smooth, i.e., for which neighboring electrodes have very different weights. Indeed, from a neurophysiological point of view, neighboring electrodes should measure similar brain signals and as such have a similar contribution in the spatial filter. It is expected that such a priori would help finding relevant spatial filters, even with noisy or few training EEG signals. Other domains also took advantage of spatial a priori [START_REF] Xiang | Boosting with spatial regularization[END_REF][START_REF] Cai | Learning a spatially smooth subspace for face recognition[END_REF], which inspired the design of SRCSP.

This paper is organized as follows: Section 2 describes the CSP algorithm as well as the SRCSP algorithm we propose. Then, Section 3 describes the EEG data used for evaluation. Finally, Sections 4 and 5 present the results and conclude the paper, respectively.

Methods

CSP algorithm

CSP aims at learning spatial filters which can maximize the variance of band-pass filtered EEG signals from one class while minimizing the variance of EEG signals from the other class [START_REF] Blankertz | Optimizing spatial filters for robust EEG single-trial analysis[END_REF][START_REF] Ramoser | Optimal spatial filtering of single trial EEG during imagined hand movement[END_REF]. As the variance of EEG signals filtered in a given frequency band corresponds to the signal power in this band, CSP aims at achieving optimal discrimination for BCI based on band power features [START_REF] Ramoser | Optimal spatial filtering of single trial EEG during imagined hand movement[END_REF]. Formally, CSP uses the spatial filters w which extremize the following function:

J(w) = w T X T 1 X 1 w w T X T 2 X 2 w = w T C 1 w w T C 2 w (1)
where T denotes transpose, X i is the data matrix for class i (with the training samples as rows and the EEG electrodes as columns) and C i is the spatial covariance matrix of the EEG signals from class i, assuming a zero mean for the EEG signals. Note that this last assumption is generally met as EEG signals are usually bandpass filtered. This optimization problem is generally solved by jointly diagonalizing the two matrices C 1 and

(C 1 + C 2 ) [2, 8
]. An alternative but equivalent way to solve this optimization problem is obtained by first observing that the function J(w) remains unchanged if the filter w is rescaled. Indeed J(k × w) = J(w), with k a real constant, which means the rescaling of w is arbitrary. As such, extremizing J(w) is equivalent to extremizing w T C 1 w subject to the constraint w T C 2 w = 1 as it is always possible to find a rescaling of w such that w T C 2 w = 1. Using the Lagrange multiplier method, this constrained optimization problem amounts to extremizing the following function:

L(λ, w) = w T C 1 w -λ(w T C 2 w -1) (2)
The filters w extremizing L are such that the derivative of L with respect to w equals 0:

∂L ∂w = 2w T C 1 -2λw T C 2 = 0 ⇔ C 1 w = λC 2 w ⇔ C -1 2 C 1 w = λw
We then obtain a standard eigenvalue problem. Therefore, the spatial filters extremizing Equation 1 are the eigenvectors of M = C -1 2 C 1 which correspond to its largest and lowest eigenvalues.

Spatially Regularized CSP algorithm

In this paper we propose the SRCSP algorithm, in order to include spatial information into the learning process of the CSP. More particularly, we would like to obtain spatially smooth filters w. Indeed, as mentioned earlier, from a neurophysiological point of view, neighboring neurons tend to have similar functions, which supports the idea that neighboring electrodes should measure similar brain signals (if the electrodes are close enough to each other). To ensure spatial smoothness of the filters w, we add a penalty term P (w) to the objective function J(w) of the classical CSP:

J P1 (w) = w T C 1 w w T C 2 w + αP (w) (3)
P (w) is a function measuring the spatial smoothness of the spatial filters w. The spatially smoother w, the lower P (w). Therefore, to maximize J P1 (w), we need to minimize P (w), hence ensuring spatially smooth filters. The variable α is a user-defined positive constant which defines the desired level of filter smoothness (the higher α, the spatially smoother the filters). Here, we use a Laplacian penalty of the form P (w) = w T Kw with K = D -G, as in [START_REF] Xiang | Boosting with spatial regularization[END_REF]. G is a Gaussian kernel such that

G ij = exp(-1 2 vi-vj 2 r 2
), with v i being a vector containing the 3D coordinates of the i th electrodes. The hyperparameter r defines how far two electrodes can be to be still considered as close to each other. D is a diagonal matrix such as 2 (see, e.g., [START_REF] Cai | Learning a spatially smooth subspace for face recognition[END_REF]), this term will be large for non-smooth filters, i.e., for filters in which neighboring electrodes have very different weights. With such a penalty term, (3) becomes:

D ii = j G ij . As w T (D -G)w = i,j G ij (w i -w j )
J P1 (w) = w T C 1 w w T C 2 w + αw T Kw = w T C 1 w w T (C 2 + αK)w
In this case, the Lagrangian is as follows:

L P (λ, w) = w T C 1 w -λ(w T (C 2 + αK)w -1) (4)
By following the same approach as previously (see Section 2.1), we obtain the following eigenvalue problem:

(C 2 + αK) -1 C 1 w = λw (5)
Thus, maximizing J P1 (w) consists in taking the eigenvectors corresponding to the largest eigenvalues of M 1 = (C 2 + αK) -1 C 1 as the filters w. With CSP, the eigenvectors corresponding to both the largest and smallest eigenvalues of M (see Section 2.1) are taken as spatial filters, as they respectively maximize and minimize Equation 1 [START_REF] Blankertz | Optimizing spatial filters for robust EEG single-trial analysis[END_REF]. However, for SRCSP, we cannot use the eigenvectors corresponding to the lowest eigenvalues of M 1 , as they will minimize Equation 3, and as such will maximize the penalty term, i.e., they will lead to highly non smooth filters. Therefore, in order to obtain the filters which maximize C 2 while minimizing C 1 , we also need to maximize the following objective function, which is the counterpart of Equation 3:

J P2 (w) = w T C 2 w w T C 1 w + αP (w) (6)
which is simply achieved by taking the eigenvectors corresponding to the largest eigenvalues of M 2 = (C 1 + αK) -1 C 2 as the filters w. In other words, with SRCSP, the spatial filters used are the eigenvectors corresponding to the largest eigenvalues of M 1 and M 2 . SRCSP has two hyperparameters: r which defines the size of the neighborhood considered for smoothing, and α which defines the level of spatial smoothness the filters should reach. In this work, we used as their optimal values, the ones which maximized the 10-fold cross validation accuracy on the training set, by using Linear Discriminant Analysis (LDA) [START_REF] Lotte | A review of classification algorithms for EEG-based brain-computer interfaces[END_REF] as the classifier.

EEG data sets for evaluation

To assess the proposed SRCSP, we compared it with the classical CSP approach on EEG data of 14 subjects, from 2 publicly available data sets of BCI competitions.

Data set IVa, BCI competition III

Data set IVa, from BCI competition III [START_REF] Blankertz | The BCI competition III: Validating alternative approaches to actual BCI problems[END_REF], contains EEG signals from 5 subjects, who performed right hand and foot Motor Imagery (MI), i.e., imagination of right hand and foot movements [START_REF] Pfurtscheller | Motor imagery and direct brain-computer communication[END_REF]. EEG were recorded using 118 electrodes. A training set and a testing set were available for each subject. The size of these sets was different for each subject. More precisely, 280 trials were available for each subject, among which 168, 224, 84, 56 and 28 composed the training set for subject A1, A2, A3, A4 and A5 respectively, the remaining trials composing the test set.

Data set IIa, BCI competition IV

Data set IIa from BCI competition IV 1 (provided by the Graz group [START_REF] Naeem | Seperability of four-class motor imagery data using independent components analysis[END_REF]) comprises EEG signals from 9 subjects who performed left hand, right hand, foot and tongue MI. The EEG signals were recorded using 22 electrodes. For the purpose of this study, only EEG signals corresponding to left and right hand MI were used.

A training and a testing set were available for each subject, both sets containing 72 trials for each class.

For both data sets, EEG signals were band-pass filtered in the 8-30 Hz frequency band using a 5 th order Butterworth filter. Indeed, this frequency band contains the main frequencies involved in MI [START_REF] Pfurtscheller | Motor imagery and direct brain-computer communication[END_REF]. In this work, we considered the discrete classification of the trials, i.e., we assigned a class to each trial and not to each trial sample. For both data sets, for each trial, we extracted the features from the time segment located from 0.5s to 2.5s after the cue instructing the subject to perform MI (as done by the winner of BCI competition IV, data set 2a). With both CSP and SRCSP, we used the 3 most discriminative pairs of filters for feature extraction, as recommended in [START_REF] Blankertz | Optimizing spatial filters for robust EEG single-trial analysis[END_REF]. In other words, we used the filters corresponding to the 3 largest and 3 smallest eigenvalues of M for CSP, and the filters corresponding to the 3 1 http://ida.first.fhg.de/projects/bci/ competition\_iv/ largest eigenvalues of M 1 and the 3 largest eigenvalues of M 2 for SRCSP (See Section 2).

Results and discussion

For each subject, the CSP/SRCSP filters were learnt on the training set available. The log-variances of the spatially filtered EEG signals were then used as the input features to an LDA classifier, one of the most popular and efficient classifier for BCI design [START_REF] Lotte | A review of classification algorithms for EEG-based brain-computer interfaces[END_REF]. Table 1 report the classification accuracies obtained when classifying the EEG signals from the test sets.

On average, SRCSP gave better classification accuracies (mean: 78.7 ± 13.9) than CSP (mean: 73.1 ± 17.6). However, this difference is not significant at the 5% level (but nearly: p = 0.07 with a two-tailed paired t-test), which might be due to the sample size. Nevertheless, results suggest that SRCSP does increase the classification accuracy specifically for subjects with poor CSP performances but not for those with already good performances. Indeed, for subjects with poor CSP accuracies (e.g., A3, A5, B2 and B5), using SRCSP leads to dramatic increase in performance, typically a gain of classification accuracy of 10% or more, whereas for already good subjects (e.g., A2, B1, B2, B8 and B9) using SRCSP leads to similar performances than CSP.

Interestingly enough, with CSP, subjects A3, A5, B2 and B5 would have been identified as "BCI illiterates", meaning they cannot use a BCI, as their performances were close to random (here below 55%). With SRCSP, none of these subjects would be identified as illiterates anymore. The most dramatic increase in performance was for subject A5, who gained 37% of accuracy. It should be noted that this subject was the one with the smallest training set (only 28 trials). Thus, we might hypothesize that adding an a priori to the algorithm, here a spatial one, can actually help by guiding the optimization process to find good spatial filters despite the limited amount of training data. In summary, it seems that SRCSP may learn good spatial filters even when training EEG data are limited or noisy, thanks to a regularization based on a spatial a priori.

Surprisingly, SRCSP led to lower score than CSP on a few subjects. This might be due to cross-validation (CV) being not a good predictor of generalization performances for BCI, maybe due to the non-stationarity of EEG. Indeed, if α = 0 (i.e., standard CSP) was the best regularization, then CV should have figured it out. However, it seems this was not always the case.

Figure 1 shows some examples of spatial filters obtained with both CSP and SRCSP. As expected by adding the spatial regularization, the SRCSP filters are indeed smoother than the CSP filters. More interest- ingly, it also shows that SRCSP filters are more convincing from a neurophysiological point of view. For instance, for subject A5, the CSP filter appear as very rough and noisy, with large weights in many different electrode locations, whereas the corresponding SRCSP filter displays large weights in a few regions, located over the motor cortex of the brain, which is expected from the neurophysiology literature [START_REF] Pfurtscheller | Motor imagery and direct brain-computer communication[END_REF]. Thus, this suggests that SRCSP may lead to more physiologically relevant, and thus more interpretable filters than CSP.

Conclusion

In this paper, we proposed the Spatially Regularized Common Spatial Pattern (SRCSP) algorithm, an extension of the famous CSP which includes spatial a priori into the learning process. To do so, we added a regularization term to the CSP objective function to ensure spatially smooth filters, and we derived an algorithm to optimize this new objective function. We compared the SRCSP and the CSP algorithms on EEG data of 14 subjects from BCI competition data sets. Results suggested that SRCSP could lead to large performance improvements for subjects with initially poor CSP accuracies, while giving similar performances than CSP for subjects with already good performances. Our results also suggested that SRCSP may lead to more physiologically relevant filters than CSP. To conclude, we would recommend adopting SRCSP instead of CSP for BCI design, especially for subjects with few and noisy data.

Figure 1 .

 1 Figure 1. Electrode weights for corresponding CSP and SRCSP filters, for subjects A1, A5 (both using 118 electrodes) and B6, B9 (both using 22 electrodes).

Table 1 . Classification accuracies (%) obtained for each subject for both the CSP and the pro- posed SRCSP method. For each subject, the best result is displayed in bold characters.

 1

		BCI competition III, data set IVa			BCI competition IV, data set IIa
	Subject	A1	A2	A3	A4	A5	B1	B2	B3	B4	B5	B6	B7	B8	B9	Mean
	CSP	66.07 96.43 47.45 71.88 49.6 88.89 51.39 96.53 70.14 54.86 71.53 81.25 93.75 93.75 73.1±17.6
	SRCSP 72.32 96.43 60.2 77.68 86.51 88.89 63.19 96.53 66.67 63.19 63.89 78.47 95.83 92.36 78.7±13.9

Acknowledgments: The authors would like to thank Dr. Blankertz for providing the electrodes coordinates of BCI competition data, and Dr. Hamadicharef for his constructive comments on this manuscript.