Paul-Elliot Anglès D'auriac

Francis Maisonneuve
email: fran-cis.maisonneuve@gmail.com

Vivien Maisonneuve
email: v.maisonneuve@gmail.com

Emmanuel Preissmann
email: emmanuel.preissmann@gmail.com

Myriam Preissmann
email: myriam.preissmann@grenoble-inp.fr

On more variants of the Majority Problem

Keywords: Combinatorial search, Majority problem, Pairwise comparison

The variant of the Majority problem we are considering is the following. A colorblind player is given a set B of N colored balls. He knows that each ball is colored either red or green, and that there are less green than red balls, but he cannot distinguish the two colors. For any two balls he can ask whether they are colored the same. His goal is to determine the color of each of the balls, asking as few questions as possible. In the case where there are at most p (respectively exactly p) green balls, the minimum number of questions that guarantees the determination of the colors is denoted by Q(N, p, ≤) (respectively Q(N, p, =)). We extend results of Aigner on exact values of Q(N, p, ≤), and we provide upper bounds for Q(N,p,=), and even exact values for the first two values of p. Our results lead to several new questions.

Introduction

Let B = {b 1 , b 2 , . . . , b N } be a set of N balls, each ball being either red or green. The goal is to provide the color of each of the balls by asking questions of the type "Are b i and b j colored the same ? " (1 ≤ i < j ≤ N ). We remark that such comparisons may lead easily to a partition of B into two subsets B 1 and B 2 that are the sets of balls of each color. If we would allow B to contain an equal number of red and green balls it would be impossible to decide the colors of the balls. Hence we will always assume in the following that B contains more red balls than green balls and we call such a coloring a Red-green coloring. Furthermore we will also consider more restricted kinds of Red-green colorings : given an integer p, a Red-green coloring of N balls will be said p-majored if there are at most p green balls and it will be said pequal if there are exactly p green balls. The difficulty consists in determining a method minimizing the number of comparisons. Given two integers N and p < N 2 we call (N, p, ≤)-identification (respectively (N, p, =)-identification) the problem of determining for sure all the colors of N balls colored by a p-majored Red-green coloring (respectively by a p-equal Red-green coloring) and we denote by Q(N, p, ≤) (respectively Q(N, p, =)) the minimum number of comparisons that are necessary to solve any instance of the (N, p, ≤)identification problem (respectively of the (N, p, =)-identification problem).

In the next section we will present what is known and what are our new results on the values of Q(N, p, ≤) and Q(N, p, =). Then we will see some properties that are similar in both identification problems. In the two last sections we will provide the proofs of the results stated in section 2.

2 Known and new results

On the (N, p, ≤)-identification problem

The theorem below is due to Aigner (Theorem 4 and end of section 4 in [START_REF] Aigner | Variants of the Majority Problem[END_REF]). Theorem 1. [START_REF] Aigner | Variants of the Majority Problem[END_REF] Let N and p be integers such that 0 ≤ p < N 2 , we have:

Q(N, p, ≤) = N + 1 - N + 1 p + 1 or = N - N p + 1 .
and Q(N, p, ≤) = N + 1 -N +1 p+1 whenever N ≡ r [p + 1] with r = 0, 1 or p.

Theorem 1 has an obvious corollary.

Corollary 2. The following equalities hold :

• Q(N, 1, ≤) = N + 1 -N +1 2
for every N ≥ 3

• Q(N, 2, ≤) = N + 1 -N +1 3
for every N ≥ 5.

Our next theorem extends Theorem 1 and partially answers a question of Wildon (Problem 8.1 in [START_REF] Wildon | Searching for knights and spies: A majority/minority game[END_REF]).

Theorem 3. Let N and p be integers such that 0 ≤ p < N 2 , we have:

Q(N, p, ≤) = N + 1 - N + 1 p + 1
whenever N ≡ r [p + 1] with 0 ≤ r ≤ p 2 or r = p.

Furthermore we could also show the following.

Proposition 4. ∀N ≥ 7, Q(N, 3, ≤) = N + 1 -N +1 4 .
A proof of Proposition 4 is provided in the arXiv version of this paper [START_REF] Anglès D'auriac | On more variants of the Majority Problem[END_REF].

Let us remark that all these results show only cases where the value of Q(N, p, ≤ ) is equal to its upper bound provided by Theorem 1. From these it is natural to wonder if the equality of Theorem 3 holds for any N and p such that N ≥ 2p + 1. This is however not the case: Wildon [START_REF] Wildon | Searching for knights and spies: A majority/minority game[END_REF] has checked by a computer search the values of Q(N, p, ≤) for N ≤ 30. In particular he listed all such Q(N, p, ≤) that are not equal to N + 1 -N +1 p+1 . Our (two different) programs confirmed this list. Looking carefully at the results and determining properties of the function Q(•, •, ≤) leads us to ask the following.

Question 1. Is it true that for any positive integer p ≥ 4 there exists a smallest integer N (p) ≥ 2p + 1 such that for any integer

N ≥ N (p), N ≡ r [p + 1] with 0 ≤ r ≤ p, we have: If r ≤ p+1 2 then Q(N, p, ≤) = N + 1 -N +1 p+1 else Q(N, p, ≤) = N -N p+1 ?
(Notice that for r = p we have N -

N p+1 = N + 1 -N +1 p+1 )
Using the program Main.hs, available from Wildon's website 1 , we did generate all couples (N, p) such that Q(N, p, ≤) < N + 1 -N +1 p+1 for N ≤ 51, and among these there is no contradiction to a positive answer to Question 1. Using furthermore Theorem 3 and (2) of Property 16 (see section 4.3) we could completely settle the values of Q(N, p, ≤) in the case of an even p ≤ 12.

Proposition 5. For all even p ≤ 12, N ≥ 2p + 1, N ≡ r [p + 1] with 0 ≤ r ≤ p, we have :

if 0 ≤ r ≤ p + 1 2 then Q(N, p, ≤) = N + 1 - N + 1 p + 1 else Q(N, p, ≤) = N - N p + 1 , with the exception of Q(18, 6, ≤) = 19 -2 = 17, Q(23, 8, ≤) = 24 -2 = 22, Q(28, 10, ≤) = 29 -2 = 27, Q(33, 12, ≤) = 34 -2 = 32.
For odd p ≤ 13, we could also verify that for N sufficiently large the values of Q(N, p, ≤) are those expected by a positive answer to Question 1, however to completely settle these cases one would need to show that

Q(N, p, ≤ ) = N + 1 -N +1 p+1 whenever N ≡ p+1 2 [p + 1].

On the (N, p, =)-identification problem

To our knowledge the (N, p, =)-identification problem has not been yet studied by other authors. A trivial upper bound for Q(N, p, =) is Q(N, p, ≤).

We did obtain a better upper bound.

Theorem 6. Let N and p be integers such that 1 ≤ p < N 2 , and let m be the largest integer such that 2 m ≤ min(N -2p, 2p), we have :

Q(N, p, =) ≤ N + 1 -m - N + 2 -2 m p + 1 .
For p = 1 or 2 we were able to compute the exact value of Q(N, p, =). Proofs for the following two propositions are proposed in the arXiv version of this paper [START_REF] Anglès D'auriac | On more variants of the Majority Problem[END_REF].

Proposition 7. ∀N ≥ 3, Q(N, 1, =) = N -N 2 . Proposition 8. ∀N ≥ 6, Q(N, 2, =) = N -N +1 3 .
Propositions 7 and 8 show that, for p = 1 or 2, the upper bound Q + (N, p, =) of Q(N, p, =) given by Theorem 6, is in fact the right value of Q(N, p, =). This is however not true for any value of p as shown by our programs. For N ≤ 30 and p < N 2 it happens several times that Q(N, p, = ) = Q + (N, p, =) -1 (see Table 1), once that Q(N, p, =) = Q + (N, p, =) -2 (for (N, p) = (30, 4)) and for all other couples (N, p) the equality Q(N, p, =) = Q + (N, p, =) holds.

From these results one could expect that Q(N, p, =) is never very far from the upper bound given by Theorem 6. As we will see in Section 5, this is however not the case as soon as p is at least 3. We will explain there that better bounds than the one of Theorem 6 may be obtained for N very large compare to p by a method that we call "Towers Method".

Table 1: The values of N and p such that

Q(N, p, =) = Q + (N, p, =) -1 .

A tool and some useful Lemmas

In order to describe algorithms solving the (N, p, ≤)-identification problem, or the (N, p, =)-identification problem, we use methods putting balls in boxes divided into two sides ; in the rest of the paper we will consider only non empty boxes of this kind and will, all along, manage to have in each box all the balls with a same color put in a same side.

Given a non empty box B we will call big side of B the side of B with the most balls. In case there is the same number of balls in each side, the big side of B will be the one containing the ball b j where j is the highest index of a ball in B. The side of B which is not the big side will be called the small side.

A non empty box will be said of Type (x, y) if there are x balls in its small side and y in its big side (hence x and y are two integers such that max(x, 1) ≤ y). A box whose small side is empty will be said monocolored, and a box of Type (x, x) will be said balanced .

Of course it has no sense to compare balls that are in a same box since the answer is already known. Given two distinct boxes B and B , the balls in their big sides either have the same color, or not, and this can be decided by comparing any ball of B with any ball of B . For that reason we may consider that we do "boxes comparisons" rather than "balls comparisons". After the comparison of B and B we may place all their balls into one box, in a way compatible with their colors, and throw away the empty boxes. If the Types of B and B were (x, y) and (x , y ) then the Type of the new box is either (x + x , y + y ) or (min(x + y , x + y), max(x + y , x + y)), according to whether the balls in the big sides of B and B have the same color or not. From a partition P of the set B of balls into boxes, we can deduce the possible colorings of the balls : a p-majored (resp. p-equal) Red-green coloring is compatible with P when any two balls in a same box are colored the same if and only if they are in the same side of the box. We will denote by C(P) the set of p-majored (resp. p-equal) Red-green colorings that are compatible with a partition P. Our goal is to reach, within a minimum number of boxes comparisons, a partition P such that |C(P)| = 1. Notice that |C(P)| depends only on the number of balls in the sides of the boxes : a partition of the balls into boxes will be said of Type (x 1 , y 1 )

N 1 (x 2 , y 2 ) N 2 . . . (x k , y k ) N k if it consists in exactly N i boxes of Type (x i , y i ), for i = 1 to k.
From our remarks above it is natural to represent a method M solving the (N, p, ≤) or (N, p, =)-identification problem by a labeled binary tree T M as follows :

• Each vertex u is labeled with a partition P(u) of B into boxes,

• The partition P(R) of the root R of T M is made of N boxes B 1 , B 2 , . . . , B N of Type (0, 1) where each B i contains only the ball b i .

• Each non-leaf vertex u is furthermore labeled with a couple (B(u), B (u)) of boxes belonging to P(u), and it has -one child connected to u by an edge labeled "=". This child is labeled by the partition obtained from P(u) by replacing B(u) and B (u) by the new box obtained in case the comparison of B(u) and B (u) provides that the balls in the big sides of B(u) and B (u) have the same color.

-one child connected to u by an edge labeled " =". This child is labeled by the partition obtained from P(u) by replacing B(u) and B (u) by the new box obtained in case the comparison of B(u) and B (u) provides that the balls in the big sides of B(u) and B (u) have different colors.

• Each leaf-vertex is such that |C(P( ))| = 1.

The binary tree T M is in a sense a "user manual" of the method M as it gives at any step which boxes to compare. However, as T M should contain all possible cases we will use more synthetic ways to describe a method. Furthermore, the partition associated to a vertex of T M is the exact expression of the knowledge on the balls colors provided by the comparisons done when reaching this vertex. We will see in the following that T M may be useful to compute bounds on Q(N, p, ≤) and Q(N, p, =).

If v and w are the two children of a vertex u of T then C(P(u)) is equal to the disjoint union of the two non empty sets C(P(v)) and C(P(w)).

A vertex of T M will be said at level k if it is at distance k from the root. The height of T M is the maximum level of a vertex of T M .

Let v be a vertex of T M at level k ≥ 1. We call parent of v, denoted by p(v), the unique neighbor of v which is at level k -1. The vertex v = v such that p(v ) = p(v) will be said the sibling of v. Remark that in a binary tree, any path P issued from the root contains p(v) for each v ∈ P which is not the root.

From its definition and some preceding remarks we get the following properties of T M . Property 9. Any binary tree T M associated to a method M solving the (N, p, ≤)-identification problem satisfies the following properties:

(i) each p-majored Red-green coloring of B labels exactly one leaf, (ii) the partition of a vertex at level k consists in N -k boxes obtained after k comparisons, (iii) the maximum number of comparisons used by an execution of M is equal to the height of T M .

Notice that similar remarks and properties are valid in the case of the (N, p, =)-identification problem. In particular the Property 9' obtained from Property 9 by replacing "(N, p, ≤)" by "(N, p, =)" and "p-majored Red-green coloring" by "p-equal Red-green coloring" is also valid. From the (easy and well known) fact that a binary tree of height k has at most 2 k leaves, Property 9'(i) and Property 9'(iii), we get the following lower bound.

Lemma 11. For every two integers N and p <

N 2 : Q(N, p, =) ≥ log 2 ( N p ).
Let ⊥ denotes either " = " or " ≤ ". The two following lemmas are also useful.

Lemma 12. For every two integers N and 1 ≤ p < N 2 we have :

Q(N, p, ⊥) ≥ 2 + Q(N -2, p -1, ⊥).
Proof. Let T M be the tree associated to a method solving the (N, p, ⊥)identification problem within Q(N, p, ⊥) comparisons. Since p ≥ 1 the height of T M , which is equal to Q(N, p, ⊥) by Property 9(iii), is at least 2 and there is in T M an edge labeled " =" between the root R and a vertex We claim that T v gives a method to find the (p -1)-equal, or (p -1)majored (depending on the value of ⊥), Red-green coloring of N -2 balls: use the N -2 boxes of cardinality 1 of P(v) \ B * , ignore b and b in the partitions, do the box-comparisons and follow the edges as indicated by the labelings, except when you reach a vertex of T v labeled with the "empty" box B * : then don't do any comparison and go to any child. Then, for any leaf of T v the resulting partition P v ( ) is the same as the one obtained from P( ) by withdrawing b and b that are in different sides of one box. Hence |C(P v ( ))| = 1, else we would contradict the fact that |C(P( ))| = 1. So the height of T v minus 1 (we skipped exactly one comparison) is at least

Q(N -2, p -1, ⊥). Since the height of T v is at most the height of T M minus 1 we get that Q(N, p, ⊥) -2 ≥ Q(N -2, p -1, ⊥).
we have :

Q(N, p, ⊥) ≤ p + Q(N -(p + 1), p, ⊥).
Proof. In order to prove the upper-bound on Q(N, p, ⊥) it is sufficient to exhibit a method solving the (N, p, ⊥)-identification problem within at most p + Q(N -p -1, p, ⊥) comparisons. So let us assume that we have a set of N balls b 1 , b 2 , . . . , b N colored by a p-equal or p-majored (depending on the value of ⊥) Red-green coloring. We may first compare b 1 to b 2 , b 3 , ...b i for some 2 ≤ i ≤ N , thus obtaining a partition of Type (x, y) 1 (0, 1) N -i for some integers 0 ≤ x ≤ y such that x + y = i. The rule will be to do so until y = x + p + 1, which will happen since we must have one side containing at most p balls and N > 3p+1. At this stage, we have done 2x+p comparisons, all balls in the side of cardinality y = x + p + 1 > p of the only bicolored box should be red and those x ≤ p in the other side are green : it remains N -(p + 2x + 1) other balls whose colors have to be determined and the only information we have about them is that there are at most p -x, or exactly p -x in case ⊥ means "=", green balls among them. Since x ≤ p and we assumed N > 3p + 1 then N -(p + 2x + 1) > 2(p -x) and we can determine the colors of the remaining balls using at most

Q(N -(p + 2x + 1), p -x, ⊥) comparisons. So Q(N, p, ⊥) ≤ M ax 0≤x≤p (p + 2x + Q(N -(p + 2x + 1), p - x, ⊥ )
). This maximum is attained for x = 0 since by Lemma 12 we have for any 1 ≤ x ≤ p :

p + Q(N -(p + 1), p, ⊥) ≥ p + 2 + Q(N -(p + 3), p -1, ⊥) ≥ . . . ≥ p + 2x + Q(N -(p + 2x + 1), p -x, ⊥).

Proofs concerning the (N, p, ≤)-identification problem

In order to have a self-contained paper we begin this section with a proof of the first statement in Aigner's Theorem 1 (the second statement is contained in Theorem 3 which is proved in the next subsection).

4.1 Proof of Q(N, p, ≤) = N + 1 -N +1 p+1 or N -N p+1
We first show that N + 1 -N +1 p+1 is an upper bound of Q(N, p, ≤). Let N and p be integers such that 0 ≤ p < N 2 . For p = 0 :

Q(N, 0, ≤) = 0 = N + 1 -N +1 1
, and the bound is correct. Let us consider the case where p ≥ 1.

Assume first that N < 3p + 2. Then N +1 p+1 = 2 and N + 1 -N +1 p+1 = N -1 which is always an upper bound of Q(N, p, ≤), as already noticed in Remark 10.

Let us consider now the case where N ≥ 3p + 2. We may use consecutively Lemma 13 as long as we have a number of balls which is at least 3p + 2 :

Q(N, p, ≤) ≤ p + Q(N -(p + 1), p, ≤) ≤ . . . ≤ p + Q(N -(p + 1), p, ≤). Then ≥ 1 is such that 2p + 1 ≤ N -(p + 1) < 3p + 2 ⇐⇒ 2p + 2 ≤ N + 1 -(p + 1) < 3p + 3 ⇐⇒ N + 1 -2(p + 1) ≥ (p + 1) > N + 1 -3(p + 1) ⇐⇒ = N + 1 p + 1 -2.
Then we have

Q(N, p, ≤) ≤ p + Q(N -(p + 1), p, ≤) ≤ p + N -(p + 1) -1 = N --1 = N + 1 - N + 1 p + 1 .
We now show that N -N p+1 is a lower bound of Q(N, p, ≤). Let N and p be integers such that 0 ≤ p < N 2 . For p = 0 : Q(N, 0, ≤) = 0 = N -N 1 , and the bound is correct. Let us consider the case where p ≥ 1.

Let M be any method that solves the (N, p, ≤)-identification problem. The binary tree T M has a leaf which is connected to the root by a path whose all edges are labeled with "=". The partition P( ) contains then only monocolored boxes.

In case one box B of P( ) is of cardinality at most p, there will be at least two p-majored Red-green colorings compatible with P( ) : one where all balls are red, and one where all balls in B are green and all other balls are red. This is in contradiction with the fact that is a leaf of T M . So all boxes of P( ) are of cardinality at least p + 1 ; hence P( ) contains at most N p+1 boxes. These are obtain after at least N -N p+1 comparisons. Since M was chosen as any method solving the (N, p, ≤)-identification problem, this implies that indeed Q(N, p, ≤) ≥ N -N p+1 . Noticing that the upper bound and lower bounds obtained above differ by at most 1 the proof is done.

We now prove Theorem 3 which contains the second statement of Theorem 1.

Proof of Theorem 3

We have to show that Q(N, p,

≤) = N + 1 -N +1 p+1 whenever N ≡ r [p + 1] with 0 ≤ r ≤ p 2 or r = p. Consider first the case where N ≡ p [p + 1]. Then N + 1 -N +1 p+1 = N -N p+1
, hence by Theorem 1 we may conclude that Q(N, p, ≤) is indeed equal to N -N p+1 . Let us assume now that N ≡ r [p + 1] for some 0 ≤ r ≤ p 2 and let then q := N +1 p+1 = N p+1 . By the first statement of Theorem 1 we have N -q ≤ Q(N, p, ≤) ≤ N + 1 -q. Assume, by contradiction, that there exists a method M * that solves the (N, p, ≤)-identification problem using only N -q comparisons. By Property 9(iii), the height of T M * is equal to N -q and the partition associated to a leaf of T M * should then contain at least q boxes. As in the proof of the lower bound in section 4.1 we know that there exists a leaf * of T M * whose associated partition P * ( * ) is made of at most q, and hence exactly q, monocolored boxes.

Let (R, u 1 , u 2 , . . . , u N -q = * ) be the path from the root R to * in T M * and let i = min{1 ≤ j ≤ N -q -1|P * (u j+1 ) has q boxes of cardinality ≥ p + 1} (i does exist since N -q -1 satisfies the requirement).

Consider the vertex v i+1 connected to u i by an edge labeled " = " (that is v i+1 is the sibling of u i+1 ). From our assumptions, the partition P * (v i+1 ) consists into q -1 monocolored boxes of cardinality at least p + 1 , called big monocolored boxes of P * (v i+1 ), one bicolored box B of cardinality at least p + 1 containing x balls in one side and y in the other where 1 ≤ x ≤ y ≤ p, and N -(i + 1) -q monocolored boxes of cardinality at most p, called small monocolored boxes of P * (v i+1 ).

Considering P * (v i+1 ), we denote by A the set of balls belonging to big monocolored boxes, X the set of the x balls in the small side of B, Y the set of the y balls in the big side of B, and C the set of balls belonging to small monocolored boxes. Notice that A, X , Y, C is a partition of the whole set B of balls.

From v i+1 we will follow a path in T M * using the following rule that will all along ensure partitions with exactly one bicolored box, containing X in one side and Y in the other, and monocolored boxes containing balls from A ∪ C.

Rule : We start from the vertex v i+1 which by definition satisfies the requirement. As long as we are on a non-leaf vertex v we go down in the tree by repeating the following :

• if B(v) and B (v) (the two boxes of P * (v) that will be compared at this step) are both monocolored we follow the edge labeled " = " and get to the next vertex v,

• else one of them, say B(v), is the bicolored box of P * (v). In that case, if in P * (v) the balls in B (v) are all in C then we follow the edge labeled with the answer that merges the balls in B (v) with those of X and else we follow the edge with the answer that merges the balls in B (v) with those of Y ; and get to the next vertex v.

The process stops when we reach a leaf-vertex l. By the rule, P * (l) has monocolored boxes whose contents are included in A ∪ C and exactly one bicolored box B l . Let X be the set of balls of B l in the side containing X and let Y be the set of balls of B l in the side containing Y. By definition the balls of X that are not in X are in C and those of Y that are not in Y are in A ∪ C.

Claim 14. |X | + |C| ≤ p.

Proof. There are at least (q-1)(p+1) balls in A and exactly N = q(p+1)+r balls in B, so we have at most p+1+r balls in X ∪Y ∪C. Since |X ∪Y| ≥ p+1, one has |X ∪ Y| = p + 1 + s, for some 0 ≤ s ≤ r ≤ p 2 . Then 0 ≤ |C| ≤ N -(q(p + 1) + s) = r -s, and

|X | ≤ p+1+s 2 ≤ p+1+s 2 ≤ |Y| ≤ p, so that |X | + |C| ≤ p+1+s 2 + r -s = p+1-s 2 + r ≤ p+1 2 + p 2 = p. The claim is proved. Claim 15. No monocolored box of P * (l) is included in C.
Proof. Let us assume the contrary and let C 1 ⊆ C be the set of balls of a monocolored box of P * (l). By definition X ∪ C 1 ⊆ X ∪ C, so by Claim 14 we have |X ∪ C 1 | ≤ p. Then there are at least two p-majored Red-green colorings compatible with P * (l) : one colors in green only the vertices of X and the other colors in green the vertices of X ∪ C 1 . This contradicts the fact that l is a leaf of T * M and ends the proof of the claim. A few remarks are now enough to end the proof of Theorem 3. Let us remind that P * (v i+1 ) contains N -(i+1) boxes and among them N -(i+1)-q are monocolored boxes included in C. By Claim 15 all these monocolored boxes disappear after doing all the comparisons indicated by the path from v i+1 to l obtained by applying the Rule. As we already know, each of these comparisons decreases the number of boxes by 1 and it is straightforward to verify that, furthermore, the number of monocolored boxes included in C either stays the same or decreases by 1 (only in case at least one of the two boxes that are compared is a monocolored box included in C). So the number of boxes in P * (l) is at most q. Moreover, by our assumption on M * , the height of T M * and hence the level of l is at most N -q, so that the number of boxes in P * (l) is at least q. From all these facts we deduce that each comparison done to get P * (l) from P * (v i+1 ) concerns at least one monocolored box included in C. So, as we followed the Rule, the bicolored box B l of P * (l) is such that X ⊆ X ∪ C and Y = Y.

Then, by Claim 14 and the fact that |Y | = y ≤ p, each side of B l contains at most p balls and we have at least two p-majored Red-green colorings compatible with P(l) : everything colored red except the balls in one of the two sides of B l . This contradicts the fact that l is a leaf of T M .

The motivation of Question 1

From the preceding results we get the following properties of Q(N, p, ≤).

Property 16. (1) Let p be a nonnegative integer, the function : N → Q(N, p, ≤) is nondecreasing and 1-lipschitz, that is for N ≥ 2p + 1:

Q(N, p, ≤) ≤ Q(N + 1, p, ≤) ≤ 1 + Q(N, p, ≤) (2
Q(N , p, ≤) < N + 1 - N + 1 p + 1 . Proof. (1)
From the first statement of Theorem 1 one get the lower bound of Q(N + 1, p, ≤):

Q(N, p, ≤) ≤ N + 1 - N + 1 p + 1 ≤ Q(N + 1, p, ≤).
Let now M be a method determining a p-majored Red-green coloring of N balls within at most Q(N, p, ≤) comparisons. It is easy to derive from M a method determining a p-majored Red-green coloring of N + 1 balls using at most one more comparison : put aside one of the N + 1 balls, you have then a p-majored Red-green coloring of N balls, determine their colors using M , if you get less that p green balls one more comparison will be necessary to know the color of the ball that was put aside. Thus the second inequality of Property 16 (1) is proved.

(2) Let us consider N = N + k(p + 1) for some k ≥ 0. By Lemma 13 we know that Q(N , p, ≤) ≤ kp + Q(N, p, ≤) and then by the assumption that Q(N, p, ≤) < N + 1 -N +1 p+1 we get

Q(N , p, ≤) < kp + N + 1 - N + 1 p + 1 = N + 1 -k -N +1 p+1 = N + 1 -N +1 p+1 .
For a given p ≥ 1 and any

N ≥ 2p + 1, let us say that N is of character p -in case Q(N, p, ≤) < N + 1 -N +1 p+1
and else N is said of character p + . Theorem 3 shows that N is of character p + as soon as N ≡ r [p + 1] with 0 ≤ r < p+1 2 . From Property 16 and Theorem 1 it is easy to derive other properties of the character of N depending on the remainder of the Euclidean division of N by p + 1: Property 17. Given p ≥ 1 and N ≥ 2p + 1, the following holds :

1. If N is of character p -then N + 1 is p -except if N ≡ p -1 [p + 1], 2. If N is of character p -then N is of character p -for any N ≥ N such that N ≡ N [p + 1].
From this last property we derive that the sequence of characters of N becomes periodic starting from a big enough N .

Property 18. For every nonnegative integer p exactly one of the two following statements is satisfied :

1. The character of every N ≥ 2p + 1 is p + , or 2. There exist two integers p+1 2 ≤ r p ≤ p -1 and N p ≥ 2p + 1 such that for every N ≥ N p :

N is of character p -⇐⇒ N ≡ r [p + 1] with r p ≤ r ≤ p -1.
Proof. Let us assume that the first statement is not satisfied. Then the set S = {N |N ≥ 2p + 1 and N is of character p -} is not empty. So we may choose r p as the minimum r for which there exists N ∈ S such that N ≡ r

[p + 1]. Let now N p be the minimum N ∈ S such that N ≡ r p [p + 1].
By Theorem 3 (page 3) and the definition of r p we know that p+1 2 ≤ r p ≤ p -1 and that every N ≥ 2p + 1 such that N ≡ r [p + 1] with 0 ≤ r ≤ r p -1 or r = p is of character p + . Furthermore, by Property 17, every N ≥ N p such that N ≡ r [p + 1] with r p ≤ r ≤ p -1 is of character p -.

As mentioned at the end of section 2.1, we looked at all couples (N, p) such that Q(N, p, ≤) < N + 1 -N +1 p+1 for N ≤ 51. We did not find any contradiction to the hypothesis that r p is always equal to p 2 + 1. This motivated our Question 1 (page 3).

5 Proofs concerning the (N, p, =)-identification problem

A Lemma

The next Lemma will allows us to prove Theorem 6.

Lemma 19. Let N and p be integers such that 1 ≤ p < N 2 , and let ν ≥ 0 be an integer such that 2 ν ≤ N -2p, then

Q(N, p, =) ≤ 2 ν -1 -ν + Q(N + 1 -2 ν , p, ≤).
Proof. Assume first that ν = 0. It is always true that Q(N, p, =) ≤ Q(N, p, ≤ ), so Lemma 19 is verified in the case ν = 0.

From now on we will assume that ν ≥ 1. As for the preceding proofs, we will use a method which compares boxes, but this time we will have several locations for the boxes : the laboratory which will initially contain all the balls of B into boxes of Type (0, 1), the reserve that all along contains only balanced bicolored boxes and a podium which contains steps numbered starting from 0: the ith step of the podium is provided to receive a monocolored box of size 2 i .

Any situation where the laboratory contains only boxes of Type (0, 1) and the reserve only balanced boxes will be said a correct situation. The overage of a correct situation is equal to the overage of red over green among balls that are in the laboratory or in the reserve. Notice that it is the same as the overage among balls in the laboratory since the boxes in the reserve are balanced.

We now describe a "subroutine" S(i), for i ≥ 0, which starting from any correct situation with an overage O i > 2 i , builds one monocolored box of size 2 i , and ends with a correct situation with a new overage of at least O i -2 i > 0.

-For i = 0, every box of the laboratory has cardinality 2 i . After putting one of it aside, the situation is still correct and the overage decreases by at most one (in case the ball in the box we have chosen happened to be red).

-For i = 1, let us compare, one by one, couples of balls in the laboratory: as long as we obtain a balanced box we put it in the reserve. Since it is assumed that O 1 > 2, there are at least three more red balls than green balls and thus we are sure to get once a monocolored couple. Putting it aside, we obtain a correct situation whose overage has decreased by at most 2.

-The same way, we may define inductively S(i + 1) from S(i). Assume S(i) exists, we will show that then S(i + 1) exists. Suppose that we are in a correct situation with an overage O i+1 > 2 i+1 . We may apply S(i) in order to get a monocolored box B of size 2 i . We put B aside. By the induction hypothesis, the situation is then correct and the remaining balls in the laboratory have an overage O > 2 i+1 -2 i = 2 i . We may apply S(i) again in order to obtain a second monocolored box B of size 2 i . We then compare B and B . If this comparison results in a bicolored box, this box is balanced and we put it into the reserve : the overage in the laboratory is still more than 2 i+1 and we may repeat the procedure. Each time we get a bicolored box the number of balls in the laboratory decreases, but not the overage, so that we will finally obtain a monocolored box of size 2 i+1 . After putting this box aside, by the induction hypothesis, the situation is correct. If the withdrawn balls are green, the overage of the final situation increases, and else it decreases by at most 2 i+1 . So S(i + 1) does exist.

Let µ be the largest integer such that 2 µ ≤ N -2p ; since we assumed that ν ≥ 1, we have µ ≥ 1. We will define a method M (ν) that solves the (N, p, =)-identification problem within at most 2 ν -1-ν +Q(N +1-2 ν , p, ≤) comparisons, thus proving the lemma. We describe now M (ν).

At

Step 0 of M (ν) we start with the initial state, that is an empty podium, an empty reserve, and a laboratory containing all the balls in boxes of Type (0, 1). So, at this stage, the situation is correct and the overage O(0) = N -2p is by definition at least 2 µ > Σ µ-1 j=0 2 j ≥ 2 0 . We apply S(0) in order to obtain a monocolored box of cardinality 2 0 which is put on the 0th step of the podium. Then we are in a correct situation with a positive overage O(1). If µ > 1 then O(1) > Σ µ-1 j=1 2 j ≥ 2 1 . We may continue: for each i ≤ ν -1 ≤ µ -1, Step i starts with a correct situation with an overage O(i) > Σ µ-1 j=i 2 j ≥ 2 i and we apply S(i) in order to obtain a monocolored box of cardinality 2 i which is put on the ith step of the podium. We are then in a correct situation with a positive overage

O(i + 1). If µ > i + 1 then O(i + 1) > Σ µ-1 j=i+1 2 j ≥ 2 i+1
. At the end of Step ν -1 of M (ν) we have filled ν steps of the podium with monocolored boxes of cardinality 1, 2, . . . , 2 ν-1 . Let B ν be the set of balls that are not on the podium and

N ν = |B ν | = N -(2 ν -1).
The reserve contains only balanced boxes and hence an even number, let us say 2k (k ≥ 0), of balls. The laboratory contains N ν -2k = N +1-2 ν -2k balls being each contained in one box of Type (0, 1) and at most p -k of these balls are green. The overage of red balls in the laboratory is the same as the overage in B ν and we know that it is positive. all balls, or x = 0 and the three green balls are in a monocolored box of size 3 or x = 1 and the two remaining green balls are in a monocolored box of size 2. In the last two cases, we have to solve a problem equivalent to the one of finding one green ball among a balls, which by Proposition 7 can be done leaving at least a 2 boxes. So in total we have at least 1 + a + a 2 boxes which is at least 1 + 3a 2 ≥ 3N 10 -4.1, so more than 3N 10 -5. We observe that the ratio 3 10 is slightly better than the ratio 1 4 obtained by Theorem 6. Hence, for a big enough N the method described in the proof of Proposition 20 is more efficient than the one in the proof of Theorem 6.

The method used in the proof of Proposition 20 can be generalized for any value of p by the Towers Method that we describe now : this name comes from the fact that we may consider that we build, from the boxes obtained by the chosen comparisons, towers each containing all monocolored boxes of a given size, the height of a tower corresponding to the number of boxes it is made of. For a given p the method depends on the following parameters :

• a non empty set E = {u 1 , . . . , u k } ⊆ {2, . . . , p} of sizes of the monocolored boxes that will be built. This subset should satisfy the following "unicity property" : For every 0 ≤ l ≤ p, there exists at most one k-tuple of non-negative integers (q 1 , . . . , q k ) such that l = q 1 u 1 +. . .+q k u k . We denote by U(p) the set of subsets of {2, . . . , p} that have the unicity property and by L E , E being in U(p), the set of values 0 ≤ l ≤ p, for which there exists a k-tuple associated with the above expression of l as a sum of values in E.

The cardinality k ≤ p -1 of E will be the number of towers that will be erected. In the proof of Proposition 20 we had E = {u 1 , u 2 } with u 1 = 2 and u 2 = 3 and indeed 1 cannot be expressed as a sum of 2's and 3's, and 0, 2 or 3 can, but by only one way ; so L E = {0, 2, 3}.

• a set of k integers h 1 , . . . h k , expressing each the number of monocolored boxes of size u i that are added to the u i -tower at each step. In the proof of Proposition 20 we had h 1 = h 2 = 1. Now we may describe the Towers method.

As usual all balls are initially in boxes of Type (0, 1). At the first step we compare b 1 to b 2 , b 3 , ... until to obtain p + 1 balls of the same color (and hence red). Thus we get a partition containing exactly one bicolored box of Type (u, p + 1) for some integer u ≤ p, with all other boxes of cardinality 1.

At the second step we use a procedure "add floors to each tower" by consecutively building h 1 monocolored boxes of cardinality u 1 added to the among the set of balls placed in monocolored boxes, for each 1 ≤ r ≤ k. So x r represents hrur h 1 u 1 +...+h k u k . We will need one more variable y E , and the linear programming problem P E will be the following :

Maximize y E subject to      k i=1 x i = 1, y E -1≤i≤k C(q i (l))u -1 i x i ≤ 0 for each l ∈ L E , x i ≥ 0
It is clear that P E is feasible. Let (x 1 , x 2 , . . . , x k , y E ) be an optimal vertex of P E . Since all coefficients of P E are rational we have that all x i 's are rational numbers, and then there exist integers a 1 , . . . , a k , b such that x r = ar b = arΠ 1≤i≤k u i bΠ 1≤i≤k u i for each 1 ≤ r ≤ k. A Towers Method with parameters E and h r = a r Π 1≤i≤k,i =r u i for each 1 ≤ r ≤ k, will provide, for a big enough number of balls, a proportion x r of balls placed in monocolored boxes of size u r among balls placed in monocolored boxes.

We can solve P E for each E ∈ U(p) and the best ratio C T (p) = max E∈U (p) y E . Notice that it is enough to consider only maximal subsets E in U(p).

In particular one can show the following : Proposition 21. For 3 ≤ p ≤ 6, the best ratio obtained by the Towers Method is

• C T (3) = 3 10 , with E = {2, 3}, u 1 = 2, u 2 = 3, h 1 = 1 and h 2 = 1, • C T (4) = 5 18 , with E = {2, 3}, u 1 = 2, u 2 = 3, h 1 = 3 and h 2 = 4, • C T (5) = 2 9 , with E = {2, 3}, u 1 = 2, u 2 = 3, h 1 = 3 and h 2 = 1, • C T (6) = 1 5 , with E = {3, 4}, u 1 = 3, u 2 = 4, h 1 = 3 and h 2 = 4.
However one may also wonder if there are other methods that could give better bounds. Given an integer q ≥ 2, let p be any integer such that p ≥ q q and set k p = p q . Claim 23. The set E = {u i |u i = k p + q i-1 , i ∈ {1, . . . , q -1}} belongs to U(p).

In order to prove this Claim we have to show that for any 0 ≤ l ≤ p there exists at most one (q -1)-tuple (x 1 , . . . , x q-1 ) of non-negative integers such that l = Σ 1≤i≤q-1 x i u i . So, let us consider 0 ≤ l ≤ p and let s = l kp+1 . Since l ≤ p, by the definition of k p , we have 0 ≤ s ≤ q -1. Then, since each u i ≥ k p + 1, we have Σ 1≤i≤q-1 x i ≤ s.

On another hand we have k p ≥ q q-1 > (q -2)q q-2 ≥ (s -1)q q-2 -s, and then by definition of s we have l ≥ s(k p + 1) = (s -1)k p + k p + s > (s -1)(k p + q q-2 ). Then we have Σ 1≤i≤q-1 x i ≥ s. By the inequality above we conclude that Σ 1≤i≤q-1 x i = s. There is a unique way to write l -sk p in basis q and hence at most one way to obtain l balls as the union of boxes of cardinalities k p + q 0 , . . . , k p + q q-2 . The Claim is proved.

Let us now assume that for some "big" N we use the Towers method with E as defined in Claim 23 and heights h i = 1 for each 1 ≤ i ≤ q -1. Let l be the number of green balls that should be detected at the end of the erection of the towers. Notice that the towers all have the same number a of monocolored boxes. By the proof of Claim 23 there are s = l kp+1 monocolored boxes to discover and 0 ≤ s ≤ q -1. We claim that the case leaving the smallest number of boxes is when there is one green box in each of the q -1 towers, in which case we end with at least (q -1) a 2 boxes. Indeed if we have less than q -1 green boxes to find, then obviously we won't end with less boxes, and in case we have to find q -1 green boxes among at most q -2 towers we gain at least a 2 boxes and loose at most a 2 -C q-1 a ≤ a 2 . It remains to observe that N is approximately equal to aΣ 1≤l≤q-1 (k p + q l-1 ) = a (q -1)k p + q q-1 -1 q-1 ≤ aqk p ≤ ap.

Hence B(N, p, =) ≥ (q -1) N 2p -R for some constant R which means that C p ≥ q-1 2p and then pC p ≥ q-1 2 , thus lim p→∞ pC p = ∞.

Conclusion

The problems we considered here on a set of bicolored balls are also known with other equivalent formulations or generalizations: detection of fake coins with a two-pan balance, minimization of the number of questions allowing to find a truth-teller in a population composed by "knights" who always tell the truth, and "knaves", who always lie, chips testing... ([8], [START_REF] Alonso | Determining the Majority[END_REF], [START_REF] Alonso | The Worst-Case Chip Problem[END_REF], [START_REF] Blecher | On a logical problem[END_REF]...). They can also be be formulated as two-players games ( [START_REF] Saks | On Computing Majority by Comparisons[END_REF], [START_REF] Wiener | Search for a majority element[END_REF], [START_REF] Blecher | On a logical problem[END_REF], [START_REF] Aigner | Variants of the Majority Problem[END_REF], [START_REF] Wildon | Knights, spies, games and ballot sequences[END_REF]...). See [START_REF] Anglès D'auriac | On more variants of the Majority Problem[END_REF] for more details.

In Theorem 3 of this paper, for a given integer p, we provide the exact value of Q(N, p, ≤) for half of the integers N and for the other half we guessed in Question 1 a formula which is verified for any N ≤ 51.

We also proposed some bounds on Q(N, p, =), but the exact value is proved only for p = 1 or 2. In fact the (N, p, =)-identification problem seems to be much more difficult to handle than the (N, p, ≤)-identification problem.

Remark that it is easy to decide if a given partition of balls into boxes is compatible with a (unique) p-majored Red-green coloring. We conclude with a last question : What is the complexity of deciding if a given partition of balls into boxes is compatible with a (unique) p-equal Red-green coloring ?

Remark 10 .

 10 Trivially N -1 comparisons are enough to solve both identification problems. The partition labeling a vertex at level N -1 (if any) consists in one single box, no more comparisons are possible, and only one side of the box contains less than p + 1 balls and those are exactly the green balls of B. Hence such a vertex should be a leaf of T M and the height of T M is at most N -1.

  v. In P(v), the first two balls b, b that are compared by M are in a box B * of Type (1, 1) and all other boxes are of Type (0, 1) and contain the balls of B \ {b, b }. Notice that the set B \ {b, b } contains N -2 balls and exactly one less green ball than B. On another hand, for any leaf of the subtree T v of T M of root v we have |C(P( ))| = 1 and hence the balls b and b should be in an unbalanced box of P( ). This means that, on any path of T M from v to a leaf, there is a vertex where one of the two boxes that are compared is B * containing only b and b .

  ) If N and p are such that N ≥ 2p + 1 and Q(N, p, ≤) < N + 1 -N +1 p+1 then for any N = N + k(p + 1) (k ≥ 0) we have:

For

  any positive integer p, let us define I p as the set of values C ∈ [0, 1] for which there exists a constant D ≥ 0 such that, for each N > 2p, we have B(N, p, =) ≥ CN -D. Let C p be the supremum of I p . It is easy to see that I p is equal either to [0, C p ] or to [0, C p [, and that, by Theorem 6, C p ≥ 1 p+1 for every p ≥ 0. Proposition 22. The sequence (C p ) is non-increasing and lim p→∞ pC p = ∞. Proof. Let us consider an integer p ≥ 1 and an integer N ≥ 2p + 1. By Lemma 12 one hasB(N -2, p-1, =) = N -2-Q(N -2, p-1, =) ≥ N -Q(N, p, =) = B(N, p, =).Assume that for some C > 0 there exists D ≥ 0 such that B(N, p, =) ≥ CN -D. Then by the previous inequality we get thatB(N -2, p -1, =) ≥ C(N -2) -D and hence C p-1 ≥ C p .To state lim p→∞ pC p = ∞, we will use a coefficient provided by the Towers Method.

www.ma.rhul.ac.uk/ uvah099/Programs/MajorityGame/Main.hs

Acknowledgment

The authors would like to thank the anonymous reviewer for helpful comments that improved the presentation of this work.

So we may determine the colors of all balls in the laboratory within at most Q(N ν -2k, p-k, ≤) comparisons and these will lead to a partition P of the balls of the laboratory into at least N ν -2k -Q(N ν -2k, p -k, ≤) boxes. By Lemma 12 (page 8) we know that Q(N ν -2k, p-k, ≤) ≤ Q(N ν , p, ≤)-2k ; from this we deduce that P has at least N ν -Q(N ν , p, ≤) boxes. Comparing one of these boxes with all boxes in the reserve will then provide a partition P ν of B ν which determines completely the colors of the balls in B ν and has the same number of boxes than P.

Then we know exactly the number p ≤ p of green balls in B ν and there should be p -p green balls on the podium. The binary representation of p -p gives us the boxes of the podium containing the green balls without any further comparisons. So we have a partition of the whole set of balls to which corresponds a unique Red-green coloring and it consists into ν boxes for balls on the podium and at least N ν -Q(N ν , p, ≤) boxes for balls in B ν . The number of comparisons that are done to obtain such a partition is then at most

The proof of Theorem 6

In this subsection we provide the proof of the theorem stated page 4 which gives an upper bound of Q(N, p, =).

Combining Lemma 19 and Theorem 3 we get that

for µ being the largest integer such that 2 µ ≤ N -2p.

It remains to show which value of ν provides the minimum of f

We will do it by comparing the value of f for two consecutive values ν and ν + 1 such that 2 ν+1 ≤ N -2p. We may write N = 2p + 2 ν+1 + = 2p + 2 ν + 2 ν + where ≥ 0:

If 2p < N -2p, then the minimum will be attained for m equal to the largest ν such that 2 ν-1 ≤ p, or equivalently 2 ν ≤ 2p.

However as mentioned in subsection 2.2 the bound in Theorem 6 is not always equal to Q(N, p, =).

The Towers Method

In this part it will be convenient to use the notation B(N, p, =) for the value N -Q(N, p, =). This value represents the minimum number of boxes we may have at the end of any optimal method solving the (N, p, =)-problem (i.e. using at most Q(N, p, =) comparisons). Similarly we define

. By Theorem 6 we know that for a "sufficiently big N ", B + (N, p, =) is approximately N p+1 . We will show in the following that a better ratio may be obtained for any p ≥ 3. Let us first consider the case where p = 3. Proof. To prove the bound we exhibit a method giving the colors of all balls that ends with at least 3N 10 -D boxes, for a constant D > 0. We first compare b 1 to b 2 , b 3 , ... until to obtain 4 balls of the same color (and hence red). Thus we get a partition containing exactly one bicolored box and, more precisely, of Type (u, 4) 1 (0, 1) N -(u+4) for some integer u ≤ 3.

Then we build monocolored boxes of cardinality alternately 2 and 3 : during this process, each time we get a bicolored box we compare it to the previous lonely bicolored box, this will happen at most 3-u times, and doing so we keep the property of having exactly one bicolored box. We stop this process when there is no more cardinality 1 boxes. At this stage, if we don't have the same number of boxes of cardinality 2 and 3, we compare the boxes obtained during the last trial with the unique bicolored box, increasing its cardinality by at most 4. So at the end of this process, we have a partition of the balls of Type (x, y) 1 (0, 2) a (0, 3) a where y ≥ 4, x + y ≤ 17 and a ≥ N -17 5 . It is not possible that x = 2, since else the remaining green ball cannot be in a box of Type (0, 2) or (0, 3). So either x = 3 and we know the colors of u 1 -tower, h 2 monocolored boxes of cardinality u 2 added to the u 2 -tower, . . . , h k monocolored boxes of cardinality u k added to the u k -tower. During this process, each time it happens that we create a new bicolored box we compare it to the previous lonely bicolored box in order to keep a partition with exactly one bicolored box. We continue to "add floors" as long as we can. If we have to stop because of lack of cardinality 1 boxes before finishing the "add floors" procedure, then we compare each box created during the last and partial "add floors" procedure with the unique bicolored box. At that point, the partition is of Type (x, y)

h 1 u 1 +...+h k u k (so c corresponds to the number of times we could perform entirely the procedure "add floors").

At this stage we know for sure x green balls and we have to detect the remaining l = p -x (0 ≤ l ≤ p). Since these balls are in the towers, by the "unicity property", there exists a unique (q 1 (l), . . . , q k (l)) such that l = Σ 1≤i≤k q i (l)u i and q i (l) ≥ 0 for each i ; that is l ∈ L E . It remains now to solve the (h i c, q i (l), =)-problem for each 1 ≤ i ≤ k in order to find all green balls, since one monocolored box may be considered as just one ball of the same color. Any method solving these problems may be used. In case we know for each (N, q i (l), =)-problem a constant C(q i (l)) such that the (N, q i (l), =)-problem may be solved leaving at least C(q i (l))N -D i boxes, for some constant D i , since exactly as in the case of the proof of Proposition 20 the value of x + y is bounded by a constant, we would then get at least 1≤i≤k C(q i (l))h i h 1 u 1 +...+h k u k N -D l remaining boxes, for some constant D l . Notice that we know from Theorem 6 that coefficients C(q i (l)) ≥ 1 q i (l)+1 do exist. As we cannot fix the value l ∈ L E of balls remaining to be detected we obtain B(N, p, =) ≥ min l∈L E { 1≤i≤k C(q i (l))h i h 1 u 1 +...+h k u k }N -D, for some constant D. Notice that since 1 / ∈ E we have q i (l) < p. Hence we may show now how, based on best known values C T (i) for i < p we may compute recursively, for each p ≥ 3, the Towers Method's parameters providing the maximum constant C T (p), by solving a linear programming problem. We will need values of C T (i) for i < 3: the (N, 0, =)-problem can obviously be solved leaving N boxes. By Propositions 7 and 8, B(N, 1, =) ≥ 1 2 N -1 2 and B(N, 2, =) ≥ 1 3 N -1 3 . So we set C T (0) = 1, C T (1) = 1 2 and C T (2) = 1 3 . First we have to compute all subsets E = {u 1 , . . . , u k } ∈ U(p). For each such E, we will show how to compute heights h 1 , h 2 , . . . h k providing the best proportion C E (p) of boxes we are sure to obtain by a Towers Method based on E. For that purpose, we need to determine what is in such an optimal method, the proportion x r of balls placed in monocolored boxes of size u r


Rakotomalala Robinson

Mustapha Abdelmoula

Martine Mallet

Romain Coustel
email: romain.coustel@univ-lorraine.fr

Mbolantenaina Rakotomalala Robinson

Starch functionalized magnetite nanoparticles: New insight into the structural and magnetic properties Mbolantenaina

Keywords: Magnetic nanoparticles, superparamagnetic materials, magnetite, polysaccharide, Raman, Mössbauer

scientifiques 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.

Introduction

The preparation and characterization of magnetic materials at nanoscale attract strong interest because of their properties that differ appreciably with respect to the bulk material.

They have many possible uses in the biomedical field as contrast agents in magnetic resonance imaging or as drug delivery systems [START_REF] Hong | Facile synthesis of polymer-enveloped ultrasmall superparamagnetic iron oxide for magnetic resonance imaging[END_REF][START_REF] Zhang | Long-Circulating Heparin-Functionalized Magnetic Nanoparticles for Potential Application as a Protein Drug Delivery Platform[END_REF], in environmental processes as nanoadsorbents or as catalysts [START_REF] Ren | Chromium (VI) adsorption from wastewater using porous magnetite nanoparticles prepared from titanium residue by a novel solid-phase reduction method[END_REF][START_REF] Yoon | Synthesis of magnetite/nonoxidative graphene composites and their application for arsenic removal[END_REF][START_REF] Iyengar | Fabrication of magnetite nanocrystals in alcohol/water mixed solvents: catalytic and colloid property evaluation[END_REF][START_REF] Bée | Magnetic chitosan/clay beads: A magsorbent for the removal of cationic dye from water[END_REF], in data storage [START_REF] Frolov | Film carriers for super-high-density magnetic storage[END_REF], etc. Magnetite (Fe3O4) exhibits one of the largest saturation magnetizations among iron oxides (92 emu g -1 at room temperature [START_REF] Buschow | Handbook of Magnetic Materials[END_REF]). It has a face-centered cubic inverse spinel structure and differs from most other iron oxides since it contains both divalent and trivalent iron. Its formula can be written as FeA 3+ [Fe 2+ Fe 3+ ]BO4 where A and B denote tetrahedral and octahedral sites respectively [START_REF] Cornell | The Iron Oxides: Structure, Properties, Reactions, Occurrences and Uses[END_REF]. The iron ions in the octahedral sites make fast electron hopping leading to the averaged valence state of Fe 2.5+ . Below 120 K, magnetite undergoes a phase transition from cubic to monoclinic known as the Verwey transition and become an insulator as the electron hopping ceases to occur [START_REF] Verwey | Electronic conductivity and transition point of magnetite[END_REF]. The magnetic properties of iron oxides and magnetite in particular are also size-dependent [START_REF] Dormann | Magnetic Relaxation in Fine-Particle Systems[END_REF]. Large size magnetite crystals have multi-domain magnetic structure and become single domain as the size is reduced below 90 nm. The magnetic moment of the nanoparticles can undergo a spontaneous flip at room temperature as the size continues to decrease at around 30 nm. This gives rise to superparamagnetic characteristic [START_REF] Si | Size-Controlled Synthesis of Magnetite Nanoparticles in the Presence of Polyelectrolytes[END_REF].

Various synthesis routes have been developed for the preparation of nanostructured magnetite. The co-precipitation of Fe 2+ and Fe 3+ by a base is by far the most synthetic method reported in the literature [START_REF] Jolivet | Synthesis of iron oxide-based magnetic nanomaterials and composites[END_REF][START_REF] Sun | Size-Controlled Synthesis of Magnetite Nanoparticles[END_REF][START_REF] Forge | Optimization of the Synthesis of Superparamagnetic Contrast Agents by the Design of Experiments Method[END_REF][START_REF] Altan | The effect of Fe 3 O 4 nanoparticles on the thermal conductivities of various base fluids[END_REF][START_REF] Yazdani | Magnetite nanoparticles synthesized by co-precipitation method: The effects of various iron anions on specifications[END_REF]. An alternative consists in the oxidation-precipitation of ferrous salt in alkali aqueous solution but remains less used [START_REF] Sugimoto | Formation of uniform spherical magnetite particles by crystallization from ferrous hydroxide gels[END_REF][START_REF] Schwertmann | Iron Oxides in the Laboratory: Preparation and Characterization[END_REF][START_REF] Gu | Facile one-pot synthesis of multi-armed Fe3O4 nanocrystals[END_REF] or by reaction of iron oxhyhydroxydes with soluble Fe(II) [START_REF] Usman | FeII induced mineralogical transformations of ferric oxyhydroxides into magnetite of variable stoichiometry and morphology[END_REF]. Coating of the magnetite surface with organic and/or inorganic material molecules allows tuning structural and magnetic properties of magnetite [START_REF] Souza | Mesoporous silica-magnetite nanocomposite synthesized by using a neutral surfactant[END_REF][START_REF] Mikhaylova | Superparamagnetism of Magnetite Nanoparticles: Dependence on Surface Modification[END_REF][START_REF] Azevedo | Combining mesoporous silicamagnetite and thermally-sensitive polymers for applications in hyperthermia[END_REF]. More recently, the involvement of polysaccharides in magnetite synthesis has been promising at fabricating eco-friendly materials [START_REF] Paulino | Two-step synthesis and properties of a magnetic-field-sensitive modified maltodextrin-based hydrogel[END_REF][START_REF] Dou | The one-pot synthesis of dextran-based nanoparticles and their application in in-situ fabrication of dextran-magnetite nanocomposites[END_REF][START_REF] Hauser | The effects of synthesis method on the physical and chemical properties of dextran coated iron oxide nanoparticles[END_REF][START_REF] Daniel-Da-Silva | Biofunctionalized magnetic hydrogel nanospheres of magnetite and κcarrageenan[END_REF][START_REF] Unal | Synthesis, structural and conductivity characterization of alginic acid-Fe3O4 nanocomposite[END_REF][START_REF] Silva | Synthesis and characterization of Fe3O4 nanoparticles coated with fucan polysaccharides[END_REF][START_REF] Chang | Polysaccharides as stabilizers for the synthesis of magnetic nanoparticles[END_REF]. Starch emerges as one of the potential functionalization agents in magnetite synthesis due to its low-toxicity, abundance and cost-effectiveness [START_REF] Abdullah | A facile and green synthetic approach toward fabrication of starch-stabilized magnetite nanoparticles[END_REF][START_REF] Jiang | A novel magnetic fluid based on starch-coated magnetite nanoparticles functionalized with homing peptide[END_REF][START_REF] Zhang | XAFS study of starch-stabilized magnetite nanoparticles and surface speciation of arsenate[END_REF][START_REF] Tancredi | Polymer-assisted size control of water-dispersible iron oxide nanoparticles in range between 15 and 100 nm[END_REF][START_REF] Shingel | Polysaccharides for Drug Delivery and Pharmaceutical Applications[END_REF][START_REF] Kim | Starch-Coated Superparamagnetic Nanoparticles as MR Contrast Agents[END_REF]. The available researches have been primarily focused on the technological application aspects and little attention has been paid to understand the effect of such polysaccharide on the structural and magnetic properties of magnetite. This report presents the successful preparation of starch functionalized nanoparticles via the oxidation-precipitation method. Peculiar attention was paid to both structure and properties of magnetite particles synthetized with increasing amount of starch. Obtained products were carefully characterized by TEM, PXRD, Raman, FTIR spectroscopies, XPS and TGA. The progressive emergence of the superparamagnetic behaviours of the nanocomposite was probed by Mössbauer spectroscopy.

Materials and methods

Materials

Ferrous sulphate heptahydrate (FeSO4•7H2O), potassium hydroxide (KOH), potassium nitrate (KNO3), ethanol (96%) and soluble starch were obtained from Fischer Chemical, Riedel-de Haën, Merck, VWR and Sigma-Aldrich, respectively. All chemicals were analytical grade and used as received without further purification. Ultrapure water (18.2 MΩ cm -1 ) was used for the all experiments. Water was previously bubbled at least 1 hour with N2 prior to use.

Synthesis of magnetic nanoparticles (MNPs)

MNPs were prepared following the synthesis of magnetite (Fe3O4) by the oxidationprecipitation of ferrous sulphate method as reported by Schwertmann and Cornell [START_REF] Schwertmann | Iron Oxides in the Laboratory: Preparation and Characterization[END_REF].

Typically, 80 g of FeSO4•7H2O were dissolved in 560 mL purified water under magnetic stirring and N2 atmosphere in a 1 L flask and heated up to 90°C. When the temperature was reached, 240 mL of aqueous solution containing 6.46 g KNO3 and 44.90 g KOH were added dropwise to the reaction vessel (50 mL min -1 ) using a peristaltic pump. After the addition of the last drop, the mixture was heated for a further 45 minutes. Then, the mixture was cooled to room temperature overnight. The black precipitate was recovered by centrifugation, washed 5 times with water and then washed 1 time with ethanol (96%, from VWR) to remove the unreacted reagents. The resulting product was dried under vacuum.

The same procedure was used for the synthesis of starch functionalized MNPs (Starch@MNPs) except that starch was added to FeSO4 solution and gelatinized at 90°C before the addition of the KNO3 and KOH mixture solution. The starch to Fe mass ratio (R) was allowed to vary over the range between 0.05 and 10. The following steps remained the same. The obtained samples were labelled from R0.05 to R10, and the non-functionalized MNPs R0.

Materials characterization

The morphologies of the as-prepared products were analyzed using transmission electron microscopy (TEM) and high-resolution transmission electron microscopy (HRTEM) on a Philips CM200 and JEOL 2100F respectively operating both at an accelerating voltage of 200 kV. Samples were dispersed in an ethanol solution under sonication and evaporated at room temperature on a carbon-coated copper grid.

The identification of crystalline structure of the synthesized nanoparticles was performed by powder X-ray diffraction (PXRD) using a PANalytical X'Pert MDP diffractometer equipped with a Cu Kα radiation source and a rapid X'Celerator detector.

Raman spectra were recorded using a Jobin Yvon T64000 spectrometer equipped with a 532 nm laser through a ×50 microscope objective. The power of the laser was set to 600 mW.

To prevent the oxidation of the sample, the power of the laser beam was reduced by means of a series of neutral density filters. 57 Fe Mössbauer spectra were collected using a conventional spectrometer in transmission geometry coupled with a cold head cryostat from Advances Research Systems (USA), equipped with vibration isolation stand, developed in LCPME laboratory. The 50 mCi 57 Co in Rh matrix radioactive source was mounted in a constant acceleration velocity transducer.

Measurements were taken at the wide range of velocity ± 11 mm s -1 . The hyperfine interaction parameters were determined by fitting the experimental spectra by a least-squares method using the Recoil software [START_REF] Lagarec | Recoil -Mössbauer Spectral Analysis Software for Windows[END_REF]. The center shifts were reported with respect to that of 25 µm-thick α-Fe foil at room temperature.

Results and discussion

TEM

Morphological study of the as-prepared nanoparticles was carried out using TEM. Figure 1 shows examples of TEM and HRTEM micrographs and selected area electron diffraction (SAED) patterns of the R0 and R10 samples. As illustrated, on the one hand, R0 was composed mostly of cubic shape nanoparticles along with some minor hexagonal shape (figure 1(a) and (c)) in the wide size range of about 20 to 200 nm. The particle size obtained by oxidation-precipitation method were relatively high compared to the size obtained by co-precipitation which is around 10 to 40 nm [START_REF] Vayssières | Size Tailoring of Magnetite Particles Formed by Aqueous Precipitation: An Example of Thermodynamic Stability of Nanometric Oxide Particles[END_REF][START_REF] Kim | Synthesis and characterization of surfactant-coated superparamagnetic monodispersed iron oxide nanoparticles[END_REF][START_REF] Daou | Hydrothermal Synthesis of Monodisperse Magnetite Nanoparticles[END_REF].

The HRTEM micrograph (figure 1(c)) of the same sample revealed clearly parallel lattice fringes, indicating the high crystallinity of the nanoparticles. The measured inter-fringe distances of about 0.24 and 0.29 nm were consistent with cubic spinel iron oxides as discussed latter (see section 3.2) and can be assigned to the inter-planar distances of the ( 222) and (220) crystallographic planes of magnetite (JCPDS data 19-0629) respectively. Each grain constituting R0 appeared to be a single crystal (figure 1(c)) with smooth edges. The corresponding SAED of R0 (figure 1(e)) displays a spotty ring pattern characteristic of single crystal specimen present in few numbers and randomly oriented in the selector aperture [START_REF] Andrews | Interpretation of Electron Diffraction Patterns[END_REF].

The indexed rings were in good agreement with PXRD analyses discussed below. On the other hand, R10 may be assimilated as a big flake of starch containing nanoparticles dispersed inside (figure 1(b)). Two different objects may be distinguished: small nanoparticles of about 10 nm that can be seen on the clear part of the polymer matrix (area surrounded by square in figure 1(b)) and larger nanoparticles in the same order of size as in R0. Thorough observation of HRTEM micrograph (figure 1(d)) revealed the main difference of R10 in comparison with R0. When considering a fairly large grain in R10, it seems that it is constituted of nano-grains gathered in a cluster forming a polycrystalline specimen that contributes to the formation of continuous rings in the SAED pattern (figure 1(f)). Lattice fringes corresponding to the crystallographic planes (444), ( 531) and (222) (dhkl ~ 0.12, 0.14 and 0.24 nm respectively) characteristics of magnetite (JCPDS data 19-0629) were also identified. SAED pattern of R10 exhibited fewer rings in regard to R0 but the indexed rings remained consistent with the cubic spinel iron oxides and were in good agreement with PXRD results discussed below. The presence of starch affects then drastically the MNPs's morphology by the extinction of some diffraction rings but the cubic spinel order is maintained.

PXRD

The phases composing the as-synthesized product were identified by PXRD. Figure 2 shows the obtained diffractograms. Considering the diffraction pattern of R0, all the reflection peaks can be indexed within the cubic spinel structure of magnetite (JCPDS data n° 19-0629) corroborating the results of HRTEM and SAED mentioned above. Spinel structure of MNPs was essentially maintained for R0.31-10 samples as the diffraction peak positions remained unchanged. The presence of amorphous starch leads to an additional broad peak at 2θ range of 15-25° for samples with high R value (R5-10). Two peaks appeared at 2θ equals to 40.7 and 51.6° and may be ascribed tentatively to δ-FeOOH impurity. From the diffraction patterns, it was also observed a broadening trend of the reflection peaks with the increase of R value, indicating the reduction of the crystallite size of magnetite. The average crystallite sizes were estimated by applying Scherrer's formula (Equation ( 1)) [START_REF] Scherrer | Bestimmung der Größe und der inneren Struktur von Kolloidteilchen mittels Röntgenstrahlen[END_REF][START_REF] Suryanarayana | X-Ray Diffraction: A Practical Approach[END_REF] on the two most intense peaks (311) and (440) after Kα2 stripping using X'Pert Highscore Plus v2.2b software.

cos XRD r k d B λ θ = ( 1
)
where k is the shape factor and equals to 0.89 for spherical particles, λ is the wavelength of Cu-Kα1 radiation, θ is the diffraction angle and Br the geometric mean of the full width at half maximum (FWHM) of the observed peak B0 and the FWHM due to instrumental effects Bi (measured from the diffractogram of size and strain effect-free LaB6 standard):

2 2 0 0 ( ) ( ) r i i B B B B B = - - (2)
The average sizes of the crystallites (dXRD) of all samples are shown in figure 2 and were estimated to be 67 ± 5, 44 ± 4, 30 ± 10, 11 ± 2 and 12 ± 4 nm for R0, R0.31, R2, R5 and R10

respectively. The crystallite sizes showed a decreasing trend with the increase of R.

Interestingly, a limited amount of starch (R0.31) in the synthetic medium leads to abrupt drop of the crystallite size from 67 nm to 44 nm. This suggests that starch may serve as nucleation points, enhancing the number of small crystallites. At higher R further crystallite size reduction is observed. One may also suspect starch to induce defaults in magnetite structure, e.g. polymer chain embedment in oxide, contributing to lower the size of coherently diffracting domains. In the case of R0, the calculated dXRD was in fair agreement with TEM observations where the distribution curve indicates an average size of 80 ± 30 nm. For the R10, the estimation of grain size from TEM was difficult which justified the use of indirect technique like PXRD. By varying the value of R, one can successfully evolves the size of the MNPs.

It is worth noting that the structure of magnetite and maghemite are very similar. Hence, the discrimination of the two phases was not easy by mean of PXRD. The main difference lies in the low Bragg angle where few extra peaks are only present for the maghemite (JCPDS data 39-1346). The intensities of theses peaks are very weak that makes the identification of maghemite difficult. Further characterization by Raman or Mössbauer spectroscopies should be performed to distinguish the iron oxide phases as these latter exhibit distinct Raman active phonon modes and distinct hyperfine parameters.

Raman spectroscopy

Raman spectroscopy is a reliable technique which allows a discrimination among the different phases of iron oxides [START_REF] De Faria | Raman microspectroscopy of some iron oxides and oxyhydroxides[END_REF]. The Raman spectra of all samples are illustrated in figure 3. The main bands corresponding to A1g, T2g and Eg modes of magnetite were clearly evidenced for the sample R0 at 667, 540 and 307 cm -1 respectively. The band positions were in good agreement with literature values [START_REF] De Faria | Raman microspectroscopy of some iron oxides and oxyhydroxides[END_REF][START_REF] Shebanova | Raman spectroscopic study of magnetite (FeFe2O4): a new assignment for the vibrational spectrum[END_REF]. The weak T2g and Eg bands overlapped with starch characteristic bands in the range of 200-600 cm -1 when starch content exceeds R2. The band centered at 667 cm -1 widened as the ratio R increased which was indicative of particle size reduction induced effect or appearance of disorder [START_REF] Kumar | Raman Spectroscopy for Nanomaterials Characterization[END_REF] in accordance with the PXRD characterizations. The bands originating from starch were not well resolved and further characterization with FTIR and XPS were performed (see Supporting Information). Both The only change observed in starch FTIR fingerprint can be attributed to a slight modification of starch crystallinity. The Raman characterization provides evidence on the formation of magnetite as the main iron oxide phase by the synthesis method used in the present study regardless the perturbation induced by starch.

Mössbauer spectroscopy

Mossbauer spectroscopy has been used to investigate the structural together with magnetic properties of the as synthetized products. The Mössbauer spectra recorded at room temperature (RT) for different samples are shown in figure 4(a), and the corresponding hyperfine parameters in table 1. The MNPs sample R0 exhibits two narrow sextets. The outer sextet with CS = 0.28 mm s -1 , Heff = 48.8 T and small quadrupole shift (ε) was assigned to high spin Fe 3+ in tetrahedral site and the inner one with CS = 0.66 mm s -1 , Heff = 45.7 T and also a small ε to mixed valence Fe 2.5+ in octahedral site noted as S1 and S2 respectively. These values were in good agreement with results obtained for well-crystallized bulk magnetite [START_REF] Vandenberghe | Mössbauer characterization of iron oxides and (oxy)hydroxides: the present state of the art[END_REF] and corroborated the results obtained by Raman spectroscopy. From the relative area (RA) of S1 and S2, the deviation from ideal stoichiometry δ of magnetite (Fe3-δO4) was determined according to the recommendations of Zegeye et al [START_REF] Zegeye | In situ monitoring of lepidocrocite bioreduction and magnetite formation by reflection Mössbauer spectroscopy[END_REF]. The obtained δ value for R0 was equal to 0.02 indicating that the sample was very close to pristine magnetite, while a bit higher deviation from ideal stoichiometry δ = 0.06 was determined for R0.31. It has to be noticed that Lorentzian multiplet analysis model was used in recoil software [START_REF] Lagarec | Recoil -Mössbauer Spectral Analysis Software for Windows[END_REF] as a fitting procedure for the spectra of R0 and R0.31. In contrast, at higher value of R (1-10) the Mössbauer spectra become more complex, with the emergence of quadrupole doublet as well as the significant broadening of the sextets, suggesting a thermal relaxation effects [START_REF] Fock | On the interpretation of Mössbauer spectra of magnetic nanoparticles[END_REF]. The broadening of the sextet lines is thereby modelled by hyperfine field distributions (HFDs) and the Voig-based fitting (VBF) analysis was used to extract characteristic spectral parameters [START_REF] Lagarec | Recoil -Mössbauer Spectral Analysis Software for Windows[END_REF][START_REF] Rancourt | Voigt-based methods for arbitrary-shape static hyperfine parameter distributions in Mössbauer spectroscopy[END_REF]. The experimental spectra for samples R1 to R10 were fitted with one quadrupole doublet and 2

HFDs. The gradual evolution from a Lorentzian multiplet characterizing a long-range magnetic order (samples R(0-0.31)) to more complex spectra with superposition of broad sextet components and doublet in which long-range magnetic order is absent can be attributed to the dynamic effects resulting from the fluctuations in the local environment of the probe nucleus (i.e. Fe), such as those arising from superparamagnetism [START_REF] Rancourt | Mössbauer spectroscopy in clay science[END_REF]. It is known from the literature that when the MNPs size decreases below a certain value, the magnetic moment of such nanoparticles are subject of spontaneous flip and exhibit superparamagnetic behaviours [START_REF] Néel | Théorie du trainage magnetique des ferromagnetiques en grains fins avec applications aux terres cuites[END_REF]. The time constant of this process is the Néel relaxation time (τN):

0 B K V k T N e τ τ = (3)
where τ0 is a constant in the range of 10 -9 -10 -12 s depending on the material, K the magnetic anisotropy constant, V the particle volume, kB the Boltzmann's constant, and T the temperature. If τN becomes lower than the Mössbauer measurement time (τN < 10 -10 s) the magnetically split spectra collapse into one or two paramagnetic lines and in the intermediate range of relaxation times, the spectra present a very broad lines with gradual transition from a sextet to a doublet [START_REF] Fock | On the interpretation of Mössbauer spectra of magnetic nanoparticles[END_REF][START_REF] Rancourt | Mössbauer spectroscopy in clay science[END_REF]. In the present study, the shape of the Mössbauer spectra of R(1-10) suggests a broad distribution of particles sizes with different relaxation times. The quadrupole doublet may arise from the very small MNPs diluted in the starch matrix, and the broad sextets from bigger MNPs and/or aggregated very small MNPs with higher relaxation times corroborating the TEM observations of R10. The relative abundance of the doublet (RA(D)) gradually increases with starch amount from 10 to 36% for R1 to R10 respectively.

One can assume that in addition to the role of starch in the reduction of crystallites sizes, the latter can also allow to better disperse the MNPs. Also, the average hyperfine fields <Hhf> for S1 and S2 were reduced as the R value increases.

To better understand the dynamic magnetic behaviours of starch@MNPs, Mössbauer measurements at different temperatures were also performed. Figure 4(b-c) shows the evolution with temperature of the sample R10 spectrum. While the fitting procedure was the same as for RT for 145 and 75 K, at 9K five Lorentzian shaped sextets were used to reproduce the magnetic component as established for magnetite at low temperature where the structure is no longer cubic but monoclinic [START_REF] Srivastava | Mössbauer study of the low-temperature phase of magnetite[END_REF][START_REF] Hargrove | Mössbauer measurements of magnetite below the Verwey transition[END_REF][START_REF] Doriguetto | Characterization of a natural magnetite[END_REF] and one quadrupole doublet for the residual superparamagnetic contribution. The spectra for R1 at 15K is supplied for comparison (figure 4(c)).

It was shown that the spectra evolve gradually when the temperature decreases. The magnetic contribution increases progressively, while the relative abundance of the doublet decreases from 36 to 3% between RT and 9 K (figure S4, Supporting Information). This change could be connected to the reduction of the thermal relaxation effects. It indicates that we approach the blocking temperature TB where the magnetization of single domain particle is fixed along its easy axis, in a blocked state [START_REF] Mørup | Superparamagnetic relaxation of weakly interacting particles[END_REF]. As temperature increases, the magnetic moment will oscillate around the easy axis with larger amplitude as it gets warmer, until it starts to jump over the energy barrier between the two easy directions with relaxation time τN.

However, only dilute fine particle systems with a narrow distribution of particle sizes, where interparticle interactions can be considered absent, have spectra properly modelled. It consists of a sum of magnetic sextet and doublet with a temperature dependent area ratio resulting of superparamagnetic relaxation. The definition of TB which depends upon equal areas of sextet and doublet, is useful for such spectra [START_REF] Bødker | Magnetic properties of hematite nanoparticles[END_REF]. However, among the abundant literature of these decades on the dynamics of magnetics nanoparticles, van Lierop and Ryan [START_REF] Van Lierop | Mössbauer spectra of single-domain fine particle systems described using a multiple-level relaxation model for superparamagnets[END_REF] suggest a more robust definition of TB from a multilevel relaxation model. Concerning R10 with distribution of particle sizes, the simplest model fails and it becomes difficult to predict TB [START_REF] Fock | On the interpretation of Mössbauer spectra of magnetic nanoparticles[END_REF]. Similarly, RA(D) decreases with decreasing temperature for R1 and R2 samples (figure S4, Supporting Information) confirming that TB decreases with increasing R.

At very low temperature, the five sextet components can be attributed to Fe 3+ in one tetrahedral site and both Fe 3+ and Fe 2+ in octahedral sites. The presence of the prominent features, specifically the hyperfine parameters of the sextet S5 (high CS~1mm s -1 , high quadrupole shift 2ε>1 mm s -1 and low magnetic hyperfine field ~34 T) suggests the presence of Fe 2+ in octahedral sites and confirms the formation of magnetite which is not obvious at RT. To ensure this assumption, a 1,10-phenantroline assay has been done on the sample R10.

The formation of orange-red complex testifies the presence of Fe 2+ . By comparing the spectra of R10 and R1 at 9 and 15 K respectively, the spectrum of R10 appears to be broader. At these temperatures, the broadening from the thermal relaxation effects can be considered as negligible which allow us to assume that the broadening arises from the disorders in the atomic environment of iron atoms that is more important in R10. Then, starch highly influences the iron environments of magnetite.

Conclusion

We have successfully synthetized and in-situ functionalized magnetite with starch via an oxidation-precipitation of Fe(II) which constitutes an alternative way to the usual coprecipitation method. The effect of starch on the structural and magnetic properties of the as synthesized products has been extensively investigated using a wide range of characterization techniques. We evidenced that starch plays a significant role in the modification of magnetite properties compared to the non-functionalized bulk phase. TEM and XRD analyses revealed that small particles were obtained in the presence of starch and the size decreases with the quantity of starch expressed as the starch to iron mass ratio R. The crystallite size varies from 66 ± 5 nm for R0 to 12 ± 4 nm for R10. The formation of cubic spinel structure phases was confirmed by SAED, XRD and Mössbauer spectroscopy. Stoichiometric magnetite was found to be the main phase formed at low values of R, while oxidation and disorder accompanied particle size reduction at higher R values as evidenced by Raman and Mössbauer spectroscopy. The reduction of the crystallite size is also accompanied by the appearance of superparamagnetic behaviour supported by the presence of the doublet and the asymmetric broadening of the magnetic component in the Mössbauer spectra as the value of R increases.

The superparamagnetic doublet represents 10 % for R1 and increases up to 36 % for R10. The presence of starch leads also to the perturbation of the iron environments conducting to the distribution of the hyperfine fields of the spectra. FTIR and XPS fingerprints of starch in Starch@MNPs appear similar to those of native starch. Finally, we expect that the possibility to tailor magnetite properties with starch which can be also extended to other polymers opens up several possibilities of application for this type of nanomaterial. For this purpose, the use of starch@MPNs to recover pollutants from water are currently under investigation in our laboratory.

Figure 1 .

 1 Figure 1. TEM micrographs of R0 (a) and R10 (b); HRTEM micrographs of R0 (c) and R10 (d); SAED patterns of R0 (e) and R10 (f). The inset image in panel (a) refers to the particle sizes distribution fitted with Log-normal profile.

5 Figure 2 .

 52 Figure 2. PXRD patterns of the as-synthetized products at different R values; dXRD denotes the crystallite size calculated from Scherrer's formula in nm.

Figure 3 .

 3 Figure 3. Raman spectra of the as-synthesized products at different R values and native starch.

FTIR

  and XPS highlighted the success of functionalization. Starch contribution to FTIR or XPS spectra clearly increases with R (figures S1 and S2, Supporting Information). Both techniques evidenced that no chemical modification of starch took place during the synthesis.

Figure 4 .

 4 Figure 4. Mössbauer spectra of the as-synthetized products at different R values recorded at room temperature (a); Mössbauer spectra of R10 between room temperature and 75 K (b) and Mössbauer spectra of R10 and R1 at 9 K and 15 K, respectively (c).

Table 1 .

 1 Mossbauer hyperfine parameters for the as-synthetized products at different R values obtained after fitting the experimental data. shift relative to alpha-iron, Δ: quadrupole splitting of paramagnetic component, ε: quadrupole shift, Hhf: hyperfine field (average value in case of distribution <Hhf>), RA: relative abundance of each site and δ: deviation from stoichiometry.

	Sample	Site	CS (mm s -1 )	Δ or ε (mm s -1 )	Hhf or <Hhf> (T)	RA (%)	δ
	R0@RT	S1 S2	0.28 0.66	0.00 -0.01	48.8 45.7	38 62	0.02
	R0.31@RT	S1 S2	0.29 0.66	0.00 -0.01	48.8 45.7	44 56	0.06
	R1@RT	D S1	0.36 0.28	0.70 0.00	-45.9	10 40
		S2	0.65	0.00	38.5	50
		S1	0.43	-0.06	50.5	33
	R1@15K	S2 S3	0.56 0.47	-0.02 0.15	53.0 50.9	24 21
		S4	0.76	-0.14	46.6	20
		S5	0.90	0.70	33.7	2
	R2@RT	D S1	0.36 0.28	0.69 0.03	-45.3	15 35
		S2	0.51	-0.10	36.9	50
	R5@RT	D S1	0.35 0.28	0.70 0.01	-44.4	17 24
		S2	0.56	-0.04	35.1	59
	R10@RT	D S1	0.35 0.29	0.69 -0.01	-41.7	36 29
		S2	0.68	-0.06	26.3	35
	R10@145K	D S1	0.41 0.36	0.73 0.02	-44.7	25 37
		S2	0.68	-0.03	33.7	39
	R10@75K	D S1	0.37 0.34	0.74 0.03	-44.1	13 55
		S2	0.59	-0.04	36.4	32
		D	0.40	1.00	-	3
		S1	0.45	-0.08	49.9	31
	R10@9K	S2 S3	0.49 0.55	0.01 0.16	52.7 49.5	29 10
		S4	0.56	-0.03	45.1	25
		S5	0.90	1.00	34.0	2
	CS: center

Acknowledgements

The authors would like to thank Corine Bouillet (IPCMS-Starsbourg), Sylvie Migot (IJL-Nancy) and Jaafar Ghanbaja (IJL-Nancy) for TEM imaging; Ghouti Medjahdi (IJL-Nancy) and Pierrick Durand (CRM2-Nancy) for PXRD characterizations and Aurélien Renard (LCPME-Nancy) for XPS analyses .