Kilian Gebhardt

Frédéric Meunier

Sylvain Salvati

O n IS AN n-MCFL

Commutative properties in formal languages pose problems at the frontier of computer science, computational linguistics and computational group theory. A prominent problem of this kind is the position of the language O n , the language that contains the same number of letters a i and āi with 1 i n, in the known classes of formal languages. It has recently been shown that O n is a Multiple Context-Free Language (MCFL). However the more precise conjecture of Nederhof that O n is an MCFL of dimension n was left open. We present two proofs of this conjecture, both relying on tools from algebraic topology. On our way, we prove a variant of the necklace splitting theorem.

It is usual to present derivations as trees where nodes have the following form:

G A(s 1 , . . . , s n ) when from the derivations of the G B i (s i,1 , . . . , s i,l i ) we can derive G A(s 1 , . . . , s n ) using a rule of G. When p equals 0, there is no derivation above the bar. This means that rules with no right-hand part form the leaves of these trees.

Using this notation we can show as follows that a 1 a 1 ā2 ā1 ā1 a 2 is in the language of G 2 . We use colors to identify each letter and allow one to infer the rules used in the derivation:

G 2 I(a 1 , a 1 ā2 ā1 ā1 a 2 ) G 2 S(a 1 a 1 ā2 ā1 ā1 a 2 ) 3. Main result

Introduction

The language O n is the language built on the alphabet Σ n = {a i , āi | i ∈ [n]} and that contains exactly all words w which, for every i in [n], have the same number of occurrences of a i and āi . Writing |w| c the number of occurrences of the letter c in w, this condition becomes |w| a i = |w| āi for all i in [n]. The problem of situating the languages O n within known classes of languages has been raised at least in two different communities.

The first one is that of computational linguistics. This problem has attracted attention with a language called M IX (also called the Bach language as it was introduced by Bach [Bac81, [START_REF] Bach | Categorial grammars as theories of language[END_REF][START_REF] Pullum | Context-freeness and the computer processing of human languages[END_REF]) that is rationally equivalent to O 2 . It was related to the research program of Joshi [START_REF] Aravind | Tree-adjoining grammars: How much context sensitivity is required to provide reasonable structural descriptions[END_REF] which consists in formally describing the class of languages corresponding to Natural Languages. According to Joshi's terminology, this is the class of Mildly Context Sensitive Languages. This program tries to give abstract properties of this class while describing possible candidates [START_REF] Weir | Characterizing mildly context-sensitive grammar formalisms[END_REF][START_REF] Aravind | The converence of mildly context-sensitive grammar formalisms[END_REF]. Among such candidates, a powerful one is formed by Multiple Context Free Languages (MCFL) [START_REF] Seki | On multiple context free grammars[END_REF]. According to Joshi et al. [START_REF] Aravind | The converence of mildly context-sensitive grammar formalisms[END_REF] the language "M IX can be regarded as the extreme case of free word order" and Mildly Context Sensitive Languages should "perhaps" not contain M IX (and thus O 2 ). This paper also mentions that the position of M IX in classes of languages, such as Tree Adjoining Languages, is not known and difficult to establish. In particular, it stresses that it is not known whether M IX is an Indexed Language.

The second community that has also shown interest for the problem is that of computational group theory which tries to identify properties of groups by means of properties of their word problem. The word problem for a group consists in describing the language of words that are equal to zero for a given presentation (all presentations giving rise to rationally equivalent languages). For example, Muller and Schuppe have characterized virtually free groups as exactly those groups whose word problems are solved by context free grammars [START_REF] Muller | Groups, the theory of ends, and context-free languages[END_REF]. A question that has been raised by that community is whether O 2 -which coincides with the language corresponding to the word problem for the additive group (Z 2 , +)-is an Indexed Language [START_REF] Gilman | Formal languages and their application to combinatorial group theory[END_REF]. This question remains open. MCFL form a natural generalization of "copyless" Macro-Languages (see [START_REF] Seki | On the generative power of multiple context-free grammars and macro grammars[END_REF] for a discussion) and Macro-Languages are equivalent to Indexed Languages. This makes the question of whether O 2 belongs to MCFL relevant.

A first important result in that line of research is that O 2 is not a well-nested MCFL of dimension 2 [START_REF] Kanazawa | MIX is not a tree-adjoining language[END_REF], which solves a long-standing open problem raised by Joshi [START_REF] Aravind | Tree-adjoining grammars: How much context sensitivity is required to provide reasonable structural descriptions[END_REF]. Subsequently it has been shown that it is actually an MCFL [START_REF] Salvati | MIX is a 2-MCFL and the word problem in is captured by the IO and the OI hierarchies[END_REF] and more precisely an MCFL of dimension 2 (a 2-MCFL). Nederhof [START_REF] Nederhof | A short proof that O 2 is an MCFL[END_REF] has given a similar proof of the same result. Later he conjectured that O n is an n-MCFL [START_REF] Nederhof | Free word order and MCFLs[END_REF]. As pointed in this work, a simple pumping argument shows that O n cannot be an MCFL of dimension strictly smaller than n. More recently, a breakthrough has been achieved by Ho [START_REF] Ho | The word problem of Z n is a multiple context-free language[END_REF] who proved that O n is an MCFL for every n. However the MCFL constructed in the proof is of dimension larger than n, namely 8 n+1 2 -2. All proofs related to these results are based on algebraic topology. While the proofs of [START_REF] Salvati | MIX is a 2-MCFL and the word problem in is captured by the IO and the OI hierarchies[END_REF] and [START_REF] Nederhof | A short proof that O 2 is an MCFL[END_REF] strongly rely on topological properties of the plane (existence of winding numbers of curves around points), the aforementioned proof by Ho is based on the well-known Borsuk-Ulam theorem, a powerful theorem from algebraic topology which holds in any dimension. More specifically, it uses a combinatorial application of this theorem, due to Alon and West [START_REF] Alon | The Borsuk-Ulam theorem and bisection of necklaces[END_REF]: the necklace splitting theorem. In this paper, we also rely on related tools to prove Nederhof's conjecture, namely that O n is an n-MCFL. Nederhof actually conjectures that a particular Multiple Context-Free Grammar (MCFG) of dimension n defines O n . We prove a slightly stronger result by showing that a grammar that uses a more restricted kind of rules is sufficient to define O n .

The article is structured as follows: In Section 2, we introduce notation regarding formal languages and MCFG as well as the grammar G n , which is an MCFG of dimension n. Section 3 establishes the main result namely that the language of G n is O n using a decomposition lemma. The decomposition lemma can on the one hand be derived from a variant of the necklace splitting theorem that we prove in Section 4. Alternatively, it can be obtained via purely combinatorial proofs presented in Section 5.

Background on Multiple Context Free Grammars

We write [n] for the set {1, . . . , n}. For a given finite set Σ, also called alphabet, we write Σ * for the monoid freely generated by Σ, and Σ + for the free semigroup generated by Σ. The elements of Σ are called letters while the elements of Σ * and Σ + are called strings or words and we write ε for the empty word. Given a word w, we write |w| for its length, and |w| c for the number of occurrences of the letter c in w. A language is a subset of Σ * .

We define the language

O n as {w ∈ Σ * n | |w| a i = |w| āi for i ∈ [n]} where Σ n is the alphabet {a i , āi | i ∈ [n]}. For α in Σ n , writing ᾱ exchanges a i and āi : if α is a i , then ᾱ is āi ; if α is āi , then ᾱ is a i .
Two letters α and β of Σ n are compatible when α = β. We extend the (•) operation to words in Σ * n as follows: the word w is obtained from w by applying (•) to each of its letters.

A ranked alphabet Ω is a pair (A, ρ) where A is a finite set and ρ is a function from A to N. For a in A, the integer ρ(a) is the rank of a. We shall write Ω (n) for the set {a ∈ A | ρ(a) = n}. The dimension of a ranked alphabet is the maximal rank of its elements.

A Multiple Context Free Grammar (MCFG) G is a tuple (Ω, Σ, R, S) where Ω is a ranked alphabet of non-terminals, Σ is a finite set of letters, R is a set of rules and S is an element of Ω (1) called initial non-terminal. The rules in R are of the form (1)

A(w 1 , . . . , w n ) ⇒ B 1 (x 1,1 , . . . , x 1,l 1 ), . . . , B p (x p,1 , . . . , x p,lp )

where A is in Ω (n) , B k is in Ω (l k ) , the x k,j are pairwise distinct variables and the w j are elements of (Σ ∪ X) * with X = {x k,j | k ∈ [p] ∧ j ∈ [l k ]} and with the restriction that each x k,j may have at most one occurrence in the string w 1 • • • w n . Note that p may be equal to 0, in which case the right part of the rule (the one on the right of the ⇒ symbol) is empty.

Then we may write the rule by omitting the symbol ⇒. The dimension of an MCFG is that of its ranked alphabet of non-terminals. An MCFG of dimension at most n is an n-MCFG.

An MCFG such as G defines judgments of the form G A(s 1 , . . . , s n ) where A is in Ω (n) and the s j belong to Σ * . The notion of derivable judgments is defined inductively: suppose we are given p derivable judgments G B k (s k,1 , . . . , s k,l k ) where B k ∈ Ω (l k ) for k in [p]. For each rule of the form (1), the judgment G A(s 1 , . . . , s n ) is derivable when each s j is obtained from w j by replacing each occurrence of the variable x k,j by s k,j . The language defined by G, denoted by L(G), is the set {w ∈ Σ * | G S(w) is derivable}. The class of languages that are definable by MCFGs is the class of Multiple Context-Free Languages (MCFL). Likewise, the class of languages definable by n-MCFGs is the class of n-Multiple Context-Free Languages (n-MCFL).

We define now G n , the central n-MCFG for which we prove that it generates O n . It uses two non-terminals S and I that are respectively of rank 1 and n. The non-terminal S is the initial one. The alphabet of G n is Σ n . The rules of the grammar G n are the following:

(1) S(

x 1 • • • x n ) ⇒ I(x 1 , . . . , x n ).
(2) I(w 1 , . . . , w n ) ⇒ I(x 1 , . . . , x n ), I(y 1 , . . . , y n ) for all w 1 , . . . , w n ∈ {x 1 , . . . , x n , y 1 , . . . , y n } * such that

w 1 • • • w n = x 1 y 1 • • • x n y n .
(3) I(w 1 , . . . , w n ) ⇒ I(x 1 , . . . , x n ) for all w 1 , . . . , w n and all α ∈ Σ n , k, ∈ [n] such that w j = x j for j = k, and • k = implies w k ∈ {αx k , x k α} and w ∈ {ᾱx , x ᾱ}.

• k = implies w k = αx k ᾱ. (4) I(ε, . . . , ε). Items numbered (2) and (3) describe finite sets of rules. The rules (2) are parametrized by a particular factorization (w 1 , . . . , w n ) of x 1 y 1 • • • x n y n . For example, when n = 3 letting w 1 = x 1 y 1 x 2 , w 2 = y 2 x 3 and w 3 = y 3 is such a factorization; we have w 1 w 2 w 3 = x 1 y 1 x 2 y 2 x 3 y 3 . A rule of the form (3) adds a compatible pair of letters at distinct endpoints of the words. For example, I(a 1 x 1 , x 2 , ā1 x 3 , x 4 ) ⇒ I(x 1 , x 2 , x 3 , x 4 ) is such a rule for n = 4.

Example 1. The grammar G 2 contains the following rules:

S(x 1 x 2 ) ⇒ I(x 1 , x 2 ) I(x 1 y 1 x 2 y 2 , ε) ⇒ I(x 1 , x 2 ), I(y 1 , y 2 ) I(x 1 y 1 x 2 , y 2 ) ⇒ I(x 1 , x 2 ), I(y 1 , y 2 ) I(x 1 y 1 , x 2 y 2 ) ⇒ I(x 1 , x 2 ), I(y 1 , y 2 ) I(x 1 , y 1 x 2 y 2 ) ⇒ I(x 1 , x 2 ), I(y 1 , y 2 ) I(ε, x 1 y 1 x 2 y 2 ) ⇒ I(x 1 , x 2 ), I(y 1 , y 2 ) I(αx 1 ᾱ, x 2 ) ⇒ I(x 1 , x 2 ) α ∈ Σ 2 I(αx 1 , ᾱx 2 ) ⇒ I(x 1 , x 2 ) α ∈ Σ 2
Our main theorem is that the language of G n is O n . The inclusion of L(G n ) into O n is obvious and the challenge consists in proving the converse inclusion. We prove actually a stronger statement:

Gn I(s 1 , . . . , s n ) is derivable for every s 1 • • • s n in O n .
With this statement, the desired inclusion is immediate: for w ∈ O n , set s 1 = w and s j = ε for all j 2 and apply rule (1).

A tuple (s 1 , . . . , s n ) is reducible if there are at least two compatible letters among the endpoints of the s j 's; otherwise the tuple is irreducible. Repeated applications of rules of the form (3) allow to derive reducible tuples from irreducible ones. Irreducible tuples are dealt with the following "decomposition lemma," which shows how a rule of the form (2) is applied to derive an irreducible tuple from smaller elements in O n . While rule (4) provides the base case for the induction, this lemma is the main technical result towards the proof of Theorem 1. It relies on Theorem 2, a result stated and proved in Section 4, and formulated with the terminology of the necklace splitting theorem.

Lemma 1 (Decomposition lemma). Consider an irreducible tuple

(s 1 , . . . , s n ) in (Σ + n ) n , where each s j is of length at least 2. If s 1 • • • s n belongs to O n , then there exist two tuples (u 1 , u 3 , . . . , u 2n-1 ) and (u 2 , u 4 , . . . , u 2n ) in (Σ * n ) n and integers 0 = k 0 k 1 • • • k n = 2n such that (I) u 1 u 3 • • • u 2n-1 and u 2 u 4 • • • u 2n are both nonempty elements of O n , and (II) s j = u k j-1 +1 u k j-1 +2 • • • u k j for each j ∈ [n]. In particular, s 1 • • • s n = u 1 u 2 • • • u 2n .
Proof. We distinguish the cases n = 1 and n 2.

We deal first with the case n = 1. In that case, Σ n = {a 1 , ā1 }. As s 1 is irreducible, without loss of generality, we may assume that s 1 = a 1 wa 1 . We consider prefixes u of w of increasing length, from |u | = 0 to |u | = |w|. Since s 1 belongs to O 1 , the quantity |a 1 u | a 1 -|a 1 u | ā1 starts with the value 1 and finishes with the value -1, and changes by steps of one unit. There is therefore a prefix u of w such that a 1 u belongs to O 1 . Setting u 1 = a 1 u and u 2 ∈ Σ + 1 such that s 1 = u 1 u 2 makes the job. We deal now with the case n 2. The proof of Theorem 2 builds explicitly u 's satisfying the desired properties: property (I) is a consequence of the fact that each of A and B are balanced; property (II) is a consequence of the fact that the endpoints of the s j 's form cuts.

From this the inclusion follows easily.

Proposition 1. The judgment Gn I(s 1 , . . . , s n ) is derivable for every s 1 • • • s n in O n . In particular, we have O n ⊆ L(G n ).
Proof. As mentioned above, the second part of the statement is a direct consequence of the first part. We proceed by induction on the pairs (|s 1 • • • s n |, e) ordered lexicographically, where e is the number of s j equal to ε.

Suppose first that (s 1 , . . . , s n ) is reducible. A rule of the form (3) shows that we can derive the judgment from another judgment Gn I(s 1 , . . . , s n ), with

|s 1 • • • s n | < |s 1 • • • s n |.
The induction hypothesis provides the conclusion.

Suppose now that (s 1 , . . . , s n ) is irreducible. Four cases are in order, distinguished according to the possible lengths of the s j 's.

The first case is when at least one s j is of length 1. Without loss of generality we may assume that s j = a 1 . As

s 1 • • • s n is in O n , there is a k such that s k = v 1 ā1 v 2 for some v 1 and v 2 in Σ * n .
The other case being similar, we suppose that j < k. Define t j = a 1 , t k = ā1 , and t = ε for = j, k; define also (u 1 , . . . , u n ) = (s 1 , . . . , s j-1 , s j+1 , . . . , s k-1 , v 1 , v 2 , s k+1 , . . . , s n ). Using rule (4) and a rule of the form (3), we get that Gn I(t 1 , . . . , t n ) is derivable. The judgment Gn I(u 1 , . . . , u n ) is derivable by induction. Then using a rule of the form (2) shows that Gn I(s 1 , . . . , s n ) is derivable. More precisely, we instantiate each variable x with t and each variable y with u in the following rule

I(x 1 y 1 , . . . , x j-1 y j-1 , x j , y j , . . . , x k-2 y k-2 x k-1 , y k-1 x k y k , . . . , x n y n ) ⇒ I(x 1 , . . . , x n ), I(y 1 , . . . , y n ) .
The second case is when all s j are equal to ε. The conclusion follows from an application of rule (4).

The third case is when some s j but not all are equal to ε and no s j is of length 1. There is then an j ∈ [n -1] such that either s j = ε and |s j+1 | > 1, or |s j | > 1 and s j+1 = ε. By symmetry, we suppose that s j = ε and

|s j+1 | > 1. As |s j+1 | > 1, we have that s j+1 = v 1 v 2 with v 1 and v 2 in Σ + . Define (s 1 , . . . , s n ) = (s 1 , . . . , s j-1 , v 1 , v 2 , s j+2 , . . . , s n ).
The judgment Gn I(s 1 , . . . , s n ) is derivable by induction (we have a smaller e). The judgment Gn I(ε, . . . , ε) is derivable from an application of rule (4). Then using a rule of the form (2) shows that Gn I(s 1 , . . . , s n ) is derivable. More precisely, we instantiate each variable x with s and each variable y with ε in the following rule: I(x 1 y 1 , . . . , x j-1 y j-1 , ε, x i y j x j+1 y j+1 , . . . , x n y n ) ⇒ I(x 1 , . . . , x n ), I(y 1 , . . . , y n ) .

The fourth case satisfies the conditions of Lemma 1 ("decomposition lemma"), which shows that Gn I(s 1 , . . . , s n ) is derivable by an application of a rule of the form (2) and by induction.

From this we can derive our main theorem.

Theorem 1. The language O n is an n-MCFL.

Remark.

Theorem 2 actually implies a version of Lemma 1 that also holds for reducible tuples albeit only if n is at least 2 and if we permit to decompose (s 1 , . . . , s n ) in more versatile tuples. This corresponds to a slightly more liberal definition of the rules (2). More precisely, we may add to the rules (2) for each j ∈ [n] the rule:

( * ) I(x 1 y 1 , . . . , x j-1 y j-1 , y j x j , x j+1 y j+1 , . . . , x n y n ) ⇒ I(x 1 , . . . , x n ), I(y 1 , . . . , y n ) .

We have chosen to exclude rules ( * ) to emphasize the surprising simplicity of the rules (2) which allow to decompose every irreducible tuple. Moreover, we want to contrast the grammar we obtain with the one that Nederhof [START_REF] Nederhof | Free word order and MCFLs[END_REF] conjectures to capture O n . Nederhof proposes binary rules of the following form:

A(w 1 , . . . , w n ) ⇒ A(x 1 , . . . , x n ), A(y 1 , . . . , y n ) where w 1 • • • w n is obtained by shuffling the words x 1 • • • x n and y 1 • • • y n , i.e., |w 1 • • • w n | = 2n, removing all occurrences of y j 's from w 1 • • • w n yields x 1 • • • x n and, analogously, removing all occurrences of x j 's from w 1 • • • w n yields y 1 • • • y n .
Furthermore, a w k may not contain an occurrence of x j x j+1 or of y j y j+1 for some j ∈ [n -1]. The rules (2) may be obtained from Nederhof's by forbidding the occurrence of x j x j+1 and of y j y j+1 not only in the w k 's but rather in the combined word w 1 • • • w n . Note however that this additional restriction implies that rules (3) need to allow the removal of compatible letters at arbitrary endpoints of the words of a tuple. The corresponding rules of Nederhof's grammar are less liberal. Were we to remove rules (3) and treat the elimination of compatible letters as in [START_REF] Nederhof | Free word order and MCFLs[END_REF], then we would need to add the rules ( * ). Clearly, these rules form a strict subset of those proposed by Nederhof as w k 's are of length 2 and at most one occurrence of x j x j+1 is allowed in w 1 • • • w n . In this sense, our grammar is simpler than Nederhof's. Notably, also Nederhof [Ned17, Sec. 5.3] conjectures for O 3 that some of the rules of his grammar are redundant.

Necklace splitting and proof of the decomposition lemma

In this section, we prove a combinatorial theorem in the tradition of the necklace splitting problem. The theorem almost implies Lemma 1, but while it does not require irreducibility, it misses the property (II). Its proof however gives the construction for the case n > 1 of Lemma 1.

This combinatorial theorem is formulated without the terminology of languages and grammars so as to make it understandable easily without background in this area. For readers who are more familiar to manipulating words, the vocabulary of the necklace problem translates easily to that of words: necklaces become words and beads become letters.

In the traditional version of the necklace splitting theorem, there is an open necklace with beads of n different types, and an even number of beads of each type. The necklace splitting theorem ensures that such a necklace can always be split between two thieves with no more than n cuts so that each thief gets the same amount of each type. The cuts have to leave the beads untouched. Here, we keep the same setting, except that a bead can be either "positive" or "negative." The amount of a type in a necklace or in a collection of necklaces is the number of positive beads of this type minus the number of negative beads of this type. A necklace or a collection of necklaces is balanced if the amount of each type is zero.

Theorem 2. Consider a collection of n open necklaces with positive and negative beads. Suppose that there are n 2 types of beads and that each of the necklaces has at least two beads. If the collection is balanced, then there is a way to cut the necklaces using at most n cuts in total and partition the subnecklaces into two parts so that each part is balanced, gets at least one bead (and thus at least two), and is formed by at most n subnecklaces.

The connection to Lemma 1 is as follows:

• The n types of beads are the numbers 1, . . . , n, the letter a i representing a positive bead of type i and the letter āi representing a negative bead of type i.

• The n open necklaces correspond to the words s 1 , . . . , s n .

• The two parts of the at most n subnecklaces are the tuples (u 1 , . . . , u 2n-1 ) and (u 2 , . . . , u 2n ) in the lemma, which, as in the theorem, are required to be balanced and to contain at least one letter each. The proof of Theorem 2 relies on the following proposition, which is actually the traditional necklace splitting theorem extended to negative beads (the relaxation of the parity condition of the number of beads is standard; see, e.g., [AMS06, Section 5.1]).

Proposition 2. Consider a necklace with positive and negative beads. Suppose that there are n 1 types of beads. Then the necklace can be split between two thieves with no more than n cuts so that the amount of beads received by the thieves differ by at most one unit for each type. It is moreover possible to choose which thief receives an extra bead for each type which requires so.

The types requiring that one of the thieves receives an extra bead are precisely those whose total amount of beads is an odd number.

Proof of Proposition 2. We proceed in two steps. In a first step, we prove a continuous version, in which we are allowed momentarily to locate cuts on beads themselves. In a second step, we show how to move the cuts so as to get a splitting with cuts leaving the beads untouched. 1We identify the necklace with [0, 1] and the beads with intervals included in [0, 1], all of same length (this length is the inverse of the total number of beads in the necklace), and with disjoint interiors. Assume that these small intervals are all open. (This assumption is made to ease the proof, but actually whether these small intervals contain or not their boundaries does not matter.) Define

g i (x) -→    +1 if
x is in a interval corresponding to a positive bead of type i.

-1 if x is in a interval corresponding to a negative bead of type i. 0 otherwise.

According to the Hobby-Rice theorem [START_REF] Hobby | A moment problem in l 1 approximation[END_REF], there are points 0 =

x 0 < x 1 < • • • < x r < x r+1 = 1 with r n such that for all i ∈ [n] r+1 j=1 (-1) j x j x j-1 g i (u) d u = 0 .
(Here, we take the formulation given by Pinkus [START_REF] Pinkus | A simple proof of the Hobby-Rice theorem[END_REF].) The r points x 1 , . . . , x r can be interpreted as cuts. The intervals (x j-1 , x j ) with j odd are given to one thief, and the intervals (x j-1 , x j ) with j even are given to the other thief. Each thief gets the same amount of each type. The only problem is that some cuts may be located on beads. The second step of the proof consists in explaining how to move these cuts so that none of them touch the beads anymore, without creating a difference of more than one unit between the amounts received by the thieves for each type. We can make that each bead is cut at most twice since moving two cuts inside a bead in the same direction and by the same distance does not change the amounts received by the thieves. If a bead is cut twice, we can similarly move the two cuts until one of them is located between two beads. (Doing this, we can have several cuts located at the same position between two beads, but this is not an issue.) So, we can assume that each bead is cut at most once and that the two parts of a cut bead go to distinct thieves. If a type has two beads or more touched by a cut, then we can move two cuts so that one at least reaches a position between two beads, without changing the amounts received by each thief. Thus, we can assume that each type is cut at most once. We finish the proof by noting that if a type has a bead that is cut, it means that each thief received a non-integral amount of the corresponding type, i.e., a half-integer, and moving the cut arbitrarily leads to the desired splitting.

Proof of Theorem 2. Denote by s 1 , . . . , s n the n necklaces. We assume that there are no two beads located at the endpoints of some necklaces and that are of the same type but of opposite signs, for otherwise there would be an easy solution: cut these two beads from the necklaces, form a balanced part with them, and leave the rest of the remaining beads for the second balanced part. The number of cuts would then be 2 n (or, if these two beads formed a necklace of their own, the solution would need no cut), and the number of subnecklaces in the parts would be 2 and n (or 1 and n -1). Making this assumption corresponds to considering only the irreducible case in the terminology of Theorem 1.

A natural idea would be to apply a result like Proposition 2 to the "big" necklace s = s 1 • • • s n obtained by appending the necklaces in their index order. The first issue with this idea is that one thief might get nothing. This can easily be dealt with as done below. The second issue is that, even though there are 2n subnecklaces in total, one thief might get more than n subnecklaces.2 Instead we consider another big necklace, which we will denote by s and which we define now.

We start by defining s 1 to be s 1 from which the left-most bead has been removed, and s n to be s n from which the right-most bead has been removed. Note that without loss of generality, we can assume that the left-most bead of s 1 is a positive bead of type 1 and that the right-most bead of s n is a positive bead of type 1 or n. We thus consider two cases:

(i) The left-most bead of s 1 and the right-most bead of s n are both positive beads of type 1.

where δ (i) ∈ {0, 1} and takes the value 1 only if we are in Case (i), and where δ i=n (ii) ∈ {0, 1} and takes the value 1 only if we are in Case (ii) and i = n.

For the beads of type 1, we have

q A 1 -q B 1 = 1 -δ (i) + n+1 k=1 j odd (-1) k+1 µ 1 (s j ∩ t k ) + n+1 k=1 j even (-1) k+1 µ 1 (s j ∩ t k ) = 1 -δ (i) + n+1 k=1 (-1) k+1 µ 1 (t k ) = 0 ,
where the last equality is a consequence of Equation (2) in Case (i) and of Equation (3) in Case (ii). For the beads of type i = 1, we have

q A i -q B i = -δ i=n (ii) + n+1 k=1 j odd (-1) k+1 µ i (s j ∩ t k ) + n+1 k=1 j even (-1) k+1 µ i (s j ∩ t k ) = -δ i=n (ii) + n+1 k=1 (-1) k+1 µ i (t k ) = 0 ,
where the last equality is a consequence of Equation (2), except when i = n and we are in Case (ii), where we use of Equation (4) instead.

Alternate combinatorial proofs of Proposition 2 and Lemma 1

All statements deal with discrete objects and properties. It is thus desirable from a logical point of view that all proofs stay in the "discrete world" if possible. Similarly to the traditional proof of the necklace splitting theorem, the proof of Proposition 2 we gave in Section 4 is relying on some "continuous" notions. Pálvőlgyi [START_REF] Pálvölgyi | Combinatorial necklace splitting[END_REF] showed how such proofs are amenable to the discrete world by using a combinatorial counterpart of the Borsuk-Ulam theorem.

We adapt here the approach proposed by Pálvőlgyi to provide a purely combinatorial proof of Proposition 2, also relying on Tucker's lemma. Moreover, we show how the more general Ky Fan lemma can actually provide a direct combinatorial proof of Lemma 1 itself. 5.1. Combinatorial tools. We start by introducing some notation. Let B = {-1, 1}. For brevity, we may write + instead of +1 and -instead of -1. Let O = {-1, 0, 1}. We define the partial order ≺ on O where 0 ≺ 1 and 0

≺ -1, or, equivalently, b b if b = 0 or b = b .
For every m ∈ N, we lift ≺ to O m where for x, y ∈ O m we have x y if for all i ∈ [m], x(i) y (i). Given a string x, we denote by x(i) the i-th letter of x. We also denote by -x the string obtained from x by replacing 1's by -1's and -1's by 1's (and the 0's are left unchanged). Now the Ky Fan lemma can be stated as follows:

Lemma 2 (Octahedral Ky Fan lemma, [Che11, Lemma 2]). Let λ : O m \ 0 m → {±1, . . . , ±q} such that (i) λ(-x) = -λ(x) for every x.

(ii) λ(x) + λ(y) = 0 for every x y.

Then there is at least one positively alternating m-chain, i.e., there are x 1 , . . . , x m ∈ O m \ 0 m and j 1 , . . . , j m ∈ [q] such that x 1 • • • x m , 1 j 1 < j 2 < • • • < j m , and λ({x 1 , . . . , x m }) = {j 1 , -j 2 , j 3 , . . . , (-1) m-1 j m }. In particular, q m.

(The statement we provide here is actually a special case of the original Ky Fan lemma [START_REF] Ky | A generalization of Tucker's combinatorial lemma with topological applications[END_REF] when the simplicial complex is the first barycentric subdivision of the octahedron.) The octahedral Tucker lemma [START_REF] Tucker | Some topological properties of disk and sphere[END_REF] is actually the same statement without the existence of the chain, but still with the inequality q m.

We explain now how strings in O m relate to decompositions of strings in Σ m n . We consider here all decompositions of a string w ∈ Σ m n into two tuples (u 1 , u 3 , . . . ), (u 2 , u 4 , . . . ) of strings in Σ + n such that w = u 1 u 2 • • • . Such a decomposition is described as a string x ∈ B m where each maximal segment of consecutive -1's, as well as each maximal segment of consecutive +1's, corresponds to one u j . Each sign change in x corresponds thus to a cut in w and to a transition from a u j to u j+1 . A string x ∈ O m , containing some 0's, can be interpreted as an underspecified decomposition, which can be completed into different decompositions by replacing the 0's with -1's or +1's.

Combinatorial proof of Proposition 2.

We prove Proposition 2 in a way that is similar to [START_REF] Pálvölgyi | Combinatorial necklace splitting[END_REF].

For x in B * we let alt(x) be the number of sign alternations in x. We extend the function alt to O * \ 0 * as follows: alt(x) = max{alt(y) | y ∈ B * , x y}. Notice that:

• alt(-x) = alt(x) for every x.

• alt(x) alt(y) for every x y. For x in O * \ 0 * , we define sign(x) ∈ {-1, 1} as the first letter of some y in B * so that x y and alt(x) = alt(y). The function sign(x) is well defined as when x is of the form 0 k κx , with κ ∈ B, the only way to replace the first k zeroes so as to maximize alt consists in changing the sign at each position.

From now on we fix the necklace w and assume it is of length m (i.e., w is in Σ m n ). We let E κ,i (x) for x in O m \ 0 m and κ ∈ {-1, 1} be the amount of beads of type i in w that are aligned with the symbol κ in x. We say that x is κi-unbalanced if E κ,i (y) > E -κ,i (y) for every y such that x y. We define unb(x) to be κi where i is the smallest i so that x is κi-unbalanced. When no such i exists, we let unb(x) = 0. We have

• unb(-x) = -unb(x) for every x. Because of the properties of alt, sign and unb, had it no zero, the function λ would satisfy the properties (i) and (ii) of the octahedral Tucker lemma. However, then the conclusion is not satisfied, thus λ must have a zero. Take x so that λ(x) = 0. We must have that alt(x) n.

As unb(x) = 0, it is possible, for each type i, to replace 0's in x with 1's or -1's so that we eventually obtain y verifying E 1,i (y) = E -1,i (y) for every i, and such that the remaining 0's in y are aligned with at most one unassigned bead of type i. We can then choose to replace these 0's with either 1 or -1 depending on how we wish to treat the extra bead of a given type. As alt(x) is smaller than n, then no matter how we have conducted the previous changes, we have obtained a way to split the necklace with at most n cuts so that each part contains the same amount of each type, with the extra beads (when the amount is odd) being distributed in any possible way.

Remark. The definition of unb is where the proof departs from the one of [START_REF] Pálvölgyi | Combinatorial necklace splitting[END_REF]. Indeed Pálvőlgyi's proof only considers positive beads and it is then enough to consider that x is unbalanced when one of the thief receives more than half of the beads of some type. In that case the split remains unbalanced for every y so that x y. This property is no longer true with negative beads. Our definition of unb is taking this into account by imposing that being unbalanced is closed under .

Combinatorial proof of

x = κ 1 1 κ 2 2 • • • κ k k with κ 1 , .
. . , κ k ∈ B, κ p = -κ p+1 and p ∈ N be such that for each j ∈ [n], there is q j ∈ {0, . . . , k} with p∈[j] |s p | = p∈[q j ] p , and k is minimal. Now, if k = 2n, then x describes a decomposition of (s 1 , . . . , s n ) in two tuples each of size n. Precisely, these tuples are (u 1 , u 3 , . . . , u 2n-1 ) and (u 2 , u 4 , . . . , u 2n ) where the length of u j is j for each j ∈ [2n] and s j = u q i-1 +1 u q i-1 +2 • • • u q j for each j ∈ [n]. If k < 2n, we may add κ q 's with q = 0 to increase k to 2n and proceed similarly. We call the value k -1 the number of sign alternations of x and write alt(x) = k -1. Hence, in the following we will search for x with alt(x) 2n -1. Crucially, we assume mandatory sign alternations between the neighboring endpoints of s j and s j+1 : if the last position of s j and the first position of s j+1 are signed equally in x, then some κ p with p = 0 occurs in our factorization of x. In this case 2 sign alternations are accounted for the transition between neighboring endpoints. In order to maximize alt, we may choose x to be strictly a 1 a 2 ā2 a 3 ā2 ā3 a 1 ā1 ā1 ā2 k by first setting each unsigned position of C(p + 1) to b , then p tob , and then the remaining position of C(p -1) to b , if it exists. Thus, h(x b k ) = h(x b k-1 ), contradicting (c). There are n -1 pairs of neighboring endpoints, i.e., in total 2n -2 internal endpoints.

x + m-n and x - m-n each have n unsigned positions, of which, by Property 1, at least n -1 are internal endpoints. Property 2 implies that the only unsigned position that is not an internal endpoint, if one exists, is 1 or m. Thus, U consists solely of endpoints of the s j 's. However, all symbols of Σ n are distributed at the positions in U . Hence, (s 1 , . . . , s n ) is such that every pair of compatible letters of Σ n can be reduced. This concludes the proof of Proposition 3.

  • |unb(x)| |unb(y)| > 0 for every x y if unb(x) = 0. Notice that |unb(x)| = |unb(y)| implies unb(x) = unb(y) for every x y. Finally we define λ as the function from O m to {-m + 1, . . . , 0, . . . , m -1}: λ(x) = ß sign(x) alt(x) when alt(x) > n . unb(x) when alt(x) n .

Figure 1 .

 1 Figure1. A word s 1 s 2 s 3 , a decomposition x with the corresponding alignment of s j 's to u p 's (in particular, u 3 = ε), and the calculation of alt(x).

  Lemma 1. Lastly, we present a direct combinatorial proof of Lemma 1 that avoids Theorem 2. The method is again inspired by Pálvőlgyi[START_REF] Pálvölgyi | Combinatorial necklace splitting[END_REF], but instead of constructing a function λ that contradicts the Tucker lemma, if it has no zero, we construct a pair of functions λ + and λ -, for which the chains guaranteed by the Ky Fan lemma cannot exist for irreducible tuples.In contrast to Section 5.2, we do not consider x ∈ B m to represent the decomposition of a single string but instead x shall represent the decomposition of an irreducible tuple (s 1 , . . . , s n ) in (Σ + n ) n where the word s 1 • • • s n is in O n and each s j is of length at least 2. To account for the arity of the tuple, we need to generalize the notion of alt. Denote the word s 1 • • • s n by s and the length of s by m. Factorize x such that

Technische Universität Dresden, Germany, kilian@gebhardt.xyz.

CERMICS, École des Ponts ParisTech, France, frederic.meunier@enpc.fr.

Université de Lille, INRIA, CRIStAL, France, sylvain.salvati@univ-lille.fr. 1

An alternative purely combinatorial proof is presented in Section 5.2.

In essence, this is the reason why Ho[START_REF] Ho | The word problem of Z n is a multiple context-free language[END_REF] could only show that O n is an 8 n+1 2 -2 -MCFL.

(ii) The left-most bead of s 1 is a positive bead of type 1 and the right-most bead of s n is a positive bead of type n. The condition of the theorem ensures that neither s 1 nor s n are empty. Consider the "big" necklace s = s 1 s2 s 3 s4 • • • . If n is even, the big necklace s ends with s n , and if n is odd, it ends with s n . (Given a sequence t of beads, the notation t means t where all positive beads become negative and conversely, without changing their types.) According to Proposition 2, there is a splitting of s into n + 1 subnecklaces t 1 , . . . , t n+1 (completing with zero-length subnecklaces if necessary) such that we have for i ∈ [n] in Case (i) and for i ∈ {2, . . . , n -1} in Case (ii)

and such that in Case (ii)

Here, we denote by µ i (t) the amount of beads of type i in the subnecklace t. We remind the reader that the amount of beads is the number of positive beads minus the number of negative beads of this type.

We interpret now the endpoints of the subnecklaces t k as cuts of the "big" necklace s (the one formed by the original necklaces s j ). Together with the endpoints of the s j , we get a splitting of s into 2n subnecklaces u 1 , . . . , u 2n (in this order). Some u can be zero-length subnecklaces. We make two parts: a part A formed by the u with an odd , and a part B formed by the u with an even . Remark two things:

• Since the left-most bead of s 1 belongs to u 1 and the right-most bead of s n belongs to u 2n , each part contains at least one bead. • The number of subnecklaces u is the same in each part, and thus equal to n. We finish the proof by checking that both A and B are balanced. We denote by q A i and q B i the amount of beads of type i in A and B, respectively. Since the original collection is balanced, we have q A i + q B i = 0. The end of the proof consists simply in checking that we have also q A i -q B i = 0, which implies then immediately that q A i = q B i = 0, as desired. Each bead x belongs to exactly one s j . Moreover, apart from the two beads at the endpoints of s, any bead x (resp. x) belongs also to exactly one t k when j is odd (resp. even). It is immediate to check that j + k -1 and the index of the u to which x belongs have the same parity. Thus if j + k -1 is odd, then x belongs to A, and if it is even, then x belongs to B. We have

and for i = 1, we have

alternating except for the n -1 transitions between neighboring endpoints. In consequence alt(x) m -(n -1) + 2(n -1) -1 = m + n -2. Figure 1 gives an example: Note that alt(x) < 2 • 3 and that the subwords in +labeled and --labeled positions are both in O 3 . Thus, x describes the decomposition of (a 1 a 2 ā2 a 3 , ā2 ā3 a 1 , ā1 ā1 ā2 ) to two strictly smaller 3-tuples (a 1 , ε, ā1 ) and (a 2 ā2 a 3 , ā2 ā3 a 1 , ā1 ā2 ), for each of which the word obtained by concatenating the tuple's components is in O 3 .

Again, we consider words in O m \ 0 m which may have unsigned positions, i.e., positions labeled with 0. In this case the decomposition is only partially determined. We define the function h :

Denote by H(x) the set arg max y∈B m : x y alt(y). All elements of H(x) may be obtained with the following algorithm:

(i) Choose a signed position p in x with an unsigned neighbor p ∈ {p -1, p + 1}.

(ii) If p and p are neighboring endpoints (in this case we call p and p internal endpoints), set x (p ) = x(p); otherwise set x (p ) = -x(p). For each q = p , set x (q) = x(q). (iii) If x ∈ B m we are done, otherwise, recursively apply the algorithm to x . This algorithm may yield words y, y where y(p) = y (p) if p is an unsigned position between two signed positions of x. However, for all position p smaller than the smallest signed position of x, the signs y(p ) and y (p ) are equal for all words y, y in H(x). Hence, we may define a function sign : O m \ 0 m → B to assign to x the first symbol of some y ∈ H(x). Moreover, for each x ∈ O m \ 0 m : sign(x) = -sign(-x).

To prove Lemma 1, we need to show that there is x ∈ B m with alt(x) < 2n and that both words u 1 u 3 • • • and u 2 u 4 • • • described by x are in O n and non-empty. To assure non-emptiness, we just need that both signs occur in x. To ensure that the words are in O n , we rephrase the notions E κ,i and unb from Section 5.2 in terms of tuples of words instead of necklaces. Now E κ,i (x) is formulated as the difference of the amount of a i 's and āi 's aligned with κ in x. Formally:

Observe that E +,i (x) + E -,i (x) = 0 for s ∈ O n and x ∈ B m . We define two functions λ + and λ -, where for each b ∈ B,

If there are x ∈ O m \ 0 m and b ∈ B such that λ b (x) = 0, then Lemma 1 holds: Note that case C3 of λ b applies. Thus, for each i ∈ [n] there is y ∈ B m such that E +,i (y) = E -,i (y) = 0. The positions relevant to balance a i and a j where i = j are distinct. Hence, we choose ŷ ∈ B m with x ŷ such that all symbols are balanced. Since ŷ x we have that alt(ŷ) h(x) < 2n, |ŷ| + > 0, and |ŷ| -> 0. Thus, ŷ encodes a decomposition with the desired properties. Otherwise, if λ + and λ -have no zero, we want to apply the Ky Fan lemma. Clearly, λ b satisfies property (i) of the octahedral Ky Fan lemma if cases C1 and C3 apply. For case C2, note that |x| Proposition 3. If λ + and λ -have no zero, then every pair of compatible symbols a i , āi ∈ Σ n can be reduced from (s 1 , . . . , s n ).

Lemma 1 follows directly, as whenever (s 1 , . . . , s n ) is irreducible, λ + and λ -have a zero.

To show Proposition 3 assume that for either b ∈ B there is no x ∈ O m \ 0 m such that λ b (x) = 0. By Lemma 2, for each b ∈ B, there is a positively alternating m-chain, i.e., there are


Andrey Moreno-Mendez

Sarita Campos-León

Philippe Béarez
email: bearez@mnhn.fr

First record of a stranded specimen of Masturus lanceolatus (Molidae) from the central coast of Peru

Keywords: Peru, new record, sunfish, morphology, marine biodiversity

Molids are a widely distributed family, but they are rarely encountered and their distribution and abundance have poorly been documented. Masturus lanceolatus (Liénard, 1840) has recently been recorded in Peru, as a by-catch in longline and purse seine fisheries. We mention here the stranding of a large individual of this rarely encountered species on the northcentral coast of Peru, probably resulting from fishing discards.

INTRODUCTION

Molas, also known as ocean sunfishes are widely distributed in tropical and temperate seas. They are large-sized bony fishes, attaining over 2 m in length and ≈ 2,000 kg in mass (Froese and Pauly 2018), characterized by a highly compressed body, absence of a caudal fin and presence of large dorsal and anal fins [START_REF] Johnson | Leis' conundrum: Homology of the clavus of the ocean sunfishes. 2. Ontogeny of the median fins and axial skeleton of Ranzania laevis (Teleostei, Tetraodontiformes, Molidae)[END_REF]. The caudal fin is replaced by a broad rudder-like lobe called the clavus.

Despite their strange appearance and unique shape, which stimulated scientific interest since the XVIth century [START_REF] Rondelet | Libri de piscibus marinis[END_REF], little attention has been paid to ocean sunfishes and their abundance among fisheries. Recently, growing interest on their taxonomy led to the resurrection of a species of Mola [START_REF] Sawai | Redescription of the bump-head sunfish Mola alexandrini (Ranzani 1839), senior synonym of Mola ramsayi (Giglioli 1883), with designation of a neotype for Mola mola (Linnaeus 1758) (Tetraodontiformes: Molidae)[END_REF] and the description of a new species of Mola [START_REF] Nyegaard | Hiding in broad daylight: molecular and morphological data reveal a new ocean sunfish species (Tetraodontiformes: Molidae) that has eluded recognition[END_REF]. In parallel, reports of the extent of ocean sunfish by-catch have been given by [START_REF] Nyegaard | Hiding in broad daylight: molecular and morphological data reveal a new ocean sunfish species (Tetraodontiformes: Molidae) that has eluded recognition[END_REF].

Currently, Molidae includes five extant species in three genera [START_REF] Nyegaard | Hiding in broad daylight: molecular and morphological data reveal a new ocean sunfish species (Tetraodontiformes: Molidae) that has eluded recognition[END_REF]):

Masturus Gill, 1884 (1 species); Mola Koelreuter, 1766 (3); and Ranzania Nardo, 1840 (1). For long, only two of them, Mola mola (Linnaeus, 1758) and Ranzania laevis (Pennant, 1776) had been recorded from Peru [START_REF] Chirichigno | Catálogo comentado de los peces marinos del Perú[END_REF], but the third species Masturus lanceolatus (Liénard, 1840) has been recently added to the Peruvian ichthyofauna [START_REF] Mangel | The effect of Peruvian small-scale fisheries on sunfishes (Molidae)[END_REF]. This species was considered almost absent from the eastern Pacific, the only records being from Mexico [START_REF] Balart | The first eastern Pacific report of the sharptail mola, Mola lanceolata (Tetraodontiformes: Molidae)[END_REF], Galápagos Islands (McCosker and Rosenblatt 2010), and northern Chile [START_REF] Pequeño | Peces de Chile. Lista sistemática revisada y comentada: addendum[END_REF]). Here we present the record of a stranded specimen of this rarely encountered species on the north-central coast of Peru.

MATERIAL AND METHODS

On December 5th 2018, fishermen from Puerto Morín informed one of us (AMM) that a strange fish had been washed up on the shore close to "Cerro negro" (8°25´56.09´´ S -78°55´19.59´´ W) (Fig. 1).

The stranded individual was photographed and measured in the beach, but due to its large size, isolated position, and poor state of preservation, the specimen could not be transported and deposited into an ichthyological collection. Measurements of the individual were taken following [START_REF] Nyegaard | Hiding in broad daylight: molecular and morphological data reveal a new ocean sunfish species (Tetraodontiformes: Molidae) that has eluded recognition[END_REF].

RESULTS

The unique shape of the sharptail mola, Masturus lanceolatus, especially the long projection on its clavus, allowed recognizing quite easily the species. The images are given in Figure 2 and the main body measurements in Table 1.

DISCUSSION

Masturus lanceolatus is globally distributed in tropical to subtropical waters (Froese and Pauly 2019), and occur widely in the western Pacific Ocean [START_REF] Nyegaard | Giant jelly eaters on the line: Species distribution and bycatch of three dominant sunfishes in the Southwest Pacific[END_REF]). However, its presence in the northeastern Pacific has been ignored until recently [START_REF] Balart | The first eastern Pacific report of the sharptail mola, Mola lanceolata (Tetraodontiformes: Molidae)[END_REF], and only known from one specimen caught in the southeastern Pacific, off Iquique (Chile) on 9 March 1985 (W. Sielfeld, pers. comm.). It is quite surprising that this species has only been reported in Peru very recently.

Accidental entanglement in fishing gear is one of the main threats to molid populations, as species from the family are often reported as by-catch in long-line (e.g. [START_REF] Joung | Observed by-catch of Taiwanese tuna longline fishery in the South Atlantic Ocean[END_REF][START_REF] Nyegaard | Giant jelly eaters on the line: Species distribution and bycatch of three dominant sunfishes in the Southwest Pacific[END_REF]) and surface gillnet fisheries [START_REF] Mangel | The effect of Peruvian small-scale fisheries on sunfishes (Molidae)[END_REF]. In Peru, Mola mola and Masturus lanceolatus have been reported as by-catch in both fisheries, which essentially target dolfinfish (Coryphaena hippurus) and sharks [START_REF] Alfaro-Shigueto | Where small can have a large impact: Structure and characterization of small-scale fisheries in Peru[END_REF].

Recent data confirm that M. lanceolatus might be more common than previously assumed [START_REF] Nyegaard | Giant jelly eaters on the line: Species distribution and bycatch of three dominant sunfishes in the Southwest Pacific[END_REF]. [START_REF] Mangel | The effect of Peruvian small-scale fisheries on sunfishes (Molidae)[END_REF] found M. lanceolatus as the second most common ocean sunfish, next to Mola spp., in the surveys on Peruvian small-scale pelagic gillnet fishery.

They mention that most of the ocean sunfishes are discarded, alive or dead, so the specimen observed at Cerro Negro well could be a result of a discard of by-catches.

Stranding of M. lanceolatus has already been observed in Mexico by [START_REF] Balart | The first eastern Pacific report of the sharptail mola, Mola lanceolata (Tetraodontiformes: Molidae)[END_REF]

  on 25 May 1999, soon after the 1997-98 very strong El Niño. The specimen from Iquique was caught by an anchovy purse seiner on 9 March 1985, not very long after the 1982-83 very strong El Niño. The present specimen was found stranded on 5 December 2018, during the weak 2018-19El Niño. Hence, the abundance of M. lanceolatus in the eastern Pacific could be linked with anomalous oceanographic conditions as the ENSO events. Changes in distribution of fishes during ENSO events, including Mola mola, are well documented (e.g.[START_REF] Sielfeld | El Niño induced changes of the coastal fish fauna off northern Chile and implications for ichthyogeography[END_REF]. It is likely that ENSO has an impact on molas distribution in Peruvian waters.

Fig. 1 .

 1 Fig. 1. Location of the stranding of Masturus lanceolatus in "Cerro Negro", La Libertad, Peru.

Figure 2 .

 2 Figure 2. Masturus lanceolatus stranded on the beach at Cerro Negro, Peru. Before (A) and after (B) cleaning.

Table 1

 1 Morphometric data of the stranded individual of Masturus lanceolatus (see[START_REF] Nyegaard | Hiding in broad daylight: molecular and morphological data reveal a new ocean sunfish species (Tetraodontiformes: Molidae) that has eluded recognition[END_REF]).

	Measurement	cm	Abbreviation
	Total length	202	TL
	Head depth	46	HD
	Snout length	20	SnL
	Head length	24	HL
	Pre-anal fin length	114	PAFL
	Pre-pectoral fin depth	74	PPFD
	Body depth	86	BD
	Total body depth	207	TBD
	Pre-clavus band length	144	PCBL

ACKNOWLEDGEMENTS

Thanks are due to Mr. Carlos Calvo Mac, who notified us of the stranding, as well to Stevens Lucero Pérez, for collaborating in the elaboration of the map.


Dominique Rauly

Médéric Vindret

Eric Chamberod

Jean Martins

Pascal Xavier

Distribution of AC Electric Field-Induced Transmembrane Voltage in Escherichia coli Cell Wall Layers

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.


Alex J Mantanona

Daniel R Tolentino

Kristine S Cay

Milan Gembicky

Rodolphe Jazzar

Guy Bertrand

Jeffrey D Rinehart

Tuning electronic structure through halide modulation of mesoionic carbene cobalt complexes

The first examples of Co(II) mesoionic carbene complexes (CoX2 Dipp MIC2 ; X = Cl⁻, Br⁻, I⁻) demonstrate a new electronic perturbation on tetrahedral Co(II) complexes. Using absorption spectroscopy and magnetometry, the consequences of the MIC's strong σ-donating / minimal π-accepting nature are analyzed and shown to be further tunable by the nature of the coordinated halide.

Using ligand coordination to fine-tune the electronic structure of transition metals is a mature area of both organometallic and inorganic coordination chemistry. [START_REF] Crabtree | The organometallic chemistry of the transition metals[END_REF] The discovery of distinctly new properties and reactivity, therefore, is often contingent upon the use of ligands that induce non-standard perturbations upon the metal center. An iconic example was the introduction of N-heterocyclic carbene (NHC) ligands where strong σdonation and wide steric tunability led to an explosion of newly accessible organometallic reactivity. NHC-ligated complexes with nearly every transition metal have been isolated to target luminescent, magnetic, catalytic, and a wide range of other properties. [START_REF] Hopkinson | [END_REF] In addition to NHCs, the electronic versatility of carbenes has diversified to include systems such as the strong σ-and π-accepting cyclic alkyl-amino carbenes (CAACs) 3 and the more purely σ-donating mesoionic carbenes (MICs) (Figure 1). 4- 5 These variable electronic properties offer an intriguing and less explored contrast to the NHCs, especially for first-row transition metal complexes where only 36 such MIC complexes have been reported in the Cambridge Structural Database.

Amongst the transition metals, complexes of Co(II) provide some of the most diverse and interesting electronic structure behavior due to an inherent ground-state bistability from Kramer's degeneracy and relatively large spin-orbit coupling. 7 Tetrahedrally-coordinated high-spin Co(II) is particularly intriguing from an electronic structure standpoint. While its 4 A2 ground state has no first order orbital moment, it does have a wide variability in ligand-field strength, distortions in symmetry, and spin-orbit coupling that all contribute to a rich manifold of low-lying excited states. These provide a source of electronic structure tunability, opening up diverse applications from olefin oligomerization, 7 electrocatalytic C-C bond formation, 8 quantum sensing and computing, 9 as well as molecular spintronics, [START_REF] Sieklucka | Molecular magnetic materials: concepts and applications[END_REF] and single-molecule magnetism (SMM). [START_REF] Rechkemmer | [END_REF][12][13][14][15][16][17] Despite intense interest in both Co(II) and MICs, there are no examples of structurally-characterized complexes combining this metal-ligand pair. In fact, only two MIC complexes with any Co oxidation state have been previously characterized, both being Co(III). 18 Additionally, while there have been a small number of reported SMMs containing carbenes in the literature, [19][20][21][22][23][24][25][26][27] no comprehensive magnetic study on a series of simple metal halide carbenes of any type is available, nor have the magnetic properties of any MIC-containing compound been explored, leaving an invaluable characterization method for complex electronic structures untapped. To this end we synthesized and used a combination of optical absorbance spectroscopy and magnetometry to characterize a series of tetrahedral complexes comprising CoX2 Dipp MIC2 (X = Cl⁻, 1; Br⁻, 2; and I⁻, 3) (Figure 2). In addition to the new information garnered about the Co(II)-MIC interaction, we demonstrate the further control over the magnetic anisotropy through the halide ligand, with an approximate doubling of the axial zero field splitting (ZFS) anisotropy constant |D| between 1 and 3.

Department of Chemistry and Biochemistry, University of California -San Diego, La

Jolla, CA 92093, USA. E-mail: jrinehart@ucsd.edu Electronic Supplementary Information (ESI) available: CIF, synthetic details, and additional magnetic and crystallographic data. See DOI: 10.1039/x0xx00000x

Please do not adjust margins Please do not adjust margins Compounds 1-3 were obtained in good yield by treatment of a THF solution of the free MIC with the corresponding divalent cobalt halogen precursors (CoX2, X = Cl⁻, Br⁻, I⁻; Figure 2). The structures of 1-3 were confirmed by X-ray crystallography and elemental analysis. As expected, in the solid-state, all three complexes have similar coordination environments although they crystallized in distinct space groups (P𝟏 ̅ , P21/n, and Pccn respectively). Select bond angles and distances between the cobalt center and ligands are tabulated in Table S1. The Co coordination environment in all three complexes are distorted tetrahedra with approximate C2v symmetry. The phenyl substituents are arranged with parallel faces, which can be attributed to π-stacking interactions. Cobalt-carbene distances are comparable to bis-NHC bis-halide Co(II) complexes. [28][29] The angular distortion from ideal tetrahedral geometry was calculated using an angular distortion parameter:

𝜏 𝛿 = 360-(𝛼+ 𝛽) 141 𝛿 (Eq. 1) 𝛿 = 𝛽 𝛼 (Eq. 2)
where α and β define the largest and second largest L-Co-L angles. 30 All three structures are remarkably similar in terms of total distortion from ideal tetrahedral geometry, with τδ values of 0.89 being found for all three structures. Variable temperature magnetic susceptibility (T = 1.8-300 K) and variable field (H = -7-7 T) DC magnetometry data were collected and fit simultaneously using an effective spin Hamiltonian with axial zero field splitting (ZFS) and Zeeman contributions (Equation 3). Only the absolute value of the axial ZFS constant is reported due to ambiguity in determining the sign via magnetometry. The value of g is fit isotropically to minimize parameterization.

𝑯 ̂= 𝑫𝑺 ̂𝒛 𝟐 + 𝒈 𝒊𝒔𝒐 𝝁 𝑩 𝑺 • 𝑩

(Eq. 3)

Values of |D| = 6.54 ± 0.02, 8.53 ± 0.01, and 9.26 ± 0.09 cm -1 and g = 2.24, 2.26, and 2.36, were obtained for 1, 2 and 3 respectively. Samples 2 and 3 displayed obvious signs of temperature independent paramagnetism (TIP) consistent with a susceptibility contribution unaffected by the Boltzmann population. To account for this, empirical values of χTIP = 0.0001, 0.0007, and 0.0007 cm 3 mol -1 were employed for 1, 2 and 3, respectively, similar in magnitude to other four-coordinate Co complexes reported in the literature. 31 Although there are no direct comparisons for the ZFS values available in the literature for bis-carbene bis-halide Co(II) complexes, these values are within the range of reported values for bis-carbene two coordinate Co(I) complexes (D = -8.2, -0.11, and 33.4 cm -1 ), and two and three coordinate isoelectronic Fe(I) complexes (D = 19.8, -13.6 cm -1 ). 19,23 It is interesting that these axial D-values approach the magnitude of lower-coordinate systems, as typically lower-coordination of similar complexes leads to higher D-values due to smaller crystal fields.

Complexes 1, 2 and 3 display room temperature χMT values of 2.37, 2.63 and 2.79 cm 3 mol -1 K, respectively (Figure 3). The value of χMT down to ~25 K is largely independent of temperature, especially for 1 while 2 and 3 show large contributions from TIP. At lower temperatures, the drop accelerates to reach χMT ≈ 1.6 cm 3 mol -1 K for each compound. The room-temperature values are significantly larger than the spin-only value for a tetrahedrally coordinated d 7 metal with S = 3/2, suggesting a large second-order orbital contribution. This contribution is a manifestation of mixing excited states into ground states, with lower-field ligands (i.e. Cl⁻ > Br⁻ > I⁻) bringing excited states closer in energy to the ground state. The room-temperature magnetic susceptibilities of these compounds are larger than their bis-NHC, bis-halide Co counterparts, 32 while being slightly less than previously reported two-and three-coordinate Co(II) and isoelectronic Fe(I) carbene-based SMMs. 21,23 The tuning effect induced by the halide series was also apparent in spectroscopic data. Normalized to max intensity, UV/Vis/near-IR absorption data (Figure 4) show two distinct regions of excited energy states ranging from roughly 18,000-13,000 and 11,000-5,500 cm -1 , in close agreement with reported bis-NHC bis-halide Co(II) complexes. 28 These regions correspond to the transitions of the tetrahedral 4 A2 ( 4 F) ground state to the excited 4 T1 ( 4 F) and 4 T1 ( 4 P) states, with the 4 A2 ( 4 F) → 4 T2 ( 4 F) transition outside of our measurement window. 33 The spectra of the complexes show a clear red-shift with increasing Please do not adjust margins Please do not adjust margins these complexes paves the way for further studies on Co-MIC complexes to probe carbene effects on low-coordination environments. Now that a baseline for understanding changes in axial anisotropy in carbene-containing compounds has been set, future work will focus on making direct comparisons between MIC complexes and their NHC/CAAC counterparts. Expanding upon these trends will allow targeted development of systems that exploit the unique nature of the MIC ligand to control electronic and magnetic structure.

This research was funded through the National Science Foundation Division of Materials award #DMR-1904937. We also thank Prof. Arnold Rheingold, Dr. Curtis Moore and Dr. Milan Gembicky at UCSD Crystallography for their expert crystallographic assistance. halide size for both regions, which can be attributed to the lower ligand-field strength of the heavier halides. Both regions for all three complexes contain multiple features resulting from spin-orbit coupling and splitting of the parent tetrahedral geometry to C2v symmetry, which splits the 4 T1 states into their 4 A1, 4 B2, and 4 B1 components. 34 To quantify the ligand field, Tanabe-Sugano diagrams were used to calculate Dq values. 35 Using the median energy value from the two excitation ranges in the absorption data to approximate a non-distorted tetrahedral excitation, Dq and B were calculated as Dq = 394, 387, and 367 cm -1 and B = 635, 615, and 571 cm -1 for complexes 1-3, respectively. These values are slightly larger than their phosphine-halide analogs, indicative of stronger σ-donation of the MIC ligands. 36 The ligand field of the complex plays a critical role in the lowlying energy states caused by ZFS. The two components contributing to ZFS are the minor direct spin-spin interactions and the dominant second-order spin-orbit coupling (SOC) introduced by mixing of ground and excited states. 37 Computational 31,38 and experimental [39][40][41][42][43] works have shown how anisotropy can be influenced via heavy atom coordination with further corroboration for ligand influence on ZFS in tetrahedral Co halide complexes emerging over the past five years. 14, [40][41][42][43][44][45] Complexes 1-3 show a clear trend in their |D| values consistent with the expected electronic-structure effect. Specifically, we can attribute this trend to three effects: (1) Ligand-field strength correlates inversely with halide size, bringing the Co excited-states lower in energy for larger halides (Figure 4). This decreased ligand-field strength allows more mixing between Co states, which incorporates more SOC into the ground state. (2) Covalency in halides increases with halide size, yielding a larger contribution of ligand character to the molecular orbitals. (3) Relativistic effects in the larger halides allow for greater SOC, an effect that is enhanced due to the increased covalency and mixed states.

In summary, we present the first synthesis and electronicstructure analysis of Co(II)-MIC complexes. These compounds show clear correlations between halide size, excited-state energies, and ZFS. Analysis of magnetic and spectroscopic data revealed the ability of ligands to incorporate varying levels of second-order SOC into the metal center itself. The synthesis of

Figure 1 :

 1 Figure 1: Cobalt complexes bearing carbenes with different donor and acceptor properties. Shown here are complexes containing (left) CAACs, (middle) NHCs, and (right) MICs.

Figure 2 :

 2 Figure 2: (Top) Reaction scheme for compounds 1-3. (Bottom) Crystal structure of 1 with spheres representing C (gray), Co (dark blue), N (light blue), and Cl (green). Hydrogen atoms have been omitted for clarity

Figure 4 :

 4 Figure 4: Normalized absorbance data for compounds 1-3 in THF showing red shifts as halide size increases

J. Name., 2013, 00, 1-3 | 3

Conflicts of interest

There are no conflicts to declare.