Guillaume Fertin
email: fertin@lina.univ-nantes.fr

André Raspaud
email: raspaud@labri.fr

L(p, q) Labeling of d-Dimensional Grids *

In this paper, we address the problem of λ labelings, that was introduced in the context of frequency assignment for telecommunication networks. In this model, stations within a given radius r must use frequencies that differ at least by a value p, while stations that are within a larger radius r > r must use frequencies that differ by at least another value q. The aim is to minimize the span of frequencies used in the network. This can be modeled by a graph coloring problem, called the L(p, q) labeling, where one wants to label vertices of the graph G modeling the network by integers in the range [0; M ], in such a way that (1) neighbors in G are assigned colors differing by at least p and (2) vertices at distance 2 in G are assigned colors differing by at least q, while minimizing the value of M . M is then called the λ number of G, and is denoted by λ p q (G). In this paper, we study the L(p, q) labeling for a specific class of networks, namely the d-dimensional grid G d = G[n1, n2 . . . n d ]. We give bounds on the value of the λ number of an L(p, q) labeling for any d ≥ 1 and p, q ≥ 0. Some of these results are optimal (namely, in the following cases : (1) p = 0, (2) q = 0, (3) q = 1 (4) p, q ≥ 1, p = α • q with 1 ≤ α ≤ 2d and (5) p ≥ 2dq + 1) ; when the results we obtain are not optimal, we observe that the bounds differ by an additive factor never exceeding 2q -2. The optimal result we obtain in the case q = 1 answers an open problem stated by Dubhashi et al. [DMP + 02], and generalizes results from [BPT00] and [DMP + 02]. We also apply our results to get upper bounds for the L(p, q) labeling of d-dimensional hypercubes.

Introduction

In this paper, we study the frequency assignment problem, originally introduced in [START_REF] Hale | Frequency assignment : theory and applications[END_REF], where radio transmitters that are geographically close may interfere if they are assigned close frequencies. This problem arises in mobile or wireless networks. Generally, this problem is modeled by a graph coloring problem, where the transmitters are the vertices, and an edge joins two transmitters that are sufficiently close to potentially interfere. The aim here is to color (i.e. give an integer value, corresponding to the frequency) the vertices of the graph in such a way that :

• any two neighbors (transmitters that are very close) are assigned colors (frequencies) that differ by a parameter at least p ;

• any two vertices at distance 2 (transmitters that are close) are assigned colors (frequencies) that differ by a parameter at least q ;

• the greatest value for the colors is minimized.

It has been proved that under this model, we could assume the colors to be integers, starting from 0 [START_REF] Griggs | Labeling graphs with a condition at distance two[END_REF]. In that case, the minimum range of frequencies that is necessary to assign the vertices of a graph G is denoted λ p q (G), and the problem itself is usually called the L(p, q) labeling problem. The frequency assignment problem has been studied in many different specific topologies [GY92, Sak94, WGM95, BPT00, BKTvL00, CKK + 02, MS02, BPT02, Kra, FKP01]. The case p = 2 and q = 1 is the most widely studied (see for instance [CK96, JNS + 00, Jha00, CP01, FKK01]). Some variants of the model also exist, such as the following generalization, called the L(δ 1 , . . . δ k ) labeling problem, where one gives k constraints on the k first distances (any two vertices at distance 1 ≤ i ≤ k in G must be assigned colors differing by at least δ i ). One of the issues also considered in the frequency assignment problem is the no-hole property, where one wants to know whether a given coloring with span M uses all the possible colors in the range [0; M ].

In this paper, we focus on the L(p, q) labeling problem, and we study in Section 2 the case of the L(p, q) labeling in the d-dimensional grid G d . We first address in Section 2.1 the cases where p = 0 or q = 0. In Section 2.2, we give results for the L(p, q) labeling of G d for any p, q, d ≥ 1. We give lower and upper bounds on λ p q (G d ), and show that in some cases, these bounds coincide. Notably, in the case q = 1, the results we obtain are optimal ; this answers an open problem stated by Dubhashi et al. in [DMP + 02], and generalizes results from [START_REF] Bertossi | Efficient use of radio spectrum in wireless networks with channel separation between close stations[END_REF] and [DMP + 02]. The results we give are also optimal when p = 0, q = 0, p = α • q with 1 ≤ α ≤ 2d, and p ≥ 2dq + 1. We prove that in some cases (namely, when 1 ≤ p ≤ 2dq), one of the colorings we propose satisfies the no-hole property. We also apply our results to get upper bounds for the L(p, q) labeling of d-dimensional hypercubes.

V (G d (n 1 , . . . , n d )) = [1, n 1 ] × [1, n 2 ] × • • • × [1, n d ] E(G d (n 1 , . . . , n d )) = {{u, v} | u = (u 1 , . . . , u d ), v = (v 1 , . . . , v d ),
and there exists i 0 such that ∀i = i 0 , u i = v i , and

|u i0 -v i0 | = 1}
We first address the L(p, q) labeling of G d in the special cases where p = 0 (resp. q = 0) in Section 2.1. We then address the more general case where p, q ≥ 1 in Section 2.2.

2.1 L(p, q) labeling when p = 0 or q = 0 Proposition 1 For any p ≥ 0 and d ≥ 1, λ p 0 (G d ) = p. Proof : Consider an optimal L(p, 0) labeling of the vertices of G d . Clearly, there must exist a vertex, say v, with color c(v) = 0 (if not, then λ p 0 (G d ) could be reduced by at least 1). Then, any neighbor of v must have a color greater than or equal to p. Thus, λ p 0 (G d ) ≥ p. Now, since G d is bipartite, we have that λ p 0 (G d ) ≤ p. Indeed, let us define the following coloring: for any vertex v = (x 1 , x 2 . . . x d ), if d i=1 x i ≡ 0 mod 2, then c(v) = 0, otherwise c(v) = p. Since q = 0, it suffices to check that any two neighbors are assigned colors that differ by at least p. It is clearly the case here, since any two neighbors in G d have the sum of their coordinates of different parity, and thus will be assigned different colors. Since the colors are taken in the set {0, p}, we have that any two neighbors u and v in G d satisfy |c(u)c(v)| ≥ p. Hence we have λ p 0 (G d ) = p. 2 Proposition 2 For any q ≥ 0 and d ≥ 1, λ 0 q (G d ) = (2d -1)q. Proof : Consider a vertex v of degree 2d in G d , and let c(v) be its color in an optimal L(0, q) labeling of G d . In that case, at most one neighbor of v, say w, can satisfy c(v) = c(w). Thus, there remains 2d -1 neighbors of u to color, and since those vertices are at distance 2 from w and from each other, they must use colors that are pairwise q away. Thus, if we assume w.l.o.g. c(v) = c(w) = 0, then the best we can expect for those 2d -1 vertices is that they be assigned colors in the set q, 2q . . . (2d -1)q. Hence, λ 0 q (G d ) ≥ (2d -1)q. Now we give an L(0, q) labeling of G d that uses colors in the set {0, p, 2q . . . (2d -1)q} : for

any vertex v = (x 1 , x 2 . . . x d ) of G d , we define c(v) = (dq x d 2 + d-1 i=1 iqx i ) mod 2dq
Since p = 0, we only need to consider two vertices u and v lying at distance 2 in G d , thus differing on two coordinates, say x i and x j , 1 ≤ i ≤ j ≤ d. W.l.o.g. we can consider only two cases, supposing u = (x 1 , . . . x i . . . x j . . . x d ) :

(1) v = (x 1 , . . . x i + 1 . . . x j + 1 . . . x d ) (where possibly i = j) and (2) v = (x 1 , . . . x i + 1 . . . x j -1 . . . x d ) (where i = j). In case (1), we will distinguish two cases : (1a) i = j and (1b) i = j. In case (1a), we have again two cases two consider : first, if i = j = d, then clearly |c(v)c(u)| = dq, and the condition is satisfied since

d ≥ 1. If i = j = d, then |c(v) -c(u)| = 2iq, since 1 ≤ i ≤ d -1.
Thus the condition is satisfied as well. Now we turn to case (1b), where i = j. W.l.o.g., we thus consider 1 ≤ i < j ≤ d. If j = d, then depending on the parity of x d , we either obtain

|c(v) -c(u)| = iq (for even x d ) or |c(v) -c(u)| = (i + d)q (for odd x d ). In both cases, since i ≤ d -1, we see that the condition is satisfied. Now, if j = d, then |c(v) -c(u)| = (i + j)q
, which also satisfies the condition that the colors differ by at least q.

In case (2), we know that necessarily i = j, and thus we consider as above 1

≤ i < j ≤ d. First, if j = d, then depending on the parity of x d , we either obtain |c(v) -c(u)| = iq (for even x d ) or |c(v) -c(u)| = (d -i)q (for odd x d ). In both cases, the condition is satisfied since 1 ≤ i ≤ d -1. Now, if j = d, we get |c(v)-c(u)| = (j -i)q, which also satisfies the conditions since 1 ≤ i < j ≤ d.
Overall, we see that this coloring satisfies the distance 2 condition, and thus is valid to L(0, q) label G d . Since it uses colors in the set {0, q, 2q, . . . (2d-1)q}, we conclude that λ 0 q (G d ) ≤ (2d-1)q. Hence, altogether we have

λ 0 q (G d ) = (2d -1)q. 2
We note that except in specific cases, the colorings we have given above do not satisfy the no-hole property (we recall that the no-hole property holds when all colors in the range [0; λ p q ] are used). Indeed, in the case q = 0, only colors 0 and p are used, thus the coloring is not no-hole for any p ≥ 2. Similarly, in the case p = 0, the colors used are taken in the set {0, q, 2q . . . (2d -1)q}, thus the coloring is not no-hole for any q ≥ 2.

L(p, q) labeling when p, q ≥ 1

We now address the L(p, q) labeling of G d , for any values of p, q ≥ 1 and d ≥ 1. First, we note that we can obtain two trivial upper bounds on λ p q (G d ) ; this is described in the two following observations.

Observation 1 For any p, q, d ≥ 1, λ p q (G d ) ≤ q • λ p q 1 (G d ). Proof :
The key idea here is to first achieve an L(α, 1) coloring C of G d (thus with λ number λ α 1 (G d )), and to get another coloring C by multiplying the color of each vertex by q. In that case, two vertices at distance 2 in G d , which were assigned different colors by C, are assigned colors differing by at least q in C . Moreover, two neighbors in G d are now assigned colors differing by at least αq. Since we want αq ≥ p, it suffices to take α = p q . 2 There exists another upper bound for λ p q (G d ), that relies on the L(1, 1) labeling of G d . We refer for this to Observation 2 below.

Observation 2 For any p, q, d ≥ 1, λ p q (G d ) ≤ max{p, q} • 2d. Proof : Let C denote the coloring derived from an optimal L(1, 1) of G d , and let C be a new coloring obtained from C by multiplying every color by max{p, q}. In that case, any two vertices at distance 1 (resp. 2) in G d are assigned colors that are at least p (resp. at least q) apart. Hence this is an L(p, q) labeling of G d . Since we know (cf. for instance [START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF] or Theorem 1 below) that

λ 1 1 (G d ) = 2d, we conclude that λ p q (G d ) ≤ max{p, q} • 2d. 2
The two above mentioned simple observations present the disadvantage to be based upon an existing labeling (an L(p, 1) labeling for Observation 1, and an L(1, 1) labeling for Observation 2).

In the following, we study the problem in more details, and define upper and lower bounds on λ p q (G d ) for all values of p, q, d ≥ 1 (resp. in Lemmas 1 and 2). These results directly imply Theorem 1.

Lemma 1 For any p, q, d ≥ 1,

• λ p q (G d ) ≥ 2p + (2d -2)q when 1 ≤ p ≤ 2dq • λ p q (G d ) ≥ p + (4d -2)q when p ≥ 2dq + 1
Proof : Suppose that it is possible to L(p, q) label the vertices of G d with M colors, with M ≤ 2p + (2d -2)q -1. We will first show that in that case, no vertex of degree 2d in G d can be assigned a color in the range [p -1; p + (2d -1)q -1]. Indeed, suppose there exists a vertex u ∈ V (G d ) such that u is assigned color p + x, with -1 ≤ x ≤ (2d -1)q -1. Then, all its neighbors must be assigned a color in the range [0

; x] ∪ [2p + x; M ],
because of the gap of at least p that must exist between neighbors. Within this range, one must be able to get 2d values, each pair of which differ of at least q. Let us distinguish two cases : (i) x = -1 and (ii) x ≥ 0. In case (i), it is clear that all the colors must be in the range [2p -1; M ]. In other words, if we want to be able to assign the 2d colors of the neighbors, we must have 2p -1 + (2d -1)q ≤ M . However, we supposed M ≤ 2p + (2d -2)q -1, hence the contradiction since q ≥ 1. Now suppose that (ii) x ≥ 0 ; we distinguish two more cases : (ii-1) x = kq with k ≥ 0 and (ii-2) x = kqi, with k ≥ 1 and 1 ≤ i ≤ q -1. In case (ii-1), we can use (k + 1) colors in the range [0; kq] (more precisely, colors 0, q, 2q . . . kq). Hence there remains 2d -(k -1) colors to get in the range [2p + x; M ]. For this, we must have 2p + x + (2d -(k -1) -1)q ≤ M . This gives 2p + (2d -2)q ≤ M , a contradiction. In case (ii-2), only k colors can be assigned in the range [0; x]. Thus 2dk colors must be assigned in the range [2p + x; M ], which can be the case only if 2p + x + (2dk -1)q ≤ M . This can happen only when i ≥ q + 1, a contradiction too. Thus we conclude that if λ p q (G d ) = M , no vertex of degree 2d in G d can be assigned a color in the range [p -1; p + (2d -1)q -1]. In other words, if such a coloring exists, all vertices of degree 2d are assigned colors in the range [0; p-2]∪[p+(2d-1)q; M ]. Let I 1 = [0; p-2] and I 2 = [p+(2d-1)q; M ], with M = 2p+(2d-2)q-j, j ≥ 1. Clearly, I 1 contains p -1 integers, and I 2 contains pqj + 1 < p integers (since j, q ≥ 1). This means that if a vertex u of degree 2d in G d is assigned a color in I 1 (resp. I 2 ), all its neighbors must be assigned colors in I 2 (resp. I 1 ) -supposing that all the neighbors of u are of degree 2d, which happens if G d is "big" enough. However, in order for I 1 (resp. I 2 ) to support 2d colors that, pairwise, admit a gap of q, the two following conditions must be fulfilled :

(1) (2d -1)q ≤ p -2 and

(2) p + (2d -1)q + (2d -1)q ≤ M In other words, we must have (1') p ≥ (2d -1)q + 2 and (2') p ≥ 2dq + j. Since j, q ≥ 1, condition (2') implies condition (1'). Thus, in order to have a valid L(p, q) labeling with λ p q (G d ) = M , we must have p ≥ 2dq + j with j ≥ 1. However, we supposed p ≤ 2dq, hence the contradiction. Overall, we have proved that for a sufficiently large grid, and when 1 ≤ p ≤ 2dq, λ p q (G d ) ≥ 2p + (2d -2)q, and the first part of the lemma is proved. Now suppose that p ≥ 2dq + 1. Suppose that λ p q (G d ) = M , with M < p + (4d -2)q. Since we supposed that p ≥ 2dq + 1, we have p + (4d -2)q < 2p + (2d -2)q, we can reuse one of the previous arguments and conclude that no vertex of degree 2d can be assigned a color in the range [p -1; p + (2d -1)q -1]. Hence all the vertices of degree 2d must be assigned colors in [0; p -2] ∪ [p + (2d -1)q; M ]. We also use one of the previous arguments here to say that in that case we must have (1) (2d -1)q ≤ p -2 and (2) p + (2d -1)q ≤ M . However, (2) is not satisfied, hence the contradiction. We then conclude that necessarily, in the case p ≥ 2dq + 1,

λ p q (G d ) ≥ p + (4d -2)q. 2
Lemma 2 For any p, q, d ≥ 1,

• λ p q (G d ) ≤ 2dq when 2 ≤ 2p < q • λ p q (G d ) ≤ 2p + (2d -1)q -1 when 1 ≤ q ≤ 2p ≤ 4dq • λ p q (G d ) ≤ p + (4d -2)q when p ≥ 2dq + 1
Proof : Let p, q, d ≥ 1. In order to prove these upper bounds, we give an ad hoc coloring in each of the two cases, and show that it respects the constraints at distances 1 and 2.

Case 1: 2 ≤ 2p < q. For any vertex v = (x 1 . . . x d ) in G d , with x i ≥ 0 for any 1 ≤ i ≤ d, we assign to v color c(v) defined as follows :

c(v) = ( d i=1 qix i ) mod (2d + 1)q
We are going to prove that this coloring is an L(p, q) labeling of G d . For this, we distinguish two cases :

• u and v are neighbors in G d , thus they differ on one coordinate x i , 1 ≤ i ≤ d. W.l.o.g., suppose u = (x 1 , . . . x i . . . x d ) and v = (x 1 , . . . x i + 1 . . . x d ). In that case |c(v)c(u)| = iq mod (2d + 1)q. Since 1 ≤ i ≤ d, we have that |c(v)c(u)| ≥ q. However, we supposed p < 2q, thus we conclude q > p and |c(v)c(u)| > p.

• u and v lie at distance 2 in G d , thus they differ on two coordinates x i and x j , 1 ≤ i ≤ j ≤ d. W.l.o.g. we can consider only two cases, supposing u = (x 1 , . . . x i . . . x j . . . x d ) : (1) v = (x 1 , . . . x i +1 . . . x j +1 . . . x d ) (where possibly i = j) and (2) v = (x 1 , . . . x i +1 . . . x j -1 . . . x d ) (where i = j). In case (1) we have |c(v)c(u)| = (i + j)q mod (2d + 1)q. Since 1 ≤ i, j ≤ d, we conclude that |c(v)c(u)| ≥ 2q, and thus |c(v)c(u)| ≥ q. In case (2), we have |c(v)c(u)| = (ji)q mod (2d + 1)q. Since 1 ≤ i < j ≤ d (because we supposed that j ≥ i, and since we are in case (2), i = j), we have that |c(v)c(u)| ≥ q. Hence the constraint is satisfied in both cases.

Hence, the above mentioned coloring is an L(p, q) labeling of the grid in the case p, q, d ≥ 1 and 2p < q. Since it uses colors in the set {0, q, 2q, . . . 2dq}, we conclude that λ p q (G d ) ≤ 2dq.

Case 2: 1 ≤ q ≤ 2p ≤ 4dq. For any vertex v = (x 1 . . . x d ) in G d , with x i ≥ 0 for any 1 ≤ i ≤ d, we assign to v color c(v) defined as follows :

c(v) = ( d i=1 (p + (i -1) • q)x i ) mod (2p + (2d -1)q)
We are going to prove that this coloring is an L(p, q) labeling of G d . For this, we distinguish two cases :

• u and v are neighbors in G d , thus they differ on one coordinate x i , 1 ≤ i ≤ d. W.l.o.g., suppose u = (x 1 , . . . x i . . . x d ) and v = (x 1 , . . . x i +1 . . . x d ). Thus |c(v)-c(u)| = (p+(i-1)q). Since 1 ≤ i ≤ d, we have that |c(v)c(u)| ≥ p.

• u and v lie at distance 2 in G d , thus they differ on two coordinates x i and x j , 1 ≤ i ≤ j ≤ d. W.l.o.g. we can consider only two cases, supposing u = (x 1 , . . . x i . . . x j . . . x d ) :

(1) v = (x 1 , . . . x i +1 . . . x j +1 . . . x d ) (where possibly i = j) and (2) v = (x 1 , . . . x i +1 . . . x j -1 . . . x d ) (where i = j). In case (1), |c(u)c(v)| = 2p + (i + j -2)q. In that case, |c(u)c(v)| ≥ q, except maybe when i = j = 1. However, when i = j = 1, then |c(u)c(v)| = 2p, and by hypothesis we know that 2p ≥ q. Thus |c(u)c(v)| ≥ q in all the cases. In case (2), since i = j, we have that j > i. Then we have |c(u)c(v)| = (ji)q. Thus, for any two vertices

u, v ∈ V (G d ) that lie at distance 2, we have |c(u) -c(v)| ≥ q.
Hence, we have proved that the above mentioned coloring is an L(p, q) labeling of the grid in the case p, q, d ≥ 1, 1 ≤ q ≤ 2p ≤ 4dq. Since it uses colors in the range [0; 2p + (2d -1)q -1], we conclude that λ p q (G d ) ≤ 2p + (2d -1)q -1.

Case 3: p ≥ 2dq + 1. In this case, any vertex having an even sum of coordinates will be assigned a color in the range [p + (2d -1)q; p + (4d -2)q], while any vertex having an odd sum of coordinates will be assigned a color in the range [0; (2d -1)q]. More precisely, for any vertex v = (x 1 . . . x d ) in G d , with x i ≥ 0 for any 1 ≤ i ≤ d, we assign to v color c(v) defined as follows :

(1) for any v such that

d i=1 x i ≡ 0 mod 2, c(v) = [( 1 2 d i=1 (2i -1)qx i ) mod (2d -1)q + 1] + (p + (2d -1)q)
(2) for any v such that

d i=1 x i ≡ 1 mod 2, c(v) = [( 1 2 [ d i=1 (2i -1)qx i -odd(q)]) mod (2d -1)q + 1
In order to prove that this is an L(p, q) labeling of G d , let us consider the two following cases :

• u and v are neighbors in G d , thus they differ by one on exactly one coordinate

x i , 1 ≤ i ≤ d. Let u = (x 1 , . . . x i . . . x d ) and v = (y 1 , . . . y i . . . y d ), S(u) = d i=1 x i and S(v) = d i=1 y i .
We clearly see that if S(u) is even, then S(v) is odd and vice-versa. Since in the case where S(u) is even (resp. odd), c(u) ∈ [p + (2d -1)q; p + (4d -2)q] (resp. c(u) ∈ [0; (2d -1)q]), we conclude that in all the cases, |c(v)c(u)| ≥ p.

• Suppose now that u and v lie at distance 2 in G d : thus u and v differ on two coordinates

x i and x j , 1 ≤ i ≤ j ≤ d. W.l.o.g. we can consider only two cases, supposing u = (x 1 , . . . -(a-even) : |c(v)c(u)| = 1 2 ((2i -1)q + (2j -1)q), that is |c(v)c(u)| = (i + j -1)q. Hence, c(u) and c(v) differ by at least q, since 1 ≤ i, j ≤ d.

x i . . . x d ) : (a) v = (x 1 , . . . x i + 1 . . . x j + 1 . . . x d ) (where possibly i = j) and (b) v = (x 1 , . . . x i + 1 . . . x j -1 . . .
-(b-even) : Since i = j let us suppose w.l.o.g. that 1

≤ i < j ≤ d. Hence |c(u) -c(v)| = 1 2 ((2j -1)q -(2i -1)q), that is |c(u) -c(v)| = (j -i)q. Since 1 ≤ i < j ≤ d, c(u) and c(v) differ by at least q.
Resp. values of p and q

λ p q (G d ) ≥ λ p q (G d ) ≤ Gap
No-hole Property p = 0 ; q = 0 p 0 No (except for p = 1) p = 0 ; q = 0 (2d -1)q 0 No (except for q = 1)

p, q ≥ 1 ; 2p < q 2p + (2d -2)q 2dq 2q -2p No q = 1 ; 1 ≤ p ≤ 2d 2p + 2d -2 0 Yes (Prop 4) p, q ≥ 1 ; q ≤ 2p ≤ 4dq 2p + (2d -2)q 2p + (2d -1)q -1 q -1 Yes (Prop 4) p, q ≥ 1 ; p = αq ; α ≤ 2d 2p + (2d -2)q 0 No p, q ≥ 1 ; p = αq + β 1 ≤ β ≤ q -1 ; p ≤ 2dq + β -q 2p + (2d -2)q 2p + 2dq -2β 2(q -β) No p, q ≥ 1 ; p ≥ 2dq + 1 p + (4d -2)q 0 No Table 1: L(p, q) labeling of G d : Summary of the results
Moreover, in the case 1 ≤ q ≤ 2p ≤ 4dq, for sufficiently large grids (that is, when the x i s are large enough for each 1 ≤ i ≤ d), the coloring we propose to achieve an L(p, q) labeling satisfies the no-hole property, that is all the colors in the range [0; 2p + 2(d -1)q -1] are used. This is the purpose of the following Proposition 4 below.

Proposition 4 (No-hole property of L(p, q) labeling of G d , when 1 ≤ q ≤ 2p ≤ 4dq) Let d ≥ 1. In that case, when 1 ≤ q ≤ 2p ≤ 4dq, there exists a no-hole L(p, q) labeling of G d such that λ p q (G d ) = 2p + (2d -1)q -1.

Proof : In Proof of Lemma 2, in the case 1 ≤ q ≤ 2p ≤ 4dq, we assign to any vertex u = (x 1 , x 2 . . . x d ) color c(u) = ( d i=1 (p + (i -1)q)x i ) mod (2p + (2d -1)q). Let U = {u k = (0, 0 . . . 0, 2k)|1 ≤ k ≤ 2p+(2d-1)q} : in other words, in any vertex u k , 1 ≤ k ≤ 2p+(2d-1)q, only the d-th coordinate x d is different from 0, and x d = 2k. In that case, c(u k ) ≡ (p+(d-1)q)•2k mod 2p+(2d-1)q by definition. However, (p+(d-1)q)•2k = (k-1)•(2p+(2d-1)q)+(2p+2(d-1)q-k), hence c(u k ) ≡ 2p + 2(d -1)qk, since k ≤ 2p + (2d -1)q. Since the grid G d is supposed to be sufficiently large, there is no restriction on the choice of x d , and thus on the choice of k. Hence, one can see that each vertex u k of U is assigned a unique color c(u k ) = 2p + (2d -1)qk. Since k takes all the values between 1 and 2p + (2d -1)q, we conclude that the vertices of U are assigned colors that take all the values in the range [0; 2p + (2d -1)q -1]. Hence, the proposed labeling is a no-hole L(p, q) labeling of G d .

2

Clearly, in the other cases, the proposed L(p, q) labelings cannot be no-hole labelings, because some colors are forbidden. Indeed, in the case 2 ≤ 2p < q, colors are taken in the set {0, q, 2q, . . . 2dq}, thus it cannot be a no-hole coloring. In the case p ≥ 2dq + 1, the colors ranging in the interval [(2d -1)q + 1; p + (2d -1)q -1] are forbidden, thus the coloring we suggest cannot be no-hole.

Table 1 summarizes the results obtained in Section 2 concerning bounds for the L(p, q) coloring of G d , for all the possible cases. In this table, we give the lower and upper bounds for λ p q (G d ) ; they are given in bold characters when the bounds coincide. We also mention the gap between the upper and lower bounds when they do not coincide. Finally, in the rightmost column, we state whether the no-hole property holds for the colorings suggested in this paper.

We also mention that the upper bounds we obtain here concerning the L(p, q) labeling of G d are also upper bounds for the L(p, q) labeling of hypercubes of dimension d, H d . Indeed, H d is isomorphic to the grid G d where each x i can take only two values (Hence, there are only two vertices lying in each dimension of the grid). L(2, 1) labeling of the hypercube of dimension d has been studied in [START_REF] Griggs | Labeling graphs with a condition at distance two[END_REF], where the authors proved that d + 3 ≤ λ 2 1 (H d ) ≤ 2d + 1, and where it was conjectured that λ 2 1 (H d ) = d + 3. The upper bound has been improved later in cite [WGM95] thanks to a technique coming from coding theory. However, to our knowledge, the L(p, q) labeling of H d has not been studied for general p and q. Hence, the results stated in Corollary 1 below constitute a first approach for tackling this problem. However, these upper bounds need to be improved.

Corollary 1 (L(p, q) labeling of d-dimensional Hypercubes, for any value of p, q, d ≥ 1) Let p ≥ 1 and d ≥ 1. Then :

• λ p 0 (H d ) = p when p, d ≥ 1 • λ 0 q (H d ) ≤ (2d -1)q when q, d ≥ 1 • λ p q (H d ) ≤ 2dq when 2 ≤ 2p < q • λ p q (H d ) ≤ 2p + (2d -1)q -1 when 1 ≤ q ≤ 2p ≤ 4dq • λ p q (H d ) ≤ 2p + (2d -
2)q when p = αq with p, q ≥ 1 and α ≤ 2d

• λ p q (H d ) ≤ 2p + 2dq -2β when p, q ≥ 1, p = αq + β with 1 ≤ β ≤ q -1 and p ≤ 2dq + β -q • λ p q (H d ) ≤ p + (4d -2)q when p ≥ 2dq + 1
We note that we get the equality λ p 0 (H d ) = p in the case q = 0 since we need to have a gap of at least p between any vertex colored 0 and its neighbor.

We finish this section by mentioning a result for the labeling of G d with k constraints, each equal to 1. This labeling is usually denoted as an L( 1 k ) labeling. The results we give here are derived from a study initiated in [START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF]. This is the purpose of the remark below.

Remark 1 (L( 1 k ) labeling of G d ) In [START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF], the authors have considered the k-distance coloring in the d-dimensional grid G d . k-distance coloring of a graph G is a coloring of its vertices such that two vertices lying at distance less than or equal to k must be assigned different colors. Clearly, k-distance coloring is equivalent to the L( 1 k ) labeling, that is the L(1, 1 . . . 1) labeling with k constraints on the distances, each equal to 1).

In their paper, the authors prove that λ 1 1 (G d ) = 2d for any d ≥ 1. This result appears as a particular result of Theorem 1, when p = q = 1.

Another result from [START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF] addresses the L( 1 k ) labeling problem in the 2-dimensional grid G 2 , for any k ≥ 1. Their result is the following :

• if k is even, then λ( 1 k )[G 2 ] = (k+1) 2 +1 2 -1 ; • if k is odd, then λ( 1 k )[G 2 ] = (k+1) 2 2 -1.
We note that this result has also been independently given in [START_REF] Bertossi | Channel assignment with separation for special classes of wireless networks : Grids and rings[END_REF].

Conclusion

In this paper, we have addressed the frequency assignment problem with constraints on the distances. We have first given general bounds for the λ number when k constraints are given for the k first distances.

We have also addressed the problem of the L(p, q) labeling in d-dimensional grids. These results are optimal in the cases p = 0, q = 0, p ≥ 2dq + 1, p = αq with 1 ≤ α ≤ 2d, and also in the case q = 1 (where in the latter case, our result answers an open question from [DMP + 02], and generalizes results from [DMP + 02] and [START_REF] Bertossi | Efficient use of radio spectrum in wireless networks with channel separation between close stations[END_REF]). The only case where the result is not optimal is when p is not a multiple of q (thus, p = α • q + β, with 1 ≤ β ≤ q -1) and 2 ≤ 2p ≤ 4dq ; in that case, the lower and upper bounds for λ p q (G d ) differ by min{q -1, 2(qβ)} (in the case 2p ≥ q), or by 2q -2p ≤ 2q -2 (in the case 2p < q). We proved that the coloring of the vertices we propose in the case 1 ≤ q ≤ 2p ≤ 4dq, though not necessarily optimal (when q ≥ 2), is a no-hole coloring. We have also derived some upper bounds for the L(p, q) coloring of d-dimensional hypercubes.

Finally, we wish to end this paper by suggesting that, using similar techniques, the results presented here could be extended to the L(p, q, r) labeling problem in d-dimensional grids G d .

2

  L(p, q) labeling of G d We now turn to the case of the λ labeling problem with two constraints on the distances, in a particular network topology, namely the d-dimensional grid G d = G[n 1 , n 2 . . . n d ]. We first recall the definition of such a network. Definition 1 Let d ∈ N and (n 1 , . . . , n d ) ∈ N d , with n i ≥ 2 for any 1 ≤ i ≤ d. The d-dimensional grid of lengths n 1 , . . . , n d , denoted by G d (n 1 , . . . , n d ), is the following graph:

  x d ) (where i = j). We also know that S(u) and S(v) have same parity. Thus for each of the cases (a) and (b), there are 2 cases to consider : (a-even) (resp. (b-even)) in case (a) (resp. (b)) when S(u) and S(v) are even and (a-odd) (resp. (b-odd)) in case (a) (resp. (b)) when S(u) and S(v) are odd. We detail each of those 4 cases below.

* Part of this work was done while both authors were visiting the Universitat Politècnica de Catalunya in Barcelona. This visit was supported by the Egide Spanish-French exchange program PICASSO Number 04295SG.

-(a-odd) : |c(v)c(u)| = 1 2 ((2i -1)q + (2j -1)q), that is |c(v)c(u)| = (i + j -1)q. But since 1 ≤ i ≤ j ≤ d, we conclude that c(u) and c(v) differ by at least q.

-(b-odd) : Since i = j let us suppose w.l.o.g. that 1 ≤ i < j ≤ d. Hence |c(u)c(v)| = 1 2 ((2j -1)q -(2i -1)q), that is |c(u)c(v)| = (ji)q. But since 1 ≤ i < j ≤ d, we conclude that c(u) and c(v) differ by at least q.

Hence, we have proved that the above mentioned coloring is an L(p, q) labeling of the grid in the case p, q, d ≥ 1 with p ≤ 2dq + 1. Since it uses colors in the range [0; (2d -1)q] ∪ [p + (2d -1)q; p + (4d -2)q], we conclude that λ p q (G d ) ≤ p + (4d -2)q. Altogether, this proves the lemma. 2

As a consequence of Lemmas 1 and 2, we have the following theorem.

Theorem 1 (L(p, q) labeling of d-dimensional Grids, for any value of p, q, d ≥ 1) Let p ≥ 1 and d ≥ 1. Then :

When 1 ≤ q ≤ 2p ≤ 4dq, the bounds we get coincide in the case q = 1, thus yielding an optimal L(p, 1) labeling of G d . We note that this generalizes Lemma 5 of [START_REF] Bertossi | Efficient use of radio spectrum in wireless networks with channel separation between close stations[END_REF] By combining some of the previous results, it is possible to improve some of the upper bounds obtained above. More precisely, this is done thanks to a combination of the results from Observation 1 and Theorem 1. This is the purpose of the following proposition.

Proposition 3 For any d ≥ 1 :

• for any q ≥ 1, and any p = αq with 1 ≤ α ≤ 2d, λ p q (G d ) = 2p + (2d -2)q • for any q ≥ 1 and any p = αq + β with 1 ≤ β ≤ q -1 and p ≤ 2dq + βq, λ p q (G d ) ≤ 2p + 2dq -2β

Proof : These two results derive from a combination of Observation 1 and Theorem 1. Suppose first that p = αq, with 1 ≤ α ≤ 2d. By Theorem 1, we know that λ p q (G d ) ≥ 2p + (2d -2)q. We are going to prove that λ p q (G d ) ≤ 2p + (2d -2)q as well. Indeed, by Observation 1, we know that

Hence, we conclude that λ p q (G d ) ≤ q(2α + 2d -2). But since αq = p, we finally have λ p q (G d ) ≤ 2p + (2d -2)q. Now suppose that q ≥ 1, and p = αq + β with 1 ≤ β ≤ q -1. Suppose also that p ≤ 2dq + βq. As previously, we apply Observation 1, which yields

However, since we suppose p ≤ 2dq + βq, this implies p-β q + 1 ≤ 2d, that is α + 1 ≤ 2d. Hence, we now apply Theorem 1, and obtain that λ α+1 1 (G d ) ≤ 2(α + 1) + 2d -2. Thus, altogether, we obtain

We note that in the first case of Proposition 3 above, we obtain the optimal value, while in second case we improve the results of Theorem 1 when p, q, d ≥ 1, β ≥ q+2 2 and p ≤ 2dq + βq. We also note that in all the results presented above, when the bounds do not coincide, they differ by an additive factor at most equal to min{q -1, 2(q -β)} (where β is the rest of the division of p by q) when 1 ≤ q ≤ 2p ≤ 4dq, and equal to 2q -2p ≤ 2q -2 when 2 ≤ 2p < q.


Édgar Roldán

Jérémie Barral

Pascal Martin

Juan M R Parrondo

Frank Jülicher

Arrow of Time in Active Fluctuations

Keywords: numbers: 05.70.Ln, 87.16.dj, 05.40.-a

We introduce lower bounds for the rate of entropy production of an active stochastic process by quantifying the irreversibility of stochastic traces obtained from mesoscopic degrees of freedom. Our measures of irreversibility reveal signatures of time's arrow and provide bounds for entropy production even in the case of active fluctuations that have no drift. We apply these irreversibility measures to experimental spontaneous hair-bundle oscillations from the ear of the bullfrog.

Active systems are maintained out of equilibrium by processes that consume resources of energy and produce entropy. This is the case of living cells, where energy is provided in the form of biochemical fuel such as adenosine triphosphate that drives active mesoscopic cellular processes. An important example of active cellular fluctuations are spontaneous oscillations of mechanosensory hair bundles of auditory hair cells [1,2]. These oscillations have been proposed to amplify sound stimuli in the ear of many vertebrates, providing exquisite sensitivity and sharp frequency selectivity [3].

Active mesoscopic processes do not obey the fluctuation-dissipation theorem: measuring both the linear response of the system to weak external stimuli and spontaneous fluctuations provides a means to quantify deviations from thermal equilibrium [4][5][6][7][8][9]. A related important question is how entropy production can be estimated in active mesoscopic systems. In cases where active systems generate movement with drift, such as molecular motors moving along filaments [10][11][START_REF] Howard | Mechanics of motor proteins and the cytoskeleton[END_REF], the rate of entropy production can be estimated from measurements of drift velocities and viscous forces [10,[START_REF] Qian | [END_REF]. However, for active fluctuations without drift, such as spontaneous oscillations, it is unclear how entropy production can be characterized. Time irreversibility is a signature of the nonequilibrium nature of a system [14]. This suggests that quantification of irreversibility of fluctuations provides information about entropy production.

In this Letter, we introduce a hierarchy of bounds for the steady-state rate of entropy production based on measures of irreversibility of sets of mesoscopic observables. We show that quantifying irreversibility can reveal whether a noisy signal is produced by an active process or by a passive system. We apply the theory to experimental recordings of spontaneous mechanical oscillations of mechanosensory hair bundles in an excised preparation from the ear of the bullfrog (Rana catesbeiana) [15]. Our measures of irreversibility provide lower bounds for en-tropy production of active processes, as we demonstrate using a biophysical model for hair-bundle oscillations and experimental data.

We first discuss the relation between entropy production and irreversibility for generic nonequilibrium stationary processes. Consider a physical system described by a set of variables labeled as X α , with α = 1, 2, . . . . In a stationary nonequilibrium process of time duration t, the physical system traces a trajectory in the phase space described by the stochastic processes X α (t). We denote by Γ [0,t] ≡ {(x 1 (s), x 2 (s), . . . ))} t s=0 a given trajectory described by the system variables and its corresponding time-reversed trajectory as Γ [0,t] ≡ {(θ 1 x 1 (t-s), θ 2 x 2 (ts), . . . )} t s=0 , where θ α = ±1 is the time-reversal signature of the α-th variable. Assume now that X α are the variables that may be out of equilibrium, i.e. we do not include in Γ [0,t] those variables corresponding to thermal reservoirs, chemostats, etc. In that case, the steady-state rate of entropy production σ tot is given by

σ tot = k B lim t→∞ 1 t D P Γ [0,t] P Γ [0,t] , (1)
where k B is the Boltzmann constant and P denotes the steady-state path probability [16][17][18][19]. Here D[Q||R] ≥ 0 is the Kullback-Leibler (KL) divergence between the probability measures Q and R, which quantifies the distinguishability between these two distributions. For measures of a single random variable x the KL divergence is given by D

[Q(x)||R(x)] ≡ dx Q(x) ln[Q(x)/R(x)].
Note that for isothermal systems σ tot T equals to the rate of heat dissipated to the environment at temperature T .

Often in experiments only one or several of the nonequilibrium variables can be tracked in time. Consider the case where only X 1 , . . . X k are known. We define the k-variable rate of entropy production in terms of path probabilities of k mesoscopic variables where

σ k ≡ k B lim t→∞ 1 t D P Γ (k) [0,t] P Γ (k) [0,t] , (2
Γ (k) [0,t] ≡ {(x 1 (s), . . . , x k (s))} t s=0 and Γ (k)
[0,t] ≡ {(θ 1 x 1 (t-s), . . . , θ k x k (t-s))} t s=0 denote paths described by k variables. The average k-variable rate of entropy production increases with the number of tracked degrees of freedom 0

≤ σ 1 ≤ • • • ≤ σ k ≤ σ k+1 ≤ • • • ≤ σ tot .
It can also be shown that the estimator σ k equals the physical entropy production σ tot if the missing variables, X with > k, are at thermal equilibrium [20][21][22]. When the missing variables are not at thermal equilibrium, which is often the case in active systems, the estimator σ k ≤ σ tot yields only a lower bound for the entropy production rate.

We now discuss irreversibility and entropy production in active mechanosensory hair cells from the bullfrog's ear. Hair cells work as cellular microphones that transduce mechanical vibrations evoked by sound into electrical signals [23]. They are endowed with a tuft of cylindrical protrusions -the hair bundle (Fig. 1A)-that serves both as sensory antenna and as active oscillator that amplifies sound [3]. In experimental recordings of spontaneous hair-bundle oscillations, only the tip position X 1 of the bundle is measured (Fig. 1B). Measuring X 1 , we can only estimate σ 1 , which provides a lower bound to the total steady-state entropy production rate σ tot . Spontaneous hair-bundle oscillations are thought to result from an interplay between opening and closing of mechanosensitive ion channels, activity of molecular motors that pull on the channels, and fast calcium feedback. This interplay can be described by two coupled stochastic differential equations for the position of the bundle X 1 and of the motors X 2 [2,15,24]:

λ 1 Ẋ1 = - ∂V ∂X 1 + 2k B T λ 1 ξ 1 (3) λ 2 Ẋ2 = - ∂V ∂X 2 -F act + 2k B T eff λ 2 ξ 2 , (4)
where λ 1 and λ 2 are friction coefficients and ξ 1 and ξ 2 in (3-4) are two independent Gaussian white noises with zero mean ξ i (t) = 0 (i = 1, 2) and correlation ξ i (t)ξ j (t ) = δ ij δ(t-t ), with i, j = 1, 2 and δ ij the Kronecker's delta. T is the temperature of the environment, whereas the parameter T eff > T is an effective temperature that characterizes fluctuations of the motors. The conservative forces derive from the potential associated with elastic elements and mechano-sensitive ion channels

V (X 1 , X 2 ) = k gs ∆X 2 + k sp X 2 1 2 (5)
+ N k B T ln exp k gs D∆X N k B T + A ,
where ∆X = X 1 -X 2 ; k gs and k sp are stiffness coefficients; D is the gating swing of a transduction channel; and

A = exp[(∆G + (k gs D 2 )/2N )/(k B T )],
∆G being the energy difference between open and closed states of the channels and N the number of transduction elements. The force

F act (X 1 , X 2 ) = F max (1 -SP o (X 1 , X 2 )
) is an active nonconservative force exerted by the molecular motors with a maximum value F max . The parameter S quantifies calcium-mediated feedback on the motor force [25] and

P o (X 1 , X 2 ) = 1/[1 + A exp(-k gs D∆X/N k B T )]
is the open probability of the transduction channels. With this model, we can capture key features of noisy spontaneous oscillations of hair-bundle position X 1 that have been observed experimentally (Fig. 1C andD). The oscillation of the motors' position (Fig. 1D) is known in the model but hidden in experiments. Trajectories of only X 1 (t) or X 2 (t) do not reveal obvious signs of a net current, which here would correspond to a drift. However, trajectories in the (X 1 , X 2 ) plane show a net current which is a signature of entropy production (Fig. 1E). In the following, we will use this stochastic model to compare the irreversibility measure σ 1 to the total entropy production σ tot .

In the stochastic model of hair-bundle oscillations given by Eqs. (3)(4) we deal with only two variables, therefore σ tot = σ 2 . From the analytical expression of σ 2 , we find that the steady-state entropy production rate can be written as [26,27]

σ tot = -Q1 1 T - 1 T eff + Ẇact T eff , (6)
where -Q1 = -(∂V /∂X 1 ) • Ẋ1 is the steady-state average heat dissipated to the thermal bath at temperature T and Ẇact = -F act • Ẋ2 is the power exerted by the active force on the motors. Here • denote steady state averages and • the Stratonovich product [28,29]. Equation ( 6) reveals two sources of nonequilibrium in the model: the difference of effective temperature and temperature, and the active force. We now introduce a new method to estimate the irreversibility measure σ 1 for any nonequilibrium steady state from a single stationary time series x i = X(i∆t) (i = 1, . . . , n) of a variable X that is even under time reversal. We describe the technique for a single variable, but it can be generalized to several variables X α (t). In discrete processes, the KL divergence in σ 1 can be accurately measured from the statistics of sequences of symbols [30,31]. In continuous processes however, estimating σ 1 is a herculean task due to the difficulties in sampling the whole phase space of paths [32][33][START_REF] Roldán | Irreversibility and dissipation in microscopic systems[END_REF].

The key idea of our method is to exploit the invariance of the KL divergence under one-to-one transformations. Suppose that there exists a one-to-one map ξ i (x 1 , . . . , x n ), i = 1, . . . , n, that transforms the original time series and its time reversal into two new time series ξ F i = ξ i (x 1 , . . . , x n ) and ξ R i = ξ i (x n , . . . , x 1 ) that are independent and identically distributed (i.i.d.) processes. Such a procedure is often called a whitening filter [START_REF] Efron | [END_REF]36]. Because the new series are i.i.d., the KL divergence is now simple to calculate: it is given by the KL divergence between two univariate distributions p(ξ) and q(ξ), corresponding to the stationary probability distribution of ξ F i and ξ R i , respectively [START_REF] Roldán | Irreversibility and dissipation in microscopic systems[END_REF]. In general, it is not possible to find a one-to-one map that fully eliminates the correlations of both the forward (x 1 , . . . , x n ) and the backward (x n , . . . , x 1 ) time series. In that case, the removal of the correlations in the backward series is enough to provide a lower bound for σ 1 :

σ 1 ≥ k B f s D[p(ξ)||q(ξ)] ≡ σ1 , (7)
where f s = (∆t) -1 is the sampling frequency and D[p(ξ)||q(ξ)] = dξ p(ξ) ln[p(ξ)/q(ξ)] is the KL divergence between the univariate distributions p(ξ) and q(ξ).

We estimate D[p(ξ)||q(ξ)] γ i pi ln(p i /q i ) where p, q are empirical densities, and the sum runs over the number of histogram bins. We introduce the prefactor γ = 1 -p KS ≤ 1, where p KS is the p-value of the Kolmogorov-Smirnov statistic between p(ξ) and q(ξ), to correct the statistical bias of our KL divergence estimate [37]. The proof of the bound (7) and further details of the estimate are found in [29].

In the following, we make use of autoregressive (AR) models for the whitening transformation. More precisely, we obtain the transformed time series ξ F i (ξ R i ) as the difference between the observed values of the forward (backward) time series and the forecast of that value based on an AR model of order m = 10. Parameters of the model are determined from fits of the AR-model to the timereversed series of positions.

Figure 2 illustrates our estimate of σ 1 applied to a representative experimental time series of hair-bundle oscillations, plotted in panel A (top left). The residual time series ξ F i and ξ R i (Fig. 2A, bottom) obtained from the whitening transformation barely have any time correlation (Fig. 2B) and are therefore i.i.d. processes in good approximation. Although the time series and its time reversed (Fig. 2A, top right) do not look different by eye, corresponding to relatively low values of the Kolmogorov-Smirnov p-value (here p KS = 0.06), the measure provided by the KL divergence (Eq. 7) yields σ1 = (4.3 ± 0.8)k B /s revealing that the residual distributions p(ξ) and q(ξ) are different (Fig. 2C), i.e. time irreversibility. Since σ tot ≥ σ 1 ≥ σ1 , Eq. ( 7) implies that our irreversibility measure σ1 provides for this case the bound σ tot ≥ (4.3± 0.8)k B /s for the rate of entropy production. This bound corresponds to an entropy production rate of at least (0.19 ± 0.03)k B per oscillation cycle [29]. Interestingly, this value corresponds to a rate of heat dissipation that is below, here by two orders of magnitude, the estimated mean power output per hair cell ∼ 10k B T /cycle found for spontaneous emissions of sound by the ears of lizards [38]. We apply our method to quantify irreversibility in active oscillatory hair bundles (Fig. 3A, top), in quiescent hair bundles exposed to a drug (gentamicin) that blocks the transduction channels (Fig. 3A, magenta and green) and for noisy signals produced by the recording apparatus when there is no hair bundle under the objective of the microscope (Fig. 3A, black). For sufficiently long recordings, σ1 saturates to a value that exceeds the value obtained for cells exposed to gentamicin and for experimental noise (Fig. 3B). To gain further insights, we apply the local irreversibility measure which obeys ŝ1 (ξ) ≥ 0 for all ξ [39], and σ1 = dξŝ 1 (ξ): for all the analyzed values of ξ, the local irreversibility of active oscillations is ∼ 10 3 times larger than for passive oscillations and experimental noise. Using a population of 182 hair cells that showed spontaneous hair-bundle oscillations [15], we obtained a probability density of σ1 that was well described by an exponential distribution with mean 3 k B /s (Fig. 3C). Interestingly, this result depends on the sampling frequency f s : irreversibility is maximal in the range f s ∼ (200 -600)Hz where its value goes up to 4.3 k B /s. This frequency dependency may provide additional information about timescales of the underlying active process [29]. Finally, we relate these estimates of entropy production from experimental recordings to results obtained for a stochastic model of hair-bundle oscillations. We performed numerical simulations of Eqs. (3)(4) for different values of the control parameters F max and S (Fig. 4) to explore entropy production throughout the state diagram of the system. The quality factor of the oscillation Q -given by the ratio between the oscillation frequency and the bandwidth at half the maximal height of the power spectrum-and the average open probability P o at steady state are displayed in Fig. 4A-B in the state diagram. The irreversibility measure σ1 for trajectories X 1 (t) of spontaneous oscillations is shown in Fig. 4C. This measure can be compared to the quantification of total entropy production σ tot of the model, given by Eq. ( 6), which is shown in Fig. 4D. Irreversibility of trajectories and total entropy production correlate strongly. However, as expected, σ1 provides a lower bound: the rate of entropy production estimated from our measure is here typically three orders of magnitude smaller than the total entropy production. Clearly, measuring other degrees of freedom additional to the hair-bundle position would be required to obtain tighter bounds to the rate of entropy production with our method or other estimation techniques [40][41][42][43][44].

ŝ1 (ξ) ≡ k B f s p(ξ) ln p(ξ) q(ξ) + q(ξ) -p(ξ) , (8)
In summary, we have shown that fluctuations of active systems can reveal the arrow of time even in the absence of net drifts or currents. The hierarchy of measures of time irreversibility introduced here provides lower bounds for the entropy production of an active process. These irreversibility measures can quantify contributions to entropy production in active matter, including living systems, from fluctuations of only a few mesoscopic degrees of freedom. We have here demonstrated the applicability of the approach by estimating entropy production associated with experimental noisy oscillations of a single degree of freedom in the case of mechanosensory hair bundles from the bullfrog's ear.

SUPPLEMENTAL MATERIAL

Here we present additional details of the methods and results discussed in the Main Text. In Secs. and , we provide a derivation of the bound used in Eq. ( 7) in the Main Text, and describe the whitening transformation that we use to estimate irreversibility of stochastic time traces. In Sec. , we provide further details on the experimental results and error analysis for the data shown in Fig. 2 in the Main Text. In Sec. , we provide further details on the experimental results reported in Fig. 3 in the Main Text. In Sec. , we analyze how our irreversibility measure depends on the data sampling rate of the experimental recordings of hair-bundle spontaneous fluctuations. In Sec. we introduce and describe the local irreversibility measure given by Eq. ( 8) in the Main Text. In Sec. , we discuss how entropy production is estimated in numerical simulations of the hair-bundle biophysical model. Section provides details on the calculation of the quality factor of spontaneous oscillations shown in Fig. 4A in the Main Text. In Sec. , we discuss the biophysical model of hair-bundle oscillations and the experimental techniques.

S1. BOUNDS ON THE MULTIVARIATE KULLBACK-LEIBLER DIVERGENCE

Here we prove a general lower bound for the Kullback-Leibler (KL) divergence between two multivariate probability densities P X (x 1 , . . . , x n ) and Q X (x 1 , . . . , x n ) that fulfill the following: there exits a one-to-one map ξ i = ξ i (x 1 , . . . , x n ) with i = 1, . . . , n, such that 1. the transformed variables ξ i are identically distributed under both P and Q, that is, the distributions P Ξ (ξ 1 , . . . , ξ n ) and Q Ξ (ξ 1 , . . . , ξ n ) have, respectively, identical marginal distributions p(ξ) and q(ξ) for any ξ i (i = 1, . . . , n);

2. the transformed variables ξ i are independent and identically distributed (i.i.d.) under the distribution

Q, that is, Q Ξ (ξ 1 , . . . , ξ n ) = Π i q(ξ).
The first step in the derivation is a simple application of the invariance of the KL distance under a one-to-one map:

D [P X (x 1 , . . . , x n )||Q X (x 1 , . . . , x n )] = D [P Ξ (ξ 1 , . . . , ξ n )||Q Ξ (ξ 1 , . . . , ξ n )] . (S9)
Second, we can rewrite the relative entropy as

D [P Ξ (ξ 1 , . . . , ξ n )||Q Ξ (ξ 1 , . . . , ξ n )] = dξ 1 • • • dξ n P Ξ (ξ 1 , . . . , ξ n ) ln P Ξ (ξ 1 , . . . , ξ n ) Π i q(ξ i ) = dξ 1 • • • dξ n P Ξ (ξ 1 , . . . , ξ n ) ln Π i p(ξ i ) Π i q(ξ i ) + P Ξ (ξ 1 , . . . , ξ n ) ln P Ξ (ξ 1 , . . . , ξ n ) Π i p(ξ i ) = nD[p(ξ)||q(ξ)] + D [P Ξ (ξ 1 , . . . , ξ n )||Π i p(ξ i )] . (S10)
Because the KL divergence between two distributions is always positive, Eqs. (S9) and (S10) yield the bound

D [P X (x 1 , . . . , x n )||Q X (x 1 , . . . , x n )] ≥ nD[p(ξ)||q(ξ)] , (S11)
and the inequality saturates if the transformed variables ξ i (i = 1 . . . n) are also i.i.d. under P Ξ (ξ 1 , . . . , ξ n ), i.e. when

P Ξ (ξ 1 , . . . , ξ n ) = Π i p(ξ i ).
If one can find a one-to-one map that transforms the original random variables into i.i.d. variables under both distributions P and Q, then (S11) becomes an equality and the exact KL divergence between the two multivariate distributions P X and Q X can be reduced to the KL divergence between single variable distributions p(ξ) and q(ξ), which is much easier to evaluate from real data. This is the key idea of our method to estimate the irreversibility of experimental time series.

S2. IRREVERSIBILITY IN CONTINUOUS TIME SERIES: THE WHITENING TRANSFORMATION

The estimation of the KL divergence rate from single stationary trajectories of both discrete and continuous random variables have been previously discussed [START_REF] Roldán | Irreversibility and dissipation in microscopic systems[END_REF]. For continuous random variables, the most common strategy is to make a symbolization or discretization of the time series [32]. Then, the KL divergence is estimated from the statistics of substrings of increasing length [30,31]. The main limitation of this method is that one easily reaches lack of statistics even for short substrings. If the observed time series is non-Markovian, this limitation could yield inaccurate bounds for the entropy production. For instance, the KL divergence between two data substrings can be zero in non-equilibrium stationary states without observable currents [30,31,[START_REF] Roldán | Irreversibility and dissipation in microscopic systems[END_REF].

Here we introduce a new method to estimate the KL divergence rate

σ 1 k B ≡ lim t→∞ 1 t D P {x(s)} t s=0 ||P {x(t -s)} t s=0 , (S12)
that is valid for continuous and possibly non-Markovian stochastic processes X(t). First, in practice one has access to discrete-time observations of the process x i ≡ X(i∆t), i = 1, . . . , n, i.e., a time series containing n = t/∆t consecutive samples of the process with sampling rate f s = 1/∆t. The time discretization implies a loss of information yielding a lower bound to the KL divergence rate:

σ 1 k B ≥ f s lim n→∞ 1 n D[P X (x 1 , . . . , x n )||Q X (x 1 , . . . , x n )] , (S13)
where Q X (x 1 , . . . , x n ) = P X (x n , . . . , x 1 ) is the probability to observe the reverse trajectory (x n , . . . , x 1 ).

We can now apply the inequality (S11) to the right-hand side in Eq. (S13) To do that, it is necessary to find a oneto-one map ξ i = ξ i (x 1 , . . . , x n ) that transforms the reverse time series (x n , . . . , x 1 ) into a sequence of n i.i.d. random variables, that is, into a white noise. Such a transformation is usually termed whitening transformation.

An example of whitening transformation is the time series formed by the residuals of an autoregressive model, which is the transformation that we will use along this paper. A discrete-time stochastic process Y i is called autoregressive of order m, AR(m), when its value at a given time is given by a linear combination of its m previous values plus a noise term. Such process is univocally determined by m ≥ 1 real coefficients, a 1 , a 2 , . . . , a m , a discrete-time white noise η i and a set of initial values Y 1 , Y 2 , . . . , Y m . The values of Y i for i > m are given by the linear recursion

Y i = m j=1 a j Y i-j + η i . (S14)
Inspired by the AR(m) process, we introduce the following one-to-one map

ξ i =      x i if i ≤ m x i - m j=1 a j x i-j if i > m , (S15)
which is a linear transformation defined by a unitriangular matrix with Jacobian equal to one. With an appropriate choice of the coefficients a j , one can get a new process (ξ 1 , . . . , ξ n ) which is approximately i.i.d. A good choice is given by a maximum likelihood fit of the process to the AR(m) model. In that case, the elements ξ i in this new time series for i > m are usually called residuals of the original time series (x 1 , . . . , x n ) with respect to the AR(m) model. Notice also that, if (x 1 , . . . , x n ) is indeed a realization of the stochastic process (S14), then the residuals are i.i.d. random variables and the process (ξ m+1 , . . . , ξ n ) has correlations ξ i ξ j = δ ij for all i, j > m.

We now apply the bound (S11) to the KL divergence in the right hand side of Eq. (S13), using the transformation defined by Eq. (S15). Since the contribution of the first, possibly correlated, m values of the time series ξ i , vanishes in the limit n → ∞, we obtain the following lower bound to the KL divergence rate [Eq. (7) in the Main Text]:

σ 1 k B ≥ f s D[p(ξ)||q(ξ)] . (S16)
We can obtain empirical estimates of p(ξ) and q(ξ) from a single stationary time series (x 1 , . . . , x n ) as follows. We apply the transformation (S15) to both the original time series (x 1 , . . . , x n ) and to its time reversal (x n , . . . , x 1 ) obtaining, respectively, two new time series (ξ F 1 , . . . , ξ F n ) and (ξ R 1 , . . . , ξ R n ), which are stationary at least for i > m. The empirical PDFs obtained from the data of each series are estimations of, respectively, p(ξ) and q(ξ). Note that the same transformation (S15) must be applied to both the original time series (x 1 , . . . , x n ) and its time reverse (x n , . . . , x 1 ), but the inequality (S11) only requires uncorrelated residuals in the reverse series. For this purpose, we calculate the coefficients a 1 , . . . , a m by fitting the reverse time series (x n , . . . , x 1 ) to the AR(m) model in Eq. (S14).

As indicated in the previous section, the inequality (S16) is tighter when the residuals are uncorrelated in the forward series as well. This is the case of the experimental series that we have analyzed (see, for instance, Fig. 2B in the Main Text) although, in principle, it is not guaranteed by this procedure. We remark that the inequality (S16) is a rigorous result if the transformation (S15) applied to the reverse time series yields an uncorrelated series

(ξ R 1 , . . . , ξ R n ). In that case, k B f s D[p(ξ)||q(ξ)
] is an estimate of σ 1 with only two possible sources of error: i) the discrete sampling of the process X(t) and ii) the remnant correlation time in the residuals (ξ F 1 , . . . , ξ F n ) obtained from the forward time series.

To summarize, our theory provides an estimate σ1 for the KL divergence rate σ 1 which can be evaluated as follows:

1. Estimate the coefficients, a 1 , . . . , a m , by fitting the time-reversed series (x n , . . . , x 1 ) to an autoregressive AR(m) model of order m > 1. A reasonable choice is m = 10, but it should be tuned to minimize the correlation time in the residuals (ξ R 1 , . . . , ξ R n ).

2. Apply the whitening transformation (S15) to the original series (x 1 , . . . , x n ) and to its time reversal (x n , . . . , x 1 ) to obtain, respectively, new time series (ξ F 1 , . . . , ξ F n ) and (ξ R 1 , . . . , ξ R n ). Note that the new processes are not each other's time reversal.

3. Obtain the empirical distributions p(ξ) and q(ξ) from the time series

(ξ F 1 , . . . , ξ F n ) and (ξ R 1 , . . . , ξ R n ), respectively.
4. Calculate the KL divergence between p(ξ) and q(ξ)

D[p(ξ)||q(ξ)] = dξ p(ξ) ln p(ξ) q(ξ) , ( S17
)
which can be estimated from numerical integration of the right hand side in (S17) using the empirical normalized histograms p(ξ) and q(ξ). We call this estimate D, which is given by

D = γ i pi ln pi qi , ( S18
)
where pi = n F i /( i n F i ) and qi = n R i /( i n R i )
are the empirical probabilities, obtained from the number of times n F i and n R i that the sequences (ξ F 1 , . . . , ξ F n ) and (ξ R 1 , . . . , ξ R n ) lie in the i-th bin, respectively. The sum in (S18) runs over all bins for which n F i > 0 and n R i > 0. For simplicity, we used 100 bins of equal spacing ranging from the minimum to the maximum values of the residual time series (ξ F 1 , . . . , ξ F n ). The value of the estimate D of the KL divergence (S17) is weighted by a prefactor γ ≤ 1 defined in terms of the probability to reject the null hypothesis p(ξ) = q(ξ). We use this procedure to correct the statistical bias in the estimation of the KL divergence that appears when two stochastic processes have similar statistics [31,37]. For this purpose, we use the Kolmogorov-Smirnov (KS) statistical test under the null hypothesis H 0 : p(ξ) = q(ξ) which yields a p-value p KS for the two distributions to be equal. Here, small p KS means that there is stronger statistical evidence in favour of the alternative hypothesis p(ξ) = q(ξ), thus γ = 1 -p KS serves as a weight of irreversibility: γ 0 when it is hard to reject H 0 (reversibility) and γ 1 there is a larger statistical evidence to reject H 0 . 5. Finally, our estimate of σ1 is thus given by the KL divergence estimate D times the Boltzmann constant and the data sampling frequency:

σ1 = k B f s D . ( S19
)
S3. DETAILS OF THE EXPERIMENTAL RESULTS IN FIG. 2 In this section, we describe the procedure used to estimate the bound σ tot ≥ (4.3 ± 0.5)k B /s for the experimental data shown in Fig. 2 in the Main Text. For different values of the observation time t ranging from 1.5s to 30s, we slice the time series x 1 , . . . , x n into N ≥ 1 non-overlapping time series. We then evaluate the estimate σ1 given by Eq. (S19) for each of the slices following the procedure described in Sec. . The value of the irreversibility measure at each time t, denoted by σ1 (t) and shown in Fig. S5, is the average of the estimate σ1 evaluated over the different slices of length t. By fitting σ1 (t) as a function of time t with an exponentially-decreasing function σ1 (t) = A+B exp(-t/τ ), we estimate the mean value of the irreversibility measure from the value of the fitting parameter A. Next, we estimate the error of σ1 (red shaded area in Fig. S5) from the standard deviation of the data points σ1 (t) in the long-time plateau t ≥ 5s > τ , which corresponds to the stationary limit.

S4. DETAILS OF THE EXPERIMENTAL RESULTS IN FIG. 3

In this section, we provide further details of the experimental results shown in Fig. 3 in the Main Text and additional information on the error and statistical analysis of these results.

The results in Fig. 3B of the Main text were obtained as follows. For different values of t ranging from t exp /20 = 1.5s to t exp /2 = 15s (with t exp = 30s the total time of the recording), we analyse N t non-overlapping time series obtained by slicing the experimental time series (x 1 , . . . , x n ), with n∆t = t exp . Here, N t equals to t exp /t rounded to the lowest integer. For each value of t, we obtain N t estimates of σ1 as described by Eq. (S19). The data points plotted in Fig. 3B in the Main Text are given by the average of the N t values of σ1 , and the error bars are the standard deviation of the N t values of σ1 .

The results in Fig. 3C of the Main text were obtained as follows. For each of the 182 experimental recordings of hair bundle oscillations at sampling frequency f s = 2.5 kHz, we estimate σ1 from the residual time series of duration t exp = 30 s and following the procedure described in Sec. .

In Fig. S6A we show the values and error bars of the estimate σ1 obtained following the procedure described in Sec. . Notably, only the time series obtained from active oscillations (cyan, orange, blue and red symbols in Fig. S6A) display values of σ1 (± error bars) that are larger than zero, corresponding to time-irreversible oscillations. Fig. S6B shows the value of the parameter γ = 1 -p KS obtained for these 30s experimental recordings. We recall here that p KS is the Kolmogorov-Smirnov (KS) statistic under the null hypothesis H 0 : p = q. This analysis reveals that recordings obtained from this set of active oscillations are not time-reversal invariant with KS p-value p KS < 0.2 (blue square in Fig. S6B), although two of the cells (green and orange symbols) show p KS < 0.05. In Fig. S6C we show the distribution of γ for the full ensemble of experimental recordings analyzed in this work. We find that in 22% of the experimental recordings, the s distributions p(ξ) and q(ξ) are different with p KS < 0.05, and thus γ > 0.95. The irreversibility measure σ1 for this sub-ensemble of irreversible oscillations, consisting of 41 recordings, displays a distribution with mean equal to 2.4 times the mean of the full ensemble (Fig. S7A). We also compare the irreversibility measure in units of k B per oscillation cycle, i.e. σ1 /f o , where f o is determined from a fit of the power-spectrum density (see Sec. ), and show that the irreversibility of our experimental recordings is on average of the order of 0.2k B /cycle (0.5k B /cycle) for the full (sub-) ensemble of the cells analyzed (Fig. S7B).

Our quantification of irreversibility thus predicts that hair bundles displaying irreversibility with p KS < 0.05 produce entropy at an average rate of at least ∼ 0.5k B per oscillation cycle. Investigating the tightness of the bound σ tot ≥ σ1 is a challenging experimental task since no direct measurements of heat dissipation in spontaneous hair-bundle oscillations have yet been reported. Reference [38] reports experimental estimates of the sound power in spontaneous oto-acoustic emissions by the iguanoid lizard Anolis sagrei. Spontaneous oto-acoustic emissions are weak sounds that are emitted spontaneously by the ears of the animal; these sounds are though to be produced by spontaneous hair-bundle oscillations in the auditory organ of the inner ear. From these measurements, the mean power output of individual hair bundles is estimated to be on average of 141 aW = 1.41 × 10 -16 J/s = 3.37 × 10 4 k B T /s, where k B T = 4.18 × 10 -21 J for T = 30 • C. The oscillation frequency of lizards' hair bundles used in [38] was in the range 1 -8 kHz. Using an average oscillation frequency f o = 3.5kHz, we estimate the mean power output to be on the order of 3.37 × 10 4 k B T /s/(3.5 × 10 3 cycle/s) 10k B T /cycle, i.e. 20 times larger than the average value of our measure of irreversibility (Fig. S7B). We remark here that the results presented in this section and in the Main Text are specific for the sampling frequency f s = 2.5 kHz. In the next section we will discuss how the KS p-value and our bound of entropy production depend on f s .

S5. DEPENDENCY OF THE IRREVERSIBILITY MEASURE ON THE SAMPLING FREQUENCY

In this section, we analyse the dependency of our irreversibility measure on the sampling frequency f s . For this purpose, we evaluate σ1 defined in Eq. (S19) for 30s recordings of the 182 cells that showed spontaneous oscillations at different sampling frequencies, ranging from 125Hz to 2500Hz (the latter corresponding to the data shown in Fig. 3C in the Main text). Figure S8 shows that the distribution of the irreversibility measure depends strongly on the sampling frequency of the data. Notably, the distributions shift towards higher irreversibility when the sampling frequency is reduced, until there is too much filtering f s < 250Hz such that oscillations cannot be distinguished clearly. In Fig. S9 we report the distributions of the parameter γ for the 182 recordings of spontaneous oscillations at different sampling frequencies. For all the analyzed cases, the distributions are right-sweked towards values of γ close to 1. Interestingly, the number of cells that display large γ (i.e. KS p-value p KS < 0.05) attains its maximum in an intermediate frequency range ∼ 200 -600Hz. To gain further insight on this result, we plot in Fig. S10 box plots of the distributions of γ and of the corresponding irreversibility estimate σ1 as a function of the data sampling frequency. Notably, the median of γ is above 0.95 for intermediate sampling frequencies ranging from 208 to 625Hz (Fig. S10A). For values of f s of this frequency band 208 -625Hz, the median of γ is above 0.95 indicating that more than half of the cells display irreversibility with "significant" KS p-value p KS < 0.05 at those frequencies. Within this band, the median of the irreversibility measure σ1 decreases monotonically with f s from 3.5 k B /s (f s = 208 Hz) to 2.6 k B /s (f s = 625 Hz).

S6. LOCAL IRREVERSIBILITY MEASURE

In this section, we introduce a local irreversibility measure σ1 (ξ) that provides further insights about the degree of irreversibility of a time series. For this purpose, we first note, following Shiraishi et al. [39] that the KL divergence between two univariate distributions D[p(ξ)||q(ξ)] can be written as follows

D[p(x)||q(x)] = dx p(x) ln p(x) q(x) (S20) = dx p(x) ln p(x) q(x) + q(x) -p(x) ≡s[p(x)||q(x)]≥0 , (S21)
where in the second line we have used the fact that both p and q are normalized, i.e. dx p(x) = dx q(x) = 1. In Ref. [39] it was shown that the function s[p(x)||q(x)] = p(x) ln p(x) q(x) + q(x) -p(x) is positive, and thus provides a local distance between two probability densities p(x) and q(x) i.e. at a given value of the random variable x. Following the irreversibility estimate provided by Eq. (S19) we can define the local irreversibility as

s 1 (ξ) = k B f s p(ξ) ln p(ξ) q(ξ) + q(ξ) -p(ξ) , (S22)
which obeys by definition σ 1 = dξ s 1 (ξ). Figure S11 shows estimates of s 1 (ξ) obtained for the seven time series reported in Fig. 3(A-B) in the Main Text. The estimate ŝ1 (ξ) is obtained by replacing p(ξ) and q(ξ) in Eq. (S22) by the corresponding empirical densities. Notably, active cells exhibit larger values of irreversibility than passive cells: at any value of the residual ξ of the whitening transformation, we find ŝact 1 (ξ) ≥ ŝpass 1 (ξ). Moreover, typical values of local irreversibility are in the range ŝact 1 (ξ) ∼ 0.1k B /s for such active cells and ŝpass 1 (ξ) ∼ 10 -4 k B /s for the passive cells, and the latter is comparable to the result obtained for the experimental noise.

We evaluate in Fig. S11 the local irreversibility measure for three representative experimental time series (Fig. S11A). We plot in Fig. S11B the residual distributions corresponding to the active cell in Fig. 2 in Main Text (blue), an active cell whose time series exhibits large jumps (red) and experimental noise (green). The active cell with larger jumps produces the most noticeable difference of the residual distributions at the tails |ξ| ≥ 0.5. Notably, we show in Fig. S11C that the local irreversibility measure for the active cells is three orders of magnitude larger than its value for the passive oscillation, throughout all the range of values of the residuals. Furthermore, the contributions to the local irreversibility measure from central and extreme residuals are of the same order of magnitude, for both typical and atypical (large jumps) active oscilaltions.

S9. BIOPHYSICS OF MECHANOSENSORY HAIR BUNDLES

Details of the experimental procedure have been published elsewhere [2]. In short, an excised preparation of the bullfrog's (Rana catesbeiana) sacculus was mounted on a two-compartment chamber to reproduce the ionic environment of the inner ear. This organ is devoted to sensitive detection of low-frequency vibrations (5 -150 Hz) of the animal's head in a vertical plane; it contains about 3000 sensory hair cells that are arranged in a planar epithelium. The basal bodies of hair cells were bathed in a standard saline solution and the hair bundles projected in an artificial endolymph. The preparation was viewed through a ×60 water-immersion objective of an upright microscope. Under these conditions, spontaneous hair-bundle oscillations were routinely observed. The oscillations could be recorded by imaging, at a magnification of ×1000, the top of the longest stereociliary row onto a displacement monitor that included a dual photodiode. Calibration was performed by measuring the output voltages of this photometric system in response to a series of offset displacements. Here, we analyzed 182 spontaneously oscillating hair bundles from data previously published [15].

Spontaneous hair-bundle oscillations were described by a published model of active hair-bundle motility [2] that rest on a necessary condition of negative hair-bundle stiffness, on the presence of molecular motors that actively pull on the tip links, and on feedback by the calcium component of the transduction current. Hair-bundle deflections affect tension in tip links that interconnect neighbouring stereocillia of the bundle. Changes in tip-link tension in turn modulate the open probability of mechano-sensitive ion channels connected to these links. Importantly, the relation between channel gating and tip-link tension is reciprocal: gating of the transduction channels affects tip-link tension. Consequently, channel gating effectively reduces the stiffness of a hair bundle, a phenomenon appropriately termed "gating compliance", which can result in negative stiffness if channel-gating forces are strong enough. Active hair-bundle movements result from the activity of the adaptation motors. By controlling tip-link tension, adaptation motors regulate the open probability of the mechanosensitive channels. The force produced by the motors is in turn regulated by the Ca 2+ component of the transduction current which thus provides negative feedback on the motor force [2]. When the fixed point of this dynamical system corresponds to an unstable position of negative stiffness, the system oscillates spontaneously. The maximal force exerted by the motors F max and the calcium feedback strength S are control parameters of the system and fully determine its dynamics (oscillatory, quiescent, bi-stable) [25].

  FIG. 1:(A) Electron micrograph of a hair-cell bundle extracted from the bullfrog's inner ear. The distance from top to bottom is ∼ 7µm. (B) Experimental recording of the tip position of an active mechanosensory hair bundle that displays spontaneous oscillations. (C,D) Trajectories of the reduced variables X1 (C) and X2 (D) as a function of time obtained from a simulation of the stochastic model given by Eqs. (3-4). (E) Representation of a 2-s trace of the simulations in (C,D) in the {X1(t), X2(t)} plane. The black arrows illustrate the value of the instantaneous velocity and the base of the arrow the position. Parameters of the simulations: λ1 = 0.9 pNms/nm, λ2 = 5 pNms/nm, kgs = 0.55 pN/nm, ksp = 0.3 pN/nm, D = 72 nm, S = 0.73, Fmax = 45.76 pN, N = 50, ∆G = 10kBT , kBT = 4.143 pNnm and T eff /T = 1.5.

FIG. 2 :

 2 FIG. 2: Illustration of the method to quantify time irreversibility σ1 from an experimentally obtained stochastic time series xi of the tip position of a hair bundle partially shown in top left panel in (A) (blue line). (A) Top: Time series (top left, blue line) and time-reversed series (top right, red line) normalized by their standard deviation. Bottom: residual time series ξ F i (bottom left, blue line), ξ R i (bottom right, red line) given by the difference between the original series and their predictions from an autoregressive model of order 10 fitted to the time-reversed series. (B) Autocorrelation function of the forward time series xi (black "+"), and the residual time series ξ F i (blue filled squares) and ξ R i (red open circles). (C) Empirical probability densities of the time series ξ F i (p(ξ), blue filled squares) and ξ R i (q(ξ), red open circles). The data corresponds to a 30-s recording of the tip position of an active hair bundle with oscillation frequency fo = 23 Hz and sampling rate fs = 2.5 kHz.

FIG. 3 :

 3 FIG. 3: (A) Examples of experimental traces for the tip position of different mechanosensory hair bundles as a function of time. Top: active hair bundles. Bottom: passive hair bundles, i.e. when the channel blocker gentamicin is present (magenta, green), and experimental noise trace (black). The data used in Fig. 2 corresponds to the oscillation shown here in red. (B) Irreversibility measure σ1 (symbols) as a function of the observation time obtained from the experimental traces partially shown in (A). (C) Estimate of the local irreversibility measure (8) obtained from single 30s recordings of the oscillations shown in panel A as a function of the residual value ξ. (D) Histogram of the irreversibility measure σ1 obtained from 182 experimental recordings of spontaneous active oscillations of the hair bundle of duration texp = 30 s. The experimental average value of the irreversibility measure σ1 is ∼ 3kB/s. Inset: Empirical cumulative distribution function (CDF) of irreversibility (black circles). The red line is a fit to an exponential distribution with mean value (2.82±0.02)kB/s and R 2 > 0.9990. The sampling rate was fs = 2.5 kHz.

FIG. 4 :

 4 FIG. 4: Dynamical and thermodynamic features of spontaneous hair-bundle oscillations as a function the calciumfeedback strength S and maximal motor force Fmax obtained from numerical simulations of the model given by Eqs. (3-4): (A) Quality factor Q; (B) Steady-state average of the open channel probability Po ; (C) Irreversibility measure σ1; (D) Steady-state entropy production rate σtot. In (B,C,D) we indicate the parameter values for which Po = 0.1, 0.5 and 0.9 (white dashed lines from top to bottom, respectively). The results are obtained from numerical simulations of Eqs. (3-4) of total duration tsim = 300 s, sampling frequency fs = 1 kHz and parameter values λ1 = 2.8 pNms/nm, λ2 = 10 pNms/nm, kgs = 0.75 pN/nm, ksp = 0.6 pN/nm, D = 61 nm, ∆G = 10kBT , kBT = 4 pNnm and T eff /T = 1.5.

  FIG. S5:Values of the irreversibility measure σ1 (red squares) evaluated for time traces of t ≤ τexp, with τexp = 30 s, obtained for the experimental recording shown in Fig.2in the Main Text. The solid line is a fit of the data to a function σ1(t) = A + B exp(-t/τ ). Parameters of the fit: A = 4.3kB/s, B = 16kB/s, τ = 2s. Goodness of fit R 2 = 0.87. The red shaded area is centred in the long-time value A and its width equals to the standard deviation of the values σ1(t) with t ≥ 5s (see histogram in the inset), which provides the mean and the error on the steady-state value of σ1 ≥ (4.3 ± 0.8)kB/s.

FIG

  FIG. S6: (A)Irreversibility measure σ1 for the oscillations depicted in Fig.3Aof the Main Text. The value and error bars are obtained as described in Sec. . The horizontal dotted line is set to zero as a guide to the eye. (B) Value of the parameter γ = 1 -pKS for the same oscillations, with pKS the p-value of the Kolmogorov-Smirnov statistic for the distributions of the residuals ξ F and ξ R to be the identical. (C) Histogram of γ obtained from 182 experimental recordings of hair bundle oscillations each with duration of 30s. The vertical dashed line is set to a common threshold of the Kolmogorov-Smirnov parameter γ = 0.95, which corresponds to 22% of the recordings. The sampling frequency of the oscillations is fs = 2.5 kHz.

  FIG.S7: Histograms of the irreversibility measure σ1 in units of kB/s (A) and in units of kB per oscillation cycle (B). The histograms were obtained from the full ensemble of 182 oscillatory hair cells (turquoise bars) and from the sub-ensemble of 66 cells that display irreversibility in the residuals with Kolmogorov-Smirnov parameter γ ≥ 0.95 (yellow bars). The sampling frequency of the oscillation is here fs = 2.5 kHz.

  FIG. S8: Histograms of the irreversibility measure σ1/kB for different values of the sampling frequency fs indicated above each panel of the figure. All the histograms were obtained from the same ensemble of 182 oscillatory hair cells that displayed active oscillations.

  FIG.S9: Histograms of the parameter γ = 1 -pKS with pKS given by the Kolmogorov-Smirnov p-value for different values of the sampling frequency fs indicated above each panel of the figure. All the histograms were obtained from the same ensemble of 182 oscillatory hair cells that displayed active oscillations.

  FIG.S10: Box plot of the parameter γ (A) and of the irreversibility measure σ1 (B) as a function of the sampling frequency obtained from recordings of the tip position of hair bundles in the entire population of 182 cells. The yellow dashed line in (A) is set to the threshold γ = 0.95 corresponding to the Kolmogorov-Smirnov p-value pKS < 0.05. In (B), we highlight (horizontal yellow thick lines) the median of the distributions of σ1 for which the median value of γ is larger than 0.95.

  FIG. S11:(A) Snapshots of duration 0.5s extracted from 30s-experimental recordings of the position of the tip of two active hair bundles (top blue and middle red) and of experimental noise, normalized by the time series standard deviation. Empirical probability density ((B)) of the residuals p(ξ) (filled squares) and q(ξ) (open circles), and local irreversibility measure ((C)) given by Eq. (S22) for the time series partially shown in (A).

  FIG. S12: Estimation of the quality factor Q from numerical simulations of the hair bundle. (A) Values of the quality factor Q calculated from numerical simulations of duration tsim = 300 s for the same parameter values as in Fig. 4 in the Main Text. (B) Examples of 0.5-second traces of X1 as a function of time for the parameter values indicated in A: B.1) [1 in (A)]; B.2) [2 in (A)], B.3) [3 in (A)]; B.4) [4 in (A)]. (C) Power spectral density (black line) of the numerical simulations with parameter values indicated with black open circles in (A). The quality factor is estimated from a fit of the power spectra to Eq. (S26) (red line). The values of Q and fo extracted from the fits are: Q = 0.5, fo = 7.3 Hz (C.1), Q = 7, fo = 25 Hz (C.2), Q = 0.45, fo = 10.6 Hz (C.3), Q = 3.8, fo = 41.3 Hz (C.4).

We thank Peter Gillespie for providing the hair-bundle picture used in Fig. 1A. We acknowledge stimulating discussions with Izaak Neri, Andre C. Barato, Simone Pigolotti, Johannes Baumgart, Jose Negrete Jr, Ken Sekimoto, Ignacio A. Martínez, Patrick Pietzonka and A.J. Hudspeth.

S7. QUANTIFICATION OF ENTROPY PRODUCTION IN NUMERICAL SIMULATIONS OF HAIR BUNDLE OSCILLATIONS

In this Section, we provide numerical results for the stochastic model of the ear hair bundle given by Eqs. (3)(4)(5) in the Main Text. The steady-state entropy production rate of the model is given by

where

) and • denotes the Stratonovich product. Using the definitions of the forces in Eq. (S23) one obtains after some algebra Eq. ( 6) in the Main Text. In all our numerical simulations, we estimate the steady-state averages of the type

for a generic force

) from a single stationary trajectory of total duration t sim = 300 s and sampling time ∆t = 1 ms as follows:

where t i = i∆t and n = t sim /∆t.

S8. ESTIMATION OF THE QUALITY FACTOR OF STOCHASTIC OSCILLATORS

We estimate the quality factor Q of spontaneous hair-bundle oscillations from numerical simulations of the hairbundle stochastic model given by Eqs. (3)(4) in the Main Text. For this purpose, we generate a single numerical simulation of duration t sim = 300 s. We then partition the simulation into 10 consecutive traces of duration T = t sim /10 = 30 s. For each of these traces {X α (t)} (α = 1, . . . , 10) we compute the power spectral density as

where Q is the quality factor, f o is the oscillation frequency and A > 0 is an amplitude parameter. Figure S12 shows examples of numerical simulations for which we apply this procedure to determine the value of the quality factor by extracting the value Q from the fit of the data to Eq. (S26). Notably, Eq. (S26) reproduces power spectra of hair-bundle simulations for oscillations with values Q that are in a wide range of orders of magnitude (Fig. S12C).