S Akshay

Hugo Bazille

Blaise Genest

Mihir Vahanwala

On Robustness for the Skolem and positivity problems

Keywords: 2012 ACM Subject Classification Theory of computation; Logic and verification Skolem problem, verification, dynamical systems, robustness Digital Object Identifier 10.4230/LIPIcs.STACS.2022.51

.

In this paper, we consider problems that lie between the initialized and uninitialized variant. More precisely, we ask if 0 (resp. negative numbers) can be avoided from every initial configuration in a neighborhood of a given initial configuration. This can be considered as a robust variant of the Skolem (resp. positivity) problem. We show that these problems lie at the frontier of decidability: if the neighborhood is given as part of the input, then robust Skolem and robust positivity are Diophantine-hard, i.e., solving either would entail major breakthrough in Diophantine approximations, as happens for (non-robust) positivity. Interestingly, this is the first Diophantinehardness result on a variant of the Skolem problem, to the best of our knowledge. On the other hand, if one asks whether such a neighborhood exists, then the problems turn out to be decidable in their full generality, with PSPACE complexity. Our analysis is based on the set of initial configurations such that positivity holds, which leads to new insights into these difficult problems, and interesting geometrical interpretations.

Introduction

A linear recurrence relation (LRR) is a relation u n+κ = κ-1 j=0 a j • u n+j for all n, κ ∈ N, κ ≥ 1, defined by a tuple of non-negative, rational coefficients (a 0 , . . . , a κ-1 ) . Given the first κ entries of the recurrence u 0 , . . . u κ-1 (called the initial configuration), the LRR uniquely defines an infinite sequence (u n ) n∈N , called a Linear Recurrence Sequence (LRS). The Skolem problem asks, given an LRS, i.e., a recurrence relation and an initial configuration, whether the sequence ever hits 0, i.e. does there exist n ∈ N with u n = 0. The positivity problem is a variant where the question asked is whether for all n ∈ N, u n ≥ 0. Both these problems have applications in software verification, probabilistic model checking, discrete dynamic systems, theoretical biology, economics.

While the statements seem simple, the decidability of these problems remains open since their introduction in the 1930's. Only partial decidability results are known, e.g., when the dimension is <5 [START_REF] Vereshchagin | The problem of appearance of a zero in a linear recurrence sequence[END_REF]. For a subclass of LRS called simple, positivity is decidable for order <10 [START_REF] Ouaknine | On the positivity problem for simple linear recurrence sequences[END_REF]. On top of the inability to provide an algorithm to decide Skolem or positivity in the general case, the authors of [START_REF] Ouaknine | Positivity problems for low-order linear recurrence sequences[END_REF] prove an important hardness result: solving positivity would entail a major breakthroughs in Diophantine approximations. More precisely, one would be able to approximate the type of many transcendental numbers t, i.e., how close one can approximate t with rational numbers with small denominators.

This hardness result contrasts with positive results obtained for relaxations of the problems. First, the continuous relaxation, where instead of considering discrete steps for the recurrence, Chonev et al [START_REF] Chonev | On the Skolem problem for continuous linear dynamical systems[END_REF] considers a continuous process, and some corresponding questions turn out to be decidable subject to Schanuel's Conjecture. Second, instead of considering a fixed initial configuration, [START_REF] Tiwari | Termination of linear programs[END_REF][START_REF] Braverman | Termination of integer linear programs[END_REF] consider every possible configuration as initial, i.e., they ask if there exists an initial configuration starting from which ensures that all entries of the sequence remain positive (this is sometimes called the uninitialized positivity problem). Surprisingly they show that this problem can be decided in PTIME. More recently, this result has been extended to processes with choices [START_REF] Akshay | Distribution-based objectives for Markov Decision Processes[END_REF].

In this paper, we consider a natural variant that lies between the hard question of fixed initial configuration [START_REF] Ouaknine | Positivity problems for low-order linear recurrence sequences[END_REF], and the easy question when the initial configuration is totally unconstrained [START_REF] Tiwari | Termination of linear programs[END_REF][START_REF] Braverman | Termination of integer linear programs[END_REF]. More precisely, we ask whether starting from an initial configuration in a neighborhood, all entries of the recurrence sequence remain positive (we call this the robust positivity problem) or away from zero (we call this the robust Skolem problem). An immediate question that arises is whether the neighborhood is part of the input or not and it turns out that this has a significant impact on decidability, as we discuss next. Our motivation to look at these problems comes from their role in capturing a powerful and natural notion of robustness, where the exact initial configuration cannot be fixed with arbitrarily high precision (which is often the case with real systems).

Since we need to tackle multiple initial configurations, we reason about the set of initial configurations from which positivity holds, which is sufficient to answer robustness questions. For that, we revisit the usual algebraic equations in a more graphical manner, which forms the crux of our approach. This allows us to reinterpret and generalize the hardness result of [START_REF] Ouaknine | On the positivity problem for simple linear recurrence sequences[END_REF], giving our first main contribution: if the neighborhood is given as a fixed ball, then the problems remain hard: both robust Skolem and robust positivity are Diophantine-hard. Interestingly, this holds regardless of whether the ball is open or closed.

We then turn to the problems where the ball is not fixed, and ask if there exists a radius ψ > 0 such that 0 or negative numbers can be avoided from every initial configuration in the ψ ball around a given initial configuration. Our second main contribution is to show 51:3 that this robust version of the Skolem and positivity problems are both decidable in full generality, with PSPACE complexities. Related work. As mentioned earlier, the Skolem problem and its variants have received a lot of attention. Given the hardness of these problems, ε-approximate solutions have been considered, e.g., in [START_REF] Biscaia | Decidability of approximate Skolem problem and applications to logical verification of dynamical properties of markov chains[END_REF][START_REF] Manindra Agrawal | Approximate verification of the symbolic dynamics of Markov chains[END_REF] with different definitions of approximations. In comparison with our work, these are designed towards allowing approximate model checking. More recently the notion of imprecision in Skolem and related problems was considered in [START_REF] Baier | Reachability in dynamical systems with rounding[END_REF][START_REF] Julian | The pseudo-Skolem problem is decidable[END_REF]. In [START_REF] Baier | Reachability in dynamical systems with rounding[END_REF], the authors consider rounding functions at every step of the trajectory. In [START_REF] Julian | The pseudo-Skolem problem is decidable[END_REF], the so called Pseudo-Skolem problem is defined, where imprecisions up to ε are allowed at every step of the trajectory, which is shown to be decidable in PTIME. These are quite different from our notion of robustness, which faithfully considers the trajectories generated from a ball representing ε-perturbations around the initial configuration. Lastly, [START_REF] Neumann | Decision problems for linear recurrences involving arbitrary real numbers[END_REF] considers real numbers as input (instead of rational numbers). This allows one to consider the set of initial configurations for which decidability of Skolem is not known, and show that this set has Lebesgue measure 0.

Preliminaries

Let κ be any non-negative integer (which will be used to denote the order of the LRS). Let c, d be two vectors of R κ that can be seen as one dimensional matrices of R κ×1 . The distance between c, d is defined as ||c -d|| = (cd) T (cd), the standard L 2 distance. In this paper, we will consider two norms on vectors: the first is the standard L 2 norm ||c||. The second is size(c), denoting the size of its bit representation i.e., number of bits needed to write down c (for complexity). We use the same notation for scalar constants with size(a) denoting the number of bits to represent a real/rational constant a. An algebraic number α is a root of a polynomial p with integer coefficients. It can be represented uniquely [20] by a 4-tuple (p, a, b, r) as the only root of p at distance < r of a + ib, with a, b, r ∈ Q (also see Appendix 8.1). We define size(α) as the size of the bit representation of (p, a, b, r).

Linear Recurrence Sequences

We start by defining linear recurrence relations and sequences over rationals.

▶ Definition 1. A linear recurrence relation (u n ) n∈N of order κ is specified by a tuple of coefficients a = (a 0 , . . . , a κ-1 ) ∈ Q κ . Given an initial configuration c = (c 0 , . . . , c κ-1 ) ∈ Q κ , the LRR uniquely defines a linear recurrence sequence (LRS henceforth), which is the sequence (u n (c)) n∈N , inductively defined as u j (c) = c j for j ≤ κ -1, and

u n+κ (c) = κ-1 j=0 a j u n+j (c) for all n ∈ N
The companion matrix associated with the LRR/LRS (it does not depend upon the initial configuration c) is:

M =        0 1 0 . . . 0 0 0 1 . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . 1 a 0 a 1 a 2 . . . a κ-1        S TA C S 2 0 2 2

51:4 On Robustness for the Skolem and positivity problems

The characteristic polynomial of the LRR/LRS is X κκ-1 j=0 a j X j . The LRS is said to be simple if every root of the characteristic polynomial has multiplicity one. The size s of the LRS is the size of its bit representation and is given by s = κ-1 j=0 (size(a j ) + size(c j )). Notice that given an initial configuration c ∈ Q κ , we have that M n c = (u n (c), . . . , u n+κ-1 (c)). Reasoning in the κ dimensions (u n , . . . , u n+κ-1 ) is a very useful technique that we will use throughout the paper as it displays the LRR as a linear transformation M.

The characteristic roots of an LRR/LRS are the roots of its characteristic polynomial, and also the eigenvalues of the companion matrix. Let γ 1 , . . . , γ r ∈ C be the characteristic roots of the LRR/LRS. An eigenvalue γ i is called dominant if it has maximal modulus |γ i | = max j≤r |γ j |, and residual otherwise. For all j ≤ r, γ j is algebraic and size(γ j ) = s O (1) . We denote by m j the multiplicity of γ j . We have

r j=1 m j = κ.
▶ Proposition 2 (Exponential polynomial solution [START_REF] Everest | Recurrence Sequences[END_REF]). Given an initial configuration c, there exists a unique tuple of coefficients (α ij (c)) i≤r,j<mr such that for all n,

u n (c) = r i=1   mr-1 j=0 α ij (c)n j   γ n i
The coefficients α ij (c) can be solved for from the initial state c [START_REF] Halava | Skolem's problem -on the border between decidability and undecidability[END_REF]. It is implicit in the solution that for all i, j, both α ij and 1 αij are algebraic with values and norms upper bounded by 2 s O (1) . A formal proof of this claim can be found in [2, Lemmas 4,[START_REF] Akshay | Distribution-based objectives for Markov Decision Processes[END_REF][START_REF] Baier | Reachability in dynamical systems with rounding[END_REF].

If the LRS is simple, then by definition m i = 1 for all i, and

u n = r i=1 α i (c)γ n i , with α i (c) linear in c, ie α i (λc + λ ′ c ′ ) = λα i (c) + λ ′ α i (c ′ ).
▶ Example 3. Consider the Linear Recurrence Relation of order 6 with a = (-1, 4, -8, 10, -8, 4), i.e. u n+6 = 4u n+5 -8u n+4 + 10u n+3 -8u n+2 + 4u n+1 -u n . The roots of the characteristic polynomial are 1, e i2πθ , e -i2πθ , with θ = 1 3 , each with multiplicity 2, and all dominant (they have the same modulus 1). The exponential polynomial solution is of the form u n (c) = z(c)n + z ′ (c) + (x(c)n + x ′ (c))e i2πnθ + (y(c)n + y ′ (c))e -i2πnθ . As u n (c) is real, we must have that x(c), y(c) are conjugates, as well as x ′ (c), y ′ (c), and thus:

un(c) = z(c)n + z ′ (c) + 2(Re(x(c))n + Re(x ′ (c))) cos(2πnθ) + 2(Im(x(c))n + Im(x ′ (c))) sin(2πnθ)

Skolem and positivity problems

▶ Definition 4 (Skolem problem). Let (u n ) n∈N an LRR and c ∈ Q κ . The Skolem problem is to determine if there exists n ∈ N such that u n (c) = 0. The positivity (resp. strict positivity) problem is to determine if for all n ∈ N, u n (c) ≥ 0 (resp. u n (c) > 0).

In this work, we will be more interested in the complement problem of Skolem: namely, whether u n (c) ̸ = 0 for all n. This is of course equivalent in terms of decidability, but this formulation is more meaningful in terms of robustness, where we want to robustly avoid 0.

The famous Skolem-Mahler-Lech theorem states that the set {i | u i (c) = 0} is the union of a finite set F and finitely many arithmetic progressions [START_REF] Skolem | Ein Verfahren zur Behandlung gewisser exponentialer Gleichungen, 8de Skand. mat. Kongr. Forh[END_REF][START_REF] Mahler | Eine arithmetische Eigenschaft der Taylor-koeffizienten rationaler Funktionen[END_REF][START_REF] Berstel | Deux propriétés décidables des suites récurrentes linéaires[END_REF]. These arithmetic progressions can be computed but the hard part lies in deciding if the set F is empty: although we know that there is N such that for all n > N , n / ∈ F , we do not have an effective bound on this N in general. The Skolem problem has been shown to be decidable for LRS of order up to 4 [START_REF] Mignotte | The distance between terms of an algebraic recurrence sequence[END_REF][START_REF] Vereshchagin | The problem of appearance of a zero in a linear recurrence sequence[END_REF] and is still open for LRS of higher order. Also, only an NP-hardness bound is known if the order is unrestricted [START_REF] Blondel | The presence of a zero in an integer linear recurrent sequence is NP-hard to decide[END_REF][START_REF] Akshay | Complexity of restricted variants of skolem and related problems[END_REF].

For simple LRS, positivity has been shown to be decidable up to order 9 [START_REF] Ouaknine | On the positivity problem for simple linear recurrence sequences[END_REF]. In [START_REF] Ouaknine | Ultimate positivity is decidable for simple linear recurrence sequences[END_REF], it is proved that positivity for simple LRS is hard for co∃R, the class of problems whose complements are solvable in the existential theory of the reals. A last result, from [START_REF] Ouaknine | Positivity problems for low-order linear recurrence sequences[END_REF], shows the difficulty of positivity, linking it to Diophantine approximation: how close one can approximate a transcendental number with a rational number with small denominator. We will follow the reasoning from [START_REF] Ouaknine | Positivity problems for low-order linear recurrence sequences[END_REF]. The Diophantine approximation type of a real number x is defined as:

L(x) = inf c ∈ R | x - n m < c m 2
, n, m ∈ Z As mentioned in [START_REF] Ouaknine | Positivity problems for low-order linear recurrence sequences[END_REF], the Diophantine approximation type of most transcendental numbers is unknown.

Let A = {p + qi ∈ C | p, q ∈ Q \ {0}, p 2 + q 2 =
1}, i.e., the set of points on the unit circle of C with rational real and imaginary parts, excluding 1, -1, i and -i. The set A consists of algebraic numbers of degree 2, none of which are roots of unity [START_REF] Ouaknine | Positivity problems for low-order linear recurrence sequences[END_REF]. In particular, writing p + qi = 2 i2πθ = (-1) 2θ , we have that θ / ∈ Q [START_REF] Ouaknine | Positivity problems for low-order linear recurrence sequences[END_REF]. We denote:

T = θ ∈ (-1/2, 1/2] | e 2πiθ ∈ A
As argued in [START_REF] Ouaknine | Positivity problems for low-order linear recurrence sequences[END_REF], the set T is dense in (-1 2 , 1 2 ], and is made only of transcendental numbers. In general, we don't have a method to compute L(θ) for θ ∈ T (or approximate it with arbitrary precision): ▶ Definition 5. We say that a problem is T -Diophantine hard if its decidability entails that for all θ ∈ T and ε > 0, one can compute a number ℓ such that |ℓ -L(θ)| ≤ ε.

Remarkably, in [START_REF] Ouaknine | Positivity problems for low-order linear recurrence sequences[END_REF], it is shown that if one can solve the positivity problem in general, then one can also approximate L(θ). That is, ▶ Theorem 6. [START_REF] Ouaknine | Positivity problems for low-order linear recurrence sequences[END_REF] Positivity for LRS of order 6 is T -Diophantine hard.

Robust Skolem and Robust Positivity

Both Skolem and Positivity consider a single initial configuration c. In this article, we investigate the notion of robustness, that is, whether the property is true in a neighborhood of c, which is important for real systems, where setting c with an arbitrary precision is not possible. We will consider two variants. The first one fixes the neighborhood as a ball B ψ of radius ψ > 0 around an initial configuration c, while the second one asks for the existence of an ψ > 0 such that for every initial configuration in B ψ , the respective condition is satisfied.

▶ Definition 7 (Robustness for Skolem and Positivity).

Let (u n ) n∈N be a linear recurrence relation (specified by the coefficient a ∈ Q κ ), and c ∈ Q κ an initial configuration. Given ψ > 0, the robust Skolem (resp. robust positivity) problem is to determine if for all c ′ with ||c ′ -c|| < ψ (open balls), or ||c ′ -c|| ≤ ψ (closed balls), we have u n (c ′ ) ̸ = 0 (resp. u n (c ′ ) ≥ 0) for all n ∈ N. The ∃-robust Skolem (resp. ∃-robust positivity) problem is to determine if there exists ψ > 0 such that for all ||c ′ -c|| < ψ we have u n (c ′ ) ̸ = 0 (resp. u n (c ′ ) ≥ 0) for all n ∈ N.
Notice that we do not consider explicitly the case of closed balls for ∃-robust Skolem (resp. positivity), because there exists an open ball of radius ψ > 0 for which robust Skolem (resp. positivity) holds iff there exists a closed ball of radius ψ ′ > 0 (e.g. ψ ′ = ψ

2 ) for which it holds. Our main results investigate the decidability and complexity of these problems.

▶ Theorem 8. Robust Skolem and robust positivity are T -Diophantine hard, even restricted to recurrence relations of order 6 for open or closed balls of rational radius ψ.

S TA C S 2 0 2 2 51:6

On Robustness for the Skolem and positivity problems

Our first result means that uninitialized positivity really needs the initial configuration to take a value possibly anywhere in the space rather than in a fixed neighborhood to obtain decidability via [START_REF] Tiwari | Termination of linear programs[END_REF][START_REF] Braverman | Termination of integer linear programs[END_REF]. We remark that Diophantine-hardness is known for the non-robust variant of positivity [START_REF] Ouaknine | Positivity problems for low-order linear recurrence sequences[END_REF], but to the best of our knowledge, it was not known for any variant of the Skolem problem.

Surprisingly, by relaxing the neighborhood to be as small as desired, one obtains decidability in full generality, as stated by our second main result: ▶ Theorem 9. ∃-robust Skolem and ∃-robust positivity are decidable in PSPACE.

The main difference between our techniques and several past works (except [START_REF] Akshay | On regularity of unary probabilistic automata[END_REF] which is restricted to eigenvalues being roots of unity) is as follows: given an LRR (u n ) n∈N , our intuition and proofs hinge on representing the set P of initial configurations d from which positivity holds. Formally:

P = {d ∈ R k | u n (d) ≥ 0 for all n ∈ N}.
We may note that the set P is convex. To see this, observe that for d, d ′ ∈ P , for all α, β > 0 with α + β = 1, we have αd

+ βd ′ ∈ P as u n (αd + βd ′ ) = αu n (d) + βu n (d ′ ) ≥ 0 for all n.
We also remark that a definition similar to P is possible for the set S of initial configurations from which 0 is avoided. But it turns out that that set is much harder to represent (e.g., it is not convex in general). Using P surprisingly suffices to deal with robust Skolem as well.

In Section 4, we provide the geometric intuitions behind our ideas as well as set up the notations for the proofs of the above theorems. We exploit the geometric intuitions from Section 4 in Section 5, to prove Theorem 8 and in Section 6, to prove Theorem 9.

Geometrical representation of an LRR for Diophantine-hardness

We will show that, as for the non-robust variant, hardness starts at order 6. Hence, in this section and the next, we will focus on a particular LRR of order κ = 6, sufficient for the proof of hardness, i.e. Theorem 8. In Section 6, we will generalize some of the constructions explored here to obtain decidability of ∃-robust Skolem. Let θ ∈ T , i.e. e i2πθ = p + qi ∈ A, with both p, q rational and p 2 + q 2 = 1. We want to approximate L(θ) (indeed this is the problem that is "Diophantine-hard"). Consider the Linear Recurrence Relation of order 6 defined by a = (-1, 4p + 2, -(4p 2 + 8p + 3), 8p 2 + 8p + 4, -(4p 2 + 8p + 2), 4p + 2). The roots of the characteristic polynomial are 1, e i2πθ , e -i2πθ , each with multiplicity 2, and all dominant (they have the same modulus 1). Example 3 is a particular case of this a, with p = 1 2 = cos( π 3 ). However, notice that θ

= 1 3 / ∈ T as it corresponds to q = sin( π 3 ) = √ 3 2 / ∈ Q. Now, since u n (c
) is a real number for any n and real initial configuration c, we can write the exponential polynomial solution in the form:

un(c) = z dom (c)n-x dom (c)n cos(2πnθ)-y dom (c)n sin(2πnθ)+zres(c)-xres(c) cos(2πnθ)-yres(c) sin(2πnθ)
The coefficients z dom (c), x dom (c), y dom (c) and z res (c), x res (c), y res (c) are associated with the initial configuration c of the LRS. In the following, we reason in the basis of vectors --→ z dom , ---→

x dom , --→ y dom , --→ z res , --→ x res , --→ y res , as the geometrical interpretation is simpler in this basis. We will eventually get back to the original coordinate vector basis at the end of the process. From e.g., [START_REF] Halava | Skolem's problem -on the border between decidability and undecidability[END_REF]Section 2], we know that we can transform from one basis to the other using an invertible Matrix C with C • c = (z dom (c), x dom (c), y dom (c), z res (c), x res (c), y res (c)).

We study the positivity of u n by studying the positivity of v n = un n , for all n ≥ 1. We denote v dom n (z dom , x dom , y dom ) = z dom -x dom cos(2πnθ) -y dom sin(2πnθ), which we call the dominant part of v n , while we denote v res n (z res , x res , y res ) = 1 n (z res -x res cos(2πnθ)y res sin(2πnθ)), which we call the residual part of v n . The residual part tends towards 0 when n tends towards infinity because of the coefficient 1 n .

High-Level intuition and Geometrical Interpretation

We provide a geometrical interpretation of set P . We cannot characterize it exactly, even in this particular LRR of order κ = 6 (else we could decide positivity for this case which is known to be Diophantine hard). To describe P , we define its "section" over (z dom , x dom , y dom ) given (z res , x res , y res ):

P (zres,xres,yres) = {(z dom , x dom , y dom ) | v n (z dom , x dom , y dom , z res , x res , y res ) ≥ 0 for all n}
It suffices to characterize P (zres,xres,yres) for all (z res , x res , y res ) in order to characterize P , as P = {(z dom , x dom , y dom , z res , x res , y res ) | (z dom , x dom , y dom ) ∈ P (zres,xres,yres) }. Among these sets, one is particularly interesting: P (0,0,0) , as it is the set of tuples (z dom , x dom , y dom ) such that v dom n (z dom , x dom , y dom ) ≥ 0 for all n ∈ N. Our reason for focussing on this representation of P is three-fold. First, unlike P , the set P (0,0,0) can be characterized exactly, as a cone depicted in Figure 1 (this will be formally shown in Lemma 10 below). Second, the set P (zres,xres,yres) is in 3 dimensions that we can represent more intuitively than a 6 dimensional set. Last but not least, we can show that P (zres,xres,yres) ⊆ P (0,0,0) for all (z res , x res , y res ) (Lemma 12).

On the other hand, we also consider a related set in 6 dimensions:

P dom = {(z dom , x dom , y dom , z res , x res , y res ) | ∀n, v dom n (z dom , x dom , y dom )) ≥ 0},
We note that P (0,0,0) is the projection of P dom over the 3 dimensions (z dom , x dom , y dom ). Also, characterizing P (0,0,0) is sufficient to characterize P dom as (z dom , x dom , y dom , z res , x res , y res ) ∈ P dom iff (z dom , x dom , y dom ) ∈ P (0,0,0) . As P (zres,xres,yres) ⊆ P (0,0,0) for all (z res , x res , y res ), we have P ⊆ P dom .

We are now ready to represent P (zres,xres,yres) given some value (z res , x res , y res ). We can interpret P (zres,xres,yres) in terms of half spaces:

P (zres,xres,yres) = ∞ m=1 H + m (
H m (z res , x res , y res ) = {(z dom , x dom , y dom ) | v m (z dom , x dom , y dom , z res , x res , y res )) = 0}
which is a vector space (cos(2πmθ) and sin(2πmθ) are constant when m is fixed). Consider the case of (z res , x res , y res ) = (0, 0, 0). We denote H + m = H + m (0, 0, 0) and

H m = H m (0, 0, 0) for all m. For instance, H 0 = {(z dom , x dom , y dom ) | z dom = x dom }, as v dom 0 (z dom , x dom , y dom ) = z dom -x dom .
Let M dom be the matrix associated with LRS (v dom n

) n∈N . We have H m = M dom H m-1 = M m dom H 0 .
We characterize M dom in Lemma 11 as a rotation around --→ z dom of angle -2πθ, which allows to characterize H m as the hyperplane which is the rotation of H 0 of angle 2mπθ around --→ z dom . That is, the cone shape for P (0,0,0) is obtained by cutting away chunk of the 3D space delimited by hyperplanes (H m ), the rotation 2nπθ being dense in [-π, π].

Coming back to some value (z res , x res , y res ) ̸ = (0, 0, 0), we have that the hyperplane H n (z res , x res , y res ) is parallel to the hyperplane H n (which is tangent to the cone P (0,0,0) ), because for H n of the form uz dom +vx dom +wy dom = 0, we have H n (z res , x res , y res ) is defined by {(z dom , x dom , y dom ) | uz dom +vx dom +wy dom = C}, for C = zres+xres cos(2πnθ)+yres sin(2πnθ) n a constant as n is fixed.

Thus, with this idea in mind, we can visualize P (zres,xres,yres) as depicted in Figure 2, using P (0,0,0) and the hyperplanes H n (z res , x res , y res ) parallel to H n , with an explicit bound on the distance from H n (z res , x res , y res ) to H n , which further tends towards 0 as n tends towards infinity. Next, we formalize the above intuition/picture into lemmas. We now formalize some of the ideas in the above subsection. First, we start with Lemma 10 which shows that P (0,0,0) describes a cone, as displayed on Figure 1.

▶ Lemma 10. P (0,0,0) = {(z dom , x dom , y dom ) | z dom ≥ x 2 dom + y 2 dom }.
Proof. We have cos(2πnθ) 2 + sin(2πnθ) 2 = 1 and cos(2πnθ) is dense in [-1, 1] as θ / ∈ Q. Denote X = cos(2πnθ), and study the function

f (X) = x dom X + y dom √ 1 -X 2 . Its derivative is f ′ (X) = x dom -y dom X √ 1-X √ 1+X . We have f ′ (X) = 0 iff X = X 0 = x dom √ x 2 dom +y 2 dom
. This gives a maximum for f (X 0 ) = ) n∈N is actually a rotation of angle -2πθ.

▶ Lemma 11. M dom (z dom , x dom , y dom ) = (z dom , x dom cos(2πθ)+y dom sin(2πθ), y dom cos(2πθ)x dom sin(2πθ)), that is M dom is a rotation around axis -→ z of angle -2πθ.

Finally, the following lemma implies that P ⊆ P dom .

▶ Lemma 12. For all z res , x res , y res , we have P (zres,xres,yres) ⊆ P (0,0,0) .

Proof. We use the following simple but important observation. Let (u n ) n∈N be an LRS where all roots have modulus 1, i.e., each root is of the form γ = e iθ , with distinct values of θ. Let u j be the j th element of the LRS, with j ∈ N. Then for all ε, N , there exists n > N with |u n -u j | < ε. That is, for each value visited, the LRS will visit arbitrarily close values an infinite number of times. This is the case in particular of v dom n . Now, assume for contradiction that there is a configuration (z dom , x dom , y dom ) in P (zres,xres,yres) \ P (0,0,0) . Since (z dom , x dom , y dom ) / ∈ P (0,0,0) , there exists m with v dom m (z dom , x dom , y dom ) < 0. We let ε =

|v dom m (z dom ,x dom ,y dom )| 3
and N such that for all n > N , |v res n | < ε (because it converges towards 0 when n tends towards infinity). From the above observation, we obtain

an n > N such that |v dom n (z dom , x dom , y dom ) -v dom m (z dom , x dom , y dom )| < ε. Thus: v n (z dom , x dom , y dom , z res , x res , y res ) < v dom n (z dom , x dom , y dom ) + v res n (z res , x res , y res ) < v dom m (z dom , x dom , y dom ) + ε + ε < 0 A contradiction with (z res , x dom , y dom ) ∈ P (zres,xres,yres) . ◀ 5
Proof of Theorem 8

Intuition for hardness of (robust) positivity

Consider a vector d = (z dom , x dom , y dom , z res , x res , y res ) on the surface of P dom , that is, (z dom , x dom , y dom ) ∈ P (0,0,0) . Consider the subset of P (0,0,0) which consists of points whose first coordinate z dom is the same as that of d. For all n, let e n be the point of this section where hyperplane H n is tangent to P (0,0,0) . Let τ be the angle made between the center b of the section, e 0 and d. Hence, e 0 is at angle 0 and e n at angle 2πnθ mod 2π. We depict this pictorially in Figure 3.

We have that u n (d) ≥ 0 for all n iff d is in the intersection of all half spaces defined by H i (z res , x res , y res ). As 2πnθ mod 2π is dense in [0, 2π), for all β > 0, there is a n such that e n is at angle α n ∈ [τ -β, τ + β], hence H n will be ε-close to d. To know whether d is in the half space defined by H n (z res , x res , y res ), we need to compare the distance ε between H n and d, with the value of n. If the value of n is too large, then the distance between H n (z res , x res , y res ) and H n is smaller than ε, and d is in the half space H + n (z res , x res , y res ). In other words, for (u n (d)) n∈N not to be positive, n needs to be both small enough and such that 2πnθ mod 2π is close to τ . This is similar to L(θ) being small, as shown in Lemma 13. Now, for robust positivity (Theorem 8), we consider a ball B entirely in P dom , tangent to the surface of P dom only on point d. The ball will be positive iff the curvature of the ball is steeper than the curvature from hyperplanes H n (z res , x res , y res ) n∈N around d, as shown in Lemma 14. This will correspond again to computing L(θ), thus showing hardness.

Formalizing the proof for closed balls and robust positivity

In this section, we formalize the intuition given above, in the case of a closed ball and for robust positivity. We will extend this to the full proof of Theorem 8 in the next subsection.

We start by picking

L(θ) = inf(c ∈ R | |θ -k n | ≤ c n 2 , k, n ∈ N \ {0}), i.e., L(θ) = inf(c ∈ R | |2πnθ -2πk| ≤ 2πc n , k, n ∈ N \ {0}). Denoting L + (θ) = inf(c ∈ R | 2πnθ mod 2π ≤ 2πc n , n ∈ N) and L -(θ) = inf(c ∈ R | | -2πnθ mod 2π| ≤ 2πc n , n ∈ N), we get L(θ) = min(L + (θ), L -(θ)).
We show how to ε-approximate L + (θ) in the following, using an oracle for robust positivity, following ideas in [START_REF] Ouaknine | Positivity problems for low-order linear recurrence sequences[END_REF]. To compute some ℓ that is ε-close to L + (θ) for a given ε > 0, we perform a binary search on ℓ. An old observation of Dirichlet shows that every real number has Diophantine approximation type at most 1. Further, L(θ) ≥ 0 by definition. So, for the binary search, we start with a lower bound ℓ min = 0 and an upper bound ℓ max = 1. For ℓ := ℓmin+ℓmax 2 , we want to know if ℓ ≥ L + (θ) -ε (and then we set ℓ min := ℓ) or whether ℓ ≤ L + (θ) + ε (and then we set ℓ max := ℓ). Approximating L -(θ) is done in a symmetric way, and L(θ) can be approximated accordingly.

For an interval I of N, we denote

L + I (θ) = inf(c ∈ R | 2πnθ mod 2π ≤ 2πc n , n ∈ I).
For instance, we have L + N (θ) = L + (θ). We will denote > n 1 for the interval I = {n 1 +1, n 1 +2, . . .}. Let ε > 0 and ℓ be a guess to check against L + (θ). Consider the closed ball B ℓ ψ of radius √ 2ψ, centered at c = (2 + ψ, 2 -ψ, 0, 0, 0, 2πℓ), with ψ < 1 3 and ψ < πℓ. Notice that d = (2, 2, 0, 0, 0, 2πℓ) ∈ B ℓ ψ , on its surface, as ||c -d|| = √ 2ψ. The ball B ℓ ψ is entirely in P dom (see Lemma 20 in Appendix 8.3, which is not necessary for the rest of the proofs, it is a sanity check because of Lemma 12). Further, the surface of the ball is tangent to the surface of P dom in d as 2 2 = 4 = (2 + 0) 2 satisfies the equation of Lemma 10. In other words, this the only point where the ball B ℓ ψ intersects the surface of P dom . We first explain the relationship between the positivity of (u n (d)) and L(θ), which is the crux of the proof of Theorem 6 by [START_REF] Ouaknine | Positivity problems for low-order linear recurrence sequences[END_REF]. ▶ Lemma 13. There is a computable n 1 > 0 such that for all n 2 ≥ n 1 , we have

(u n (d)) n>n2 positive implies L + >n2 (θ) > ℓ -ε and (u n (d)) n>n2 not positive implies L + >n2 (θ) < ℓ + ε.
Proof. Let α n = 2πnθ mod 2π ≥ 0. Considering the Taylor development for α n > 0 close to 0 of (1 -cos(α n )) and sin(α n ), we get

u n (d) = 2 2 α 2 n -2πℓαn n + f (α n ), with f (α n ) = O(α 3 n ). We have u n (d) ≤ 0 iff 2πℓαn n is larger than α 2 n (1 + f (αn) α 2 n ), that is iff α n ≤ 2πℓ n(1+ f (αn ) α 2 n ) .
There exists a value α 0 > 0 such that α n < α 0 implies 1 ). The diameter of the C dom circle is 2 + ψ + z ′ dom . By Lemma 10 and the description of H n (z res , x res , y res ) as parallel to H n , characterized by Lemma 11, and at a distance from H n which we can effectively bound for all n ∈ N, we obtain that if r is smaller than

-ε ℓ ≤ 1 (1+ f (αn ) α 2 n ) ≤ 1 + ε ℓ . That is, if u n (d) ≤ 0 and α n < α 0 , then L + (θ) ≤ ℓ + ε. Let n 0 = ⌊ πℓ 1-cos(α0) ⌋ + 1. As | sin(α)| ≤ 1, if α n > α 0 , then for all n > n 0 , u n (d) > 2(1 -cos(α 0 )) -2πℓ 1-cos(α0) πℓ = 0 is positive. We define n 1 = max(n 0 , ⌊ 2π(ℓ-ε) α0 ⌋ + 1). That is, if u n (d) ≤ 0 with n > n 1 ,
2 + ψ ± √ 2 1 -λ 2 2 λ 1 ψ -α(sin α + ψ √ 2-2λ 2 1 2πℓ
), then e is in P (zres,xres,2πℓ+y ′ res ) . That is, we want 2+ψ±

√ 2 1 -λ 2 2 λ 1 ψ-α(sin α+ ψ √ 2-2λ 2 1 2πℓ )-r = ψ(2± √ 2 1 -λ 2 2 λ 1 - √ 2 cos β|λ 2 |λ 1 )-α √ 2-2λ 2 1 2πℓ ))+O(α 2 ) > 0. Now remark that | √ 2 1 -λ 2 2 λ 1 ψ+ √ 2 cos β|λ 2 |λ 1 | ≤ λ 1 ( 2 + 2 cos 2 β). And also |λ 1 ( 2 + 2 cos 2 β) + α ψ √ 2-2λ 2 1 2πℓ )| ≤ 2 + 2 cos 2 β + α 2 ψ 2
πℓ , applying twice the same reasoning as in the proof of Lemma 15.

We now prove that we have ψ(1 -cos 2 β) = ψ sin 2 β dominates any O(α 2 ) for ψ small, i.e., we prove that for any f = O(α 2 ), we have f ψ(sin 2 β) tends to 0 as ψ tends to 0. In particular, for all ψ small enough, the fraction is below 1, i.e., (sin 2 β)ψ > f . We have [START_REF] Manindra Agrawal | Approximate verification of the symbolic dynamics of Markov chains[END_REF][START_REF] Akshay | Complexity of restricted variants of skolem and related problems[END_REF]. This indeed dominates any function O(α 2 ), as

(sin 2 β)ψ ≥ r 2 sin 2 (α) ψ ≥ sin 2 (α) ψ as r ∈
α sin α is bounded in [-π 2 , π 2 ]. In particular, sin 2 β > α 2 ψ 2 2πℓ
) for ψ small enough. Now, we write 2 + 2 cos

2 β + α 2 ψ 2 πℓ = 2 1 -1 2 (sin 2 β -α 2 ψ 2 2πℓ ) ≤ 2(1 -1 4 (sin 2 β - 1 4 α 2 ψ 2 2πℓ
)) using the Taylor development of √ 1 -r, and the fact that (sin 2 β -α 2 ψ 2 2πℓ ) > 0 because ψ is small enough. Thus, we obtain ψ( 2

-2(1-1 4 (sin 2 β))+O(α 2 ) = ψ 4 (sin 2 β)+O(α 2
), which is positive for ψ small enough, and e is in P (zres,xres,2πℓ+y ′ res ) . Notice that the function in O(α 2 ) is well defined and well known, and thus Ψ small enough can be effectively computed. ◀

Let us explain why these two Lemmas suffice, provided that we have an oracle for ψ-robust positivity, to answer either L + (θ) ≤ ℓ + ε or L + (θ) ≥ ℓ -ε, which proves Theorem 8 for robust positivity and closed balls. Intuitively, if the ball B ℓ ψ is positive, then in particular (u n (d)) is positive since d ∈ B ℓ ψ and we have L + >n1 (θ) > ℓ -ε by Lemma 13. Otherwise, the ball is not positive and Lemma 14 shows that L + (θ) < ℓ + ε, granted that the radius of the ball is small enough.

Proof of Theorem 8 for robust positivity and closed balls. Let ε > 0. Assume that an ℓ has been fixed, such that we want to know either L + (θ) < ℓ + ε or L + (θ) > ℓ -ε. First, we fix ψ given by Lemma 14. We remark that B ℓ ψ corresponds to a ball in the coordinates (z dom , x dom , y dom , z res , x res , y res ) (which are not necessarily orthonormal), not in the original coordinates (v 0 , v 1 , v 2 , v 3 , v 4 , v 5 ). Taking the transformation from the latter to the former, which is a linear operator H, the ball B ℓ ψ corresponds to an ovaloid O in the original coordinates. We can explicitly define a ball B ′ ⊆ O in the original coordinates, with d ∈ B ′ . Notice that we can choose B ′ with an arbitrarily small radius, so in particular we can choose this radius to be rational without loss of generality.

We first compute L + ≤n1 (θ), which is easy as it only involves a bounded number of indices n. If L + ≤n1 (θ) < ℓ + ε, then we know L + (θ) ≤ L + ≤n1 (θ) < ℓ + ε and we stop. Otherwise L + ≤n1 (θ) ≥ ℓ + ε, and we check whether u n (d ′ ) ≥ 0 for all n > n 1 and all d ′ ∈ B ′ , using the robust positivity oracle (by starting from M n1 (v 0 , . . . , v k ) rather than (v 0 , . . . , v k )). If it is positive, then in particular it is for d ′ = d, and applying Lemma 13, we obtain

L + >n1 (θ) > ℓ -ε. Combined with L + ≤n1 (θ) ≥ ℓ + ε, we obtain L + (θ) > ℓ -ε. The last case means that there is u n (d ′ ) < 0 for some n > n 1 and d ∈ B ′ ⊆ B ℓ ψ .
Applying the contrapositive of Lemma 14, we obtain that L + (θ) < ℓ + ε. ◀

Case of Open Balls and robust Skolem

In this subsection, we extend the proof of Theorem 8 to show that considering open or closed balls does not make a difference for the Diophantine-hardness. Further, there is also no difference whether we consider the robust Skolem problem (0 is avoided), the robust positivity problem (negative numbers are avoided), or the robust strict positivity problem (negative and 0 are avoided).

Let B be an open ball and cl(B) its topological closure, which is the closed ball consisting of B and its surface. Consider the following statements: We show that equivalence results between these statements. This allows us to conclude that having open or closed balls does not make a difference for T -Diophantine hardness of Skolem and (strict) positivity. Formally, we have the following.

▶ Lemma 15. (1), ( 2) and ( 3) are equivalent. Further, for balls B containing at least one initial configuration d 0 in its interior that is strictly positive, i.e. u n (d 0 ) > 0 for all n, both (3) and ( 4) are equivalent and ( 5) and ( 6 (3) implies ( 4) is trivial. ( 4) implies (3): We consider the contrapositive: if we have an initial configuration d 1 of B which is not strictly positive, then u n (d 1 ) ≤ 0 for some n, and there is a barycenter d 2 between d 0 , d 1 which satisfies u n (d 2 ) = 0, i.e. negation of (4). To be more precise, we can choose d 2 = -un(d1) un(d1)-un(c) d 0 + un(d1) un(d1)-un(d0) d 1 . Now, ( 5) and ( 6) are equivalent for balls containing at least one initial configuration d 0 that is strictly positive in its interior (same proof as for the equivalence between (3) and (4) above). However, notice that [START_REF] Akshay | Distribution-based objectives for Markov Decision Processes[END_REF][START_REF] Baier | Reachability in dynamical systems with rounding[END_REF] are not equivalent with [START_REF] Manindra Agrawal | Approximate verification of the symbolic dynamics of Markov chains[END_REF][START_REF] Akshay | Near-Optimal Complexity Bounds for Fragments of the Skolem Problem[END_REF][START_REF] Akshay | Complexity of restricted variants of skolem and related problems[END_REF][START_REF] Akshay | On regularity of unary probabilistic automata[END_REF] in general. ◀

We are now ready to prove Theorem 8 for open balls B. It suffices to remark that the center c of B ℓ ψ is strictly in the interior of P dom , and thus it will be eventually strictly positive by Lemma 10, that is there exists n 2 > n 1 such that u n (c) > 0 for all n > n 2 , and we can choose d 0 = c. Hence by Lemma 15, robustness (for n > max(n 1 , n 2 )) of positivity, strict positivity and Skolem are equivalent on B, and these are equivalent with robust positivity of cl(B) which was proved T -Diophantine hard in the previous section.

S TA C S 2 0 2 2

It remains to prove Theorem 8 for robust Skolem for closed balls B. For that, it suffices to easily adapt Lemma 13, replacing (u n (d)) n>n2 positive by strictly positive, and obtain the T -Diophantine hardness for robust strict positivity of closed balls. We again apply Lemma 15 (( 5) and ( 6) are equivalent) to obtain hardness for robust Skolem of closed balls.

6

Proof of Theorem 9

We now turn to the proof of Theorem 9, generalizing elements from Section 4.

Intuitions for the proof of Theorem 9

Let (u n ) n∈N be a recurrence relation defined by coefficients a ∈ Q κ . As before, we will consider (v n ) n∈N = ( un fn ) n∈N , for f n such that the dominant coefficients of (v n ) n∈N are of the form αe inθ . We will then decompose the exponential solution of (v n ) n∈N as a dominant term (v dom n ) n∈N made of coefficients αe inθ , and a residue (v res n ) n∈N with (v res n ) n∈N -→ n→+∞ 0. For an initial distribution a, we denote by a dom its projection on dominant space. As before, we define P dom = {a | ∀n, v dom n (a dom ) ≥ 0}. To solve ∃-robust Skolem and ∃-robust positivity, the reasoning is based on the range of the dominant term. For ∃-robust Skolem, we consider the minimum absolute value ν of the dominant term |v dom n (c 0 )| obtained for the center of the neighborhood c 0 . ν > 0. Then as the residue has negligible contribution to (v n ) n∈N for large n, we show that the LRS will ultimately avoid zero beyond a threshold index n thr . Having assured ourselves of the long run behaviour, it suffices to check the value of the LRS up to n thr , where the residue can have significant contribution, to see whether the LRS satisfies robust Skolem. ν = 0. Then we show in Proposition 18 that the LRS does not satisfy robust Skolem: no matter how small we pick a neighbourhood around c 0 , there will always exist a c in that neighbourhood that hits zero at some iteration. Further, Proposition 17 states that ν can be computed effectively. For robust positivity, we let µ be the minimum value of the dominant term (and not of its absolute value). Thus, µ can take three kinds of values: µ > 0 (c 0 ∈ P dom ) and we proceed as for ν > 0; µ < 0 (c 0 / ∈ P dom ) and then there exists a n such that the LRS from c 0 is negative; and µ = 0 (c 0 is at the surface of P dom ), and then we can show that there exists a configuration arbitrarily close to c such that the LRS from that configuration is negative.

Range of the Dominant Term

We first define the normalized exponential polynomial solution (v n ) n∈N :

▶ Definition 16. Let (u n ) n∈N be an LRS of general term u n (c) = r i=1 mr-1 j=0 p ij n j γ n
i , with ρ being the modulus of the dominant roots and m + 1 the maximal multiplicity of a dominant root. Define v n (c) = un (c) n m ρ n for n > 0, and v 0 (c) = u 0 (c). We call every term of v n which converges towards 0 as n tends towards infinity residual, while the other terms, of the form αe iθ are dominant. We denote {θ j | j = 1, . . . , k} the set of θ in dominant terms, and α j (c) the associated coefficient. We define:

v dom n (c) = α j (c)e inθj and v res n (c) = v n (c) -v dom n (c) = O( 1 n ) → n→∞ 0
As we explained in Section 6.1, knowing the range of (v dom n ) n∈N is crucial in order to solve ∃-robust Skolem and positivity. In Section 4 and 5, we dealt with hardness via an example

(c 0 )| ≤ µ 2 as v res n (c 0 ) → n→∞ 0. Thus v n (c 0 ) = v dom n (c 0 )+v res n (c 0 ) < µ 2 .
That is, c ε = c 0 satisfies the statement. Otherwise, µ = 0. We prove that for all α > 0, we have a n α such that |v nα (c 0 )| ≤ α, which suffices by Lemma 19. Let α > 0 arbitrarily small, and let N such that for all n > N , |v res n (c 0 )| ≤ α 2 . This N exists as v res n (c 0 ) → n→∞ 0. By Kronecker, as µ = 0, there exists

n α > N with |v dom nα (c 0 )| < α 2 . Thus |v nα (c 0 )| ≤ |v dom nα (c 0 )| + |v res nα (c 0 )| ≤ α.
We now prove the second statement in the same way. Assume ν = 0, and let ε > 0. We again prove that for all α > 0, we have a n α such that |v nα (c 0 )| ≤ α, which suffices by Lemma 19. Let α > 0 arbitrarily small, and let N such that for all n > N , |v res n (c 0 )| ≤ α 2 . This N exists as v res n (c 0 ) → n→∞ 0. By Kronecker, as ν = 0, there exists n α > N with

|v dom nα (c 0 )| < α 2 . Thus |v nα (c 0 )| ≤ |v dom nα (c 0 )| + |v res nα (c 0 )| ≤ α. ◀

Decidability and complexity for ∃-robust Skolem and ∃-robust positivity

We now turn to deciding ∃-robust Skolem and positivity as stated in Theorem 9, using Proposition 18. The algorithm for ∃-robust Skolem is as follows (as detailed in Algorithm 1 in Appendix 8.4). First, we compute ν ← min t∈T |dominant(c, t)| using Proposition 17, for c the initial configuration around which we are looking for a neighborhood. If ν = 0, then ∃-robust Skolem does not hold. Otherwise, we compute N such that v res n (c 0 ) < ν 2 for all n > N . Then we check if v n (c 0 ) = 0 for some n ≤ N . If yes, then ∃-robust Skolem does not hold, otherwise it holds. This algorithm can readily be adapted to provide an ε > 0 such that for all c with |c -c 0 | ≤ ε, we have u c ̸ = 0, as well as to decide robust positivity.

The correctness of the above algorithm follows from Proposition 18, because if ν > 0, then for all n > N , v n (c 0 ) > ν -ν 2 ≥ ν 2 > 0, and this remains > 0 in a neighborhood of c 0 . Denoting ν ′ (c) = min n≤N |v n (c)|, if ν ′ (c 0 ) > 0, then also ν ′ (c) for c in a neighborhood of c 0 .

We now argue about the complexity. Both µ and 1/µ = 2 s O(1) are bounded (Proposition 17). We thus have n thr = 2 s O(1) because v res n (c 0 ) = O( 1 n ). This is the number of iterates we have to explicitly check, which gives the PSPACE complexity. This finally completes the proof of Theorem 9.

Conclusion

We have formulated a natural notion of robustness for the Skolem and positivity problems and shown several results: for a given neighborhood around an initial configuration c 0 , we show Diophantine-hardness for both problems. Interestingly, this is the first Diophantine-hardness result for a variant of Skolem as far as we know. This implies that for uninitialized positivity, the fact that the initial configuration c 0 is arbitrary is crucial to decidability [START_REF] Tiwari | Termination of linear programs[END_REF][START_REF] Braverman | Termination of integer linear programs[END_REF], as having a fixed ball around c 0 is not sufficient. On the other hand, we proved decidability of ∃-robust Skolem/Positivity around an initial configuration in full generality, hence this problem is simpler. It is also more practical because in a real system, it is often impossible to determine the initial configuration with absolute accuracy. Our results can provide a precision with which it is sufficient to set the initial configuration. Beyond these results, we provided geometrical reinterpretations of Skolem

Results and Proofs for Section 6

A deep result of Masser [START_REF] Masser | Linear relations on algebraic groups[END_REF] shows that integer multiplicative relationships between algebraic numbers can be elicited efficiently.

▶ Theorem 21 (Masser [19]). Let k, be fixed, and let e iθ1 , ..., e iθ k be complex algebraic numbers of unit modulus. Consider the free abelian group L under addition given by L = {(λ 1 , ..., λ k ) ∈ Z k : e iλ1θ1 ...e iλ k θ k = 1}. L has a basis {l 1 , ..., l p } ⊂ Z k with p ≤ k. The basis can be computed in time polynomial and each entry in the basis vector is polynomially bounded in size(e iθ1 ), ..., size(e iθ k ).

Kronecker theorem [START_REF] Bourbaki | Elements of Mathematics: General Topology (Part 2)[END_REF] states that each linear combination t of the basis given by Masser theorem can be approximated by a power s n of s = (e iθ1 , . . . , e iθ k ).

▶ Theorem 22 (Kronecker [START_REF] Bourbaki | Elements of Mathematics: General Topology (Part 2)[END_REF]). Let θ 1 , ..., θ k , ϕ 1 , ..., ϕ k ∈ [0, 2π). The following two statements are equivalent:

For any ϵ ′ > 0, there exist n, m 1 , ..., m k ∈ Z such that for 1 ≤ j ≤ k we have |nθ j -ϕ j -2m j π| ≤ ϵ ′ For every tuple (λ 1 , ...λ k ) of integers such that k j=1 λ j θ j ∈ 2πZ we have k j=1 λ j ϕ j ∈ 2πZ Finally, we provide the reasoning why constant C independent of n exists which bounds the distance, i.e., we prove Lemma 19.

S 1 Figure 1

 11 Figure 1Visual representation of the cone P (0,0,0) .

Figure 2

 2 Figure 2 Sections of P (0,0,0) (in black) and P (zres,xres,yres) (in dashed red), carved out by hyperplanes (Hi) (in black) and (Hi(zres, xres, yres)) (in red) respectively.

4. 2

 2 Characterization of P (0,0,0) and representing P (zres,xres,yres)

Figure 3

 3 Figure 3 Representation of a section of P (0,0,0) , with hyperplanes H0, H10 being represented.

, λ 3 Figure 4

 34 Figure 4 Representation of B in the section over ---→ x dom , --→ y dom at height ℓ = 2 + ψ + z ′ dom over --→ z dom .

1 . 2 . 3 . 4 . 5 . 6 .

 123456 Robust Positivity holds for the closed ball cl(B) Robust Positivity holds for the open ball B Robust Strict Positivity holds for the open ball B Robust Skolem holds for the open ball B Robust Strict Positivity holds for the closed ball cl(B) Robust Skolem holds for the closed ball cl(B)

  ) are equivalent. Proof. (1) implying (2) is trivial. (2) implies (1): we show the contrapositive. Suppose there exists an initial configuration d on the surface of the ball B and an integer n such that u n (d) = y < 0. Recall that M is the companion matrix, and u n (d) is the first component of (M n .d), so u n (x) is a continuous function. Thus, there exists a neighbourhood of d, such that for all d ′ in the neighbourhood, u n (d ′ ) < y/2 < 0. This neighbourhood intersects the open ball B enclosed by the surface, and picking d ′ in this intersection shows that Robust Positivity does not hold in the open ball. (3) implying (2) is trivial. (2) implies (3): Assume for the sake of contradiction that there is an initial configuration c ′ in the open ball B such that u n (c ′ ) = 0. Consider any open O around c ′ entirely in the open ball B. We have that c ′ is on hyperplane H n by definition. That is, there are initial configurations in O on both sides of H n . In particular, there is an initial configuration c ′′ in O, hence in B, with c ′′ / ∈ H + n , i.e. u n (c ′′ ) < 0, a contradiction with B being robustly positive.

▶ Lemma 19 .

 19 There exists C such that for all n, distance(c, Hn ) ≤ C • |v n (c)|. Proof. Let n ∈ N. We have distance(c, H n ) = |un(c)|||y|| for y the first row of M n by basic geometry. Let H be the transformation matrix between the basis of initial configurations and the basis of the exponential polynomial solution of (u n ) n∈N . Let x = (x 1 , . . . , x κ ) with x i = n k ρ n j so that to cover every root ρ j and multiplicities k = 1, . . . , m j . We haveu n (c) = y • c = x • (H • c)for all initial configurations c, i.e., y = x • H. That is, there exists a constant D > 0 depending upon H with ||y|| ≥ Dn m ρ n for ρ the modulus of a dominant root and m + 1 the highest multiplicity of a root of modulus ρ. We obtain distance(c, H n ) ≤ |un(c)| Dn m ρ n = |vn(c)| D . ◀ Finally, we provide Algorithm 1 for ∃-robust Skolem.

  z res , x res , y res ), with H + m (z res , x res , y res ) = {(z dom , x dom , y dom ) | v m (z dom , x dom , y dom , z res , x res , y res )) ≥ 0}. The half space H + m (z res , x res , y res ) is delimited by hyperplane

  On the other hand, if z dom < x 2 dom + y 2 dom , then there exists n such that f (cos(2πnθ)) is arbitrarily close to max f (X) > z dom , and in particular v n = z dom -f (cos(2πnθ)) < 0. ◀We show in Appendix 8.2 the following lemma which states the linear function M dom associated with the LRR (v dom n

	x 2 dom +y 2 dom √ x 2 dom +y 2

dom = x 2 dom + y 2 dom . Thus, for all (z dom , x dom , y dom ) with z dom ≥ x 2 dom + y 2 dom , we have z dom ≥ max(f (X)) and v n ((z dom , x dom , y dom , z res , x res , y res ) ≥ z dom -f (X) ≥ 0 for all n.

  then n > n 0 and α n < α 0 , and thus L + >n1 (θ) ≤ ℓ + ε. Otherwise, for all n > n 1 , we have u n (d) is positive and 2πnθ mod 2π > ℓ -ε. Thus we haveL + >n1 (θ) ≥ ℓ -ε. ◀The ball B ℓ ψ is chosen to have the following crucial Lemma to approximate L + (θ):▶ Lemma 14. If L + (θ) ≥ ℓ + ε,there exists an explicitly computable ψ such that u n (d ′ ) ≥ 0 for all n > n 1 and all d ′ ∈ B ℓ ψ , for the n 1 from Lemma 13. The proof of Lemma 14 uses Lemmas 10, 11 and the description of H n (z res , x res , y res ) as parallel and at a bounded distance to H n .

Proof. Let e = (2 + ψ + z ′ dom , 2 -ψ + x ′ dom ,

y dom , z res , x res , 2πℓ + y ′ res ) ∈ B ℓ ψ , and use the same notation λ 1 , λ 2

▶

  Lemma 19. There exists C such that for all n, distance(c, H n ) ≤ C • |v n (c)|. Lemma 19, proved in Appendix 8.4, implies that if for all α > 0, there exists n α with |v nα (c)| < α, then there exists n with distance(c, H n ) < ε (choose n = n α for α = ε 2C ). Proof of Proposition 18. Consider the first statement. If µ < 0, then there exists n with |v res n

  /positivity, shedding a new light on this hard open problem.Proof. Let d′ = (2 + ψ + z ′ dom , 2 -ψ + x ′ dom , y dom , z res , x res , 2πℓ + y ′ res ) ∈ B ℓ ψ \ {d}. We now show that d ′ is strictly in P dom , i.e. (2 + ψ + z ′ dom ) -(2 -ψ + x ′ dom ) 2 + y 2 dom > 0. We have z ′ dom 2 + x ′ dom 2 + y 2 dom ≤ 2ψ 2 , and we write z ′ dom 2 + x ′ dom 2 + y 2 dom = 2λ 2 1 ψ 2 , with λ 1 ∈ [0,[START_REF] Manindra Agrawal | Approximate verification of the symbolic dynamics of Markov chains[END_REF] and λ 1 = 1 iff (z res , x res , y ′ res ) = (0, 0, 0). We also write x ′ , with λ 3 ∈ [0, 1] and λ 3 = 1 iff y dom = 0. We writex ′ dom = √ 2λ 3 λ 2 λ 1 ψ and z ′ dom = ± √ 2 1 -λ 2 2 λ 1 ψ. That is, d is the configuration with λ 1 = λ 3 = 1 and λ 2 = -ψ)λ 3 λ 2 λ 1 ψ ≤ (2 -ψ) 2 + 2λ 2 2 λ 2 1 ψ 2 + 2 √ 2(2 -ψ)|λ 2 |λ 1 ψ = (2ψ + √ 2|λ 2 |λ 1 ψ) 2 , with equality iff λ 3 = 1, ie when y dom = 0. Given that ψ < 1 3 , we have 2 -ψ + √ 2|λ 2 |λ 1 ψ > 0. Thus (2 + ψ + z ′ dom ) -(2 -ψ -x ′ dom ) 2 + y 2 dom ≥ 2 + ψ ± √ 2 1 -λ 2 2 λ 1 ψ -(2 -ψ + √ 2|λ 2 |λ 1 ψ) = 2ψ -√ 2(|λ 2 | ± 1 -λ 2 2 )λ 1 ψ ≥ 2ψ -2λ 1 ψ ≥ 0 as (|λ 2 | ± 1 -λ 2 2 ) ≤ .That is, for all d ′ ∈ B ℓ ψ , d ′ ∈ P dom , and it is strictly inside whenever d ′ ̸ = d (one can check that λ 1 = λ 3 = 1 and λ 2 = -

	dom 3 λ 2 2 = 2λ 2 2 λ 2 2 + y 2 dom = 2λ 2 2 λ 2 1 ψ 2 1 ψ 2 √ 1 ψ. We write x ′ 2 )λ 2 2 = 2(1 -λ 2 dom 2 2 . dom ) 2 + y 2 dom 2 ∈ [0, 1], i.e. z ′ with λ 2 We have (2 -ψ + x ′ dom = (2 -ψ) 2 + x ′ 2 dom + y 2 dom + 2(2 -ψ)x ′ dom = (2 -ψ) 2 + 2λ 2 2 λ 2 1 ψ 2 + 2 √ 2(2 √ 2, √ 2 with equality iff λ 2 = ± 2 √ 2 2 does not yield the overall
	equality).	◀

Funding This work was partly supported by the DST/CEFIPRA/INRIA associated team EQuaVE, DST/SERB Matrices grant MTR/2018/00074, and ANR-20-CE25-0012 MAVeriQ.

51:15

which had 3 dominant roots, and it was rather simple to determine the min/max value (computed in the proof of Lemma 10). The general case is not so easy however, because there may be relationships between the θ j which may alter the range of (v dom n ) n∈N . A tedious but now rather classical way to compute the range of (v dom n ) n∈N is by invoking Masser's theorem [START_REF] Masser | Linear relations on algebraic groups[END_REF] (Theorem 21 in Appendix 8.4), to describe the set of tuples that can be reached (at least arbitrarily close) by s n = (e inθ1 , . . . , e inθ k ) for n ∈ N, as used in [START_REF] Ouaknine | On the positivity problem for simple linear recurrence sequences[END_REF]Theorem 4]. We can describe a continuous relaxation of {s n | n ∈ N} as a set T of tuples t = (t 1 , . . . , t k ) of complex numbers with |t j | = 1 for all j. The set T is the set of linear combinations of the finite basis given by Theorem 21, which describes a Torus, independent of the initial configuration c. Notice that T may be discrete and have finitely many points (the case where θj 2π ∈ Q), else, it is continuous and has uncountably many points. We have s n ∈ T for all n ∈ N. Further, Kronecker [START_REF] Bourbaki | Elements of Mathematics: General Topology (Part 2)[END_REF] (Theorem 22 in Appendix 8.4) implies that for all t = (t 1 , . . . , t k ) ∈ T and ε > 0, there exists an n such that |t j -e inθj | ≤ ε for all j ≤ k. For every initial configuration c and element of the torus t ∈ T , we denote dominant(c, t) = j α j (c)t j . Thus, for all n and all c, we have

Conversely, for all t ∈ T, ε > 0, there exists n with |v dom n (c) -dominant(c, t)| ≤ ε, for all c. Using Renegar's result [START_REF] Renegar | On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part I: Introduction. Preliminaries. The Geometry of Semi-Algebraic Sets. The Decision Problem for the Existential Theory of the Reals[END_REF], one can compute effectively the range of dominant(c, t) over T , and thus of (v dom n ) n∈N . A simple adaptation allows to compute the range of |dominant(c, t)|.

In the following, we fix c 0 to be the center of the neighborhood and define

Proof. The statement for µ comes directly from Renegar [START_REF] Renegar | On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part I: Introduction. Preliminaries. The Geometry of Semi-Algebraic Sets. The Decision Problem for the Existential Theory of the Reals[END_REF], stating that we can compute the min and max values µ = min t∈T (dominant(c 0 , t)) and µ ′ = max t∈T (dominant(c 0 , t)) over t in the torus T . The statement for ν is a corollary obtained as follows:

If µ > 0 (u n (c 0 ) ≥ µ > 0 for all n ∈ N), then ν = µ and we are done.

If T is discrete, we enumerate the polynomially many values of t (noting that they all correspond to λ th roots of unity, and Masser polynomially bounds λ) to compute ν as the minimum of the absolute values. Otherwise, we have µ < 0 < µ ′ , that is there exist two elements t, t ′ ∈ T with dominant(c 0 , t) < 0 < dominant(c 0 , t ′ ). As x → dominant(c 0 , x) is continuous over T , there is a t ′′ ∈ T with dominant(c 0 , t ′′ ) = 0, that is ν = 0. ◀

We now state that if µ ≤ 0, then ∃-robust positivity does not hold, while if ν = 0, then ∃-robust Skolem does not hold.

To prove Proposition 18, we reason as follows. For every n, let distance(c, H n ) be the distance between an initial configuration c and the hyperplane

as there will be initial configurations in the ε neighborhood of c 0 on both sides of H n , thus some will be outside of

Regarding algebraic numbers and their bit representation

A complex number α is said to be algebraic if it is a root of a polynomial with integer coefficients. For an algebraic number α, its defining polynomial p α is the unique polynomial of least degree of Z[X] such that the GCD of its coefficients is 1 and α is one of its roots. Given a polynomial p ∈ Z[X], we denote the length of its representation size(p), its height H(p) the maximum absolute value of the coefficients of p and d(p) the degree of p. When the context is clear, we will only use H and d.

A separation bound provided in [20] has established that for distinct roots α and

. This bound allows one to represent an algebraic number α as a 4-tuple (p, a, b, r) where α is the only root of p at distance ≤ r if a + ib, and we denote sizeα the size of this representation, i.e., number of bits needed to write down this 4-tuple.

Further, we note that two distinct algebraic numbers α and β, are always roots of p α p β , and we have that

Given a polynomial p ∈ Z[X], one can compute its roots in polynomial time wrt size(p) [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF]. Since algebraic numbers form a field, given α, β two algebraic numbers, one can always compute the representations of α + β, αβ, 1 α , Re(α), Im(α) in polynomial time wrt size(α) + size(β) [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF][START_REF] Cohen | A Course in Computational Algebraic Number Theory[END_REF].

Proofs for Section 4

▶ Lemma 11. M dom (z dom , x dom , y dom ) = (z dom , x dom cos(2πθ)+y dom sin(2πθ), y dom cos(2πθ)x dom sin(2πθ)), that is M dom is a rotation around axis -→ z of angle -2πθ. Matrix M dom transforms v dom n (z dom , x dom , y dom ) into v dom n+1 (z dom , x dom , y dom ). Using the formulas above with a = 2πnθ, b = 2πθ, we have that for all n ≥ 1, v dom n+1 (z dom , x dom , y dom ) = v dom n (z dom , x dom cos(2πθ) + y dom sin(2πθ), y dom cos(2πθ) -x dom sin(2πθ)) for all n, and thus M dom transforms (z dom , x dom , y dom ) into (z dom , x dom cos(2πθ)+y dom sin(2πθ), y dom cos(2πθ)x dom sin(2πθ)). Now, consider a point p in 2D space at cartesian coordinates (x dom , y dom ). Its polar coordinates are (r, α), with r = x 2 dom + y 2 dom the distance between (0, 0) and p. Consider the point at polar coordinates (r, α -2πθ). Thus it is at cartesian coordinates (r cos(α -2πθ), r sin(α -2πθ)) = (r cos(α) cos(2πθ) + r sin(α) sin(2πθ), r sin(α) cos(2πθ)r cos(α) sin(2πθ)) = x dom cos(2πθ)+y dom sin(2πθ), y dom cos(2πθ)-x dom sin(2πθ)). Hence the rotation of angle -2πθ transforms (x dom , y dom ) into (x dom cos(2πθ)+y dom sin(2πθ), y dom cos(2πθ)x dom sin(2πθ)). ◀

Proof

Proofs for Section 5

We now show that B ℓ ψ is fully in P dom , tangent to the surface of P dom , for d = (2, 2, 0, 0, 0, 2πℓ).

▶


Hugo Parada
email: hugo.parada@univ-grenoble-alpes.fr

Stability analysis of a Korteweg-de Vries equation with saturated boundary feedback

Keywords: Partial differential equations, saturation control, boundary control, stability of nonlinear systems

The stability analysis of the linear and nonlinear Korteweg-de Vries equations in presence of a saturated feedback actuator is studied. The well-posedness is derived by using nonlinear semigroup results, Schauder's and Banach fixed point theorems. The exponential stability is shown thanks to an observability inequality, which is obtained via contradiction and compactness arguments. Finally, an alternative proof of the asymptotic stability of the linear Korteweg-de Vries equation is presented.

INTRODUCTION

The Korteweg-de Vries (KdV) equation u t + u x + u xxx + uu x = 0 was introduced by [START_REF] Korteweg | On the change of form of long waves advancing in a rectangular channel, and a new type of long stationary wave[END_REF] to model the propagation of long water waves in a channel. The KdV equation has been widely studied in the last years, in particular its controllability and stabilization properties, see [START_REF] Cerpa | Control of a Korteweg-de Vries equation: a tutorial[END_REF]; [START_REF] Rosier | Control and stabilization of the Korteweg-de Vries equation: recent progresses[END_REF] for a complete introduction of these problems.

From the point of view of stabilization, we can refer to the work of [START_REF] Zhang | Boundary stabilization of the Korteweg-de Vries equation[END_REF] in which the boundary exponential stabilization problem in the bounded spatial domain x ∈ (0, 1) was studied. It is well known that the length L of the spatial domain plays an important role in the stabilization and controllability properties of the KdV equation. For example, when L = 2π it is possible to find a solution of the linearization around 0 of the KdV equation (u(t, x) = 1 -cos(x)) that has a constant energy. More generally, if L ∈ N , where N is the set of critical lengths defined by

N = 2π (k 2 + kl + l 2 )/3 ; k, l ∈ N * ,
we can find suitable initial data, such that the solution of the linear KdV equation has a constant energy. In the case of internal stabilization, it is proved in Perla [START_REF] Menzala | Stabilization of the Korteweg-de Vries equation with localized damping[END_REF]; [START_REF] Pazoto | Unique continuation and decay for the Korteweg-de Vries equation with localized damping[END_REF] that for any critical length we achieve local exponential stability for the nonlinear KdV. In most real-life settings, we have to take into account the saturation in the input control due to some physical or economical constraints. With respect to saturated control in infinite dimensional systems, we can refer to [START_REF] Prieur | Wave equation with cone-bounded control laws[END_REF] where a wave equation with distributed and boundary saturated feedback law was studied, [START_REF] Marx | Global Stabilization of a Korteweg-de Vries Equation with saturating distributed control[END_REF] where the saturated internal stabilization of a single KdV equation was studied and recently [START_REF] Mironchenko | Local stabilization of an unstable parabolic equation via saturated controls[END_REF] where a saturated feedback control law was derived for a linear reaction-diffusion equation. In our best knowledge, there are no work dealing with the stability of a KdV equation with saturated feedback on the boundary, thus this work gives a sake of completeness on this topic. The plan is to follow the ideas presented in [START_REF] Marx | Global Stabilization of a Korteweg-de Vries Equation with saturating distributed control[END_REF] and [START_REF] Parada | Delayed stabilization of the Korteweg-de Vries equation on a starshaped network[END_REF] to prove the stability of the KdV equation with saturated actuator. To be more specific, let us define the following saturation map:

sat(s) = s, if |s| ≤ M, M sgn(s), if |s| ≥ M, (1)
where M > 0 is the saturation level and sgn is the sign function. In this work, we are going to consider the following equations      y t + y x + y xxx + yy x = 0, t > 0, x ∈ (0, L), y(t, 0) = y(t, L) = 0, t > 0, y x (t, L) = sat(αy x (t, 0)), t > 0, y(0, x) = y 0 (x),

x ∈ (0, L).

(KdVs)

and

     y t + y x + y xxx = 0, t > 0, x ∈ (0, L), y(t, 0) = y(t, L) = 0, t > 0, y x (t, L) = sat(αy x (t, 0)), t > 0, y(0, x) = y 0 (x),
x ∈ (0, L).

(KdVLs)

Note that both (KdVs) and (KdVLs) are nonlinear equations due to the action of the saturation. Keep in mind that (KdVLs) is just (KdVs) but without the nonlinear internal term yy x .

The next theorem is the main result of this work, Theorem 1. Let L / ∈ N and |α| < 1, then there exist C > 0 and µ > 0 such that:

• For all y 0 ∈ L 2 (0, L), the unique mild solution y ∈ C([0, ∞), L 2 (0, L))∩L 2 ((0, ∞), H 1 (0, L)) of (KdVLs) satisfies ∥y(t)∥ L 2 (0,L) ≤ Ce -µt ∥y 0 ∥ L 2 (0,L) . • For all y 0 ∈ L 2 (0, L), satisfying ∥y 0 ∥ L 2 (0,L) ≤ ϵ for some ϵ > 0, the unique mild solution y ∈ C([0, ∞), L 2 (0, L)) ∩ L 2 ((0, ∞), H 1 (0, L)) of (KdVs) satisfies ∥y(t)∥ L 2 (0,L) ≤ Ce -µt ∥y 0 ∥ L 2 (0,L) .
The article is organized as follows. Section 2 is devoted to prove the well-posedness results associated to (KdVLs) and (KdVs). In Section 3 we study the stability analysis of (KdVLs) and (KdVs) using an observability inequality. In Section 4 we show the asymptotic stability of (KdVLs) by using LaSalle's invariance principle. Finally, we give some conclusions and open problems. From now on, C > 0 will be a generic positive constant.

WELL-POSEDNESS RESULTS

The goal of this section is to prove the appropriate wellposedness results for (KdVLs) and (KdVs). The proof for (KdVLs) is based on semigroup theory. For (KdVs) we use the result for (KdVLs), then we will add an internal source term in order to take in account the nonlinear term yy x , and derive some multiplier estimates to obtain the needed regularity.

Consider the operator A :

D(A) → L 2 (0, L) defined by Aw := -w ′ -w ′′′ (2) where D(A) = {w ∈ H 3 (0, L)∩H 1 0 (0, L) : w ′ (L) = sat(αw ′ (0))}.
Well-posedness asks to handle the fact that the operator A is nonlinear. We follow the approach presented in [START_REF] Marx | Stabilization of a linear Korteweg-de Vries equation with a saturated internal control[END_REF]; [START_REF] Prieur | Wave equation with cone-bounded control laws[END_REF], i.e., we show that A is a closed, dissipative operator and that for some λ > 0, D(A) ⊂ R(I -λA), where R denotes the range of the operator.

Well-posedness of (KdVLs)

In this part, we focus on the study of (KdVLs), in particular we prove the following result. Proposition 2. Let y 0 ∈ L 2 (0, L) and |α| < 1, then there exists a unique mild solution y

∈ C([0, ∞), L 2 (0, L)) of (KdVLs). Moreover, if y 0 ∈ D(A), this solution is classical and y ∈ C([0, ∞), D(A)) ∩ C 1 ((0, ∞), L 2 (0, L)).
Proof. By [START_REF] Rosier | Exact boundary controllability for the Korteweg-de Vries equation on a bounded domain[END_REF]

the operator A 0 : D(A 0 ) → L 2 (0, L), D(A 0 ) = {w ∈ H 3 (0, L) ∩ H 1 0 (0, L) : w ′ (L) = 0} such that A 0 w = Aw
is closed and by (Khalil and Grizzle, 2002, Page 91) the operator sat satisfies

∀(s, s) ∈ R 2 , |sat(s) -sat(s)| ≤ |s -s| , (3
) Thus, sat is a Lipschitz continuous function and hence the operator A is closed. Now, let us prove that A is dissipative, let u, v ∈ D(A), then we get ⟨Au -Av, u -v⟩ L 2 (0,L)

= L 0 (-u ′ -u ′′′ + v ′ + v ′′′ )(u -v)dx = - L 0 (u -v) ′ (u -v)dx - L 0 (u -v) ′′′ (u -v)dx. Now, note that for f ∈ H 3 (0, L) L 0 f ′ f dx = 1 2 L 0 (f 2 ) ′ dx = 1 2 [f 2 ] L 0 , (4)
and

L 0 f ′′′ f dx = - L 0 f ′′ f ′ dx + [f ′′ f ] L 0 , = - 1 2 L 0 (f ′2 ) ′ dx + [f ′′ f ] L 0 , = - 1 2 [f ′2 ] L 0 + [f ′′ f ] L 0 .
(5) Thus, using (4), ( 5) and that u, v ∈ D(A) we get

⟨Au -Av, u -v⟩ L 2 (0,L) = - 1 2 [(u -v) ′2 ] L 0 = 1 2 (sat(αu ′ (0)) -sat(αv ′ (0))) 2 - 1 2 (u ′ (0) -v ′ (0)) 2 .
Therefore, denoting

C α = 1 -|α| 2 2 > 0 (6)
which is positive by |α| < 1, and using (3)

⟨Au -Av, u -v⟩ L 2 (0,L) ≤ -C α |u ′ (0) -v ′ (0)| 2 ≤ 0.
Thus, we get A dissipative. Now, we are going to prove that, for λ > 0 small enough D(A) ⊂ R(I -λA). In other words, for each u ∈ D(A), there exists v ∈ D(A) such that (I -λA)v = u. Let u ∈ D(A) and λ = 1 λ we are looking for solutions of λv

+ v ′ + v ′′′ = λu, v(0) = v(L) = 0, v ′ (L) = sat(αv ′ (0)). ( 7
)
Consider the map T :

H 2 (0, L) → L 2 (0, L) defined by T (y) = z, where z is the solution of λz + z ′ + z ′′′ = λu, z(0) = z(L) = 0, z ′ (L) = sat(αy ′ (0)). (8)
Note that the operator T is well-defined, that is, for all y ∈ H 2 (0, L) there exists a unique solution to (8). Indeed, let ψ(x) = sat(αy ′ (0))L 2π

sin 2πx L . Then φ = z -ψ satisfies λφ + φ ′ + φ ′′′ = f = λu -λψ -ψ ′ -ψ ′′′ , φ(0) = φ(L) = φ ′ (L) = 0.
that can be written as (A 0 -λI)φ = -f . But as λ > 0 then λ / ∈ σ(A 0 ) (see for instance [START_REF] Rosier | Exact boundary controllability for the Korteweg-de Vries equation on a bounded domain[END_REF]). Thus (A 0 -λI) is invertible, and we conclude that φ is well-defined and hence z. Now, we show that T has a fixed point. Let C > 0 to be defined after and consider the set

K C = {u ∈ H 1 0 (0, L) : ∥u∥ H 1 0 (0,L) ≤ C}. (9)
Note that by the Rellich-Kondrachov theorem (Brezis, 2010, Thm 9.19, Page 285) we know that the inclusion

H 1 0 (0, L) → L 2 (0, L) is compact and then K C is a bounded set in H 1 0 (0, L) and relatively compact in L 2 (0, L), more- over as K C is closed in L 2 (0, L) we conclude that K C is compact in L 2 (0, L).
Then in order to apply Schauder fixed point theorem (Coron, 2009, Thm B.19), we need to find

C > 0 such that T (H 2 (0, L)) ⊂ K C . Lemma 3. There exists C > 0 such that T (H 2 (0, L)) ⊂ K C .
Proof of Lemma 3. Multiplying the first line of ( 8) by z and integrating on (0, L) we get,

λ L 0 z 2 dx + L 0 z ′ zdx + L 0 z ′′′ zdx = λ L 0 uzdx. (10)
Using ( 4) and ( 5) for z and noticing that z(0) = z(L) = 0, we obtain:

z ′ zdx = 1 2 L 0 (z 2 ) ′ dx = 0, and using z ′ (L) = sat(αy ′ (0)) L 0 z ′′′ zdx = - 1 2 L 0 (z ′2 ) ′ dx = 1 2 z ′ (0) 2 - 1 2 sat(αy ′ (0)) 2 ,
which with (10) yields

λ L 0 z 2 dx + 1 2 z ′ (0) 2 = 1 2 sat(αy ′ (0)) 2 + λ L 0 uzdx.
Then, using Cauchy-Schwarz inequality and the definition of the saturation (1), we get λ 2

∥z∥ 2 L 2 (0,L) ≤ M 2 2 + λ 2 ∥u∥ 2 L 2 (0,L) . (11)
Similarly, multiplying the first line of ( 8) by xz and integrating on (0, L) we get

λ L 0 xz 2 dx + L 0 xz ′ zdx + L 0 xz ′′′ zdx = λ L 0 xuzdx.
(12) Performing integration by parts and by the second line of (8) we obtain,

L 0 xz ′ zdx = 1 2 L 0 x(z 2 ) ′ dx = - 1 2 L 0 z 2 dx,
and

L 0 xz ′′′ zdx = - L 0 z ′′ zdx - L 0 xz ′′ z ′ dx = L 0 (z ′ ) 2 dx - 1 2 L 0 x(z ′2 ) ′ dx = 3 2 L 0 (z ′ ) 2 dx - L 2 sat(αy ′ (0)) 2 .
Thus, from ( 12) we obtain

λ L 0 xz 2 dx + 3 2 L 0 (z ′ ) 2 dx = 1 2 L 0 z 2 dx + L 2 sat(αy ′ (0)) 2 + λ L 0 xuzdx, which yields 3 2 ∥z ′ ∥ 2 L 2 (0,L) ≤ L λ 2 + 1 2 ∥z∥ 2 L 2 (0,L) + LM 2 2 + L λ 2 ∥u∥ 2 L 2 (0,L) , (13)
and hence using (11) we deduce, ∥z ′ ∥ 2 L 2 (0,L) ≤ C, where C > 0 only depends on the level of saturation M , L, λ and u which finishes the proof of Lemma 3. □

Then, applying Schauder fixed point theorem to T , we find the solution v ∈ H 2 (0, L) of ( 7). Moreover, as u ∈ D(A), then v ∈ H 3 (0, L) and hence by the boundary conditions v ∈ D(A). We conclude that for all λ > 0, D(A) ⊂ R(A -λI). Using (Miyadera, 1992, Thm 4.2, Page 77) A is the generator of a semigroup of contractions S(t), t > 0 and by (Miyadera, 1992, Thm 4.2, Page 81) (or [START_REF] Barbu | Nonlinear semigroups and differential equations in Banach spaces[END_REF], Thm 1.2, Page 102)) for all T > 0,

y 0 ∈ D(A), y = S(t)y 0 ∈ C([0, T ]; D(A))∩C 1 ((0, T ); L 2 (0, L)
) is a classical solution to (KdVLs). Moreover, by (Miyadera, 1992, Thm 4.10, Page 87) this solution is unique. Also, we can deduce that for all T > 0, for all y 0 ∈ L 2 (0, L), there exists a unique mild solution of (KdVLs) y ∈ C([0, T ]; L 2 (0, L)) and then, the proof of Proposition 2 is finished. □

Well-posedness of equation (KdVLs) with a source term

Now, we deal with the well-posedness of the system (KdVLs) with an extra source term f     

y t + y x + y xxx = f, t > 0, x ∈ (0, L), y(t, 0) = y(t, L) = 0, t > 0, y x (t, L) = sat(αy x (t, 0)), t > 0, y(0, x) = y 0 (x),
x ∈ (0, L).

(14) Formally, this system can be written as y t = Ay + f . The following result can be obtained using (Pavel, 1987, Thm 10.1, Page 129) and (Pavel, 1987, Thm 10.1, Page 132)

Proposition 4. Let y 0 ∈ L 2 (0, L), |α| < 1, f ∈ L 1 ((0, ∞), L 2 (0, L))
, then there exists a unique mild solution y ∈ C([0, ∞), L 2 (0, L)) of ( 14). Moreover, if

y 0 ∈ D(A) and f ∈ W 1,1 ((0, ∞), L 2 (0, L)) this solution is clas- sical and y ∈ C([0, ∞), L 2 (0, L)), y(t) ∈ D(A), for all t ≥ 0 and y ∈ C 1 ((0, ∞), L 2 (0, L)).
Our idea now is to show that, indeed, the solution of ( 14) has an extra-regularity that will help us to deal the nonlinear term yy x . More specifically, let T > 0 and define

B T = C([0, T ], L 2 (0, L)) ∩ L 2 ((0, T ), H 1 (0, L)) (15) endowed with the norm ∥y∥ 2 B T = ∥y∥ 2 C([0,T ],L 2 (0,L)) + ∥y∥ 2 L 2 ((0,T ),H 1 (0,L)) . Proposition 5. Let y 0 ∈ L 2 (0, L), |α| < 1, f ∈ L 1 ((0, T ), L 2 (0, L)) and T > 0, consider y ∈ C([0, T ], L 2 (0, L))
, the restriction of the solution of ( 14) on [0, T ], then y ∈ B T . Moreover, the following estimate holds,

∥y∥ B T ≤ C(1 + √ T ) ∥y 0 ∥ L 2 (0,L) + ∥f ∥ L 1 ((0,T ),L 2 (0,L)) . (16)
Proof. Suppose y is a classical solution of ( 14), let T > 0 and 0 ≤ s ≤ T . Several computations are quite similar to those performed in the proof of Lemma 3 and for that reason are omitted here. Multiplying the first line of ( 14) by y and integrating on (0, L) × (0, s), we get

s 0 L 0 y t ydxdt + s 0 L 0 y x ydxdt + s 0 L 0 y xxx ydxdt = s 0 L 0 f ydxdt. (17) Note that, s 0 y t ydt = 1 2 s 0 d dt y 2 dt = 1 2 y 2 (s, •) - 1 2 y 2 0 . (18)
Hence, using (4) and ( 5), ( 17) becomes

1 2 L 0 y(s, x) 2 dx + 1 2 s 0 y x (t, 0) 2 -sat(αy x (t, 0)) 2 dt = 1 2 L 0 y 2 0 dx + s 0 L 0 f ydxdt. (19) First, note that for all s ∈ [0, T ] s 0 L 0 f ydxdt ≤ T 0 ∥y(t, •)∥ L 2 (0,L) ∥f (t, •)∥ L 2 (0,L) dt ≤ ∥y∥ C([0,T ],L 2 (0,L)) ∥f ∥ L 1 ((0,T ),L 2 (0,L)) .
(20) Now, using (1), ( 19) and ( 20) we get for all s ∈ [0, T ],

1 2

L 0 y(s, x) 2 dx + C α s 0 y x (t, 0) 2 dt ≤ 1 2 L 0 y 2 0 dx +∥y∥ C([0,T ],L 2 (0,L)) ∥f ∥ L 1 ((0,T ),L 2 (0,L)) . (21)
Taking the supremum for s ∈ [0, T ], and with Young's inequality, we get

∥y∥ 2 C([0,T ],L 2 (0,L)) ≤ C ∥y 0 ∥ 2 L 2 (0,L) + ∥f ∥ 2 L 1 ((0,T ),L 2 (0,L)) .
(22) Moreover, from ( 21) taking s = T , and using ( 22) we can derive the following hidden regularity

T 0 y x (t, 0) 2 dt ≤ C ∥y 0 ∥ 2 L 2 (0,L) + ∥f ∥ 2 L 1 ((0,T ),L 2 (0,L)) .
(23) Now, we multiply the first line of ( 14) by xy and integrate on (0, L) × (0, T ) and we get

= T 0 L 0 y 2 x dxdt - 1 2 T 0 L 0 x d dx y 2 x dxdt = 3 2 T 0 L 0 y 2 x dxdt - L 2 T 0 sat(αy x (t, 0) 2 dt.
Thus, from (24) we obtain

1 2 L 0 xy(T, x) 2 dx + 3 2 T 0 L 0 y 2 x dxdt = 1 2 L 0 xy 2 0 dx + 1 2 T 0 L 0 y 2 dxdt + L 2 T 0 sat(αy x (t, 0)) 2 dt + T 0 L 0 xf ydxdt. (25) Note that T 0 L 0 y 2 dxdt ≤ T 0 sup t∈[0,T ] L 0 y 2 (t, •)dx dt = T ∥y∥ 2 C([0,T ],L 2 (0,L)) (26)
Moreover, by ( 1) and ( 23)

T 0 sat(αy x (t, 0)) 2 dt ≤ C ∥y 0 ∥ 2 L 2 (0,L) + ∥f ∥ 2 L 1 ((0,T ),L 2 (0,L))
, and by ( 20) and ( 22)

T 0 L 0 xf ydxdt ≤ C ∥y 0 ∥ 2 L 2 (0,L) + ∥f ∥ 2 L 1 ((0,T ),L 2 (0,L)) .
Therefore, joining these estimates, we deduce from ( 25)

∥y x ∥ 2 L 2 ((0,T ),L 2 (0,L)) ≤ C(1 + T ) ∥y 0 ∥ 2 L 2 (0,L) + ∥f ∥ 2 L 1 ((0,T ),L 2 (0,L)) , (27)
and thus y ∈ L 2 ((0, T ), H 1 (0, L)). Mixing ( 22) and ( 27) we deduce ( 16). The result can be extended by density to mild solutions. □

Well-posedness of the nonlinear system

Now, we are ready to give the proof of the well-posedness result for (KdVs). For that the next proposition will be crucial, its proof can be founded in Perla [START_REF] Menzala | Stabilization of the Korteweg-de Vries equation with localized damping[END_REF]. Proposition 6. Let y ∈ B T . Then

yy x ∈ L 1 ((0, T ), L 2 (0, L)) and the map y ∈ B T → yy x ∈ L 1 ((0, T ), L 2 (0, L)) is continuous. Moreover, there exists C > 0 such that, for any y, z ∈ B T ∥yy x -zz x ∥ L 1 ((0,T ),L 2 (0,L)) ≤ CT 1/4 (∥y∥ B T + ∥z∥ B T )∥y -z∥ B T .
The main result of this subsection is the following one. Proposition 7. Let y 0 ∈ L 2 (0, L) and |α| < 1, then there exists a unique mild solution y ∈ C([0, ∞), L 2 (0, L)) ∩ L 2 ((0, ∞), H 1 (0, L)) of (KdVs).

Proof. Let y 0 ∈ D(A) and R, θ > 0 to be chosen later.

Consider the closed ball B B θ (0, R) := {z ∈ B θ , ∥z∥ B θ ≤ R}, where B θ is defined by (15). Then, B B θ (0, R) is a complete metric space. Let the map Φ : B θ → B θ defined for z ∈ B θ by Φ(z) = y, where y is the solution of

     y t + y x + y xxx = -zz x , t > 0, x ∈ (0, L), y(t, 0) = y(t, L) = 0, t > 0, y x (t, L) = sat(αy x (t, 0)), t > 0, y(0, x) = y 0 (x),
x ∈ (0, L). Note first that y is well-defined, since by Proposition 6, zz x ∈ L 1 ((0, θ), L 2 (0, L)). Clearly, y ∈ B θ is solution of (KdVs) if y is a fixed point of Φ. From Proposition 5 and Proposition 6, we get for all z ∈ B θ

∥Φ(z)∥ B θ = ∥y∥ B θ ≤ C(1 + θ 1/2 ) ∥y 0 ∥ L 2 (0,L) +∥zz x ∥ L 1 ((0,T ),L 2 (0,L)) ≤ C 1 (1 + θ 1/2 )∥y 0 ∥ L 2 (0,L) + C 2 (1 + θ 1/2 )θ 1/4 ∥z∥ 2 B θ , for some C 1 , C 2 > 0. Then taking R = 3C 1 ∥y 0 ∥ L 2 (0,L) and θ > 0 small enough such that C 2 (1 + θ 1/2 )θ 1/4 R < 1 3 and (1 + θ 1/2 ) < 2, we have that ∥Φ(z)∥ B θ ≤ R. Thus, Φ maps the ball B B θ (0, R) into itself. Now, take z 1 , z 2 ∈ B B θ (0, R), y 1 = Φ(z 1 ), y 2 = Φ(z 2 ), then w = Φ(z 1 ) -Φ(z 2 ) satisfies      w t + w x + w xxx = f, t > 0, x ∈ (0, L), w(t, 0) = w(t, L) = 0, t > 0, w x (t, L) = h(t), t > 0, w(0, x) = 0,
x ∈ (0, L).

(28)

where f = -z 1 z 1,x + z 2 z 2,x and h = sat(αy 1,x (t, 0))sat(αy 2,x (t, 0)). First, note that by ( 23), h ∈ L 2 (0, θ) and hence ( 28) is well-posed (Cerpa, 2014, Prop 3). Moreover,

∥w∥ B θ ≤ C ∥h∥ L 2 (0,θ) + ∥f ∥ L 1 ((0,θ),L 2 (0,L)) .
(29) We can not use directly the estimates obtained in Section 2.2, because h ̸ = sat(αw x (t, 0)), but similar estimates can be obtained. If we multiply the first line of ( 28) by w and integrate on (0, L) × (0, θ), we get (31) Since h = sat(αy 1,x (t, 0)) -sat(αy 2,x (t, 0)), using (3) we derive,

∥h∥ L 2 (0,θ) = ∥sat(αy 1,x (t, 0)) -sat(αy 2,x (t, 0))∥ L 2 (0,θ) ≤ ∥αy 1,x (•, 0) -αy 2,x (•, 0)∥ L 2 (0,θ) = |α|∥w x (•, 0)∥ L 2 (0,θ) .
(32) Thus, plugging (32) in (31), we obtain 1 2

L 0 w(θ, x) 2 dx + C α θ 0 w x (t, 0) 2 dt ≤ θ 0 L 0 f wdxdt, (33) which implies using Young's inequality ∥w∥ C([0,θ],L 2 (0,L)) ≤ C∥f ∥ L 1 ((0,θ),L 2 (0,L)) . ( 34
)
Using ( 34) in ( 33), we get

θ 0 w x (t, 0) 2 dt ≤ C∥f ∥ 2 L 1 ((0,θ),L 2 (0,L)) ,
and then (32

) brings ∥h∥ L 2 (0,θ) ≤ C∥f ∥ L 1 ((0,θ),L 2 (0,L)) , which transforms (29) into ∥w∥ B θ ≤ C∥f ∥ L 1 ((0,θ),L 2 (0,L)) . (35)
Finally, by ( 35) and Proposition 6 we conclude:

∥Φ(z 1 ) -Φ(z 2 )∥ B θ = ∥w∥ B θ ≤ C 3 θ 1/4 R∥z 1 -z 2 ∥ B θ , for some C 3 > 0.
Then taking θ > 0, small enough such that C 3 θ 1/4 R < 1, we get that Φ is a contraction, and we conclude by using the Banach Fixed Point theorem (Brezis, 2010, Thm 5.7) and density argument to extend the result for all y 0 ∈ L 2 (0, L). Thus, we have proved the following local in-time well-posedness result: Proposition 8. Let y 0 ∈ L 2 (0, L), |α| < 1 and T > 0. Then there exists 0 < T * ≤ T and a unique mild solution y ∈ B T * of (KdVs) on the time interval [0, T * ]. Moreover, there exists C > 0 such that ∥y∥ B T * ≤ C∥y 0 ∥ L 2 (0,L) .

To conclude the proof of the global well-posedness result stated on Proposition 7, we need some a priori estimates, based on a multiplier approach, similar to those presented in Section 2.2. Let T > 0 and y a classical solution of (KdVs). Multiplying the first line of (KdVs) by y, integrating on (0, L) × (0, s) we get Therefore, we derive from ( 36) Then, taking the supremum for s ∈ [0, T ] in (38),

1 2 L 0 y(s, x) 2 dx + 1 2 s 0 y x (t, 0) 2 -sat(αy x (t, 0)) 2 = 1 2 L 0 y 2 0 dx. ( 37
∥y∥ 2 C([0,T ],L 2 (0,L)) ≤ ∥y 0 ∥ 2 L 2 (0,L) . ( 39
)
On the other hand, taking s = T in (38),

T 0 y x (t, 0) 2 dt ≤ 1 2 C -1 α ∥y 0 ∥ 2 L 2 (0,L) . (40)
Now, we multiply the first line of (KdVs) by xy and integrate on (0, L) × (0, T ), obtaining Hence, we infer from ( 41)

1 2 L 0 xy(T, x) 2 dx + 3 2 T 0 L 0 y 2 x dxdt = 1 2 L 0 xy 2 0 dx + 1 2 T 0 L 0 y 2 dxdt + L 2 T 0 sat(αy x (t, 0)) 2 dt + 1 3 T 0 L 0 y 3 dxdt.
(42) For the term involving

L 0 y 3 (t, x)dx, by the injection of H 1 0 (0, L) into L ∞ (0, L) we know that ∥y∥ L ∞ (0,L) ≤ C∥y x ∥ L 2 (0,L) , for some C > 0 then T 0 L 0 y 3 (t, x)dxdt ≤ T 0 ∥y∥ L ∞ (0,L) ∥y∥ 2 L 2 (0,L) dt ≤ C T 0 ∥y x ∥ L 2 (0,L) ∥y∥ 2 L 2 (0,L) dt,
which implies using (39)

T 0 L 0 y 3 (t, x)dxdt ≤ C √ T ∥y 0 ∥ 2 L 2 (0,L) ∥y x ∥ L 2 ((0,T ),L 2 (0,L)) .
(43) Thus, from (42) using ( 26), ( 39), ( 40) and ( 43) we derive

∥y x ∥ 2 L 2 ((0,T ),L 2 (0,L)) ≤ C(1 + T )∥y 0 ∥ 2 L 2 (0,L) +C √ T ∥y 0 ∥ 2 L 2 (0,L) ∥y x ∥ L 2 ((0,T ),L 2 (0,L)) . Using Young's inequality ∥y x ∥ 2 L 2 ((0,T ),L 2 (0,L)) ≤ C(1+T )∥y 0 ∥ 2 L 2 (0,L) +CT ∥y 0 ∥ 4 L 2 (0,L) . (44)
Finally, with (39) and ( 44) and arguing by density, the proof of Proposition 7 is finished. □

EXPONENTIAL STABILITY

In this section, we are going to prove the main result of this work, namely Theorem 1. For all t > 0, we define the energy of (KdVs) (or (KdVLs)) by

E(t) = 1 2 L 0 y(t, x) 2 dx. (45)
Then, for a classical solution of (KdVs) (or (KdVLs)) performing integration by parts, we get using |α| < 1

Ė(t) = 1 2 (sat(αy x (t, 0))) 2 - 1 2 (y x (t, 0)) 2 ≤ 0. ( 46
)
Thus, formally, the energy is a non-increasing function of time. Now, we will prove that indeed, the energy decays exponentially to 0 when L / ∈ N . Our approach will be based on an observability inequality for the system (KdVLs). Proposition 9. Let L / ∈ N , |α| < 1 and y 0 ∈ L 2 (0, L). For any solution y of (KdVLs), the following inequality holds:

L 0 y 2 0 dx ≤ C obs T 0 y 2 x (t, 0)dt, (47)
for some C obs > 0, that does not depend on y 0 .

Proof. In order to prove the observability inequality, we follow [START_REF] Rosier | Exact boundary controllability for the Korteweg-de Vries equation on a bounded domain[END_REF] and use a contradiction argument. Let us suppose that (47) is false, then there exists (

y n 0 ) n∈N ⊂ L 2 (0, L) such that L 0 (y n 0 ) 2 dx = 1, and T 0 (y n x (t, 0)) 2 dt → 0
when n → ∞ and where y n = S(t)y n 0 . Now, using ( 27) with f = 0 we get that (y n ) n∈N is bounded in L 2 ((0, T ), H 1 (0, L)). Then as y n t = -y n x -y n xxx , we can see that (y n t ) n∈N is bounded in L 2 ((0, T ), H -2 (0, L)), thus by Aubin-Lions lemma (y n ) n∈N is relatively compact in L 2 ((0, T ), L 2 (0, L)), therefore we can assume that y n → y in L 2 ((0, T ), L 2 (0, L)). Now, multiplying the first line of (KdVLs) by (T -t)y, integrating on (0, L) × (0, T ), we get

T 0 L 0 (T -t)y t ydxdt + T 0 L 0 (T -t)y xxx ydxdt + T 0 L 0 (T -t)y x ydxdt + T 0 L 0 (T -t)y 2 y x dxdt = 0. (48) Using L 0 y x ydx = 0, L 0 y 2 y x dx = 0, L 0 y xxx ydx = y 2 x (t, 0) 2 - sat(αy x (t, 0)) 2 2 ,
and

T 0 L 0 (T -t)y t ydxdt = 1 2 T 0 L 0 (T -t) d dt y 2 dxdt = 1 2 T 0 L 0 y 2 dxdt + 1 2 L 0 (T -t)y 2 (t, x)dx t=T t=0 = 1 2 T 0 L 0 y 2 dxdt - 1 2 L 0 T y 2 0 dx,
we get from (48)

T 2 L 0 y 2 0 dx + 1 2 T 0 (T -t)sat(αy x (t, 0)) 2 dt = 1 2 T 0 L 0 y 2 dxdt + 1 2 T 0 (T -t)y x (t, 0) 2 dt. Therefore, L 0 y 2 0 dx ≤ 1 T ∥y∥ 2 L 2 (0,T,L 2 (0,L)) + T 0 y x (t, 0) 2 dt. (49)
Hence, using (49) we derive that (y n 0 ) n∈N is a Cauchy sequence in L 2 (0, L) . Let y 0 = lim n→∞ y n 0 , then L 0 y 2 0 dx = 1, and

T 0 y x (t, 0) 2 dt = 0
Thus, as sat(0) = 0, we conclude that y solves the following linear equation:

y t + y x + y xxx = 0, t > 0, x ∈ (0, L), y(t, 0) = y(t, L) = 0, t > 0, y x (t, 0) = y x (t, L) = 0, t > 0, (50)
But by (Rosier, 1997, Lemma 3.4) if L / ∈ N , there is no function satisfying this system and ∥y 0 ∥ L 2 (0,L) = 1, which gives us the contradiction and finishes the proof of Proposition 9. □ Now, we prove our main result.

Proof of Theorem 1. Let y 0 ∈ D(A), using ( 46) and ( 3) we get for a classical solution of (KdVLs) Ė(t) ≤ -C α (y x (t, 0)) 2 , thus, integrating the last expression between 0 and T , we derive

E(T ) -E(0) ≤ -C α T 0 (y x (t, 0)) 2 dt.
Using the last expression, ( 46) and ( 47) we get

E(T ) ≤ E(0) ≤ C obs T 0 (y x (t, 0)) 2 dt ≤ C obs C α (E(0) -E(T )),
which implies that

E(T ) ≤ γE(0), with γ = C obs C α + C obs < 1. ( 51
)
Now as the system is invariant by translation in time, we can repeat this argument on [(m -1)T, mT ] for m = 1, 2, • • • to obtain,

E(mT ) ≤ γE((m -1)T ) ≤ • • • ≤ γ m E(0)
. Hence, we have E(mT ) ≤ e -µmT E(0) where µ = 1 T ln( 1 γ ) > 0. Let t > 0 then there exists m ∈ N * such that (m -1)T < t ≤ mT , and then using again the nonincreasing property of the energy we get

E(t) ≤ E((m -1)T ) ≤ e -µ(m-1)T E(0) ≤ 1 γ e -µt E(0).
Finally, we conclude the exponential stability of (KdVLs) by a density argument and hence the first point of Theorem 1.

Since (KdVs) is also invariant by translation in time, to prove the second point of Theorem 1, the goal is to prove (51) for a solution of (KdVs). This idea was used in several works, for instance Perla [START_REF] Menzala | Stabilization of the Korteweg-de Vries equation with localized damping[END_REF]; [START_REF] Parada | Delayed stabilization of the Korteweg-de Vries equation on a starshaped network[END_REF]. More specifically, we are going to show that ∥y(T )∥ L 2 (0,L) ≤ γ∥y 0 ∥ L 2 (0,L) , for some γ ∈ (0, 1). Let ∥y 0 ∥ L 2 (0,L) ≤ ϵ for ϵ > 0 to fix later. Take y the solution of (KdVs), then we can split y as y = y + ỹ, where

     y t + y x + y xxx = 0, t > 0, x ∈ (0, L), y(t, 0) = y(t, L) = 0, t > 0, y x (t, L) = sat(αy x (t, 0)), t > 0, y(0, x) = y 0 (x), x ∈ (0, L), and      ỹt + ỹx + ỹxxx = -yy x , t > 0, x ∈ (0, L), ỹ(t, 0) = ỹ(t, L) = 0, t > 0, ỹx (t, L) = h(t), t > 0, ỹ(0, x) = 0, x ∈ (0, L),
where h(t) = sat(αy x (t, 0)) -sat(αy x (t, 0)).

Now clearly, ∥y(T, •)∥

L 2 (0,L) ≤ ∥y(T, •)∥ L 2 (0,L) + ∥ỹ(T, •)∥ L 2 (0,L) . (52)
Moreover, as y satisfies (KdVLs), we get using (51) and y(0, x) = y 0 (x) that there exists γ < 1 such that ∥y

(T )∥ L 2 (0,L) ≤ γ∥y 0 ∥ L 2 (0,L) . (53) Besides, ∥ỹ(T, •)∥ L 2 (0,L) ≤ ∥ỹ∥ C([0,T ],L 2 (0,L)) .
To estimate ∥ỹ∥ C([0,T ],L 2 (0,L)) using (34) we get ∥ỹ∥ C([0,T ],L 2 (0,L)) ≤ C∥yy x ∥ L 1 ((0,T ),L 2 (0,L)) , by Proposition 6, ∥yy x ∥ L 1 ((0,T ),L 2 (0,L)) ≤ C∥y∥ 2 B T , using (39)-( 44), we derive

∥y∥ 2 B T ≤ C ∥y 0 ∥ 2 L 2 (0,L) + ∥y 0 ∥ 4 L 2 (0,L) . Thus, we get for ỹ ∥ỹ∥ C([0,T ],L 2 (0,L)) ≤ C ∥y 0 ∥ 2 L 2 (0,L) + ∥y 0 ∥ 4 L 2 (0,L) , and hence ∥ỹ(T, •)∥ L 2 (0,L) ≤ C∥y 0 ∥ L 2 (0,L) +C∥y 0 ∥ 3 L 2 (0,L) ∥y 0 ∥ L 2 (0,L) , (54)
Finally, as ∥y 0 ∥ L 2 (0,L) ≤ ϵ using ( 53) and ( 54), we deduce from ( 52)

∥y(T, •)∥ L 2 (0,L) ≤ ∥y(T, •)∥ L 2 (0,L) + ∥ỹ(T, •)∥ L 2 (0,L) ≤ γ∥y 0 ∥ L 2 (0,L) + (Cϵ + Cϵ 3 )∥y 0 ∥ L 2 (0,L) = (γ + Cϵ + Cϵ 3 )∥y 0 ∥ L 2 (0,L) ,
we conclude by choosing ϵ > 0 small enough such that γ = γ + Cϵ + Cϵ 3 < 1. □

ASYMPTOTIC STABILITY VIA LASALLE'S INVARIANCE PRINCIPLE

Another approach to prove the stability of (KdVLs) is to use Lyapunov techniques and LaSalle's invariance principle. This idea was developed in the case of internal saturation in [START_REF] Marx | Stabilization of a linear Korteweg-de Vries equation with a saturated internal control[END_REF]. The Lyapunov function to take in account is the energy defined by ( 45). Proposition 10. Let L / ∈ N and |α| < 1, then for all y 0 ∈ L 2 (0, L), the mild solution y of (KdVLs) satisfies:

∥y(t, •)∥ L 2 (0,L) → 0, as t → ∞.
Proof. First, note that by (46), Ė(t) ≤ 0 that tells us that for regular initial data the solution of (KdVLs) is stable and moreover Ė(t) = 0 if and only if y x (t, 0) = 0. In fact, we consider now two cases:

• |sat(αy x (t, 0))| = M . This happens when |αy x (t, 0)| ≥ M which implies |y x (t, 0)| ≥ M |α| . By (46), Ė(t) = 0 if and only if M = |y x (t, 0)|. Then M ≥ M |α| , which is a contradiction because |α| < 1. • sat(αy x (t, 0)) = αy x (t, 0). Then Ė(t) = 0 if and only if α 2 |y x (t, 0)| 2 = |y x (t, 0)| 2 , which is only possible if y x (t, 0) = 0.

To apply LaSalle's invariance principle, we need that the trajectories are compact, in this context, it is possible to show the following result. Lemma 11. The canonical embedding from D(A), equipped with the graph norm, into L 2 (0, L) is compact. Now as A generates a semigroup of contractions, then from (Brezis, 1973, Thm 3.1 Page 54), we get that for all t ≥ 0 and y(0, •) ∈ D(A), ∥y(t, •)∥ L 2 (0,L) ≤ ∥y(0, •)∥ L 2 (0,L) , ∥Ay(t, •)∥ L 2 (0,L) ≤ ∥Ay(0, •)∥ L 2 (0,L) . Thus, by Lemma 11, we have that the trajectory {v(t) = S(t)v 0 , t ≥ 0} is pre-compact in L 2 (0, L), then by (Slemrod, 1989, Thm, 3,1) the ω-limit set, ω[y(0, •)] ⊂ D(A), is not empty and invariant to the semigroup S(t). Take now a regular solution such that Ė(t) = 0, that is y x (t, 0) = 0 t ≥ 0. Then y solves (50) and by (Rosier, 1997, Lemma 3.4) if L / ∈ N y(t, x) = 0 a.e x ∈ (0, L). Consequently, ∥y(t, •)∥ L 2 (0,L) → 0, as t → ∞

for the regular solution of (KdVLs). It is possible to extend this result to mild solutions by density. □

CONCLUSION

The exponential stability of the nonlinear KdV equation with a saturated feedback on the boundary was addressed.

The well-posedness is obtained using nonlinear semigroup theory and fixed point results. The exponential stability was shown via the classical observability approach, and the asymptotic stability of the linear KdV was addressed using LaSalle's invariance principle. An important open question arising in this context is to design a saturated boundary feedback term which gives stability when L ∈ N . What it is known about the linear KdV equation with boundary conditions on y(t, 0), y(t, L) and y x (t, L) is that it is never exactly controllable from the right side when L ∈ N (see [START_REF] Rosier | Exact boundary controllability for the Korteweg-de Vries equation on a bounded domain[END_REF] and [START_REF] Glass | Controllability of the Korteweg-de Vries equation from the right Dirichlet boundary condition[END_REF]). In particular, concerning the system (KdVs) the feedback term αy x (t, 0), and the strategies employed here are not capable of dealing with critical lengths. A possible solution to this problem could be to take another boundary feedback term acting on the left Dirichlet condition as in [START_REF] Cerpa | Rapid stabilization for a Korteweg-de Vries equation from the left Dirichlet boundary condition[END_REF], where a backstepping controller was designed. To saturate this control, an idea is to follow [START_REF] Kang | Boundary control of delayed ODE-Heat cascade under actuator saturation[END_REF] and [START_REF] Kang | Regional stabilization of linear delayed Schrödinger equation by constrained bound-ary control[END_REF].

  x y 2 dxdt, the other terms are computing as in (20).

ACKNOWLEDGEMENTS

We thank Emmanuelle Crépeau and Christophe Prieur for the fruitful discussions and precious suggestions. This work was supported by the French National Research Agency in the framework of the "Investissements d'avenir" program (ANR-15-IDEX-02).