Etienne De Klerk
email: e.deklerk@uvt.nl

Monique Laurent
email: monique@cwi.nl

CONVERGENCE ANALYSIS OF A LASSERRE HIERARCHY OF UPPER BOUNDS FOR POLYNOMIAL MINIMIZATION ON THE SPHERE

Keywords: polynomial optimization on sphere, Lasserre hierarchy, semidefinite programming, generalized eigenvalue problem AMS subject classification 90C22, 90C26, 90C30

We study the convergence rate of a hierarchy of upper bounds for polynomial minimization problems, proposed by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864 -885], for the special case when the feasible set is the unit (hyper)sphere. The upper bound at level r ∈ N of the hierarchy is defined as the minimal expected value of the polynomial over all probability distributions on the sphere, when the probability density function is a sum-of-squares polynomial of degree at most 2r with respect to the surface measure.

We show that the exact rate of convergence is Θ(1/r 2 ), and explore the implications for the related rate of convergence for the generalized problem of moments on the sphere.

Introduction

We consider the problem of minimizing an n-variate polynomial f : R n → R over a compact set K ⊆ R n , i.e., the problem of computing the parameter:

f min,K := min x∈K f (x). (1)
In this paper we will focus on the case when K is the unit sphere: K = S n-1 = {x ∈ R n : x = 1}, in which case we will omit the subscript K and simply write f min = min x∈S n-1 f (x).

Problem [START_REF] Ahmadi | NP-hardness of deciding convexity of quartic polynomials and related problems[END_REF] is in general a computationally hard problem, already for simple sets K like the hypercube, the standard simplex, and the unit ball or sphere. For instance, the problem of finding the maximum cardinality α(G) of a stable set in a graph G = ([n], E) can be expressed as optimizing a quadratic polynomial over the standard simplex [START_REF] Motzkin | Maxima for graphs and a newproof of a theorem of Túran[END_REF], or

1 α(G) = min x∈R n x T (I + A G )x : x ≥ 0, n i=1 x i = 1 = min y∈S n-1   i =j:{i,j}∈E y 2 i y 2 j + i∈[n] y 4 i   , √ 2 3 √ 3 1 - 1 α(G) = max (y,z)∈S n+m-1 ij∈E y i y j z ij ,
where A G is the adjacency matrix of G, E is the set of non-edges of G and m = |E|. Other applications of polynomial optimization over the unit sphere include deciding whether homogeneous polynomials are positive semidefinite. Indeed, a homogeneous polynomial f is defined as positive semidefinite precisely if

f min = min x∈S n-1 f (x) ≥ 0,
and positive definite if the inequality is strict; see e.g. [START_REF] Reznick | Some concrete aspects of Hilbert's 17th Problem[END_REF]. As special case, one may decide if a symmetric matrix A = (a ij ) ∈ R n×n is copositive, by deciding if the associated form f (x) = i,j∈[n] a ij x 2 i x 2 j is positive semidefinite; see, e.g. [START_REF] Parrilo | Structured Semidefinite Programs and Semi-algebraic Geometry Methods in Robustness and Optimization[END_REF].

Another special case is to decide the convexity of a homogeneous polynomial f , by considering the parameter min (x,y)∈S 2n-1 y T ∇f (x)y, which is nonnegative if and only if f is convex. This decision problem is known to be NP-hard, already for degree 4 forms [START_REF] Ahmadi | NP-hardness of deciding convexity of quartic polynomials and related problems[END_REF].

As shown by Lasserre [START_REF] Lasserre | A new look at nonnegativity on closed sets and polynomial optimization[END_REF], the parameter (1) can be reformulated via the infinite dimensional program

f min,K = inf h∈Σ[x] K h(x)f (x)dµ(x) s.t. K h(x)dµ(x) = 1, (2)
where Σ[x] denotes the set of sums of squares of polynomials, and µ is a given Borel measure supported on K. Given an integer r ∈ N, by bounding the degree of the polynomial h ∈ Σ[x] by 2r, Lasserre [START_REF] Lasserre | A new look at nonnegativity on closed sets and polynomial optimization[END_REF] defined the parameter:

f (r) K := min h∈Σ[x]r K h(x)f (x)dµ(x) s.t. K h(x)dµ(x) = 1, (3)
where Σ[x] r consists of the polynomials in Σ[x] with degree at most 2r. Here we use the 'overline' symbol to indicate that the parameters provide upper bounds for f min,K , in contrast to the parameters f (r) in ( 9) below, which provide lower bounds for it.

Since sums of squares of polynomials can be formulated using semidefinite programming, the parameter (3) can be expressed via a semidefinite program. In fact, since this program has only one affine constraint, it even admits an eigenvalue reformulation [START_REF] Lasserre | A new look at nonnegativity on closed sets and polynomial optimization[END_REF], which will be mentioned in [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF] in Section 2.2 below. Of course, in order to be able to compute the parameter (3) in practice, one needs to know explicitly (or via some computational procedure) the moments of the reference measure µ on K. These moments are known for simple sets like the simplex, the box, the sphere, the ball and some simple transforms of them (they can be found, e.g., in Table 1 in [START_REF] De Klerk | A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis[END_REF]).

As a direct consequence of the formulation (2), the bounds f (r)

K converge asymptotically to the global minimum f min,K when r → ∞. How fast the bounds converge to the global minimum in terms of the degree r has been investigated in the papers [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF][START_REF] De Klerk | Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing[END_REF][START_REF] De Klerk | Worst-case examples for Lasserre's measure-based hierarchy for polynomial optimization on the hypercube[END_REF], which show, respectively, a convergence rate in O(1/ √ r) for general compact K (satisfying a minor geometric condition), a convergence rate in O(1/r) when K is a convex body, and a convergence rate in O(1/r 2 ) when K is the box [-1, 1] n . In these works the reference measure µ is the Lebesgue measure, except for the box [-1, 1] n where more general measures are considered (see Theorem 3 below for details).

In this paper we are interested in analyzing the worst-case convergence of the bounds (3) in the case of the unit sphere K = S n-1 , when selecting as reference measure the surface (Haar) measure dσ(x) on S n-1 . We let σ n-1 denote the surface measure of S n-1 , so that dσ(x)/σ n-1 is a probability measure on S n-1 , with

σ n-1 := S n-1 dσ(x) = 2π n 2 Γ n 2 . (4)
(See, e.g., [6, relation (2.2.3)].) To simplify notation we will throughout omit the subscript K = S n-1 in the parameters ( 1) and ( 3), which we simply denote as

f min = min x∈S n-1 f (x), f (r) = inf h∈Σ[x]r S n-1 h(x)f (x)dσ(x) : S n-1 h(x)dσ(x) = 1 . (5)
Example 1. Consider the minimization of the Motzkin form

f (x 1 , x 2 , x 3 ) = x 6 3 + x 4 1 x 2 2 + x 2 1 x 4 2 -3x 2 1 x 2 2 x 2 3
on S 2 . This form has 12 minimizers on the sphere, namely 1 √ 3 (±1, ±1, ±1) as well as (±1, 0, 0) and (0, ±1, 0), and one has f min = 0.

In Table 1 we give the bounds f (r) for the Motzkin form for r ≤ 9. In Figure 1 we show a contour plot of the form on the sphere (top left), as well as a contour plot of the optimal density function for r = 3 (top right), r = 6 (bottom left), and r = 9 (bottom right). In the figure, the red end of the spectrum denotes higher function values. Some local maximimizers of the Motzkin form are visible that correspond to |x 3 | = 1 (at the poles) and x 3 = 0 (on the equator).

When r = 3 and r = 6, the modes of the optimal density are at the global minimizers (±1, 0, 0) and (0, ±1, 0) (one may see the contours of two of these modes in one hemisphere). On the other hand, when r = 9, the mass of the distribution is concentrated at the 8 global minimizers 1 √ 3 (±1, ±1, ±1) (one may see 4 of these in one hemisphere), and there are no modes at the global minimizers (±1, 0, 0) and (0, ±1, 0).

It is also illustrative to do the same plots using spherical coordinates:

x 1 = sin θ sin φ x 2 = sin θ cos φ x 3 = cos θ θ ∈ [0, π] φ ∈ [0, 2π].
In Figure 2 we plot the Motzkin form in spherical coordinates (top left), as well as the optimal density function that corresponds to r = 3 (top right), r = 6 (bottom left), and r = 9 (bottom right). For example, when r = 9 one can see the 8 modes (peaks) of the density that correspond to the 8 global minimizers 1 √ 3 (±1, ±1, ±1). (Note that the peaks at φ = 0 and φ = 2π correspond to the same mode of the density, due to periodicity.) Likewise when r = 3 and r = 6 one may see 4 modes corresponding to (±1, 0, 0) and (0, ±1, 0).

The convergence rate of the bounds f (r) was investigated by Doherty and Wehner [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF], who showed

f (r) -f min = O 1 r (6)
when f is a homogeneous polynomial. As we will briefly recap in Section 2.1, their result follows in fact as a byproduct of their analysis of another Lasserre hierarchy of bounds for f min , namely the lower bounds (9) below.

Our main contribution in this paper is to show that the convergence rate of the bounds f (r) is O(1/r 2 ) for any polynomial f and, moreover, that this analysis is tight for any (nonzero) linear polynomial f . This is summarized in the following theorem. (i) For any polynomial f we have

f (r) -f min = O 1 r 2 . ( 7
)
(ii) For any (nonzero) linear polynomial f we have

f (r) -f min = Ω 1 r 2 . (8)
Let us say a few words about the proof technique. For the first part (i), our analysis relies on the following two basic steps: first, we observe that it suffices to consider the case when f is linear (which follows using Taylor's theorem), and then we show how to reduce to the case of minimizing a linear univariate polynomial over the interval [-1, 1], where we can rely on the analysis completed in [START_REF] De Klerk | Worst-case examples for Lasserre's measure-based hierarchy for polynomial optimization on the hypercube[END_REF]. For the second part (ii), by exploiting a connection recently mentioned in [START_REF] Martinez | Quadrature-based polynomial optimization[END_REF] between the bounds (3) and cubature rules, we can rely on known results for cubature rules on the unit sphere to show tightness of the bounds.

Organization of the paper. In Section 2 we recall some previously known results that are most relevant to this paper. First we give in Section 2.1 a brief recap of the approach of Doherty and Wehner [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] for analysing bounds for polynomial optimization over the unit sphere. After that, we recall our earlier results about the quality of the bounds (3) in the case of the interval K = [-1, 1]. Section 3 contains our main results about the convergence analysis of the bounds (3) for the unit sphere: after showing in Section 3.1 that the convergence rate is in O(1/r 2 ) we prove in Section 3.2 that the analysis is tight for nonzero linear polynomials. 2 Preliminaries

The approach of Doherty & Wehner for the sphere

Here we briefly sketch the approach followed by Doherty and Wehner [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] for showing the convergence rate O(1/r) mentioned above in [START_REF] Dunkl | Orthogonal Polynomials of Several Variables[END_REF]. Their approach applies to the case when f is a homogeneous polynomial, which enables using the tensor analysis framework. A first observation made in [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] is that we may restrict to the case when f has even degree, because if f is homogeneous with odd degree d then we have

max x∈S n-1 f (x) = d d/2 (d + 1) (d+1)/2 max (x,xn+1)∈S n x n+1 f (x).
So we now assume that f is homogeneous with even degree d = 2a.

The approach in [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] in fact also permits to analyze the following hierarchy of lower bounds on f min :

f (r) := sup λ∈R λ s.t. f (x) -λ ∈ Σ[x] r + (1 -x 2 )R[x], (9)
which are the usual sums-of-squares bounds for polynomial optimization (as introduced in [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF][START_REF] Parrilo | Semidefinite programming relaxations for semialgebraic problems[END_REF]). Here and throughout, x denotes the Euclidean norm for real vectors. One can verify that (9) can be reformulated as

f (r) = sup λ∈R λ s.t. (f (x) -λ x 2a ) x 2r-2a ∈ Σ[x] r + (1 -x 2 )R[x] = sup λ∈R λ s.t. f (x) x 2r-2a -λ x 2r ∈ Σ[x] (10)
(see [START_REF] De Klerk | On the equivalence of algebraic approaches to the miniization of forms on the simplex[END_REF]). For any integer r ∈ N we have

f (r) ≤ f min ≤ f (r) .
The following error estimate is shown on the range f

(r) -f (r) in [4].
Theorem 2. [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] Assume n ≥ 3 and f is a homogeneous polynomial of degree 2a. There exists a constant C n,a (depending only on n and a) such that, for any integer ≥ a(2a 2 + n -2) -n/2, we have

f (r) -f (r) ≤ C n,a r (f max -f min ),
where f max is the maximum value of f taken over S n-1 .

The starting point in the approach in [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] is reformulating the problem in terms of tensors. For this we need the following notion of 'maximally symmetric matrix'. Given a real symmetric matrix M = (M i,j ) indexed by sequences i ∈ [n] a , M is called maximally symmetric if it is invariant under action of the permutation group Sym(2a) after viewing M as a 2a-tensor acting on R n . This notion is the analogue of the 'moment matrix' property, when expressed in the tensor setting. To see this, for a sequence i = (i 1 , . . . , i a ) ∈ [n] a , define α(i) = (α 1 , . . . , α n ) ∈ N n by letting α denote the number of occurrences of within the multi-set {i 1 , . . . , i a } for each ∈ [n], so that a = |α| = n i=1 α i . Then, the matrix M is maximally symmetric if and only if each entry M i,j depends only on the n-tuple α(i) + α(j). Following [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] we let MSym((R n ) ⊗a ) denote the set of maximally symmetric matrices acting on (R n ) ⊗a . It is not difficult to see that any degree 2a homogeneous polynomial f can be represented in a unique way as

f (x) = (x ⊗a ) T Z f x ⊗a ,
where the matrix Z f is maximally symmetric.

Given an integer r ≥ a, define the polynomial f r (x) = f (x) x 2r-2a , thus homogeneous with degree 2r. The parameter [START_REF] De Klerk | A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis[END_REF] can now be reformulated as

f (r) = sup{ Z fr , M : M ∈ MSym((R n ) ⊗r ), M 0, Tr(M ) = 1}. (11)
The approach in [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] can be sketched as follows. Let M be an optimal solution to the program [START_REF] De Klerk | On the equivalence of algebraic approaches to the miniization of forms on the simplex[END_REF] (which exists since the feasible region is a compact set). Then the polynomial Q M (x) := (x ⊗r ) T M x ⊗r is a sum of squares since M 0.

After scaling, we obtain the polynomial

h(x) = Q M (x)/ S n-1 Q M (x)dσ(x) ∈ Σ[x] r ,
which defines a probability density function on S n-1 , i.e., S n-1 h(x)dσ(x) = 1. In this way h provides a feasible solution for the program defining the upper bound f (r) . This thus implies the chain of inequalities

Z fr , M = f (r) ≤ f min ≤ f (r) ≤ S n-1 f (x)h(x)dσ(x).
The main contribution in [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] is their analysis for bounding the range between the two extreme values in the above chain and showing Theorem 2, which is done by using, in particular, Fourier analysis on the unit sphere.

Using different techniques we will show below a rate of convergence in O(1/r 2 ) for the upper bounds f (r) , thus stronger than the rate O(1/r) in Theorem 2 above and applying to any polynomial (not necessarily homogeneous). On the other hand, while the constant involved in Theorem 2 depends only on the degree of f and the dimension n, the constant in our result depends also on other characteristics of f (its first and second order derivatives). A key ingredient in our analysis will be to reduce to the univariate case, namely to the optimization of a linear polynomial over the interval [-1, 1]. Thus we next recall the relevant known results that we will need in our treatment.

Convergence analysis for the interval [-1, 1]

We start with recalling the following eigenvalue reformulation for the bound (3), which holds for general K compact and plays a key role in the analysis for the case K = [-1, 1]. For this consider the following inner product

(f, g) → K f (x)g(x)dµ(x)
on the space of polynomials on K and let {b α (x) : α ∈ N n } denote a basis of this polynomial space that is orthonormal with respect to the above inner product; that is, K b α (x)b β (x)dµ(x) = δ α,β . Then the bound (2) can be equivalently rewritten as

f (r) = λ min (A f ), where A f = K f (x)b α (x)b β (x)dµ(x) α,β∈N n |α|,|β|≤r (12)
(see [START_REF] Lasserre | A new look at nonnegativity on closed sets and polynomial optimization[END_REF][START_REF] De Klerk | Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing[END_REF]). Using this reformulation we could show in [START_REF] De Klerk | Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing[END_REF] that the bounds The key fact is that, in the case of the univariate polynomial f (x) = x, the matrix A f in ( 12) has a tri-diagonal shape, which follows from the 3-term recurrence relationship satisfied by the orthogonal polynomials. In fact, A f coincides with the so-called Jacobi matrix of the orthogonal polynomials in the theory of orthogonal polynomials and its eigenvalues are given by the roots of the degree r + 1 orthogonal polynomial (see, e.g. [START_REF] Dunkl | Orthogonal Polynomials of Several Variables[END_REF]Chapter 1]). This fact is key to the following result. Theorem 3. (with degree r + 1). In particular, f

(r) = -cos π 2r+2 when a = b = -1/2. For any a, b > -1 we have f (r) -f min = f (r) + 1 = Θ 1 r 2 .
3 Convergence analysis for the unit sphere

In this section we analyze the quality of the bounds f (r) when minimizing a polynomial f over the unit sphere S n-1 .

In Section 3.1 we show that the range f (r) -f min is in O(1/r 2 ) and in Section 3.2 we show that the analysis is tight for linear polynomials.

The bound O(1/r 2 )

We first deal with the n-variate linear (coordinate) polynomial f (x) = x 1 and after that we will indicate how the general case can be reduced to this special case. The key idea is to get back to the analysis in Section 2.2, for the interval [-1, 1] with an appropriate weight function. We begin with introducing some notation we need.

To simplify notation we set d = n -1 (which also matches the notation customary in the theory of orthogonal polynomials where d usually is the number of variables). We let

B d = {x ∈ R d : x ≤ 1} denote the unit ball in R d , where x 2 = d i=1 x 2 i for x ∈ R d . Given a scalar λ > -1/2, define the d-variate weight function w d,λ (x) = (1 -x 2 ) λ-1/2 (13)
(well-defined when x < 1) and set

C d,λ := B d w d,λ (x 1 , . . . , x d )dx 1 • • • dx d = π d/2 Γ λ + 1 2 Γ λ + d+1 2 (14) so that C -1 d,λ w d,λ (x 1 , . . . , x d )dx 1 • • • dx d is
{(x2,...,x d ):x 2 2 +...+x 2 d ≤1-x 2 1 } w d,λ (x 1 , . . . , x d )dx 2 • • • dx d = C d-1,λ (1 -x 2 1 ) λ+ d-2 2 ,
which is thus equal to C d-1,λ w 1,λ+(d-1)/2 (x 1 ).

Proof. Change variables and set

u j = x j / 1 -x 2 1 for 2 ≤ j ≤ d. Then we have w d,λ (x) = (1 -x 2 1 -x 2 2 + . . . - x 2 d ) λ-1 2 = (1 -x 2 1 ) λ-1 2 (1 -u 2 2 -. . . -u 2 d ) λ-1 2 and dx 2 • • • dx d = (1 -x 2 1 ) d-1 2 du 2 • • • du d .
Putting things together and using relation [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF] we obtain the desired result.

We also need the following lemma, which relates integration over the unit sphere S d ⊆ R d+1 and integration over the unit ball B d ⊆ R d and can be found, e.g., in [6, Lemma 3.8.1] and [2, Lemma 11.7.1]. Lemma 2. Let g be a (d + 1)-variate integrable function defined on S d and d ≥ 1. Then we have:

S d g(x)dσ(x) = B d g(x, 1 -x 2 ) + g(x, -1 -x 2 ) dx 1 • • • dx d 1 -x 2 .
By combining these two lemmas we obtain the following result. Lemma 3. Let g(x 1 ) be a univariate polynomial and d ≥ 1. Then we have:

σ -1 d S d g(x 1 )dσ(x 1 , . . . , x d+1 ) = C -1 1,ν 1 -1 g(x 1 )w 1,ν (x 1 )dx 1 ,
where we set ν = d-1 2 .

Proof. Applying Lemma 2 to the function x ∈ R d+1 → g(x 1 ) we get

σ -1 d S d g(x 1 )dσ(x 1 , . . . , x d+1 ) = 2σ -1 d B d g(x 1 )w d,0 (x)dx 1 • • • dx d . ( 15
)
If d = 1 then ν = 0 and the right hand side term in ( 15) is equal to

2σ -1 1 1 -1 g(x 1 )w 1,0 (x 1 )dx 1 = C -1 1,0 1 -1 g(x 1 )w 1,0 (x 1 )dx 1 ,
as desired, since 2σ -1 1 C 1,0 = 1 using σ 1 = 2π and C 1,0 = π (by [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF] and

Γ(1/2) = √ π). Assume now d ≥ 2.
Then the right hand side in ( 15) is equal to

2σ -1 d 1 -1 g(x 1 ) x 2 2 +...+x 2 d ≤1-x 2 1 w d,0 (x 1 , . . . , x d )dx 2 • • • dx d dx 1 = 2σ -1 d C d-1,0 1 -1 g(x 1 )(1 -x 2 1 ) (d-2)/2 dx 1 = 2σ -1 d C d-1,0 1 -1 g(x 1 )w 1,ν (x 1 )dx 1 ,
where we have used Lemma 1 for the first equality. Finally we verify that the constant 2σ

-1 d C d-1,0 C 1,ν is equal to 1: 2σ -1 d C d-1,0 C 1,ν = 2 Γ d+1 2 2π d+1 2 π d-1 2 Γ 1 2 Γ d 2 π 1 2 Γ d 2 Γ d+1 2 = 1
(using relations ( 4) and ( 14)), and thus we arrive at the desired identity.

We can now complete the convergence analysis for the minimization of x 1 on the unit sphere. Lemma 4. For the minimization of the polynomial f (x) = x 1 over S d with d ≥ 1, the order r upper bound (3) satisfies

f (r) = -1 + O 1 r 2 .
Proof. Let h(x 1 ) be an optimal univariate sum-of-squares polynomial of degree 2r for the order r upper bound corresponding to the minimization of x 1 over [-1, 1], when using as reference measure on [-1, 1] the measure with weight function w 1,ν (x 1 )C -1 1,ν and ν = (d -1)/2 (thus ν > -1). Applying Lemma 3 to the univariate polynomials h(x 1 ) and x 1 h(x 1 ), we obtain

σ -1 d S d h(x 1 )dσ(x) = C -1 1,ν 1 -1 h(x 1 )w 1,ν (x 1 )dx 1 = 1 and f (r) ≤ σ -1 d S d x 1 h(x 1 )dσ(x) = C -1 1,ν 1 -1
x 1 h(x 1 )w 1,ν (x 1 )dx 1 .

Since the function x 1 has the same global minimum -1 over [-1, 1] and over the sphere S d , we can apply Theorem 3 to conclude that

f (r) + 1 ≤ 1 + C -1 1,ν 1 -1 x 1 h(x 1 )w 1,ν (x 1 )dx 1 = O 1 r 2 .
We now indicate how the analysis for an arbitrary polynomial f reduces to the case of the linear coordinate polynomial x 1 . To see this, suppose a ∈ S n-1 is a global minimizer of f over S n-1 . Then, using Taylor's theorem, we can upper estimate f as follows:

f (x) ≤ f (a) + ∇f (a) T (x -a) + 1 2 C f x -a 2 ∀x ∈ S n-1 = f (a) + ∇f (a) T (x -a) + C f (1 -a T x) =: g(x) ∀x ∈ S n-1 , setting C f = max x∈S n-1 ∇ 2 f (x) 2 .
Note that the upper estimate g(x) is a linear polynomial, which has the same minimum value as f (x) on S n-1 , namely f (a) = f min = g min . From this it follows that f (r) -f min ≤ g (r) -g min and thus we may restrict to analyzing the bounds for a linear polynomial.

Next, assume f is a linear polynomial, of the form f (x) = c T x with (up to scaling) c = 1. We can then apply a change of variables to bring f (x) into the form x 1 . Namely, let U be an orthogonal n × n matrix such that U c = e 1 .

Then the polynomial g(x) := f (U T x) = x 1 has the desired form and it has the same minimum value -1 over S n-1 as f (x). As the sphere is invariant under any orthogonal transformation it follows that f

(r) = g (r) = -1 + O(1/r 2 )
(applying Lemma 4 to g(x) = x 1 ). Summarizing, we have shown the following. Theorem 4. For the minimization of any polynomial f (x) over S n-1 with n ≥ 2, the order r upper bound (3) satisfies

f (r) -f min = O 1 r 2 .
Note the difference to Theorem 2 where the constant depends only on the degree of f and the number n of variables; here the constant in O(1/r 2 ) does also depend on the polynomial f , namely it depends on the norm of ∇f (a) at a global minimizer a of f in S n-1 and on

C f = max x∈S n-1 ∇ 2 f (x) 2 .

The analysis is tight for linear polynomials

In this section we show -through an example -that the convergence rate cannot be better than Ω 1/r 2 . The example is simply minimizing x 1 over the sphere S n-1 . The key tool we use is a link between the bounds f (r) and properties of some known cubature rules on the unit sphere. This connection, recently mentioned in [START_REF] Martinez | Quadrature-based polynomial optimization[END_REF], holds for any compact set K. It goes as follows.

Suppose the points x (1) , . . . , x (N ) ∈ K and the weights w 1 , . . . , w N > 0 provide a (positive) cubature rule for K for a given measure µ, which is exact up to degree d + 2r, that is,

K g(x)dµ(x) = N i=1 w i g(x (i) )
for all polynomials g with degree at most d + 2r. Then, for any polynomial f with degree at most d, we have

f (r) ≥ N min i=1 f (x (i) ). ( 16
)
The argument is simple: if h ∈ Σ[x] r is an optimal sum-of-squares density for the parameter f (r) , then we have

1 = K h(x)dµ(x) = N i=1 w i h(x (i) ), f (r) = K f (x)h(x)dµ(x) = N i=1 w i f (x (i) )h(x (i) ) ≥ min i f (x (i) ).
As a warm-up we consider the case n = 2, where we can use the cubature rule in Theorem 5 below for the unit circle. We use spherical coordinates (x 1 , x 2 ) = (cos θ, sin θ) to express a polynomial f in x 1 , x 2 as a polynomial g in cos θ, sin θ. Theorem 5. [2, Proposition 6.5.1] For each d ∈ N, the cubature formula

1 2π 2π 0 g(θ)dθ = 1 d d-1 j=0 g 2πj d
is exact for all g ∈ span{1, cos θ, sin θ, . . . , cos(dθ), sin(dθ)}, i.e. for all polynomials of degree at most d, restricted to the unit circle.

Using this cubature rule on S 1 we can lower bound the parameters f (r) for the minimization of f (x) = x 1 over S 1 .

Namely, by setting x 1 = cos θ, we derive directly from the above theorem combined with relation ( 16) that

f (r) ≥ min 0≤j≤2r cos 2πj 2r + 1 = cos 2πr 2r + 1 = -1 + Ω 1 r 2 .
This reasoning extends to any dimension n ≥ 2, by using product-type cubature formulas on the sphere S n-1 . In particular we will use the cubature rule described in [2, Theorem 6.2.3], see Theorem 7 below.

We will need the generalized spherical coordinates given by

x 1 = r sin θ n-1 • • • sin θ 3 sin θ 2 sin θ 1 x 2 = r sin θ n-1 • • • sin θ 3 sin θ 2 cos θ 1 x 3 = r sin θ n-1 • • • sin θ 3 cos θ 2 . . . x n = r cos θ n-1 ,            (17)
where r ≥ 0 (r = 1 on S n-1 ), 0 ≤ θ 1 ≤ 2π, and 0 ≤ θ i ≤ π (i = 2, . . . , n -1).

To define the nodes of the cubature rule on S n-1 we need the Gegenbauer polynomials C λ d (x), where λ > -1/2. Recall that these are the orthogonal polynomials with respect to the weight function

w 1,λ (x) = (1 -x 2 ) λ-1/2 x ∈ (-1, 1)
on [-1, 1]. We will not need the explicit expressions for the polynomials C λ d (x), we only need the following information about their extremal roots, shown in [START_REF] De Klerk | Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing[END_REF] (for general Jacobi polynomials, using results of [START_REF] Dimitrov | Sharp bounds for the extreme zeros of classical orthogonal polynomials[END_REF][START_REF] Driver | Bounds for extreme zeros of some classical orthogonal polynomials[END_REF]). It is well known that each C λ d (x) has d distinct roots, lying in (-1, 1). Theorem 6. Denote the roots of the polynomial C λ d (x) by t

(λ) 1,d < . . . < t (λ) d,d . Then, t (λ) 1,d + 1 = Θ(1/d 2 ).
The cubature rule we will use may now be stated. Theorem 7. [2, Theorem 6.2.3] Let f : S n-1 → R be a polynomial of degree at most 2d -1, and let g(θ 1 , . . . , θ n-1 ) := f (x 1 , . . . , x n ), be the expression of f in the generalized spherical coordinates [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF]. Then

S n-1 f (x)dσ(x) = π d 2d-1 k=0 d j2=1 • • • d jn-1=1 n-1 i=2 µ ((i-1)/2) i,d g πk d , θ (1/2)
j2,d , . . . , θ

((n-2)/2) jn-1,d , (18)
where cos θ

((i-1)/2) i,d
are positive scalars as in relation (6.2.3) of [START_REF] Dai | Approximation Theory and Harmonic Analysis on Spheres and Balls[END_REF].

We can now show the tightness of the convergence rate Ω(1/r 2 ) for the minimization of a coordinate polynomial on S n-1 . Theorem 8. Consider the problem of minimizing the coordinate polynomial x n on the unit sphere S n-1 with n ≥ 2.

The convergence rate for the parameters (3) satisfies

f (d) -f min = f (d) + 1 = Ω 1 d 2 .
Proof. We have f (x 1 , . . . , x n ) = x n , so that g(θ 1 , . . . , θ n-1 ) = cos θ n-1 . Using ( 16) we obtain that

f (r) ≥ min 1≤j≤d cos θ ((n-2)/2) j,d = min 1≤j≤d t ((n-2)/2) j,d = t ((n-2)/2) 1,d = -1 + Ω 1 d 2 ,
where we use the fact that t

(λ) 1,d + 1 = Θ(1/d 2 ) (Theorem 6).
4 Implications for the generalized problem of moments

In this section, we describe the implications of our results for the generalized problem of moments (GPM), defined as follows for a compact set K ⊂ R n .

val := inf

ν∈M(K)+ K f 0 (x)dν(x) : K f i (x)dν(x) = b i ∀i ∈ [m] , (19) where
• the functions f i (i = 0, . . . , m) are continuous on K;

• M(K) + denotes the convex cone of probability measures supported on the set K;

• the scalars b i ∈ R (i ∈ [m]) are given.
As before, we are interested in the special case where K = S n-1 . This special case is already of independent interest, since it contains the problem of finding cubature schemes for numerical integration on the sphere, see e.g. [START_REF] De Klerk | A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis[END_REF] and the references therein. Our main result in Theorem 4 has the following implication for the GPM on the sphere, as a corollary of the following result in [START_REF] De Klerk | Distributionally robust optimization with polynomial densities: theory, models and algorithms[END_REF] (which applies to any compact K, see also [START_REF] De Klerk | A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis[END_REF] for a sketch of the proof in the setting described here). Theorem 9 (De Klerk-Postek-Kuhn [START_REF] De Klerk | Distributionally robust optimization with polynomial densities: theory, models and algorithms[END_REF]). Assume that f 0 , . . . , f m are polynomials, K is compact, µ is a Borel measure supported on K, and the GPM (19) has an optimal solution. Given r ∈ N, define the parameter

∆(r) = min h∈Σr max i∈{0,1,...,m} K f i (x)h(x)dµ(x) -b i , setting b 0 = val. If, for any polynomial f , we have f (r) K -f min = O(ε(r))
, where lim r→∞ ε(r) = 0, then the parameters ∆(r) satisfy:

∆(r) = O( ε(r)).
As a consequence of our main result in Theorem 4, combined with Theorem 10, we immediately obtain the following corollary. Corollary 1. Assume that f 0 , . . . , f m are polynomials, K = S n-1 , and the GPM (19) has an optimal solution. Then, for any integer r ∈ N, there is an h r ∈ Σ r such that

S n-1 f 0 (x)h r (x)dσ(x) -val = O(1/r), S n-1 f i (x)h r (x)dσ(x) -b i = O(1/r) ∀i ∈ [m].
Minimization of a rational function on K is a special case of the GPM where we may prove a better rate of convergence. In particular, we now consider the global optimization problem:

val = min x∈K p(x) q(x) , (20)
where p, q are polynomials such that q(x) > 0 ∀ x ∈ K, and K ⊆ R n is compact.

It is well-known that one may reformulate this problem as the GPM with m = 1 and f 0 = p, f 1 = q, and b 1 = 1, i.e.:

val = min ν∈M(K)+ K p(x)dν(x) : K q(x)dν(x) = 1 .
Analogously to (3), we now define the hierarchy of upper bounds on val as follows:

p/q (r) K := min h∈Σ[x]r K p(x)h(x)dµ(x) s.t. K q(x)h(x)dµ(x) = 1,

where µ is a Borel measure supported on K. Theorem 10. Consider the rational optimization problem [START_REF] Nesterov | Random walk in a simplex and quadratic optimization over convex polytopes[END_REF]. If, for any polynomial f , it holds that f (r)

K -f min = O(ε(r))
where lim r→∞ ε(r) = 0, then one also has p/q (r)

K -val = O(ε(r)). In particular, if K = S n-1 , then p/q (r)

K -val = O(1/r 2 ).
Proof. Consider the polynomial f (x) = p(x) -val • q(x). Then f (x) ≥ 0 for all x ∈ K, and f min,K = 0, with global minimizer given by the minimizer of problem [START_REF] Nesterov | Random walk in a simplex and quadratic optimization over convex polytopes[END_REF]. Now, for given r ∈ N, let h ∈ Σ r be such that f (r) K = K f (x)h(x)dµ(x), and K h(x)dµ(x) = 1, where µ is the reference measure for K. Setting

h * = 1 K h(x)q(x)dµ(x)
h, one has h * ∈ Σ r and K h * (x)q(x)dµ(x) = 1. Thus h * is feasible for problem [START_REF] Parrilo | Structured Semidefinite Programs and Semi-algebraic Geometry Methods in Robustness and Optimization[END_REF]. Moreover, by construction, The final result for the special case K = S n-1 and µ = σ (surface measure) now follows from our main result in Theorem 4.

Concluding remarks

In this paper we have improved on the O(1/r) convergence result of Doherty and Wehner [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] for the Lasserre hierarchy of upper bounds (3) for (homogeneous) polynomial optimization on the sphere. Having said that, Doherty and Wehner also showed that the hierarchy of lower bounds (9) of Lasserre satisfies the same rate of convergence, due to Theorem 2.

In view of the fact that we could show the improved O(1/r 2 ) rate for the upper bounds, and the fact that the lower bounds hierarchy empirically converges much faster in practice, one would expect that the lower bounds ( 9) also converge at a rate no worse than O(1/r 2 ). However, our analysis does not allow us to analyse the convergence of the lower bound hierarchy, and this remains an interesting open problem.

Another open problem is the exact rate of convergence of the bounds in Theorem 10 for the generalized problem of moments (GPM). In our analysis of the GPM on the sphere in Corollary 1, we could only obtain O(1/r) convergence, which is a square root worse than the special cases for polynomial and rational function minimization. We do not know at the moment if this is a weakness of the analysis or inherent to the GPM.

Note that if we pick another reference measure dµ(x) = q(x)dσ(x), where q is strictly positive on the sphere, then the convergences rates with respect to both measures σ and µ have the same behaviour (up to multiplicative constant).

It would be interesting to understand the convergence rate for more general reference measures.

Figure 1 :

 1 Figure 1: Contour plots of the Motzkin form on the sphere (top left) and optimal density for r = 3 (top right), r = 6 (bottom left), and r = 9 (bottom right).

Figure 2 :

 2 Figure 2: Plots of the Motzkin form on the sphere (top left) and optimal density for r = 3 (top right), r = 6 (bottom left), and r = 9 (bottom right), in spherical coordinates.

( 3 )

 3 have a convergence rate in O(1/r 2 ) for the case of the interval K = [-1, 1] (and as an application also for the n-dimensional box [-1, 1] n ). This result holds for a large class of measures on [-1, 1], namely those which admit a weight function w(x) = (1 -x) a (1 + x) b (with a, b > -1) with respect to the Lebesgue measure. The corresponding orthogonal polynomials are known as the Jacobi polynomials P a,b d (x) where d ≥ 0 is their degree. The case a = b = -1/2 (resp., a = b = 0) corresponds to the Chebychev polynomials (resp., the Legendre polynomials), and when a = b = λ -1/2, the corresponding polynomials are the Gegenbauer polynomials C λ d (x) where d is their degree. See, e.g., [6, Chapter 1] for a general reference about orthogonal polynomials.

[ 7 ]

 7 Consider the measure dµ(x) = (1 -x) a (1 + x) b dx on the interval [-1, 1], where a, b > -1. For the univariate polynomial f (x) = x, the parameter f (r) is equal to the smallest root of the Jacobi polynomial P a,b r+1

Lemma 1 .

 1 a probability measure over the unit ball B d . See, e.g., [6, Section 2.3.2] or [2, Section 11]. We will use the following simple lemma, which indicates how to integrate the d-variate weight function w d,λ along d -1 variables. Fix x 1 ∈ [-1, 1] and let d ≥ 2. Then we have:

  j,d and the parameters µ

K

  p(x)h * (x)dµ(x) -val = f (r) K K h(x)q(x)dµ(x) ≤ f (r) K min x∈K q(x) = O(ε(r)).

Table 1 :

 1 Upper bounds for the Motzkin form

	Motzkin

Acknowledgement

This work has been supported by European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement 813211 (POEMA).


Alix Pérusseau-Lambert

Margarita Anastassova

Mehdi Boukallel

Mohamed Chetouani

Ouriel Grynszpan
email: ouriel.grynszpan@upmc.fr

THE SOCIAL SIMON EFFECT IN THE TACTILE SENSORY MODALITY: A NEGATIVE FINDING

Keywords: Tactile, Joint action, Interpersonal coordination, stimulus-response compatibility

Objective: This study seeks to investigate whether users activate cognitive representations of their partner's action when they are involved in tactile collaborative tasks.

Background:

The social Simon effect is a spatial stimulus-response interference induced by the mere presence of a partner in a go/nogo task. It has been extensively studied in the visual and auditory sensory modalities, but never before in the tactile modality.

Method:

We compared the performances of 28 participants in three tasks: (i) a standard Simon task where participants responded to two different tactile stimuli applied to their fingertips with either their left or right foot, (ii) an individual go/nogo task where participants responded to only one stimulus and (iii) a social go/nogo task where they again responded to only one stimulus, but were partnered with another person who responded to the complementary stimulus.

Results:

The interference effect due to spatial incongruence between the side where participants received the stimulus and the foot used to answer increased significantly in the standard Simon task compared to the social go/nogo task. Such a difference was not observed between the social and individual go/nogo tasks. Performances were nevertheless enhanced in the social go/nogo task, but irrespectively of the stimulus-response congruency.

Conclusion:

This study is the first to report a negative result for the social Simon effect in the tactile modality. Results suggest that cognitive representation of the co-actor is weaker in this modality.

I. INTRODUCTION

Action performed jointly between two or more human partners has spurred much debate in the field of cognitive sciences. [START_REF] Gallotti | Social cognition in the we-mode[END_REF] advocate for the existence of a specific mode of functioning, which they called the "we-mode" (p. 160), that appears when individuals are involved in collective actions. One of the core mechanisms that give rise to the "we-mode" is our spontaneous tendency to be influenced by actions performed by co-actors. [START_REF] Sebanz | Representing others' actions: just like one's own?[END_REF] reported an experiment that illustrated how one's motor planning ability was affected by a co-actor's actions. It has become a prominent paradigm, referred to as the social or joint Simon effect, which has been extensively used to study joint actions between two co-actors [START_REF] Dittrich | Increased spatial salience in the social Simon task: A response-coding account of spatial compatibility effects[END_REF][START_REF] Iani | The role of group membership on the modulation of joint action[END_REF][START_REF] Klempova | Do you really represent my task? Sequential adaptation effects to unexpected events support referential coding for the joint Simon effect[END_REF][START_REF] Kuhbandner | The role of positive and negative affect in the "mirroring" of other persons' actions[END_REF][START_REF] Liepelt | Effects of feature integration in a hands-crossed version of the Social Simon paradigm[END_REF][START_REF] Liepelt | Trial-to-trial sequential dependencies in a social and non-social Simon task[END_REF][START_REF] Stenzel | When humanoid robots become human-like interaction partners: Corepresentation of robotic actions[END_REF][START_REF] Stenzel | The joint Simon effect depends on perceived agency, but not intentionality, of the alternative action[END_REF][START_REF] Tsai | Does the Human Motor System Simulate Pinocchio's Actions?: Coacting With a Human Hand Versus a Wooden Hand in a Dyadic Interaction[END_REF][START_REF] Vlainic | The Virtual Co-Actor: The Social Simon Effect does not Rely on Online Feedback from the Other[END_REF][START_REF] Welsh | When 1+1=1: The unification of independent actors revealed through joint Simon effects in crossed and uncrossed effector conditions[END_REF][START_REF] Welsh | Joint Simon Effects in Extrapersonal Space[END_REF]. It derives from the standard Simon task [START_REF] Simon | Reactions toward the source of stimulation[END_REF] that induces a spatial stimulusresponse interference effect whereby participants respond faster to stimuli that are presented on the same side as the limb they use to answer, even though the location of the stimuli is taskirrelevant. For instance, either a blue or green circle appears to the left or right of the participant who is to press a key on her/his left for the green circle and a key on her/his right for the blue circle [START_REF] Hasbroucq | The effects of intensity and irrelevant location of a tactile stimulation in a choice reaction time task[END_REF]. Participants' response times will decrease when the location of the stimulus is congruent with the location of the response key. This effect disappears if participants are instructed to perform a simple go/nogo task where they respond to only one of the two stimuli with a single key. The interference effect however reappears de novo when the participant is partnered with another individual who responds to the alternative stimulus. The partner's action in this social go/nogo condition thus influences the participant's motor planning. The goal of the study reported here was to test whether this effect can still be observed when the stimuli are delivered on the tactile sensory modality. This issue is expected to be highly relevant for the design of collaborative tactile interfaces.

The social Simon effect has been shown to depend on the degree of perceived interdependence between the co-actors [START_REF] Colzato | Up to "Me" or Up to "Us"? The Impact of Self-Construal Priming on Cognitive Self-Other Integration[END_REF][START_REF] Iani | The role of group membership on the modulation of joint action[END_REF][START_REF] Ruys | When competition merges people's behavior: Interdependency activates shared action representations[END_REF]. It is enhanced when the co-actor is seen as friendly and cooperative compared to intimidating and competitive [START_REF] Hasbroucq | The effects of intensity and irrelevant location of a tactile stimulation in a choice reaction time task[END_REF][START_REF] Iani | The role of group membership on the modulation of joint action[END_REF]. The social Simon effect has been classically explained by our spontaneous tendency to represent actions performed by others within our own sensory-motor system [START_REF] Sebanz | Representing others' actions: just like one's own?[END_REF][START_REF] Sebanz | Twin Peaks: An ERP Study of Action Planning and Control in Coacting Individuals[END_REF], although alternative accounts emphasize the importance of the spatial arrangement of the two co-acting partners with respect to the stimuli [START_REF] Dittrich | Keys and seats: Spatial response coding underlying the joint spatial compatibility effect[END_REF][START_REF] Dittrich | Increased spatial salience in the social Simon task: A response-coding account of spatial compatibility effects[END_REF][START_REF] Guagnano | Sharing a task or sharing space? On the effect of the confederate in action coding in a detection task[END_REF] and the attention-grabbing events caused by the coactor's actions [START_REF] Dolk | The (not so) social Simon effect: a referential coding account[END_REF][START_REF] Klempova | Do you really represent my task? Sequential adaptation effects to unexpected events support referential coding for the joint Simon effect[END_REF]. Despite the different theoretical frameworks that are used to account for the effect, the social Simon effect has been robustly reproduced across various settings and has been used in numerous imaging studies to examine neural networks associated with joint action [START_REF] Costantini | Studying social cognition using near-infrared spectroscopy: the case of social Simon effect[END_REF][START_REF] De La Asuncion | Neurophysiological evidence for diminished monitoring of own, but intact monitoring of other's errors in schizophrenia[END_REF][START_REF] Dolk | Morphometric gray matter differences of the medial frontal cortex influence the social Simon effect[END_REF][START_REF] Sebanz | Twin Peaks: An ERP Study of Action Planning and Control in Coacting Individuals[END_REF][START_REF] Sebanz | Is it really my turn? An eventrelated fMRI study of task sharing[END_REF][START_REF] Tsai | Action Co-representation is Tuned to Other Humans[END_REF]). Yet, to our knowledge, until now, experiments on the social Simon effect have always used either visual or auditory stimuli, but have never been conducted in the tactile modality.

The small number of studies that implemented the standard Simon task in the tactile modality have been consistent in reporting the expected interference effect. [START_REF] Hasbroucq | The effects of intensity and irrelevant location of a tactile stimulation in a choice reaction time task[END_REF] applied mechanical taps on the index fingers and thumbs of the two hands and found shorter response times when the stimulation was congruent with the hand with which participants had to answer. In the study by Medina, McCloskey, Coslett and Rapp (2014), participants received vibrotactile stimuli on their middle fingers and had to respond using foot pedals. They responded faster on trials where the finger receiving the stimulus and the foot releasing the pedal were somatotopically congruent. [START_REF] Salzer | In Touch With the Simon Effect *The first two authors contributed equally[END_REF] exerted vibrotactile stimulations on the left and right part of the back of the torso. Once again, they observed an interference effect when participants had to answer with the hand opposite to the side where they perceived the tactile stimulus.

In the present experiment, we applied vibrotactile stimulations on the index fingertips of participants, who had to respond by pressing foot pedals. Following a classical experimental design for studying the social Simon effect, we compared three tasks: (i) a standard Simon task where participants received two different types of tactile vibration and had to respond with their two feet;

(ii) an individual go/nogo task where participants still received the two types of tactile vibration, but responded to only one of them; (iii) a social go/nogo task where participants responded in the same way as in the individual go/nogo task, while another person sitting next to them responded to the complementary stimulus. We hypothesized that the congruency between the side where the vibrotactile stimulation was applied and the foot with which participants had to respond would have an effect on response times in the standard Simon task and in the social go/nogo task, but not in the individual go/nogo task. Additionally, participants were administered the Autism-Spectrum Quotient (AQ) questionnaire [START_REF] Baron-Cohen | The Autism-Spectrum Quotient (AQ): Evidence from Asperger Syndrome/High-Functioning Autism, Malesand Females, Scientists and Mathematicians[END_REF], which assesses Autism-Spectrum traits in the general population. This questionnaire provided a metric that we intended to correlate with the amplitude of the hypothesized interference effect in the social Simon go/nogo task. A previous study [START_REF] Sebanz | Far from action-blind: Representation of others' actions in individuals with Autism[END_REF] reported that the social Simon effect was unaltered in individuals with Autism Spectrum Disorder (ASD). However, given the profound impairments in the ability to spontaneously represent others' intentions in action that are associated with ASD [START_REF] Senju | Mindblind eyes: an absence of spontaneous theory of mind in Asperger syndrome[END_REF] and the theory linking the social Simon effect to a spontaneous representation of others' action [START_REF] Sebanz | Representing others' actions: just like one's own?[END_REF][START_REF] Sebanz | Twin Peaks: An ERP Study of Action Planning and Control in Coacting Individuals[END_REF], we tentatively hypothesized a negative correlation between the social Simon effect and Autism-Spectrum traits given the social nature of the experimental manipulation.

II. METHODS

II.1 Participants

Twenty-eight adults (14 males, 14 females) participated in the experiment. Their age range was 21 -39 years with a mean of 27.4 years (SD = 5.1). A power analysis was performed prior to the experiment to estimate the required minimum sample size based on data reported by former studies [START_REF] Hasbroucq | The effects of intensity and irrelevant location of a tactile stimulation in a choice reaction time task[END_REF][START_REF] Liepelt | Trial-to-trial sequential dependencies in a social and non-social Simon task[END_REF]. The computation was carried out with the G*Power application [START_REF] Faul | G*Power 3: A flexible statistical power analysis program for the social, behavioral, and biomedical sciences[END_REF] setting the significance threshold to 0.05 and the power to 0.9. It yielded a minimum sample size of 16. Participants were free of any known psychiatric or neurologic symptoms, non-corrected visual or auditory deficits and recent use of any substance that could impede concentration. This research complied with the tenets of the Declaration of Helsinki and was approved by the Institutional Review Board at Université Paris-Descartes. Informed consent was obtained from each participant.

II.2 Material

The tactile stimulations were produced by two Linear Resonant Actuators (LRA) from Precision MicroDrive™ that produced vibrations. The actuators were monitored with the National Instrument Emission/ Acquisition cards (NI 9265 and NI 9205). The input signals were amplified and powered by home-made electronic cards. The entire experimental systems was controlled with a home-made program coded in the Python language. The LRAs were fixed on a table and positioned on an axis that was parallel to the edge of the table. Participants would sit on a comfortable chair in front of the table, in-between the two LRAs, and would place their right and left index fingertips on the LRA that was on the same side as their hand. The vibrotactile stimuli were provided by a 205 Hz vibration of either (a) 1.5μm displacement amplitude or (b) 3.7μm displacement amplitude. The vibration was continuous and lasted 250ms. The 1.5μm amplitude vibration was referred to as the "low" stimulus signal and the 3.7μm amplitude vibration was the "high" stimulus signal. Participants responded to the tactile stimuli by pushing pedals that were located under the table. One pedal was on the left side of the participant and the other one was on the right. Each pedal was associated with a given vibration amplitude (either high or low) that was indicated on the pedal. The vibration noise was totally eliminated by having participants wear a noise-cancelling headphones playing pink noise.

Hence, the sense of touch was the only sensory modality that participants could rely on to discriminate between the two vibration amplitudes.

II.3 Procedure

Participants sat next to the experimenter who was on their left. A computer screen was placed on the table in-between the participant and the experimenter. Instructions were provided verbally and by writing. The written version was accessible throughout the experiment. Participants were instructed to respond as fast as they could to the tactile stimuli. They had to place their feet symmetrically with respect to their body. Their feet were separated by a distance equivalent to the size of their hips or distance from shoulder to shoulder, according to what was the most natural posture for them. The pedals were placed besides each one of their foot, either under it or next to it, in the most comfortable and easy to reach positions for every individual participant. Participants were then introduced the low and high stimuli on each LRA. For half of the participants, the "high" pedal, which was to be pressed when perceiving a high stimulus, was on their right side, and the "low" pedal on their left side. The reverse configuration was used for the other half of participants.

As in [START_REF] Salzer | In Touch With the Simon Effect *The first two authors contributed equally[END_REF], each trial began with a fixation cross that was displayed at the center of the screen for 250ms. When the fixation cross disappeared, one of the LRA delivered a vibrotactile stimulus for 250ms. Once the vibrotactile stimulus began, participants had 1500ms to respond by pressing one of the two pedals. After the participants' response, a "Right" or "Wrong" feedback message was displayed during 300ms. No feedback was provided if participants had not responded fast enough. The feedback message was followed by a black screen that lasted until the next trial began. The inter-trial interval duration varied randomly between 1000 and 1500ms. Figure 1 summarizes the event flow during a trial. The experiment was composed of 5 blocks that were separated by short breaks. The first block was used to train participants in perceiving the two different vibrotactile stimulations. It contained 60 trials that were not included in the analyses. The four following blocks comprised 120 trials each and were used to collect experimental data, that is, reaction time and accuracy (number of errors). The Reaction Time was measured from the stimulus onset until the participant's response. During each block, the LRAs produced an equal number of low and high amplitude stimuli that were equally distributed on the left and on the right. The left/right positions and low/high amplitudes of the stimuli were randomly allocated. As explained above, participants were to respond to the low or high stimuli with either their left foot or right foot depending on where the low and high pedals had been placed. When the stimulus appeared on the same side as the pedal to be pressed, the trial was said to be congruent. It was incongruent when the stimulus appeared on the opposite side.

The four experimental blocks presented three different tasks: One block was dedicated to the standard Simon task, one block to the individual go/nogo task and two blocks for the social go/nogo task. To neutralize the effect of the tasks' order, their sequential order was counterbalanced across participants using the Latin Square method. As there were three tasks, there were six possible counterbalancing sequences and similar numbers of participants were allotted to each possible sequence (4 to 6 participants per sequence).

In the standard Simon task, participants had to respond to the two amplitudes of vibration stimuli (high and low) by pressing the matching pedal. In the individual and social go/nogo tasks, participants would either respond exclusively to the low amplitude stimuli for the first 60 trials of each block and to the high amplitude stimuli for the next 60 trials, or they would respond first to the high amplitude stimuli and then to the low amplitude stimuli. The order in which participants were to respond to vibration amplitudes was counterbalanced across participants. The position of the pedal which they had to press was also counterbalanced across participants.

The only difference between the individual go/nogo condition and the social go/nogo condition was that the experimenter took part in the task during the social go/nogo condition. In the latter condition, the experimenter responded to the amplitude of the vibration stimuli that the participant was asked not to respond to. For instance, if the participant had to respond to the low amplitude stimuli, the experimenter responded to the high amplitude stimuli and vice versa. The instructions explicitly specified that the participant and the experimenter were to cooperate in performing the task. The experimenter placed her fingertips on a second set of LRAs that reproduced the vibrotactile stimuli sent to the participant. The experimenter used the same foot as the participant to press the response pedal. The experimenter was the same for all participants. As she was a female, the participant's gender was taken into account in the statistical analysis. The experimenter was required to respond evenly with every participants and not adjust to the participants' performances.

Standard Simon

Individual Go/nogo Social Go/nogo At the end of the experiment, participants were asked to fill in the Autism-Spectrum Quotient (AQ) questionnaire [START_REF] Baron-Cohen | The Autism-Spectrum Quotient (AQ): Evidence from Asperger Syndrome/High-Functioning Autism, Malesand Females, Scientists and Mathematicians[END_REF]. The AQ is a psychometric instrument used screen autisticlike traits in the general population. The AQ focuses on questions related to social and communicative skills, imagination and flexibility.

III. RESULTS

Response times and error were analyzed using repeated measures analyses of variance (ANOVA) with participants' gender as an adjustment factor to account for possible effects due to the fact that the experimenter was always a female. Three ANOVA were conducted for each measure. Every ANOVA had two within factors: the experimental task and the congruency of the trial. Congruent trials were those where the stimulus appeared on the same side as the response pedal. Incongruent trials were those where the stimulus appeared on the opposite side.

The experimental design included three tasks: the standard Simon task, the individual go/nogo task and the social go/nogo task. To test whether there was a social Simon effect, we performed one ANOVA that compared the social go/nogo task with the individual go/nogo task and another ANOVA comparing the social go/nogo task with the standard Simon task. The social Simon effect entailed that congruency would affect response times and errors in the standard Simon task and the social go/nogo task, while it would not in the individual go/nogo task. We therefore hypothesized that the ANOVA comparing the social go/nogo task with the individual go/nogo task would yield an interaction between the task and congruency factors, but that no such interaction would be observed in the ANOVA comparing the social go/nogo task with the standard Simon task. Post-hoc ttest were performed using the Tukey procedure. The analyses were carried out with Statistica software (www.statsoft.com).

Although the sequential order of the tasks had been counterbalanced across participants, we tested for a possible order effect by adding an additional adjustment factor representing the order in which tasks had been administered. Yet, the tasks' order did not yield any significant differences except for the percentage of errors in the ANOVA comparing the social go/nogo task with the standard Simon task and, even in this case, this additional adjustment factor did not change the pattern of results.

Hence, to facilitate readability, we did not include this additional factor in the analyses presented below.

III.1 Number of errors

We computed the percentage of erroneous trials in each task. A trial was considered erroneous when the participant pressed the wrong pedal. There were generally few errors and thus the distribution of the percentage of errors was skewed towards zero. To normalize the distribution, we used a Box Cox transformation (Sakia, 1992) before applying the ANOVA. The ANOVA comparing the individual go/nogo task with the social go/nogo task did not yield any significant main effect, nor interaction between task and congruency, F(1,26) = 0.52, p = 0.48,  p ² = 0.02 . The ANOVA comparing the standard Simon task with the social go/nogo task revealed a significant main effect of task, F(1,26) = 16.08, p < 0.001,  p ² = 0.38. There were more errors in the standard Simon task (median = 9.17%, interquartile range = 4.58%) than in the social go/nogo task (median = 4.17%, interquartile range = 3.75%). There was no main effect of congruency, nor interaction between congruency and task. The number of errors in each block is plotted in Figure 3. As explained earlier, we additionally sought to test whether the amplitude of the social Simon effect would correlate with AQ scores. The AQ scores of the participants ranged from 7 to 35 (the maximum possible score is 50) with a mean of 18.2 (SD = 6.9). The amplitude of the social Simon effect was computed as the difference between response times in the incongruent and congruent trials.

Pearsons' correlation coefficients were not significant: r = -0.03 p = 0.89.

III.4 Correlations with the experimenter's response times

Given the unexpected shorter response times in the social go/nogo task, we conducted further analyses to qualify the effect of the partnership. We correlated the response times of the experimenter with those of the participants during this task. Pearson's correlation was significant, r = 0.87 p < 0.001. We also verified whether there were significant differences in response times between the experimenter and the participants during the social go/nogo task with a Student t-test.

The difference was not significant, t(27) = 1.74 p = 0.09.

IV. DISCUSSION

The results of the present study confirmed the existence of a Simon effect for tactile stimulations, but they did not support our hypothesis of a reappearance of this effect when the action was distributed between two partners. Participants responded faster to congruent trials than to incongruent trials in the standard Simon task where they had to react to the two different vibrotactile amplitudes. When comparing the individual and social versions of the go/nogo task where participants responded to only one vibrotactile amplitude, we did not find the expected difference in the effect of congruency. By contrast, the effect of congruency was superior in the standard Simon condition compared to the social go/nogo condition. In other words, the influence of congruency was reduced in the social go/nogo task to a degree that was not dissimilar to the individual go/nogo task. Response times thus showed patterns that were opposite to what the social Simon effect predicted. Given that our study was dimensioned according to previous studies carried out with visual stimuli, this outcome tentatively suggests that the social Simon effect may depend on the sensory modality of the stimuli. If so, a reduced social Simon effect in the tactile modality is not well accounted for by the current theories explaining this effect. It may be that representing another person's action within one's own sensory-motor system [START_REF] Sebanz | Representing others' actions: just like one's own?[END_REF] or response coding scheme [START_REF] Dittrich | The joint flanker effect and the joint Simon effect: On the comparability of processes underlying joint compatibility effects[END_REF][START_REF] Dolk | The (not so) social Simon effect: a referential coding account[END_REF] does not spontaneously occur when stimulations are in the tactile sensory modality. The sense of touch is contingent on one's local skin contact with an object. It is therefore more personal and does not yield a sensory environment that can be straightforwardly shared. In the social go/nogo task of our experiment, the two partners received the same vibrotacile stimulations, but they originated from different (although identical) sources. The lack of shared sensory space may have hindered the natural tendency of participants to activate sensory-motor representations of their partner's actions. This interpretation is consistent with neural imaging evidence that emphasize the important role of shared attention mechanisms in the social Simon effect [START_REF] Costantini | Studying social cognition using near-infrared spectroscopy: the case of social Simon effect[END_REF].

The Autism-Spectrum Quotient (AQ) did not correlate with the response time difference between the incongruent and congruent trials in the social go/nogo condition. This result is not surprising given the absence of a social Simon effect.

Despite the absence of the expected social Simon interference, the social go/nogo condition did have an effect: Performances increased independently of the congruency of the stimuli, as shown by the reduced response times in the social go/nogo task compared to the standard Simon and individual go/nogo tasks. This decrease in response times did not come at the expense of accuracy. The percentage of erroneous trials was actually lower in the social go/nogo task compared to the standard Simon task.

One could argue that participants could have used a strategy whereby they relied on the experimenter's responses, that is, responding only when the experimenter did not respond and inhibiting their response when the experimenter responded. Such a strategy entails that participants would have been waiting for the experimenter' response, or lack of response, before they would initiate a response. If this was the case, then their response times would be superior to the upper range of the experimenter's response times. However, response times of the participants were not significantly different from those of the experimenter. Additionally, waiting for the experimenter's response should have increased the cognitive load of the social go/nogo task compared to the individual go/nogo task, which seems at odds with the fact that processing time was actually reduced in the social go/nogo task.

Altogether, the data showed that performing the task with a partner boosted performances. A similar result was reported in the study on the social Simon effect by [START_REF] Liepelt | Trial-to-trial sequential dependencies in a social and non-social Simon task[END_REF]. The performance boost observed in our experiment cannot be merely attributed by the attendance of another person alongside the participant. Indeed, the experimenter sat next to the participants in every experimental conditions. The only variation introduced by the social go/nogo condition was that the experimenter took part in the task. The enhancing effect on performances in this condition may be explained by the classical effect of social facilitation induced by engaging in the same activity as a partner [START_REF] Zajonc | Social Facilitation[END_REF]. Additionally, the response times of the participants correlated with those of the experimenter. The participants and the experimenter thus appeared to have adjusted their processing time when performing the task as partners. This observation tends to support the view of social facilitation induced by the partnership.

In the present experiment, as participants were partnered with the experimenter in the social go/nogo task, they may have considered her as a reference that they should try to match. This could explain why their performances were boosted in the social go/nogo condition. Further research would be warranted to verify whether or not the observed enhancement of performances in the social go/nogo task would have also occurred if the partner had been another randomly selected participant. Despite this limitation, the present study contributes to the current knowledge on joint action by indicating that the social Simon effect may be hindered when the stimulations are in the tactile modality. This outcome suggests that coordination between co-actors might be challenging in this modality as their natural tendency to activate sensory-motor representations of their partner's actions could to be less spontaneous than in other modalities. We tentatively attributed this failure to a lack of shared sensory space. This hypothesis could be tested by future experiments in which the tactile stimulations would be provided to the two partners via the same vibrotactile devices.

Figure 1 :

 1 Figure 1: Flow of sequential events that occur during a trial

Figure 2 :

 2 Figure 2: Upper view of the experimental setups for the three tasks. In each task, the participant received two tactile stimuli from two LRA. Top: standard Simon task: The participant responded to two stimuli with two pedals; Middle: Individual go/nogo task: The participant responded to only one stimulus with one pedal; Bottom: Social go/nogo task: The experimenter and the participant each responded to a different stimuli with one pedal. The position of the response pedal in the individual and social go/nogo tasks was counterbalanced across participants. LRA : Linear Resonant Actuator

Figure 3 :Figure 4 :

 34 Figure 3: The percentage of erroneous trials in each experimental tasks. As the distribution of data was not normal, boxplots were used to represent the median (horizontal bold lines), the 25 th and 75 th percentiles (boxes) and the minimum and maximum values (error bars)

Conflict of Interest:

The authors declare that they have no conflict of interest.

Ethical approval: All procedures performed in studies involving human participants were in accordance with the ethical standards of the institutional and/or national research committee and with the 1964 Helsinki declaration and its later amendments or comparable ethical standards.

Informed consent was obtained from all individual participants included in the study.


Athénaïs Vaginay
email: <athenais.vaginay@inria.fr>

Malika Smail-Tabbone

Taha Boukhobza

Towards an automatic conversion from SBML core to SBML qual

The SBML format is the de facto standard to encode biological model in different formalisms. It was first developed to encode quantitative models like Differentials Equations (DEs), but the current release allows the definition of packages extending the core format. One of these packages, named qual, encodes qualitative models like Boolean Networks (BNs). To the best of our knowledge, there is no automatic pipeline to convert a quantitative model encoded in SBML core into a qualitative model encoded with the qual package. Here, we explore such a pipeline on a relatively simple system: the cell division of fission yeast, which has been studied both with a set DEs [1] and with a BN [2]. Our approach consists in extracting the model topology from the set of DEs and in solving them numerically in order to retrieve the time course data of species' concentrations on which we apply a discretization. Then we extract from these data a scarce state transition table. We are currently investigating ways to synthesize a BN fitting both topology knowledge and state transitions.

From 1 :Case 2 :

 12 Biological system Quantitative model (e.g. DE) Qualitative models (e.g. BN) MPF E.g. the cell division cycle of wild type fission yeast θ i =1 for Cdc2/Cdc13* and Cdc2/Cdc13 otherwise 0 model agents positive interaction (a ij =1) negative interaction (a ij =-1) self-degradation (a ii =-1) + state transition rules Next objectives: -Use the knowledge about topology derived from the kinetic model to synthetize boolean functions -Define pipeline validation criteria such as attractor identification and matching -Assess the pipeline on other models -Fully automatize the pipeline → to be submitted to SBFC convertor Complete consistent STT → Convertor to canonical boolean formula (BioLQM) (weighted) False examples (weighted) True examples boolean classifier + Incomplete consistent STT → REVEAL (BoolNet) Case 3: Incomplete inconsistent STT → Lähdesmäki's best-fit extension (BoolNet) Case 4: Incomplete inconsitent STT + topology →