Salvatore Tringali

SMALL DOUBLING IN ORDERED SEMIGROUPS

Keywords: 2010 Mathematics Subject Classification. 06A07, 06F05, 20M10, 20N02 Freiman's theory, ordered magmas, ordered semigroups, product-sets, small doubling, sum-sets, torsion-free semigroups

come

Small doubling in ordered semigroups

Introduction

Semigroups (and magmas) are ubiquitous in mathematics. Apart from being a subject of continuous interest to algebraists, they are the natural framework for the introduction of several broadly-scoped concepts and for the development of some large parts of theories traditionally presented in somewhat richer settings. Semigroups serve, for instance, as fundamental models for linear time-invariant systems and, as a result of the pioneer work of Hille and Phillips on their use in functional analysis [START_REF] Hille | Functional analysis and semi-groups[END_REF], have been successfully applied for decades to the study of partial [START_REF] Engel | A Short Course on Operator Semigroups[END_REF] and stochastic [START_REF] Van Casteren | Markov Processes, Feller Semigroups and Evolution Equations, Series on Concrete and Applicable Mathematics[END_REF] differential equations (e.g., in relation to the method of strongly continuous one-parameter semigroups). Also, finite semigroups have been of primary importance in theoretical computer science since the 1950s due to the their natural link with finite automata.

Our personal interest in semigroups is related here to some recent results by G.A. Freiman, M. Herzog and coauthors on the structure theory of product-sets in the (nonabelian) setting of linearly (i.e., strictly and totally) ordered groups [START_REF] Freiman | Small doubling in ordered groups[END_REF]. This is an active area of research, with notable applications, e.g., to additive combinatorics [START_REF] Tao | Product set estimates for non-commutative groups[END_REF], Freiman's structure theory [START_REF] Ruzsa | Sumsets and structure[END_REF], invariant measures [START_REF] Bourgain | Invariant measures and stiffness for nonabelian groups of toral automorphisms[END_REF], and spectral gaps [START_REF] Bourgain | On the spectral gap for finitely-generated subgroups of SU(2)[END_REF]. The present work fits into this background; it is basically a collection of miscellaneous results, serving as a preliminary to further study and future developments and aiming to be a contribute to the efforts of extending some parts of the theory from groups to the scenery of semigroups (and magmas). Specifically, our main result is the following generalization of [6, Theorem 1.2]: Theorem 1. Let S be a finite subset of a linearly ordered semigroup (written multiplicatively), which generates a nonabelian subsemigroup. Then,

|S 2 | ≥ 3 |S| -2.
Net of a number of (minor) simplifications, our proof of Theorem 1 basically follows the same broad scheme as the proof of [START_REF] Freiman | Small doubling in ordered groups[END_REF]Theorem 1.2]. However, the increased generality implied by the switching to the setting of linearly ordered semigroups raises a number of challenges and requires more than a mere adjustment of terminology, and especially the refinement of several classical results on linearly orderable groups, such as the following: Corollary 2. Let A = (A, •, ) be a linearly ordered semigroup (written multiplicatively) and a, b ∈ A. If a n b = ba n for some n ∈ N + , then ab = ba.

Corollary 2 is actually a generalization of an old lemma by N.H. Neumann [START_REF] Neumann | On ordered groups[END_REF] on commutators of linearly ordered groups, appearing as Lemma 2.2 in [START_REF] Freiman | Small doubling in ordered groups[END_REF]; we prove it in Section 2. [START_REF] Clifford | Totally ordered commutative semigroups[END_REF].

The next proposition is an extension of classical lower bounds on the size of product-sets of finite subsets of linearly ordered groups to the setting of linearly ordered magmas.

Proposition 9. Suppose that A = (A, •, ) is a linearly ordered magma (written multiplicatively). Pick n ∈ N + and let S 1 , S 2 , . . . , S n be nonempty finite subsets of A. Then The reader might want to consult [START_REF] Eliahou | Some extensions of the Cauchy-Davenport theorem[END_REF] and the references therein for similar results in the context of arbitrary groups (notably including the Cauchy-Davenport theorem). Proposition 9 is proved in Section 2.3. Here, as is expected, we use ≥ (and its dual ≤) for the standard order of the real numbers (unless an explicit statement to the contrary) and, if S is a set, we denote by |S| the cardinality of S. More notation and terminology used in this introduction without explanation will be clarified below, in Section 2.1.

We give two simple applications of Proposition 9, none of them covered by less general formulations of the same result such as the (classical) one reported in [START_REF] Freiman | Small doubling in ordered groups[END_REF] for linearly ordered groups: The second one concerns the set of all upper (respectively, lower) triangular matrices with positive real entries, which we prove to be a linearly orderable semigroup (with respect to the usual matrix multiplication) in Proposition 1. In this respect, we raise the question, at present open to us, whether the same holds true for the set of all matrices which are a (finite) product of upper or lower triangular matrices with positive real entries.

Then, we combine Proposition 9 with other basic properties to establish the following:

Proposition 10. Let A = (A, •, ) be a linearly ordered semigroup (written multiplicatively) and S a nonempty finite subset of A of size m, and pick y ∈ A \ C A (S). Then |yS ∪ Sy| ≥ m + 1, so in particular there exist a, b ∈ S such that ya / ∈ Sy and by / ∈ yS.

Proposition 10 is a generalization of [START_REF] Freiman | Small doubling in ordered groups[END_REF]Proposition 2.4]. We prove it in Section 3, along with the following interesting result, which in turn generalizes [START_REF] Freiman | Small doubling in ordered groups[END_REF]Corollary 1.5].

Corollary 3. If S is a finite subset of a linearly ordered semigroup A, then N A (S) = C A (S).
The whole is accompanied by a significant number of examples, mostly finalized to explore conditions under which some special classes of semigroups (or more sophisticated structures as semirings) are linearly orderable. In particular, we show by Proposition 6 that every abelian torsion-free cancellative semigroup is linearly orderable, so extending a similar 1913 result of F.W. Levi on abelian torsion-free groups.

Definitions, examples and basic properties

The present section is divided into three parts. First, we fix notation and terminology and recall the definitions of ordered (and orderable) magmas, semigroups and groups. Then, we mention some relevant examples for each of these structures. Finally, we derive a few basic properties that will be used to prove, later in Section 4, our main results.

2.1. Notation and terminology. For all purposes and intents, and especially to avoid misunderstandings due to different conventions, let us first clarify some basic points and recall a few definitions. Our main reference for terms not given here or in a later section is [START_REF] Howie | Fundamentals of semigroup theory[END_REF]; in particular, for order-theoretic concepts the reader should consult [9, §1.3].

Given a set A, an order on A is a binary relation on A which is reflexive, antisymmetric and transitive. One then refers to the pair (A, ) as a poset and writes a ≺ b for a, b ∈ A to mean that a b and a = b. If (A, ) is a poset, we denote by op the dual order of , defined by taking a op b for a, b ∈ A if and only if b a. Definition 1. A magma is a pair A = (A, ), consisting of a (possibly empty) set A, the magma carrier, and a binary operation : A × A → A, the magma product. If S is a subset of A and S is closed under , i.e. a b ∈ S for all a, b ∈ S, we say that (S, ) is a submagma of A.

Note that [9, §1.1] refers to magmas as groupoids. A magma A = (A, ) is associative if is associative, i.e. a (b c) = (a b) c for all a, b, c ∈ A; abelian if a b = b a for all a, b ∈ A; and unital if there exists a distinguished element e ∈ A (which is, in fact, unique and called the magma identity) such that a e = e a = a for every a ∈ A. An associative magma is a semigroup and a unital semigroup is identified with a monoid, which is formally a triple of type (A, , e), where (A, ) is a semigroup and e ∈ A the identity thereof. Something analogous holds for groups, formally defined as 4-tuples of type (A, , ∼, e) for which (A, , e) is a monoid and ∼ is a unary operation A → A such that a (∼ a) = (∼ a) a = e for every a ∈ A. Definition 2. An ordered magma is a pair of the form (A, ), where (i) A = (A, ) is a magma, (ii) is an order on A, and (iii) a c b c and c a c b for all a, b, c ∈ A with a b; this will be equivalently represented by the triple (A, , ). If (A, ) is such a pair, one says that A is ordered by . In particular, (A, ) is a totally ordered magma if is total; a strictly ordered magma if a c ≺ a c and c a ≺ c b for all a, b, c ∈ A with a ≺ b; and a linearly ordered magma if it is strictly and totally ordered. Accordingly, A is totally orderable in the first case, strictly orderable in the second, and linearly orderable in the latter, and we say respectively that A is totally, strictly, and linearly ordered by .

Since semigroups and monoids can be viewed as a special kind of magmas (forgetting some of their structure as appropriate), one will safely speak of ordered semigroups, totally orderable monoids, etc. Similar considerations apply to groups, provided that an ordered group is defined as a 5-tuple of type (A, , ∼, e, ) such that (A, , ∼, e) is a group, (A, , e, ) is an ordered monoid, and (∼ b) (∼ a) for all a, b ∈ A with a b.

Totally ordered semigroups are considered, for instance, by A.H. Clifford in his 1958 survey on the subject [START_REF] Clifford | Totally ordered commutative semigroups[END_REF], where they are simply referred to as ordered semigroups. Note that, in spite of its title, Clifford's work deals with totally ordered semigroups both in the abelian and nonabelian setting; however, the manuscript is not really focused on linearly ordered semigroups as here defined (these are only mentioned in the introduction, but not further considered).

As is usual, if the magma product is written multiplicatively as • and there is no likelihood of confusion, we use the notation ab instead of a • b. Moreover, if A is a magma and A its carrier, we abuse notation and write a ∈ A to mean that a ∈ A, especially in contexts or statements implicitly involving, along with a, the structure of A. This principle applies also to sets (and not only to elements) and to other structures such as posets, semigroups, ordered groups, etc.

Remark 1. The notion of orderable magma is somewhat vacuous since every magma A is ordered by the trivial order , defined for a, b ∈ A by taking a b if and only if a = b. Remark 2. If (A, , ) is an ordered, totally ordered, or strictly ordered magma, then the same is also true for (A, , op ), (A, op , ) and (A, op , op ), where op is the dual order of and op the dual product of , i.e. the binary operation A × A → A : (a, b) → b a. Remark 3. Every submagma of a linearly orderable magma is linearly orderable.

With this in mind, let A = (A, ) be a magma. Given n ∈ N + , we define recursively P 1 := {id A }, where id A is the map A → A : a → a, and P n+1 := P L n+1 ∪ P R n+1 , where (i) P L n+1 is the set of all functions A n+1 → A sending, for some f ∈ P n , a (n + 1)-tuple (a 1 , a 2 , . . . , a n+1 ) to the product a 1 f (a 2 , a 3 , . . . , a n+1 ). (ii) P R n+1 is the set of all functions A n+1 → A mapping, for some f ∈ P n , a (n + 1)-tuple (a 1 , a 2 , . . . , a n+1 ) to the product f (a 1 , a 2 , . . . , a n ) a n+1 . For n ∈ N + , we then refer to an element P of P n as a parenthetization of A of length n, or also a n-parenthetization of A. Moreover, for a 1 , a 2 , . . . , a n ∈ A, we write (a 1 a 2 • • • a n ) P in place of P(a 1 , a 2 , . . . , a n ) and, whenever S 1 , S 2 , . . . , S n are subsets of A, we let

(2) (S 1 S 2 • • • S n ) P := {(a 1 a 2 • • • a n ) P : a 1 ∈ S 1 , a 2 ∈ S 2 , . . . , a n ∈ S n } if S i is nonempty for each i = 1, 2, . . . , n, while taking (S 1 S 2 • • • S n ) P := ∅ otherwise. If A is a semigroup or n ≤ 2, then (a 1 a 2 • • • a n ) P
does not really depend on P, and we can simply write it as a 1 a 2 • • • a n ; at the end of the day, parenthetization is, in fact, just a formal way to deal with long products in a magma whose operation is not associative. In particular, if a ∈ A and S ⊆ A, we use a S in place of {a} S (and similarly with S a). These notations are then simplified in the obvious way in the case where A is written multiplicatively (and there is no serious sdanger of ambiguity). Finally, if A = (A, ) is a magma, or A = (A, , ) is an ordered magma, and S is a subset of A, we write S A for the submagma of A generated by S, i.e. the smallest submagma of A containing S (which is clearly a semigroup if the magma operation is associative); cf. [9, §1.2]. Also, we use C A (S) for the centralizer of S in A, i.e. the set of all a ∈ A such that a y = y a for every y ∈ S, and N A (S) for the normalizer of S in A, i.e. the set {a ∈ A : a S = S a}. In particular, these are written as C A (a) and N A (S), respectively, if S = {a} for some a ∈ A.

Some examples.

To start with, we exhibit a totally orderable semigroup which is not linearly orderable. Then, we mention some special classes of linearly orderable groups, some linearly orderable monoids (respectively, semigroups) which are not groups (respectively, monoids), and a linearly orderable magma which is not a semigroup. Example 1. Every set A can be turned into a semigroup by the operation : A × A → A : (a, b) → a; some authors refer to (A, ) as the left zero semigroup (e.g., see [9, p. 3]). It is trivial that, if is a total order on A, then (A, , ) is a totally ordered semigroup. However, since a b = a c for all a, b, c ∈ A, it is clear that (A, ) is not linearly orderable if |A| ≥ 2.

Example 2. A notable example of linearly ordered groups is provided by abelian torsion-free groups, as first proved by F.W. Levi in [START_REF] Levi | Arithmetische Gesetze im Gebiete diskreter Gruppen[END_REF], and we show in Section 2.3 that Levi's result can be, in fact, extended to abelian cancellative torsion-free semigroups (see Proposition 6). In the same lines, K. Iwasawa [START_REF] Iwasawa | On linearly ordered groups[END_REF], A.I. Mal'cev [START_REF]'cev, On ordered groups[END_REF] and B.H. Neumann [START_REF] Neumann | On ordered groups[END_REF] established, independently from each other, that the class of torsion-free nilpotent groups is contained in the class of linearly orderable groups. These are already reported in [START_REF] Freiman | Small doubling in ordered groups[END_REF], along with further references to existing literature on the subject.

Example 3. As for linearly ordered monoids which are not linearly ordered groups, one can consider, for instance, the free monoid on an alphabet X together with the "shortlex ordering": Words are primarily sorted by length, with the shortest ones first, and words of the same length are then sorted into lexicographical order. On the other hand, the positive integers divisible only for the members of a given subset S of (natural) primes, endowed with the usual multiplication, provides the example of a linearly orderable semigroup which is not even a monoid unless S = ∅.

Example 4. Let A be the open interval ]1, +∞[ of the real line and the operation

A × A → A : (a, b) → a b . Then, (A,
) is a nonabelian linearly orderable magma (just consider the usual order on the real numbers and restrict it to A), but not a semigroup.

The next example might be interesting in its own right: Not only it gives a class of linearly ordered semigroups which are neither abelian nor groups in disguise (at least in general), it also shows that, for each n ∈ N + , the set of all n-by-n upper (respectively, lower) triangular matrices with positive real entries is a linearly orderable semigroup when endowed with the usual row-by-column multiplication (which applies especially to matrices of positive integers). One refers to (A, +, 0) and (A, •) as the additive monoid and the multiplicative semigroup of A, respectively, and A is said to be unital if (A, •) is a unital semigroup (cf. [7, Ch. II]). A semiring is similar to a ring, save that elements in semirings do not necessarily have an inverse for the addition. We denote by A 0 the set of zero divisors of A, i.e. the non-zero elements

a ∈ A such that a • b = 0 or b • a = 0 for some b ∈ A \ {0}; A has no zero divisors if A 0 = ∅.
We say that A is an orderable (respectively, totally orderable) semiring if there exists an order (respectively, a total order) on A such that (A, +, ) and (A, •, ) are ordered semigroups. When this occurs, the pair (A, ), or equivalently the 5-tuple (A, +, •, 0, ), is said an ordered (respectively, totally ordered) semiring. If, on the other hand, the following conditions hold:

(iv) (A, +, ) is a strictly ordered semigroup; (v) (A \ {0}, •, ) is a strictly ordered semigroup,
then A is said to be strictly orderable and (A, ) is called a strictly ordered semiring. Lastly, we say that A is linearly orderable if it is both strictly and totally orderable, and accordingly we refer to (A, ) as a linearly ordered semiring.

The notion of orderable semiring is basically vacuous, insomuch as every semiring is ordered by the trivial order (cf. Remark 1). Also, a semiring is strictly orderable only if it has no zero divisors. The class of linearly ordered semirings includes, as notable examples, the nonnegative real numbers (equipped with the standard order and the usual algebraic structure) and interesting subsemirings of this one such as the nonnegative integers.

Based on these premises, assume in what follows that (A, ) is an ordered semiring with A = (A, +, •, 0). We denote by A + the set {a ∈ A : 0 ≺ a}. Note that, if A has no zero divisors and is total, one can assume without loss of generality that A + = A \ {0}. If n is a fixed positive integer, we then use M n (A) for the set of all n-by-n matrices with entries in A. Together with the usual operations of entry-wise addition and row-by-column multiplication implied by the algebraic structure of A (here respectively denoted, as is usual, by the same symbols as the addition and multiplication of this latter), M n (A) becomes a semiring in its own right, referred to as the semiring of the n-by-n matrices over A and indicated throughout by M n (A). Now, suppose for the sequel that A has no zero divisors and denote by U n (A + ) the subsemigroup of the multiplicative semigroup of M n (A) consisting of all upper triangular matrices whose entries are elements of A + . Note that U n (A + ) is not, in general, a group (e.g., the inverse of a regular 2-by-2 matrix with positive real entries has not positive real entries), and not even a monoid unless A is unital. More interestingly, U n (A + ) is linearly orderable, as we are going to prove by the following theorem.

Proposition 1. U n (A + ) is a linearly orderable semigroup. Proof. Set I n := {1, 2, . . . , n}, Ξ n := {(i, j) ∈ I n × I n : i ≤ j} and define a binary relation ≤ n on Ξ n by letting (i 1 , j 1 ) ≤ n (i 2 , j 2 ) if and only if (i) j 1 -i 1 < j 2 -i 2 or (ii) j 1 -i 1 = j 2 -i 2 and j 1 < j 2 .
It is easily seen that ≤ n is a total order, and indeed a well-order as Ξ n is finite. This allows us define a binary relation U n on U n (A + ) by taking, for α = (a i,j ) n i,j=1 and β = (b i,j

) n i,j=1 in U n (A + ), α U n β if and only if (i) α = β or (ii) there exists (i 0 , j 0 ) ∈ Ξ n such that a i0,j0 ≺ b i0,j0 and a i,j = b i,j for all (i, j) ∈ Ξ n such that (i, j) < n (i 0 , j 0 ).
It is routine to check that U n is an order. To see that it is total: Pick α = (a i,j ) n i,j=1 and β = (b i,j ) n i,j=1 in U n (A + ) with α = β. There then exists (i 0 , j 0 ) ∈ Ξ n such that a i0,j0 = b i0,j0 and, using that ≤ n is a well-order, (i 0 , j 0 ) can be chosen in such a way that a i,j = b i,j for every (i, j) ≤ n (i 0 , j 0 ). Thus, as is total, either α ≺ U n β if a i0,j0 ≺ b i0,j0 or β ≺ U n α otherwise. It remains to prove that U n (A + ) is linearly ordered by U n . For let α, β and γ be as above and suppose α ≺ n β. This means that there exists (i 0 , j 0 ) ∈ Ξ n such that a i0,j0 ≺ b i0,j0 and a i,j = b i,j for all (i, j) ∈ Ξ n with (i, j) < n (i 0 , j 0 ). As a consequence, a i,k c k,j b i,k c k,j and c i,k a k,j c i,k b k,j for all (i, j) ∈ Ξ n and k ∈ I n such that (i, k) ≤ n (i 0 , j 0 ) and (k, j) ≤ n (k, j 0 ), and indeed a i0,j0 c j0,j0 ≺ b i0,j0 c j0,j0 and c i0,i0 a i0,j0 ≺ c i0,i0 b i0,j0 for the fact that (A, ) is a linearly ordered semiring (to the effect that A + = A \ {0} or A + = ∅). It follows that, for all (i, j) ∈ Ξ n with (i, j) ≤ n (i 0 , j 0 ), ( 3)

n k=1 a i,k c k,j = j k=i a i,k c k,j U n j k=i b i,k c k,j = n k=1 b i,k c k,j and, similarly, n k=1 c i,k a k,j U n n k=1 c i,k b k,j .
In particular, these majorizations are equalities for (i, j) < n (i 0 , j 0 ) and strict inequalities if (i, j) = (i 0 , j 0 ). This ultimately shows that α • γ ≺ n β • γ and γ • α ≺ n γ • β, and our proof is complete.

We refer to the order U n defined in the proof of Proposition 1 as the zig-zag order on U n (A + ). If L n (A + ) stands for the subsemigroup of the multiplicative semigroup of M n (A) consisting of all lower triangular matrices with entries in A + , it is then straightforward to prove that L n (A + ) is itself linearly orderable, as it is in fact linearly ordered by the binary relation At present, we do not have an answer, but Carlo Pagano (Università di Roma Tor Vergata) observed, in a private communication, that M n (A + ), i.e. the subsemigroup of the multiplicative semigroup of M n (A) consisting of all matrices with entries in A + , is not in general linearly orderable. For a counterexample, let A be the linearly ordered semiring of all nonnegative real numbers (with their standard structure) and take α as the n-by-n matrix whose entries are all equal to 1 and β as any n-by-n matrix with positive entries each of whose columns sums up to n. Then, α 2 = αβ regardless as to whether α = β.

New exemplars of linearly orderable magmas can now be obtained from the previous ones using, for instance, the constructions reported below.

Example 6. Suppose that I = (I, ≤) is a well-ordered set and let {(A i , i , i )} i∈I be a family of totally ordered magmas indexed by I. Set A i = (A i , i , i ) for each i ∈ I and take A to be the Cartesian product of the A i 's, that is the set of all functions f : I → i∈I A i such that f (i) ∈ A i for each i ∈ I. Also, define as the binary operation (4)

A × A → A : (f, g) → I → i∈I A i : i → f (i) i g(i) ,
so that (A, ) is the magma direct product of the family {(A i , i )} i∈I . The product order on A induced by the i 's is not, in general, total. However, this is happily the case with the lexicographical order, herein denoted by , which is defined by taking f g for f, g ∈ A if (and only if

) (i) f = g or (ii) f (i) ≺ i g(i)
for some i ∈ I and f (j) = g(j) for every j ∈ I with j < i. Furthermore, is compatible with , in the sense that A = (A, , ) becomes a totally ordered magma, and indeed a linearly ordered magma whenever A i is linearly ordered for each i ∈ I.

Example 7. Let A = (A, ) and B = (B, •) be magmas and φ : A → B a magma monomorphism, i.e. an injective function A → B with φ(a 1 a 2 ) = φ(a 1 ) • φ(a 2 ) for all a 1 , a 2 ∈ A. If B is linearly ordered by some total order B and A is the binary relation on A defined for a 1 , a 2 ∈ A by taking a 1 A a 2 if (and only if) φ(a 1 ) B φ(a 2 ), it is routine to verify that A is a total order, and indeed (A, A ) is a linearly ordered magma: In particular, if a 1 , a 2 , c ∈ A and a 1 ≺ B a 2 , then φ(a 1 ) ≺ B φ(a 2 ), from which it follows that

(5) φ(a 1 c) = φ(a 1 ) • φ(c) ≺ B φ(a 2 ) • φ(c) = φ(a 2 c)
and similarly φ(c a 1 ) ≺ A φ(c a 2 ), since φ is a magma monomorphism. Thus, a 1 c ≺ A a 2 c and c a 1 ≺ A c a 2 , by definition of A . For future reference we summarize the result in the following proposition:

Proposition 2. Let A and B be magmas and suppose that A embeds in B, that is, there exists a magma monomorphism φ : A → B. Then, A is totally (respectively, linearly) orderable if and only if the same holds true for φ(A).

Example 8. This example deals with polynomials. We start by recalling some basic definitions, to fix notation and terminology. Let X = (X, X ) be a well-ordered nonempty set (which can be interpreted as a set of distinct labelled variables) and A = (A, +, •, 0) a semiring (see Example 5).

Writing F c (X, N) for the set of all functions φ : X → N with |{x ∈ X : φ(x) = 0}| < ∞, we take a polynomial variable with X over (the ground semiring) A to be any function f : F c (X, N) → A such that f (φ) = 0 for finitely many φ (here, N includes 0). We use A[X] for the set of all such functions and endow it with binary operations of addition and multiplication defined as follows (we denote them, each in turn, by the same symbols as the addition and multiplication of A): For all f, g ∈ A[X], f + g is the pointwise sum of f and g, i.e. the mapping

(6) F c (X, N) → A : φ → f (φ) + g(φ),
and f g the Cauchy product of f by g, i.e. the function

(7) F c (X, N) → A : φ → (α,β)∈Π(φ) f (α) • g(β),
Here, given φ ∈ F c (X, N), Π(φ) means the set of all pairs (α,

β) ∈ F c (X, N) × F c (X, N) such that α ⊕ β = φ, where α ⊕ β is the function X → N : x → α(x) + β(x).
For what it is worth, note that the summation in [START_REF] Hebisch | Semirings: Algebraic Theory and Applications in Computer Science[END_REF] involves only a finite number of non-zero terms for every φ, which makes the Cauchy product well-defined even if X is infinite.

It is routine to check that (A[X], +, •, 0) is a semiring, with 0 the function F c (X, N) → A : φ → 0. We call it the semiring of polynomials over A with variables in X. This is denoted, in general, by A[X], and indeed by A[x 1 , x 2 , . . . , x k ] in the case where X is finite of size k and x 1 , x 2 , . . . , x k is the unique enumeration of the elements of X with

x 1 ≺ X x 2 ≺ X • • • ≺ X x k .
Here, we focus on this latter case, by systematically identifying the elements of A[x 1 , x 2 , . . . , x k ] with the functions f : N k → A such that N k \ f -1 (0) is finite. Especially, we have the following:

Proposition 3. If A is a linearly orderable semiring, then the same is true for A[x 1 , x 2 , . . . , x k ]. Proof. It is well-known (cf. [7, Remark 1.10]) that, for k ≥ 2, A[x 1 , x 2 , . . . , x k ] is canonically isomorphic to A [x k ], where A := A[x 1 , x 2 , . . . , x k-1 ]
. By induction and Proposition 2, it is then enough to show that A[x 1 , x 2 , . . . , x k ] is a linearly orderable semiring for k = 1.

So write x in place of x 1 , for notational simplicity, and assume that A is linearly ordered, as a semiring, by a certain order (see Example 5). Accordingly, define a binary relation poly on A[x] by taking, for f, g ∈ A[x], f poly g if and only if either (i) f = g or (ii) there exists i 0 ∈ N such that (ii.1) f (i 0 ) ≺ g(i 0 ) and (ii.2) f (i) = g(i) for all i ∈ N with i < i 0 .

It is easily recognized that poly is an order. To see that poly is total: Pick f, g ∈ A[x] with f = g. Then, there exists i 0 ∈ N such that f (i 0 ) = g(i 0 ). In particular, as ≤ is a well-order, i 0 can be chosen in such a way that f (i) = g(i) for every i < i 0 . Thus, since A is totally ordered by , either f ≺ poly g if f (i 0 ) ≺ g(i 0 ) or g ≺ poly f otherwise.

It remains to prove that (A[x], poly ) is a linearly ordered semiring. For pick f, g, h ∈ A[x] with f ≺ poly g and h = 0. By condition (ii), there exists i 1 ∈ N such that f (i 1 ) < g(i 1 ) and f (i) = g(i) for all i < i 1 ; furthermore, there exists i 2 ∈ N such that h(i 2 ) = 0 and h(i) = 0 for all i < i 2 . Now, take i ∈ N with i ≤ i 0 :

= i 1 + i 2 . It is immediate from (7) that (8) (f h)(i) = (a,b)∈Π0(i) f (a)h(b), (gh)(i) = (a,b)∈Π0(i) g(a)h(b), where Π 0 (i) := {(a, b) ∈ N 2 : a + b = i and i 2 ≤ b}, to the effect that (f h)(i) = (gh)(i) if i < i 0 .
Hence, assume i 0 ≤ i. It is then easy to check that a ≤ i 1 for every (a, b) ∈ Π 0 (i), and indeed a < i 1 unless i = i 0 , a = i 1 and b = i 2 . It follows from here that (f h)(i) = (gh)(i) for every i < i 0 and (f h)(i 0 ) ≺ (gh)(i 0 ), whence f h ≺ poly gh. On the other hand, similar arguments show that hf ≺ poly hg. And this completes our proof on account of the fact that it is actually a trivial task to check that (A[x], +, poly ) is a linearly ordered monoid.

We could not figure out how to extend the proof of Proposition 3 in such a way to cover the case of polynomials depending on infinitely many variables. Hence, we conclude this section by raising the following question (up to date, open to us): Question 2. If A is a linearly orderable semiring and X a well-ordered nonempty set, is A[X] a linearly orderable semiring in its own right regardless of the finiteness of X? 2.3. A few useful properties. Here, we aim to derive a few elementary properties of ordered semigroups and magmas, which are basically a generalization of some elementary properties reported in [6, §2] in reference to linearly ordered groups; with the exception of Proposition 6 and Corollary 1 (which are somewhat subsidiary to the main purpose of the paper), these properties will be essential to prove the main results of the paper, in Section 4. Most of them are straightforward, and their group analogues are very well-known; however, since we have no explicit references to similar results in the context of ordered semigroups (and magmas), we prove them here for the sake of completeness and exposition.

All magmas in this section are written multiplicatively (unless an explicit statement to the contrary); in particular, if A is a magma (or an ordered magma), a an element of A, n a positive integer and P a n-parenthetization of A, we use (a n ) P for the n-fold product P(a, a, . . . , a). Proposition 4. Let A = (A, •, ) be an ordered magma. The following holds:

(i) If n ∈ N + and P is a n-parenthetization of (A, •), then (a 1 a 2 • • • a n ) P (b 1 b 2 • • • b n ) P for all a 1 , a 2 , . . . , a n , b 1 , b 2 , . . . , b n ∈ A such that a 1 b 1 , a 2 b 2 , . . . , a n b n , and indeed (a 1 a 2 • • • a n ) P ≺ (b 1 b 2 • • • b n ) P if A is strictly ordered and a i ≺ b i for each i. (ii) If a, b ∈ A
and a b, then (a n ) P (b n ) P for all n ∈ N + and every n-parenthetization P of (A, •), and indeed (a n ) P (b n ) P if A is strictly ordered and a ≺ b. (iii) If • is associative and a ∈ A is such that a 2 a, then a n a m for all m, n ∈ N + with m ≤ n, and indeed a n ≺ a m if A is strictly ordered, a 2 ≺ a and m < n.

Proof. (i) If n = 1, the claim is obvious. If n = 2, then a 1 b 1 and a 2 b 2 implies, as A is an ordered magma, that a 1 a 2 b 1 a 2 b 1 b 2 , and indeed a 1 a 2 ≺ b 1 a 2 ≺ b 1 b 2 if A is strictly ordered and a 1 ≺ b 1 , a 2 ≺ b 2 .
Lastly, if n ≥ 3, then there exists a parenthetization Q of (A, •) of length (n -1) such that (c Let A = (A, •) be a magma and pick a ∈ A. One says that a is left (respectively, right) cancellable (with respect to •) if the mapping A → A : x → ax (respectively, A → A : x → xa) is one-to-one, and cancellable if it is both left and right cancellable. Then, A is called cancellative if each one of its elements is cancellative. On another hand, we say that a is idempotent if a = a 2 and periodic, when A is a semigroup, if there exist n, p ∈ N + such that a n = a n+p : One then refers to the smallest n with this property as the index of a and to the smallest p relative to such an n as the period of a. Clearly, the concept of period generalizes the notion of order from the setting of groups to that of semigroups. Then, we say that a semigroup is torsion-free if the only periodic elements of it are idempotent. The same definitions now apply to ordered magmas and semigroups, as appropriate, by implicit reference to the underlying algebraic structures. Remark 4. A cancellative magma is linearly orderable if and only if it is totally orderable, as is immediate to check; conversely, every linearly orderable magma is cancellative.

1 c 2 • • • c n ) P = (c 1 • • • c n-1 ) Q • c n or (c 1 c 2 • • • c n ) P = c 1 • (c 2 • • • c n ) Q for all c 1 ,
Remark 5. The unique idempotent element of a cancellative unital magma is the identity, so that torsion-free groups are definitely a special kind of torsion-free semigroups. Furthermore, a cancellative semigroup A with an idempotent element a is unital (which applies especially to linearly ordered semigroups, as implied by Remark 4). In fact, a 2 = a entails that a 2 b = ab and ba 2 = ba for every b ∈ A; then ab = ba = b (by cancellativity of a), which ultimately proves that a serves as an identity for A.

The next proposition shows that, for (A, •, ) an ordered semigroup and a an element of A, the condition a 2 ≺ a plays the same role that a ≺ 1 would play in an ordered group (A, •, -1 , 1, ), while being more general than the latter. (iii) It is straightforward from Remark 2, point (iii) of Proposition 4 and Remark 5.

Based on point (iii) of Proposition 5 and the work of F.W. Levi on abelian torsion-free groups already mentioned in Example 2, it is somewhat natural to ask whether every abelian torsionfree cancellative semigroup is linearly orderable. This is answered in the positive by the following proposition, which is in fact an extension of Levi's result: Proposition 6. Every abelian torsion-free cancellative semigroup is linearly orderable.

Proof. Let A = (A, •) be a semigroup and denote by A (1) the canonical unitization of A as given in [9, p. 2], where A (1) is described as "the monoid obtained from A by adjoining an identity if necessary." In fact, A (1) is an abelian torsion-free cancellative monoid if and only if A is abelian, torsion-free and cancellative as a semigroup. Furthermore, A embeds in A (1) as a subsemigroup, so A is linearly orderable if this is the case with A (1) , by Remark 3 and Proposition 2.

As a consequence, assume in the sequel, without loss of generality, that A is an abelian cancellative monoid with identity 1 and denote by R the binary relation on

A × A defined, for a 1 , a 2 , b 1 , b 2 ∈ A, by taking (a 1 , a 2 ) R (b 1 , b 2 ) if and only if a 1 • b 2 = a 2 • b 1 . It is easily seen that R is an equivalence and • is compatible with R, in the sense that, for a 1 , a 2 , b 1 , b 2 , c 1 , c 2 ∈ A, (a 1 , a 2 ) R (b 1 , b 2 ) implies that (a 1 • c 1 , a 2 • c 2 ) R (b 1 • c 1 , b 2 • c 2 ). If A/ R is now the quotient set of A by R and, for (a, b) ∈ A × A, we write [(a, b)] R
for the equivalence class of (a, b), then A/ R becomes an abelian group with the binary operation ( 9)

A/ R × A/ R → A/ R : ([(a 1 , a 2 )] R , [(b 1 , b 2 )] R ) → [(a 1 + a 2 , b 1 + b 2 )] R ,
which we still denote by the same symbol as the product of A. Indeed, the pair (A/ R , •) is the Grothendieck group of A and we indicate it by A G ; its construction is simplified here by the assumed cancellativity of A, which entails as well that A embeds as a submonoid in A G . Now, since, on the one hand, A is torsion-free if and only if the same holds true for A G and, on the other, every abelian torsion-free group is linearly orderable by Levi's original result [START_REF] Levi | Arithmetische Gesetze im Gebiete diskreter Gruppen[END_REF], our proof is complete, again by virtue of Proposition 2.

As a minor remark, observe that not every abelian torsion-free monoid is linearly orderable, as recognized by adjoining an extra element, say ∞, to the set Z of all integers and considering the monoid (Z ∪ {∞}, +), where + is the usual addition of integers when it is restricted to Z and a + ∞ := ∞ + a := ∞ for all a ∈ Z ∪ {∞}. This monoid has two idempotent elements, namely 0 and ∞, so it cannot be linearly orderable by point (iii) of Proposition 5.

Another consequence of Proposition 5 is the following:

Corollary 1. Let A = (A,
•) be a semigroup and denote by A (1) its canonical unitization. Then, A is linearly orderable if and only if the same holds true with A (1) .

Proof. Since A canonically embeds in A (1) , the right-to-left implication is trivial by Remark 3 and Proposition 2. As for the converse, assume that A = (A, •) is linearly ordered by a certain total order . If A is unital, there is nothing to prove. So, suppose that A is not unital and set (10)

A -:= {a ∈ A : a 2 ≺ a}, A + := {a ∈ A : a ≺ a 2 }.
Also, denote by 1 the identity of A (1) . Since is total, we have by point (iii) of Proposition 5 that {{1}, A -1 , A + } is a partition of A (1) . Accordingly, we define a binary relation (1) on A (1) by taking a (1) b if and only if either (i) a, b ∈ A and a b, (ii) a ∈ A -and b = 1, (iii) a = 1 and b ∈ A + , or (iv) a = b = 1. It is routine to check that (1) is a total order. Furthermore, if a, b ∈ A (1) and a ≺ (1) 1, then by construction a 2 ≺ a; hence, we get from Remark 2 and point (i) of Proposition 5 that ab ≺ b and ba ≺ b, with the result that ab ≺ (1) b and ba ≺ (1) b. Similarly, b ≺ (1) ab and b ≺ (1) ba if a, b ∈ A and 1 ≺ (1) a. The claim follows.

We conclude the section with the generalization of Neumann's lemma already mentioned in the introduction (cf. Lemma 2.2 in [START_REF] Freiman | Small doubling in ordered groups[END_REF]): The basic observation is that, if A is a group with identity 1 and a, b ∈ A are such that [a n , b] = 1 for some n ∈ N + , then a n b = ab n (the square brackets denote a commutator, as is expected). Proof. Assume that a n b ≺ a n-1 ba ≺ • • • ≺ aba n-1 ≺ ba n for some n ∈ N + . Then, multiplying by a on the left gives a n+1 b ≺ a n ba ≺ • • • ≺ a 2 ba n-1 ≺ aba n , while multiplying by a on the right yields aba n ≺ ba n+1 . Since ab ≺ ba, the transitivity of implies the claim by induction. Proof. It is an immediate consequence of Proposition 7 and the fact that, in virtue of Remark 2, one can assume without loss of generality that ab ba.

Finite subsets of linearly ordered semigroups

The present section is concerned with various lower bounds on the size of the product-set of two or more finite subsets of linearly ordered magmas or semigroups (here again written multiplicatively, as in the previous section). First, we extend [6, Theorem 1.1] to the setting of linearly ordered magmas and derive a number of related results. Proof. Denote m the size of S and n the size of T , and let a 1 , a 2 , . . . , a m be a one-to-one enumeration of S and b 1 , b 2 , . . . , b n a one-to-one enumeration of T . Without loss of generality, we can assume that a

1 ≺ a 2 ≺ • • • ≺ a m and b 1 ≺ b 2 ≺ • • • ≺ b n . Since A is linearly ordered by , then a 1 b 1 ≺ a 2 b 1 ≺ • • • ≺ a m b 1 ≺ a m b 2 ≺ • • • ≺ a m b n , whence |ST | ≥ m + n -1.
Proposition 9. Suppose that A = (A, •) is a linearly ordered magma. Pick n ∈ N + and let S 1 , S 2 , . . . , S n be nonempty finite subsets of A. Then

(11) |(S 1 S 2 • • • S n ) P | ≥ 1 -n + n i=1 |S i | for any given parenthetization P of A of length n.
Proof. The claim is obvious if n = 1 and it reduces to Proposition 8 when n = 2, while for n ≥ 3 it follows by induction from the fact that there exists a (n

-1)-parenthetization Q of A such that (S 1 S 2 • • • S n ) P = S 1 • (S 2 • • • S n ) Q or (S 1 S 2 • • • S n ) P = (S 1 • • • S n-1 ) Q • S n .
Corollary 3. Pick m ∈ N + and let A = (A, •) be a linearly ordered magma and S a finite subset of A of size m. Then, for every n ∈ N + and every n-parenthetization P of A, one has

(12) |(S n ) P | ≥ (m -1)n + 1,
where (S n ) P := {(a 1 a 2 • • • a n ) P : a 1 , a 2 , . . . , a n ∈ S}. In addition to this, if A is associative and there exists at least one element a ∈ A which is not idempotent, then ( 12) is a sharp inequality, the lower bound being attained, for all n ∈ N + , by taking S = {a i : i = 1, 2, . . . , m}.

Proof. The first part of the claim is obvious if m = 0, while it follows from Proposition 9 if m = 0. As for the second part, assume that A is associative and a ∈ A is not idempotent. Then, point (iii) of Proposition 4 implies that a i = a j for all i, j ∈ N + with i = j, to the effect that T = {a i : i = 1, 2, . . . , m} is a set of size m and |T n | = (m -1)n + 1 for every n ∈ N + .

We give two applications of these results. The first one being based on Example 4; while on the one hand this is not much more than a curiosity, on the other it serves as an instance of a simply-stated problem which cannot be solved by relying on less general formulations of Corollary 3 such as the classical one reported in [START_REF] Freiman | Small doubling in ordered groups[END_REF] and already mentioned in the introduction.

|(S n ) P | ≥ |( Sn ) P | + |T | ≥ (m -2)n + 1 + |T |,
where T is the set of the elements of (S n ) P which are smaller than (a n ) P . This is enough to complete our proof when considering that |T | ≥ n as Proof. Assume to the contrary that yS = Sy. Since y / ∈ C A (S), there exists a 1 ∈ S such that a 1 y = ya 1 , which in turn implies, as y ∈ N A (S), that there exists an element a 2 ∈ S such that ya 1 = a 2 y. Hence, by the finiteness of S, it is possible to find a maximum integer k ≥ 2 such that (i) ya i = a i+1 y for every i = 1, 2, . . . , k -1 and (ii) a i = a j for i, j = 1, 2, . . . , k only if i = j. From the maximality of k and, again, the fact that yS = Sy, it follows that ya k = a h y for some h = 1, 2, . . . , k. Then, by induction, y i+1 a k = a h+i y i+1 for every i = 0, 1, . . . , k-h. In particular, y k-h+1 a k = a k y k-h+1 , whence ya k = a k y (due to Corollary 2), and indeed ya k = ya k-1 (as a k y = ya k-1 , by design). Therefore, Remark 4 yields that a k = a k-1 , which is absurd since a i = a j for all i, j = 1, 2, . . . , k with i = j. Proof. If S = ∅, the claim is obvious, so assume that S is nonempty. If y ∈ N A (S), then yS = Sy, and Proposition 10 implies that y ∈ C A (S), whence follows that N A (S) ⊆ C A (S). On the other hand, it is trivial that C A (S) ⊆ N A (S).

The main results

In this section we prove our main results and some corollaries. We start with a series of lemmas: The two first of these apply to cancellative semigroups in general, while the others, more restrictively, to linearly ordered semigroups. All semigroups here are written multiplicatively.

∈ A \ C A (S). If S A is abelian, then |S 2 ∪ yS ∪ Sy| ≥ 3m.
Proof. Since every linearly ordered semigroup is cancellative (Remark 4), the inclusion-exclusion principle, in combination with Lemma 1, implies that

(15) |S 2 ∪ yS ∪ Sy| = |S 2 | + |yS ∪ Sy| -|S 2 ∩ (yS ∪ Sy)| = |S 2 | + |yS ∪ Sy|,
which is enough to complete the proof on account of the fact that |S

≤ 3 |B| -3. Furthermore, assume for the sake of contradiction that S A is not abelian and accordingly denote by i the maximum integer in I m such that T A is abelian for T := {a 1 , a 2 , . . . , a i }. Then 1 ≤ i < m and a i+1 / ∈ C A (T ), so in particular ( 16)

T 2 ∩ (a i+1 T ∪ T a i+1 ) = ∅,
thanks to Remark 4 and Lemma 1, and

(17) |T 2 ∪ a i+1 T ∪ T a i+1 | ≥ 3i,
by virtue of Lemma 3. Also, there exists a positive integer j ≤ m such that (18) a i+1 a j = a j a i+1 , which is chosen here to be as great as possible, in such a way that (19) xa i+1 = a i+1 x for every x ∈ A with a j ≺ x.

We have that a j / ∈ C A (V ), where V := S \ T = {a i+1 , a i+2 , . . . , a m }, and

(20) V 2 ∩ (T 2 ∪ a i+1 T ∪ T a i+1 ) = ∅ since a h a k ≺ a 2 i+1
a r a s for all h, k, r, s ∈ I m with h + k ≤ 2i + 1 and i + 1 ≤ min(r, s). Then, the inclusion-exclusion principle, together with (17) and our hypotheses, gives that It follows that 2 ≤ |V | < m, and the inductive hypothesis yields that V A is abelian. Thus, (22) V 2 ∩ (a j V ∪ V a j ) = ∅ in view of Remark 4, Lemma 1 and the fact that a j / ∈ C A (V ). We want to prove that (23) T 2 ∩ (a j V ∪ V a j ) = ∅.

Indeed, assume to the contrary, without loss of generality, that T 2 ∩ a j V = ∅, i.e. xy = a j z for some x, y ∈ T and z ∈ V . Since y ≺ z, this yields that a j ≺ x; similarly, a j ≺ y as T A is abelian (to the effect that xy = yx, and hence yx = a j z). It then follows from (19) and the abelianity of V A that x, y, z ∈ C A (a i+1 ). Hence, Lemma 2 entails that a i+1 a j = a j a i+1 , which contradicts (18) and implies (23). That said, let x ∈ T and y ∈ V be such that xa i+1 = a j y. Since a i+1 y, it is apparent that a j x. Suppose for the sake of contradiction that a j ≺ x. Then, we get from (19) and the abelianity of V A that x, a i+1 , y ∈ C A (a i+1 ), to the effect that a j a i+1 = a i+1 a j (by Lemma 2). But this is in open contrast with (18), and it is enough to deduce that (24)

T a i+1 ∩ a j V = {a j a i+1 }.

Thus, the inclusion-exclusion principle gives that

(25) |T a i+1 ∪ a j V | = |T a i+1 | + |a j V | -|T a i+1 ∩ a j V | = i + (m -i) -1 = m -1,
which in turn implies, together with ( 16), (20), ( 22) and (23), that (26)

|T 2 ∪ V 2 ∪ T a i+1 ∪ a j V | = |T 2 | + |V 2 | + |T a i+1 ∪ a j V |.
Hence, it follows from Theorem 3 and (25) that (27) |T 2 ∪ V 2 ∪ T a i+1 ∪ a j V | ≥ (2i -1) + (2m -2i -1) + (m -1) = 3m -3.

As |S 2 | ≤ 3m -3 and T 2 ∪ V 2 ∪ T a i+1 ∪ a j V ⊆ S 2 , it is then established that (28)

S 2 = T 2 ∪ V 2 ∪ T a i+1 ∪ a j V.
So to conclude our proof, let us define a := a i+1 a j . By ( 16) and (20), it is immediate that a / ∈ A 2 ∪ V 2 , and we want to show that a / ∈ T a i+1 ∪ a j V to reach a contradiction. To this aim, observe first that, by (18) and Proposition 10, there exist x ∈ T and ỹ ∈ V such that (29) a i+1 x / ∈ T a i+1 , ỹa j / ∈ a j V.

Since a i+1 x, ỹa j / ∈ T 2 ∪ V 2 by ( 16), (20), ( 22) and ( 23), it follows from (28) that a i+1 x ∈ a j V and ỹa j ∈ T a i+1 , with the result that it is possible to find b ∈ V and c ∈ T such that (30) a j b = a i+1 x, ỹa j = c a i+1 .

Based on this, suppose first that a ∈ T a i+1 , i.e. there exists z ∈ T such that za i+1 = a i+1 a j , and indeed z = a j by (18). If a j ≺ z, then z ∈ C A (a i+1 ) by ( 19), and hence a i+1 a j = a j a i+1 by Lemma 2, again in contradiction to (18). Thus, z ≺ a j . Furthermore, x a j , as otherwise a i+1 x = xa i+1 ∈ T a i+1 by (19), in contradiction to (29). Using that T A is abelian, it follows from (30) that a j b a j = a i+1 xa j = a i+1 a j x. But a i+1 a j = za i+1 , so in the end a j b a j = za i+1 x. Therefore, b a j ≺ a i+1 x as z ≺ a j , which is absurd since a i+1 b and x a j , to the effect that a i+1 x b a j . This implies, in the end, that a / ∈ T a i+1 . Finally, assume that a ∈ a j V , viz there exists w ∈ V such that a i+1 a j = a j w. By construction of V , a i+1 w, and indeed a i+1 ≺ w by (18). We want to show that c a j . For this purpose, suppose to the contrary that a j ≺ c. The abelianity of V A , together with (19), then yields that c, a i+1 , ỹ ∈ C A (a i+1 ), so a i+1 a j = a j a i+1 by (30) and Lemma 2; this contradicts (18), and hence c a j . Using once more that V A is abelian, it is then immediate from (30) that a i+1 ca i+1 = a i+1 ỹa j = ỹa i+1 a j , so that a i+1 ca i+1 = ỹa j w since a i+1 a j = a j w. But, as argued before, a i+1 ≺ w, whence it is seen that ỹa j ≺ a i+1 c, which in turn is absurd because a i+1 ỹ, by construction of V , and c a j , as proved above. Thus, we get that a / ∈ a j V . Putting all pieces together, it follows that a / ∈ T 2 ∪ V 2 ∪ T a i+1 ∪ a j V , which is however in contradiction to (28), as a is obviously an element of S 2 . Therefore, S A is abelian.

In some sense, Theorem 1 is best possible; specifically, [6, §3] provides the example of a subset S of linearly ordered group generating a nonabelian subgroup and such that |S 2 | = 3 |S| -2.

Corollary 5. Let S be a finite subset of a linearly ordered semigroup, which generates a nonabelian subsemigroup. Then, |S 2 | ≥ 3 |S| -2.

Proof. Nothing to check here; it is just a trivially equivalent formulation of Theorem 1.

( 1 )

 1 |(S 1 S 2 • • • S n ) P | ≥ 1 -n + n i=1 |S i |for any given parenthetization P of A of length n.

Example 5 .

 5 Let A be a semiring, i.e. a 4-tuple of type (A, +, •, 0) consisting of a (nonempty) set A, associative operations + and • from A × A to A (referred to, respectively, as the semiring addition and the semiring multiplication), and a distinguished element 0 ∈ A such that (i) (A, +, 0) is an abelian monoid and (A, •) a semigroup. (ii) multiplication by 0 annihilates A, i.e. 0 • a = a • 0 = 0 for every a ∈ A. (iii) multiplication distributes over addition (from the left and the right), i.e. a • (b + c) = a • b + a • c and (a + b) • c = a • c + b • c for all a, b, c ∈ A.

  c 2 , . . . , c n ∈ A, from which the conclusion follows by a routine induction. (ii) It is a straightforward consequence of the previous point. (iii) Pick a ∈ A and let a 2 a. Again by a routine induction, a n • • • a 2 a for all n ∈ N + , and indeed a n ≺ • • • ≺ a 2 ≺ a if A is strictly ordered, a 2 ≺ a and n ≥ 2.

Proposition 5 .

 5 Let A = (A, •, ) be a linearly ordered semigroup. (i) If a ∈ A and a 2 ≺ a, then ab ≺ b and aba ≺ b for all b ∈ A. (ii) If aba = b for some a, b ∈ A, then A is unital and a is the identity of A. (iii) None of the elements of A has finite period unless A is unital and such an element is the identity. In particular, A is torsion-free. Proof. (i) Pick a, b ∈ A with a 2 ≺ a. Then a 2 b ≺ ab, whence ab ≺ b by totality of and Remark 4. It follows from Proposition 4 that aba 2 ≺ ba; thus, aba ≺ b by the same arguments as before. (ii) Let a, b ∈ A be such that aba = b. Due to Remark 2, we can suppose without loss of generality that a 2 a, which implies the claim by Remark 5 and the previous point (i).

Proposition 7 .

 7 Let A = (A, •, ) be a linearly ordered semigroup and pick a, b ∈ A. If ab ≺ ba, then a n b ≺ a n-1 ba ≺ • • • ≺ aba n-1 ≺ ba n for all n ∈ N + .

Corollary 2 .

 2 Let A = (A, •, ) be a linearly ordered semigroup and a, b ∈ A. If a n b = ba n for some n ∈ N + , then ab = ba.

Proposition 8 .

 8 Suppose that A = (A, •, ) is a linearly ordered magma and let S and T be nonempty finite subsets of A. Then, |ST | ≥ |S| + |T | -1.

Example 9 .

 9 Let A be the interval [1, +∞[ of the real line and the binary operation A × A → A : (a, b) → a b . As a magma, (A, ) is totally ordered by the standard ordering ≤ of the real field, but it is not linearly orderable, since 1 a = 1 b for a, b ∈ A regardless as to whether a = b. With this in mind, let n be a positive integer, S a finite subset of A of size m and P a parenthetization of A of length n. We want to prove that |(S n )| P ≥ (m -1)n + 1. If m = 1 or 1 /∈ S, the claim follows from Corollary 3 in the light of Example 4. Otherwise, let S := S \ {1} and denote by a the minimum of S in (A, ≤). Then, by the same reasoning as before,[START_REF] Neumann | On ordered groups[END_REF]

1 ,Example 10 .

 110 . . . , 1) < a = P(a, 1, . . . , 1) < • • • < P(a, a, . . . , a) = (a n ) P . Let n be a positive integer and A a subsemigroup of the (unital) semigroup of all n-by-n upper (respectively, lower) triangular matrices with positive real entries equipped with the usual row-by-column multiplication. If k ∈ N + and S 1 , S 2 , . . . , S k are nonempty finite subsets of A, then Propositions 1 and 9 yield that|S 1 S 2 • • • S k | ≥ 1 -k + k i=1 |S i |.Proposition 10. Let A = (A, •, ) be a linearly ordered semigroup and S a nonempty finite subset of A of size m, and pick y ∈ A \ C A (S). Then |yS ∪ Sy| ≥ m + 1, so in particular there exist a, b ∈ S such that ya / ∈ Sy and by / ∈ yS.

Corollary 4 .

 4 If S is a finite subset of a linearly ordered semigroup A, then N A (S) = C A (S).

Lemma 1 .Lemma 3 .

 13 Let A be a cancellative semigroup and S a finite subset of A such that S A is abelian. If y ∈ A \ C A (S), then S 2 ∩ (yS ∪ Sy) = ∅.Proof. Pick y ∈ A \ C A (S) and suppose for the sake of contradiction that S 2 ∩ (yS ∪ Sy) = ∅. Then, without loss of generality, there exist a, b, c ∈ A such that ab = cy. As S A is abelian, this gives that cyc = abc = cab, whence ab = yc since A is cancellative, and finally cy = yc.We claim that xy = yx for all x ∈ S. Indeed, let x ∈ S. Then, on the one hand, abx = cyx = ycx = yxc (as we have just seen that cy = yc); on the other, xab = xcy = xyc. But abx = xab (again by the abelianity of S A ), so in the end yxc = xyc, and hence yx = xy (by cancellativity of c). It follows that y / ∈ C A (S), which is absurd. Lemma 2. Let A be a cancellative semigroup and pick a, b, x, y, z ∈ A such that x, y, z ∈ C A (b) and xy = az (respectively, xy = za). Then ab = ba. Proof. On the one hand, xyb = azb = abz since zb = bz; on the other hand, baz = bxy = xyb as x, y ∈ C A (b). Then abz = baz, from which ab = ba (by cancellativity of z). The dual case where xy = za is now immediate by Remark 2. Let A = (A, •, ) be a linearly ordered semigroup and S a nonempty finite subset of A of size m, and pick y

  |V 2 | ≤ |S 2 | -|T 2 ∪ a i+1 T ∪ T a i+1 | ≤ 3m -3 -3i = 3(m -i) -3 = 3 |V | -3.

  Provided that T n (A + ) is the smallest subsemigroup of the multiplicative semigroup of M n (A) generated by U n (A + ) and L n (A + ), it is then natural to ask: Question 1. Is T n (A + ) a linearly orderable semigroup?

	'transpose'.
	taking α L n β for α, β ∈ L n (A + ) if and only if α	L n defined by n β , where the superscript ' ' means U

  2 | ≥ 2m -1 by Corollary 3 and |yS ∪ Sy| ≥ m + 1 by Proposition 10.At long last, we are ready to prove the main theorems of the paper. Theorem 1. Let A be a linearly ordered semigroup and S a finite subset of A of size m such that |S 2 | ≤ 3m -3. Then S A is abelian.Proof. Write I m for the set {1, 2, . . . , m} and let a 1 , a 2 , . . . , a m be a one-to-one enumeration of S, assuming, without loss of generality, thata 1 ≺ a 2 ≺ • • • ≺ a m . Clearly, m ≥ 2. If m = 2 then |S 2 | ≤ 3,and indeed |S 2 | = 3 by Corollary 3; as a 2 1 ≺ a 1 a 2 ≺ a 2 2 and a 2 1 ≺ a 2 a 1 ≺ a 2 2 , it follows that S 2 = {a 2 1 , a 1 a 2 , a 2 2 } and a 1 a 2 = a 2 a 1 , which implies that S A is abelian, as required. So, in what follows, let m ≥ 3 and suppose that B A is abelian for every subset B of A satisfying 2 ≤ |B| < m and |B 2

Acknowledgements

I am grateful to Martino Garonzi (Università di Padova) for attracting my attention to the work of G.A. Freiman, M. Herzog and coauthors which inspired this research.

The author is funded from the European Community's 7th Framework Programme (FP7/2007-2013) under Grant Agreement No. 276487 (project ApProCEM).

1


Sandye Gloria-Palermo

Keywords:

teaching and research institutions in France or abroad, or from public or private research centers.

According to Campagnolo, only archival work can give us an appropriate knowledge of Menger, our understanding of whom comes mostly from the secondary literature or from the unsatisfactory {Au: Is "unsatisfactory" your assessment, or Campagnolo's?} English translations of his books and articles. Of course, the author is aware of the limits of archival work: finding the annotated copy of Say's Traité in Menger's library does not inform us of the extent to which Say may have influenced Menger; the book may have been read after the conception of the Grundsätze or, if we can assert that he had effectively read Say's book before he wrote his own, nothing may help us to understand if Say had been a source of inspiration or if his book simply confirmed Menger's preestablished intuitions. In other words, archival work may turn into a highly speculative exercise if not rigorously carried out. I am not sure, however, that Campagnolo entirely averts this pitfall. Indeed, the author hardly quotes from Menger's manuscript notes, basing his arguments on his private reading of the notes. Under these circumstances, I am ready to credit his interpretations only when they fit my own. When his reading of Menger contradicts my knowledge with, as sole argument, the discovery of an The impression I get is that Campagnolo did not make full use of the potential interpretative resources of the material he analyzes, distilling the quotations to the minimum and leaving the reader somewhat frustrated.

There are, however, a few fortunate exceptions, such as the analysis of the influence of Gossen on Menger, where Campagnolo used the archival material to confirm or invalidate the intuitions {Au: Or do you mean "interpretations"?} of the historian of thought. Consider also his analysis of Menger's attitude toward the use of mathematics; access to Menger's comments in the margins of the books of Gossen and of Auspitz and Lieben allows Campagnolo to affirm that Menger's resistance to the use of mathematics in economic theory cannot be reduced to a question of form, but stems from his rejection of the equilibrium Walrasian framework. I regret once again, however, that, except quoting from Menger's comments on Gossen's book, Campagnolo does not quote any of Menger's annotations on this theme.

If this aspect leaves us a little bit disappointed, there is another aspect of the book that quite deserves the attention of those historians of economic thought who consider their practice as mainly an exercise in full immersion into the historical context of the author they study. From this point of view, Campagnolo's book is undoubtedly a mine of information. If one believes in the relativism of economic theories, she will find here an accurate analysis of the cultural, political, and academic contexts that shaped Menger's reflections. Campagnolo offers us a detailed portrait of the Austrian founder, whom Campagnolo ultimately depicts as a "man of the Enlightenment."

The priority given to the comprehension of the historical context over the theoretical content is flagrant, and it is not in this book that one should look for a linear presentation of Mengerian or Austrian economic theories. Consider for instance the presentation of the first and second generations of Austrian authors: Campagnolo sets the reader straight about the academic relationships between Menger, Wieser, and Böhm-Bawerk, about the difficulties met by Mises and Hayek during their American exile, about the role of Rothbard in raising {Au: I.e., "forming"?} a libertarian American academic lobby, and so on; but few words if any are spent describing Wieser's theory of imputation, Böhm-Bawerk's theory of capital, Lachmann's theory of institutions, and the like. As a matter of fact, Campagnolo defines the Austrian tradition as a set of antitheses. There are a few exceptions, such as the reflections-the rapid reflections-on the theoretical connections between Menger and Weber and, more surprisingly-and even more rapidly-between Menger and Karl Polanyi. Campagnolo suggests here that Weber and Polanyi would have grasped what constitutes the essence of the Mengerian message and elaborated their own views starting precisely from these Mengerian aspects neglected by his official followers. These original reflections are, however, diluted into the relativist approach privileged by the author. {Au: I don't understand the last two sentences. Weber and Polanyi "would have grasped" the essence of Menger's message if they had started from the Mengerian aspects neglected by his official followers?} Throughout the book, there is a theme that gets out while the going is good {Au: This is not really idiomatic. There is a phrase, "to get while the getting is good," and that is perhaps what you are thinking of. What do you mean here, literally?}, thanks precisely to the methodological choice of the author: the Methodenstreit is very well documented and is perhaps the most detailed analytical subject of the book to which the author puts his knowledge of the intellectual Austrian context to good use for an analytical comprehension of the controversy.

This successful example of retrospective analysis represents a middle ground between pure relativism and pure absolutism.

The author is currently preparing a translation in French of the Grundzätze, one of the Untersuchungen, and also a translation of the notes that Carl Menger prepared for the second edition of his Grundzätze. No doubt the access to these notes will inject new enthusiasm and revitalize studies on Menger. This book represents the appetizer of a meal that holds a few surprises {Au: Surprises that will be pleasant, I take it?} in store.

Sandye Gloria-Palermo, University of the French West Indies, Guadalupa

1

  Carl Menger: Entre Aristote et Hayek; Aux sources de l'économie moderne. By Gilles Campagnolo. Paris: CNRS éditions, 2008. 236 pp. €26.00. This book is one of the outcomes of the meticulous archival work that Gilles Campagnolo is carrying out. With this book, Campagnolo offers us a synthesis in French of the current knowledge on the life and work of Carl Menger, enriched with the considerations he has drawn from Menger's archives. The Hitotsubashi University in Japan stores about twenty thousand volumes of Menger's personal library, most of them annotated by hand; there is also the annotated version of his own Grundsätze der Volkswirtschaftslehre, of which Menger was planning a new edition that was ultimately completed by his son.

"

  outraged" exclamation mark in the margin of a volume, I don't think that I should reconsider my whole position simply because I have no proof that Menger used exclamation marks as a sign of dismissal! {Au: I don't quite understand. Do you mean that you should not reconsider your position just because Menger may, according to Campagnolo, have used exclamation marks as a sign of dismissal?}


Denis Dochain
email: denis.dochain@uclouvain.be

Patrick De Leenheer
email: deleenhe@ufl.edu

Alain Rapaport
email: rapaport@supagro.inra.fr

About Transgressive Over-Yielding in the Chemostat

Keywords: Chemostat, steady-state, optimization, over-yielding

  L'archive ouverte pluridisciplinaire

Introduction

The study of biodiversity and environment on the functioning of ecosystems is one of the most important issues in ecology nowadays (see for instance [START_REF] Replansky | The relationship between environmental complexity, species diversity and productivity in a natural reconstructed yeast community[END_REF]).

Recent investigations on the functioning of microbial ecosystems has revealed that combinations of certain species and resources enhance the functioning of the overall ecosystem, leading to a "transgressive overyielding" ( [START_REF] Schmid | Biodiversity effects and transgressive overyielding[END_REF][START_REF] Langenheder | Bacterial biodiversity-ecosystem functioning relations are modified by environmental complexity[END_REF]). In those experiments, the environment is modified by altering the composition of the resources and its richness ( [START_REF] Tylianakis | Resource heterogeneity moderates the biodiversity-function relationship in real world ecosystems[END_REF]). In the literature in ecology, the consideration of spatial heterogeneity in the environment (niches, islands...) is often promoted as a leading factor for the explanation and prediction of abundance and distribution of species and resources in ecosystems. Comparatively, the influence of the spatialization on the performances of the functioning of ecosystems has been much more rarely studied ( [START_REF] Eriksson | Biotic habitat complexity controls species diversity and nutrient effects on net biomass production[END_REF]).

From the view point of the industry of biotechnology and waste water treatment, the spatial decoupling of bio-transformation is known to impact significantly the yield conversion, and engineers are looking for design of bio-processes that offer the best performances (see [START_REF] Luyben | Optimal design for continuously stirred tank reactors in series using michaelis-menten kinetics[END_REF][START_REF] Hill | Minimum tank volumes for cfst bioreactors in series[END_REF][START_REF] De Gooijer | Bioreactors in series : an overview of design procedures and practical applications[END_REF][START_REF] Harmand | Towards a unified approach for the design of interconnected catalytic and auto-catalytic reactors[END_REF]). For instance, a series of continuous stirred bioreactors is known to be potentially more efficient than a single one (for precise distributions of the volumes) in [START_REF] Harmand | Optimal design of two interconnected bioreactors-some new results[END_REF][START_REF] Harmand | Optimal design of 2 interconnected enzymatic reactors[END_REF][START_REF] Nelson | Evaluating the performance of a cascade of two bioreactors[END_REF]. Recent investigations on the chemostat model have revealed that other simple spatial motifs, such as parallel interconnections of tanks, can also present interesting benefits ( [START_REF] Haidar | Effects of spatial structure and diffusion on the performances of the chemostat[END_REF]). In this framework, most of the studies are conducted for a single species. Only a few of them investigate the role of biodiversity and spatial heterogeneity on the performances of the ecosystem ( [START_REF] Stephanopoulos | Effect of inhomogeneities on the coexistence of competing microbial populations[END_REF][START_REF] Rapaport | Coexistence in the design of a series of two chemostats[END_REF]).

In the present work, we show that spatialization can be another factor responsible for a transgressive over-yielding. For this purpose, we consider the usual framework of the chemostat and show that splitting one volume into two tanks in parallel with different dilution rates can enhance the performances at steady state when two different species are present in each vessel, compared to the situations of having the same species present in both volumes. Here, optimal performance is achieved when the value of the nutrient at steady state in the outflow of the system is minimized. This notion is inspired by the scenario of waste water treatment processes where the input nutrient to the reactor is the pollutant, and the purpose of the treatment plant is to minimize the pollutant concentration.

2 One species

One reactor

Let a chemostat be operated with constant volumetric flow rate Q, constant volume V , and constant input nutrient concentration S in . We call D = Q/V the dilution rate. In case only 1 species is present, the equations for the nutrient concentration S(t) and the species concentration x(t), are:

Ṡ = D(S in -S) - f (S) γ x (1) ẋ = x(f (S) -D) (2)
where γ ∈ (0, 1] is the yield of the conversion of nutrient into species biomass, and f (S) is the per capita growth rate, a smooth, increasing function (with f ′ (S) > 0 for all S ≥ 0) with f (0) = 0. We also assume that f is concave, i.e. f ′′ (S) ≤ 0 for all S ≥ 0. Finally, we let D * = f (S in ).

A typical example satisfying all these conditions would be the Monod function f (S) = mS/(a + S) for positive a and m.

The first statement of the following result is well-known (see for instance the textbook [START_REF] Smith | The theory of chemostat, dynamics of microbial competition[END_REF]).

Proposition 1 Let x(0) > 0. Every solution (S(t), x(t)) of (1) -(2) satisfies:

lim t→+∞ S(t) = λ(D), where λ(D) = f -1 (D), if D ≤ D * , and = S in , if D > D * (3)
The (continuous) function λ(D) is increasing on [0, D * ) (since λ ′ > 0 there) and nondecreasing on [0, +∞).

λ(D) is convex if D ∈ [0, D * ) (since λ ′′ ≥ 0 there), but not if D ∈ [D * , ∞).
Proof . That λ(D) is continuous, is obvious from the definition, and that it is increasing on [0, D * ) follows from the fact that it is the inverse function of the increasing function f (S), S ∈ [0, S in ). To show the convexity of λ(D) for D ∈ [0, D * ) we implicitly differentiate f -1 (f (S)) = S, S ∈ [0, S in ], twice:

(f -1 ) ′ (f (S))f ′ (S) = 1 ⇒ (f -1 ) ′′ (f (S))(f ′ (S)) 2 + (f -1 ) ′ (f (S))f ′′ (S) = 0,
and thus that

(f -1 ) ′′ = - (f -1 ) ′ f ′′ (f ′ ) 2
Since f ′ > 0 and hence also (f -1 ) ′ > 0, and since f ′′ ≤ 0, it follows that (f -1 ) ′′ ≥ 0, hence f -1 is convex, and therefore so is λ(D) as long as D ∈ [0, D * ). Nonconvexity of λ(D) when D ∈ [0, +∞) follows by picking an arbitrary D > D * , and letting D * = p0 + (1 -p) D for an appropriate p ∈ (0, 1). It follows that:

λ(p0 + (1 -p) D) = λ(D * ) = S in > (1 -p)S in = (1 -p) D = pλ(0) + (1 -p)λ( D),
and thus λ(D) is not convex if D ∈ [0, +∞).

Two reactors

Assume that we split the inflow channel to the chemostat in two channels, and the reactor volume in two parts. The first reactor is fed by the first channel with volumetric flow rate αQ for some α ∈ [0, 1] and it has volume rV for some r ∈ [0, 1]. The second reactor is fed by the second channel with volumetric flow rate (1 -α)Q, and it has volume (1 -r)V . Note that the total reactor volume of both reactors equals the initial single reactor volume. Note also that the initial inflow channel has simply been split into two channels. Of course, we assume that for both species into bioreactors optimal environmental conditions (temperature, pH etc.) are applied.

To determine the asymptotic value of the nutrient concentration in each of the two reactors, we use the Proposition from the previous section. This value is completely determined by the dilution rate that each reactor experiences. For the first reactor, this dilution rate is

αQ rV = α r D, whereas it is (1 -α)Q (1 -r)V = 1 -α 1 -r D
for the second reactor. Therefore, the asymptotic nutrient values are

λ α r D and λ 1 -α 1 -r D ,
in the first and second reactor respectively. Assume that we mix the outflows of both reactors (in the same proportions α and 1 -α as the volumetric flow rates at their respective input channels). The asymptotic value of the nutrient in the mixture is then given by the function

F (α, r) := αλ α r D + (1 -α)λ 1 -α 1 -r D , (4)
where (α, r) ∈ (0, 1) 2 . Clearly, this function is smooth in (0, 1) 2 . We would like to extend it to [0, 1] 2 . First we extend it continuously to (α, r) = (0, 0) and = (1, 1) by defining

F (α, 0) := αS in + (1 -α)λ ((1 -α)D) for α > 0, F (α, 1) := αλ (αD) + (1 -α)S in for α < 1
Finally, we continuously extend it to [0, 1] 2 by defining:

F (0, 0) = F (1, 1) := λ(D)
An important property of F is that:

F (α, r) = λ(D), whenever α = r.
This is not surprising since all configurations with α = r result in the same dilution rate D for each of the two reactors, which is the same as the dilution rate of the initial single reactor. The asymptotic nutrient concentrations in each reactor will be the same, and equal to λ(D), which equals the asymptotic nutrient concentration of the single reactor. The mixing of these concentrations with proportions α and 1 -α, yields λ(D). In other words, for these configurations, the splitting of the reactor is merely artificial, and the asymptotic outcome is the same as if the reactor would not have been split at all. An obvious question is to determine those configurations (α, r) where F (α, r) is minimal, and also to see if these minima are lower than the corresponding value λ(D) which is obtained in case of a single reactor (or in case of any configuration satisfying α = r in view of the remark above)

We first define a convex polygonal region in the unit square [0, 1] 2 :

C = {(α, r) ∈ [0, 1] 2 | (α/r)D ≤ D * and ((1 -α)/(1 -r)) D ≤ D * }
and we note that C is a nontrivial set (i.e. has nonzero Lebesgue measure) if and only if

D < D * ,
an assumption we make in the remainder of this paper. This condition on D simply expresses that in case of a single reactor, the asymptotic nutrient concentration λ(D) will be strictly less than the maximal possible value S in . Next, we also define two triangular regions in [0, 1] 2 :

T 1 = {(α, r) ∈ [0, 1] 2 | (α/r)D > D * } T 2 = {(α, r) ∈ [0, 1] 2 | ((1 -α)/(1 -r)) D > D * )}
and we note that C, T 1 and T 2 are pairwise disjoint, and that they cover [0, 1] 2 .

The following Lemma is usefull for the following.

Lemma 1 The function

δ : (α, r) ∈ [0, 1] × (0, 1] → α 2 r ( 5
)
is convex on its domain.

Proof . One has

δ α = 2α r , δ r = - α 2 r 2
, and furthermore

δ αα = 2 r , δ rr = 2 α 2 r 3 , δ αr = - 2α r 2 .

It follows that

δ αα > 0 , δ rr > 0 , δ αα δ rr -δ 2 αr = 0 . Thus the Hessian of δ is positive semi-definite.

We introduce the following function

T in (D) = λ(D) + Dλ ′ (D) (6)
that plays an important role in the following.

The following Proposition shows that the performance of a single species chemostat can only be improved if S in is small enough, and this is achieved by bypassing the second reactor with a unique, specific flow rate.

Proposition 2 The restriction of F to the convex set C, F | C , is convex. Moreover there holds that

min [0,1] 2 F = λ(D) = F (α, α), ∀α ∈ [0, 1], for S in ≥ T in (D) min α F (α, 0) < λ(D), for S in < T in (D)
Proof . Let us first show that F | C is convex. We consider the functions L and R defined on C:

L(α, r) = αλ α r D , R(α, r) = (1 -α)λ 1 -α 1 -r D (7)
and show that L and R are convex on C.

Let (α 1 , r 1 ), (α 2 , r 2 ) belong to C and µ be a number in [0, 1]. One has

Γ = µL(α 1 , r 1 ) + (1 -µ)L(α 2 , r 2 ) = µα 1 λ α 1 r 1 D + (1 -µ)α 2 λ α 2 r 2 D = (µα 1 + (1 -µ)α 2 ) µα 1 µα 1 + (1 -µ)α 2 λ α 1 r 1 D + (1 -µ)α 2 µα 1 + (1 -µ)α 2 λ α 2 r 2 D
By convexity of the function λ, it follows

Γ ≥ (µα 1 + (1 -µ)α 2 )λ µα 2 1 /r 1 + (1 -µ)α 2 2 /r 2 µα 1 + (1 -µ)α 2 D = (µα 1 + (1 -µ)α 2 )λ µδ(α 1 , r 1 ) + (1 -µ)δ(α 2 , r 2 ) µα 1 + (1 -µ)α 2 D
The function λ being increasing and δ being convex (see the former Lemma), one obtains

Γ ≥ (µα 1 + (1 -µ)α 2 ). λ δ(µα 1 + (1 -µ)α 2 , µr 1 + (1 -µ)r 2 ) µα 1 + (1 -µ)α 2 D = (µα 1 + (1 -µ)α 2 )λ µα 1 + (1 -µ)α 2 µr 1 + (1 -µ)r 2 D = L(µα 1 + (1 -µ)α 2 , µr 1 + (1 -µ)r 2 )
Similarily, it can be shown that R is convex on C. The function F being the sum of the two functions L and R, one concludes that F is also convex on C.

For (α, r) ∈ int(C), we have that

F α = λ α r D + αD r λ ′ α r D -λ 1 -α 1 -r D (8)
- (1 -α)D 1 -r λ ′ 1 -α 1 -r D (9)
F r = - α 2 D r 2 λ ′ α r D + (1 -α) 2 D (1 -r) 2 λ ′ 1 -α 1 -r D (10)
We note from ( 9) and ( 10) that every point on the diagonal where α = r in int(C) is a critical point, i.e.:

F α | α=r = F r | α=r = 0,
and thus, since

F is convex in C, it follows that min C F = λ(D) = F (α, α), ∀α ∈ [0, 1] (11)
Since [0, 1] 2 is the disjoint union of C, T 1 and T 2 , the proof of the Proposition will be complete if we study the minimisation of F on T 1 and T 2 . Notice that

T 2 = {(α, r) ∈ [0, 1] 2 | (1 -α, 1 -r) ∈ T 1 } and F (α, r) = F (1 -α, 1 -r).
Consequently, one has min T1 F = min T2 F , and we can study the restriction of F to T 1 only. When (α, r) ∈ T 1 , then

F (α, r) = αS in + (1 -α)λ 1 -α 1 -r D
Note that F has no critical points in int(T 1 ) because

F r = (1 -α) 2 D (1 -r) 2 λ ′ 1 -α 1 -r D > 0,
and thus the extrema of F | T1 are necessarily located on the boundary of T 1 . We calculate the values of F on the various parts of the boundary of T 1 , and bound them below:

F (α, 0) = αS in + (1 -α)λ((1 -α)D) F (1, r) = S in ≥ λ(D) F (α, α D D * ) = αS in + (1 -α)λ 1 -α 1 -α D D * D ≥ αS in + (1 -α)λ((1 -α)D) = F (α, 0)
where we used that λ(.) is non-decreasing. One has

F α (α, 0) = S in -λ((1 -α)D) -Dλ ′ ((1 -α)D)(1 -α) F αα (α, 0) = 2Dλ ′ ((1 -α)D) + D 2 λ ′′ ((1 -α)D)(1 -α)
and one concludes that α → F (α, 0) is strictly convex, λ being a convex increasing function on the domain [0, D]. Furhermore, one has

F α (0, 0) = S in -T in (D) F α (1, 0) = S in
Consequently, the unique minimum of F (α, 0) over α is reached at α = 0 exactly when F α (0, 0) ≥ 0, that is to write S in ≥ T in (D). Finally, notice that one has F (0, 0) = λ(D) and the proof of the Proposition now follows from [START_REF] Rapaport | Coexistence in the design of a series of two chemostats[END_REF].

Remark 1 When S in < T in (D) the best configuration is obtained for the by-pass of one tank with α different than 0 or 1. For the Monod function, the threshold on S in has the following expression

T in (D) = Da m -D 1 + m m -D .

Two species

We consider two species with respective per capita growth rate functions f 1 and f 2 , satisfying the conditions of a single species we imposed in the previous section. We assume that there is a unique S ∈ (0, S in ) such that

f 1 (S) > f 2 (S) if S ∈ (0, S) f 2 (S) > f 1 (S) if S ∈ ( S, +∞) and we let D = f 1 ( S) = f 2 ( S), D * 1 = f 1 (S in ), D * 2 = f 2 (S in ) We assume as before that D < min(D * 1 , D * 2 )
Definition 1 We say that a configuration (α, r) ∈ (0, 1) 2 corresponds to transgressive overyielding if

G(α, r) := αλ 1 α r D + (1 -α)λ 2 1 -α 1 -r D < min(F 1 (α, r), F 2 (α, r)), (12)
where λ i is defined as in (3) but with f = f i and D * = D * i , and F i is defined as in (4) but with λ = λ i .

Let us first consider the case where α = r. Then

G(α, α) = αλ 1 (D) + (1 -α)λ 2 (D) F 1 (α, α) = αλ 1 (D) + (1 -α)λ 1 (D) = λ 1 (D) F 2 (α, α) = αλ 2 (D) + (1 -α)λ 2 (D) = λ 2 (D)
Consequently, since any convex combination of two non-negative numbers cannot be smaller than the smallest of these two numbers, it follows that

G(α, α) = αλ 1 (D) + (1 -α)λ 2 (D) ≥ min(λ 1 (D), λ 2 (D)) = min(F 1 (α, α), F 2 (α, α)), (13)
which implies that no configuration with α = r can correspond to transgressive overyielding. Moreover, if λ 1 (D) = λ 2 (D), then the inequality in ( 13) is strict for all α ∈ (0, 1). By continuity of G, F 1 and F 2 this inequality remains strict for all configurations (α, r) near such configurations where α = r and α ∈ (0, 1), implying that we will not find configurations corresponding to transgressive overyielding nearby. On the other hand, if λ 1 (D) = λ 2 (D) = S, or equivalently if D = D, then the inequality in (13) reduces to an equality for all α ∈ (0, 1). In this case we show that there always exist configurations nearby corresponding to transgressive overyielding. The two next Propositions show that there always exist configurations of two parallel chemostats with only one of the species in each reactor volume that perform better than in the case in which for the same configuration, only one of the species is present in both reactors, regardless of the selected species.

Proposition 3 Let D = D and fix α ∈ (0, 1). Then there always exist configurations (α, r) near (α, α) that correspond to transgressive overyielding.

Proof . We start with the simple observation that for any (α, r) ∈ (0, 1)

2 : α r 1 ⇐⇒ 1 - α 1 -r 1
Therefore, for fixed α ∈ (0, 1), we can always find (α, r) ∈ (0, 1)

2 near (α, α) such that α r D < D < 1 - α 1 - r D Moreover, since D = D < min(D * 1 , D * 2 )
, we may assume w.l.o.g. that

1 - α 1 - r D < min(D * 1 , D * 2 )
The properties of f 1 and f 2 imply that:

0 < λ 1 α r D < λ 2 α r D < S < λ 2 1 - α 1 - r D < λ 1 1 - α 1 - r D < S in
and thus in particular that:

0 < λ 1 α r D < λ 2 α r D < λ 2 1 - α 1 - r D < λ 1 1 - α 1 - r D
There holds that

G(α, r) = αλ 1 α r D + (1 -α)λ 2 1 - α 1 - r D F 1 (α, r) = αλ 1 α r D + (1 -α)λ 1 1 - α 1 - r D F 2 (α, r) = αλ 2 α r D + (1 -α)λ 2 1 - α 1 - r D
Noting that each of G(α, r), F 1 (α, r) and F 2 (α, r) is a convex combination with the same weights α and 1 -α of a pair of distinct positive numbers from a collection of four positive numbers that are ordered as indicated by [START_REF] Smith | The theory of chemostat, dynamics of microbial competition[END_REF], it follows that: G(α, r) < min (F 1 (α, r), F 2 (α, r)) , and thus the configuration (α, r) corresponds to transgressive overyielding.

The case where D = D, can be handled similarly:

Proposition 4 Let D = D. Then there exist (α, r) ∈ (0, 1) 2 such that α r D < D < 1 -α 1 -r D < min(D * 1 , D * 2 ) (14)
and this configuration (α, r) corresponds to transgressive overyielding.

Proof .

Using the fact that D, D < min(D * 1 , D * 2 ), it is not hard to show that there always exist (α, r) ∈ (0, 1) 2 such that (14) holds. Indeed, the half spaces {(α, r)|α/r < D/ D} and {(α, r)|(1 -α)/(1 -r) < min(D * 1 , D * 2 )/D} are easily seen to intersect in the open unit square (0, 1) 2 . From this follows that (14) holds with (α, r) replaced by (α, r), and then the rest of the proof of the previous Proposition can be carried out with (α, r) replaced by (α, r). In conclusion, the configuration (α, r) corresponds to transgressive overyielding.

Numerical examples

We consider two species whose graphs of growth functions f i (i = 1, 2) intersect away from zero :

f 1 (s) = 2s 3 + s , f 2 (s) = s 0.3 + s
One can easily check that f 1 (S ⋆ ) = f 2 (S ⋆ ) for S ⋆ = 2.4. For the simulations, we have chosen D = 0.9 that is slightly above f 1 (S ⋆ ) = f 2 (S ⋆ ) = 0.88 (see Figure 1). For this value of the dilution rate D, the break-even concentrations of the two species are

λ 1 (D) = 2.499 , λ 2 (D) = 2.993
The thresholds given by formula (6) are Table 1: Best values of by-pass configurations.

We have studied numerically three values of S in , larger than both thresholds, in between or lower. The best values for the bypass configurations are reported on the following table For S in = 40, the best configuration is obtained for α = 0.41 and r = 0.36 that achieves the minimum of G equal to 0.234, which represents a gain of 12% compared to having the best species (the first one) in a single tank. Accordingly to the Table 1, the best configurations for S in = 10 and S in = 5 are obtained for the bypass of the first tank, using the second species only in the second tank (although this species has the worst break-even concentration). Nevertheless, we show on Figures 2 and3 the benefit of the parallel configuration with non-null volumes for different distributions of the volumes given by the parameter r.

One can check that in any case the minimum of G(•, r) over α is lower than min(λ 1 (D), λ 2 (D)) and is reached for a value of α close to r.

Conclusion

Our main contribution is to show that whatever are monotonic growh rate functions of two species, whose graphs have an intersection away from the origin, there always exist configurations of two parallel chemostats with only one of the species in each reactor volume that perform better than in the case in which for the same configuration, only one of the species is present in both reactors, regardless of the selected species. We beleive that this result is of interest for potential applications in bio-industry. Further investigations could be conducted to determine more precisely what gain could be expected. Our simulations show that this gain could be significant. Centrum) for hosting him as a research fellow during a sabbatical leave from the University of Florida. PDL also gratefully acknowledges support received from the University of Florida through a Faculty Enhancement Opportunity, and the Université Catholique de Louvain-la-Neuve for providing him with a visiting professorship in the fall of 2011.

Figure 1 :

 1 Figure 1: Growth curves and dilution rate D

Figure 2 :

 2 Figure 2: Graphs of F i (•, r) and G(•, r) for S in = 10

Figure 3 :

 3 Figure 3: Graphs of F i (•, r) and G(•, r) for S in = 5

Acknowledgments This research was initiated at INRA in Montpellier during a visit of DD and PDL there. They wish to express their gratitude for the opportunity. PDL thanks VLAC (Vlaams Academisch