Irène Marcovici
email: irene.marcovici@univ-lorraine.fr

Thomas Stoll
email: thomas.stoll@univ-lorraine.fr

Pierre-Adrien Tahay
email: pierre-adrien.tahay@univ-lorraine.fr

Construction of Some Nonautomatic Sequences by Cellular Automata

Keywords: cellular automata, automatic sequences, nonautomatic sequences, computability, polynomials, Fibonacci word

It is known that if p is a prime number, the columns of linear CA are pautomatic sequences and all p-automatic sequences can be realized by some linear CA with memory. We give some constructions of (nonlinear) CA that realize certain nonautomatic sequences. First, we show through a recoding that from a construction with additional symbols, we can construct a CA using only the symbols occurring in the sequence. This answers a question posed by Rowland and Yassawi. Then, we propose a construction for the characteristic sequence of the integer polynomials, which are nonautomatic sequences by the Minsky-Papert criterion. We also provide a construction based on the indicator of Fibonacci numbers for the Fibonacci word, which is an emblematic nonautomatic sequence.

Introduction

A one-dimensional cellular automaton (CA) is a dynamical system (A Z , F ), where A is a finite set, and where the map F : A Z → A Z is defined by a local rule which acts uniformly and synchronously on the configuration space. Precisely, there exists an integer r ≥ 0 called the radius of the CA, and a local rule f : A 2r+1 → A such that ∀x ∈ A Z , ∀k ∈ Z, F (x) k = f ((x k+i ) -r≤i≤r ). By the Curtis-Hedlund-Lyndon theorem, a map F : A Z → A Z is a CA if and only if it is continuous with respect to the product topology, and it commutes with the shift map σ defined by σ(x) k = x k-1 , ∀x ∈ A Z , ∀k ∈ Z.

Let A be a finite set containing an element denoted by 0, and let F : A Z → A Z be a CA. We say that F is 0-quiescent if F (0 Z ) = 0 Z . A configuration x ∈ A Z is said to be finite if the set {k ∈ Z : x k = 0} is finite. We denote by C 0 (A) the set of finite configurations of A Z .

In the present paper, we study the set of sequences of A N that can occur as a column sequence in the space-time diagram of some one-dimensional CA, with a finite initial configuration. Precisely, we study the set S of sequences having the form (F n (x) 0 ) n≥0 , where F is a 0-quiescent CA on A Z and where x ∈ C 0 (A). Thus, S = (F n (x) 0 ) n≥0 ∈ A N : F is a 0-quiescent CA on A Z and x ∈ C 0 (A) .

With the terminology introduced by Mazoyer and Terrier, this corresponds to the notion of Fischer's produced sequences [START_REF] Mazoyer | Signals in one-dimensional cellular automata[END_REF]Def. 5]. We will use in particular the following closure property of S: if u ∈ S then, for any sequence v that differs from u in a finite number of positions only, we also have v ∈ S. Mazoyer and Terrier have also investigated further properties of the set S above, and proved that it is stable by different operations. Here, we are particularly interested in clarifying the relationship to (non)automaticity of the underlying sequences, and we propose effective constructions for some specific families of sequences.

When A = F p , a CA F is said to be linear if it defines an F p -linear map. Equivalently, this means that the local rule of F can be written as f ((x i ) -r≤i≤r ) = r i=-r α i x i , for some r ≥ 0 and coefficients α i ∈ F p .

A deterministic finite automaton with output (DFAO) is a 6-tuple (Q, Σ k , δ, s 0 , A, ω) where Q is a finite set of states, Σ k = {0, 1, . . . , k -1}, s 0 ∈ Q is the initial state, A is a finite alphabet, ω : Q -→ A is the output function, and δ :

Q × Σ k -→ Q is the transition function. A sequence (u n ) n 0 of elements in A is k-automatic if there is a DFAO (Q, Σ k , δ, s 0 , A, ω) such that u n = ω(δ(s 0 , (n) k )) for all n
0, where (n) k is the word constituted by the digits of the standard base-k representation of n. We refer to the book of Allouche and Shallit [1, Sections 5,[START_REF] Fischer | Generation of Primes by a One-Dimensional Real-Time Iterative Array[END_REF] for the robustness of the concept of automatic sequences and their various characterizations.

In 1993, Litow and Dumas [START_REF] Litow | Additive cellular automata and algebraic series[END_REF] proved that if p is a prime number, every column of a linear CA over F p (with a finite initial configuration) is p-automatic. In 2015, Rowland and Yassawi [START_REF] Rowland | A characterization of p-automatic sequences as columns of linear cellular automata[END_REF] established a converse statement. Namely, for any p-automatic sequence, they show how to obtain that sequence as a column of a linear CA with memory, with eventually periodic initial conditions.

Let us now consider nonautomatic sequences. By the results above, they cannot be realized by a linear CA. However, for some nonautomatic sequences having a simple algorithmic description, we can reasonably think that they can be obtained with other kinds of CA. Throughout the present article, we will focus on binary sequences, that is, we will assume that the set of symbols is A = {0, 1}. Then, a sequence u ∈ A N is characterized by the set of positions k ∈ N such that u k = 1. For a subset E of N, we denote by u = 1 E the sequence defined by

u k = 1 ⇐⇒ k ∈ E.
Let f : N → N be an increasing function and π f (x) = #{n : f (n) ≤ x}. Minsky and Papert [START_REF] Minsky | Unrecognizable Sets of Numbers[END_REF] showed that if lim x→∞ π f (x)/x = 0 and lim n→∞ f (n+1

)/f (n) = 1, then the sequence u = 1 f (N) is nonautomatic. For example, if P ∈ Q[X]
is a polynomial of degree d ≥ 2 such that P (N) ⊂ N, and P is strictly increasing on N, then the Minsky-Papert criterion is satisfied (since π P (x) is of order x 1/d ), meaning that the sequence 1 P (N) is nonautomatic. Note that the case of nonrecognizability of the squares was known before the work of Minsky and Papert, namely, it follows from work of Büchi [START_REF] Büchi | Weak Second-Order Arithmetic and Finite Automata[END_REF] concerning second order weak arithmetic. Ritchie [START_REF] Ritchie | Finite Automata and the Set of Squares[END_REF] gave a short proof of this fact in the case for squares in base-2 expansions (see also [START_REF] Allouche | Automatic Sequences: Theory, Applications, Generalizations[END_REF]Section 5.5,p.166]). However, as shown by Mazoyer and Terrier [START_REF] Mazoyer | Signals in one-dimensional cellular automata[END_REF] and by Delacourt, Poupet, Sablik and Theyssier [START_REF] Delacourt | Directional dynamics along arbitrary curves in cellular automata[END_REF], there exists a simple CA giving the characteristic function of the squares in its column, using only three additional symbols corresponding to walls and left and right signals.

Another example of nonautomatic sequence is given by u = 1 P , where P denotes the set of prime numbers. With the help of the prime number theorem, the Minsky-Papert criterion can also be used to prove the nonautomaticiy of this sequence. This means that the primes cannot be recognized by a finite automaton. A first intricate construction of that sequence as a column of CA was provided by Fischer [START_REF] Fischer | Generation of Primes by a One-Dimensional Real-Time Iterative Array[END_REF], then a simpler one was proposed by Korec [START_REF] Korec | Real-time generation of primes by a one-dimensional cellular automaton with 11 states[END_REF], using only a few signals having different speeds.

In the present article, we describe two constructions of nonautomatic sequences, one that realizes the characteristic function of any polynomial of any arbitrary fixed degree d ≥ 2 (Section 3), and one that realizes the Fibonacci word (Section 4) which is an emblematic morphic and nonautomatic word.

Before presenting our constructions, we show that any sequence that can be obtained with the help of auxiliary symbols from a larger set B ⊃ A can also be obtained with a CA defined on A Z (Prop. 1). Our proof is based on a binary recoding of the elements of B, a technique already used for the construction of primes [START_REF] Korec | Real-time generation of primes by a one-dimensional cellular automaton with 11 states[END_REF]. As a consequence of this result, in order to prove that a sequence belongs to S, it is sufficient to provide a CA that uses additional states, and this is what we will do. In particular, this recoding answers a question asked by Rowland and Yassawi, since it shows that any 3-automatic sequence on a 2-letter alphabet occurs as a column of a (nonlinear) 2-state space-time diagram [14, third question on p. 80].

In contrast with these results, we also give an elementary proof of the fact that there are computable sequences that lie outside of S, meaning that the class of computable sequences is "richer" than the set of sequences obtained via CA (Prop. 5). We end with some open questions, asking whether some concrete sequences that are relevant in number theory or in combinatorics can be obtained by a CA or not.

Binary recoding

Let us recall that for the rest of the article, we will consider a binary set of symbols: A = {0, 1}.

Proposition 1. Let B be a finite set of symbols such that B A, let F : B Z → B Z be a 0-quiescent CA, and let x ∈ B Z be a finite configuration.

If ∀n ∈ N, F n (x) 0 ∈ A, then, (F n (x) 0 ) n≥0 ∈ S.
Proof. Without loss of generality, let us assume that B = {0, . . . , k-1} for some k ≥ 3. We recode the k symbols of the alphabet B by binary words of length 2k -1, using the map τ : B → A 2k-1 defined as follows:

τ (0) = 00 • • • 0 2k-1 ,
and

for i ∈ {1, . . . , k -1}, τ (i) = 1 0 • • • 0 i-1 1 0 • • • 0 2k-i-2
.

From a configuration x ∈ B Z , the concatenation of the blocks τ (x i ) for i ∈ Z gives rise to a new configuration x ∈ A Z , where we assume that the block τ (x 0 ) starts at position 0 in the new configuration, meaning that (x i ) 0≤i≤2k-2 = τ (x 0 ). With this recoding, it is possible to determine locally the boundaries between the blocks in the new configuration, except if we have a long range of 0's. But in that case, since F is 0-quiescent, we know that the local function will output a 0. So, using this recoding, we can define a new CA G : A Z → A Z of radius (2k -1)r + 2k -2 = (2k -1)(r + 1) -1 that mimics on A Z the action of the original CA F : B Z → B Z , and G is itself a 0-quiescent CA. Since the first letter of τ (0) and τ (1) are respectively 0 and 1, if there is no occurence of symbols from B \ A in the central column, then we will have:

∀n ∈ N, F n (x) 0 = G n (x) 0 .
Example 1. In particular, if B = {0, 1, 2}, the recoding τ above is defined by: τ (0) = 00000, τ (1) = 11000, τ (2) = 101000, and the construction answers a question asked by Rowland and Yassawi [START_REF] Rowland | A characterization of p-automatic sequences as columns of linear cellular automata[END_REF]. Indeed, it proves that any 3-automatic sequence (u n ) n≥0 on a binary alphabet occurs as a column of a (nonlinear) 2-state space-time diagram. On Fig. 1, we present an illustration for the 3-automatic sequence defined by u n = 1 T , where T = {3 n : n ∈ N}. We can use the method of Rowland and Yassawi [START_REF] Rowland | A characterization of p-automatic sequences as columns of linear cellular automata[END_REF] to obtain this sequence as a column of a linear CA with memory 2, with a finite initial configuration. Let us denote by φ(m, n) the value of the cell on column m ∈ Z and line n ∈ N. The local rule obtained to generate the space-time diagram is given, for all m ∈ Z and n ≥ 2, by: φ(m, n+2) = φ(m+1, n)+φ(m-2, n). In particular there are only 0's on all lines of even rank. For a better readability, we represent 0's by empty cells. Time axis is oriented upward. The four first lines correspond to initial conditions, and the sequence (u n ) n≥0 appears in the red framed column. Fig. 2 shows the space-time diagram after recoding. Fig. 1: Construction of the powers of three.

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Fig. 2: Construction of the powers of three, after recoding.

Remark 1. For a larger alphabet A = {0, . . . , q -1} with q > 2, if B is a finite set of symbols such that B A, it is also possible to recode the elements of B by blocks made by elements of A only. Let us assume that B = {0, . . . , k -1}, with k > q. We recode the k symbols of the alphabet B by words of length 2k -1, using the map ω : B → A 2k-1 defined as follows:

ω(0) = 00 • • • 0 2k-1 , ω(i) = i 0 • • • 0 i-1 1 0 • • • 0 2k-i-2 for i ∈ {1, . . . , q -1},
and

ω(i) = 0 0 • • • 0 i-1 1 0 • • • 0 2k-i-2 for i ∈ {q, . . . , k -1}.
Remark 2. In order to optimize the size of the blocks in the recoding, we can use some further results on non-overlapping codes [START_REF] Blackburn | Non-Overlapping Codes[END_REF]. Two words u and v (not necessarily distinct) are said to be overlapping if a non-empty proper prefix of u is equal to a non-empty proper suffix of v, or the converse. A code C ⊆ A n is non-overlapping if for all (not necessarily distinct) u, v ∈ C, the words u and v are non-overlapping. For an integer k ∈ {0, . . . , n -1}, we can build a non-overlapping code C (k) n of length n by considering the family of words c ∈ A n satisfying the following properties: c i = 0 for 1 i k, c k+1 = 1, c n = 1, and the sequence c k+2 , c k+3 , . . . , c n-1 does not contain k consecutive 0's (see [START_REF] Chee | Cross-Bifix-Free Codes Within a Constant Factor of Optimality[END_REF][START_REF] Gilbert | Synchronization of binary messages[END_REF][START_REF] Levenshteȋn | The maximal number of words in codes without overlap[END_REF]). Let us denote by F (k) n the number of codewords obtained, that is, the cardinality of C (k) n . One can check that the sequence (F

(k) n ) n≥1 satisfies the recurrence relation: F (k) n+k = F (k) n+k-1 + F (k) n+k-2 + • • • + F (k) n+1 + F (k)
n , which corresponds to the k-step Fibonacci sequence.

If B is an alphabet with k letters, we can match each letter k ≥ 1 with a codeword of a non-overlapping code, and match 0 with the block of 0 • • • 0 of the same size. The set obtained is no more exactly a non-overlapping code, but it is enough for our purpose, since we can determine locally the boundaries between blocks as soon as there is one occurence of 1, and the CA F is assumed to be 0-quiescent. For example, for a length n = 9, if we consider the words starting with two 0's, with a 1 at the third position and a 1 at the last position, the construction above provides 13 codewords, and with the recoding of the symbol 0 by a block of 0's, this allows to handle an alphabet of 14 letters. In comparison, with the map τ introduced earlier, as soon as the alphabet contains more than 5 letters, the length of the recoding is already larger than 9.

Remark 3. Prop. 1 can be strengthened in the following way. Let π : B → A define a symbolto-symbol projection from B to A. Assume that u ∈ B N occurs as a column of a CA on B with a finite initial configuration, and consider the sequence v = π(u), defined by v n = π(u n ) for all n ∈ N. Then, the sequence v occurs as a column of a CA on A with a finite initial configuration.

Polynomial sequences

In this section we present a CA that realizes the indicator function of any given polynomial P (under suitable conditions) in column 0, thus showing that 1 P (N) ∈ S. As seen in Section 1, these are typical sequences that are nonautomatic. By the results of Mazoyer and Terrier [START_REF] Mazoyer | Signals in one-dimensional cellular automata[END_REF], these sequences are constructible by CA, as the underlying set can be obtained by successive addition and multiplication operations. Our aim here is to generalize the geometric construction for squares due to Mazoyer and Terrier [11, To start with, let us shortly recall the construction concerning squares [START_REF] Delacourt | Directional dynamics along arbitrary curves in cellular automata[END_REF]. A signal (represented by an arrow, see Fig. 3) starts on level 1 to the NE-direction (right signal). Every time it meets the wall (represented by a vertical bar), the wall gets shifted by one cell to the right and the signal changes its direction from right to left. When the signal meets the 0-column, then a 1 appears, and it changes again its direction from left to right.

This construction can be generalized. We first show a way to generate from a constructed sequence the summatory sequence in column 0. Note that Mazoyer and Terrier proved a similar result for their geometric construction [START_REF] Mazoyer | Signals in one-dimensional cellular automata[END_REF]Corollary 2]. Proposition 2. Let f : N -→ N be an ultimately strictly increasing function, and let g denote its summatory sequence defined by g(n) = n k=0 f (k) for all n ≥ 0. Suppose that u = 1 f (N) belongs to S. Then v = 1 g(N) also belongs to S.

Proof. Let us call F the CA that constructs u = 1 f (N) and denote by G the CA that we are going to construct for v = 1 g(N) . For the proof, it is sufficient to treat the case when f is strictly increasing for all n ≥ 0, since we can treat a finite number of exceptions by introducing some appropriate initial conditions for G.

Suppose first that the following condition holds:

( ) 2g(i) > f (i + 1) for all i ≥ 1.
In a second step, we will show how to transform the construction in order to handle the case when ( ) is not satisfied. But for the sake of clearness, we first assume that ( ) holds. This condition allows to split the construction into three steps.

(i) Marking the columns:

The first step consists in marking the columns f (0), f (1), . . . , f (n), . . . For this, we start from the construction of u = 1 f (N) and for all integers i, we shift all cells of line i exactly i cells to the right, which corresponds to considering the space-time diagram of the CA σ • F (with the same initial configuration). Note that if the CA F constructing u is made of signals of different speeds, then we increase by 1 the speeds of all signals in order to get this marking of the column. In the construction of u = 1 f (N) , column 0 is marked by a 1 at lines f (0), f (1), . . . , f (n), . . ., therefore in the space-time diagram of G, lines f (0), f (1), . . . , f (n), . . . are marked but now in the columns f (0), f (1), . . . , f (n), . . ., that is on the diagonal of the new space-time diagram. Since f is strictly increasing, these columns are distinct. (ii) Constructing the walls:

Next, we define a new signal of speed 1 that runs on the diagonal of the space-time diagram. The intersections between this signal and the (marked) columns f (0), f (1), . . . , f (n), . . . send a new signal of speed 0 which are the walls. (iii) Passing from one hit on the column 0 to the next one:

Suppose we have a 1 on some line in column 0. We now show how to generate the next hit on column 0. Define a signal of speed 2 that moves to the right. When this signal meets a wall, that is a column f (i) for some integer i, the signal changes direction to the left (same absolute speed). When this signal meets the column 0 we mark a new 1. Depending on the parity, there are two ways for such a signal and a wall to meet. Either the two signals are in two columns side by side and then, the signal of speed -2 starts in the same column of the last symbol of the signal of speed 2 but one line above, or there is a cell between the two signals and then, the signal of speed -2 starts in the same column of the last symbol of the signal of speed 2 but two lines above. In both cases, we annihilate the wall after the signal has passed. Since f is strictly increasing, we do not have two walls in a same column, and the procedure is well-defined.

Let us now assume that we have so far constructed the first lines of the CA, in other words, we have a 1 in column 0 at lines f (0), f (0) + f (1), . . . , f (0) + • • • + f (i) for some i. We use the previous rules to continue the process. In particular, the 1 on the column 0 at line f (0)+• • •+f (i) sends a signal of speed 2 to the intersection with the wall in column f (i + 1). If f (i + 1) is odd, we are in the case where the two signals are in two columns side by side. The distance crossed by the signal of speed 2 is f (i+1)-1 2 from the initial 1 and the signal of speed -2 runs the same distance. We place the new 1 in column 0 one line above. Therefore, this new 1 is on the line:

f (0) + • • • + f (i) + 2 f (i + 1) -1 2 + 1 = f (0) + • • • + f (i) + f (i + 1). If f (i + 1
) is even, we are in the other case and the new 1 in column 0 is on the line:

f (0) + • • • + f (i) + f (i + 1) 2 -1 + 1 + f (i + 1) 2 -1 + 1 = f (0) + • • • + f (i) + f (i + 1).
Note that the condition ( ), which can be rewritten as:

f (0) + f (1) + . . . + f (i) + f (i + 1) 2 > f (i + 1),
ensures that the wall at column f (i + 1) has already been created when the signal of speed 2 arrives at column f (i + 1). Depending on the exact form of the function f , the condition ( ) is not always satisfied. In the case where ( ) is satisfied for n ≥ n 0 , in order to cope with this problem, one possibility consists in considering the first lines of the space-time diagram as initial conditions (which is not a loss of generality, since it amounts to introducing some auxiliary symbols in the initial configuration only, in such a way that they will fix the first few lines of the space-time diagram). Another possibility is to move the construction of the points f (i) under the main diagonal several lines lower, so that the walls appear sufficiently early. We can then use the procedure given above exactly in the same way. If there are infinitely many values of n such that ( ) is not satisfied, we use another strategy: we change the signals of speed 2 and -2 at the step (iii) to signals of speed 1 and -1. In this case, the sequence that is constructed is not 1 g(N) but 1 2g(N) . Nevertheless, we can recover 1 g(N) with the CA G 2 .

Example 2 (Construction of the characteristic sequence of the sum of the squares, see Fig. 3).

Let

f (n) = n 2 and g(n) = n k=0 k 2 = n(n + 1)(2n + 1)/6.
Here, the condition ( ) is satisfied for n ≥ 2, and for the construction of 1 g(N) , we consider the first three lines of the space-time diagram as an initial condition. In Example 2, a polynomial of degree 3 is realized. This suggests that the method can be generalized to obtain the characteristic sequence of any polynomial with higher degree as a column of a CA. To begin with, we show by an explicit construction that the characteristic sequence of the cubes belongs again to S.

Example 3 (Construction of the characteristic sequence of the cubes, see Fig. 4). For all n ∈ N we have (n + 1)

3 -n 3 = 3n 2 + 3n + 1. With the construction of the squares, it is straightforward to obtain the characteristic sequence of 3n 2 : In fact, it suffices to divide the speed of signals of speed ±1 by 3 (see Fig. 4, left). The red, blue and black cells in column 0 correspond to the term 3n . Thus, the construction of the characteristic sequence of the polynomial 3n 2 + 3n + 1 follows. The eight first lines are initial conditions. Now, to obtain the characteristic sequence of the cubes (see Fig. 4, right), we observe that for all n 1, n-1 k=0 (k + 1) 3 -k 3 = n 3 and we use the construction given in the proof of Prop. 2. The first five lines are initial conditions. The construction under the diagonal is moved three lines down. We finally arrive at our main result.

Theorem 1. Let P (X) ∈ Q[X] denote a polynomial of degree d ≥ 1 with P (N) ⊂ N. Then the sequence u = 1 P (N) belongs to S and can be realized by the hitting of one single signal in column 0.

Proof. The result of Theorem 1 is clear for all polynomials of degree 1. Indeed, if P has the form P (X) = aX + b with a ∈ N, b ∈ Z, one can construct the sequence by the trajectory of a signal that hits a wall in column a/2 (we fix the initial conditions in order to take into account the translation of b). Note that we can deal with rational coefficients by multiplying and dividing accordingly the speed of the symbols. Suppose now that the statement is true for all polynomials of degree k < d, for some d ≥ 2. We show that we can realize any polynomial P of degree d with only one hitting in column 0. For this purpose, we observe that Q(X) = P (X + 1) -P (X) is a polynomial of degree at most d -1. Furthermore, since P (N) ⊂ N, the leading coefficient of P is positive, so that there exists c ∈ N, depending only on P , such that the polynomial Q

(X) = Q(X + c) satisfies Q(N) ⊂ N. P (n) -P (0) = n-1 k=0 (P (k + 1) -P (k)) = n-1 k=0 Q(k)
By induction, we know that 1 Q(N) is constructible. Taking care of the finite initial conditions due to the introduction of the integer c and to the occurrence of P (0), Prop. 2 implies that 1 P (N) belongs to S, and is realized by the hitting of just one signal.

Fibonacci word

The Fibonacci sequence is the recursive sequence defined by F 0 = 0, F 1 = 1, and ∀n ≥ 0, F n+2 = F n+1 + F n . We denote by F the set of numbers that appear in the Fibonacci sequence, that is, F = {F n : n ∈ N}. We propose a construction of the sequence u = 1 F , which by definition, satisfies: u n = 1 ⇐⇒ ∃k ∈ N, n = F k . Our construction presents some similarities with the one proposed by Mazoyer and Terrier for general linear recursions [START_REF] Mazoyer | Signals in one-dimensional cellular automata[END_REF]Prop. 4]. Proposition 3. The indicator sequence 1 F of Fibonacci numbers belongs to S.

Proof. We propose an explicit construction that uses signals of speed 0 (walls), ±1, and 2. Let us assume that on line F n , we have marked the positions 0, F n-2 , F n-1 and F n . We show how to produce the same marking at time F n+1 . In particular, the procedure will enable us to spot the points of ordinate F n in the column 0 of the space-time diagram. The dynamics is as follows.

-From point (0, F n ), we send a signal of speed 1.

-From point (F n-2 , F n ) we send a signal of speed 1 and one of speed 2.

-From point (F n-1 , F n ) we send a signal of speed 0 (wall) and one of speed -1.

-From point (F n , F n ) we send a signal of speed 0 (wall) and one of speed 1.

Using elementary arguments based only on the definition of the Fibonacci sequence, one can show that the intersections of these different signals on line F n+1 give points at positions 0, F n-1 , F n and F n+1 , as illustrated on Fig. 5. In order to complete the construction, one only has to choose appropriate initialisation symbols.

The Fibonacci word is the morphic sequence v ∈ A N which is the unique fixed point of the substitution σ defined by 0 → 01 and 1 → 0. Proof (sketch). It follows from the definition that for any n ≥ 1, the length of the word w n is equal to F n . Furthermore, one can check that for any n ≥ 1, we have:

w n+1 = w n • w n-1 = w n-1 • w n-2 • w n-2 • w n-3 = w n-2 • w n-3 • w n-2 wn • w n-2 • w n-3 ,
where the symbol • represents the concatenation of words. It follows that if the word w n has already been computed, in order to obtain the word w n+1 , one can first concatenate after w n the sequence w n-2 , which is the one that appears at the last F n-2 positions of w n , and then the sequence w n-3 , which appears in w n between positions F n-2 and F n-2 + F n-3 = F n-1 . This can be done with a finite state cellular automaton: the block w n-2 appearing at the end of w n is translated to the right until reaching a wall placed at position F n-2 /2 and then translated to the left. And in the same way, the block w n-3 appearing between positions F n-2 and F n-1 is translated to the right until reaching a wall placed at position (F n-2 + F n-1 )/2 = F n /2 and then translated to the left. Note that the walls at positions F n-2 /2 and (F n-2 + F n-1 )/2 can be computed without much difficulty. The construction of the wall at position F n-2 /2 appears on Fig. 5. For the construction of the wall at position (F n-2 + F n-1 )/2, one can send signals of respective speeds 1 and -1 from positions F n-2 and F n-1 at time F n-1 .

Other computable sequences and open questions

Since S is countable, whereas A N is uncountable, there exist sequences of A N that do not belong to S. A sequence (u n ) n≥0 ∈ A N is computable if there exists an algorithm, or more formally, a Turing machine, which on the input n, calculates u n , for any n ≥ 0. In other words, this means that the set {n ∈ N : u n = 1} is accepted by a Turing machine that always halts. It follows easily from the definition that all the sequences of S are computable. Next proposition gives an elementary proof of the fact that S is strictly contained in the set of computable sequences, using a diagonal argument. We refer to the article of Mazoyer and Terrier [START_REF] Mazoyer | Signals in one-dimensional cellular automata[END_REF]Prop. 12 and 13] for further characterizations of S in terms of computability. Proposition 5. There exist computable sequences that do not belong to S.

Fig. 5 ]

 5 , and used again by Delacourt, Poupet, Sablik and Theyssier [5, Section 3], that involves the notion of walls (i.e. signals of speed 0) and of directed left and right signals. While the constructions proposed by Mazoyer and Terrier for polynomials of higher degree use several signals zigzaging between the trajectories of other signals and the resulting sequence, our construction allows to realize 1 P (N) by hits of just one single signal at column 0.

Fig. 3 :

 3 Fig.3: CA for squares[START_REF] Delacourt | Directional dynamics along arbitrary curves in cellular automata[END_REF] (left) and for the sum of squares (right).

Fig. 4 :

 4 Fig. 4: CA for the difference of cubes (left) and for the cubes (right).

Fig. 5 :

 5 Fig. 5: Construction of Fibonacci numbers and of the Fibonacci word.

Acknowledgements. The authors thank N. Fatès and E. Jeandel for fruitful discussions and the referees for valuable comments.

Proof. For an integer r ≥ 0, let us denote by F r the set of CA F : A Z → A Z of radius r. The set F r is a finite set, of cardinality 2 2r+1 , and it can be enumerated in a canonical way, for example using Wolfram code [START_REF] Wolfram | Statistical mechanics of cellular automata[END_REF]. So, the set F = ∪ r≥0 F r of all CA F : A Z → A Z is countable, and one can define a computable surjection φ : N → F.

The set C 0 (A) of finite configurations on A Z is also countable, and can be enumerated by a computable surjection ψ : N → C 0 (A). Let now τ : N → N 2 be a computable surjection, and let us consider the following map:

The map Π above is surjective. Let us consider the sequence (u n ) n≥0 defined by u n = 1 -Π(n) n , for any n ≥ 0. This sequence is computable, and does not belong to the image of Π, so it does not belong to S.

The proposition above provides an example of sequence that cannot be obtained by a CA. Nevertheless, this sequence has an abstract form, and it is an open problem to exhibit a more concrete example of (computable) sequence that does not belong to S. We conclude with some open questions.

1. We have seen that the Fibonacci word belongs to S. More generally, does any morphic sequence belong to S? Is there a canonical way to construct the CA using directly the form of the defining morphism of the sequence, at least for k-step reccurences over words? 2. A sequence of A N is said to be normal if all finite strings of equal length occur with equal asymptotic frequency. None of the sequences that we have evocated here is normal. Is it possible to come up with a CA that gives a normal sequence such as the Champernowne sequence (concatenation of natural numbers in base 10 : 12345678910111213. . . ), or the Copeland-Erdős sequence (concatenation of prime numbers in base 10 : 2357111317192329. . . )? 3. Do the binary expansions of √ 2 = (1.011010100000100 . . .) or π = (11.00100100001111 . . .) belong to S? Note that it is not known whether the binary digits of these two constants give rise to normal sequences. 4. There is a close connection between one-dimensional linear CA and p-automatic sequences. Do there exist analogous statements for higher dimensional linear CA? Also, is it possible to realize any multivariate polynomial with the help of a suitable higher dimensional (nonlinear) CA? 5. Linear CA provide examples of permutive CA. What kind of sequences can be obtained with permutive CA?


INTRODUCTION

Shock waves play a major role in inertial connement fusion (ICF) as a process to control the target implosion and fuel heating [START_REF] Atzeni | The Physics of Inertial Fusion[END_REF]. The shocks are excited with temporally shaped laser pulses that ablate the outer surface of the shell and launch a shock propagating inward through the target material. In contrast to a cold piston in classical hydrodynamics, the ablation pressure is dened by the vaporization rate of the shell material, which in turn is dened by the energy transport from the laser-energy deposition zone in an underdense hot plasma to a relatively cold ablation zone. Under the ICF conditions, where the laser intensities exceed 10 14 W/cm 2 , the electrons dominate the energy transport. The energy ux depends strongly on the distribution function of the electrons that are heated and accelerated in the laser absorption zone. It is well known that the classical model of the electron diusion transport developed for plasmas by Spitzer and Härm [START_REF] Spitzer | Transport Phenomena in a Completely Ionized Gas[END_REF] and Braginskii [START_REF] Braginskii | Transport processes in a plasma[END_REF] is not sucient: the mean free path of energycarrying electrons could be comparable with the thickness of the transport zone. Nonlocal eects must therefore to be accounted for. The simplest solution consists of introducing a limiter of the diusion heat ux [START_REF] Malone | Indications of strongly ux-limited electron thermal conduction in laser-target experiments[END_REF], but more-accurate nonlocal models have also been developed [START_REF] Schurtz | A nonlocal electron conduction model for multidimensional radiation hydrodynamics codes[END_REF].

The nonlocal models provide a good description of the electron energy transport in the cases where the electron heating in the laser eld is collisional and the electron distribution function only weakly departs from the local thermal equilibrium. This is not the case, however, for high laser intensities exceeding 10 15 W/cm 2 , where parametric instabilities are excited. Collisionless absorption of the daughter plasma waves results in the production of energetic electrons with characteristic energies exceeding the ambient electron temperature by 10× to 20× or more. They can propagate beyond the ablation zone and deposit their energy directly upstream or downstream of the shock. Depending on the ratio of the electron mean free path to the distance to the shock front, the hot electrons may either increase or decrease the shock strength [START_REF] Gus'kov | Ablation pressure driven by an energetic electron beam in a dense plasma[END_REF][START_REF] Ribeyre | Dense plasma heating and Gbar shock formation by a high intensity ux of energetic electrons[END_REF].

The eect of hot electrons is particularly important for the shock-ignition ICF scheme [START_REF] Betti | Shock ignition of thermonuclear fuel with high areal density[END_REF] where a strong shock igniting the fuel is launched at the end of the implosion phase by a strong laser spike with an intensity of the order of 10 16 W/cm 2 . Strong shock experiments have been conducted in the planar and spherical geometries [START_REF] Batani | Physics issues for shock ignition[END_REF], but the shock pressure was not measured directly. It was evaluated with radiationhydrodynamics codes predicting the time of its propagation across the sample. While such a numerical procedure is constrained by additional measurements of the hot-electron fraction and laser absorption, it is not suciently accurate because of a too-simple model of the physics of laserplasma interaction and hot-electron kinetics.

The record ablation and shock pressures were reported in the experiments preformed at the Omega Laser Facility [START_REF] Boehly | Initial performance results of the OMEGA laser system[END_REF] in the converging geometry [START_REF] Nora | Gigabar spherical shock generation on the OMEGA laser[END_REF][START_REF] Theobald | Spherical strong-shock generation for shock-ignition inertial fusion[END_REF]. The 400-to 500-µm-diam solid plastic spheres were irradiated with 60 OMEGA laser beams with a total energy of 22 to 26 kJ, achieving a homogeneous irradiation with an average overlapping intensity of 5 × 10 15 W/cm 2 at a wavelength of 351 nm. The 1-ns main pulse was preceded with a 1-ns prepulse of a lower intensity mimicking the plasma corona conditions in the shock-ignition scheme. The laser-driven shock was detected by a short x-ray ash emitted at the moment when the converging shock reached the target center. An earlier ash time corresponds to a stronger shock, higher shock velocity, and higher shock pressure. The shortest ash times were correlated with the generation of a large number of energetic electrons, providing a clear indication of their contribution to shock generation or amplication.

A quantitative evaluation of the shock pressure was performed using numerical simulations with the radiation hydrodynamics code LILAC [START_REF] Delettrez | Laboratory for Laser Energetics[END_REF]. One approach was to adjust the value of the ux limiter [START_REF] Malone | Indications of strongly ux-limited electron thermal conduction in laser-target experiments[END_REF] to match the x-ray ash time with the observation. This simplied description does not capture important details related to the localization of the energy deposition by hot electrons that can cause target preheat upstream of the shock. Additional simulations were carried out with a xed ux limiter and a hot-electron transport package [START_REF] Delettrez | Laboratory for Laser Energetics[END_REF] to model the interaction [START_REF] Nora | Gigabar spherical shock generation on the OMEGA laser[END_REF]. A fraction of the laser energy reaching the quarter-critical (n c /4) surface was converted into hot electrons with a single-temperature Maxwellian distribution and 2π forward divergence. The electrons were propagated in straight lines into the target with the stopping range calculated by the model described in Ref. [START_REF] Solodov | Stopping power and range of energetic electrons in dense plasmas of fast-ignition fusion targets[END_REF]. The measured hot-electron fraction and temperature were used as input in the simulations as well as the temporal dependence of the hot-electron production rate. An additional constraint came from the measured absorbed laser power. This model does not selfconsistently describe the laser-plasma interaction in the underdense plasma but rather prescribes a certain energy conversion into hot electrons at n c /4.

A model of laser-energy deposition that takes into account the excitation of parametric instabilities in the plasma corona and hot-electron production has been implemented recently in the radiationhydrodynamics code CHIC [START_REF] Breil | Multi-material ALE computation in Inertial Connement Fusion code CHIC[END_REF].

In this model, the standard ray-tracing scheme describing the laser propagation in the framework of geometrical optics [START_REF] Kaiser | Laser ray tracing and power deposition on an unstructured three-dimensional grid[END_REF] is replaced with the paraxial complex geometrical optics (PCGO) [START_REF] Colaïtis | Towards modeling of nonlinear laser-plasma interactions with hydrocodes: the thick rays approach[END_REF][START_REF] Colaïtis | Multiscale description of the laser-plasma interaction: application to the physics of shock ignition in inertial connement fusion[END_REF], where realistic laser beams are represented as a combination of Gaussian beamlets. The PCGO model provides access to the laser intensity in any location in plasma and is well suited to account for nonlinear processes in plasma. The model accounts for the resonant absorption (RAB), stimulated Raman scattering (SRS), and two-plasmon decay (TPD) [START_REF] Colaïtis | Coupled hydrodynamic model for laser-plasma interaction and hot electron generation[END_REF]. Each of these processes is a source of energetic electrons, which are characterized by a temperature, density, direction and angular divergence. The electrons from the dierent sources propagate through the plasma, scatter, and deposit their energy according to the classical continuous-slowing-down theory. The model assures the energy conservation at each time step.

First comparisons of the PCGO model with experiments conducted on the PALS Laser Facility in a planar geometry show quite good agreement for both the hot-electron fraction and temperature [START_REF] Colaïtis | Coupled hydrodynamic model for laser-plasma interaction and hot electron generation[END_REF] and the scaling with the laser intensity [START_REF] Cristoforetti | Experimental observation of parametric instabilities at laser intensities relevant for shock ignition[END_REF]. It was demonstrated that hot electrons generated by RAB and SRS processes have a relatively low energy, deposit their energy downstream of the shock front, and increase the shock pressure and shock velocity. In contrast, the TPD-generated electrons are more energetic; they penetrate upstream of the shock and preheat the target, which results in a premature expansion. Strong-shock experiments [START_REF] Nora | Gigabar spherical shock generation on the OMEGA laser[END_REF][START_REF] Theobald | Spherical strong-shock generation for shock-ignition inertial fusion[END_REF] provide a possibility for testing the PCGO model for the rst time in the spherical converging geometry and compare it with well-diagnosed data. In what follows, we recall the major experimental results obtained in the strong-shock campaign, describe the principal characteristics of the PCGO model, and present the results of numerical simulations demonstrating the role of hot electrons in the generation and propagation of a strong shock in a convergent geometry. This analysis provides a more-accurate evaluation of the shock pressure under the conditions relevant to the shock-ignition scheme.

II. EXPERIMENTAL SETUP AND NUMERICAL TOOLS

A.

Experimental results of the strong-shock campaign A detailed description of the experiment is presented in Ref. [START_REF] Theobald | Spherical strong-shock generation for shock-ignition inertial fusion[END_REF]. The main goal was to demonstrate the possibility of generating a shock with a downstream pressure exceeding 300 Mbar in the conditions pertinent to the shock-ignition scheme. OMEGA's 60 laser beams were focused at a wavelength of 351 nm on a solid spherical target with an average intensity of 5 × 10 15 W/cm 2 . The laser beams smoothed with phase plates could also be temporally smoothed by spectral dispersion (SSD). In some shots the SSD was turned o, thereby creating a static small-scale intensity pattern at the target surface. This created local zones of high intensity, enhancing the hot-electron production by exciting parametric instabilities. The laser-energy balance was measured with backscatter diagnostics providing the absorbed laser power and time-resolved diagnostics provided temporally streaked spectra of the SRS and the stimulated Brillouin scattering (SBS). SBS is responsible for ∼2% to 3% of the reected energy. This fraction did not change signicantly between shots with or without SSD. In contrast, the SRS signal was very sensitive to laser beam smoothing. The shots without SSD showed 5× more SRS scattered light, which persisted during the entire pulse. Figure 1(a) shows a typical temporal shape of the laser power (gray curve) along with the measured absorbed power (red curve) for the shot with temporally smoothed laser beams. The time integrated absorption fraction, α, was measured to be 61±3% for this shot (SSD on), which produced a small fraction of hot electrons (3%). The quantity α is dened as α = 1 -E 351 /E L , where E 351 is the measured backscattered energy around the laser wavelength and E L is the measured incident laser energy. Contributions from backscattered SRS were not measured and are not taken into account in α. Averaging over multiple SSD-on shots, α is slightly higher with 62 ± 4%. The laser absorption for the similar shot with SSD turned o is shown in Fig. 1(b). This shot produced a much higher hot electron fraction (∼9%) and exhibited a larger α (73±5%). The average α over multiple SSD-o shots was 71±3%. The blue and black curves in Fig. 1(b) show the absorption calculated for the shot 73648 with the code CHIC with and without hot electrons, respectively, as explained in the next section. A low-power prepulse operating during the rst nanosecond had an intensity below 10 14 W/cm 2 . According to the numerical simulations presented below, it produced a plasma corona with a temperature of 600 eV and a density scale length of 100 µm in the near-quarter-critical density zone where nonlinear processes may take place when the 1-ns main pulse interacts with the preformed plasma.

The target had an outer diameter of 480 µm for shot 72676 and 496 µm for shot 73648. The target was made out of plastic (CH) that was doped with 5% of titanium to detect hot electrons and the shock collapse time. The outside was covered with a pure-CH ablator layer with thicknesses of 34.7 µm and 33.9 µm, respectively. Experiments were also performed with other ablators, but here we consider only the results obtained from CH, which led to the largest number of hot electrons. Other materials were found to be less ecient for hot-electron production [START_REF] Theobald | Enhanced hot-electron production and strong-shock generation in hydrogen rich ablators for shock ignition[END_REF]. The temperature of hot electrons was in the 60-to 70-keV range, increasing by ∼10% when the SSD was turned o. In contrast, the fraction of laser energy transferred to hot electrons increased signicantly from 3.3% when SSD was on to 7.6% when SSD was o. These values represent averages over multiple shots. The one-to-one correlation between the SRS signal and hot-electron production unambiguously points out to SRS as the origin of hot-electron generation.

The x-ray emission was measured with two instruments an x-ray framing camera (XRFC) and a streaked x-ray spectrometer (SXS) in the 3-to 7-keV range with a time resolution of 50 ps. These instruments detected the emission originating from the target surface and a ash from the target center at the moment of shock collapse. The hot electrons were characterized with three instruments: a four-channel hard x-ray detector (HXRD) having a temporal resolution of 100 ps in the energy range between 20 and 80 keV, and two time-integrated diagnostics covering an energy range up to 2 MeV. These instruments measured the hot-electron total energy and temperature.

Emission near half of the laser frequency was detected in all shots, indicating excitation of TPD near n c /4. Its signal was much weaker, however, than SRS and did not depend on the laser beam temporal smoothing. TPD is therefore expected to make a minor contribution to the hot electron source, but it generates more-energetic electrons which may contribute to target preheat.

B.

Radiation-hydrodynamic code CHIC

The experiment was modeled with the radiation-hydrodynamics code CHIC [START_REF] Breil | Multi-material ALE computation in Inertial Connement Fusion code CHIC[END_REF]. CHIC is a 2-D (axial symmetry) arbitrary Lagrangian-Eulerian (ALE) code based on the second-order Godunov numerical scheme. It includes twotemperature (electron and ion) single-uid hydrodynamics, a Thomas-Fermi ionization model, and SESAM E tables for the equation of state. The electron and ion energy transport is described by the Spitzer-Härm model with an electron ux limiter and nonlocal electron transport model [START_REF] Schurtz | A nonlocal electron conduction model for multidimensional radiation hydrodynamics codes[END_REF]. The radiation transport is described by a multigroup model with the tabulated opacities calculated in the approximation of local thermodynamic equilibrium. In the original version of CHIC, the laser-energy deposition is described by a 3-D ray-tracing model based on the classical geometrical optics [START_REF] Kaiser | Laser ray tracing and power deposition on an unstructured three-dimensional grid[END_REF]. This model accounts for the laser beam refraction in a spatially inhomogeneous plasma and for the collisional absorption by electrons (inverse bremsstrahlung), but it does not fully account for diraction and is ill suited to compute the laser intensity in plasma [START_REF] Colaïtis | Multiscale description of the laser-plasma interaction: application to the physics of shock ignition in inertial connement fusion[END_REF].

PCGO [START_REF] Kravtsov | Theory of Diraction, Heuristic Approaches, Alpha Science Series on Wave Phenomena[END_REF] describes the propagation of a Gaussian beam with two equations: one describes the evolution of the central ray according to the geometrical optics; the other is a complex matrix describing the beam width and the wavefront curvature. In the model implemented in CHIC [START_REF] Colaïtis | Towards modeling of nonlinear laser-plasma interactions with hydrocodes: the thick rays approach[END_REF], realistic laser beams are represented by a combination of Gaussian beamlets, each of them described by the PCGO equations. The PCGO model provides access to the laser intensity in any location in a plasma and is well suited to account for nonlinear processes in a plasma. The present 2-D version of PCGO describes the beamlet diraction in only one transverse direction. The laser collisional absorption is complemented with the resonant absorption (RAB) at the ray's turning point, the TPD instability at the n c /4, and the SRS instability, which was localized near the zone where the plasma density was 20% of the critical density [START_REF] Colaïtis | Coupled hydrodynamic model for laser-plasma interaction and hot electron generation[END_REF]. The TPD and SRS processes are activated locally as soon as the corresponding threshold conditions are fullled. The model predicts the power fraction converted from the incident electromagnetic eld to TPD hot electrons. This power is locally subtracted from the optical beamlets and used as input for the hot-electrons beams, ensuring energy conservation. It is assumed that half of the energy is emitted in forward-propagating hot electrons, and the other half in backward-propagating hot electrons. For the SRS process, the power locally subtracted from the optical beamlets is equally divided between backward-propagating light and forward-propagating hot electrons. It is assumed that all three sources produce hot electrons with exponential distribution in energy characterized by a corresponding temperature. The RAB and SRS electrons are generated as collimated beams in the direction of the density gradient in the case of RAB and in the local direction of the pump beamlet in the case of SRS [START_REF] Rousseaux | [END_REF], respectively.

Given the natural spread of wave vectors at the point of emission of SRS (arising from refraction and beam f number), the overall hot-electron emission from SRS is not monodirectional. The TPD electrons are generated in a 90 • wide cone symmetrically with respect to the direction of the pump beamlet. The spatially integrated divergence of the hot electrons (from both TPD and SRS) predicted by the code is in agreement with data from experiments conducted in spherical geometry [START_REF] Yaakobi | Measurements of the divergence of fast electrons in laser-irradiated spherical targets[END_REF]. The instability conditions and hot-electron sources are updated at each time step assuming that the nonlinear processes are suciently rapid to bring the parametric instabilities to saturation on each time step of hydrodynamic evolution (∼ 1 ps).

The hot-electron beam propagation is described in the continuous slowing-down approximation accounting also for pitch angle scattering [START_REF] Li | Stopping, straggling, and blooming of directed energetic electrons in hydrogenic and arbitrary-Z plasmas[END_REF]. The distribution of electrons at the source is split in groups on energy and angle (in the case of TPD) and each group propagates along a straight line. The electrons that reach the plasma edge are allowed to exit, their energy being lost. The electron transport was considered in the stationary approximation, assuming that the electron life time is shorter than the hydrodynamic time step.

C.

CHIC simulations without hot electrons

The strong-shock experiment was modeled with the radiationhydrodynamics code LILAC [START_REF] Delettrez | Laboratory for Laser Energetics[END_REF], which has been used for a long time at LLE to model laser-plasma interaction experiments at lower intensities. As described above, the limitations in LILAC simulations are overcome here with CHIC by providing a model of hot-electron generation in the plasma corona. To ensure that both codes provide the same description of large-scale plasma hydrodynamics, we performed CHIC simulations for the same laser-plasma interaction physics; i.e., the processes RAB, TPD and SRS were turned o and no hot electrons were generated.

A simulation was performed for shot 73648 (which is equivalent to the shot 72676) but neglected the contribution of hot electrons. The target was a 428-µm-diam sphere of the CH doped with 5% of titanium of 1.72-g/cm 3 density covered with a 34-µm-thick pure-CH layer with a 1.04-g/cm 3 density. Since the numerical schemes are dierent, the same physics may correspond to a dierent choice of ux limiters. It was found that numerical simulations with both codes gave quite similar results for the shock timing if one used a ux limiter of 8% in LILAC and 4% in CHIC.

Figure 1(b) shows the temporal proles of the incident laser pulse (gray) and absorbed power measured (red) and calculated with CHIC (black). The total incident energy was 23.8 kJ. The absorption prole obtained with CHIC is quite close to the measured prole in shot 72676. The calculated absorption of 60% is in agreement with the experimental value of 61 ± 3% for this SSD-on shot but is smaller than the measured average α of 71 ± 3% in SSD-o shots. The absorption calculated with LILAC is 57%, slightly lower than the experimental value for shot 72676. t = 0.9 ns (black), 1.2 ns (red), 1.5 ns (green), 1.8 ns (blue) and 2.1 ns (violet). The time moments correspond to the power proles shown in Fig. 1.

Figure 2 shows the density and pressure proles from CHIC in the time interval from 0.9 to 2.1 ns. Similar proles have been obtained from LILAC. Despite the slight dierence in the calculated absorbed energy, both codes give the same shock collapse time of 2.8 ns. At the time when the main pulse arrives, t = 1 ns, the shock created by the prepulse has already traveled through the ablator and entered the denser part of the target. Its pressure is at a relatively modest level of 20 to 30 Mbar (black proles in Fig. 2). The shock created by the main pulse is much stronger. Its pressure rises above 200 Mbar when it catches up with the rst shock at 1.5 ns. The pressure enhances to ∼300 Mbar because of the convergent eect at the end of the laser pulse. The shock continues progressing to the center after the end of the laser pulse, and the pressure attains the value of a few Gbar at the moment of collapse.

III. NUMERICAL SIMULATIONS OF THE CONVERGING SHOCK

The simulations shown in the previous section demonstrate that CHIC provides similar results to LILAC in the hydrodynamic regime, where the nonlinear laserplasma interaction processes and hot electrons are not important. We consider these results as representative for the case where the SSD was turned on. In contrast, in the case of SSD o, there are strong uctuations of laser intensity in plasma, and parametric instabilities can be excited in speckles.

Our PCGO model accounts for the SRS and TPD excitation and subsequent generation of the hot electrons. The enhanced laser absorption and hot-electron production facilitate the generation of a stronger shock. It propagates faster and arrives 390 ps earlier at the target center according to simulations. A correlation of the enhanced SRS activity with the hard x-ray diagnostics shows (9±1%) of the incident laser energy converted into hot electrons, indicating the role of hot electrons in shock acceleration. Simulations presented in this section establish relations between the SRS, hot-electron generation, and shock dynamics.

Numerical simulations with CHIC were conducted in a 1-D spherically-symmetric conguration with an electron ux limiter of 4% (see Section II C) and with the PCGO module switched on. The previous parameters of the PCGO model were chosen based on a comparison with experiments in the planar geometry [START_REF] Colaïtis | Coupled hydrodynamic model for laser-plasma interaction and hot electron generation[END_REF]. The hot-electron beamlets propagate in the meridional plane with a xed transverse width.

A.

Energy balance

Simulation results shown in the previous section provide information on laserplasma interaction conditions. At the moment the main pulse arrives, the plasma is expanded and the critical density is located 240 µm from the target center, while n c /4 is 300 µm away. The characteristic density scale length at this latter point is 100 µm, and the electron temperature, which is 0.6 keV before the main pulse arrives, increases rapidly to 3.8 keV. These parameters allow us to estimate the contribution of parametric instabilities in the laser-plasma absorption. The collisional absorption of a laser beam on such a plasma prole is ∼50%; i.e., the laser intensity near n c /4 is ∼70% of the incident intensity or 3.5 × 10 15 W/cm 2 . This value is signicantly larger than the thresholds for the SRS and TPD instabilities.

Using the expressions for the SRS and TPD thresholds (see, for example, Ref. [START_REF] Batani | Physics issues for shock ignition[END_REF] and references therein), one nds that the laser's prepulse intensity stays below the thresholds of both instabilities. In that case, laser absorption is caused only by the electron collisions. At the moment the main pulse arrives, the SRS threshold is exceeded by 10×, while the TPD threshold is exceeded by only 5×. This ratio between the two instabilities is explained by the fact that the SRS threshold depends only on the density gradient and is mostly unaected by the main pulse's arrival. In contrast, the TPD threshold is proportional to the electron temperature, which increases rapidly upon the main pulse's arrival. Therefore, rapid plasma heating favors SRS and suppresses TPD.

The repartition of the absorbed energy is shown in Fig. 3. The contribution of the resonant absorption is only important at the beginning of prepulse when the density prole is steep. However, the energy of RAB-generated electrons is relatively small throughout the laser pulse and its contribution to the energy balance is less than 2%. The SRS dominates the interaction. It starts at the arrival of the main pulse and corresponds to an instantaneous conversion of 6% of the laser power into electrons with the temperature of 40 keV. The TPD contribution in the energy balance is smaller, and only half of the electrons are directed to the dense plasma. The second half is directed outwards and does not contribute to absorption. However, the TPD-generated electrons are more energetic, their temperature is ∼ 70 keV, and consequently their mean free path is more than 3× longer than for the SRS electrons.

The total balance of absorbed energy in the simulations is as follows: RAB 1.6%, SRS 5.4%, TPD 2% and collisional absorption 60% (i.e., 69% of the incident laser energy). This is compared to the measured α of 73 ± 5%, as shown in Fig. 1(b). A small fraction of stimulated Brillouin scattering amounting to 3% in the experiment is not accounted for in our simulation. There is also a slight dierence in the hot-electron dynamics. The hot electrons in the experiment [START_REF] Theobald | Enhanced hot-electron production and strong-shock generation in hydrogen rich ablators for shock ignition[END_REF] were observed with a delay of ∼200 ps with respect to the main laser pulse and their instantaneous conversion fraction is larger than calculated. This demonstrates the limits of the PCGO model, which does not account for the temporal evolution of parametric instabilities (other than related to hydrodynamic eects), assuming that the nonlinear saturation and energy transfer take place on a time scale shorter than one time step in the hydrodynamic simulation (of the order of 1 ps). This energy balance can be compared with the case where the parametric instabilities were switched o; the total absorption is then calculated to be 61%. Therefore, the parametric instabilities accounted for slightly reduce the collisional absorption (as smaller laser power attains the near-critical densities) but signicantly increase the total absorbed power resulting from the generation of hot electrons.

The reected energy in the CHICPCGO simulation is 31%. It comprises ∼ 11% SRS and 20% at the main wavelength. The PCGO model does not account for the SBS, which was ∼3% in the experiment. In the simulations this fraction was subtracted from the incident laser energy. Accounting for the SBS contribution, the calculated reected energy fraction at the main wavelength is 23%, which is in reasonable agreement with the measured reection of 27±5%. Although the PCGO model was not specially tuned for this particular experiment, it provides good agreement with the measured shock ash time for the SSD-o case, as discussed below. The x-ray emission of titanium ions in the 3-to 5-keV energy range was calculated with a spectral code TRANSPEC [START_REF] Peyrusse | A model for the simulation of non-equilibrium line transfer in laboratory plasmas[END_REF] by post-processing the hydrodynamic proles calculated with CHIC. The temporal evolution of the x-ray emission shown in the graph of Fig. 4 has three parts: The rst weak emission peak comes at the prepulse arrival, resulting from plasma emission created at the target surface. The second one is correlated with the main pulse. This is also emission of the coronal plasma but with intensity an order of magnitude larger because of higher plasma temperature. There is no measurable contribution of hot electrons at that time. A signicant dierence can be seen only in the last ash, which is caused by the emission of titanium ions (He-α line at 4.7 keV). The intensity of the ash is three orders of magnitude higher, and the presence of hot electrons increases the ash intensity in agreement with experiments [START_REF] Theobald | Spherical strong-shock generation for shock-ignition inertial fusion[END_REF]. The calculated ash time of 2436 ps agrees with the experimentally measured ash time of 2440 ± 50 ps for the case without SSD. The case with SSD was modeled with the PCGO model by simply turning o the parametric instability modules, which is an oversimplication since there is still some degree of hot-electron generation observed experimentally in those cases. Without the hot-electrons modules, the PCGO model does not succeed in reproducing the experimentally measured ash time of 2500 ps for the shot with SSD, predicting a ash time at 2818 ps (blue curve in Fig. 4). This shows that the lower amount of hot electrons observed in that case (∼3%) is also important and should be accounted for. This case can be considered in the future when the PCGO model will include the SSD option. Nevertheless, the large dierence observed in modeling results between the cases with and without hot electrons highlights the importance of consistently accounting for those in radiationhydrodynamics codes.

B.

Shock-wave dynamics Numerical simulations also provide information on the contribution of hot electrons to shock-wave dynamics. Figure 5 shows the spatial and temporal evolution of the pressure in the target obtained with and without hot electrons. The rst shock with the amplitude of 30 Mbar crosses the ablator and enters the inner target at t = 0.8 ns. The main pulse arriving at t = 1 ns generates a stronger shock with a pressure of 130 to 150 Mbar, while the ablation pressure is maintained at a level of 110 Mbar. In the case without hot electrons, this shock enters the main target and merges with the rst shock at 1.5 ns. During merging, the shock pressure slightly decreases and then increases again because of the convergence eect. The shock collapses in the center at 2.8 ns. The temporal evolution of the pressure at the shock front and the ablation pressure is shown in Fig. 6. The position of the ablation surface is dened by zero of the hydrodynamic velocity. It separates the imploding inner part of the target and the expanding ablated plasma. The calculated ablation pressures creating both rst and second shocks are ∼30% smaller compared to the values expected from the scaling relations [START_REF] Atzeni | The Physics of Inertial Fusion[END_REF]:

P abl = 12(A/2Z) 1/3 (I abs /λ) 2/3 Mbar,
where A and Z are the average mass number and charge of the target, respectively, λ is the laser wavelength in microns and I abs is the absorbed laser intensity in units of 10 14 W/cm 2 . The increase in ablation pressure at the end of laser pulse at t ∼ 1.8 ns is explained by the reected shock propagating outwards from the merging point.

The shock-wave dynamic is dierent if hot electrons are included in the simulation. First, according to Fig. 6, the ablation pressure is increases slightly to 120 to 130 Mbar. This is caused by the contribution of the low-energy part of the hot-electron spectrum, which is stopped in the transport zone before reaching the ablation surface. In contrast, the shock pressure is rising much stronger, rst, to ∼ 180 Mbar, while propagating through the ablator, and then to 250 Mbar after merging with the rst shock. As shown in Fig. 5, the shock propagates much faster in that case and its amplitude increases with time because of the convergence eect. It collapses at t 2.4 ns leading to the x-ray ash shown in Fig. 4.

The boost in shock pressure from 150 to 250 Mbar resulting from the presence of hot electrons agrees with the qualitative estimate proposed in Refs. [START_REF] Gus'kov | Ablation pressure driven by an energetic electron beam in a dense plasma[END_REF][START_REF] Llor Aisa | The preplasma eect on the properties of the shock wave driven by a fast electron beam[END_REF]:

P he 37ρ 1/3 t I 2/3
he Mbar, where ρ t is the target density downstream of the shock and I he is the hot-electron energy ux in units of 10 14 W/cm 2 . For the target density behind the 4-g/cm 3 shock and the electron energy ux of 3 × 10 14 W/cm 2 (8% of the incident laser intensity), one nds a pressure boost of 120 Mbar, which should be added to the shock pressure created by thermal electrons.

The situation is however more complicated: not all hot electrons deposit their energy downstream of the shock. An increase in the pressure can also be observed upstream of the shock. It is caused by the energy deposited by very energetic electrons that penetrate across the entire target. The areal density of the target is 40 mg/cm 2 , which corresponds to the stopping range of 200-keV electrons. The SRS-generated electrons have an eective temperature of 40 keV; less than 1% of electrons have energies above this limit. Conversely, a signicant part (∼6%) of the TPD electrons with a temperature of 70 keV may penetrate to the target center. However, the TPD electrons are strongly divergent and only a small fraction of them reach the central part of the target. To verify the origin of the target preheat, we conducted an additional simulation with the TPD switched o. This resulted in a less-than-5% reduction in the shock pressure and less-than-50% reduction in the temperature upstream of the shock, which prove the minor role of TPD in shock generation and target preheat. In agreement with the experiments [START_REF] Nora | Gigabar spherical shock generation on the OMEGA laser[END_REF][START_REF] Theobald | Spherical strong-shock generation for shock-ignition inertial fusion[END_REF][START_REF] Theobald | Enhanced hot-electron production and strong-shock generation in hydrogen rich ablators for shock ignition[END_REF] the model conrms the dominant role of SRS-generated electrons in strong-shock dynamics.

Figure 7(a) shows the spatial and temporal evolution of the target temperature. It rises to 20 to 30 eV at a distance of ∼ 50 µm ahead the shock front. This results in a dramatic reduction of the shock strength, dened as a pressure ratio down-and upstream of the shock front, from more than 1000 in the case without hot electrons to about 10 in the case with hot electrons, as shown in Fig. 7(b). Knowing the specic heat capacity of CH, which is ∼ 1 J/gK, and the target mass of ∼ 0.1 mg, we may estimate the energy deposited by hot electrons in the target upstream the shock. About 20 J energy is needed to heat the plastic to 20 to 30 eV, i.e., 1% of the total energy converted in the SRS-generated electrons. This number is indeed compatible with the hard electron fraction.

IV. CONCLUSION

An analysis of a strong-shock experiment with numerical simulations taking into account the nonlinear laserplasma interaction and hot electrons has provided a better understanding of the shock-wave dynamics driven by high-intensity laser pulses. First, a higher absorbed laser energy is correlated with a large fraction of hot electrons that are produced in the experiments with SSD o; ∼10% of the incident laser energy is transferred to hot electrons. SRS is the dominant nonlinear process producing hot electrons with a temperature of 40 keV. These electrons largely contribute to an increase in shock pressure by a factor of ∼2 by depositing their energy downstream of the shock front. However, about 1% of the hot-electron energy is deposited upstream of the shock, signicantly reducing its strength. Accounting for hot electrons in the simulation is found to be key to recovering measured experimental data, thereby allowing a more-robust estimation of the shock parameters.

The methodology proposed in Ref. [START_REF] Nora | Gigabar spherical shock generation on the OMEGA laser[END_REF] of estimating the shock pressure by changing the ux limiter in the case with hot electrons leads to a signicant overestimate of the shock pressure and ablation pressure by ∼100 Mbar (or 30%). The CHIC simulations show only a minor increase in ablation pressure (less than 10%) and a strong increase in shock pressure resulting from hot electrons. The target preheat is an undesirable issue in the context of shock ignition since a shock of a small strength is much less ecient in the fuel heating of the central spot and hot-electron preheat during the ignitor spike may lead to hot-spot mass increase because of inner-shell ablation [START_REF] Colaïtis | Inuence of laser induced hot electrons on the threshold for shock ignition of fusion reactions[END_REF]. These problems may be mitigated by designing a target with a larger areal density. Assuming the hot-electron temperature will be the same in the present shock-ignition target design, it would be sucient to increase the areal shell density to 50 to 60 mg/cm 2 at the moment of the shock launch to reduce the preheat by a factor of 10 and to restore the shock strength needed for ignition. Given the strong eects of hot electrons on shock dynamics, proposing a convincing shock-ignition design requires additional theoretical and experimental work. The most obvious problems are (1) obtaining a ner characterization of the hot-electron spectra generated by parametric instabilities, especially for the very high energy hot electrons, and (2) continuing the eorts to develop in-line models for coupling radiationhydrodynamics codes with the generation of hot electrons. Additional work would also need to address the potential interplay between cross-beam energy transfer and the generation of hot electrons in direct-drive geometry.

Figure 1 .

 1 Figure 1. Laser pulse temporal prole at the target (gray) and experimentally measured absorbed power (red) for shots (a) 72676 (SSD on) and (b) 73648 (SSD o ). The blue and black curves show the calculated absorbed power with the numerical code CHIC in runs with (blue) and without (black) hot electrons.

Figure 2 .

 2 Figure 2. Density (a) and pressure (b) proles obtained with CHIC simulations for the time interval of the main laser pulse:

Figure 3 .

 3 Figure 3. (a) Fraction of laser power converted in hot electrons and (b) their temperature calculated with CHIC for the laser power prole shown with gray line in (a). Resonance absorption is shown in black, SRS in red, and TPD in green.

Figure 4 .

 4 Figure 4. Temporal evolution of the plasma x-ray emission in the 3-to 5-keV energy range obtained from post-processing CHIC simulations with (red) and without (blue) hot electrons.

Figure 5 .

 5 Figure 5. Pressure evolution as a function of the position in the target and time for the case (a) without hot electrons and (b) with hot electrons. The red line shows the position of the external target surface, the green line the interface between the ablator and the inner part, the black line the position of the strongest shock.

Figure 6 .

 6 Figure 6. Evolution of the shock (red) and ablation (black) pressure for the case (a) without hot electrons and (b) with hot electrons.

Figure 7 .

 7 Figure 7. (a) Spatiotemporal evolution of the target temperature in the simulation with hot electrons. (b) The shock strength evolution for the runs without (black) and with (red) hot electrons.

Acknowledgment

This work has been carried out within the framework of the EUROfusion Consortium and has received funding from the Euratom research and training programme 2014-2018 under grant agreement No 633053. The views and opinions expressed herein do not necessarily reect those of the European Commission. We acknowledge a support from the Aquitaine Regional Council. Part of this work was supported by the DOE NNSA under awards No. DE-NA0001944 and DE-FC02-04ER54789, the Laboratory Basic Science Program, the University of Rochester, and the New York State Energy Research and Development Authority.

This report was prepared as an account of work sponsored by an agency of the U.S. Government. Neither the U.S. Government nor any agency thereof, nor any of their employees, makes any warranty, express or implied, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any information, apparatus, product, or process disclosed, or represents that its use would not infringe privately owned rights. Reference herein to any specic commercial product, process, or service by trade name, trademark, manufacturer, or otherwise does not necessarily constitute or imply its endorsement, recommendation, or favoring by the U.S. Government or any agency thereof. The views and opinions of authors expressed herein do not necessarily state or reect those of the U.S.