Jean-Sébastien Gomez

Wei Chen

Bo Bai

Xin Guo

Philippe Martins

Energy-Based Spectrum Sensing For Uplink Downlink Identification

Keywords: Cognitive radio, 5G mobile communication, Spectral analysis, UL/DL identifiation, Energy-based spectrum sensing, Resource block

In this paper, an energy-based spectrum sensing algorithm is proposed to address the problem of Uplink (UL)/Downlink (DL) resource block identification in a single cell. This framework aims to provide a general UL/DL identification tool for interference management algorithms in autonomus cells. The proposed algorithm is base on the observation that user terminals can be active from any part of the cell during DL. And on the contrary, a base station is only active at one single position during DL. Because of these two spatial properties, UL/DL identification is made impossible with only one single sensing equipment -or Secondary User Equipment (SUE). A multiple soft-sensing framework is introduced, using path-loss as spatial information provider. Theoretical analysis and simulations show that the proposed algorithm achieve high reliability, with an error probability decreasing exponentially to zero in the number of SUE.

I. INTRODUCTION

T ECHNOLOGIES in 5G networks will aim to introduce more real-time and more dynamic resource allocation strategies to fulfill energy consumption and data traffic needs. Heterogeneous cell architecture implemented in third generation cell networks, have enhanced cell edge user experience, by optimizing local spatial use of spectrum. Research on interference management between micro-cells and macrocells have brought numerous cooperative and non-cooperative strategies. In this paper, we consider that cooperation between micro and macro-cells is impossible or undesirable due to limited overhead, limited channel capacity, etc. Then, state of the resource blocks (UL or DL) of the macro-cell can be required by the micro-cell to apply the appropriate interference management policy. Spectrum techniques (a core topic in Cognitive Radio) can provide information about the use of the local spectrum environment. In the studied scenario, a microcell or Secondary System (SS) cell is placed in a macro-cell or Primary System (PS) cell. A Secondary Base station (SBS) is Jean-Sébastien Gomez is with the Department of Electronic Engineering, Tsinghua University, Beijing, China, e-mail: jgomez@telecom-paritech.fr.

Pr. Wei Chen is with the Department of Electronic Engineering, Tsinghua University, Beijing, China, e-mail: wchen@tsinghua.edu.cn.

Pr. Bo Bai is with the Department of Electronic Engineering, Tsinghua University, Beijing, China, e-mail: eebobai@tsinghua.edu.cn.

Xin Guo is with Sony China Research Laboratory, Beijing, China, e-mail: Xin.Guo@sony.com.cn.

Professor Philippe Martins is with the department INFRES, Telecom ParisTech, Paris, France, e-mail: martins@enst.fr. This research is supported by Information Technology Development Division, Sony Corporation and Sony China Research Laboratory, Sony (China) Ltd. located at the center of the SS. Secondary Users Equipments (SUE) are randomly spread in the SS cell. To optimize the allocation of resource blocks on point-to-point links, the SS has to retrieve some state information about the PS.

Spectrum sensing techniques have been widely explored in CR papers. Classical CR problems found in the literature, are related to active Primary User (PU) detection. Common spectrum sensing techniques are presented in [START_REF] Beibei Wang | Advances in Cognitive Radio Networks: A Survey[END_REF] and [START_REF] Visotsky | On collaborative detection of TV transmissions in support of dynamic spectrum sharing[END_REF] such as energy-based, cyclostationary and waveform-based frameworks. In early development of CR, single SS equipment sensing has been investigated. Such cognitive equipment would determine itself the availability of the spectrum band. In order to mitigate path-loss, fading and overcoming the hidden primary user issue (i.e. a PU that cannot be detected but will interfere during transmission), sensing results of each SUEs can be combined at a SBS or a super-SUE to get a sensing result. One can distinguish two strategies to merge SUEs information. The first one -called hard-decision process [START_REF] Visotsky | On collaborative detection of TV transmissions in support of dynamic spectrum sharing[END_REF]-considers the spectrum sensing output of each SUE (i.e. presence or absence of a PU using the spectrum band) and merge it through an AND, OR, majority voting or n among m law. In [START_REF] Weiss | A diversity approach for the detection of idle spectral resources in spectrum pooling systems[END_REF], hard-decision process has proven to be sub-optimal compared to the second merging strategy (softdecision process). In this case, raw results are transmitted to a SBS or a super-SUE. SUEs do not have an active role in the computation of the sensing algorithm output. The spectrum sensing algorithm is processed at the SBS or at the super-SUE.

The framework proposed applies soft-decision process to generate a sensing output. However, this paper focuses on Primary User (PU) type differentiation rather than PU detection. Based on the observation of antenna power difference between each type of PU, the PU differentiation problem could be reduced to a trivial PU detection problem. However, because of the spatial characteristics of the two types of PU, such reformulation is made impossible (see next part). In [START_REF] Abdelmonem | Coarse spectrum sensing for LTE systems[END_REF], a UL/DL identification framework based on waveform already exists. But to our knowledge, no energy-based spectrum sensing algorithm has been proposed.

As demodulation of the signal is not needed, the choice of energy-based sensing has been made. Only raw value of the energy received by the SUE is required, cutting down equipment complexity and gaining robustness to privacy policies. The main contribution is the use of path-loss as a criterion to differentiate PU types. In the next section, a closer description of PS system will be given and an energy-based spectrum sensing framework will be proposed. On this basis, an algorithm will be given to discriminate the two types of PUs. The optimality of this algorithm will be proven in part IV. In part V, simulation results will be given for a single cell scenario.

II. SYSTEM DESCRIPTION

In a macro PS cell of radius R, a Primary Base Station (PBS) is placed in the center. Primary User Equipments (PUEs) are uniformly distributed in the cell. SUEs numbered from 1 to N s, are also randomly distributed in the same cell. The SBS which only computes the output result, is omitted on Figure 1. Sensing is performed in a time-frequency slot, in which either the PBS is active (DL state) or a PUE is active (DL state). R and of the coordinates of the SUEs are known by the SS. Definition 1. The space engendered by the energy received by each SUEs is called energy space. Each dimension of the energy space represents the energy received by each SUEs.

Let P k be either P 1 or P 2 , respectively the antenna power of the PBS, or the PUE. The path loss exponentα can take values between 2 and 4. Let D SU Ej -P U be the distance in meters between the active PU and the SUE number j denoted SU E j . Thermal noise due to the measurement of the SUE is considered as a normal random variable Z j and of power P noise . Definition 2. In the energy space, let Et be a vector where the j th coordinate is the energy received by the SU E j in a time-frequency slot. Two assumptions are made on the PS. The first one states that the antenna power of a PBS is far greater than the antenna power of a PUE.

Et(j) = P k D α SU Ej -P U + P noise Z j (1)
P 2 ≫ P 1 (2)
The second one states that the PBS is a static source, whereas a PUE can be active from any position of the cell.

Lemma 3. Under the two stated assumptions, the spectrum sensing energy space must be at least of dimension two to ensure UL/DL identification.

Proof: The identification of UL and DL is assumed to be possible in an energy space of dimension one. The following situation: α = 2, P 2 = 100 • P 1 is considered. A SUE is placed at 1 meter from a PUE and 10 meters from the PBS. Counterexample. Because of path loss, it is not possible to discriminate the source.

Therefore, the same amount of energy is received by SUE in DL and UL state. Thus identification is not possible. Hence to ensure UL/DL identification, the spectrum sensing energy space must be at least of dimension two.

Let (r, θ) and (R k , θ k ) be respectively the polar coordinates of an active PUE and the SUE number k (SU E k ). Letρ k (r, θ) be the distance between SU E k and the active PUE. Let N s be the number of SUEs. Definition 4. Let f be the mapping between the positions of a PUE of coordinate (r, θ) and the spectrum sensing energy space:

f : (r, θ) →        P 1 ρ α 1 (r, θ) . . . P 1 ρ α N s (r, θ)        (3)
Let the image of f be defined by:

D = P ∈ R N s |∃(r, θ) ∈ [0, R] × [0, 2π], f (r, θ) = P (4)
Definition 5. Let E 2 be the vector engendered by the PBS in the spectrum sensing energy space:

E 2 =        P 2 R α 1 . . . P 2 R α N s       
(5) Figure 3 gives an example of the shape of D and relative position of E 2 in dimension two. In UL state, the vector Et will appear in D, or at least in the topological neighborhood of the set D. As for DL state, Et will appear in the neighborhood of E 2 . Hence, identifying UL or DL state becomes equivalent to separate D and E 2 . A strategy for finding a frontier between these two subspaces is therefore proposed in the next part.

E 1i (j) = P 1 ρ α j (r i , θ i ) (6)
The notation •, • is introduced for the inner product in the energy space. For more clarity, E 1i E 2 represents the vector E 2 -E 1i .

Definition 7. A decision hyperplane H i is associated to each element E 1i . H i is defined by its normal vector E 1i E 2 and the middle of the segment

[E 1i , E 2 ] P ∈ R N s | P, E 1i E 2 = E 1i + 1 2 E 1i E 2 , E 1i E 2 (7)

B. Algorithm

The algorithm is performed in two steps. In the first step (figure 4), the vector from S that best matches the direction of the vector Et is selected. Let i0 be the index of this vector. In the second step (figure 5), the position of Et is compared relatively to the position of the hyperplane H i0 . If Et is "over" the hyperplane H i0 , then the PS is considered in DL state. Otherwise, the system is considered in UL state.

IV. THEORETICAL ANALYSIS

Assumption 1: The minimum distance between two test vectors in the energy space is bigger than the noise power. This situation is encountered for high SNR, big values of N , and low noise power value P noise , or in low SNR, small values of N and high noise power value P noise . Assumption 2: Let P i be the probability of selecting the test vector number i. Regardless of the state of the PS,

P noise ≪ min (i,j)∈[|1,N S |] 2 ( E 1i E 1j ) (8) Algorithm 1 Decision algorithm i0 = 1; /*Step one*/ for i = 2 to N s if Et, E 1i E 1i ≥ Et, E 1i0 E 1i0 then i0 = i; end end /*Step two*/ if E t , E 1i0 E 2 ≥ E 1i0 + 1 2 E 1i0 E 2 , E 1i0 E 2 then return DL; else return UL;
P i = 1 N (9)
A. Optimality of the algorithm Theorem 8. The proposed sensing algorithm minimizes the error probability P e . P e is given by:

P e = N i=1 1 N • Q E 1i E 2 2P noise ( 10
)
Proof: Proposition 9 ensures the optimality of step one and proposition 10 ensures the optimality of step two in terms of error probability. Hence, the proposed sensing algorithm minimizes the overall error probability P e . Proposition 9. The selected test vector E 1i0 is the one minimizing the error probability P e .

Proof: Considering assumption 1, the influence of the noise in the selection of the test vector is minimized. Noise is indeed constraint in a sphere of radius P noise , thanks to Chebyshev inequality. The deviation angle of the vector Et is therefore mainly due to the position of the active PUE in the PS cell rather than noise. The selected test vector E 1i0 is the one which best matches the spacial configuration of the currently active PUE, introducing the smallest error.

Proposition 10. The position of the hyperplanes H i are those minimizing the error probability P e .

Proof: The direction of the hyperplane is already optimal because of assumption 1. A hyperplane H i has for normal direction the vector E 1i E 2 . A particular point O i of the hyperplane is given by the middle of the segment

[E 1i E 2 ].
We want to demonstrate that for each i, O i is the optimal point on the segment. Let's consider :

O i : t i → E 1i + t i E 1i E 2 (11)
with t i ∈ [0, 1]. The error probability, when the PS is in UL state and when the PS in in DL state, for the test vector number i, are respectively given by:

P DL/U L,i = Q t i E 1i E 2 P noise (12)
P U L/DL,i = Q (1 -t i ) E 1i E 2 P noise (13)
Considering assumption 2, the probability error P e is given using the law of total probability by: P e = P DL P i P U L/DL,i + P U L P i P DL/U L,i

Let C = E 1i E2 Pnoise .

P e = N i=1 1 2N • [Q (t i • C) + Q ((1 -t i ) • C)] (15)
It is clear that P e is a convex function for each t i in [0, 1].

Then to find the minimum error probability, it suffices that for each i: ∂P e ∂t i = 0 (16)

A trivial solution of ( 16) is given for

t i = 0.5 (17)
This proves that if O i is the middle of the segment [E 1i E 2 ] for all i, P e is minimal.

B. Influence of the number of SUEs

Theorem 11. The error probability P e is going to zero exponentially as the dimension of the energy space is increasing.

Proof:

As E 1i E 2 = 0, let E 1im E2(j m ) = min i,j, E1iE2(j) =0 (E 1i E2(j)) (18)
Using the Chernoff bound of the Q-function in equation ( 10) we have:

P e ≤ 1 2 exp - N s • (E 1im E2(j m )) 2 2P 2 noise ( 19
)
Hence the error probability is going down to zero exponentially as the number of SUEs increases. Remark 12. One can notice that the number of test vectors N has no influence on the error probability. In figure 6, the decision region is given by several hyperplanes. However, adding hyperplanes will not influence in a decisive manner the error probability, because the decision volume added by the new hyperplanes is small compared to the sphere of radius P noise .

C. An analytical approximation for the error probability

As the term E1 im E 2 (j m ) is difficult to evaluate, an analytical approximation is proposed for the error probability.

Definition 13. Let SN R min , the quantity representing the SNR for a SUE and PUE placed at the edge of the PS cell and diametrically opposed. In this situation, SNR is minimum.

SN R min

= P 1 (2R) α P noise (20) Proposition 14. P e ≈ Q 2 α-1 (k -1)SN R min √ N s
Proof: Let k be:

k = P 2 P 1 (21)
Hence considering definition 13, equation (10) becomes:

P e ≈ Q 2 α-1 (k -1)SN R min N s (22)
V. SIMULATIONS This sensing algorithm has been tested on one scenario: single PS cell environment. Simulation parameters are given in table 1. The influence of two parameters of the algorithm In figure 7, no obvious correlation can be observed between the number of test vectors and the evolution of the error probability. This confirms the argument given in remark 12. In figure 8, the more SUEs, the smaller the error probability. The analytical formula given in proposition 14 is an optimistic approximation of the error probability. However both curves shape are alike.

VI. CONCLUSION

In this paper we have introduced an energy-based spectrum sensing algorithm using soft-decision process to identify the two types of PU. Path-loss ensures that the energy received in UL and DL resource blocks is constraint in the neighborhood of two different subspaces. The proposed decision algorithm is performed in two steps. The first step relies on test vectors to diminish complexity. In the second step, UL/DL identification is done by a simple position comparison of the current received energy vector and the selected decision hyperplane. Simulation results shows that the error probability is going exponentially to zero with the number of SUEs, confirming theoretical analysis.

Figure 1 .

 1 Figure 1. An Example of PS and SS configuration

Figure 2 .

 2 Figure 2.Counterexample. Because of path loss, it is not possible to discriminate the source.

Figure 3 .

 3 Figure 3. Shape of D and relative position with E 2

Figure 4 .

 4 Figure 4. Algorithm step one. The test vector circled in red, is selected.

Figure 5 .

 5 Figure 5. Algorithm step two. If Et is in the blue part, then we consider that PS is in UL state. Otherwise we consider that PS is in DL state.

Figure 6 .

 6 Figure 6. Example of decision domain for 3 test vectors, symbolized by the interface between the red and blue subspace.

Figure 8 .

 8 Figure 8. Influence of the number of SUEs on the error probability. In green the theoretical approximation, in blue, the simulation results, in red the Chernoff bound of the approximation. N = 400.


Erwan Brugall

Pierre-Vincent Koseleff

Daniel Pecker

UNTANGLING TRIGONAL DIAGRAMS

Keywords: Mathematics Subject Classification. 14H50, 57M25, 11A55, 14P99 Two-bridge knots, polynomial knots. 1

Let K be a link of Conway's normal form C(m), m ≥ 0, or C(m, n) with mn > 0, and let D be a trigonal diagram of K. We show that it is possible to transform D into an alternating trigonal diagram, so that all intermediate diagrams remain trigonal, and the number of crossings never increases.

Introduction

If we try to simplify a knot or link diagram, then the number of crossings may have to be increased in some intermediate diagrams, see [START_REF] Göritz | Bemerkungen zur Knoten theorie[END_REF][START_REF] Kauffman | Hard unknots and collapsing tangles, Introductory lectures on knot theory[END_REF]A,[START_REF] Cromwell | Knots and links[END_REF]. In this paper, we shall see that this strange phenomenon cannot occur for trigonal diagrams of two-bridge torus links and for generalized twist links. The next theorem is the main result of this paper.

Theorem 1.1. Let K be a link of Conway's normal form C(m), m ≥ 0, or C(m, n) with mn > 0, and let D be a trigonal diagram of K. Then, it is possible to transform D into an alternating trigonal diagram, so that all intermediate diagrams remain trigonal, and the number of crossings never increases.

We also prove that if K is a two-bridge link which is not of these two types, then K admits diagrams that cannot be simplified without increasing the number of crossings. Our original motivation to tackle this problem is the study of polynomial knots, their polynomial isotopies and their degrees, see examples in Figure 1, [START_REF] Brugallé | On the lexicographic degree of two-bridge knots[END_REF][START_REF] Koseleff | On polynomial Torus Knots[END_REF][START_REF] Koseleff | Chebyshev knots[END_REF][START_REF] Ranjan | On polynomial representation of torus knots[END_REF][START_REF] Vassiliev | Cohomology of knot spaces, Theory of singularities and its Applications[END_REF]. In particular this is why we prefer to consider our knots as long knots. As an application of Theorem 1.1, we determine in [BKP] the lexicographic degree of two-bridge knots of Conway's normal form C(m) with m odd, or C(m, n) with mn positive and even.

The paper is organized as follows. In Section 2, we recall Conway's notation for trigonal diagrams of two-bridge links, and their classification by their Schubert fractions. In Section 3 we define slide isotopies as trigonal isotopies such that the number of crossings never increases. We find necessary conditions for a twobridge link diagram to be simple, that is to say it cannot be transformed into a simpler diagram by any slide isotopy. We use continued fraction properties to prove Theorem 1.1 in Section 4. In Section 5 we show that if a two-bridge link is neither a torus link nor a twist link, then it possesses awkward trigonal diagrams.

Trigonal diagrams of two-bridge knots

A two-bridge link admits a diagram in Conway's open form (or trigonal form). This diagram, denoted by D(m 1 , m 2 , . . . , m k ) where m i ∈ Z * are integers, is explained by the following picture (see [Co], [M, p. 187]). The number of twists is denoted by the integer |m i |, and the sign of m i is defined as follows: if i is odd, then the right twist is positive, if i is even, then the right twist is negative. In Figure 2 the m i are positive (the m 1 first twists are right twists). These diagrams are also called 3-strand-braid representations, see [START_REF] Kauffman | On the classification of rational knots[END_REF][START_REF] Kauffman | Hard unknots and collapsing tangles, Introductory lectures on knot theory[END_REF].

The two-bridge links are classified by their Schubert fractions [START_REF] Murasugi | Knot Theory and its Applications[END_REF]Theorem 9.3.3]. The integer α is odd for a knot, and even for a two-component link. It is classical that one can transform any trigonal diagram of a two-bridge link into its Conway's normal form using the Lagrange isotopies, see [START_REF] Kauffman | Hard unknots and collapsing tangles, Introductory lectures on knot theory[END_REF] or [START_REF] Cromwell | Knots and links[END_REF]p. 204]:

α β = m 1 + 1 m 2 + 1 • • • + 1 m k = [m 1 , . . . , m k ], α > 0, (α, β) = 1. Given [m 1 , . . . , m k ] = α β and [m ′ 1 , . . . , m ′ l ] = α ′ β ′ , the diagrams D(m 1 , m 2 , . . . , m k ) and D(m ′ 1 , m ′ 2 , . . . , m ′ l ) correspond to isotopic links if and only if α = α ′ and β ′ ≡ β ±1 (mod α), see
(1)

D(x, m, -n, -y) → D(x, m -ε, ε, n -ε, y), ε = ±1,
where m, n are integers, and x, y are sequences of integers (possibly empty), see Figure 3. These isotopies twist a part of the diagram, and the number of crossings

m -1 1 -n m -1 n -1 Figure 3. Lagrange isotopies
may increase in intermediate diagrams. Since we want to simplify links without increasing their complexity, we introduce different isotopies in the following section.

3. Slide isotopies, simple and awkward diagrams Definition 3.1. We shall say that an isotopy of trigonal diagrams is a slide isotopy if the number of crossings never increases and if all the intermediate diagrams remain trigonal.

Example 3.2. Some diagrams of the torus knot 5 Then we have

1 = C(5): D(5), D(2, 1, -1, -2), D(-1, -1, -1, 1, 1, 1), D(-2, 2, -2, 2),
(i) |m 1 | ≥ 2; |m k | ≥ 2; m i = 0, i = 2, . . . , k -1; (ii) m 1 m 2 > 0 or |m 1 | ≥ 3; m k-1 m k > 0 or |m k | ≥ 3; (iii) for i = 2, . . . , k, m i-1 m i = -1; (iv) suppose that |m i | = 1, then (a) if m i-1 m i < 0, then i ≤ k -2, m i m i+1 > 0, and m i m i+2 > 0; (b) if m i m i+1 < 0, then i ≥ 3, m i-2 m i > 0, and m i-1 m i > 0.
Proof. (iv) By (i) we have i = 1 and i = k. Let us assume that m i-1 m i < 0, the proof in the case m i m i+1 < 0 being entirely similar. The slide isotopy D(x, m, -1, n) → D(x, m -1, -n + 1) depicted in Figure 10 shows that i ≤ k -2. Since D is minimal, the slide isotopy D(x, m, -1, n, p, y) → D(x, m-1, -n, 1, p-1, y) depicted in Figure 11 implies that p < 0, that is

m i m i+2 > 0. m -1 n m -1 -n m -1 -n + 1 m -1 -n + 1 Figure 10. The slide isotopy D(x, m, -1, n) → D(x, m -1, -n + 1), m > 0
Now, assume that m i m i+1 < 0. Let i be the maximal integer such that there exists a simple diagram D(m 1 , . . . m k ) of length k such that |m i | = 1, m i-1 m i < 0, and m i m i+1 < 0. Once more we use the slide isotopy D(x, m, -1, n, p, y) → D(x, m -1, -n, 1, p -1, y) depicted in Figure 11. Since p = m i+2 > 0 and n = m i+1 > 0 by assumption, the new diagram contradicts the maximality of i.

2 m -1 n p m -1 -n p m -1 -n p Figure 11. The slide isotopy D(x, m, -1, n, p, y) → D(x, m - 1, -n, 1, p -1, y), m > 0, p < 0
The condition (iv) of Proposition 3.8 asserts that a simple diagram cannot contain any subsequence ±(m, -1, n), m, n > 0. Nevertheless, it can contain subsequences of the form ±(m, -1), m > 1. However, the next corollary shows that this phenomenon can be avoided.

Corollary 3.9. Let D be a trigonal Conway diagram of a two-bridge link. Then it is possible to transform D by slide isotopies into a simple diagram D(m 1 , . . . , m k ) such that for i = 2, . . . , k, either

|m i | = 1, or m i-1 m i > 0.
Proof. Let us suppose that each simple diagram deduced from D by slide isotopies contains subsequences of the form ±(m, -1), m ≥ 2, and let µ = 0 be the minimum number of such subsequences. Among all simple diagrams D(m 1 , . . . , m k ) deduced from D by slide isotopies and possessing µ such subsequences there is a minimal integer r such that (m r-1 , m r ) = ±(m, -1), m ≥ 2. By Proposition 3.8, (iv) we have r ≤ k -2 and our diagram is of the form ∆ = D(x, m, -1, n, p, y), where n, p < 0. The use of the slide isotopy depicted in Figure 11 The proof is based on some arithmetical properties of the continued fractions [m 1 , . . . , m k ] related to simple diagrams D(m 1 , . . . , m k ), that are consequences of Proposition 3.8 and Corollary 3.9.

Lemma 4.1. Let x be a rational number defined by its continued fraction expansion

x = α β = [m 1 , m 2 , . . . , m k ], m 1 > 0, |m k | ≥ 2, m i ∈ Z * , α ≥ 0.
m 2 + 1 ≥ 2. If m 2 < 0, then we have |m 2 | ≥ 3. Then β = |m 2 | ≥ 3 and α = m 1 |m 2 | -1 ≥ 3m 1 -1 ≥ 2. Let us suppose now that k ≥ 3. Let x = m 1 +q/p, where p/q = [m 2 , . . . , m k ], p > 0.
If m 2 > 0, then β = p ≥ 2 and q ≥ 2 by induction, and then α

= m 1 p + q ≥ 2. If m 2 < 0, then -m 2 ≥ 2. By induction, [-m 2 -1, -m 3 , . . . , -m k ] = p + q -q is such that p + q ≥ 2 and -q ≥ 2. Consequently, we obtain β = p ≥ 2 -q ≥ 4 ≥ 2, and α = m 1 p + q = m 1 (p + q) + (m 1 -1)(-q) ≥ 2m 1 ≥ 2. (c) If m 2 > 0, then x > m 1 ≥ 2. If m 2 < 0, then m 1 ≥ 3, and then x > m 1 -1 ≥ 2 by (a).
(d) If m 2 < 0, then -m 2 ≥ 2 and as in the proof of (b) we get p + q ≥ 2 and -q ≥ 2, where p -q = [-m 2 , . . . , -m k ] > 1. Consequently we obtain p ≥ 2q > 1q > 0 and then q ≡ 1 (mod p). As α = m 1 p + q and β = p, the result is proved in this case. Proof. Using the identity az + 1 (a -1)z + 1 = [2, -2, 2, . . . , (-1) a-2 2 a-1 terms , (-1) a-1 (z + 1)],

we obtain [m, a, n] = [m + 1, -an + 1 (a -1)n + 1 ] = [m + 1, -2, 2, -2, . . . , (-1) a-1 2, (-1) a (n + 1)],

and we deduce that [m 1 , . . . , m k ] = [x, m, a, n] = [x, m + 1, -2, 2, . . . , (-1) a-1 2, (-1) a (n + 1)].

Therefore, the diagram D = D(x, m + 1, -2, 2, . . . , (-1) a-1 2, (-1) a (n + 1)) is a diagram of K, and it is a hard diagram by Remark 3.7. 2

Remark 5.3. Theorem 1.1 shows that the trivial knot has no trigonal awkward diagram. On the other hand, Göritz found an awkward diagram of the trivial knot in [G], and Kauffman and Lambropoulou constructed many such examples (see [START_REF] Kauffman | Hard unknots and collapsing tangles, Introductory lectures on knot theory[END_REF]A,[START_REF] Cromwell | Knots and links[END_REF]).

Figure 1 .

 1 Figure 1. Polynomial representations of the knots 4 1 and 5 1

Figure 2 .

 2 Figure 2. Conway's form for long links

  Any fraction admits a continued fraction expansion α β = [m 1 , . . . , m k ] where all the m ′ i s have the same sign. Therefore every two-bridge link K admits a diagram in Conway's normal form, that is an alternating diagram of the form D(m 1 , m 2 , . . . m k ) where all the m ′ i s have the same sign. In this case we will write L = C(m 1 , . . . , m k ).

  and D(2, 2, -1, 2, 2) are depicted in Figure4. By Theorem 1.1, it is possible to simplify these diagrams into the alternating diagram D(5) by slide isotopies only.

Figure 4 .

 4 Figure 4. Some trigonal diagrams of the torus knot 5 1

Figure 5 .Figure 6 .

 56 Figure 5. The two diagrams D and D with the same Conway notation.

  (i) the slide isotopy D(x, m, 0) → D(x) diminishes the complexity, consequently m k = 0, and similarly m 1 = 0. The slide isotopy D(x, m, 1) → D(x, m + 1) diminishes the complexity, see Figure7. Consequently m k = 1 since D is simple. We also have m k = -1, and similarly m 1 = ±1. The slide isotopy D(x, m, 0, n, y) → D(x, m + n, y) shows that m i = 0.

m m + 1 Figure 7 . 1 Figure 8 .Figure 9 .

 17189 Figure 7. The slide isotopy D(x, m, 1) → D(x, m + 1)

  : ∆ → ∆ ′ = D(x, m -1, -n, 1, p -1, y),contradicts the minimality of either µ or r. 2 4. Proof of Theorem 1.1

  Suppose that for i = 2, . . . , k, we have either |m i | = 1 or m i-1 m i > 0. Then the following hold:(a) x > m 1 -1, and consequently α > 0 andβ > 0; (b) if k ≥ 2 and (m k-1 m k > 0 or |m k | ≥ 3), then α ≥ 2 and β ≥ 2; (c) if in addition we have m 1 ≥ 2 and (m 1 m 2 > 0 or m 1 ≥ 3) then x > 2; (d) if in addition we have k ≥ 3 and (|m 2 | = 1 or m 2 m 3 > 0), then α ≡ 1 (mod β).Proof. (a) We use an induction on k. If k = 1, then we have x = m 1 > m 1 -1, and the result is true. Let us suppose that k ≥ 2. If m 2 > 0, then we have y = [m 2 , . . . , m k ] > 0, and then x = m 1 + 1/y > m 1 > m 1 -1. If m 2 < 0, then by assumption -m 2 ≥ 2. By induction we have y = [-m 2 , . . . , -m k ] > 1, and then x = m 1 -1/y > m 1 -1. (b) We use again an induction on k. If k = 2, then there are two cases to consider. If m 2 > 0, then we have β = m 2 ≥ 2, and α = m 1

Figure 12 .

 12 Figure 12. The awkward diagrams D(x, m+1, -1, 1-a, -n) and D(x, m + 1, -n -1).

Suppose now that m 2 > 0, and consider u v = [m 3 , . . . , m k ] with u > 0. In particular, we have β = m 2 u + v, and α = m 1 β + u ≡ u (mod β).

If m 3 > 0, then v > 0 and so β > u. If k = 3, then u = m 3 ≥ 2. If k > 3, then we have u ≥ 2 by (b). Hence β > u ≥ 2, and so α ≡ u ≡ 1 (mod β).

If m 3 < 0, then m 2 ≥ 2, -m 3 ≥ 2, and v < 0. We have u -v > 1 by (a), i.e.

u > -v. Hence we have β ≥ 2u + v > u ≥ 2, and we obtain α ≡ u ≡ 1 (mod β). 2

Proof of Theorem 1.1. Let D(m 1 , . . . , m k ) be a simple diagram deduced from D by admissible isotopies, and satisfying the condition of Corollary 3.9. Recall that it also satisfies all conclusions of Proposition 3.8. We write

with α > 0 and (α, β) = 1. Without loss of generality, we may assume that both m and n are nonnegative.

Let us first consider the case when K is the torus link C(m).

Some awkward trigonal diagrams

The following result shows that if a two-bridge link is not of the Conway normal form C(m), or C(m, n) with mn > 0, then it possesses an awkward trigonal diagram.

Proposition 5.1. Let k ≥ 3 and let K be a two-bridge link of Conway normal form

Therefore K admits the trigonal diagram D(m 1 , . . . , m k-3 , m + 1, -1, 1a, -n), if a > 1; or D(m 1 , . . . , m k-3 , m + 1, -n -1) if a = 1. These two diagrams are awkward (see Figure 12).

2

Furthermore, we have a stronger result.


Erwan Brugallé

Pierre-Vincent Koseleff

Daniel Pecker

Erwan Brugall

On the lexicographic degree of two-bridge knots

Keywords: Mathematics Subject Classification. 14H50, 57M25, 11A55, 14P99 Real pseudoholomorphic curves, polynomial knots, two-bridge knots. 1

. We also give a sharp lower bound for the lexicographic degree of any knot, using real polynomial curves properties.

Introduction

It is known that every knot in S 3 can be represented as the closure of the image of a polynomial embedding R → R 3 ⊂ S 3 , see [START_REF] Shastri | Polynomial representation of knots[END_REF][START_REF] Vassiliev | Cohomology of knot spaces, Theory of singularities and its Applications[END_REF]. In these early papers on the subject, only a few specific examples were given. The two-bridge torus knots form the first infinite family of knots for which a polynomial representation was explicitly given, see [START_REF] Ranjan | On polynomial representation of torus knots[END_REF][START_REF] Koseleff | On polynomial Torus Knots[END_REF][START_REF] Koseleff | Chebyshev knots[END_REF][START_REF] Koseleff | Chebyshev diagrams for two-bridge knots[END_REF].

Example 1.1 (Harmonic knots ([KP11, KP12])). The harmonic knot H(a, b, c) is the polynomial knot parametrized by (T a (t), T b (t), T c (t)), where T n is the classical Chebyshev polynomial T n (cos t) = cos nt and a, b, c are pairwise coprime integers. The two knot diagrams depicted in Figure 1 The multidegree of a polynomial map γ : R → R n , t → (P i (t)) is the n-tuple (deg(P i )). The lexicographic degree of a knot K is the minimal multidegree, for the lexicographic order, of a polynomial knot whose closure in S 3 is isotopic to K. The unknot has lexicographic degree (-∞, -∞, 1), and one sees easily that the lexicographic degree of any other knot is (a, b, c) with 3 ≤ a < b < c. Given a knot, it is in general a difficult problem to determine its lexicographic degree.

In particular, the corresponding diagram might not have the minimal number of crossings.

In this paper we investigate the case of two-bridge knots, that are the knots for which a = 3, see [START_REF] Cromwell | Knots and links[END_REF][START_REF] Koseleff | Chebyshev diagrams for two-bridge knots[END_REF][START_REF] Brugallé | Untangling trigonal diagrams[END_REF]. We focus in particular on two-bridge torus knots and generalized twist knots, that we respectively denote by C(m) with m odd, and C(m, n) with mn positive and even (see Figure 2). Note that C(-m) and C(-m, -n) are the mirror images of C(m) and C(m, n). Mishra claimed in [START_REF] Mishra | Minimal degree sequence for torus knots[END_REF] that the lexicographic degree of the torus knot C(m), m ≡ 2 (mod 3), is (3, m + 1, c). Later on, it was proved in [START_REF] Koseleff | On polynomial Torus Knots[END_REF] that this is false for every integer m > 5. At that stage, the lexicographic degree of only a few knots was known, namely the trefoil, the figure-eight knot, the torus knot 5 1 [START_REF] Mishra | Minimal degree sequence for torus knots[END_REF], and the torus knot 7 1 [START_REF] Koseleff | On polynomial Torus Knots[END_REF].

For every two-bridge knot of crossing number N , a polynomial representation of degree (3, b, c), with b + c = 3N and b ≥ N + 1 is constructed in [START_REF] Koseleff | Chebyshev diagrams for two-bridge knots[END_REF]. From that construction an upper bound for the lexicographic degree of two-bridge knots is immediately deduced. The main result of this paper is that this upper bound is sharp for two-bridge torus knots and for generalized twist knots. Theorem 3.9. Let K be the two-bridge knot C(m), or C(m, n) with mn > 0, and let N be its crossing number. Then the lexicographic degree of K is

3, 3N -1 2 , 3N 2 + 1 .
The proof goes by the study of the plane curve defined by the xy-projection of a polynomial knot, and uses Orevkov's braid theoretical approach to study real plane curves (see [START_REF] Yu | Link theory and oval arrangements of real algebraic curves[END_REF] or Section 2). Like in the case of knots, we define the lexicographic degree of a long knot diagram as the minimal multidegree, for the lexicographic order, of a polynomial knot whose xy-diagram is isotopic in R 2 to D.

The main idea in the proof of Theorem 3.9 is as follows. Suppose that D 1 is a trigonal long knot diagram with lexicographic degree (3, b, c). If D 2 is a trigonal diagram obtained from D 1 by an isotopy through trigonal diagrams which never increases the number of crossings, then one may expect that it has lexicographic degree (3, b ′ , c ′ ) with b ′ ≤ b. If this was the case, then Theorem 3.9 would follow from the study of the alternating diagrams C(m) or C(m, n), combined with the following theorem. Unfortunately, one cannot ensure that the lexicographic degree of a trigonal knot diagram does not increase during an isotopy, even if this isotopy never increases the number of crossings. For this to be true, one needs to enlarge the set of objects we are studying, namely we have to consider real pseudoholomorphic curves (see Corollary 3.7). Note that a real algebraic curve is real pseudoholomorphic, however the converse is not true in general.

We conclude the paper by providing a lower bound for the lexicographic degree of every non-trivial knot. We also give the lexicographic degree of some infinite families of knots, showing in particular that this lower bound is sharp.

Theorem 4.3. Let K be a knot of crossing number N > 0. Then the lexicographic degree of K is at least (3, N + 1, 2N -1). For every integer N ≡ 2 (mod 3), N ≥ 3, there exists a knot of crossing number N and lexicographic degree (3, N + 1, 2N -1).

The paper is organized as follows. We recall Orevkov's braid theoretical method in Section 2. To avoid technical difficulties coming from an excess of generality, we restrict ourselves to the case of real curves of bidegree (3, b), whereas the whole section generalizes to all bidegrees. We prove Theorem 3.9 in Section 3. To keep the exposition as light as possible we keep working with real algebraic curves as long as pseudoholomorphic curves are not needed. In particular we prove the lower bound of Theorem 3.9 in the particular case of the diagrams C(m) and C(m, n) for real algebraic curves (Proposition 3.1). We introduce real pseudoholomorphic curves only in Section 3.2 to deduce the general lower bound of Theorem 3.9 from Proposition 3.1 (Proposition 3.8). In Section 4, we first obtain a sharp lower bound for alternating diagrams. The proof is elementary, it is based on polynomial plane curves properties. As a consequence, we deduce Theorem 4.3 and an upper bound for the crossing number of alternating knots of polynomial degree d.

The braid of a real algebraic curve in C 2

Here we recall basic facts about the braid theoretical approach developed by Orevkov to study real algebraic curves in C 2 . 2.1. Link associated to a real algebraic curve. Given C ⊂ C 2 a real algebraic curve, we denote by RC the real part of C, i.e. RC = C ∩ R 2 . Let us fix an orientation preserving diffeomorphism Φ : R 4 → {(x, y) ∈ C 2 | Im (x) > 0}, and let us denote by B r the image by Φ of the 4-ball of radius r, and by S r = ∂B r the image by Φ of the 3-sphere of radius r. If C ⊂ C 2 is a real algebraic curve, then all links S r ∩ C (resp. all surfaces B r ∩ C) are isotopic if r is large enough.

Definition 2.1. The link L C = S r ∩ C, for r large enough, is called the link associated to the real algebraic curve C.

We denote U C = B r ∩ C, and we orient L C as the boundary of U C . We will use the following standard proposition in the proof of Theorem 3.9. The linking number of two oriented links L 1 and L 2 is denoted by lk (L 1 , L 2 ); the algebraic intersection number of two smooth surfaces U 1 and U 2 in B r intersecting transversally and in B r \ S r is denoted by

U 1 • U 2 . Proposition 2.2. If L 1 and L 2 are two sublinks of L C which bound two components U 1 and U 2 of N C , then lk (L 1 , L 2 ) = U 1 • U 2 .
It turns out that in some situations, one can read directly on the real part RC an expression of the oriented link L C as a closed braid. For the sake of simplicity, we restrict ourselves here to the very special case of trigonal rational curves. For the general case, we refer to [START_REF] Yu | Link theory and oval arrangements of real algebraic curves[END_REF]. In what follows, we are interested in curves in C 2 up to isotopies respecting the fibration of C 2 by vertical lines.

Definition 2.3. An isotopy on a curve C ⊂ C 2 is called a L-isotopy if it commutes with the projection π : C 2 → C, (x, y) → x.
Let us consider a polynomial map

γ : C -→ C 2 t -→ (P (t), Q(t))
where P (t) and Q(t) are two real polynomials of degrees 3 and b ≥ 1. Replacing P (t) with -P (t) if necessary, we may assume that P (t) is positive for t large enough. We may also assume that b = 3k -1 or b = 3k -2. If b = 3k, then we can replace the map γ by the map t → (P (t), Q(t) -αP k (t)). In the target space C 2 , this corresponds to performing the real change of coordinates y = yαx k and does not affect the topology of the real algebraic curve

C = γ(C) in C 2 .
We suppose in addition that the map γ is generic enough so that:

-

γ is an immersion; -if γ(t 1 ) = γ(t 2 ) for t 1 = t 2 , then γ ′ (t 1 ) = γ ′ (t 2 ) and γ -1 (γ(t 1 )) = {t 1 , t 2 }.
In other words, the only singularities of the embedded algebraic curve C ⊂ C 2 are nodes. Since C is real, it has three kinds of nodes:

(1) the intersection of two real branches of C (i.e. t 1 , t 2 ∈ R); such a real node is called a crossing, see Figure 4a; (2) the intersection of two complex conjugated branches of C (i.e. t 2 = t 1 ); such a real node is called solitary node, see Figure 4b; (3) the intersection of two branches of C which are neither real nor complex conjugated; all such nodes lie in C 2 \ R 2 and come in pairs of complex conjugated nodes. We denote by N the number of crossings of C, by α the number of solitary nodes of C and by 2β its number of nodes lying in C 2 \ R 2 . Hence the real part RC is the union of γ(R) together with the α solitary nodes of C. Proof. The Newton polygon T of the curve γ(C) is the triangle with vertices (0, 0), (0, 3) and (b, 0), and the number of nodes of γ(C) is the number of points in Z 2 contained in the interior of T .

Example 2.5. Let 1/ √ 3 < ν < 1. Using elementary elimination theory, one sees that the real part of the parametrized curve γ :

t → (T 3 (t), T 4 (t + ν)) is depicted, up to L-isotopy, in

Now let us consider the set

A = π -1 (R) ∩ C.
It consists in the real part RC together with some pairs of complex conjugated arcs, meeting at critical points of the map π |RC (i.e. at points of RC which intersect a vertical line non-transversely).

Example 2.6. The set A in the case of the parametrization of Example 2.5 is depicted in Figure 5b. The dotted curves correspond to complex conjugate arcs. The set A is not a manifold because of critical points of the map π |RC . However there is a canonical way to perturb A to a 1-dimensional manifold and to recover the link L C . Let R 1 , R 2 and ε be some positive real numbers, and let

V 1 = π -1 ({x ∈ C | |x| ≤ R 1 and Im (x) > ε}) and V 2 = {y ∈ C | |y| ≤ R 2 }.
Then for R 1 and R 2 large enough, and ε small enough, the link

C ∩ ∂ (V 1 × V 2 ) in ∂ (V 1 × V 2 ) ≃ S 3 is precisely the link L C , and the surface C ∩ (V 1 × V 2 ) is precisely the surface U C in V 1 ×V 2 ≃ B 4 . Moreover the link C ∩∂ (V 1 × V 2 )
appears naturally as the closure of a braid b C , that we describe in the next section.

2.2. The link L C as a closed braid. Recall that the group of braids with 3-strings is defined as

B 3 = σ 1 , σ 2 |σ 1 σ 2 σ 1 = σ 2 σ 1 σ 2 .
This terminology comes from the fact that there exists a natural geometric interpretation of σ 1 , σ 2 , and of the relation σ 1 σ 2 σ 1 = σ 2 σ 1 σ 2 as depicted in Figure 6. Note that a string of a braid is implicitly oriented from left to right. In particular if an oriented link L is represented as the closure of a braid b, then the linking number of two sublinks L 1 and L 2 of L is half the sum of all exponents of b corresponding to the crossings of L 1 and L 2 .

a) σ 1 b) σ 2 c) σ 1 σ 2 σ 1 = σ 2 σ 1 σ 2 Figure 6.
Let us associate an L-scheme to the real curve C. Denote by l 1 < l 2 < . . . < l s the real vertical lines of C 2 which are not transversal to C (the order on the l i 's is the one induced by the canonical orientation of R). Recall that the degree of the polynomial

Q(t) is b = 3k -1 or b = 3k -2.
Definition 2.7. The L-scheme L C realized by C is given by the sequence c 1 c 2 . . . c s+1 where c i with 1 ≤ i ≤ s is given by

-c i =⊃ j (resp. c i =⊂ j ) if 1 ≤ i ≤ s
; -c i = × j (resp. c i = • j ) if i ≤ s and l i passes through a crossing (resp.
solitary node) of RC; (in each case j = 1 if the transverse intersection point of Rl i and RC is below the second point of Rl i ∩ RC, and j = 2 otherwise) and c s+1 is given by -c s+1 =↓ (resp. ↑) if b = 3k -1, and Q(t) is positive (resp. negative) for t large enough; -c s+1 = ∨ (resp. ∧) if b = 3k -2, and Q(t) is positive (resp. negative) for t large enough.

Example 2.8. The L-scheme realized by the parametrization of Example 2.5 is

• 1 ⊂ 1 × 2 × 1 ⊃ 1 ∨. Then replace the L-scheme c 1 c 2 . . . c s+1 by c ′ 0 c 1 c 2 . . . c ′ s+1 where -c ′ 0 =⊃ 2 (resp. ⊃ 1 ) and c ′ s+1 =⊂ 1 if c s+1 =↓ and k is even (resp. odd); -c ′ 0 =⊃ 1 (resp. ⊃ 2 ) and c ′ s+1 =⊂ 2 if c s+1 =↑ and k is even (resp. odd); -c ′ 0 =⊃ 2 (resp. ⊃ 1 ) and c ′ s+1 =⊂ 1 ⊃ 1 ⊂ 1 if c s+1 = ∨ and k is even (resp. odd); -c ′ 0 =⊃ 1 (resp. ⊃ 2 ) and c ′ s+1 =⊂ 2 ⊃ 2 ⊂ 2 if c s+1 = ∧ and k is even (resp. odd).
Finally replace each • j with ⊂ j ⊃ j and each × j with ⊃ j ⊂ j in c ′ 0 c 1 c 2 . . . c ′ s+1 , and do the following final substitutions:

-replace each ⊃ j ⊂ j by σ -1 j (see Figure 7a); -replace each ⊃ 1 ⊂ 2 by σ -1 1 σ -1 2 σ 1 (see Figure 7b); -replace each ⊃ 2 ⊂ 1 by σ -1 2 σ -1 1 σ 2 (see Figure 7c). Then we obtain a braid b R . We define the braid associated to the L-scheme L C , denoted b C , as the braid b R (σ 1 σ 2 σ 1 ) k .

Example 2.9. After the two replacements described above, we obtain in the case of Example 2.5

a) ⊃ j ⊂ j → σ -1 j b) ⊃ 1 ⊂ 2 → σ -1 1 σ -1 2 σ 1 c) ⊃ 2 ⊂ 1 → σ -1 2 σ -1 1 σ 2 Figure 7. • 1 ⊂ 1 × 2 × 1 ⊃ 1 ∨ ⊃ 2 ⊂ 1 ⊃ 1 ⊂ 1 ⊃ 2 ⊂ 2 ⊃ 1 ⊂ 1 ⊃ 1 ⊂ 1 ⊃ 1 ⊂ 1 σ -1 2 σ -1 1 σ 2 σ -1 1 σ -1 2 σ -1 1 σ -2 1 (σ 1 σ 2 σ 1 ) 2
which finally gives the braid Proof. The only part which is not already contained in [Ore99, Section 3] is the determination of the braid C ∩ π -1 (γ) where γ is the arc in C parametrized by u ∈ [0; π] → ε + R 1 exp(2iπu) (recall that ε and R 1 have been introduced at the end of Section 2.1). But this braid is dictated by the monomials of an equation of C in C 2 which are dominating at infinity. Up to a real multiplicative constant, these monomials are precisely

b C = σ -1 2 σ -1 1 σ 2 σ -1 1 σ -1 2 σ -3 1 (σ 1 σ 2 σ 1 )
-y 3 -λx 3k-1 if c s+1 =↓, -y 3 + λx 3k-1 if c s+1 =↑, -y 3 -λx 3k-2 if c s+1 = ∨, -y 3 + λx 3k-2 if c s+1 = ∧,
where λ is some positive real number. Now the result follows from straightforward local computations as in [Ore99, Section 3].

Proof of Theorem 3.9

Here we apply the method described in the previous section to the study of the lexicographic degree of two-bridge knots. Given a long knot diagram D in R 2 , we denote by D its projection to R 2 (i.e. we forget about the sign of the crossings).

3.1. The case of alternating diagrams. We first consider the special case of alternating diagrams, from which we will deduce the general case in Section 3.2. Proposition 3.1. Let D be the alternating trigonal diagram C(m) with m odd, or C(m, n) with mn even and positive. If γ : R → R 2 is a polynomial map of bidegree

(3, b) such that γ(R) is L-isotopic to D, then b ≥ 3N -1 2
, where N is the crossing number of the knot.

Proof. Up to a change of coordinates in C 2 , we may suppose that b = 3k -1 or b = 3k -2. By genericity argument, we may also suppose that C = γ(C) is a nodal curve in C 2 . Finally by symmetry we may further assume that m is even when m + n is odd.

In the case of C(m), the L-scheme of C contains the patterns ⊂ 2 (× 1 ) m ⊃ 2 . In the case of C(m, n), the L-scheme of C contains the patterns ⊂ 2 (× 1 ) m (× 2 ) n ⊃ 1 (see Figure 9). By the Riemann-Hurwitz formula the map π • γ has exactly two In particular, these two ramification points are real. Hence, still by the Riemann-Hurwitz formula, the surface U C is made of three embedded disks U 1 , U 2 , and U 3 . Each disk U i bounds the subknot L i of the link L C . The positivity of self-intersections of a complex algebraic curve and Proposition 2.2 implies that lk (L i , L j ) = U i • U j ≥ 0. On the other hand U i and U j intersect transversally at complex conjugated nodes, thus we have

1 1 2 2 3 3 m 1 1 1 2 2 2 3 3 3 m n 1 1 1 2 2 2 3 3 3 m n C(m) C(m, n) with n even C(m, n) with n odd
1≤i<j≤3 U i • U j = β,
and therefore

(1) lk (L i , L j ) ≤ β, 1 ≤ i < j ≤ 3. Moreover Lemma 2.4 states that (2) N + α + 2β = b -1.
Let us label the components L 1 , L 2 , and L 3 as depicted in Figure 9, and let us evaluate the quantity 2lk (L 1 , L 3 ) from the algorithm described in Section 2.2. Clearly, no crossing point of RC contributes to 2lk (L 1 , L 3 ), and the factor (σ 1 σ 2 σ 1 ) k contributes k to 2lk (L 1 , L 3 ). As in Section 2.2, we denote by c 1 . . . c s+1 the L-scheme realized by C, and by c ′ 0 c 1 . . . c s c ′ s+1 the result of replacing c s+1 by c ′ 0 and c ′ s+1 . We have N = n + m and s = N + α + 2. Let p ≥ 1 such that c p =⊂ 2 . Then we have c p+N +1 =⊃ 2 and c q = • j for 1 ≤ q ≤ p -1 and N + p + 2 ≤ q ≤ s. We can estimate the contribution of b R to 2lk (L 1 , L 3 ) as follows:

-in the case of C(m) or C(m, n) with N odd: each pattern c q with p + N + 1 ≤ q ≤ s contributes -1; each pattern c q c q+1 with 1 ≤ q ≤ p -1 contributes at least -1; the pattern c ′ 0 c 1 contributes at least 0; the pattern c ′ s+1 contributes 0 if b = 3k -1, and -1 if b = 3k -2. -in the case of C(m, n) with N even: each pattern c q c q+1 with 1 ≤ q ≤ p -1 or p + N + 1 ≤ q ≤ s -1 contributes at least -1, as well as the pattern c ′ 0 c 1 ; the pattern c s c ′ s+1 contributes at least -1 if b = 3k -1, and at least 0 if b = 3k -2.

Altogether, writing d = 3k -1 -ε, we obtain 2lk (L 1 , L 3 ) ≥ k -α -1 -ε if N is odd, and 2lk (L 1 , L 3 ) ≥ k -α -2 + ε
if N is even. These last inequalities together with identities (1) and ( 2 2 -2 depending on the parity of N . Moreover the mutual position of the solitary nodes of C is imposed: the L-scheme realized by C does not contain the pattern (• j ) 2 (i.e. the pattern corresponding to two successive solitary nodes must be • j • j±1 ).

) give b -k ≥ N -ε if N is odd, and b -k ≥ N -1 + ε if N is even.
Remark 3.3. Let us consider the harmonic knot H(3, 7, 11). It is proved in [START_REF] Koseleff | On polynomial Torus Knots[END_REF] that its crossing number is 6. Then its lexicographic degree is (3, 7, c), which is smaller than the upper bound given in Proposition 3.1. This is the knot 6 3 which is neither a torus knot nor a generalized twist knot ( [START_REF] Koseleff | Chebyshev diagrams for two-bridge knots[END_REF]). In Section 4 we shall see that the lexicographic degree of 6 3 is (3, 7, 11).

Figure 10. The harmonic knot H(3, 7, 11) = 6 3 3.2. Reduction to the case of alternating diagrams: real pseudoholomorphic curves. As explained in the introduction it might not be true that the lexicographic degree of a trigonal long knot diagram does not increases along an isotopy through trigonal diagrams which never increases the number of crossings. For this to be true we have to consider real pseudoholomorphic curves (see Corollary 3.7).

We consider C 2 equipped with the standard Fubini-Study symplectic form

ω(u + iv, u ′ + iv ′ ) = u ∧ v + u ′ ∧ v ′ .
Recall that an almost complex structure J on C 2 is a smooth section J : C 2 → End R (T C 2 ) such that J 2 p = -Id TpC 2 for any p ∈ C 2 , and that J is said to be tamed by ω if ω(v, Jv) > 0 for any non-null vector v ∈ T C 2 . Such an almost complex structure is called real if the standard complex conjugation conj on C 2 is J-antiholomorphic (i.e. conj • J = J -1 • conj). For example, the standard complex structure J 0 on C 2 is real and tamed by ω. An almost complex structure is called admissible if it is real, tamed by ω, and coincide with J 0 outside a compact set in C 2 .

The next definition follows the lines of [OS02, Section 1] and [MS04, Chapter 2]. We also denote by J 0 (resp. conj) the standard complex structure (resp. complex conjugation) on C. Definition 3.4. Let J be an admissible almost complex structure on C 2 . A real (rational) J-holomorphic curve is a map γ : C → C 2 which is polynomial outside a compact set of C, and such that

dγ ′ • J 0 = J • dγ ′ and γ • conj = conj • γ.
A real pseudoholomorphic curve γ : C → C 2 is a map which is J-holomorphic for some admissible almost complex structure J on C 2 . Example 3.5. Every polynomial real map γ : R → R 2 is a real J 0 -holomorphic curve. However not every real pseudoholomorphic curve is J 0 -holomorphic.

By definition, the image C = γ(C) of any real pseudoholomorphic curve γ coincide with a real algebraic curve C 0 outside a compact set of C 2 . We say that γ is of bidegree (3, b) if the curve C 0 has for Newton polygon the triangle with vertices (0, 0), (0, 3), and (0, b). As in the algebraic case, we may assume for our purposes that if a real pseudoholomorphic curve is of bidegree (3, b), then b = 3k -1 or b = 3k -2. Note that nodal pseudoholomorphic curves satisfy the adjunction formula (see [MS04, Chapter 2]), in particular Lemma 2.4 still holds for pseudoholomorphic curves.

The braid theoretical approach described in Section 3 extends word by word to the case of nodal real pseudoholomorphic curves of bidegree (3, b) (see for example [START_REF] Yu | Link theory and oval arrangements of real algebraic curves[END_REF][START_REF] Yu | Flexible, algebraically unrealizable curves: rehabilitation of Hilbert-Rohn-Gudkov approach[END_REF]). Indeed, in these latter two sections we only use the behavior at infinity of real algebraic curves and the three following facts:

(1) any intersection of two complex algebraic curves is positive;

(2) there exists a unique vertical line passing through a given point p of C 2 , which is real if p is real; (3) the map π is a real holomorphic map. Let us fix an admissible almost complex structure J on C 2 . The word by word extension of Sections 2.1 and 2.2 to J-holomorphic curves follows from the three following facts:

(1') any intersection of two J-holomorphic curves is positive (see [MS04, Appendix E]); (2') there is an analogue of the pencil of vertical lines in C 2 : consider the standard embedding

C 2 -→ CP 2 (x, y) -→ [x : y : 1] ;
then given a point p ∈ C 2 there exists a unique J-holomorphic line in CP 2 passing through p and [0 : 1 : 0] (see [START_REF] Gromov | Pseudoholomorphic curves in symplectic manifolds[END_REF]); by uniqueness, this line is real if p is real; this produces a real pencil of "vertical" J-holomorphic lines on C 2 ; (3') since J is standard outside a compact set of C 2 , the line {y = b} is Jholomorphic for |b| large enough; replace the map π by the map π b : C 2 → {y = b} which associates to each point p of C 2 the (unique) intersection point of {y = b} with the J-holomorphic vertical line passing through p; the map π b is clearly a real J-holomorphic map. The main advantage in dealing with real pseudoholomorphic curves rather than real algebraic curves is that we have the following proposition.

Proposition 3.6 (Orevkov, [START_REF] Yu | Link theory and oval arrangements of real algebraic curves[END_REF]). Let γ : C → C 2 be a real nodal pseudoholomorphic curve of bidegree (3, b) realizing an L-scheme L γ , and let L ′ γ be the L-scheme obtained from L γ by one of the following elementary operations :

× j ⊃ j±1 ↔ × j±1 ⊃ j ⊂ j±1 × j ↔ ⊂ j × j±1 × j × j → ∅ × j ⊃ j ↔ ⊃ j • j ⊂ j × j ↔ • j ⊂ j × j+1 × j × j+1 ↔ × j × j+1 × j
Then there exists a real nodal pseudoholomorphic curve of bidegree (3, b) realizing L ′ γ . Corollary 3.7. Let D 1 and D 2 be two trigonal long knot diagrams such that D 2 is obtained from D 1 by an isotopy of trigonal diagrams which never increase the number of crossings. If there exists a real nodal pseudoholomorphic curve γ 1 : C → C 2 of bidegree (3, b) such that γ 1 (R) is L-isotopic to D 1 , then there also exists a real nodal pseudoholomorphic curve γ

2 : C → C 2 of bidegree (3, b) such that γ 2 (R) is L-isotopic to D 2 .
Proposition 3.8. Let K be the two-bridge knot C(m) with m odd, or C(m, n) with mn positive and even, and let N be its crossing number. Let D be any trigonal diagram of K. If there exists a real nodal pseudoholomorphic curve γ :

C → C 2 of bidegree (3, b) such that γ(R) is L-isotopic to D, then b ≥ 3N -1 2 .
Proof. According to Corollary 3.7 and Theorem A, it is enough to prove the proposition when D is alternating, which has been done in Proposition 3.1 (recall that real pseudoholomorphic curves satisfy Lemma 2.4, so the proof of Proposition 3.1 extends word by word to this case). 2

Theorem 3.9. Let K be the two-bridge knot C(m) with m odd, or C(m, n) with mn positive and even, and let N be its crossing number. Then the lexicographic degree of . This implies that c ≤ 3N 2 + 1, and the theorem is proved. 2

K is 3, 3N -1 2 , 3N 2 + 1 .
Remark 3.10. It is shown in [START_REF] Koseleff | Chebyshev knots[END_REF] that the harmonic knot H(3, 3n + 2, 3n + 1) is the torus knot T(2, 2n + 1) = C(2n + 1). By Theorem 3.9, this is an explicit polynomial parametrization of minimal lexicographic degree (3, 3n + 1, 3n + 2). In this example, the number of crossings of the diagram is greater than the crossing number of the knot. In [START_REF] Koseleff | A polynomial parametrization of torus knots[END_REF] it is proved that there exists a polynomial representation of T(2, 2n + 1) which is of minimal degree, and such that the number of crossings is minimal.

A lower bound

Theorem 4.3 provides a general lower bound for the lexicographic degree of every non-trivial knot, furthermore this lower bound is sharp.

= {(α, β) ∈ Z 2 ≥0 , αa + βb ≤ 2N -2} and Q = {(α, β) ∈ Z 2 ≥0 , α ≤ b -2, β ≤ a -2}. The set Q has 2N elements, and contains E. Denoting s(α, β) = αa + βb, α ′ = b -2 -α, and β ′ = a -2 -β, we have s(α, β) + s(α ′ , β ′ ) = 2(2N -1), and then (α ′ , β ′ ) ∈ Q -E if and only if (α, β) ∈ E.
Consequently, half the elements of Q are in E, and then E has N elements. Since a and b are coprime, the mapping s is an injection from E to Z ≥0 , which concludes the proof.

Proof of Proposition 4.1. The N = (a -1)(b -1)/2 crossing points of the xyprojection of γ(t) = (x(t), y(t), z(t)) correspond to parameter pairs (s i , t i ) such that x(t i ) = x(s i ), y(t i ) = y(s i ), z(t i ) > z(s i ).

Consider V the vector subspace of R[t] generated by the polynomials x(t) α y(t) β , αa + βb ≤ 2N -2. By Lemma 4.2, the dimension of V is N . Let us define the linear mapping ϕ : V → R N by ϕ(h) = h(t 1 ), . . . , h(t N ) . If a polynomial h is in the kernel of ϕ, then h(t 1 ) = h(s 1 ) = • • • = h(t N ) = h(s N ) = 0, and the polynomial h has 2N distinct roots. Since deg(h) ≤ 2N -2, we deduce that h = 0.

Consequently the mapping ϕ is an isomorphism and there exists h ∈ V such that h

(t i ) = h(s i ) = (z(t i ) + z(s i ))/2.
Let us define z(t) = z(t)h(t). The images of γ and γ(t) = x(t), y(t), z(t) are isotopic and realize the same diagram. By construction, at each crossing we have z(t i ) > 0 > z(s i ).

Let us write {t 1 , . . . , t N , s 1 , . . . , s N } = {τ 1 , . . . , τ 2N } where τ j < τ j+1 . Since the diagram realized by γ(t) is alternating, we may assume that (-1) i z(τ i ) > 0. Consequently the polynomial z(t) has at least one root in the interval (τ j , τ j+1 ), and deg(z) ≥ 2N -1. Since deg(h) ≤ 2N -2, we conclude that deg(z) ≥ 2N -1.

As a consequence we deduce: Theorem 4.3. Let K be a knot of crossing number N = 0. Then the lexicographic degree of K is at least (3, N + 1, 2N -1). For every integer N ≡ 2 (mod 3), N ≥ 3, there exists a knot of crossing number N and lexicographic degree (3, N + 1, 2N -1)

Proof. Let (a, b, c) be the lexicographic degree of K. Since K is nontrivial, we have a ≥ 3. Suppose that a = 3. Then K is a two-bridge knot, and b is not divisible by 3. Moreover by Bézout's theorem we have N ≤ (a -1)(b -1)/2 = b -1, that is b ≥ N + 1.

Let γ(t) : R → R 3 be a polynomial parametrization of K of degree (3, b, c). If b = N + 1, then the xy-diagram of γ(t) has the minimal number of crossings. Since K is a two-bridge knot, it is an alternating knot, and the xy-diagram of γ(t) is alternating. By Proposition 4.1, we conclude that c ≥ 2N -1.

On the other hand, when N ≡ 2 (mod 3), the harmonic knot H(3, N +1, 2N -1) has crossing number N (see [START_REF] Koseleff | On polynomial Torus Knots[END_REF]), hence its lexicographic degree is (3, N + 1, 2N -1).

We also obtain the lexicographic degree of an infinite family of three-bridge knots.

Corollary 4.4. Let H be the harmonic knot H = H(5, b, 4b-5), with b ≡ 0 (mod 5). The knot H is a three-bridge knot of lexicographic degree (5, b, 4b -5).

Proof. The xy-projection of the knot H has N = 2(b-1) crossings and is alternating (see [START_REF] Koseleff | Chebyshev knots[END_REF]). If H was two-bridged, then it would have a minimal diagram which would be alternating and two-bridged. By Tait's flyping conjecture, this is not the case since the xy-projection of H is alternating and three-bridged.

Let x(t), y(t), z(t) be a polynomial knot isotopic to H. Since H is not two-bridged, we have deg( Remark 4.5. The lexicographic degree of the harmonic knot H(a, b, abab) is not always (a, b, abab). For example, if a = 4 this knot is two-bridged and has a polynomial parametrization of degree (3, b ′ , c ′ ), which is lexicographically smaller than (4, b, 3b -4). Proposition 4.1 can also be used to study the maximal degree of a polynomial knot, that is the maximum degree of its components.

Figure 1 .

 1 Figure 1. Two harmonic knots H(3, 4, 5) and H(3, 5, 7), corresponding to the projection (x, y, z) → (x, y).

Figure 2 .Figure 3 .

 23 Figure 2. Two-bridge torus knots and generalized twist knots

  Theorem A. ([START_REF] Brugallé | Untangling trigonal diagrams[END_REF]) Let K be the two-bridge knot C(m), or C(m, n) with mn > 0, and let D be a trigonal diagram of K. Then it is possible to transform D into an alternating trigonal diagram, so that all intermediate diagrams remain trigonal, and the number of crossings never increases.

  Figure 4.

  Figure 5.

Figure 8 .

 8 Figure 8.

Figure 9 .

 9 Figure 9. Diagrams for C(m) or C(m, n) knots

  Hence we obtain b ≥ 3N -1 2 which proves the proposition. Remark 3.2. The proof of Proposition 3.1 shows that if b = 3N -1 2 then β = 0 and α = N -3 2 or α = N

Proof.

  Let K be any two-bridge knot. It is proved in [KP10] that there exists a polynomial curve γ : R → R 3 of degree (3, b, c) such that N < b < c, b + c = 3N , and γ(R) is the knot K. In particular we have b ≤ 3N -1 2 and c ≥ 3N 2 + 1. If K is C(m) or C(m, n), then by Proposition 3.8 we have b ≥ 3N -1 2

Proposition 4. 1 .

 1 Let γ : R → R 3 be a polynomial map of degree (a, b, c) whose image is a smooth knot. Suppose that a and b are coprime, and that the xy-diagram of γ(t) is alternating with (a -1)(b -1)/2 crossings. Then c ≥ abab. The proof of Proposition 4.1 uses the following lemma of Frobenius type. Lemma 4.2. Let a and b be coprime positive integers. The number of integers of the form n = αa + βb, n ≤ abab -1, (α, β) ∈ Z 2 ≥0 , is equal to (a -1)(b -1)/2. Proof. Let N = (a-1)(b-1)/2. First, let us show that the integer 2N -1 = ab-a-b is not of the form αa + βb, with (α, β) ∈ Z 2 ≥0 . If we had abab = αa + βb, then α ≡ -1 (mod b), and α ≥ b -1. Hence we deduce that αa + βb ≥ aba + βb > 2N -1, contrary to our hypothesis Now consider the sets E

  x) ≥ 5. If deg(x) = 5, then by Bézout's theorem we have N ≤ 2 deg(y) -1 , that is deg(y) ≥ b. If deg(y) = b, then by Proposition 4.1 we obtain deg(z) ≥ 5b -5b = 4b -5.

Corollary 4.6. Let K be a polynomial knot of degree d and crossing number N. We have

Moreover, if d > 5 and if K is alternating, then we have:

Proof. Using an affine transformation, we can suppose that the lexicographic degree of

. By Bézout's theorem we see that the number of crossings of the xy-projection is at most (d-2)(d-3)/2, which proves the first assertion. If we had N = (d-2)(d-3)/2, then the lexicographic degree of K would be (d-2, d-1, d).

By Proposition 4.1, we have d

Remark 4.7. Since knots of crossing number smaller than 8 are alternating, we deduce that the only knot of degree 4 is the trivial knot, the only nontrivial knot of degree 5 is trefoil, and the crossing number of a knot of degree 6 is at most 5.


Argelaguet Ferran

Takuya Sanz
email: takuyas6@riec.tohoku.ac.jp

Thierry Sato

Yoshifumi Duval

Anatole Kitamura
email: kitamura@riec.tohoku.ac.jp

Lécuyer

Ferran Argelaguet

Takuya Sato

Thierry Duval
email: thierry.duval@irisa.fr

Yoshifumi Kitamura

Anatole Lécuyer
email: anatole.lecuyer@inria.fr

Collaborative Pseudo-Haptics: Two-User Stiffness Discrimination Based on Visual Feedback

Keywords: Pseudo-haptics, User Interfaces, Multi-user Interaction

come   L'archive ouverte pluridisciplinaire

Introduction

Collaborative interaction has a wide range of applications such as virtual prototyping, training environments, project reviews and video games. In such applications, it is critical to ensure the communication between users (user awareness). All users must have knowledge about the state of the system and the actions performed by other users. In this work we explore how the concept of pseudohaptic feedback can be introduced in such multi-user scenarios. Specifically, how the perception of physical properties of objects can be enhanced during of coexploration and co-manipulation.

Pseudo-haptic research has been conducted in order to explore how physical properties of virtual objects (e.g. stiffness, friction, mass) can be simulated without the need of dedicated haptic devices [START_REF] Lecuyer | Pseudo-haptic feedback: can isometric input devices simulate force feedback?[END_REF]. By delivering appropriate visual feedback accounting for users' actions and the simulated physical properties, some kind of "haptic illusions" can be induced [START_REF] Pusch | Pseudo-haptics : From the Theoretical Foundationsto Practical System Design Guidelines[END_REF]. Among them, the first pseudohaptic paper focused on stiffness perception [START_REF] Lecuyer | Pseudo-haptic feedback: can isometric input devices simulate force feedback?[END_REF]. Users, by interacting with an isometric input device manipulated a virtual piston displayed on a computer string. The user could displace the virtual piston according to simulated stiffness. Varying the degrees of visual compression of the virtual piston leaded to different levels of perceived stiffness. However, pseudo-haptic studies have not only considered the simulation of physical parameter (e.g. stiffness, torque, friction). For example, Lécuyer et al. [START_REF] Lécuyer | Feeling bumps and holes without a haptic interface[END_REF] explored how the relief of textures could be simulated by adjusting the Control/Display (CD) ratio of the mouse cursor based on the underlying texture information. Other studies have focused on the perception of the shape of 3D objects [START_REF] Ban | Modifying an identified curved surface shape using pseudo-haptic effect[END_REF] or on graphical user interfaces [START_REF] Rodgers | Smart sticky widgets: Pseudo-haptic enhancements for multi-monitor displays[END_REF].

In this research, in contrast to existing pseudo-haptic research on stiffness perception [START_REF] Lecuyer | Pseudo-haptic feedback: can isometric input devices simulate force feedback?[END_REF], we investigate the stiffness perception when two users interact in a non-colocated setup with deformable objects. The proposed setup enables two users to interact through a tactile interface with a deformable object. The feedback provided to the user is only visual, which is expected to enable stiffness discrimination [START_REF] Drewing | Haptic, visual and visuo-haptic softness judgments for objects with deformable surfaces[END_REF]. The interaction with the deformable object is dependent on the users' actions and its physical properties. The results showed that participants were able to perceive the stiffness of virtual objects during co-manipulation through pseudo-haptic feedback. From this, we conclude that pseudo-haptic feedback can be introduced in collaborative environments. The remaining of the paper details the interaction model and its evaluation.

Concept of Pseudo-Haptic Stiffness Simulation in a Two-User Collaborative Scenario

The virtual environment considered is composed by a deformable object (cube), and two actuators at each side (see Figure 1 left). In our two-user scheme, each user is able to manipulate one actuator in order to interact with the deformable object. For simplicity, the actuators only have one degree of freedom (horizontal axis). The system is designed in a way that users, in order to deform the object, have to work in a coordinate way. For example, if only one user is pushing, it results only in the translation of the cube without any deformation. In such a system, we have to determine (1) how the user input determines the force exerted by the actuator, and (2) how the forces applied by both actuators modify the state of the deformable object.

Regarding the user input, in our prototype, each user interacts with one of the actuators by moving his finger along a touch surface (see Figure 1 right). The force (F ) delivered by the actuator is linked with the amount of displacement accumulated is F = ∆x f /a. Where ∆x f is the displacement of the user's finger in the touch surface and a is a scaling factor. Each actuator is manipulated independently. When the user removes the finger from the tactile surface the actuator will no longer exert any force (F = 0).

Considering the environment and the user interaction, the system presents five different cases. They are characterized by the force delivered by each actuator (left F l and right F r ) and whether the actuators are in contact with the deformable object or not:

1. The actuator is not in contact with the interactive object. The movement of the actuator is mapped directly with the user's input. 2. Only one actuator is pushing the interactive object. The actuator displaces the object along the horizontal axis with a 1:1 CD ratio. 3. Both actuators are in contact with the interactive object but one of them does not deliver any force. The behavior is the same as case 2 but the actuator with F = 0 is also displaced. 4. Both actuators are in contact with the interactive object, and F l > 0 and F r > 0. In this case, the force is transmitted to the deformable object which is deformed based on Hooke's law x d = F/k. k determines the stiffness of the virtual cube and x d is the compression of the cube in the x-axis. The force applied is F = min(F l , F r ). The exceeding force will displace the object and the actuator delivering less force. 5. The virtual object is compressed and F = 0. The virtual object will recover its original size (elastic deformation). If an actuator is in contact with the virtual object and their force is equal to zero, it will be displaced. The recovery time was not dependent on the cube's stiffness.

The simulation requires participants to interact synchronously when interacting with the virtual object. If both users do not deliver a similar force it will result in the displacement of the virtual object without any deformation. The pseudo-haptic feedback is linked with the stiffness of the deformable object which modifies the force required to deform it. The higher the value of k is, the higher is the force required to deform the object and vice-versa. Additionally, to increase the visual feedback provided, we preserved the volume of the object while it is being deformed (see Figure 1 left).

Implementation details. Rendering and simulation were handled by a Unity 3D application while the communication between the touch devices (iPads) and the main application was achieved using websockets. The system architecture is displayed in Figure 1.

User Evaluation

A user evaluation of the system was conducted in order to explore its usability and explore the effects of the user collaboration on the perception of the pseudohaptic feedback. The questions posed in the evaluation were the computation of the Just Noticeable Differences (JND) of the virtual stiffness and whether the fact that both users had to interact synchronously influenced their perception or not. These results are needed both to validate our approach and to provide guidelines to the integration of the proposed effect in a real application.

Design and Procedure. The evaluation followed a 2AFC (two alternative forced choice) procedure with two main conditions: single-user (S) and multi-user (M). For each trial, participants were presented with two virtual cubes (one after another) with different stiffness coefficients (k). Participants had to determine which one was the stiffest. While for the multi-user condition we used the system described in Section 2, for the single-user condition, the user interacted with two iPads at the same time with his two index fingers. For the 2AFC task, the comparisons were based on one reference value (k f = 4) and six comparison values (±30%, ±20%, ±10%). The order of the conditions (single vs multi) was balanced and the comparisons randomized. For each combination, users performed ten repetitions, resulting in a total of 2x6x10 (120) trials. Regarding the procedure, for each trial, users were presented with a discrimination task. They had five seconds to interact with each virtual cube and then, they had to answer which cube was the stiffest. Users were able to answer the question through a GUI displayed on their iPads. For each trial, we recorded the answer for the question "Which virtual cube is the stiffest?". Furthermore, we also recorded the displacement of the virtual cube and the difference between the force applied by each effector, which are measures of the users' synchronization. Our hypotheses were [H1]: Stiffness discrimination accuracy will be higher for the single user condition and [H2]: The synchronization between both effectors will be higher for the single-user condition.

Participants. 16 users aged from 21 to 31 (11 male and 5 female) took part in the experiment. All users had no known perception disorders, and used their dominant hand to perform the task.

Apparatus. The evaluation was conducted using two displays of 20" (see Figure 2 right). Users interacted with the application sitting down, at 50cm from the display. In the multi-user condition, users were not able to see neither the others user's display nor the others interface. Oral exchange was not allowed.

Results. The analysis of the results followed a classical psychophysical analysis as described in [START_REF] Gescheider | Psychophysics : Method, Theory, and Application[END_REF]. First, we consider the answers in which the reference is considered to be stiffer (see Figure 2 left). The JND threshold is computed as the difference between the reference value and the value of the psychophysical curve (f (x) = 1/(1 + e

x-α β )) at the 84% ordinate. Multi-user: ∆I M = 4 -2.93 = 1.07 and single-user: ∆I S = 4 -2.96 = 1.04. With this information, we compute the Weber fraction as k = ∆I/I where I is the value of the reference stiffness. This computation results in k M = 0.267 and k S = 0.26.

The two-way ANOVA of Condition (multi,single) and Comparison (±30%, ±20%, ±10%) versus Accuracy showed a significant difference for Comparison (F 5,75 = 26.12;p < 0.001) but no significant difference was found between conditions (F 1,75 = 0.49;p = 0.494). The fact that there are no significant differences on the user accuracy is consistent with the fact that the Weber fractions for each condition are similar. In contrast, when analyzing the data regarding the synchronization between both actuators the two-way ANOVA for the cube displacement showed a main effect for Condition (F 1,15 = 712.43;p < 0.001). Posthoc tests (Bonferroni) showed that the cube displacement was significantly lower (p < 0.05) for the singe-user condition (38% smaller). Regarding the force difference, there is also a significant effect on Condition (F 1,15 = 411.93;p < 0.001). Post-hoc (Bonferroni) tests showed that the difference was significantly higher (p < 0.05) for the multi-user condition (29% higher).

Discussion. The results show that users were able to perceive differences of stiffness with a comparable performance for single and multi-user conditions (similar Weber fractions and no significant differences in accuracy). Although we expected a reduced discrimination for the multi-user condition, this was not the case, thus we reject [H1]. Nevertheless, considering the results on cube displacement and force difference, we clearly observe differences in the degree of synchronization between conditions. Both measures are correlated, the higher is the difference between forces the more the cube is displaced. The deformation is determined by the minimum of the forces delivered by the effectors. In both cases, the values were higher for the multi-user condition, thus we accept [H2]. Hence, for the given simulation, users seem to perceive the stiffness property of the deformable object at the same level between single and multi-user conditions, although their motions are naturally less accurate during a co-manipulation.

Conclusion

In this work, we have studied the introduction of pseudo-haptic feedback in a collaborative perceptive task: two-user stiffness discrimination task based on visual feedback and tactile input. We have proposed and evaluated the interaction model. In the proposed simulation, two users could feel the stiffness of a deformable cube in a collaborative task. The evaluation conducted investigated the effects of the collaborative interaction in terms of user perception and synchronization. Although we expected a decrease in performance of stiffness discrimination for the collaborative task, the results surprisingly showed that it was not the case. The Weber fraction for single-user was 0.267 and 0.26 for the multi-user scenario. This result could be applied in various applications such as future remote co-exploration, assembly/maintenance simulations or multi-player video games.

Fig. 1 .

 1 Fig. 1. (Left) the virtual environment considered is composed by one interactive object (center object) and two actuators. The deformation of the virtual object is only triggered when both users interact synchronously. (Right) System's architecture. Each user controls one actuator by swiping his finger on a touch device.

Fig. 2 .

 2 Fig. 2. Left, psychometric curves obtained for the single-user (α = 4.113, β = 0.711) and multi-user (α = 4.098, β = 0.681) conditions. Right, experimental setup.