Mario Kummer

Simone Naldi

Daniel Plaumann

SPECTRAHEDRAL REPRESENTATIONS OF PLANE HYPERBOLIC CURVES

We describe a new method for constructing a spectrahedral representation of the hyperbolicity region of a hyperbolic curve in the real projective plane. As a consequence, we show that if the curve is smooth and defined over the rational numbers, then there is a spectrahedral representation with rational matrices. This generalizes a classical construction for determinantal representations of plane curves due to Dixon and relies on the special properties of real hyperbolic curves that interlace the given curve.

Introduction

Determinantal representations of plane curves are a classical topic in algebraic geometry. Given a form f (i.e. a homogeneous polynomial) of degree d in three variables with complex coefficients and a general form g of degree d -1, there exists a d × d linear matrix M = xA + yB + zC such that f is the determinant of M and g a principal minor of size d -1 (see for example [START_REF] Dolgachev | Classical algebraic geometry: a modern view[END_REF]Ch. 4]). The matrix M can be chosen symmetric if g is a contact curve, which means that all intersection points between the curves defined by f and g have even multiplicity. The construction of M from f and g is due to Dixon [START_REF] Cardew | Note on the reduction of a ternary quantic to a symmetrical determinant[END_REF] (following Hesse's much earlier study of the case d = 4). We refer to this construction as the Dixon process.

For real curves, the most interesting case for us is that of hyperbolic curves. The smooth hyperbolic curves are precisely the curves whose real points contain a set of d 2 nested ovals in the real projective plane (plus a pseudo-line if d is odd). A form f ∈ R[x, y, z] is hyperbolic if and only if it possesses a real symmetric determinantal representation f = det(M ) such that M (e) = e 1 A + e 2 B + e 3 C is (positive or negative) definite for some point e ∈ P 2 (R). This is the Helton-Vinnikov theorem, which confirmed a conjecture by Peter Lax [START_REF] Helton | Linear matrix inequality representation of sets[END_REF].

The Helton-Vinnikov theorem received a lot of attention in the context of semidefinite programming, which was also part of the original motivation: The set of points a ∈ R 3 for which the matrix M (a) is positive semidefinite is a spectrahedron:

S(M ) = {a ∈ R 3 : M (a) 0}.
It coincides with the hyperbolicity cone C(f, e) of f = det M in direction e, that is the closure of the connected component of {a ∈ R 3 : f (a) = 0} containing e. This is a convex cone in R 3 , whose image in P 2 is the region enclosed by the convex innermost oval of the curve (see Figure 1). A triple of real symmetric matrices A, B, C is a spectrahedral representation of C(f, e) if M = xA + yB + zC satisfies C(f, e) = S(M ).

Figure 1. A quintic hyperbolic curve (blue), a quartic interlacer (green), and the hyperbolicity region (green region) It has been pointed out by several authors [START_REF] Plaumann | Determinantal representations of hyperbolic plane curves: an elementary approach[END_REF][START_REF] Vinnikov | LMI representations of convex semialgebraic sets and determinantal representations of algebraic hypersurfaces: past, present, and future[END_REF] that the proof of the Helton-Vinnikov theorem becomes much simpler if one requires the matrix M to be only hermitian, rather than real symmetric. In that case, M can be constructed via the Dixon process starting from any interlacer of f : That is, any hyperbolic form g of degree d -1 whose ovals are nested between those of the curve defined by f (see Figure 1). One downside of this apparent simplification is that the corresponding determinantal representation f = det(M ) with principal minor g is harder to construct explicitly, since one has to find the intersection points of f and g, while this can be avoided if g is a contact curve. We refer to [START_REF] Vinnikov | LMI representations of convex semialgebraic sets and determinantal representations of algebraic hypersurfaces: past, present, and future[END_REF] for a survey of these results.

In this paper, we study a modification of the Dixon process, which can be described as follows: Given a form f of degree d, hyperbolic with respect to e, and an interlacer g of degree d -1, we construct a real symmetric matrix pencil M with the following properties:

• The determinant det(M ) is divisible by f . • The principal minor det(M 11 ) is divisible by g.

• The extra factors det(M )/f and det(M 11 )/g are products of linear forms.

• The spectrahedron defined by M coincides with C(f, e).

The extra factor in our spectrahedral representation of C(f, e) is an arrangement of real lines, as in Figure 2. Informally speaking, these additional lines correct the failure of g to be a contact curve by passing through the intersection points of g with f that are not of even multiplicitity.

The precise statement is Theorem 2.2. The size of M is at most quadratic in d. Thus while M may not be the smallest or simplest determinantal representation of (some multiple of) f , it is easier to construct and may better reflect properties of the hyperbolicity region C(f, e): as a corollary, we show that if f has coefficients in Q, then C(f, e) can be represented by a linear matrix inequality with coefficients in Q (Cor. 2.10). We may also view Theorem 2.2 in the context of the Generalized Lax Conjecture, which states that every hyperbolicity region (in any dimension) is Figure 2. The extra factor (dashed blue lines) giving the spectrahedral representation of the hyperbolicity region spectrahedral. While various stronger forms of this conjecture have been disproved, it remains open as stated. One obstacle for constructing symmetric determinantal representations in higher dimensions is the nonexistence of contact interlacers for general hyperbolic hypersurfaces. Since our generalized Dixon process does not require the interlacer to be contact, it is possible that a spectrahedral description of the hyperbolicity cone could be constructed in a similar way, but this is currently purely speculative. In §3 we point out how our construction is related to sum-ofsquares decompositions of Bézout matrices and the construction in [START_REF] Kummer | Determinantal representations and Bézoutians[END_REF].

Even in the original Dixon process for plane curves, details are somewhat subtle: For the construction to succeed as stated, the curve defined by f must be smooth, and the existence of a contact curve satisfying the required genericity assumption (equivalent to the existence of a non-vanishing even theta characteristic) was not rigourously established until somewhat later. Additionally, the case of singular curves was, to our knowledge, only fully settled and explicitly stated by Beauville in 2000 [START_REF] Beauville | Determinantal hypersurfaces[END_REF]. Likewise, in our generalized Dixon process, we need to treat degenerate cases with care and need some genericity assumptions.

Our generalized Dixon process has the additional feature that the size of the matrix M decreases if the interlacer g has real contact points with f . In particular, if g is an interlacer with only real intersection points, our statement reduces to that of the Helton-Vinnikov theorem. This leads us to the study of interlacers with real intersection (i.e. contact) points. Such interlacers are necessarily on the boundary of the cone Int(f, e) of all interlacers of f . An extreme ray of that cone will necessarily have a certain number of real contact points (Lemma 1.3). However, we do not know whether there always exists an interlacer with the maximal number d(d -1)/2 of real contact points. Even in the case d = 4, we only obtain a partial answer to this question (see §1.1). There remain interesting (and easily stated) open questions concerning interlacing curves and the geometry of the interlacer cone.

Extremal interlacers

Let f ∈ R[x, y, z] be homogeneous of degree d and hyperbolic with respect to e = (0 : 0 : 1), with f (e) > 0. Let C = V C (f ) be the plane projective curve defined by f . We denote by C(f, e) the closed hyperbolicity region of f with respect to e in the real projective plane. Definition 1.1. Let f, g ∈ R[t] be univariate polynomials with only real zeros and with deg(g

) = deg(f ) -1. Let α 1 ≤ • • • ≤ α d be the roots of f , and let β 1 ≤ • • • ≤ β d-1
be the roots of g. We say that g interlaces f if α i β i α i+1 holds for all i = 1, . . . , d -1. If all these inequalities are strict, we say that g strictly interlaces f .

If f ∈ R[x, y, z] is hyperbolic with respect to e and g is homogeneous of degree deg(f ) -1, we say that g interlaces f with respect to e if g(te + v) interlaces f (te + v) for every v ∈ R 3 . This implies that g is also hyperbolic with respect to e. We say that g strictly interlaces f if g(te + v) strictly interlaces f (te + v) for every v ∈ R 3 not in Re.

With f as above, let g be any form in R[x, y, z] coprime to f . We say that an intersection point p ∈ V C (f, g) is a contact point of g with f if the intersection multiplicitity mult p (f, g) is even. If all intersection points are contact points, then g is called a contact curve of f . A curve of real contact is a curve g for which all real intersection points are contact points, without any assumption on non-real intersection points. Any interlacer is a curve of real contact.

Interlacers of f appear naturally in the context of determinantal representations of f (see [START_REF] Kummer | Hyperbolic polynomials, interlacers, and sums of squares[END_REF][START_REF] Plaumann | Determinantal representations of hyperbolic plane curves: an elementary approach[END_REF]). For example, if f = det(xA + yB + zC) is a real symmetric and definite determinantal representation of f , then every principal (d-1)×(d-1) minor of xA+yB +zC is an interlacer of f (see [START_REF] Plaumann | Determinantal representations of hyperbolic plane curves: an elementary approach[END_REF]Thm. 3.3]). Furthermore, such a minor defines a contact curve (see e.g. [START_REF] Plaumann | Determinantal representations of hyperbolic plane curves: an elementary approach[END_REF]Prop. 3.2]). Conversely, given any interlacer of f that is also a contact curve, one can construct a definite determinantal representation of f and therefore a spectrahedral representation of its hyperbolicity region of size d×d. However, for computational purposes, it is very difficult to actually find such an interlacer, even though its existence is guaranteed by the Helton-Vinnikov Theorem [START_REF] Helton | Linear matrix inequality representation of sets[END_REF]. In Section 2, we will introduce a method for constructing from an arbitrary interlacer a spectrahedral representation of possibly larger size. We denote by

Int(f, e) = g ∈ R[x, y, z] d-1 : g interlaces f and g(e) > 0
the set of interlacers of f . It is shown in [START_REF] Kummer | Hyperbolic polynomials, interlacers, and sums of squares[END_REF]Cor. 2.7] that this is a closed convex cone. Every boundary point of this cone has at least one contact point. In order to find interlacers with many contact points, it is therefore natural to consider extreme rays of this cone. Definition 1.2. Let f be hyperbolic with respect to e. By an extremal interlacer of f we mean an extreme ray of the cone Int(f, e).

The next lemma gives a lower bound on the number of real contact points of an extremal interlacer. real contact points with f , counted with multiplicity.

Proof. Let g be an extremal interlacer and let k be the number of real contact points of g. By definition, the real part of the divisor div C (g) is even, say 2D, with D real and effective of degree k. The space V of forms h of degree d -1 with div C (h) 2D has dimension at least n = (d + 1)d/2 -2k and contains g. If n > 1, then V contains another form h linearly independent of g. We conclude that g ± εh ∈ Int(f, e) for sufficiently small ε. Thus g is not extremal. Therefore, we must have n 1, which gives k (d+1)d-2 4 .

Remark 1.4. For smooth f , given any d -1 real points on the curve, there is an extremal interlacer touching the curve in (at least) the given points. Indeed, it is clear from the above proof that it suffices to show that there is an interlacer passing through these d -1 points. The quadratic system of interlacers considered in [START_REF] Plaumann | Determinantal representations of hyperbolic plane curves: an elementary approach[END_REF]Def. 3.1] has dimension d, so we can prescribe d -1 points.

Remark 1.5. We do not know whether every hyperbolic curve possesses an irreducible extremal interlacer. This is true if C is a smooth cubic: For any two distinct points p and q on C, there is an extremal interlacing conic Q passing through p and q, by the preceding remark. If Q is reducible, it must factor into the two tangent lines to C at p and q. But Q is a contact curve by Lemma 1.3, hence the intersection point of the two tangents must lie on C. Clearly, this will not be the case for a generic choice of p and q. This observation will be used at one point later on. It does not seem clear how to generalize this argument to higher degrees.

The following table shows the expected number of real contact points of an extremal interlacer compared with the number of points for a full contact curve.

d 2 3 4 5 6 • • • (d+1)d-2 4 1 3 5 7 10 • • • d(d-1) 2
1 3 6 10 15 • • •
An interlacer can have many more real contact points than the estimate given by Lemma 1.3 and we do not know whether there is always one with only real intersection points. Question 1.6. Does every hyperbolic plane curve have an interlacer that intersects the curve only in real points?

Even without the interlacing condition, it seems to be unknown whether a real curve always possesses a real contact curve with only real contact points. In the case of plane quartic curves we have some partial answers to that question.

1.1. The case of quartics. Let C ⊆ P 2 be a smooth hyperbolic quartic that has a real bitangent touching C in only real points. We will show that in this case there is a contact interlacer touching C only in real points. It suffices to show that there is a conic touching both ovals in two real points. This, together with the above bitangent, will be the desired totally real interlacer.

Assume that C(R) is contained in the affine chart z = 0 (for smooth quartic curves this is not a restriction). Let l ∈ R[x, y] 1 be a nonzero linear form. Maximizing and minimizing l on the hyperbolicity region gives us two different linear polynomials l 1 and l 2 that are parallel and whose zero sets are tangent to the inner oval at some points p 1 and p 2 (see Figure 6).

Choose the signs such that both l 1 and l 2 are nonnegative on the inner oval. We consider the pencil of conics whose zero sets pass through p 1 and p 2 such that the tangent lines of the conics at p 1 and p 2 are defined by l 1 and l 2 respectively. This pencil is given by q λ = g 2 -λl 1 l 2 , λ ∈ R, where g is the line spanned by p 1 and p 2 . The zero set of q λ is completely contained in the interior of the outer oval for small λ > 0. Label the two half spaces defined by g by 1 and 2 and let λ i > 0 be the smallest positive number such that the zero set of q λ i intersects the outer oval in the half-space labeled by i. We observe that both q λ i have three real contact points with C. If λ 1 = λ 2 , then we are done. Now we let the linear form l, which we started with, vary continuously and we also keep track of the labels of the half-spaces in a continuous manner. The resulting conic q λ 1 (l) depends continuously on l and we note that q λ 1 (-l) = q λ 2 (l). Note that one of the zero sets of q λ 1 (l) resp. q λ 1 (-l) on C contains a pair of complex conjugate points (the orange oval in Figure (3)) whereas the other one contains only real points of C (the red oval in Figure ( 3)). Therefore, there must be a linear form l 0 such that q λ 1 (l 0 ) has the desired properties (Figure ( 4) and ( 5)).

If there is no bitangent touching the quartic in two real points, we do not know whether there always exists an interlacer intersecting the curve in only real points. The next example shows that this is at least sometimes the case.

Example 1.7. We consider the smooth plane quartic defined by

f = 1250000x 4 -1749500x 3 y -2250800x 2 y 2 -4312500x 2 z 2 +69260xy 3 + 786875xyz 2 + 88176y 4 + 1141000y 2 z 2 + 1687500z 4 .
Its real locus consists of two nested ovals both of which are convex (Figure 7), meaning that there is no bitangent touching the curve in two real points. Nevertheless the interlacer given by g = 500x 3 -800x 2 y -740xy 2 -625xz 2 + 176y 3 + 1000yz 2 intersects the quartic curve only in real points. Indeed, its divisor is given by:

A generalized Dixon process

Given a real hyperbolic form f of degree d and an interlacer g of degree d -1, we wish to produce a real symmetric determinantal representation of f with a principal minor divisible by g. If g is a contact curve, this is achieved through the classical Dixon process. We will extend the procedure in such a way that the resulting representation will reflect any real contact points between f and g, relating to our discussion of extremal curves of real contact in the previous section.

Let f be irreducible and hyperbolic with respect to e ∈ P 2 (R) and assume that the plane curve V C (f ) is smooth. Let g be an interlacer of f with r real contact points p 1 , . . . , p r , counted with multiplicities. Consider the d(d -1) -2r further intersection points, which are non-real and therefore come in complex conjugate pairs, say q 1 , . . . , q s , q 1 , . . . , q s , so that d(d -1) = 2r + 2s. For each i = 1, . . . , s let Figure 7. A hyperbolic quartic curve (in blue) and a cubic interlacer (in green) with only real intersection points i be a linear form defining the unique (real) line joining q i and q i . We will make the following assumptions: (G1) No three of the intersection points of f with g lie on a line. (G2) No three of the i pass through the same point. (G3) f does not vanish on any point where two of the i intersect.

We begin by showing that such an interlacer always exists.

Lemma 2.1. There exists a strict interlacer for which the genericity assumptions (G1), (G2), and (G3) are satisfied.

Proof. Every choice of k = 1 2 d(d + 1) -1 points on the zero set of f that pose linearly independent conditions on forms of degree d -1 determines a unique such form. The other zeros of this (d -1)-form on the zero set of f depend continuously on the choice of the k points. By the General Position Theorem [1, Ch. III, §1], any neighborhood of the given interlacer contains a strict interlacer g with the property that its zero set intersects the one of f in d(d -1) distinct points any k of which pose linearly independent conditions on forms of degree d -1. Then we can slightly perturb any subset of k points in this intersection, and thus g, so that the number of triples of points in the intersection that lie on a line decreases. Thus we can find a strict interlacer of f with the property that no three intersection points with the zero set of g lie on a line, so that genericity condition (G1) is satisfied. By the same argument, we can satisfy condition (G3).

For condition (G2), we need to move six points spanning three of the lines. Thus the same argument applies, provided that k 6, which means d > 3. The case d 2 being trivial, we are left with condition (G2) for cubics (d = 3). In this case, we argue as follows: Suppose there is no interlacing conic satisfying condition (G2). Since the condition is Zariski-open, this would imply that condition (G2) is violated for any conic, strictly interlacing or not. But Lemma 1.3 and the subsequent Remark 1.5 imply that there exists an irreducible conic g touching f in three real points. Considering g as the limit of forms all of whose intersection points with f are simple, the assumption will imply that the three tangents to V(g) at the contact points meet in one point. But since g is irreducible of degree 2, this is impossible. This contradiction shows the claim.

Under these genericity assumptions, we will construct a symmetric linear determinantal representation M of 1 • • • s • f such that S(M ) is the hyperbolicity region of f . Furthermore, the interlacer g divides a principal minor of M . The main result of this section is as follows:

Theorem 2.2. Let f be an irreducible form of degree d that is hyperbolic with respect to e ∈ P 2 (R) and assume that the plane curve V(f ) is smooth. Let g be an interlacer of f with r real contact points, counted with multiplicities, that satisfies the genericity assumptions (G1), (G2), (G3). Then there exists a symmetric linear matrix pencil M of size

m = d 2 + d -2r 2
which is positive definite at e and such that C(f, e) = S(M ). We can choose M in such a way that g divides the principal minor M 1,1 of M and det(M )/f is a product of m -d linear forms. Furthermore, each (m -1) × (m -1) minor M 1l , 1 ≤ l ≤ m, of M is also divisible by the product of these m -d linear forms.

The proof will consist of an algorithm that produces the desired representation given f and g.

We begin with some preliminaries. Given any two real ternary forms f, g of degree d resp. d without common components, we denote by (f.g) the intersection cycle of f and g, consisting of the intersection points of the curves V(f ) and V(g) in P 2 (C). It is a 0-cycle, i.e. an element of the free abelian group over the points of P 2 (C). Explicitly, (f.g) = k i=1 m i p i , with V(f ) ∩ V(g) = {p 1 , . . . , p k } and m i positive integers, the intersection multiplicities. By Bézout's theorem, we have

k i=1 m i = dd . Intersection cycles are additive, i.e. ((f 1 • f 2 ).g) = (f 1 .g) + (f 2 .g).
Furthermore, there is a natural partial order on 0-cycles, by comparing coeffcients. We need the following classical result from the theory of plane curves, which we restate in the form we require.

Theorem 2.3 (Max Noether). Let f, g, h be real ternary forms. Assume that f is irreducible and does not divide gh, and that the curve V(f Now let f and g be given as in the statement of Thm. 2.2, with intersection points p 1 , . . . , p r , q 1 , . . . , q s , q 1 , . . . , q s as before, and let i be the linear form defining the line between q i and q i , for i = 1, . . . , s, under the genericity assumptions (G1)-(G3).

) ⊂ P 2 (C) is smooth. If (h.f ) (g.f ),
Put h = 1 • • • s and consider the polynomial f h. It is of degree (d 2 +d-2r)/2 = m and hyperbolic with respect to e. Furthermore, since each line i meets C in the non-real point q i , none of the lines pass through C(f, e), so that C(f h, e) = C(f, e).

It therefore suffices to construct a symmetric linear determinantal representation of f h which is definite at e. This can be carried out with a modification of Dixon's method, which we now describe in several steps.

1) Let V be the linear space of real forms of degree d -1 vanishing at p 1 , . . . , p r . We have dim(V ) ≥ (d+1)d 2 -r = d + s, and we pick linearly independent forms a 1 , . . . , a d+s ∈ V , with a 1 = g. We introduce names for all the occuring intersection points:

(a 1 .f ) = (g.f ) = 2 r j=1 p j + s j=1 (q j + q j ) (a i .f ) = r j=1 p j + r+2s j=1 p ij for i 2 ( i .f ) = q i + q i + d-2 j=1 r ij ( i . j ) = s ij for i = j 2) Fix k, l ∈ {2, . . . , d + s} with k l.
We wish to find a real form b kl of degree 3) Assume that k = l. Then we will produce a real form q of degree s -1 such that c kk := b kk + qf satisfies

d + s -1 such that b kl g -ha k a l ∈ (f ) (2.
(c kk . i ) = (b + qf. i ) = d-2 j=1 r ij + j =i s ij + 2t ki
for some real point t ki ∈ ki , for all i = 1, . . . , s. To this end, we let 0 be a linear form which does not vanish on any of the s ij . Let

h ij = 0 ••• s i j and α ij = - b kk (s ij ) h ij (s ij )f (s ij )
for 1 ≤ i < j ≤ s. Note that h ij vanishes on all s mn except for s ij . After replacing b kk by b kk + i,j α ij h ij f , we can thus assume that b kk vanishes on all the s ij .

Next, we consider

q α = s j=1 α j 1 • • • s j .
with α 1 , . . . , α s ∈ R. The form q α satisfies q α (s ij ) = 0 for all j = i for any choice of the α j . If we now take q = q + q α , we find

(b kk + qf. i ) = d-2 j=1 r ij + j =i s ij + u i + v i
with u i and v i depending on α. Restricting to i we therefore get b kk + qf = P • ( b + α i f ) where P is a nonzero polynomial whose roots are the r ij and s ij , and where b and f are polynomials of degree two. After possibly replacing α i by its negative, we can assume that f is strictly positive on i since it has no real zeros on i . Therefore, we can choose α i in such a way that b + α i f has a double zero t ki and that makes the product of b kk + qf and f

• 1 ••• s i
i (e) nonnegative on i . The reasons for the latter requirement will become clear in a later step.

4) Similarly, if k < l, we can find a real form q of degree s -1 such that c kl := b kl + qf satisfies

(c kl . i ) = (b kl + qf. i ) = d-2 j=1 r ij + j =i s ij + t ki + t ki
for some real point t ki ∈ i . In fact, we even have that t ki = t li . Indeed, this follows from (2.4) and the following lemma applied to each i . Proof. Let a = α(t -β) 2 , c = α (t -β ) 2 and b = γ(t -β)(t -β ) for some α, α , β, β , β , γ ∈ R with αα ≥ 0. We have by assumption

αα (t -β) 2 (t -β ) 2 = γ 2 (t -β) 2 (t -β ) 2 mod f. Since R[t]/(f ) is isomorphic to the field of complex numbers, it follows that αα (t -β ) 2 = γ 2 (t -β ) 2 mod f. If γ = 0, then αα > 0 and t -β = ± γ 2 αα (t -β ) mod f . Finally, it follows that αα = γ and that β = β because 1, t ∈ R[t]/(f ) are R-linearly independent.
If k > l, we let c kl = c lk . 5) We now put c 1k = c k1 = ha k and consider the matrix N with entries c kl , for k, l = 1, . . . , d + s. By construction, the 2 × 2-minors

c 11 c kl -c 1k c 1l = hgc kl -h 2 a k a l = h(gc kl -ha k a l )
are divisible by f h. Since the first row of N is not divisible by f , it follows that all 2 × 2-minors of N are divisible by f . We need to show that all 2 × 2-minors c kl c k l -c kl c k l are also divisible by h. Let u be such a minor and fix i ∈ {1, . . . , s}. Note that u has degree 2d+2s-2 and vanishes (with multiplicities) on the 2d+2s-2 points 2 d-2 j=1 r ij , 2 j =i s ij , (t ki + t k i + t li + t l i ) on i , since both products c kl c k l and c kl c k l vanish at those points. Since u is divisible by f , it also vanishes at q i + q i . Thus u vanishes identically on i for each i, which implies h|u. 6) In this step we show that c 22 interlaces f h. This can be done by proving that c 22 •D e (f h) is nonnegative on the zero set of f h [10, Thm. 2.1]. Here D e (f h) denotes the derivative of f h in direction e. We have

D e (f h) = h • D e f + f • s i=1 i (e) 1 • • • s i .
We can rewrite this modulo f and find

c 22 • D e (f h) = c 22 • h • D e f = ha 2 2 g • h • D e f = D e f g h 2 a 2 2 (mod f )
by (2.4). This is nonnegative on the zero set of f because both D e f and g are interlacers. On the other hand, modulo i we obtain

c 22 • D e (f h) = c 22 • i (e) • 1 • • • s i (mod i )
which is nonnegative on the line defined by i by the choices made in Step 3). 7) Now we proceed as in the usual Dixon process, referring to [START_REF] Plaumann | Determinantal representations of hyperbolic plane curves: an elementary approach[END_REF] for details: Since all 2 × 2-minors of the (d + s) × (d + s)-matrix N are divisible by f h, its maximal minors are divisible by (f h) d+s-2 (see for example [START_REF] Plaumann | Determinantal representations of hyperbolic plane curves: an elementary approach[END_REF]Lemma 4.7]). The signed maximal minors of N have degree (d + s -1) 2 and are the entries of the adjugate matrix N adj . It follows that M = (f h) 2-d-s • N adj has linear entries. Using the familiar identity N N adj = det(N ) • I d+s , we conclude

det(M ) = γ • f h
for some constant γ ∈ R. It remains to show that γ = 0. Suppose γ = 0, then det(M ) is identically zero, hence so is det(N ). In particular, the matrix N (e) is singular. Let λ ∈ R d+s be a non-trivial vector in the kernel of N (e) and consider the polynomial g = λ t N λ. It follows from the linear independence of the entries of the first row of N that g is not the zero polynomial [START_REF] Plaumann | Determinantal representations of hyperbolic plane curves: an elementary approach[END_REF]Lemma 4.8]. Since c 22 interlaces f h by ( 6), so does g [11, Thm. 3.3, (1)⇒( 2)], contradicting g(e) = 0. That M (e) is definite also follows from the fact that c 22 interlaces f h, by [START_REF] Plaumann | Determinantal representations of hyperbolic plane curves: an elementary approach[END_REF]Thm. 3.3

, (2)⇒(3)].

Note that the result in [START_REF] Plaumann | Determinantal representations of hyperbolic plane curves: an elementary approach[END_REF] is stated only for irreducible curves. However, the same argument will apply here, since c 22 is coprime to f h (unlike c 11 , which is divisible by h). Indeed, we have chosen c 22 in step (3) in such a way that it does not vanish entirely on any of the lines l i . Thus c 22 is coprime to h. Moreover, c 22 is congruent to b 22 modulo (f ). Thus if f divided c 22 , it would also divide a 2 by (2.4) which is not the case. This finishes the construction of the determinantal representation M of f h. Finally, we note that the spectrahedron S(M ) coincides with the hyperbolicity region C(f, e) of f . Since det(M ) = f • 1 • • • s , this simply amounts to the fact that the lines points with C, while lines passing through the hyperbolicity region will meet C in only real points. This completes the proof of Theorem 2.2.

Remark 2.6. Clearly, the corank of the constructed matrix pencil M is at least one at each point where f h vanishes. It can have corank more than one only at singularities of f h, i.e. in our case the points where two components intersect. Since the adjugate N = M adj vanishes identically at the points r ij and s ij and because these are ordinary nodes, the corank of M at these points is exactly two. On the other hand, we have constructed N in such a way that it is not entirely zero at the points q j and q j . Thus M has corank one at these points. This shows in particular that M is not equivalent to a block diagonal matrix with more than one block.

Remark 2.7. The vector space V in Step 1) of our construction can be found without computing all the real contact points p 1 , . . . , p r . Indeed, by genericity assumption (G1) the q i , q i are all simple intersection points. Therefore, the p i can be computed as the singular locus of the zero dimensional scheme cut out by f and g via the Jacobian criterion.

Next we observe that the genericity assumption in the theorem, as well as the smoothness assumption on f , can be dropped for strict interlacers by applying a limit argument.

Corollary 2.8. Let f be a real form of degree d that is hyperbolic with respect to e ∈ P 2 (R), and let g be a strict interlacer of f . Then there exists a symmetric linear matrix pencil M of size d 2 +d 2 which is definite at e and such that C(f, e) = S(M ). We can choose M in such a way that g divides a principal minor of M and det(M )/f is a product of d 2 -d 2 linear forms.

Proof. Let m = d 2 +d
2 . We may assume that f (e) = 1 and consider only monic representations f = det(M ), i.e. with M (e) = I m . The determinant map taking a monic symmetric real linear matrix pencil of size m × m to its determinant is proper, hence its image is closed (see for example [START_REF] Plaumann | Determinantal representations of hyperbolic plane curves: an elementary approach[END_REF]Lemma 3.4]). If g is a strict interlacer of f , the pair (f, g) is in the closure of the set of pairs ( f , g), where f is hyperbolic with respect to e, V( f ) is smooth, and g is a strict interlacer of f satisfying the genericity assumptions (G1)-(G3). Therefore, there exists a sequence ( f n , g n ) converging to (f, g) together with representations f n = det( M n ) with g n dividing the first principal minor of M and det( M )/ f a product of m -d linear forms, by Theorem 2.2. The sequence M n then has a subsequence converging to a matrix pencil M , which is the desired determinantal representation of f . Remark 2.9. The procedure of approximating a given hyperbolic form together with an interlacer as in the proof above may be difficult to carry out in practice. However, the generalized Dixon process can often be applied (with small modifications if needed) even when the genericity assumptions fail.

As a further consequence, we can prove the following rationality result. Theorem 2.10. Let f ∈ Q[x, y, z] d be a polynomial hyperbolic with respect to e ∈ R 3 whose real projective zero set is smooth. Then its hyperbolicity cone is of the form

{(x, y, z) ∈ R 3 : xA + yB + zC 0}
where A, B, C are symmetric matrices with rational entries of size at most d+1 2 . Proof. Let m ∈ Q[x, y, z] e d-1 be the vector of all monomials of degree d -1 and let e = d+1

2 . The equation

(xA + yB + zC) • m = f • v (2.11)
poses linear conditions on the entries of the symmetric e × e matrices A, B, C and on the entries of v ∈ R e . These linear conditions are defined over the rational numbers.

We now apply the above construction to f with a strict interlacer g satisfying the genericity assumptions (G1), (G2), and (G3) whose existence is guaranteed by Lemma 2.1. The vector space V from step (1) is just the vector space of all ternary forms of degree d -1 and the a i form a basis of V . Thus we can find an invertible matrix S ∈ GL e (R) that maps the vector a = (a 1 , . . . , a N ) t to the vector m of all monomials of degree d -1. In step [START_REF] Henrion | Spectra -a maple library for solving linear matrix inequalities in exact arithmetic[END_REF] of our construction we have seen that there is a matrix N such that our symmetric determinantal representation

M of f •h satisfies M • N = γ • f h • I e . Moreover, the first column of N is h • a. Thus we have that M • a = γ • f • δ 1 . Now we get the identity S -t M S -1 • m = γ • f • S -t δ 1 .
This is a solution over R to Equation (2.11) with e 0 A + e 1 B + e 2 C positive definite and det(xA + yB + zC) = h • f where h is a product of linear forms whose zero set does not intersect the hyperbolicity cone of f .

Since the rational solutions to (2.11) are dense in the solution set over the real numbers, we can find rational matrices A, B, C satisfying (2.11) with e 0 A+e 1 B+e 2 C being positive definite, as well. Then det(xA + yB + zC) is not the zero polynomial and is divisible by f , since the pencil has a nonzero kernel vector whenever f vanishes at (x, y, z) by (2.11). If A, B, C are chosen close enough to our original solution, the other factor of det(xA + yB + zC) will not intersect the hyperbolicity cone of f either.

Remark 2.12. One might be tempted to generalize Theorem 2.10 to singular f using the determinantal representation det(M ) = h • f , where h is a product of linear forms, obtained in Corollary 2.8 by a limit argument. In order to make the arguments from the preceding proof work, the first column of M adj would have to be of the form h • a where a is a vector whose entries span a subspace of R[x, y, z] d-1 that is defined over the rationals. It is not clear whether this is always the case.

The next example shows that the smallest size of a rational spectrahedral representation is in general larger than the degree of the curve.

Example 2.13. Consider the univariate polynomial p = x 3 -6x -3 ∈ Q[x]. It has three distinct real zeros but is irreducible over the rational numbers by Eisenstein's criterion. The plane elliptic curve defined by y 2 = p(x) is hyperbolic. Its hyperbolicity cone has the following spectrahedral representation with rational 4 × 4 matrices:

{(x, y, z) ∈ R 3 :     3z y -x -z -3x + z y -x + 2z 0 -y -x -z 0 z x + 4z -3x + z -y x + 4z -x + 18z     0}.
This was obtained by applying our construction to the interlacer y 2 + 3xz + z 2 with two real contact points (Figure 8). It also has a 3 × 3 spectrahedral representation with real matrices by the Helton-Vinnikov Theorem. It does, however, not have such a representation with rational 3 × 3 matrices. Indeed, any such representation would yield a contact interlacer defined over the rational numbers by taking some principal 2 × 2 minor. This interlacer would give rise to a divisor D defined over the rational numbers with 2D = 6P ∞ where P ∞ is the point of the curve at infinity. Thus D -3P ∞ would be an even theta characteristic defined over the rationals. On the other hand, the three even theta characteristics of the curve are given by P i -P ∞ for P 1 , P 2 , P 3 the three intersection points of the curve with the x-axis. These are clearly not defined over the rationals.

Bézout matrices

Let f, g ∈ R[t] be two univariate polynomials having degrees deg(f ) = d and deg(g) = d -1. The Bézout matrix of f and g is defined as follows. We write

f (s)g(t) -f (t)g(s) s -t = d i,j=1 b ij s i-1 t j-1
for some real numbers b ij . Then the Bézout matrix is defined as B(f, g) = (b ij ) ij . Note that B(f, g) is always a real symmetric matrix. The Bézout matrix can be used to detect the properties of being real-rooted and interlacing. Furthermore, the Bézout matrix has full rank if and only if f and g have no common zero.

In the multivariate case we can proceed analogously. Let f, g ∈ R[x 0 , . . . , x n ] be homogeneous polynomials of degrees d and d -1 respectively. We assume that f and g do not vanish at e = (1, 0, . . . , 0). Then, writing x = (x 1 , . . . , x n ), we have

f (s, x)g(t, x) -f (t, x)g(s, x) s -t = d i,j=1 b ij s i-1 t j-1
for some homogeneous polynomials b ij ∈ R[x 1 , . . . , x n ] of degree 2d -(i + j). Again, we define the Bézout matrix as B(f, g) = (b ij ) ij . It follows from the above theorem that B(f, g) is positive definite for every 0 = x ∈ R n if and only if f is hyperbolic with respect to e and g is a strict interlacer of f .

lim s→t f (s, x)g(t, x) -f (t, x)g(s, x) s -t = W(f, g).
We also note that for square-free polynomials f the polynomial g of degree deg(f )-1 is uniquely determined by W(f, g).

We can use the Wronskian polynomial W(f, g) to describe the set Int(f, e) of interlacers of f in direction e, which is a convex cone. By [10, Cor.2.7], Int(f, e) can be represented as a linear image of a section of the cone of positive polynomials of degree 2d -2, where d = deg f :

Int(f, e) = g ∈ R[x, y, z] d-1 : W(f, g) ≥ 0 .
Whenever W(f, g) is a sum of squares, the cone Int(f, e) can be sampled by solving a linear matrix inequality as shown in the following example. Let g = x 2 + g 110 xy + g 101 xz + g 020 y 2 + g 011 yz + g 002 z 2 be a generic quadratic form such that g(e) = 1. The Wronskian of f, g in direction e is the ternary quartic W(f, g) = 2g 110 x 3 y + 2g 110 x 2 y 2 + 2g 110 y 4 + 2g 101 x 3 z + 2g 101 x 2 yz + 2g 101 y 3 z+ + 3g 020 x 2 y 2 + 4g 020 xy 3 -g 020 y 4 -g 020 y 2 z 2 + 3g 011 x 2 yz + 4g 011 xy 2 z--g 011 y 3 z -g 011 yz 3 + 3g 002 x 2 z 2 + 4g 002 xyz 2 -g 002 y 2 z 2 -g 002 z 4 + + x 4 + x 2 y 2 + x 2 z 2 + 4xy 3 .

Let G = (G ij ) be a symmetric 6 × 6 matrix of unknowns, and consider the linear system W(f, g) = m t • G • m, where m is the vector of monomials of degree 2 in x, y, z. We obtain that G (the Gram matrix of W(f, g), cf. [START_REF] Powers | An algorithm for sums of squares of real polynomials[END_REF]) has the form Solving (3.4) symbolically using [START_REF] Henrion | Spectra -a maple library for solving linear matrix inequalities in exact arithmetic[END_REF] yields the following parametrization of an interlacer: g = x 2 -y 2 + t • z 2 , where t is any of the two real roots t 1 , t 2 of q(t) = 49t 4 -20t 3 + 22t 2 + 12t + 1 (the green curves in Figure 9). Since the matrices G corresponding to the two interlacers have rank 2, the corresponding Wronskian polynomials are sums of two squares. Choosing a rational t 1 < r < t 2 gives a rational interlacer, for instance g = x 2 -y 2 -1 5 z 2 .

G =         
As in Example 2.13, our construction yields rational 4×4 determinantal representations of f times a rational linear polynomial, that can be built from the interlacer g = x 2 -y 2 -1 5 z 2 : The matrix on the right hand side of the previous equality gives a spectrahedral representation of C(f, e) (the green region in Figure 9).

In the following, we show how our construction gives a sum-of-squares decomposition, i.e. a representation B(f, g) = S t S for some (not necessarily square) matrix S with polynomial entries, for any curve f hyperbolic with respect to (1, 0, 0) and any strict interlacer g.

We have seen that there is a basis g 1 , . . . , g N of R[x, y, z] d-1 with g 1 = g and real symmetric matrices A, B, C of size N such that A is positive definite and

(xA + yB + zC) • v = δ 1 • f (3.5)
where v = (g 1 , . . . , g N ) t and δ 1 ∈ R N is the first unit vector. Let us write v = h 0 x d-1 + . . . + h d-1 for some h i ∈ R[y, z] N i and let S be the matrix with columns h d , . . . , h 0 . We claim that B(f, g) = S t AS. Indeed, by [9, §3], we have that B(f, g) = S t AS for some g ∈ R[x, y, z] d-1 . Furthermore, taking the derivative of (3.5) yields:

A • v + (xA + yB + zC) • D e v = δ 1 • D e f.
Now it follows by multiplying with v t from the left and another application of (3.5) that

v t • A • v + f • δ t 1 • D e v = v t • A • v + v t • (xA + yB + zC) • D e v = v t • δ 1
• D e f. Thus by Remark 3.2, applied with v = Sw, we find W(f, g) = w t B(f, g)w = w t S t ASw = v t • δ 1 D e f -f • δ t 1 D e v = W(f, g) which implies g = g, again by Remark 3.2, since f is square-free. Remark 3.6. It has been shown in [START_REF] Kummer | Determinantal representations and Bézoutians[END_REF] that a sum-of-squares representation B(f, g) = S t AS of a Bézout matrix of a hyperbolic polynomial f with a positive definite matrix A as above gives rise to a definite determinantal representation of some multiple of f . Now we have seen that for every strict interlacer of a hyperbolic curve there is a sum-of-squares decomposition of the corresponding Bézout matrix which even gives rise to a spectrahedral representation of the hyperbolicity cone.

Lemma 1 . 3 .

 13 Assume that f defines a smooth curve of degree d. Any extremal interlacer of f has at least (d + 1)d -2 4

4 •

 4 (4 : -5 : 0) + 2 • (11 : 5 : 0) + 2 • (1 : 5 : 0) + 2 • (7 : 10 : -10) + 2 • (7 : 10 : 10).

. 3 Figure 3 . 3

 333 Figure 3

Figure 4 . 3 Figure 5 Figure 6 .

 4356 Figure 4

  then there exist real forms a and b such that h = af + bg. Proof. See [5, §5.5, Prop. 1].

4 )

 4 by applying Max Noether's theorem: We compute the intersection cycles(ha k a l .f ) = 2 + q j )and thus find b kl with (b kl .f ) =

Lemma 2 . 5 .

 25 Let f ∈ R[t] be a polynomial of degree two without real zeros. Let a, b, c ∈ R[t] be polynomials of degree at most two such that a and c both have a double zero, ac is nonnegative and b vanishes at the zero of a. If ac = b 2 mod f , then b vanishes at the zero of c as well.

Figure 8 .

 8 Figure 8. Hyperbolic cubic (in blue), an interlacer touching in 2 real points (in green) and the linear factor (dashed in blue)

Theorem 3 . 1 (

 31 see §2.2 of[START_REF] Kreȋn | The method of symmetric and Hermitian forms in the theory of the separation of the roots of algebraic equations[END_REF]). Let f, g ∈ R[t] be univariate polynomials with d = deg(f ) = deg(g) + 1. Then the following are equivalent:(i) The Bézout matrix B(f, g) is positive semidefinite. (ii) The polynomial g interlaces f .

Remark 3 . 2 .

 32 The Bézout matrix B(f, g) is closely related to the Wronskian polynomial W(f, g) = D e f • g -f • D e g. Namely, if we let w = (1, x 0 , . . . , x d-1 0 ) t , then W(f, g) = w t • B(f, g) • w. Indeed, by the definition of the Bézout matrix the righthand side equals

Example 3 . 3 .

 33 The cubic f = x 3 + 2x 2 y -xy 2 -2y 3 -xz 2 is hyperbolic with respect to e = (1, 0, 0), and C(f, e) is the green region in Figure9.

Figure 9 .

 9 Figure 9. A cubic hyperbolic curve (in blue) with three interlacers, one defined over Q (in dashed black) and two over an extension of degree 4 (in green). The dashed blue line is the extra factor in the determinantal representation.

Let p 1 =

 1 (1, 1, 0) and p 2 = (1, -1, 0). Interlacers in Int(f, e) vanishing in p 1 and p 2 can be computed through the quantified linear matrix inequality(3.4) ∃ G ij : g(p 1 ) = g(p 2 ) = 0, G 0.

, . . . , s do not pass through C(f, e). Indeed, each j has two non-real intersection

Acknowledgements. We thank the Max Planck Institute for Mathematics in the Sciences in Leipzig for its hospitality, where this work was started. We would also like to thank the referee for useful remarks that helped us improve the exposition. Simone Naldi acknowledges the support of the Fondation Mathématique Jacques Hadamard through the PGMO project 2018-0061H.


Tengfei Chang
email: tengfei.chang@inria.fr

Thomas Watteyne
email: thomas.watteyne@inria.fr

Brad Wheeler
email: brad.wheeler@berkeley.edu

Filip Maksimovic

Osama Khan
email: oukhan@berkeley.edu

Sahar Mesri
email: smesri@berkeley.edu

Lydia Lee
email: lydia.lee@berkeley.edu

Kris Pister

Ioana Suciu
email: isuciu0@uoc.edu

Xavier Vilajosana
email: xvilajosana@uoc.edu

M, Running a Synchronized Protocol Stack without Crystals

Keywords: Crystal-free, 6TiSCH, SCµM, smart dust

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

Time Synchronized Channel Hopping (TSCH) is at the core of all main industrial standards, including Wire-lessHART, ISA100.11a and IEEE802.15.4. 6TiSCH [START_REF] Vilajosana | 6TiSCH: Industrial Performance for IPv6 Internet-of-Things Networks[END_REF] protocol stack is the latest such standardization efforts, lead by the Internet Engineering Task Force (IETF). It combines the industrial performance of IEEE802.15.4 TSCH, with the IETF upper stack for IoT devices. As depicted in Fig. 2, this upper stack includes CoAP, UDP, RPL and 6LoWPAN.

The commercial IEEE802.15.4-compliant chips running these standards use stable oscillators as a time reference. Typical those crystal oscillators drift rates, i.e. the inaccuracy of the frequency, is in the 10-30 ppm (parts-per-million) range. The problem of needing a crystal is cost and space. While the crystal itself might be relatively cheap (in the USD 0.50 range), using them requires one to make a printed circuit board to assemble the crystal to the chip, which consumes space and increases cost.

The Single Chip micro-Mote, or SCµM, is a crystal-free chip we taped out in 2019. It is a 2×3 mm 2 single-chip crystal-free mote-on-chip which contains an ARM Cortex-M0 micro-controller, a 2.4 GHz IEEE802.15.4 radio, and an optical receiver for optical programming. Fig. 1 shows SCµM on the board we use to develop/debug it. The digital part of SCµM is implemented over a FPGA board (indicated on the left of the figure) and the analog part is implemented over the chip. Loading code into the chip is done optically by using an external board which blinks an LED close to the optical receiver on SCµM. The goal of this paper is to show a 6TiSCH network composed of one SCµM and one OpenMote [START_REF] Vilajosana | OpenMote: Open-Source Prototyping Platform for the Industrial IoT[END_REF]. The challenge is that SCµM does not have an accurate sense of time, and therefore derives its time reference from OpenMote. The following section describes how SCµM tunes the frequency it communicates on, and how we calibrate its clocks.

Frequency Synthesis and Clock Calibration

First we need to give SCµM a rough time reference so it can send frames that OpenMote can receive. The frequency of each of the oscillators is tunable. We designed the code running on the optical programmer board in such a way that, at the end of the bootloading process, the optical programmer repeatedly sends a sequence that causes an OPTICAL ISR interrupt to be generated on SCµM. This interrupt fires every 100 ms for 2.5 s. While this is happening, on SCµM, all the clocks are running. By recording the counter value of each of the clocks, and knowing the interval between interrupts, SCµM calibrates each of the oscillators.

Following this coarse calibration using the optical programmer, SCµM can also calibrate against the OpenMote. We do this offline, i.e. this calibration is done once, the result of which is reused the next time SCµM is programmed. For this calibration, SCµM sends frames on channel 11 (2.405 GHz) to OpenMote. OpenMote is programmed to listen on that channel, and prints over its serial port the value of its XREG FREQEST register, which indicates the frequency offset of the incoming signal. According to that value, we manually tune the 2.4GHz oscillator of SCµM, to minimize that frequency offset. This procedure is repeated for each SCµM board, as each has slightly different tuning parameters. This is illustrated in Fig. 3. While SCµM is running the 6TiSCH stack, it keeps synchronized to the OpenMote. Part of that is making sure the boundaries of its TSCH slots are aligned in time with that of OpenMote. The frequency of the timer used for implementing TSCH slot state machine runs at 32 kHz. However, RFTimer, the timer SCµM used for the same purpose, runs at 500 kHz. This means the OpenWSN port to SCµM divides down the 500 kHz RFTimer so it appears as a 32 kHz clock source to the otherwise unmodified OpenWSN stack implementation. Since 500/32 = 15.625, the integer division applied in the port results in a rounding error. This means the slot length on SCµM is slightly different than the slot length of OpenMote. As is, this difference in slot length results in an apparent relative drift between OpenMote and SCµM. We therefore implement a digital trimming (tick skipping) compensation algorithm, explained in [START_REF] Chang | Adaptive synchronization in multi-hop TSCH networks[END_REF].

Conclusion

This paper provides the first example of a synchronized network protocol (6TiSCH) running on a crystal-free device, the Single Chip micro-Mote (SCµM), a 2×3 mm 2 crystalfree mote-on-a-chip. SCµM features an ARM Cortex-M0 micro-controller and an IEEE802.15.4 radio. It first listens to a blinking LED to provide coarse calibration of its oscillators. Then using an OpenMote, which report the frequency offset, provides a second level of more precise tuning. Finally, as SCµM and OpenMote are communicating, the OpenWSN port on SCµM uses a digital trimming compensation algorithm based on tick skipping to counteract a rounding error caused by frequency converting. This allows a synchronized fully functional 6TiSCH network to form between SCµM and OpenMote.

Figure 1 .

 1 Figure 1. The Single Chip Micro-Mote (SCµM) is a 2×3 mm 2 mote-on-a-chip. It features an ARM Cortex-M0 micro-controller, an IEEE802.15.4 radio, and an optical bootloader. While SCµM runs with no external components, it is shown here on its development board. In this setup, we use an FPGA board to implement the digital part (including the Cortex-M0 micro-controller), and use the analog front-end of the SCµM chip.

Figure 2 .

 2 Figure 2. The 6TiSCH stack. The upper stack provides IPv6 connectivity. The lower stack, through TSCH, provides industrial-level performance.

Figure 3 .

 3 Figure 3. Setup for tuning the communication frequency of SCµM. SCµM transmits frames to OpenMote, which logs the frequency offset for each frame it receives. These offsets are then used to manually tune the 2.4GHz oscillator of SCµM, which is used to select the transmit frequency, to minimize the mean frequency offset.


Ba Yasuyuki Tanaka

Hai Le

Victor Kobayashi

Camilo Lopez

Thomas Watteyne

Mina Rady
email: mina1.rady@orange.com

Demo: Blink -Room-Level Localization Using SmartMesh IP

Keywords: Localization, low-power, TSCH, SmartMesh IP

This demo presents a room-level localization solution built on top of the market leading SmartMesh IP industrial low-power wireless mesh network. Without any changes to the hardware or protocol stack of that product, we re-purpose Blink -a feature designed to allow for mobile nodes -for localization. We demonstrate how we can deploy the resulting localization solution throughout a building by installing an anchor node in each room, and locate the room a mobile tag is in. Initial results indicate that this solution offers over 90% room-level localization accuracy, and at worst adjacent room localization. The unique aspect of it is that the entire network of anchor nodes in battery powered and operates for years on a pair of AA batteries. There are countless applications looking for easily to install and fully battery powered room-level localization, for which our solution, which is production-ready, is ideal.

Introduction

Low-power wireless mesh solution have been a commercial reality, with tens of thousands of networks deployed in applications ranging from industrial monitoring, to smart building, smart parking and environmental sensing. All of these networks use a variant of Time Synchronized Channel Hopping (TSCH). And while these networks are used to carry sensor data and actuator commands, there are many use cases where being able to localize at least a certain number of motes opens up many new applications. A representative example is the mobile echograph machine in a hospital, a piece of medical equipment on wheels which is shared by the medical personnel, and which travels from room to room. We are trying to design a solution that fits that need: know in which room the echograph is (e.g. centimeter-level accuracy is absolutely not needed), and make sure that solution is fast to deploy and cheap (e.g. does not require wires).

There are many localization technologies, based on Ultra-Wide Band [START_REF] Despaux | An accurate time-of-flight-based N-ary ranging protocol for Ultra-Wide band[END_REF], ultra-sound or BLE beacons [START_REF] Jeon | BLE Beacons for Internet of Things Applications: Survey, Challenges, and Opportunities[END_REF]. While they generally work, they either require anchor nodes to be mains powered, or tags to be recharged every day or so. And while some offer a much better localization accuracy, the lack of low-power makes them unsuitable.

In this demo, we demonstrate a full indoor room-level localization solution, which consists of only wireless devices which can be deployed in a couple of hours throughout a building, and operate for years without requiring any battery change. We do so by re-purposing the existing Blink feature of SmartMesh IP, without requiring any changes to the hardware. This makes our solution production-ready, as it benefits from the industrial performances and overall quality of this product. All elements which are not part of SmartMesh IP are available open-source.

Blink Localization System

SmartMesh IP is a commercial low-power wireless mesh networking solution designed by the Dust Networks team, and commercialized by Analog Devices1 . It is the market leading low-power wireless mesh solution for demanding applications. Over 76,000 SmartMesh networks are deployed today; a SmartMesh IP network offers >99.999% end-toend reliability, <50 µA average current draw even for routing nodes (i.e. over a decade of battery lifetime), and NISTcertified security [START_REF] Watteyne | Industrial IEEE802. 15.4 e networks: Performance and trade-offs[END_REF].

Blink is part of the production SmartMesh IP firmware, any mote implements it. In Blink mode, when a mote has information to send, it goes through what looks like a regular secure join process, but, rather than sending a join request to the manager, it sends application data. After sending that data, the mote turns back off consuming virtually nothing. The Blink traffic benefits from the same security and reliability as any traffic in a SmartMesh IP network. Blink was built to allow for very large networks (up to 500,000 Blink motes in a network), and for Blink motes to move. We repurpose Blink and have the mote report the identifiers and RSSI of neighbor motes it discovered. We then use that information to get an idea of where the Blink mote is. There is very comprehensive body of work which focuses on RSSI-based localization. It is a very appealing technique, as any radio can measure and report the RSSI for any received frame; RSSI measurements are free. The problem is that it does not work, as receive signal strength is not a good indicator of distance in any sort of practical setting.

We are not looking to use RSSI for ranging or trilateration. Instead, the idea is simple: deploy an anchor in each room and if the tag is located in the same room as an anchor, because of the walls separating the rooms, it will hear the anchor in that room which an RSSI much higher than anchors in other rooms.

Fig. 1 shows the resulting architecture. 1 A number of anchor motes are deployed in the building to be equipped, one per room, and form a canopy low-power wireless network. These are unmodified SmartMesh IP motes, configured to join the SmartMesh IP network. 2 A SmartMesh IP manager is deployed in the vicinity of the anchor motes, and is in charge of managing the SmartMesh IP network. This is an unmodified SmartMesh IP manager connected to a Raspberry Pi running the blink manager.py script. 3 One or more SmartMesh IP motes roam around the building, and are the mobile tags. These are unmodified SmartMesh IP motes, configured not to join the SmartMesh IP network. Instead, they run an application which sends Blink packets. All SmartMesh IP hardware is built around the LTC5800 chip.

Demonstration

Initial testing of our demonstration is carried out across a floor of our office building at Inria-Paris. We believe our building to be representative of most modern office buildings. We deploy 25 anchor nodes, one per office. The ceiling of this building is metallic, so we use a magnet with a 50 cm long wire on which the mote dangles. This allows us to deploy the entire network of anchors in less than 15 min, without needing to climb a ladder. We place the manager, connected to a Raspberry Pi, in office A124. On the Raspberry Pi, we run the blink manager.py script that collects the Blink packets. We use a cart to walk about the area. On the cart, we put the tag mote and a laptop computer.

During the demonstration, we make sure all anchors are switched on, and form a stable SmartMesh IP mesh network around the manager. We start the blink manager.py script on the Raspberry Pi. We then walk around with the tag. At each location, which have the tag to send Blink packets; these are received and logged by the blink manager.py script on the Raspberry Pi.

Fig. 2 shows the resulting localization. Initial testing suggests that the solution positions the tag in the correct room 90% of the time, and in the room right next to it 10% of the time. The solution runs with only battery-powered devices, and hence benefits from the ultra low-power nature of SmartMesh IP, and anchors having a battery lifetime of a decade.

Discussion

This solution offers over 90% room-level localization accuracy, and adjacent room localization in all other cases. What you concede in term of localization accuracy against for example UWB solution, you get back in total cost of ownership. The entire solution is wireless, including the canopy network of anchor nodes, which can be set up in a matter of minutes. The position of every tag can be monitored centrally. This localization solution is built on the marketleading low-power wireless product, so offers an industrial level of reliability and security, making this localization solution production-ready.

A ideal example use case for this localization is tracking rolling equipment in a hospital. The building is already in use and installing a heavy localization infrastructure, possibly involving wiring up many components, is a non-starter. The proposed localization solution can be retrofit to an existing building with the full installation throughout a building taking a couple of hours. Once installed, every anchor is battery-powered and runs for over a decade on batteries. The systems supports a very large number of tags to roam around the building, simply stuck to the equipment to track.

Figure 1 .

 1 Figure 1. Architecture of the Blink localization system.

Figure 2 .

 2 Figure 2. The system positions the tag in the right office.

https://www.analog.com/en/applications/technology/ smartmesh-pavilion-home.html


A conference with such a huge number of participants requires a perfect organization in order to be successful, and indeed it was a real success. All the members of the Local Organizing Committee contributed to the excellent organization, especially the chair of the LOC, Marja van den Heuvel-Panhuizen, and her co-chair, Michiel Veldhuis. They did a wonderful work. They paid attention to all the small details before and during the conference. Both paid attention to all the specific needs of each participant. They dealt successfully with all the issues, challenges (small and big), and always with a smile. We thank both of them so deeply! Inclusion and quality is an integral part of the CERME spirit. The success of the conference is tightly connected with the quality of the scientific program, which was excellent. We address our sincere thanks to the International Program Committee, especially to the chair of the IPC, Uffe Thomas Jankvist, and his co-chair, Miguel Ribeiro, for their excellent work before, during, and after the conference, taking into account ERME principles: selecting deep and interesting plenaries, organizing a panel discussion, organizing the distribution of Thematic Working Groups and the publication process of the proceedings.

In his plenary lecture, Paul Drijvers offered a deep reflection on a promising integrative approach to tool use, called embodied instrumentation, which is based on three lenses: a Realistic Mathematics Education view; instrumental approaches, and embodied views on cognition. In the second plenary lecture, Kathleen M. Clark offered a thoughtful analysis of examples in which research on the use of history of mathematics contributed to the broader landscape of research in mathematics education. The examples address the role of history of mathematics in the learning of different mathematical concepts, ranging from the function concept to determinants of matrices, as well as topics in analysis and abstract algebra. The third plenary talk was given by Sebastian Rezat. Using the transition from natural numbers to integers as an exemplary case, Rezat delineated an insightful analysis on transitions from one number system to the other with a particular interest in continuities and discontinuities in the teaching of these number systems. Rezat integrated the results in an approach to achieve learner-centered coherence in the learning of number. Three papers corresponding to these three plenary addresses are included in the proceedings.

On the occasion of the 20 th anniversary of ERME, the IPC organized an anniversary panel chaired by Konrad Krainer and Hanna Palmer. The panel offered a deep reflection on ERME contribution to research in mathematics education. Barbara Jaworski and Susanne Prediger (past and current ERME president), Paolo Boero and Simon Modeste (representatives of YESS and YERME -Young Researchers in ERME), and Tommy Dreyfus and Jana Žalská (editor and reader of the ERME book) made up the panel.

The work done in the plenaries and the panel contributed substantially to the success of the conference.

The core and the heart of each CERME are the Thematic Working Groups and the serious work which is done in all of them. In the TWGs, the collaboration between experienced and young researchers supports the scientific development of the young researchers. At CERME11, 575 papers and 152 posters were accepted. 26 TWGs were organized with 8 TWGs which were divided in two subgroups due to the large number of participants. Our sincere thanks are adressed to the 34 working group leaders and 99 co-leaders for their huge and wonderful work. Before the conference, the leaders and co-leaders organized the review process and devoted much time in planning the program of the TWG. As a result, they were able to lead excellent discussions during the work of the TWG at the conference. A wonderful atmosphere and a lot of motivation characterized the work in the working groups. Every participant was involved in the work. After the conference, the authors had the possibility to further revise their papers, integrating significant changes which emerged in the discussions in the TWGs. The leaders and co-leaders organized this final review process.

The work done by all the organizers and deep involvement of the TWG leaders, IPC members, LOC members and ERME board members contributed to the success of the conference. We thank everybody who has contributed to this success. Specific thanks go to Uffe Thomas Jankvist, Miguel Ribeiro, Marja van den Heuvel-Panhuizen, and Michiel Veldhuis for all their work with a wonderful result. We encourage interested researchers to meet us at the next CERME that will take place in February 2021 in Bolzano (Italy).

Susanne Prediger & Ivy Kidron ERME President

ERME Vice-President

Preface: CERME 11 in lovely Utrecht historic sites

  Each second year, the European Society for Research in Mathematics Education (ERME) organises a conference. The 11th Congress of ERME (CERME11) took place in Utrecht (The Netherlands), from February 6 to 10, 2019. The conference was hosted by the Freudenthal Group, in collaboration with the Freudenthal Institute, of Utrecht University. The participants of the conference were offered an excellent academic environment in a place in which important blocks in the foundation of mathematics education research were laid fifty years ago by Freudenthal and his collaborators.

	Susanne Prediger	&	Ivy Kidron
	ERME President		ERME Vice-President
	Dortmund (Germany)		Jerusalem (Israel)
			at
	900 participants. Most participants at CERME11 are European researchers, but CERME is
	getting increasingly international with 152 researchers from outside Europe: Asia (30), North
	-America (54), South-America (40), Australia/New Zealand (9), Africa (19). The European
	researchers are essentially from Germany (169), Norway (82), United Kingdom (57), Sweden
	(54), Italy (40), The Netherlands (39), Israel (36), Spain (36), France (33), Portugal (31),
	Denmark (27), Turkey (26), Greece (23), Ireland (19), Austria (14), Finland (13), Cyprus (11),
	Hungary (8)

CERME is getting larger from congress to congress: from 774 participants at CERME10 to 900 participants at CERME11 -the highest number of participants in comparison with the previous CERMEs. In order to avoid overflow (more than 300 more people were interested in participating), the ERME board had to decide to stop the growth tendencies with stopping , Czech Republic (6), Croatia (5), Switzerland (4), Iceland (3), Slovakia (3), and Poland (2), and many other countries with one participant each.