Carolina Medina

Jorge Luis

Ramírez Alfonsín
email: jorge.ramirez-alfonsin@univ-montp2.fr

Gelasio

Jorge Ram

Írez-Alfons Ín

Gelasio Salazar
email: gsalazar@ifisica.uaslp.mx

The unavoidable arrangements of pseudocircles

published or not. The documents may come

Introduction

A seminal result by Erdős and Szekeres [START_REF] Erdös | A combinatorial problem in geometry[END_REF] states that for every fixed integer k ≥ 3, every sufficiently large set of points in general position in R 2 contains k points in convex position, that is, k points that are the vertices of a convex k-gon. In the dual setting, a set (or arrangement) of lines in R 2 is in general position if no two are parallel, and no three lines intersect at a common point. An arrangement of k lines is in in convex position if one of its cells is bounded by a k-gon, which necessarily contains a segment from each of the k lines. The dual version of the Erdős-Szekeres theorem for lines is that for every fixed k ≥ 3, every sufficiently large arrangement of lines in general position contains k lines in convex position (see [START_REF] Bárány | Erdős-Szekeres theorem for lines[END_REF]).

It must be noted that the point and line versions of the Erdős-Szekeres theorem are not dual to each other in R 2 , but they are so in the projective plane RP 2 . A pseudoline is a noncontractible simple closed curve in RP 2 . An arrangement of pseudolines is a set of pseudolines that cross each other exactly once. An arrangement of pseudolines is simple if no three pseudolines have a common point. Two arrangements of pseudolines are isomorphic if the cell complexes they induce in RP 2 are isomorphic.

A simple arrangement of pseudolines is cyclic if its pseudolines can be labelled 1, 2, . . . , m, so that each pseudoline i ∈ [m] intersects the pseudolines in {1, 2, . . . , m}\{i} in increasing order (see Figure 1). Cyclic arrangements of pseudolines have a cell whose boundary contains a segment from each pseudoline, and so they are the natural counterpart in RP 2 to arrangements of lines in convex position in R 2 . The following statement is the version of the Erdős-Szekeres theorem for simple arrangements of pseudolines. In the spirit of [START_REF] Pach | Unavoidable configurations in complete topological graphs[END_REF], this shows that cyclic arrangements are the only unavoidable arrangements of pseudolines.

Theorem 1 ( [START_REF] Harborth | The Esther Klein problem in the projective plane[END_REF][START_REF] Negami | Ramsey theorems for knots, links and spatial graphs[END_REF]). For each fixed m ≥ 1, every sufficiently large simple arrangement of pseudolines has a cyclic subarrangement of size m.

We prove an analogue of Theorem 1 for arrangements of pseudocircles. A pseudocircle is a simple closed curve in the sphere S 2 . We use Grünbaum's original notion that an arrangement of pseudocircles is a set of pseudocircles that pairwise intersect at exactly two points, at which they cross, and no three pseudocircles have a common point [START_REF] Grünbaum | Arrangements and spreads[END_REF]. This notion is still adopted nowadays [START_REF] Ortner | Embeddability of arrangements of pseudocircles into the sphere[END_REF], and some more general notions are also used in the literature [START_REF] Felsner | Arrangements of pseudocircles: On circularizability[END_REF][START_REF] Kang | Arrangements of pseudocircles and circles[END_REF]. Two arrangements of pseudocircles are isomorphic if the cell complexes they induce in S 2 are isomorphic.

In Figure 2 we illustrate three arrangements C

≤ n, all subarrangements of C 1 n (respectively, C 2 n , C 3 n ) of size m are isomorphic to C 1 m (respectively, C 2 m , C 3 m ).
Thus it is accurate to say that these are (up to isomorphism) the unavoidable arrangements of pseudocircles.

We now give a formal description of the arrangements C 1 m , C 2 m , and C 3 m for every m ≥ 1. The pseudocircles of C 1 m are labelled 1, 2, . . . , m, and pseudocircle i is the unit radius disk centered at ((4/5) cos (2πi/m), (4/5) sin (2πi/m)). The pseudocircles of C 2 m are labelled 1, 2, . . . , m, and pseudocircle i is the unit radius disk centered at ((2i -1)/m, 0). The pseudocircles of C 3 m are labelled 1, 2, . . . , m, and pseudocircle i is the axis-parallel 6-gon with vertices (-i, -i), (-i, i), (2i-1, i), (2i-1, m+1), (2i, m+1), and (2i, -i). For good measure, in order to verify the accuracy of these descriptions, we did not prepare the depictions in Figure 2 "by hand", but with the vector graphics drawing program TikZ [START_REF] Tantau | The TikZ and PGF Packages[END_REF], using these prescriptions with m = 5.

For the rest of the paper, for brevity we refer to an arrangement of pseudocircles simply as an arrangement.

Reducing Theorem 2 to two kinds of arrangements

There are, up to isomorphism, only two arrangements of size 3. Following [START_REF] Felsner | Arrangements of pseudocircles: On circularizability[END_REF], these are the Krupp arrangement and the NonKrupp arrangement. We refer the reader to Figure 3. Note that the Krupp arrangement is isomorphic to C 1 3 , and the NonKrupp arrangement is isomorphic to C 2 3 and C 3 3 . If an arrangement P of size at least 3 has all its 3-subarrangements isomorphic to the Krupp arrangement (respectively, to the NonKrupp arrangement), then we say that P is Krupp-packed (respectively, NonKrupp-packed). We now state Theorem 2 for Krupp-packed and for NonKrupp-packed arrangements. As we shall see shortly, the general version of Theorem 2 easily follows as a consequence. We use Ramsey theory in our arguments. We recall that the order of a hypergraph is its number of vertices, and r k ( 1 , 2 , . . . , n ) denotes the Ramsey number for complete kuniform hypergraphs. That is, if each k-edge of a complete k-uniform hypergraph of order at least r k ( 1 , 2 , . . . , n ) has colour i for some i ∈ [n], then there is an i ∈ [n] and a complete subhypergraph of order i , all of whose k-edges have colour i.

Proof of Theorem 2, assuming Lemmas 3 and 4. Let m ≥ 1 be a fixed integer. Assuming Lemmas 3 and 4, it follows that there is an integer p such that every Krupp-packed or NonKrupp-packed arrangement of size at least p has a subarrangement isomorphic to

C 1 m , C 2 m , or C 3 m .
Let Q be an arrangement of size q = r 3 (p, p). Regard Q as a complete 3-uniform hypergraph, and colour a 3-edge blue (respectively, red) if the pseudocircles in the 3-edge form an arrangement isomorphic to the Krupp arrangement (respectively, to the NonKrupp arrangement).

Since q = r 3 (p, p) it follows from Ramsey's theorem that Q has a subarrangement P of size p that is either Krupp-packed or NonKrupp-packed. The assumption on p implies that P, and hence Q, contains a subarrangement isomorphic to C 1 m , C 2 m , or C 3 m . We finish this section by proving Lemma 3. The rest of the paper is devoted to the proof of Lemma 4.

The key fact we use in the proof of Lemma 3 is the bijection between simple arrangements of pseudolines and Krupp-packed arrangements (which are known in the literature as arrangements of great pseudocircles). This correspondence makes use of the wiring diagram representation of an arrangement of pseudolines [START_REF] Felsner | Pseudoline arrangements[END_REF][START_REF] Goodman | Proof of a conjecture of Burr, Grünbaum, and Sloane[END_REF]. We now proceed to recall this bijection. For further details we refer the reader to the lively description in [START_REF] Felsner | Hamiltonicity and colorings of arrangement graphs[END_REF]Section 2.3].

Let L be an arrangement of n pseudolines. Construct a wiring diagram representation W of L , drawing W inside a rectangle R, so that flipping R around its horizontal symmetry axis takes wire endpoints to wire endpoints. We refer the reader to Figure 4(a) for an illustration. Now let W be the wiring diagram obtained by flipping R along its horizontal symmetry axis (Figure 4(b)). We identify the right wire endpoints of W with the left wire endpoints of W , obtaining a diagram W whose n wires pairwise cross in exactly two points. In our running illustration, W is enclosed in the dotted rectangle of Figure 4(c).

The obtained diagram W is a wiring diagram representation of an arrangement of pseudocircles P. The arrangement P is obtained by joining with an arc the two endpoints of each wire in W , as illustrated in Figure 4(c). In this way the simple arrangement of pseudolines L induces the arrangement of pseudocircles P, and it is easy to check that P is Krupp-packed. Moreover (this the nontrivial direction of the bijection), every Krupp-packed arrangement of pseudocircles is isomorphic to an arrangement of pseudocircles induced in this manner by a simple arrangement of pseudolines (see [START_REF] Felsner | Arrangements of pseudocircles: On circularizability[END_REF]Section 3.2], or [17, Section 6.1.4]). Proof of Lemma 3. Let m ≥ 1 be a fixed integer. Let P be a Krupp-packed arrangement of size p := r 3 (m, m), and let S be a simple arrangement of pseudolines that induces P. Since p = r 3 (m, m), then by [START_REF] Ramírez-Alfonsín | Spatial graphs, knots and the cyclic polytope[END_REF]Proposition 1.4] it follows that S has a cyclic subarrangement L of size m. It is readily verified that if an arrangement of pseudocircles is induced by a cyclic arrangement of pseudolines of size m, then it is isomorphic to C 1 m . From this it follows that the subarrangement of P induced by the pseudolines in L is isomorphic to C 1 m .

Intersection codes

In the proof of Lemma 4 we use intersection codes, as developed in [START_REF] Linhart | On the combinatorial structure of arrangements of oriented pseudocircles[END_REF][START_REF] Ortner | Embeddability of arrangements of pseudocircles into the sphere[END_REF]. This framework, in which one naturally encodes combinatorially essential information of an arrangement, can be seen as a generalization of the axiomatization of oriented matroids based on hyperline sequences [START_REF] Bokowski | Oriented matroids[END_REF], and its essence goes back to the work of Gauss on planar curves in the 1830s.

Let P = {1, . . . , n} be an arrangement. For each i ∈ P choose a reference point p i not contained in any other pseudocircle, and also choose one of the two possible orientations for i, so that for each pseudocircle we can naturally speak of a left side and a right side. Suppose that as we traverse i starting at p i following the chosen orientation, we intersect j from the left (respectively, right) side of j. We record this by writing j + (respectively, j -).

By keeping track of the order in which the intersections occur, we obtain the code of i in P. Thus the code of each i is a permutation of j∈[n]\{i} {j + , j -}. If we omit the superscripts + and -, we obtain the unsigned code of i.

For instance, suppose that P is C 2 5 in Figure 2. Choose the counterclockwise orientation for each pseudocircle. If we choose as reference point for 3 its leftmost point, then its code is 1 + 2 + 4 -5 -5 + 4 + 2 -1 -, and its unsigned code is 12455421.

We make essential use of the following.

Proposition 5 ([12, Section 3],[14, Section 2]). Let P, Q be arrangements, both of which have their pseudocircles labelled 1, 2, . . . , n, where an orientation and a reference point has been chosen for each pseudocircle in P and each pseudocircle in Q. Suppose that for each i ∈ [n], the code of i in P is the same as the code of i in Q. Then P and Q are isomorphic.

We now introduce some notation to describe the codes of C 2 m and C 3 m in a compact manner. Let i, m be integers such that 1 ≤ i ≤ m. We use [1

+ :i + ) to denote the string 1 + 2 + • • • (i-1) + .
In a similar spirit, we use (i

-:1 -] to denote (i -1) -(i -2) -• • • 1 -; we use (i -:m -] to denote (i + 1) -(i + 2) -• • • m -; and we use [m + :i + ) to denote m + • • • (i + 2) + (i + 1) + . Finally, we use [1 + 1 -:i + i -) to denote 1 + 1 -2 + 2 -• • • (i-1) + (i-1) -. Note that [1 + :1 + ), (1 -:1 -], [1 + 1 -:1 + 1 -), (m -:m -],
i ∈ [m], the code of pseudocircle i in C 2 m is [1 + :i + )(i -:m -] [m + :i + ) (i -:1 -]. Observation 7.
Orient all pseudocircles 1, 2, . . . , m of C 3 m clockwise, and for each pseudocircle choose as reference point its bottom right corner. Then the code of each i in

C 3 m is [1 + 1 -:i + i -)(i -:m -][m + :i + ).
We close this section with a remark on NonKrupp-packed arrangements. We say that an arrangement is bad if its pseudocircles can be labelled 1, . . . , n so that with a reference point p i for i = 1, . . . , n, the following holds. For each pseudocircle i = 1, 2, . . . , n -2, the unsigned code of i in the subarrangement {i, i + 1, . . . , n} is (i + 1)(i + 1)(i + 2)(i + 2) • • • nn. Up to isomorphism, there is only one bad NonKrupp-packed arrangement of size 4, namely the arrangement X 4 shown in Figure 5. This is easily checked by hand, or by an inspection of [7, Figure 2], which contains all arrangements of size 4. In a bad NonKrupp-packed arrangement of size 5, all 4-subarrangements would then be isomorphic to X 4 . A routine case analysis by hand shows that no arrangement of size 5 satisfies this property. We highlight this remark, as we use it in the proof of Lemma 4. Observation 8. There is no bad NonKrupp-packed arrangement of size 5 (or larger).

Proof of Lemma 4

First we identify a property shared by C 2 m and C 3 m . To motivate this, we refer the reader to C 2 5 and C 3 5 , shown in Figure 2. If we perform the relabelling i → i-1 to the pseudocircles in either of these arrangements, the parts of 1, 2, 3, 4 in one component of S 2 \{0} are pairwise disjoint, and appear in a rainbow-like fashion: the unsigned code of 0 is 12344321. We say that an arrangement is rainbow if its pseudocircles can be labelled 0, 1, . . . , n so that (I) one of the components of S 2 \ {0} contains no intersections among the pseudocircles 1, 2, . . . , n; and (II) the unsigned code of pseudocircle 0 is 12

• • • nn • • • 21.
Lemma 4 follows easily from the next two statements.

Proposition 9. For each fixed integer n ≥ 5, every sufficiently large NonKrupp-packed arrangement has a rainbow subarrangement of size n.

Proposition 10. For each fixed integer m ≥ 5, every sufficiently large NonKrupp-packed rainbow arrangement contains a subarrangement isomorphic to C 2 m or C 3 m . Before proving these propositions, for completeness we give the proof of Lemma 4.

Proof of Lemma 4, assuming Propositions 9 and 10. Obviously it suffices to prove Theorem 2 for every integer m ≥ 5. Let m ≥ 5 be a fixed integer. By Proposition 10, there is an integer n := n(m) such that every NonKrupp-packed rainbow arrangement contains a subarrangement isomorphic to C 2 m or C 3 m . By Proposition 9, there is an integer q := q(n) such that every NonKrupp-packed arrangement has a rainbow subarrangement of size n. Thus every NonKrupp-packed arrangement of size at least q contains a subarrangement isomorphic to C 2 m or C 3 m . Proof of Proposition 9. Let n ≥ 5 be a fixed integer. Let p := r 3 (n, n)+1 and q := r 3 (p, p, p, p). We let Q = {1, . . . , q} be a NonKrupp-packed arrangement, and show that Q contains a rainbow subarrangement of size n.

Choose an arbitrary reference point and orientation for each pseudocircle in Q. The NonKrupp-packedness of Q implies that if j, k, are pseudocircles in Q such that j < k < , then the unsigned code of j in the subarrangement {j, k, } is either (i) kk ; or (ii) kk; or (iii) k k; or (iv) kk .

Regard Q as a complete 3-uniform hypergraph, and assign to each 3-edge {j, k, } with j<k< the colour (i), (ii), (iii), or (iv), depending on which of these scenarios holds. By Ramsey's theorem, Q has a subarrangement P = {1 , 2 , . . . , p }, with 1 ≤ 1 < • • • < p ≤ q, all of whose 3-edges are of the same colour.

Suppose that all 3-edges of P are of colour (i). Then for each i = 1, . . . , p-2, the unsigned code of i in the subarrangement {i , (i + 1) , . . . , p } is (i + 1) (i + 1) • • • p p . Thus P is a bad arrangement of size p > 5, contradicting Observation 8. Thus not all 3-edges of P can be of colour (i). An analogous argument shows that not all 3-edges can be of colour (ii).

If all 3-edges of P are of colour (iv) then by relabelling the pseudocircles in the reverse order we obtain an arrangement in which all 3-edges are of colour (iii). Thus we may assume that all 3-edges of P are of colour (iii). In particular, the unsigned code of 1 in {1 , . . . , p } is 2 3

• • • p p • • • 3 2 . Using that p -1 = r 2 (n, n),
an application of Ramsey's theorem shows that there exist i 1 , i 2 , . . . , i n , with 2 ≤ i 1 < i 2 • • • < i n ≤ p such that one of the connected components of S 2 \ {1 } contains no intersections among the pseudocircles i 1 , . . . , i n . The arrangement {1 , i 1 , . . . , i n } is rainbow. To see this, it suffices to relabel 1 with 0, and i j with j, for each j = 1, . . . , n.

Proof of Proposition 10. Let m ≥ 5 be a fixed integer. Let q = r 3 (m, m, m), and n = r 3 (q, q). Let N 0 = {0, 1, 2, . . . , n} be a NonKrupp-packed rainbow arrangement. We show that N 0 contains a subarrangement isomorphic to either C 2 m or to C 3 m . Our first goal is to show that we may assume that the layout of N 0 is as shown on the right hand side of Figure 6. To achieve this, first we note that by performing a self-homeomorphism of the sphere we may assume that the pseudocircle 0 is the union of the Greenwich Meridian and the 180th Meridian, in particular passing through the north pole N and the south pole S. We orient 0 in the direction from S to N following the Greenwich Meridian, as on the left hand side of Figure 6. On the left hand side we illustrate pseudocircle 0. On the right hand side we illustrate the eastern hemisphere, which contains all intersections among the pseudocircles 1, . . . , n. We illustrate the regions N k (grey) and S k (white) of pseudocircle k.

Since N 0 satisfies rainbowness Property (II), we may assume that as we traverse the Greenwich Meridian from S to N we intersect the pseudocircles 1, 2, . . . , n in this order, and as we traverse the 180th Meridian from N to S, we intersect them in the order n, . . . , 2, 1. Since N 0 satisfies rainbowness Property (I), then either the eastern or the western hemisphere (say the eastern one) contains all the intersections among the pseudocircles in N := {1, 2, . . . , n}. We orient all pseudocircles in N so that as we traverse 0 along the Greenwich Meridian from S to N the code we obtain is 1 -2 -• • • n -(that is, these pseudocircles hit 0 from its left hand side). Thus as we traverse the 180th Meridian from N to S the code is n + (n -1) + • • • 1 + . Each pseudocircle k ∈ N decomposes the eastern hemisphere into two parts, a part N k that contains N, and a part S k that contains S. Thus the setup is as illustrated in Figure 6.

Since N is NonKrupp-packed, for any three pseudocircles j, k, in N , either both intersections of j and occur in N k , or they both occur in S k . Regard N as a complete 3-uniform hypergraph, and assign to a 3-edge {j, k, } with j<k< the colour N (respectively, S) if the intersections of j and lie on N k (respectively, S k ). Since |N | = n = r 3 (q, q), then by Ramsey's theorem N has a subarrangement Q = {1 , 2 , . . . , q } of size q, with 1 <2 < • • • <q , all of whose 3-edges are of the same colour. By symmetry we may assume that all 3-edges of Q have colour N . To avoid unnecessary cluttered notation, we relabel the pseudocircles in Q as 1, 2, . . . , q.

Let j, k, be such that 1 ≤ j<k< ≤ q. Since the intersections between j and occur in N k , that is, above k, and Q is NonKrupp-packed, then there are only three possibilities for how j and can intersect each other, namely as shown in Figure 7(a), (b), and (c). Thus the code of k in {j, k, } is either (1) j + -+ j -, or (2) j + j --+ , or (3) -+ j + j -, respectively. Regard Q as a complete 3-uniform hypergraph. We assign to a 3-edge {j, k, } with j<k< a colour in {1, 2, 3}, depending, respectively, on which one of ( 1), [START_REF] Bokowski | Oriented matroids[END_REF], and (3) gives the code of k in {j, k, }. Since q = r 3 (m, m, m), by Ramsey's theorem Q has a subarrangement M = {1 , 2 , . . . , m }, where 1 <2 < • • • <m , all of whose 3-edges are of the same colour. If all the 3-edges are of colour 3, then by changing the traversal directions of all pseudocircles and inverting the crossing-sign convention we obtain that all the 3-edges become of colour 2. Thus we may assume that either all the 3-edges are of colour 1, or they are all of colour 2. Again, to avoid unnecessary cluttered notation we relabel the pseudocircles in M with 1, 2, . . . , m.

Suppose first that all the 3-edges of M are of colour 1. Then for each 1≤j<k< ≤m, the situation is as in Figure 7(a). Thus (i) the code of j in {j, k, } is k --+ k + ; (ii) the code of k in {j, k, } is j + -+ j -; and (iii) the code of in {j, k, } is j + k + k -j -. We first analyze the code of each pseudocircle i ∈ {2, 3, . . . , m-1}. By (i), the code of i in M contains the subpermutation (i -:m -][m + :i + ); by (iii), this code contains the subpermutation [1 + :i + )(i -:1 -]; and by (ii), it contains the subpermutation (i -1) + (i + 1) -(i + 1) + (i -1) -. These three conditions hold only if the code of i is [1

+ :i + )(i -:m -][m + :i + ) (i -:1 -].
We now analyze the codes of pseudocircles 1 and m. By (i), the code of

1 in M is (1 -:m -][m + :1 + ) = [1 + :1 + )(1 -:m -][m + :1 + )(1 -:1 -] (since [1 + :1 + ) and (1 -:1 -] are empty strings). Finally, by (iii), the code of m in M is [1 + :m + )(m -:1 -] = [1 + :m + ) (m -:m -] [m + :m + ) (m -:1 -] (since (m -:m -]
and [m + :m) are empty strings). We conclude that the code of every i ∈ M is [1

+ :i + )(i -:m -] [m + :i + )(i -:1 -]
. By Proposition 5 and Observation 6, then M is isomorphic to C 2 m . Suppose finally that all the 3-edges of M have colour 2. Then for each 1≤j<k< ≤m, the situation is as in Figure 7

(b). Thus (i) the code of j in {j, k, } is k --+ k + ; (ii) the code of k in {j, k, } is j + j --+ ; and (iii) the code of in {j, k, } is j + j -k + k -.
We first analyze the code of each pseudocircle i ∈ {2, 3, . . . , m-1}. By (i), the code of i in M contains the subpermutation (i -:m -][m + :i + ); by (iii), this code contains the subpermutation [1 + 1 -:i + i -); and by (ii), it contains the subpermutation (i -1) + (i -1) -(i + 1) -(i + 1) + . These three conditions hold only if the code of i is [1 + 1 -:i + i -) (i -:m -][m + :i + ).

We now analyze the codes of 1 and m. By (i), the code of 1 in M is (1 -:m -][m + :1 + ) = [1 + 1 -:1 + 1 -)(1 -:m -][m + :1 + ) (since [1 + 1 -:1 + 1 -) is an empty string). Finally, by (iii), the code of m in M is [1 + 1 -:m + m -) = [1 + 1 -:m + m -)(m -:m -][m + :m + ) (since (m -:m -] and [m + :m + ) are empty strings). We conclude that the code of every i ∈ M is [1 + 1 -:i + i -)(i -:m -] [m + :i + ). By Proposition 5 and Observation 7, then M is isomorphic to C 3 m .

Open questions

To prove Theorem 2 we make repeated use of Ramsey's theorem, and so an explicit bound for this theorem, derived from our proofs, would be multiply exponential. With additional effort (and considerably more space) we can save several applications of Ramsey's theorem, and show that for each fixed m ≥ 1, every arrangement of pseudocircles of size at least 2 2 cm 2 contains a subarrangement isomorphic to C 1 m , C 2 m , or C 3 m . This bound is still doubly exponential in m. What is the best explicit bound that can be proved for this theorem?

We now include two questions that were brought to our attention by a reviewer. Let us say that a k-arrangement of pseudocircles is a collection of pseudocircles that pairwise cross at exactly k points. With this terminology, the main result in this paper is that 2arrangements of pseudocircles have three unavoidable arrangements. Which are the unavoidable k-arrangements of pseudocircles? How does the number of unavoidable k-arrangements of pseudocircles increase with k?

In this mindset, we finally add a question of our own, which may be regarded as a warm-up to the questions in the previous paragraph. Is it obvious, or (this seems more likely) at least reasonably easy to prove, that for each fixed (even) integer k ≥ 2 the set of unavoidable k-arrangements of pseudocircles is finite?

Figure 1 .

 1 Figure 1. A cyclic arrangement of five pseudolines. 2010 Mathematics Subject Classification. Primary 52C30; Secondary 05C10, 52C40.

1

 1

Figure 3 .

 3 Figure 3. The Krupp arrangement (left) and the NonKrupp arrangement (right).

Lemma 3 .

 3 Theorem 2 holds for Krupp-packed arrangements.

Lemma 4 .

 4 Theorem 2 holds for NonKrupp-packed arrangements.

Figure 4 .

 4 Figure 4. A cyclic arrangement of 5 pseudolines (shown in its wiring diagram representation) induces an arrangement of pseudocircles isomorphic to C 1 5 .

Observation 6 .

 6 and [m + :m + ) are all empty strings. Using this terminology, based on the descriptions of the arrangements C 2 m and C 3 m in Section 1, we have the following. Orient all pseudocircles 1, 2, . . . , m of C 2 m counterclockwise, and for each pseudocircle choose as reference point its leftmost point. Then for each

Figure 5 .

 5 Figure 5. The arrangement X 4 .

Figure 6 .

 6 Figure 6. Initial setup in the proof of Proposition 10. On the left hand side we illustrate pseudocircle 0. On the right hand side we illustrate the eastern hemisphere, which contains all intersections among the pseudocircles 1, . . . , n. We illustrate the regions N k (grey) and S k (white) of pseudocircle k.

Figure 7 .

 7 Figure 7. Illustration of the proof of Proposition 10.

  Theorem 2. For each fixed m ≥ 1, every sufficiently large arrangement of pseudocircles has a subarrangement isomorphic to C 1 m , C 2 m , or C 3 m .

	them to arrangements C 1 m , C 2	1 5 , C 2 5 , C 3 5 , and it is clear how to generalize
		1	2	3	4	5
	1
	2
	5	1 2 3 4 5
	3
	4
	Figure 2. The arrangements C 1 5 (left), C 2 5 (center), and C 3 5 (right).
	We note that Theorem 2 is best possible, as no other type of arrangement of pseudocircles
	can be added to the collection {C 1 m , C 2

m , and C 3 m of size m, for any m ≥ 1 (we describe formally these arrangements below). These are the unavoidable arrangements of pseudocircles. m , C 3 m }. This follows since for all integers m, n with m

Acknowledgements

We thank an anonymous referee for corrections and substantial suggestions that improved the content and presentation of this paper. We thank Stefan Felsner and Manfred Scheucher for making available to us their software to generate all arrangements of pseudocircles of small order; experimenting with this code was very useful at the early stages of this project. The first author was supported by Fordecyt grant 265667. The second author is partially supported by PICS07848 grant. The third author was supported by Conacyt grant 222667 and by FRC-UASLP.


Roland Triay

Henri-Hugues Fliche

Voids in the distribution of galaxies and the Cosmological constant

With the motivation in mind to evaluate the contribution of the cosmological constant Λ on the foam like patterns formation process in the distribution of galaxies, we investigate the Newtonian dynamics of a spherical void embedded in an uniform medium which undergoes a Hubble expansion. We use a covariant approach for deriving the evolution with time of the shell (S) acting as a boundaries condition for the inside and outside media. As a result, with the usual values for the cosmological parameters, S expands with a huge initial burst that freezes up to matching Hubble flow. With respect to Friedmann comoving frame, its magnification increases nonlinearly with Λ, with a maximal growth rate at redshift z ∼ 1.7. The velocity field inside S shows an interesting feature which enables us to disentangle a spatially closed from open universe. Namely, the void region are swept out in the first case, what can be interpreted as a stability criterion.

§1. Introduction

The understanding of the foam like patterns with large empty regions in the distribution of galaxies 1)-4) has become an important challenge for the formation theory of cosmological structures. 5) Our motivation for understanding the dynamics of a single empty void in an expanding universe is twofold. According to Schwarzschild solution, the cosmological constant Λ that is required for the interpretation of high redshift data makes repulsive the gravity at a given critical distance, 6) what forces us to understand the underlying effect on the dynamics of voids since it does not limit solely to a pure chronological effect as in a Friedmann model. Additionally, the usual approaches based on gravitational collapse of density excess in which perturbations theory can be successfully applied from Zeldovich's approximation 7) are not valid for voids because they never evolve within a linear regime, 8) what motivates us to look for exact solutions. We limit our investigation to a newtonian approach [START_REF] Triay | Relat. & Gravit[END_REF] as a first step of a more general N-bodies treatment, although the related results must be interpreted with care when cosmological distances are involved. [START_REF] Triay | Proceedings of the XIIth Brazilian School of Cosmology and Gravitation[END_REF] Relativistic treatments of an analogous problem (an empty bubble as singularity) have been performed 11)-15) but with a different aim. §2. A void model in an expanding universe For the investigation of structures formation in an isotropic expanding medium, instead of position r = a x, it is convenient to use reference coordinates (t, x) related to the expansion factor a = a(t); let us choose a normalization condition at a given date a • = a(t • ) = 1. Hence, the density ρ = ρ( r, t) and velocity fields v = v( r, t) of the cosmic fluid translate in the appropriated reference frame by

ρ c = ρa 3 , v c = d x dt = 1 a ( v -H r) , H = ȧ a (2 . 1)
According to the standard world model, we assume that the gravitational sources behave as dust. The motions of such a pressureless medium are constraint by Euler-Poisson-Newton (EPN) equations system. For accounting of the cosmological expansion, the function a(t) must verify a Friedmann type equation

H 2 = Λ 3 - K • a 2 + 8πG 3 ρ • a 3 ≥ 0, K • = 8πG 3 ρ • + Λ 3 -H 2 • (2 . 2)
what depends on two parameters chosen among Λ, ρ • and K • (which stands for an integration constant in Friedmann differential equation). It is important to mention that at this step, excepted G and Λ, these variables stand merely for a coordinates choice. The formal expression t → a is derived as reciprocal mapping of a quadrature from eq. (2 . 2), what gives the reference frame chronology. It turns out that EPN equations system shows two trivial solutions : 1. Newton-Friedmann (NF) solution, defined by ρ c = ρ • and v c = 0, which accounts for a uniform distribution of dust. According to eq. (2 . 1,2 . 2), a and H recover now their usual interpretations in cosmology as expansion parameter and Hubble parameter respectively, ρ • = ρa 3 identifies to the density of sources in the comoving space and K • interprets in GR as its scalar curvature * ) , k

• = K • H -2
• being its dimensionless measure * * ) . Such a model depends on a scale parameter H • = H(t • ) and two dimensionless parameters

Ω • = 8 3 πGH -2 • ρ c and λ • = 1 3 ΛH -2 • . 2. Vacuum (V) solution, defined by ρ c = 0 and v c = Λ 3 -H x.
The dynamics of a spherical void surrounded by an uniform distribution of gravitational sources is obtained by using a covariant formulation of Euler-Poisson equations system, 16), 17) which allows us to stick together the local V and NF solutions. We assume that their common border is a material shell (S) with a negligible tensionstress characterized by a (symmetric contravariant) mass-momentum tensor

T 00 S = (ρ S ) c , T 0j S = (ρ S ) c v j c , T jk S = (ρ S ) c v j c v k c (2 . 3) * )
We limit our investigation to motions which do not correspond to cosmological bouncing solutions, what requires the constraint K 3

• < (4πGρ•) 2 Λ to be fulfilled, according to analysis on roots of third degree polynomials.

* * ) A dimensional analysis of Eq. (2 . 2) shows that the Newtonian interpretation of k• corresponds to a dimensionless binding energy for the universe. The lower k• the faster the cosmological expansion.

The NF-kinematics, which applies to the outer part of S for describing the cosmological expansion (Hubble flow), shows two distinct behaviors characterized by the sign of k • : H decreases with a by reaching its limiting value H ∞ either upward (k

• ≤ 0) or downward (k • > 0) from a minimum H m = H ∞ 1 - K 3 • Λ (4πGρ • ) 2 < H ∞ = lim a→∞ H = Λ 3 (2 . 4) at (epoch) a = 4πGρ • K -1
• , what defines a loitering period. The expansion velocity of the shell S with respect to its centre reads v = yH r, where the corrective factor y to Hubble expansion versus a is given in Fig. 1. It results from a vanishing initial expansion velocity at a = 0.003, and has been evaluated for three world models defined by Ω • = 0.3. and λ • = 0, λ • = 0.7, λ • = 1.4. It can be noted that S expands faster than Hubble expansion (y > 1) with no significant dependence on Λ at early stages of its evolution. However, the presence of Λ magnifies its expansion (and hence its size) later during its evolution, and the larger the λ • (i.e., k • ) the major this effect. Such an effect shows its maximum at redshift z ∼ 1.7 and then decreases with time for reaching asymptotically Hubble flow * ) . Todays, its magnitude, which is of order of 10 percent of Hubble expansion, contributes possibly to the peculiar motion of our galactic region away from the Local Void. 18)-20) §3. Discussion

We have proved that a spherical void stands for a global solution of Euler-Poissons equations, which provides us with an hint on Λ effect on the dynamics * ) This bump on the diagram results from the cosmological expansion which undergoes a loitering period while the void expands, see Eq. (2 . 4). The present epoch t = t• appears quite peculiar because of the relative proximity of curves, but it is solely an artifact due to the choice of the scale.

of voids in the distribution of galaxies. More realistic shapes cannot be treated analytically for taking into account the active role of such a structure in the description of gravitational field, unless by numerical methods. The reason is that the radial symmetry is required for the boundary region (S) in order to preserve the isotropy of Friedmann model (also required in GR), otherwise another background model must envisaged.

An interesting property of the velocity field inside S enables us to disentangle a spatially closed universe (k • > 0) from an open one if inside S few galaxies are present so that to not contribute significantly to the gravitational fields. Indeed, in the reference frame, a test-particle moves toward the centre of S but if k • > 0 then it starts moving toward its border at (date) a = 8 3 πGρ • K -1 • . Such a property of sweeping out the void region (due to H < H ∞ ) interprets as a stability criterion for void regions.

Fig. 1 .

 1 Fig. 1. The corrective factor to Hubble expansion.

Acknowledgements

I would like to thank Prof. Masakatsu Kenmoku for his hospitality and successful organization of the conference.


Guadalupe M Árquez-Campos

Jorge L Ram

Írez-Alfons Ín

Jos É M Tornero
email: tornero@us.es

INTEGRAL POINTS IN RATIONAL POLYGONS: A NUMERICAL SEMIGROUP APPROACH

Keywords: 2010 Mathematics Subject Classification. Primary: 11H06, 11P21; Secondary: 20M13, 11-04 Lattice points, numerical semigroups, geometry of numbers

In this paper we use an elementary approach by using numerical semigroups (specifically, those with two generators) to give a formula for the number of integral points inside a right-angled triangle with rational vertices. This is the basic case for computing the number of integral points inside a rational (not necessarily convex) polygon.

Introduction: A little bit of history

In recent times, impressive advances in computational combinatorics and the ever-increasing amount of applications to other branches of mathematics have made lattice-point counting a fruitful and dynamic research field.

The problem of computing the set of integral points inside plane bodies has a long history. We will see how to reduce this problem to an interated application of Theorem 2. A milestone in this story is Pick's Theorem [START_REF] Pick | Geometrisches zur Zahlenlehre[END_REF], from the late years of the 19th century.

Theorem 1. Let S be a polygon such that all of its vertices are integral, and int(S) and ∂S are, respectively, its interior and its boundary, let A(S) be the area of S, I(S) = # Z 2 ∩ int(S) , B(S) = # Z 2 ∩ ∂S . More specifically, the question of counting lattice (in particular integral 1 ) points inside a right triangle has a long and interesting story. As early as 1922 Hardy and Littlewood [START_REF] Hardy | Some problems of Diophantine approximation: The latticepoints of a right-angled triangle[END_REF] studied the problem of right triangles defined by the coordinate axes and a hypotenuse with irrational slope.

In the following years, the interest for the subject did not decline. For instance, in [START_REF] Ehrhart | Sur les polyèdres rationnels homothétiques à n dimensions[END_REF] Ehrhart introduced the so-called Ehrhart quasi-polynomials, an almost ubiquous tool nowadays. In [START_REF] Mordell | Lattice points in a tetrahedron and generalized Dedekind sums[END_REF] Mordell established a connection between lattice points problems (for the tetrahedron) and Dedekind sums while in [START_REF] Pommersheim | Toric varieties, lattice points and Dedekind sums[END_REF] Pommersheim derived a more genaral formula by using techniques from algebraic geometry, see also [START_REF] Reeve | On the volume of the lattice polyhedra[END_REF].

A very good and comprehensive introduction to the subject, with a good share of deep results is Beck and Robins book [START_REF] Beck | Computing the continuous discretely. Integer-point enumeration in polyhedra[END_REF] where, in particular, the reader can find a formula, due the same authors [START_REF] Beck | Explicit and efficient formulas for the lattice point count inside rational polygons using Dedekind -Rademacher sums[END_REF], to compute the number of integral points inside a right triangle. Their approach is quite different from ours, they came out with a formula that uses either n-th primitive roots of unity or Fourier-Dedekind sums. The latter allowed them to give an efficient algorithm to calculate the number of integral points inside a right triangle since Dedekind sums with 2 variables can be computed in polynomial time. In this regard, we mention a polynomial time algorithm, due to Barnikov [START_REF] Barvinok | Integer Points in Polyhedra[END_REF][START_REF] Barvinok | A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed[END_REF] (that has significally influenced the field) that enumerates the lattice points of rational polytopes in fixed dimension.

Let us finally mention an interesting generalization of our problem. Let us call a right tetrahedron the convex set of R n ≥0 limited by the coordinate hyperplanes and a hyperplane a 1 x 1 + ... + a n x n = 1, with a i ∈ R. The question of counting (more precisely, bounding) the number of points in n-dimensional right tetrahedra has been a subject of study of S.S.T. Yau and some of his collaborators [START_REF] Lin | Analysis of sharp polynomial upper estimate of number of positive integral points in 4-dimensional tetrahedra[END_REF][START_REF] Lin | Analysis of sharp polynomial upper estimate of number of positive integral points in 5-dimensional tetrahedra[END_REF][START_REF] Lin | Counting the number of integral points in general n-dimensional tetrahedra and Bernoulli polynomials[END_REF][START_REF] Wang | On the GLY conjecture of upper estimate of positive integral points in real right-angled simplices[END_REF][START_REF] Xu | A sharp estimate of number of integral points in a tetrahedron[END_REF][START_REF] Xu | Durfee conjecture and coordinate free characterization of homogeneous singularities[END_REF][START_REF] Xu | A sharp estimate of number of integral points in a 4-dimensional tetrahedra[END_REF], a research that produced the so-called GLY conjecture (named after its creators, A. Granville, K.P. Lin and S.S.T. Yau).

This conjecture gives a lower estimate for the number of integral points in an n-dimensional right tetrahedron in terms of its vertex coordinates (the weak estimate) and in terms of these coordinates and the Stirling numbers (the strong estimate). The weak version was proved by Yau and Zhang [START_REF] Yau | An upper estimate of integral points in real simplices with an application to singularity theory[END_REF]. Asfor the strong version is concerned, the authors claim in the same paper that it has been checked computationally up to n = 10. The fact is that the conjecture might be checked for a particular n, but the state-of-the-art has not changed since. According to the authors, the case n = 10 took weeks to be completed. This result came handy to the first and third author in [START_REF] Márquez-Campos | Characterization of gaps and elements of a numerical semigroup using Groebner bases[END_REF]. Please note that the GLY conjecture only applies to n ≥ 3.

The main result of this paper is concerned with the following situation.

Theorem 2. Let a < b be coprime integers, c ∈ Z. Consider the following set:

T = (y 1 , y 2 ) ∈ Z 2 ≥0 | ay 1 + by 2 ≤ c . Then #T = - ab 2 k 2 + a + b + 1 + 2c 2 k + ⌊ c-kab b ⌋ i=0 c -kab -ib a + 1
where k = ⌊c/(ab)⌋. Equivalently, by using the Euclidean division c = q • ab + r, the above formula can be expressed in the following alternative way

#T = - ab 2 q 2 + a + b + 1 + 2c 2 q + ⌊r/b⌋ i=0 r -ib a + 1 .
Our technique to prove this result is based essentially in numerical semigroup invariants (the relationship between semigroups and lattice points problems has already been remarked in [START_REF] Ramírez Alfonsín | Gaps in semigroups[END_REF]). Although the above formula is not polynomial in the input size (since the sum has a terms in the worse case), we think that this elementary approach (avoiding Fourier analysis) might suggest a number of follow-up questions, which would be fruitful to investigate.

Two such questions are shown as applications of the main result in the last section. The first one will be computing the number of integral points inside a polygon with rational vertices. The second will explore a possible application to a well-known problem in numerical semigroups: the computation of the denumerant.

An interlude on numerical semigroups

This paper relies on numerical semigroups as a fundamental tool. A numerical semigroup is a very special kind of semigroup that can be thought of as a set

a 1 , ..., a k = {λ 1 a 1 + ... + λ k a k | λ i ∈ Z ≥0 } , with gcd(a 1 , ..., a k ) = 1.
This object has been thoroughly studied in the last years, when a significant number of problems concerning the description of these semigroups and some of its more interesting invariants have been tackled. Unless otherwise stated, all proofs which are not included can be found in [START_REF] García-Sánchez | Numerical semigroups[END_REF][START_REF] Ramírez Alfonsín | The Diophantine Frobenius problem[END_REF].

Given a numerical semigroup S, there are some invariants which will be of interest for us. The most relevant will be the set of gaps, noted G(S), and defined by

G(S) = Z ≥0 \ S,
which is a finite set. Its cardinality will be noted g(S) and its maximum f (S), the so-called Frobenius number.

The Apéry set of S with respect to an element s ∈ S can be defined as

Ap(S, s) = {0, w 0 , ..., w s-1 }
where w i is the smallest element in S congruent with i modulo s.

In particular, for semigroups with two generators, the invariants g(S) and f (S) and the relevant Apéry sets are fully determined.

Lemma 3. Let S = a 1 , a 2 . Then g(S) = 1 2 (a 1 -1)(a 2 -1) f (S) = (a 1 -1)(a 2 -1) -1 Ap(S, a i ) = {0, a j , 2a j , ..., (a i -1)a j }

The number of integral points inside a right triangle

Let us consider then a right triangle determined by the positive coordinate axes and the line ax + by = c, a, b, c ∈ Z and gcd(a, b) = 1, where we will assume a < b, with no loss of generality.

Take the set: Let us perform the following partition on our set T :

T = (x, y) ∈ Z 2 ≥0 | ax +
B 0 = (x, y) ∈ Z 2 ≥0 | ax + by ≤ c, 0 ≤ x < b B 1 = (x, y) ∈ Z 2 ≥0 | ax + by ≤ c, b ≤ x < 2b . . . . . . B i = (x, y) ∈ Z 2 ≥0 | ax + by ≤ c, ib ≤ x < (i + 1)b . . . . . . B k = (x, y) ∈ Z 2 ≥0 | ax + by ≤ c, kb ≤ x
where k = ⌊c/(ab)⌋.

As our aim is to find #T , and it is plain that:

#T = #B 0 + #B 1 + ... + #B k-1 + #B k ,
we can reduce our problem to that of finding #B i , for i = 0, ..., k.

Lemma 4. Under the previous assumptions, if k > 0,

#B 0 = a + b -ab + 1 2 + c = 1 -f (S) 2 + c
Proof. We will actually show that

S ∩ [0, c] 1:1 ←→ B 0 .
Given a pair (x, y) ∈ B 0 we define its corresponding element in S ∩ [0, c] to be n = ax + by.

In the same way, given n ∈ S ∩[0, c] it is clear that we must have a representation n = ax + by and we can in fact assume 0 ≤ x < b (if otherwise, we can move part of ax into the by summand until x < b).

Let us assume that we have such a representation (that is, with 0 ≤ x < b) and we will prove that then the pair (x, y) must be unique, which will establish the bijection. Should we have

n = ax 0 + by 0 = ax 1 + by 1 , with 0 < x 0 , x 1 < b,
we must have a(x 0 -x 1 ) = b(y 1 -y 0 ) and, as gcd(a, b) = 1, this means b|(x 1 -x 0 ), which in turn implies x 0 = x 1 . Note that the case x 0 = x 1 = 0 leads directly to y 0 = y 1 as desired.

Note that k > 0 is equivalent to c ≥ ab, which also yields c > f (S). Therefore, after Lemma 3,

#B 0 = # S ∩ [0, c] = # S ∩ [0, f (S)] + c -f (S) = ab -(a + b) + 1 2 + c -ab -(a + b) = a + b -ab + 1 2 + c.
Simple as it is, this case is the basic argument for the whole process. Now, if we want to compute #B 1 , we just move our triangle, so that (b, 0) is now at the origin. Similarly, the line ax + by = c is moved, as in the picture: So, with a little abuse of notation, let us redefine:

B 1 = (x, y) ∈ Z 2 ≥0 | ax + by ≤ c 1 , 0 ≤ x < b
where c 1 = c -ab (obviously this only makes sense if c > ab). Assuming k > 1 we have, following the same way:

#B 1 = # (S ∩ [0, c 1 ]) = # S ∩ [0, c -ab] = ab -(a + b) + 1 2 + c -ab -(ab -(a + b) + 1) = a + b -3ab + 1 2 + c.
We can of course go along the same lines for computing #B i for i = 1, ..., k -1, where k = ⌊c/(ab)⌋, rewriting c i = c -iab, whenever c > iab and we will find:

#B i = # (S ∩ [0, c i ]) = # S ∩ [0, c -iab] = ab -(a + b) + 1 2 + c -iab -(ab -(a + b)) = (a + b) -(1 + 2i)ab + 1 2 + c
We have then arrived at the nutshell of the problem: the set B k . After we have moved it to the origin, we have our renamed B k :

B k = (x, y) ∈ Z 2 ≥0 | ax + by ≤ c k . Now
ib + ja ≤ c k ⇐⇒ j ≤ c k -ib a ,
and then

S ∩ [0, c k ] = {ib + ja ≤ c k | i, j ∈ Z ≥0 } = ib + ja i ∈ 0, ..., c k b , j ≤ c k -ib a = ⌊c k /b⌋ i=0 c k -ib a + 1
Adding up all of these computations, we arrive to our result. In the previous conditions:

#T = #B 0 + #B 1 + ... + #B i + ... + #B k-1 + #B k = a + b -ab + 1 2 + c + ... + (a + b) -(1 + 2i)ab + 1 2 + c + +... + ⌊c k /b⌋ i=0 c k -ib a + 1 = k-1 i=0 (a + b) -(1 + 2i)ab + 1 2 + c + ⌊c k /b⌋ i=0 c k -ib a + 1 = - ab 2 k 2 + a + b + 1 + 2c 2 k + ⌊ c-kab b ⌋ i=0 c -kab -ib a + 1
where k = ⌊c/(ab)⌋. Or equivalently, by using the Euclidean division: c = q • ab + r we obtain

#T = - ab 2 q 2 + a + b + 1 + 2c 2 q + ⌊r/b⌋ i=0 r -ib a + 1 .
This proves Theorem 2.

Example. Let us do a simple example to illustrate the process, considering the triangle defined by the line 3x + 7y = 46. Following Theorem 2 we have k = 46 3•7 = 2, that is,

# T = - 3 • 7 2 2 2 + 3 + 7 + 1 + 2 • 46 2 •2+ ⌊ 46-2•3•7 7 ⌋ i=0 46 -2 • 3 • 7 -i • 7 3 + 1 = 63.
Let us see the actual counting:

In the picture we have put different symbols for the different sets B j , following the process. Round points correpond to B 0 . There are 41 of them, as predicted by the formula:

#B 0 = a + b -ab + 1 2 + c = 3 + 7 -3 • 7 + 1 2 + 46 = 41.
Crossed points correspond to points in B 1 :

#B 1 = a + b -3ab + 1 2 + c = 3 + 7 -3 • 3 • 7 + 1 2 + 46 = 20.
And finally the square points are those of B 2 :

#B 2 = ⌊ c k b ⌋ i=0 c k -ib a + 1 = 46 -42 3 + 1 = 2.

Applications (I): Integral points in general triangles

Our aim in this section is to give a result (in some sense in the spirit of Pick's theorem) to compute the number of integral points inside a generic triangle. This, of course, is enough to compute the number of integral points inside polygons (not necessarily convex) defined by rational vertices. But we will not address here the problem of dividing a polygon into triangles [START_REF] Berg | Computational Geometry[END_REF][START_REF] Kirkpatrick | Polygon triangulation in O(n log log n) time with simple data structures[END_REF].

The important point here is that, in order to compute the number of integral points of such a polygon, it suffices with rectangles and right triangles of a particular type. Of course rectangles can be divided in two right triangles, but this brings no substantial computational simplification to our problem.

From now on, a rectangle whose sides are parallel to the coordinate axes will be called a stable rectangle. Computing the number of integral points inside a stable rectangle is very easy. Lemma 5. Let α 1 < β 1 and α 2 < β 2 be real numbers. Let R ⊂ R 2 be the stable rectangle with vertices (α 1 , α 2 ) and (β 1 , β 2 ). Then

#(R ∩ Z 2 ) = (⌊β 1 ⌋ -⌈α 1 ⌉ + 1) • (⌊β 2 ⌋ -⌈α 2 ⌉ + 1)
Similarly, a right triangle whose orthogonal sides are parallel to the coordinate axes will be called a stable right triangle. The computation of the number of integral points inside a stable right triangle can be easily achieved from Theorem 2, as we shall show now.

Assume we have such a triangle T defined by rational vertices (A is the vertex at which T has its right angle):

A = (α, β), B = (α, γ), C = (δ, β),
and we can assume, up to symmetry, α < γ, β < δ. Furthermore, it is clear that, as for counting integral points is concerned, we can substitute

α -→ ⌈α⌉, β -→ ⌈β⌉,
and the number of integral points does not change by traslations of integral vectors, hence we can in fact assume A = (0, 0). (1) d = 1. We can apply Theorem 2.

(2) d > 1. As gcd(d, c) = 1 clearly there are no integral points in the hypothenuse, as any such point (x, y) must verify ax + by ∈ Zd. So we are going to change the triangle T , moving the hypothenuse in a parallel way towards A, until the new triangle has at least some chance to have one integral point in the hypothenuse. This is the triangle T ′ defined by

ax + by = c ′ ,
where c ′ = ⌊c/d⌋d. It is clear that with such construction #(T ∩ Z 2 ) = #(T ′ ∩ Z 2 ) and so #(T ∩ Z 2 ) can be computed counting the number of integral points in the stable triangle defined by

a d x + b d y = c ′ d = c d ,
that is, using Theorem 2.

As we shall see later, in related problems (as, for instance, the problem of computing the number of integral points inside a polygon), we might have to compute the number of points in the sides of a right stable triangle. To do this, note that:

• The number of integral points in the orthogonal sides can be easily computed: in the segment limited by (a, b) and (a, c), say with b < c (any other case is obviously symmetric), the number of integral points is It is easy to see that this denumerant has to be either ⌊c/(ab)⌋ or ⌊c/(ab)⌋ + 1, that is, k or k + 1 with the notation of the previous section, assuming c ∈ S (obviously it is 0 otherwise). This is because c (or c i ) must be representable and from Lemma 4 there must exist exactly one representation whose coefficients are in B 0 (respectively B i ). This holds true for B 0 ,...,B k-1 but not necessarily for B k (because c k might not be in S), hence the two possible cases. More precisely, we have the following result (see [START_REF] Popoviciou | Asupra unei probleme de patitie a numerelor[END_REF] for the original proof in Romanian, [START_REF] Brown | On the partition function of a finite set[END_REF] for a shorter and easier one): Theorem 6. Under the previous asumptions, let a ′ and b ′ be the only integers veryfing

0 < a ′ < b, a • a ′ = -c mod b 0 < b ′ < a, b • b ′ = -c mod a
Then the denumerant of c in S is given by

d(c; a, b) = c + a • a ′ + b • b ′ ab - 1
In the sequel, when we are interested in the points inside a right triangle T we will write #T int and if we want the points excluding only the hypothenuse we will denote this cardinal by #T hyp . Finally, then, let us show how to compute the integral points in a generic triangle using stable rectangles and right triangles (and hence, Theorem 2). Assume we are given a triangle T , given by We consider the (stable right) rectangle R T determined by

A 1 = (α 1 , β 1 ), A 2 = (α 2 , β 2 ), A 3 = (α 3 , β 3 ),
V 1 = (x 0 , y 0 ), V 2 = (x 1 , y 0 ), V 3 = (x 0 , y 1 ), V 4 = (x 1 , y 1 ) .
It is clear that it must hold V i = A j for some i = 1, 2, 3, 4 and j = 1, 2, 3. Depending on the relative position of the maximal vertices, the situation must be one of these four (up to rotation and flip, if necessary):

• Only one of the vertices of R T is a vertex of T . Then it is clear that:

#T = #R T -#T hyp 1 -#T hyp 2 -#T hyp 3 .
• Two adjacent vertices of R T are vertices of T . Then:

#T = #R T -#T hyp 1 -#T hyp 2 .
• Two non-adjacent vertices of R T are vertices of T . Then (one of many possibilities):

#T = #R T -#T hyp 1 -#T hyp 2 -#T hyp 3 -#T 4 -#T int 5 + 1 Z 2 (P ) + 1 Z 2 (Q).
• The three vertices of T are vertices of R T . This is the trivial case, as T is a right stable triangle.

Applications (II): On the denumerant of a numerical semigroup with 3 generators

The result on rational polygons and its reduction to rectangles and right triangles could be generalized to an n-dimensional set-up. However, the actual formulas are not easy enough so as to give a tight result. We give a first idea on how this could be done by computing the number of points in a stable right tetrahedron (the definition is the obvious one).

Theorem 7. Let T (a 1 , a 2 , a 3 , b) ⊂ R 3 be the tetrahedron defined by

T (a 1 , a 2 , a 3 , b) = {(x 1 , x 2 , x 3 ) | x i ≥ 0, a 1 x 1 + a 2 x 2 + a 3 x 3 ≤ b}
where we are assuming a 1 < a 2 < a 3 , gcd(a 1 , a 2 ) = 1.

For i = 0, ..., ⌊b/a 3 ⌋ define q i and r i by the Euclidean division:

b -a 3 i = q i (a 1 a 2 ) + r i . Proof. The formula is just the result of adding the number of points in every right triangle T (a 1 , a 2 , a 3 , b) ∩ {x 3 = i} for i = 0, ..., ⌊b/a 3 ⌋.

The condition gcd(a 1 , a 2 ) = 1 can obviously be substituted by gcd(a 1 , a 3 ) = 1 or gcd(a 2 , a 3 ) = 1 if necessary. If none of this conditions is met, like in the tetrahedron defined by 6x 1 + 10x 2 + 15x 3 = 21, for instance, then some of the right triangles have to be adjusted as we did in the previous section. This is not a difficulty when programming, so to say, but the general formula gets a lot more complicated. We have tried to get a compact version of this, but this effort has been unsuccesful so far.

This result can be handy when trying to compute the denumerant function we introduced above.

Easy as it is to define, the denumerant is a very elusive function which has proved elusive to compute even in cases with 3 generators (see [START_REF] Ramírez Alfonsín | The Diophantine Frobenius problem[END_REF]Chapter 4]). With the previous result one can give a formula, not very sophisticated though. Simply note that d (a; a 1 , a 2 , a 3 ) = # (x 1 , x 2 , x 3 ) ∈ Z ≥0 | a 1 x 1 + a 2 x 2 + a 3 x 3 = a = # T (a 1 , a 2 , a 3 , a) ∩ Z 3 -# T (a 1 , a 2 , a 3 , a -1) ∩ Z 3 .

And then, from the previous result, one can obtain the desired formula.

  by ≤ c and let us define the numerical semigroup associated to our triangle as S = a, b . S therefore verifies that its Frobenius number is f (S) = ab -(a + b).

  we might have c k < ab -(a + b). So we cannot proceed in the same way as before. We do know c k = c -kab, that is, c k = c mod ab, and from Lemma 3 we also know: Ap(S, a) = {0, b, 2b, ..., (a -1)b} and therefore {w ∈ Ap(S, a) | w ≤ c k } = ib i = 0, 1, ..., c k b On the other hand, if i ∈ {0, ..., ⌊c k /b⌋}, we have

  After translating the triangle T , we can write the hypothenuse of the new triangle as ax + by = c, where we can assume a, b, c ∈ Z, gcd(a, b, c) = 1. That is, B = (0, c/b), C = (c/a, 0). Mind that a and b need not to be coprime in this set-up. But, in order to apply Theorem 2, we should have gcd(a, b) = 1. Let d = gcd(a, b). There are two possibilities:

(⌊c⌋ -⌈b⌉ + 1 ) • 1 Z

 11 (a), where 1 Z (a) is the indicator function of Z. • The number of integral points in the line ax + by = c is the number of representations of c inside the semigroup S = a, b . This number is known as the denumerant of c in S [19].

Then # T (a 1 , a 2 , a 3 , b) ∩ Z 3 =

 1233

Acknowledgements

The authors warmly acknowledge the help and advice of J.C. Rosales.

The final stage of this work was completed during a stay of the first author in the Institut Montpelliérain Alexander Grothendieck, Université de Montpellier, during the spring term of 2013, thanks to the grant P08-FQM-3894 (Junta de Andalucía).

First and third authors were partially supported by the grant FQM-218 and P12-FQM-2696 (FEDER and FSE). The second author was supported by ANR TEOMATRO grant ANR-10-BLAN 0207 and grant ECOS-Nord M13M01.


Loic Guegan
email: loic.guegan@ens-rennes.fr

Betsegaw Lemma Amersho

Anne-Cécile Orgerie
email: anne-cecile.orgerie@irisa.fr2

Martin Quinson
email: martin.quinson@ens-rennes.fr

A Large-Scale Wired Network Energy Model for Flow-Level Simulations

The use of simulators to predict network energy consumption is a good way for scientists to improve and develop new algorithms and also to assess them. However, the average size of a network platforms is continuously increasing with the emergence of new technologies like the Internet Of Things and Fog Computing. Packet-level simulators start to reach their limits in terms of performance and this calls for newer solutions in the domain of large-scale platform energy models. In this paper, we propose two energy models for wired networks adapted to flow level simulators in order to estimate the energy consumption of large platforms. An evaluation of these models is proposed and it demonstrates their applicability in practice and their accuracy. Indeed, we obtain simulation results with a relative error lower than 4% compared to an ns-3-based solution, and our flow-based simulation is 120 times faster.

Introduction

Since the beginning of Internet, distributed systems are widely used and researchers put large efforts in this field in order to improve performance models and provide new solutions. Since their usage tends to grow with the arrival of new technologies like Internet of Things (IoT) and Fog computing [START_REF] Bonomi | Fog computing and its role in the internet of things[END_REF], their energy consumption is an increasingly important metric to optimize. Information and communication technology (ICT) devices, that are part of distributed systems, can be categorize in three classes [START_REF] Van Heddeghem | Trends in worldwide ICT electricity consumption from 2007 to 2012[END_REF]: end-user devices, communication networks, and data centers. Researchers estimate that the overall energy consumption growth rate of each of these classes is respectively 5%, 10% and 4%. With the highest expected growth, communication networks constitute a key player in the ICT's global electricity consumption. Energy-efficient solutions are required for curbing this trend.

Several methods are available to study energy saving techniques. First, testbeds can be used to perform experiments in order to be as close to the reality as possible. However, test-beds face three main drawbacks: 1) Deploying equipment and building a real network is expensive especially at large scale. 2) Such a deployment requires a lot of setting-up time. 3) Experiments are hardly reproducible due to numerous uncontrollable parameters. Another option to study energy saving techniques consists in using simulators. They allow to conduct diverse experiments on any types of platforms in a convenient way. Moreover, they permit to save time compared to real deployments, and experiments can be reproduced easily. On the other hand, network simulators need to be carefully calibrated and assessed to produce valid results.

Several types of simulators can estimate the energy consumption of networks. However, current network platforms and traffic volumes push their scalability to their limits. Indeed, with the arrival of new technologies like the Internet Of Things and fog computing, the number of connected devices increases. Besides, generated and exchanged data volumes are augmented consequently in these increasingly distributed systems, leading to an unprecedented rise of the global energy consumption attributable to ICT.

This calls for scalable yet accurate models and simulators to estimate network energy consumption. Existing simulators that model the energy consumption work at fine grain -simulating each packet exchange -and thus are not scalable for modern research purposes. Their over-approximation is not compatible with efficient simulations. Nevertheless, scalable simulators exist but to the best of our knowledge, none of them is modeling network energy consumption or they are limited to study specific environments or protocols. Flow-based simulators operate at a flow level without simulating each packet, thus saving memory and computations. In practice, they constitute a nice compromise between network abstraction and scalability, in terms of memory usage and computation time.

In this work, we propose to extend an existing flow-based simulator with network energy models. We show that modeling the network energy consumption into a flow-level simulator leads to predictions that are in line with the predictions of packet-level simulators. We also show that simple linear models are sufficient on realistic settings to obtain accurate values, while more complex models were proposed in literature. Indeed, this model exhibits a relative error lower than 4% compared to an ns-3-based solution and provides the simulation results 120 times faster with using more than 17 times less memory.

The rest of this paper is structured as follows. Section 2 details the different simulators and the classical network energy models. Section 3 presents energy modeling in flow-level simulators. Section 4 presents the proposed energy models. Section 5 details our evaluation methodology. An evaluation of the energy models in terms of validity, scalability and applicability is proposed in Section 6. Finally, we conclude in Section 7.

Related Work

Network Simulators

In the literature several packet-level simulators were extended in order to simulate the energy consumption of network devices.

The first well-known simulator that enters in this category is ns-2. It has been extended into GreenCloud [START_REF] Kliazovich | GreenCloud: A Packet-Level Simulator of Energy-Aware Cloud Computing Data Centers[END_REF] which is designed for cloud simulations using different architectures: two-tiers, three-tiers and three-tiers high-speed. However, Greencloud can be used only in cloud context and thus, it is very limited. Furthermore, as it relies on ns-2, its scalability is limited in terms of number of simulated devices and exchanges volumes of data.

As a replacement for ns-2, another packet-level simulator called ns-3 was proposed. It provides several modules including ECOFEN [START_REF] Orgerie | ECOFEN: An End-to-end energy Cost mOdel and simulator For Evaluating power consumption in large-scale Networks[END_REF]. This module is able to simulate the energy consumption of network communications based on three energy models namely basic, linear and complete. Even if they provide accurate results [START_REF] Orgerie | Simulation Toolbox for Studying Energy Consumption in Wired Networks[END_REF], the packet-level nature of ns-3 prevents the usage of ECOFEN for large-scale networks.

While these simulators offer accurate predictions, they fail to scale. In fact, event rate of packet-level simulators increases very quickly on large-scale platforms with real workloads. Flow-level simulators work at a higher level of abstraction in order to have very efficient performance models. Hence, this feature makes them suitable for large-scale network simulations. Moreover, they show good prediction abilities when their are properly instantiated. This makes them good candidates for network energy consumption simulations.

CloudSim belongs flow-level simulators and is built on top of GridSim. It is a well-known event-based simulator capable of simulating cloud environments and estimating their energy consumption. It implements green strategies like Dynamic Voltage Frequency Scaling and energy-conscious VM provisioning techniques. On the other side, CloudSim is designed for cloud environment which makes it difficult to use outside of this context. Another point is that, CloudSim models are very similar to the GridSim ones which are known to contain bandwidth sharing model aberrations [START_REF] Velho | On the validity of flow-level tcp network models for grid and cloud simulations[END_REF].

SimGrid is another flow-level simulator, it is very versatile and can be used to simulate High Performance Computing, Grid, Peer-to-peer etc. It is also scalable [START_REF] Quinson | Parallel Simulation of Peer-to-Peer Systems[END_REF], but unfortunately it does not provide network energy model. Consequently, we propose to extend SimGrid by adding network energy models. However, because of the coarse granularity nature of flow-level simulators, we should carefully instantiate and validate these energy models.

Classical network energy models

Simulators are able to abstract the complexity of network devices' energy consumption. Even if a network equipment is not subject to any network traffic, it consumes energy. Indeed, the different components involved in network devices should be maintained powered on to ensure a fully functional network communication in case of packet arrival. This energy consumption part is called the idle or static part. In some cases, the idle energy cost of a network device can represent 85% of its peak power [START_REF] Fiandrino | Performance Metrics for Data Center Communication Systems[END_REF]. Classically, the energy consumption is estimated using the energy definition E(t) = t 0 P (t)dt. Considering a network equipment, its energy consumption varies over time according to the network traffic. Since its power is composed of two parts: one static and one dynamic, we can define its power in Equation 1 with S the set of ports on the given network device, N p i and N b i respectively the number of packets and the number of bytes going through the port i, and P p i and P b i the power costs per packet and per byte for the port i.

P netdev = P idle Static + i∈S N p i × P p i + N b i × P b i Dynamic (1)
Existing energy models in literature are based on this equation and consequently, they are not directly compatible with flow-level simulators. Indeed, flow-level simulators do not provide any notion of port in their models nor packets. These energy models should be adapted to this network representation.

Background on simulation

Simulation models can be built by following different approaches. One of them is to model every details of the reality. In this case, lots of parameters increase the model instantiation complexity. For the same reasons, the observations generated by these models are more difficult to interpret. On another hand, well detailed models can lead to accurate predictions, but they still should be validated in spite of their detailed nature. Another approach is to use abstract models. Thereby, no assumptions can be made on their level of accuracy. The last approachthis is the one that we chose -is to use simpler models that are still able to do accurate predictions. A good reference related to these types of models is the LogP model proposed by David Coller et al. [START_REF] Culler | LogP: Towards a realistic model of parallel computation[END_REF]. They propose a simple model for parallel computing composed of only four parameters. Still, LogP is taking into account communication delay and CPU overhead, which makes it suitable for accurate performance predictions and algorithm optimizations. Thereby, our energy model is part of this latter approach.

As aforementioned, the energy models proposed in this paper are implemented on a flow-level simulator called SimGrid. This simulator is based on a modeling philosophy where the different models are simplified but nevertheless assessed with the aims of providing valid results. It goes against two classical believes. First, a model with more parameters is necessarily more accurate and thus gives results closer to the reality. Indeed, we showed in previous work that simple models are sometimes enough to capture complex effects [START_REF] Velho | On the validity of flow-level tcp network models for grid and cloud simulations[END_REF][START_REF] Legrand | Scheduling distributed applications: the SimGrid simulation framework[END_REF]. Second, a model that implements all the parameters present in the reality are somehow correct by design (these parameters can be routing protocols, link delays, bit error rate, etc.). Yet, model validations are mandatory in all cases. It can be justified by the fact that some published simulators suffer from trivial implementation bugs [START_REF] Velho | On the validity of flow-level tcp network models for grid and cloud simulations[END_REF] that have never been fixed. Hence, in this work we provide validation results that can be reproduced by everyone (our code is open source and available on the SimGrid web page).

SimGrid does not include Network Interface Controllers (NICs) and routers. Instead, the paths between two hosts are represented by routes. Each route is composed of several entities, called links that represent both, the wire and the NIC at each end. A route between two hosts can be composed of multiple links but not necessarily of multiple hosts. To this end, there is no notion of port in flow-level simulators. In spite of this, we can attach the energy consumption of ports on the links. Then, it is possible to define the power of the overall network platform using the equation P total = i∈L LinkPower i × LinkUsage i with L representing the set of links on the simulated network platform.

However, in every networks, each link is connected to two different ports with potentially different energy consumption schemes. Thus, flow-level simulators abstraction introduces difficulties to transpose packet-level energy models into them. To solve this issue, we propose to define two energy models, one for homogeneous energy platform (same energy consumption for ports on a given link) and one for heterogeneous energy platform. We will see later that this distinction can in fact be simplified.

Contribution

Homogeneous model for flow-based simulators

We first introduce an energy model for network topologies that uses homogeneous energy consumptions. As said previously, links will hold the energy consumption of each of their ports and additionally, will ensure the bandwidth sharing. To achieve this goal, we propose to use one split-duplex link between each end-node. Then, to overcome the lack of port representation into SimGrid, we double the dynamic energy consumption of each link to account for the two ports (one at each end of the link). Since split-duplex links cause the creation of two links, the idle power will be already doubled and we only need to double the dynamic part of the power. More generally, the energy consumed by ports follows a linear model with a minimum value equals to the idle energy consumption and a maximum value define as:

max = idle + (BW × ByteCons + P ktCons /MT U ) × 2 (2)
In this equation, BW represents the port rate in Bps, ByteCons its energy consumption per byte in Joules, P ktCons represents the network device energy consumption in Joules needed for handling a packet. Finally, M T U , the Maximum Transmission Unit is used as an over-approximation of the packet size. Considering a one-way communication, the link consumes energy for the transmitting (Tx) and receiving (Rx) ports at the same time and vice-versa. If there are multiple flows, the bandwidth sharing occurs on the up or down links according to the flows' directions. Figure 1 depicts this homogeneous energy model for both kinds of simulators.

This energy model has multiple advantages. First, it is very easy to instantiate because there is only one energy cost per link. Consequently, this makes it easier to implement on flow-level simulators since these simulators use at least links for communications (but not necessarily ports). Finally, this model provides low computational overhead. However, many real topologies use heterogeneous networking devices. Thus, the energy consumption from one NIC to another varies according to its specifications. Consequently, this heterogeneity cannot be explicitly represented using the homogeneous model. Hence, we decide to introduce another model to overcome this limitation.

Heterogeneous model

In SimGrid, routes from one host to another can be composed of multiple links. Therefore, we can take advantage of this feature to build the heterogeneous model. This model is represented on Figure 2. In order to model two ports with different energy consumption on a single link, we introduce routes made of 3 links. The first link models the energy consumption of the first port, the second link handle the bandwidth sharing and finally, the third link models the energy consumption of the second port. However, we are using split-duplex links, thus two links will be created by SimGrid and consequently the idle power will be multiplied by two. To overcome this issue, we simply have to divide by two the idle power of each energy link. Thus, this energy model follows a linear behavior with a minimum value equals to idle /2 and a maximum value defined as:

max = idle /2 + (BW × ByteCons + P ktCons /MT U ) (3)

Methodology

The evaluation of the two energy models is divided in two steps. The first step is dedicated to assessing the models by means of microbenchmark simulations. Hence, the experiments are running on small platforms in order to do simulations on a simple and controlled environment. The second step of the evaluation is focused on testing the energy models on a real large-scale platform. In this way, we can demonstrate that the models are suitable for real research purposes and thus, are useful for the scientific community. In addition, it demonstrates that the energy models are scalable regardless to the simulated platform and the workload size. It is important to note that our evaluation focuses on the network energy consumption estimation and not on the network performance model. Yet, it is mandatory to have accurate time estimations to get accurate energy consumptions.

To conduct the validation experiments, we decided by lack of real largescale platforms to do simulations. In fact, validating these energy models using test-beds requires to measure the energy consumption per byte and per packet on each network devices. However, these measurements require high-precision instruments. Nevertheless, these energy measurements results are proposed in the literature [START_REF] Sivaraman | Profiling per-packet and per-byte energy consumption in the NetFPGA Gigabit router[END_REF][START_REF] Cornea | Studying the energy consumption of data transfers in Clouds: the Ecofen approach[END_REF]. Therefore, we based our experiments on these works.

To validate the two energy models, the experiments are done in parallel on a packet-level simulator that acts as a trusted party. We choose to use ns-3 and ECOFEN for this purpose. It is a logical choice since ECOFEN has been assessed as accurate in the literature [START_REF] Orgerie | Simulation Toolbox for Studying Energy Consumption in Wired Networks[END_REF]. Moreover, ECOFEN is a packet-level simulator, thus it will be useful for the scalability experiments in order to compare its simulation performances to SimGrid. It is important to mention that all the simulations ran on Grid'5000, a large-scale test-bed for experiment-driven research in computer science. In fact, microbenchmark scenarios require 96 unique simulations for only one experiment point (4 data transfer scenarios, 3 topologies with 2 energy instantiation, 3 models are tested including one which is an optimization). Moreover, the real use case experiment was also very computationally intensive for ns-3 and ECOFEN.

All the experiments presented in this paper are available online [START_REF] Guegan | Reproducible Experiments Repository[END_REF]. We did our best effort to provide reproducible experiments that can be run with different parameters and require the least possible amount of user interaction for the reader desirous of reproducing our experiments.

Experimental setup

To conduct microbenchmark simulations, we designed different experimental scenarios. These scenarios are built in order to account for the effects on the energy consumption of the following parameters: 1) The number of nodes and their connections in the network 2) Different flow configurations, and thus different bandwidth sharing patterns 3) The heterogeneity of the devices in terms of energy profile. For this, we define three platforms. The first one is composed of two hosts connected by one link. The second platform is an extension of the first one where we add two hosts and two links. Finally, the last platform, called Dogbone, is composed of six hosts connected together in order to have a bottleneck on the two central hosts. Furthermore, the platforms can be set up with homogeneous or heterogeneous energy consuming devices. Thanks to these two variants, the ability of each model to predict the overall energy consumption of platforms with homogeneous and heterogeneous devices is highlighted. Then, each platform is running with different TCP flow configurations. Other classical network parameters are also defined. These parameters are equals for all the microbenchmark scenarios: the latency is set to 10ms and the bandwidth to 1Gbps for each link since the energy value for such a NIC is available in the literature [START_REF] Sivaraman | Profiling per-packet and per-byte energy consumption in the NetFPGA Gigabit router[END_REF][START_REF] Cornea | Studying the energy consumption of data transfers in Clouds: the Ecofen approach[END_REF]. Thus according to these papers, the energy values used in our microbenchmarks for 1Gbps links are 1.12 Watts for idle power consumption, 3.4nJ for energy consumed per byte and 197.2nJ for the energy consumption per packet. However, for the heterogeneous platform instantiation, we used energy values of 10Gbps links namely 0.53 Watts for idle power consumption, 14nJ and 1504nJ respectively for energy consumption per byte and per packet. Finally, the data flow size is varying randomly between 10MB to 100MB (x-axis) in order to build a power profile of the network platforms.

6 Evaluation: validity, scalability and real use case

Validity of the proposed models

As a first step, we simulate the microbenchmark scenarios on homogeneous energy consumption platforms. The amount of data sent by the hosts are varied according to the parameters defined in Section 5.2. Due to space limitation, we only provide the results for two scenarios on Figure 3. The flow configuration used for these scenarios is the following: 3 flows overall (2 up and 1 down) between the extreme nodes of each platform.

These first results show the ability of each model to predict the energy consumption on two platforms namely Dogbone and 4 hosts and 3 links with homogeneous network devices. They clearly show a linear relation between the amount of data sent between hosts and the overall energy consumption. One interesting phenomenon to note is that both SimGrid energy models predict the exact same amount of energy. Their energy relative error are close to 0, which means they have the same energy prediction ability. In fact, it is not surprising since the first energy model is a subset of the second one. Thus, they show similar predicting abilities on homogeneous platforms. It is also interesting to note that both homogeneous and heterogeneous energy models show a very small relative error (less than 1%) compared to ns3 with ECOFEN.

Next, to demonstrate the ability of each model to predict the energy consumption on heterogeneous platforms, we did similar microbenchmark experiments using the scenarios with heterogeneous devices in terms of energy consumption. Thereby, we expect the homogeneous model to have a lower prediction ability since it is not designed to handle heterogeneous energy platforms. The simulation results are shown on Figure 4. As expected, the homogeneous model is less accurate than the heterogeneous model. In fact, we can clearly see that the heterogeneous model energy estimation corresponds to the energy predicted by ns-3 and ECOFEN. However, the homogeneous model is doing wrong approximation. This phenomenon is explain by the fact that the granularity of the first energy model is not fine enough to fully capture the dynamic energy consumption of the network devices.

Nonetheless, we decided to modify the instantiation of the homogeneous model in order to improve its prediction capability. Hence, for each link we attached an energy consumption equal to the average energy consumption of their ports. The results of these simulations are also visible on Figure 4 in pink. We can see that by using this simple optimization we surprisingly observe that the homogeneous model produces very accurate results almost equal to the heterogeneous model. This improvement can be explain by the fact that on real platforms, the difference between the energy consumption of the ports is small and thus, taking the mean has a limited impact on the overall energy consumption. Obviously, the relative error between ECOFEN and the homogeneous model will increase if this difference becomes larger. Hopefully, in real platforms this difference remains reasonable. Moreover, the heterogeneous energy model multiply by three the number of links used in the SimGrid simulation, which is not negligible on large-scale platforms. This is why, by following the Occam's razor Principle, we decide to use the homogeneous energy model with the arithmetic mean instantiation in the remaining experiments.

Realistic use case

To evaluate the scalability of our approach, we propose to simulate a datacenter' network which is a classical large-scale platform widely used in research. Therefore, the final experiment has two main goals. Firstly, it demonstrates that our modified homogeneous energy model scales up in terms of execution time and memory usage. Secondly, it shows that this energy model is usable for real experiments and thus is interesting for the scientific community. The data center platform is based on a classical three-tier architecture used by Greencloud [START_REF] Kliazovich | GreenCloud: A Packet-Level Simulator of Energy-Aware Cloud Computing Data Centers[END_REF]. It is composed of 8 core nodes that provide access to the data center. These two core nodes are linked to 16 aggregation nodes by 10Gbps links. These aggregation nodes are linked to 512 access switches by 1Gbps links that provide access to 1,536 servers by mean of 1Gbps links. Each link latency is fixed to 0.2ms which is the average latency measured between two Grid'5000 internal nodes. The platform is set with the energy consumption of 1Gbps/10Gbps links referenced in the literature [START_REF] Sivaraman | Profiling per-packet and per-byte energy consumption in the NetFPGA Gigabit router[END_REF][START_REF] Cornea | Studying the energy consumption of data transfers in Clouds: the Ecofen approach[END_REF].

The simulation scenario is defined as follows. First, 10 to 400 clients requests, modeled by TCP flows, are generated and arrive simultaneously to the data center by the 4 core nodes. Next, the flows are spread among the different aggregation switches randomly and then reach the servers. Finally, the requests are handled by servers to answer the clients' requests. The experiment runs on both simulators, SimGrid and ns-3 in order to compare their energy consumption estimation and also their performance in terms of execution time and memory usage. For each point of the simulation, we run several experiments using different random seeds in order to better estimate the accuracy of our proposition.

The energy and scalability results are shown in Figure 5. The energy consumption results show that we have similar values on both simulators. The homogeneous model provide similar results to ns-3 with ECOFEN. Even in the The homogeneous model has a relative error to ECOFEN lower than 4%, which is a reasonable accuracy regarding to its level of granularity. Performance and scalability results are also shown on Figures 5(b) and 5(c). The execution time is clearly higher on ns-3 than on SimGrid. In fact, for 258 requests, ns-3 takes more than 12 hours against only 6 minutes for 897 requests on SimGrid. This is why we stopped ns-3 experiments earlier than SimGrid ones. On this example, SimGrid is more than 120 times faster than ns-3 with ECOFEN. Similarly, the memory usage is also reduced: for 258 requests ns-3 requires 3GB of memory whereas SimGrid uses at most 169.08MB. It is logical since flow level simulators do not model every packets that are transferred from one host to another. Hence, their memory footprint and their computational overhead are drastically reduced. In this case, SimGrid uses 17 times less memory than ns-3.

In this paper, we proposed a network energy model for flow based simulators. We showed that classical models have to be adapted for flow-based simulators due to their coarse grain nature. To evaluate these energy models, we performed microbenchmark experiments. They showed that with simple energy models, we can produce energy consumption estimations close to the ones provided by packet level simulators. We also demonstrated that a fine grain modeling of platforms energy heterogeneity is not required to have suitable energy estimations. Moreover, on simulations of a data center network comprising more than 1,500 servers, we obtained a precision close to packet-level simulators with less than 4% relative error, and with simulation runtimes 120 times faster on flow-level simulators. This realistic use case highlighted how it can be used by the scientific community on large-scale platforms. The implementation is open-source and already available on the website [START_REF] Guegan | Reproducible Experiments Repository[END_REF].

Fig. 1 .

 1 Fig. 1. Homogeneous model on packet/flow level simulators

Fig. 2 .

 2 Fig. 2. Heterogeneous model on packet/flow level simulators

Fig. 3 .

 3 Fig. 3. Microbenchmarks energy consumption on platforms with homogeneous devices.

  (a) Dogbone platform power profile (b) 4 hosts 3 links platform power profile

Fig. 4 .

 4 Fig. 4. Microbenchmarks energy results on heterogeneous energy platforms.

  (a) Overall data center power profile (b) Simulations execution time (c) Simulation memory usage

Fig. 5 .

 5 Fig. 5. Energy and scalability simulations results