Panikos Heracleous
email: panikos.heracleous@gipsa-lab.inpg.fr

Noureddine Aboutabit
email: noureddine.aboutabit@gipsa-lab.inpg.fr

Denis Beautemps
email: denis.beautemps@gipsa-lab.inpg.fr

ALTERNATIVE SPEECH COMMUNICATION BASED ON CUED SPEECH

This study focuses on alternative speech communication based on Cued Speech. Cued Speech is a visual mode of communication that uses hand shapes and placements in combination with the mouth movements of speech to make the phonemes of a spoken language look different from each other and clearly understandable to deaf and hearingimpaired people. Originally, the aim of Cued Speech was to overcome the problems of lip reading and thus enable deaf children and adults to wholly understand spoken language. In this study, however, we investigate the use of Cued Speech not only for perception, but also for speech production in the case of speech-or hearing-impaired individuals. The proposed method is based on hidden Markov model (HMM) automatic recognition. Automatic recognition of Cued Speech and conversion to text, audio, or synthesized Cued Speech can be served as an alternative speech communication method for individuals with speech or hearing impairments. This article presents vowel and consonant, and also isolated word recognition experiments for Cued Speech for French. The results obtained are promising and comparable to the results obtained when using audio signal.

INTRODUCTION

Speech is often described as a uni-modal process. However, it is well known that speech is multi-modal in nature and includes modalities such as audio modality, visual modality, touch modality, signal of muscles, articulatory speech, and brain activity during speech production.

The audio modality describes the audible speech used for communication between individuals without disorders in speech perception and production. In addition, audio modality includes inaudible speech produced when vocal folds are not vibrating (i.e., whisper speech), and also tissueconducted Non-Audible Murmur speech [START_REF] Heracleous | Non-audible murmur (nam) recognition using a stethoscopic nam microphone[END_REF]. Messages can be also transferred using information produced by lips and mouth, and by facial information. Cued Speech, a system that uses hand shapes in different positions to complement lipreading, is a wholly visual speech system [START_REF] Cornett | Cued speech[END_REF]. Speech can be perceived and interpreted by touching, as in the Tadoma technique. Tadoma is a technique that enables a person who is both blind and deaf to receive and interpret speech. In addition, speech messages can be transferred through the activation signal of muscles during speech production [START_REF] Jou | Towards continuous speech recognition using surface electromyography[END_REF]. Invisible articulatory components i.e., tongue and velum is the motor which makes link between the different modalities. Movements of the invisible articulators during speech production also carry speech information [START_REF] Badin | An audiovisual talking head for augmented speech generation: models and animations based on a real speaker's articulatory data[END_REF][START_REF] Hueber | Phone recognition from ultrasound and optical video sequences for a silent speech interface[END_REF]. Also some studies investigate the brain activity during speech production [START_REF] Blankertz | The berlin brain-computer interface: Eeg-based communication without subject training[END_REF].

This work is supported by the French TELMA project (RNTS / ANR). Alternative speech communication makes possible for individuals with impairments to communicate using their existing abilities. A speech-impaired individual (i.e. after laryngectomy) can use gestures to transfer messages, and a blind and deaf individual can use touch speech modality to perceive speech. Alternative speech can be also used in education for pronunciation training for second language learners, and for perception and production rehabilitation of hearing impaired children. Since environmental noise does not affect alternative speech, it can be used when the communication occurs in noisy environments (e.g., airports, stations, etc.). In addition, it can be also used in situations when privacy in communication is preferable.

To date, visual information is widely used to improve speech perception, or automatic speech recognition (lipreading). With lipreading technique, speech can be understood by interpreting movements of lips, face and tongue. However, even with high lipreading performance, speech without knowledge of the semantic context can not be completely perceived. To overcome the problems of lipreading and to improve the reading abilities of profoundly deaf children, in 1967 Cornett developed the Cued Speech system to complement the lip information and make all phonemes of a spoken language clearly visible. As many sounds look identical on lips (e.g., /p/ and /b/), using hand information those sounds can be distinguished and thus make possible for deaf people to completely understand a spoken language using only visual information.

Cued Speech uses hand shapes placed in different po- sitions near the face in combination with natural speech lipreading to enhance speech perception from visual input.

A manual cue in this system contains two components: the hand shape and the hand position relative to the face. Hand shapes distinguish consonants whereas hand positions distinguish vowels. A hand shape together with a hand position cue a syllable. The advantage of Cued Speech is that improves speech perception to a large extent for hearingimpaired people. Moreover, Cued Speech offers a complete representation of the phonological system for hearingimpaired people exposed to this method since their youth, and therefore has a positive impact on language development [START_REF] Leybaert | Phonology acquired through the eyes and spelling in deaf children[END_REF]. Fig. 1 describes the complete system for French. In Cued French, eight hand shapes in five positions are used.

The access to communication technologies has become essential for the handicapped people. The TELMA project (Phone for deaf people) aims to develop an automatic translation system of acoustic speech into visual speech completed with CS and vice versa, i.e. from CS components into auditory speech [START_REF] Beautemps | Telma: Telephony for the hearing-impaired people. from models to user tests[END_REF]. This project would enable deaf users to communicate between themselves and with normal-hearing people through the help of the autonomous terminal TELMA.

The Cued Speech paradigm requires accurate recognition of both lip shape and hand information. Fusion of lip shape and hand components is also necessary and very important. Fusion is the integration of available single modality streams to a combined one. Previously, several studies have been made in automatic audio-visual recognition and integration of visual and audio modalities [START_REF] Potamianos | Recent advances in the automatic recognition of audiovisual speech[END_REF]. The aim of audio-visual speech recognition is to improve the performance of a recognizer, especially under noisy environments.

In the first attempt for vowel recognition in Cued Speech for French, in [START_REF] Aboutabit | Automatic identification of vowels in the cued speech context[END_REF] a method based on separate identification, i.e., indirect decision fusion was used by the authors, and 77.6% vowel accuracy was obtained. A similar study for digit recognition in English Cued language was also introduced in [START_REF] Argyropoulos | Multimodal fusion for cued speech language recognition[END_REF]. Previously, the authors presented a method for automatic vowel recognition in Cued Speech for French based on HMMs [START_REF] Heracleous | Lip shape and hand position fusion for automatic vowel recognition in cued speech for french[END_REF]. In the current study, vowel recognition is further investigated, and the proposed method was extended to deal with consonant and isolated word recognition.

METHODS

The female native French speaker-employed for data recording was certified in transliteration speech into Cued Speech in the French language. She regularly cues in schools. The cuer wore a helmet to keep her head in a fixed position and opaque glasses to protect her eyes against glare from the halogen floodlight. The speaker's lips were painted blue, and blue marks were marked on her glasses as reference points. These constraints were applied in recordings in order to control the data and facilitate the extraction of accurate features (see [START_REF] Aboutabit | Lips and hand modeling for recognition of the cued speech gestures: The french vowel case[END_REF] for details).

The data were derived from a video recording of the speaker pronouncing and coding in Cued Speech a set of 262 French sentences. The sentences (composed of low predicted multi-syllabic words) were derived from a corpus that was dedicated to Cued Speech synthesis. Each sentence was dictated by an experimenter, and was repeated two-or three times (to correct errors in pronunciation of words) by the cuer resulting in a set of 638 sentences.

The audio part of the video recording was synchronized with the image. An automatic image processing method was applied to the video frames in the lip region to extract their inner-and outer contours and to derive the corresponding characteristic parameters: lip width (A), lip aperture (B), and lip area (S) (i.e., six parameters in all).

The process described here resulted in a set of temporally coherent signals: the 2-D hand information, the lip width (A), the lip aperture (B), and the lip area (S) values for both inner-and outer contours, and the corresponding acoustic signal. In addition, two supplementary parameters relative to the lip morphology were extracted: the pinching of the upper lip (Bsup) and lower (Binf) lip. As a result, a set of eight parameters in all was extracted for modeling lip shapes. For hand position modeling, the xy coordinates of two landmarks placed on the hand were used (i.e., 4 parameters). For hand shape modeling the xy coordinates of the landmarks placed on the fingers were used (i.e., 10 parameters). Fig. 2 shows the lip shape parameters used in the current study.

In the vowel and consonant recognition experiments, context-independent, 3-state, left-to-right with no skip HMMs were used. Each state was modeled with 32 Gaussian mixtures. In addition to the basic lip and hand parameters, the first (∆) and second derivatives (∆∆) were used, as well. For training and test 426 and 212 sentences were used, respectively. The training sentences contained 3838 vowels and 4401 consonants, and the test sentences contained 1913 vowels and 2155 consonants, respectively. Vowels and consonants were extracted automatically from the data after forced alignment was performed (using the audio signal).

For isolated word recognition experiments, 1450 isolated words were recorded employing a different cuer than that employed in the previous recordings. The vocabulary included 50 words, and each one was repeated twenty-nine times. Twenty repetitions of each word were used to train fifty, 6-state, whole word HMMs, and 9 repetitions were used for test. For lip shape and hand shape modeling , the same kind of parameters as in vowel and consonant recognition experiments were used. In this data recording session, the recording constraints were eliminated by excluding the use of the helmet by the cuer.

In automatic speech recognition, a diagonal covariance matrix is often used because of the assumption that the parameters are uncorrelated. In lipreading, however parameters show a strong correlation. In this study, Principal Component Analysis (PCA) was applied to decorrelate the lip shape parameters and then a diagonal covariance matrix was used. All PCA lip shape components were used for HMM training.

For training and recognition the HTK3.1 toolkit was used. The French language includes 14 vowels and 17 consonants. Based on similarities on lips, the 31 phonemes can be grouped into 8 visemes. A viseme consists of phonemes that look similar on mouth/lips. Table 2 shows the mapping of French phonemes to visemes. Based on previous works, five consonant-visemes and three vowel-visemes reflect the most appropriate phoneme-to-viseme mapping [START_REF] Aboutabit | A hmm recognition of consonant-vowel syllabes from lip contours: the cued speech case[END_REF].

Because of the nature of Cued Speech, for vowel recognition lip shape and hand position elements were integrated into a single component using concatenative feature fusion. For consonant recognition, lip shape and hand shape elements were integrated. The feature concatenation uses the concatenation of the synchronous lip shape and hand features as the joint bimodal feature vector

O LH t = [O (L) T t , O (H) T t ] T ∈ R D (1)
where O LH t is the joint lip-hand feature vector, O (L) t the lip shape feature vector, O (H) t the hand feature vector, and D the dimensionality of the joint feature vector. In vowel recognition experiments, the dimension of the lip shape stream was 24 (8 basic parameters, 8 ∆, and 8 ∆∆ parameters) and the dimension of the hand position stream was 12 ( 4 basic parameters, 4 ∆, and 4 ∆∆ parameters). The dimension D of the joint lip-hand position feature vectors was, therefore 36. In consonant recognition experiments, the dimension of the hand shape stream was 30 (10 basic parameters, 10 ∆, and 10 ∆∆ parameters). The dimension D of the joint lip-hand shape feature vectors was, therefore 54.

EXPERIMENTS

Vowel-viseme classification using lip shape information

An experiment was conducted for recognition of the three vowel-visemes in order to evaluate the proposed method for lip shape modeling and also the vowel-viseme mapping. For each viseme, a 3-state HMM was trained using the previously described training data. The vowel labels in the phonetic transcription were translated to include only three viseme labels. Table 2 shows the confusion matrix of vowel-viseme recognition. As can be seen, the vowel-visemes were recognized with high accuracy. More specifically, 96.1% viseme classification accuracy was achieved (i.e., percentage of diagonal elements). Table 2 also shows that the partial error corresponding to each viseme is uniform and almost equal.

Vowel recognition based on concatenative feature fusion

Based on concatenative feature fusion, experiments were conducted for vowel recognition considering the similarities on lips. The aim was to investigate how the integration of hand position element improves the recognition accuracy when vowels belonging to the same class were recognized. As previously described, vowels which show similarities on lips (visemes) cannot be recognized accurately using lip shape information alone.

Using the previously described phoneme-to-viseme mapping, the 14 vowels were classified into three groups and three separate HMM sets were trained using the appropriate training data. In this way, each group included the most confusable vowels based on lip shape. Table 3 shows the obtained results. Using lip shape parameters only, the average vowel accuracy was 64.4% because of the high number of confusions between similar vowels in each group. On the other hand, by integrating also hand position element with lip shape element, the average vowel accuracy was raised to 91.2%, showing a 75.3% relative improvement compared with using lip shape parameters alone. In this case, however, vowels belonging to the same group -based on lips similarities-are distinguishable using hand position information. As a result the confusions between them drastically decreased, which increases the recognition accuracy. Table 3 shows also the results when auditory parameters were used. More specifically, the acoustic signal was parameterized using 12 Mel-Frequency Cepstral Coefficients (MFCC) and first and second derivatives, as well. As can be seen, in the case of Cued Speech the performance is very similar to the performance obtained when using the acoustic signal. Table 4 shows the obtained results for the overall vowel recognition using a common HMM set. Compared with using lip shape parameters alone, when fusion was applied a 63.3% relative improvement was obtained. It is also shown, that results of vowel recognition in Cued Speech and those obtained using the acoustic signal do not show significant differences.

Consonant recognition based on concatenative feature fusion

In this section, experiments for consonant recognition in French Cued Speech are introduced. Using concatenative feature fusion, lip shape element was integrated with hand shape element, and consonant recognition was conducted. For hand shape modeling the xy coordinates of fingers were used along with the first and second derivatives. In total 30 parameters were used for hand shape modeling.

In a way similar to vowel recognition, the consonants were classified into groups based on lip shape similarities, and separate HMM sets were trained. Five HMM sets were trained corresponding to the five consonant groups. Table 5 shows the obtained results. It can be seen, that using lip shape and hand shape information, significant improvements in accuracy were obtained compared with using lip shape parameters only. More specifically, a 65.2% relative improvement was obtained when hand shape element was also used. Table 5 also shows the results obtained when using the acoustic signal. It can be seen, that accuracies obtained using the acoustic signal are higher. A possible reason might be the errors occurred in hand shape recognition. However, results are still comparable and promising also in consonant recognition in Cued Speech for French.

Table 4 shows the obtained overall results for consonant recognition. It is shown, that compared with using lip shape parameters alone, when fusion was applied a 56% relative improvement was obtained.

Isolated word recognition based on concatenative feature fusion

In this section, isolated word recognition experiments in Cued Speech for French are presented. Fig. 3 shows the results obtained in the function of several mixtures of Gaussians per state. In the case of a single Gaussian per state, using lip shape alone a 53.3% word accuracy was obtained. When, however, hand shape information was also used, a 95.6% word accuracy was obtained, showing a 91% relative improvement. The highest word accuracy when using lip shape was 74.9%, obtained in the case of using 8 Gaus- sians per state. In that case, the Cued Speech word accuracy using also hand information was 96.9%. Fig. 4 shows a comparison between audio recognition and Cued Speech recognition in the function of several Signal-to-Noise (SNR) levels of acoustic noise. Office noise at different levels was superimposed onto clean test audio data and recognition experiments were conducted using clean HMMs. For the analysis of the audio signal, 12 MFCC along with the first and second derivatives were used. Each state was modeled with 8 Gaussian mixtures. It is shown, that up to 30 dB SNR, the Cued Speech recognition performs better compared with the audio recognition. The maximum word accuracy of audio recognition was 98% in the clean case, slightly higher compared with the 96.9% word accuracy of the Cued Speech recognition.

To show the effect of integrating hand information in isolated word recognition, PCA analysis was performed using the means of the fourth state of each word-HMM. Fig. 5 shows a visualization of the words in the 3-D PCA space using lip shape alone, and Fig. 6 shows the visualization of the same words when hand shape was also integrated. It can be seen, that using also hand information the words are much better discriminated. As a result, the word accuracy was significantly increased.

CONCLUSION

In this paper, vowel, consonant, and isolated word recognition in Cued Speech for French was presented in order to investigate an alternative speech communication method for individuals with speech-or hearing impairments. Using concatenative feature fusion, lip shape and hand information was integrated and automatic recognition experiments were conducted with very promising accuracies. The final aim of this study is to automatically recognize Cued Speech for French using visual information alone, and then convert it to a different modalities enabling human-human and human-machine interaction for people with disorders using their existing abilities. Currently, collection of additional data is in progress in order to realize automatic recognition for continuous Cued Speech recognition using larger vocabularies.

Figure 1 :

 1 Figure 1: Hand position for vowels (top) and hand shapes for consonants (bottom) in Cued Speech for French.

Figure 2 :

 2 Figure 2: Parameters used for lip shape modeling.

Figure 3 :

 3 Figure 3: Word accuracy for isolated word recognition.

Figure 4 :

 4 Figure 4: Word accuracy for isolated word recognition in the function of acoustic noise.

Figure 5 :

 5 Figure 5: Location of the words in the 3-D PCA space when using lip shape parameters

Figure 6 :

 6 Figure 6: Location of the words in the 3-D PCA space when using fused lip shape and hand shape parameters

Table 1 :

 1 Phoneme-to-viseme mapping in French language.

	Consonants		Vowels
	Viseme Phonemes	Viseme Phonemes
	C1	/p/, /b/, /m/	V1	/Õ/, /y/, /o/
				/ø/, /u/
	C2	/f/, /v/	V2	/a/, /Ẽ/. /ı/
				/ oe/, /e/, / E/
	C3	/t/, /d/, /s/	V3	/Ã/, /O/, /oe/
		/z/, /n/, /ñ/
	C4	/S/, /Z/
	C5	/k/ , /g/
		/ö/, /l/

Table 2 :

 2

	Confusion matrix of vowel-viseme recognition us-
	ing lip shape information only.
	V1	V2	V3	%correct %error
	V1 583	3	20	96.2	1.2
	V2 33 1039 23	97.2	1.5
	V3 11	11	209	90.5	1.2

Table 3 :

 3 Accuracy for three vowel groups considering similarities on lips.

			Element
	Vowel group Lips Lips+Position Audio
	Group1	60.2	94.0	96.7
	Group2	58.6	85.9	90.9
	Group3	74.3	93.7	93.8
	Average	64.4	91.2	93.8

Table 4 :

 4 Vowel and consonant overall accuracy.

			Element
	Phonemes Lips Lips+Hand Audio
	Vowels	59.4	85.1	91.5
	Consonants 52.1	78.9	90.7
	Average	55.8	82.0	91.1

Table 5 :

 5 Accuracy for five consonant groups considering similarities on lips.

			Element
	Consonant group Lips Lips+Shape Audio
	Group1	66.2	88.1	98.2
	Group2	83.1	96.3	98.7
	Group3	50.5	81.1	97.2
	Group4	82.9	93.0	98.6
	Group5	59.1	86.6	96.7
	Average	68.4	89.0	97.9

ACKNOWLEDGMENTS

The authors would like to thank Ch. Savariaux and C. Vilain for their help in the Cued Speech material recordings. Also many thanks to S. Chevalier and M. Dibui, our cuers, for having accepted the recording constraints.


Alina Firicel

SUBWORD COMPLEXITY AND LAURENT SERIES WITH COEFFICIENTS IN A FINITE FIELD

may come

Subword complexity and Laurent series with coefficients in a finite field

Alina Firicel

Introduction and motivations

A long standing open question concerns the digits of the real number π = 3.14159 • • • . The decimal expansion of π has been calculated to billions of digits and unfortunately, there are no evident patterns occurring. Actually, for any b ≥ 2, the b-ary expansion of π looks like a random sequence (see for instance [10]). More concretely, it is widely believed that π is normal, meaning that all blocks of digits of equal length occur in the b-ary representation of π with the same frequency, but current knowledge on this point is scarce.

A usual way to describe the disorder of an infinite sequence a = a 0 a 1 a 2 • • • is to compute its subword complexity, which is the function that associates to each positive integer m the number p(a, m) of distinct blocks of length m occurring in the word a. Let α be a real number and let a be the representation of α in an integral base b ≥ 2. The complexity function of α is defined as follows:

p(α, b, m) = p(a, m), for any positive integer m.

Notice that π being normal would imply that its complexity must be maximal, that is p(π, b, m) = b m . In this direction, similar questions have been asked about other well-known constants like e, log 2, ζ(3) or √ 2 and it is widely believed that the following conjecture is true. We mention that in all this paper we will use Landau's notations. We write f (m) = Θ(g(m)) if there exist positive real numbers k 1 , k 2 , n 0 such that, for every n > n 0 we have

k 1 |g(n)| < |f (n)| < k 2 |g(n)| .
We write also f (m) = O(g(m)) if there exist two positive real numbers k, n 0 such that, for every n ≥ n 0 we have:

|f (n)| < k |g(n)| .
If α is a rational real number then p(α, b, m) = O(1), for every integer b ≥ 2. Moreover, there is a classical theorem of Morse and Hedlund [START_REF] Morse | Symbolic dynamics[END_REF] which states that an infinite sequence a = (a n ) n≥0 is eventually periodic if and only if p(a, m) is bounded. If not, the complexity function is strictly increasing. In particular, (1) p(a, m) ≥ m + 1, for every nonnegative integer m.

A sequence which saturates the inequality above is called a Sturmian sequence (see the original papers of Morse and Hedlund [START_REF] Morse | Symbolic dynamics[END_REF][START_REF] Morse | Symbolic dynamics II[END_REF]).

According to this theorem, an irrational real number α has a complexity function which satisfies p(α, b, m) ≥ m + 1, for every m ∈ N. Concerning irrational algebraic numbers, the main result known to date in this direction is due to Adamczewski and Bugeaud [3]. These authors proved that the complexity of an irrational algebraic real number α satisfies For more details about complexity of algebraic real numbers, see [3,4]. For classical transcendental constants, there is a more ambiguous situation and, to the best of our knowledge, the only result that improves the bound following from Inequality (1) was recently proved in [1]. It concerns the real number e and some other exponential periods. More precisely, Adamczewski showed that if ξ is an irrational real number whose irrational exponent µ(ξ) = 2, then lim The present paper is motivated by this type of questions, but asked for Laurent series with coefficients in a finite field. In the sequel we will denote respectively by F q (T ), F q [[T -1 ]] and F q ((T -1 )) the field of rational functions, the ring of formal series and the field of Laurent series over the finite field F q , q being a power of a prime number p.

Let us also recall the well-known analogy between integers, rationals and real numbers on one side, and polynomials, rationals functions, and Laurent series with coefficients in a finite field, on the other side. Notice that, the coefficients in F q play the role of "digits" in the basis given by the powers of the indeterminate T . There is still a main difference: in the case of real numbers, it is hard to control carry-overs when we add or multiply whereas in the case of power series over a finite field, this difficulty disappear.

By analogy with the real numbers, the complexity of a Laurent series is defined as the subword complexity of its sequence of coefficients. Again, the theorem of Morse and Hedlund gives a complete description of the rational Laurent series; more precisely, they are the Laurent series of bounded complexity. Hence, most interesting questions concern irrational series.

There is a remarkable theorem of Christol [18] which describes precisely the algebraic Laurent series over F q (T ) as follows. Let f (T ) = n≥-n 0 a n T -n be a Laurent series with coefficients in F q . Then f is algebraic over F q (T ) if, and only if, the sequence of coefficients (a n ) n≥0 is p-automatic.

For more references on automatic sequences, see for example [8]. Furthermore, Cobham proved that the subword complexity of an automatic sequence is at most linear [20]. Hence, an easy consequence of those two results is the following.

Theorem 1.1. Let f ∈ F q ((T -1 )) algebraic over F q (T ). Then we have:

p(f, m) = O(m).
The reciprocal is obviously not true, since there are uncountable many Laurent series with linear complexity. In contrast with real numbers, the situation is thus clarified in the case of algebraic Laurent series. Also, notice that Conjecture 1.1 and Theorem 1.1 point out the fact that the situations in F q ((T -1 )) and in R appear to be completely opposite.

On the other hand, Carlitz introduced [START_REF] Carlitz | On certain functions connected with polynomials in a Galois field[END_REF] functions in positive characteristic by analogy with the number π, the Riemann ζ function, the usual exponential and the logarithm function. Many of these were shown to be transcendental over F q (T ) (see [START_REF] Cherif | Irrationality measures of Carlitz zeta values in characteristic p[END_REF][START_REF] Goss | Basic Structures of Function Field Arithmetic[END_REF][START_REF] Thakur | Function Field Arithmetic[END_REF][START_REF] Wade | Certain quantities transcendental over GF (pn)(x)[END_REF][START_REF] Yu | Transcendence and Special Zeta Values in Characteristic p[END_REF]). In the present paper we focus on the analog of π, denoted, for each q, by Π q , and we prove that its inverse has a "low" complexity. More precisely, we will prove in Section 3 the following results.

Theorem 1.2. Let q = 2. The complexity of the inverse of Π q satisfies:

p 1 Π 2 , m = Θ(m 2 ).
Theorem 1.3. Let q ≥ 3. The complexity of the inverse of Π q satisfies:

p 1 Π q , m = Θ(m).
Since any algebraic series has a linear complexity (by Theorem 1.1), the following corollary yields.

Corollary 1.1. Π 2 is transcendental over F 2 (T ).
The transcendence of Π q over F q (T ) was first proved by [START_REF] Wade | Certain quantities transcendental over GF (pn)(x)[END_REF] (see [START_REF] Wade | Certain quantities transcendental over GF (pn)(x)[END_REF]) using an analog of a classical method of transcendence in zero characteristic. Another proof was given by Yu in 1991 (see [START_REF] Yu | Transcendence and Special Zeta Values in Characteristic p[END_REF]), using the theory of Drinfeld modules. Then, de Mathan and Cherif, in 1993 (see [START_REF] Cherif | Irrationality measures of Carlitz zeta values in characteristic p[END_REF]), using tools from Diophantine approximation, proved a more general result, but in particular their result implied the transcendence of Π q .

Christol's theorem has also been used as a combinatorial criterion in order to prove the transcendence of Π q . This is what is usually called an "automatic proof". The non-automaticity and also the transcendence, was first obtained by Allouche, in [6], via the so-called q-kernel. Notice that our proof of transcendence here is based also by Christol's theorem, but we obtain the non-automaticity of Π 2 over F 2 (T ) as a consequence of the subword complexity.

Furthermore, motivated by Theorems 1.2, 1.3 and by Conjecture 1.1, we consider the classes of Laurent series of at most polynomial complexity P and of zero entropy Z (see Section 4), which seem to be good candidates to enjoy some nice closure properties. In particular, we prove the following theorem.

Theorem 1.4. P and Z are vector spaces over F q (T ).

Another motivation of this work is the article [11] of Beals and Thakur. These authors proposed a classification of Laurent series in function of their space or time complexity. This complexity is in fact a characteristic of the (Turing) machine that computes the coefficient a i , if f (T ) := i a i T -i . They showed that some classes of Laurent series have good algebraic properties (for instance, the class of Laurent series corresponding to any deterministic space class at least linear form a field). They also place some Carlitz's analogs in the computational hierarchy. This paper is organized as follows. Some definitions and basic notions on combinatorics on words and Laurent series are recalled in Section 2. Section 3 is devoted to the study of the Carlitz's analog of π; we prove Theorems 1.2 and 1.3. In Section 4 we study some closure properties of Laurent series of "low" complexity (addition, Hadamard product, derivative, Cartier operator) and we prove Theorem 1.4; in particular, this provides a criterion of linear independence over F q (T ) for two Laurent series in function of their complexity. Finally, we conclude in Section 5 with some remarks concerning the complexity of the Cauchy product of two Laurent series, which seems to be a more difficult problem.

Terminologies and basic notions

In this section, we briefly recall some definitions and well-known results from combinatorics on words. Moreover, we recall some basic notions on algebraic Laurent series.

A word is a finite, as well as infinite, sequence of symbols (or letters) belonging to a nonempty set A, called alphabet. We usually denote words by juxtaposition of theirs symbols.

Given an alphabet A, we denote by

A * := ∪ ∞ k=0 A k the set of finite words over A. Let V := a 0 a 1 • • • a m-1 ∈ A * .
Then the integer m is the length of V and is denoted by |V |. The word of length 0 is the empty word, usually denoted by ε. We also denote by A m the set of all finite words of length m and by A N the set of all infinite words over A. We typically use the uppercase italic letters X, Y, Z, U, V, W to represent elements of A * . We also use bold lowercase letters a, b, c, d, e, f to represent infinite words. The elements of A are usually denoted by lowercase letters a, b, c, • • • .

We say that V is a factor (or subword) of a finite word U if there exist some finite words A, B, possibly empty such that U = AV B and we denote it by V ⊳ U . Otherwise, V ⋪ U . We say that X is a prefix of U , and we denote by X ≺ p U if there exists Y such that U = XY . We say that Y is a suffix of U , and we denote by Y ≺ s U if there exists X such that U = XY . Also, we say that a finite word V is a factor (or subword) of an infinite word a = (a n ) n≥0 if there exists a nonnegative integer j such that V = a j a j+1 • • • a j+m-1 . The integer j is called an occurence of V .

Let U, V, W be three finite words over A, V possibly empty. We denote:

i(U, V, W ) := {AV B, A ≺ s U, B ≺ p W, A, B possibly empty}, and i(U, V, W ) + := {AV B, A ≺ s U, B ≺ p W, A, B nonempty}.
If n is a nonnegative integer, we denote by

U n := U U • • • U n times
. We denote also U ∞ := U U • • • , that is U concatenated (with itself) infinitely many times. An infinite word a is periodic if there exists a finite word V such that a = V ∞ . An infinite word is eventually periodic if there exist two finite words U and V such that a = U V ∞ .

The fundamental operation on words is concatenation. Notice that A * , together with concatenation, form the free monoid over A, whose neutral element is the empty word ε.

2.1. Subword complexity. Let a be an infinite word over A. As already mentioned in Introduction, the subword complexity of a is the function that associates to each m ∈ N the number p(a, m) defined as follows:

p(a, m) = Card{(a j , a j+1 , . . . , a j+m-1 ), j ∈ N}.

For any word a, p(a, 0) = 1 since, by convention, the unique word of length 0 is the empty word ε.

For example, let us consider the infinite word a = aaa • • • , the concatenation of a letter a infinitely many times. It is obvious that p(a, m) = 1 for any m ∈ N. More generally, if a is eventually periodic, then its complexity function is bounded.

On the other side, let us consider the infinite word of Champernowne over the alphabet {0, 1, 2, 3, . . . , 9}, a := 0123456789101112 • • • . Notice that p(a, m) = 10 m for every positive integer m.

More generally, one can easily prove that for every m ∈ N and for every word a over the alphabet A, we have the following:

1 ≤ p(a, m) ≤ (card A) m .
We give now an important tool we shall use in general, in order to obtain a bound of the subword complexity function (for a proof see for example [8]):

Lemma 2.1. Let a be an infinite word over an alphabet A. We have the following properties:

• p(a, m) ≤ p(a, m + 1) ≤ card A • p(a, m), for every integer m ≥ 0; • p(a, m + n) ≤ p(a, m)p(a, n), for all integers m, n ≥ 0.

Let F q be the finite field with q elements, where q is a power of a prime number p.

In this paper, we are interested in Laurent series with coefficients in F q . Let n 0 ∈ N and consider the Laurent series:

f (T ) = +∞ n=-n 0 a n T -n ∈ F q ((T -1 )).
Let m be a nonnegative integer. We define the complexity of f , denoted by p(f, m), as being equal to the complexity of the infinite word a = (a n ) n≥0 .

2.2. Topological entropy. Let a be an infinite word over an alphabet A. The (topological) entropy of a is defined as follows:

h(a) = lim m→∞ log p(a, m) m .
The limit exists as an easy consequence of the following property: p(a, n+ m) ≤ p(a, n)p(a, m), for every m, n ≥ 0 (which is the second part of the Lemma 2.1). If the base of the logarithm is the cardinality of the alphabet then:

0 ≤ h(a) ≤ 1.
Notice that, by definition, the "simpler" the sequence is, the smaller its entropy is.

Let n 0 ∈ N and consider the Laurent series

f (T ) = +∞ n=-n 0 a n T -n ∈ F q ((T -1 )).
We define the entropy of f , denoted by h(f ), as being equal to the entropy of the infinite word a = (a n ) n≥0 .

2.3. Morphisms. Let A (respectively B) be an alphabet and let A * (respectively B * ) be the corresponding free monoid. A morphism σ is a map from A * to B * such that σ(U V ) = σ(U )σ(V ) for all words U, V ∈ A * . Since the concatenation is preserved, it is then possible to define a morphism on A.

If A = B we can iterate the application of σ. Hence, if a ∈ A, σ 0 (a) = a, σ i (a) = σ(σ i-1 (a)), for every i ≥ 1.

Let σ : A → A be a morphism. The set A * ∪A N is endowed with a natural topology. Roughly, two words are close if they have a long common prefix. We can thus extend the action of a morphism by continuity to A * ∪ A N . Then, a word a ∈ A N is a fixed point of a morphism σ if σ(a) = a.

A morphism σ is prolongable on a ∈ A if σ(a) = ax, for some x ∈ A + := A * \{ε}. If σ is prolongable then the sequence (σ i (a)) i≥0 converges to the infinite word: σ ∞ (a) = lim i→∞ σ i (a) = axσ(x)σ 2 (x)σ 3 (x) • • • .
Example 2.1. The Fibonacci word f = 0100101001001 • • • is an example of an infinite word generated by iterating the morphism: σ(0) = 01 and σ(1) = 0. More precisely, f = σ ∞ (0) is the unique fixed point of σ.

The order of growth of a letter x is the function |σ n (x)|, for n ≥ 0. In general, this function is bounded or, if not, is growing asymptotically like the function n ax b n

x . A morphism is said to be polynomially diverging if there exists b > 1 such that, for any letter x, the order of growth of x is n ax b n and a x ≥ 1 for some x. A morphism is exponentially diverging if every letter

x has the order of growth n ax b n

x with b x > 1 and not all b x are equal. For more details the reader may refer to [START_REF] Pansiot | Subword Complexities and Iteration[END_REF].

A morphism σ is said to be uniform of length m ≥ 2 if |g(x)| = m. Notice that a word generated by an uniform morphism of length m is m-automatic (see for example [20]). In particular, its complexity is O(1) if the word is eventually periodic; otherwise, it is Θ(m).

For more about the complexity function of words generated by morphisms there is a classical theorem of Pansiot [START_REF] Pansiot | Subword Complexities and Iteration[END_REF] that characterizes the asymptotic behavior of factor complexity of words obtained by iterating a morphism.

Algebraic Laurent series

. A Laurent series f (T ) = n≥-n 0 a n T -n ∈ F q ((T -1
)) is said to be algebraic over the field F q (T ) if there exist an integer d ≥ 1 and polynomials A 0 (T ), A 1 (T ), . . . , A d (T ), with coefficients in F q and not all zero, such that:

A 0 + A 1 f + • • • + A d f d = 0.
Otherwise, f is transcendental over F q (T ).

Let us now give an example of Laurent series algebraic over the field of rational functions.

(T ) = n≥0 c n T -n ∈ F 3 [[T -1 ]
] where c := (c n ) n≥0 is the Cantor sequence defined as follows:

c n =
1 if (n) 3 contains only 0 and 2; 0 if (n) 3 contains the letter 1. .

Here (n) 3 denotes the expansion in base 3 of n. By definition, we get that c 3n = c n = c 3n+2 and c 3n+1 = 0, for all n ∈ N.

We have:

f (T ) = n≥0 c 3n T -3n + n≥0 c 3n+1 T -3n-1 + n≥0 c 3n+2 T -3n-2 = n≥0 c n T -3n + n≥0 c n T -3n-2 .
Hence,

f (T ) = f (T 3 ) + T -2 f (T 3 )
and, since we are in characteristic 3, we obtain that f satisfies the following equation:

(1 + T 2 )f 2 (T ) -T 2 = 0. Thus f is an algebraic Laurent series.
Notice also that, the infinite sequence c is 3-automatic, as predicted by Christol's theorem, and in particular the complexity of c satisfies:

p(c, m) = O(m).

An analogue of Π

In 1935, Carlitz [START_REF] Carlitz | On certain functions connected with polynomials in a Galois field[END_REF] introduced for function fields in positive characteristic an analog of the exponential function defined over C ∞ , which is the completion of the algebraic closure of F q ((T -1 )) (this is the natural analogue of the complex numbers field). In order to get good properties in parallel with the complex exponential, the resulting analogue, z → e C (z), satisfies:

e C (0) = 0, d/dz(e C (z)) = 1 and e C (T z) = T e C (z) + e C (z) q .
This is what we call the Carlitz exponential and the action u → T u + u q leads to the definition of the Carlitz F q [T ]-module, which is in fact a particular case of Drinfeld module. The Carlitz exponential, e C (z), may be defined by the following infinite product:

e C (z) = z a∈Fq[T ], a =0 (1 - z a Π q )
where

Π q = (-T ) q q-1 ∞ j=1 1 - 1 T q j -1 -1
.

Since e z = 1 if and only if z ∈ 2πiZ and since e C (z) was constructed by analogy such that e C (z) = 0 if and only if z ∈ Π q F q [T ] (in other words the kernel of e C (z) is Π q F q [T ]), we get a good analogue Π q of 2πi. In order to obtain a good analogue of the real number π, we take its one unit part and hence we obtain:

Π q = ∞ j=1 1 - 1 T q j -1 -1 .
For more details about analogs given by the theory of Carlitz modules, and in particular about the exponential function or its fundamental period Π q , we refer the reader to the monographs [START_REF] Goss | Basic Structures of Function Field Arithmetic[END_REF][START_REF] Thakur | Function Field Arithmetic[END_REF].

If we look for the Laurent series expansion of Π q , then we obtain that

Π q = ∞ j=1 1 - 1 T q j -1 -1 = n≥0 a n T -n ,
where a n is defined as the number of partitions of n whose parts take values in I = {q j -1, j ≥ 1}, taken modulo p.

To compute the complexity of Π q , we would like to find a closed formula or some recurrence relations for the sequence of partitions (a n ) n≥0 . This question seems quite difficult and we are not able to solve it at this moment.

However, it was shown in [6] that the inverse of Π q has the following simple Laurent series expansion:

1 Π q = ∞ j=1 1 - 1 X q j -1 = ∞ n=0 p n X -n
where the sequence p q = (p(n)) n≥0 is defined as follows:

(2)

p n =      1 if n = 0; (-1) card J if there exists a set J ⊂ N * such that n = j∈J (q j -1); 0 if there is no set J ⊂ N * such that n = j∈J (q j -1).
We mention that if such a decomposition exists, it is unique.

In the rest of this section we will prove Theorem 1.2 and 1.3.

3.1. Proof of Theorem 1.2. In this part we study the sequence p 2 = (p

(2)
n ) n≥0 , defined by the formula (2) in the case where q = 2. More precisely:

(3)

p (2) n = 1 if n = 0 or if there exists J ⊂ N * such that n = j∈J (2 j -1); 0 otherwise.
In order to lighten the notations, in the rest of this subsection we set

p n := p (2) n so that p 2 = p 0 p 1 p 2 • • • .
For every n ≥ 1, we denote by W n the factor of p 2 that occurs between positions 2 n -1 and 2 n+1 -2, that is:

W n := p 2 n -1 • • • p 2 n+1 -2 .
We also set W 0 := 1. Observe that |W n | = 2 n . With these notations the infinite word p 2 can be factorized as:

p 2 = 1 W 0 10 W 1 1100 W 2 11011000 W 3 • • • = W 0 W 1 W 2 • • • .
In order to compute the complexity function of p 2 , we need the following lemmas.

Lemma 3.1. Let n and k be two positive integers such that: k < 2 n -1. Then k can be written as j∈J (2 j -1) if and only if k + (2 n -1) can be written as i∈I (2 i -1), where I and J are finite subsets of N * . Remark 3.1. This is equivalent to say that a k = 1 if and only if a k+(2 n -1) = 1.

Proof. The first part is pretty obvious. If k = j∈J (2 j -1), then:

k + (2 n -1) = j∈J (2 j -1) + (2 n -1) = j∈J∪{n} (2 j -1).
For the second part, let suppose that k + (2 n -1) = i∈I (2 i -1). We prove that k can be also represented in this form. More precisely, we show that n ∈ I and consequently k = i∈I\{n} (2 i -1).

Notice that I cannot contain any index greater than n since k < 2 n -1. We argue by contradiction and we assume that I does not contain n. Then

i∈I (2 i -1) < 2 n -1 since i∈I (2 i -1) ≤ n-1 i=1 (2 i -1) = 2(2 n-1 -1) -(n -1) = 2 n -n -1 < 2 n -1. Hence, if n does not belong to I, then k + (2 n -1) < 2 n -1 which is absurd. Consequently, n belongs to I and thus k = i∈I\{n} (2 i -1). Lemma 3.2. For every n ≥ 2 we have W n = 1W 1 W 2 • • • W n-1 0.
Proof. Clearly, the word W n begins with 1 because p 2 n -1 = 1. The word W n ends with 0 since the last letter is p 2 n+1 -2 = 0. To explain the structure of W n , we split the word W n into subwords as follows:

W n = p 2 n -1 1 p (2 n -1)+(2-1) p (2 n -1)+(2 2 -2) W ′ 1 p (2 n -1)+(2 2 -1) • • • p (2 n -1)+(2 3 -2) W ′ 2 • • • p (2 n -1)+(2 n-1 -1) • • • p (2 n -1)+(2 n -2) W ′ n-1 p 2 n+1 -2 0 .
Since by Lemma 3.1 p (2 n -1)+k = p k for k < 2 n -1, we obtain that

W ′ i = W i , for 1 ≤ i ≤ n -1.
Since the subword W n ends with 0, we can define U n by W n := U n 0, for every n ≥ 1. Thus,

U 1 = 1, U 2 = 110. Lemma 3.3. For every n ≥ 1, we have U n+1 = U n U n 0. Proof. By Lemma 3.2, U n = 1W 1 W 2 • • • W n-1 for all n ≥ 2. Consequently: U n+1 = 1W 1 W 2 • • • W n-1 Un W n = U n W n = U n U n 0 Wn .
Lemma 3.4. For every n ≥ 2, there exists a word Z n such that W n = 1Z n 10 n and 0 n ⋪ Z n (in other words W n ends with exactly n zeros and Z n does not contain blocks of 0 of length larger than n -1). This is equivalent to say that U n = 1Z n 10 n-1 and 0 n ⋪ Z n .

Proof. We argue by induction on n.

For n ≥ 2, W 2 = 1100 ends with two zeros and obviously there are no other zeros.

We assume that W n ends with n zeros and does not contain other block of zeros of length greater than n -1. We show this statement holds for n + 1. By Lemma 3.3

W n+1 = U n+1 0 = U n U n 00.
As U n ends exactly with n -1 zeros (by induction hypothesis), then W n+1 ends also by n + 1 zeros. Since we have that U n = 1Z n 10 n-1 and 0 n ⋪ Z n then W n+1 = 1Z n 10 n-1 1Z n 10 n-1 00 = 1Z n+1 0 n+1 , when Z n+1 := Z n 10 n-1 1Z n . Since 0 n ⋪ Z n , then 0 n+1 ⋪ Z n+1 . This completes the proof.

Lemma 3.5. For every n ≥ 1, let A n := {U 2 n 0 k , k ≥ 1}. Then p 2 ∈ A N n . Proof. Let n ≥ 1.
By definition of W n and U n and by Lemma 3.2, the infinite word p 2 can be factorized as:

(4) p 2 = 1W 1 W 2 • • • W n-1 Un U n 0 Wn U n+1 0 W n+1 U n+2 0 W n+2 • • • .
We prove that for every positive integer k, there exist a positive integer r and k 1 , k 2 , . . . , k r ∈ N * such that:

(5)

U n+k = U 2 n 0 k 1 U 2 n 0 k 2 • • • U 2 n 0 kr . We argue by induction on k. For k = 1, we have U n+1 = U n U n 0 = U 2
n 0. We suppose that the relation ( 5) is true for k and we show it for k + 1. By Lemma 3.3:

U n+k+1 = U n+k U n+k 0 = U 2 n 0 k 1 U 2 n 0 k 2 • • • U 2 n 0 kr U 2 n 0 k 1 U 2 n 0 k 2 • • • U 2 n 0 kr+1
. By equality (4), this ends the proof.

Fix m ∈ N. Then, there is a unique integer n such that:

(6) 2 n-1 < m ≤ 2 n .
Lemma 3.6. Let m ∈ N. All distinct words of length m of p 2 occur in the prefix:

P m = W 0 W 1 • • • W m .
Proof. Let m, n be some positive integer satisfying 6.

We show that all distinct words of length m occur in the prefix

P m = W 0 W 1 W 2 • • • W n-1 W n • • • W m = U n U n 0 Wn U n U n 00 W n+1 U n U n 0U n U n 000 W n+2 • • • W m ;
the second identity follows by Lemmas 3.2 and 3.3. Notice that we have to consider all the words till W m because the word 0 m first occurs in W m . Also, by Lemma 3.4 and using the identity (5), W i ends with U n U n 0 i-n+1 , for every i ≥ n + 1. Consequently, all the words

U n U n 0 k , 0 ≤ k ≤ m -n + 1 are factors of P m .
Moreover, notice that if

B n := {U n U n 0 k , 0 ≤ k ≤ m -n + 1}, then P m ∈ B *
n . This follows from Lemmas 3.5 and 3.4 (there are no blocks of zeros of length greater than

m in W 0 W 1 • • • W m ).
After the occurrence of W m , it is not possible to see new different subwords of length m. Indeed, suppose that there exists a word F of length m that occur in W m+1 W m+2 W m+3 • • • and does not occur in P m . Then, by Lemma 3.5 and by the remark above, F must occur in the words U n 0 k U n , with k ≥ m -n + 1. But since U n ends with n -1 zeros (by Lemma 3.4), F must be equal to 0 m or 0 i P i , where i ≥ m -n + 2 and P i ≺ p U n , or F must occur in U n . But all these words already occur in P m . This contradicts our assumption.

3.1.1. An upper bound for p( 1 Π 2 , m). In this part we prove the following result.

Proposition 3.1.

p(p 2 , m) ≤ (m -log m)(m + log m + 2) 2 + 2m.
Proof. In order to find all different factors of length m that occur in p 2 , it suffices, by Lemmas 3.5 and 3.6, to consider factors appearing in the word

U n U n and in the sets i(U n , 0 k , U n ), where 1 ≤ k ≤ m -n.
In the word U n U n we can find at most

|U n | distinct words of length m. Since |U n | = 2 n -1 and 2 n-1 < m ≤ 2 n , the number of factors of length m that occur in U n U n is at most 2 n , so at most 2m. Also, it is not difficult to see that i(U n , 0 k , U n ) ∩ A m ≤ m -k + 1.
The total number of subwords occurring in all these sets, for 1 ≤ k ≤ m -n, is less than or equal to:

m-n k=1 (m -k + 1) = (m + 1)(m -n) - (m -n)(m -n + 1) 2 .
Counting all these words and using the fact that 2 n-1 < m ≤ 2 n , we obtain that:

p(p 2 , m) ≤ 2m + (m -n)(m + n + 1) 2 < (m -log m)(m + log m + 2) 2 + 2m
as claimed.

3.1.2.

A lower bound for p( 1 Π 2 , m). In this part we prove the following result. Proposition 3.2.

p(p 2 , m) ≥ (m -log m)(m -log m + 1) 2 .
Proof. By Lemma 3.6, we have to look for distinct words of length m occurring in

W n W n+1 • • • W m .
In order to prove this proposition, we use the final blocks of 0 from each W i . These blocks are increasing (as we have shown in Lemma 3.4). First, in the word W m we find for the first time the word of length m: 0 m . In the set i(W m-1 , ε, W m ), we find two distinct words of length m that cannot be seen before (10 m-1 and 0 m-1 1) since there are no other words containing blocks of zeros of length m -

1 in i(W k , ε, W k+1 ), for k < m -1. More generally, fix k such that n ≤ k ≤ m -2. Since W k W k+1 = 1Z k 10 k W k 1Z k+1 10 k+1 W k+1 , in i(W k , ε, W k+1 ) we find m -k + 1 words of length m of form α k 0 k β k .
More precisely, the words we count here are the following:

S m-k-1 10 k , S m-k-2 10 k 1, S m-k-3 10 k 1T 1 ,..., S 1 0 k 1T m-k-2 , 0 k 1T m-k-1 , where S i ≺ s Z k and T i ≺ p Z k+1 , |S i | = |T i | = i, for every integer i, 1 ≤ i ≤ m -k -1.
All these words cannot be seen before, that is in i(W s , ε, W s+1 ), for s < k, since there are no blocks of zeros of length k before the word W k (according to Lemma 3.4). Also, in i(W s , ε, W s+1 ), for s > k, we focus on the words α s 0 s β s and hence they are different from all the words seen before (because k < s).

Consequently, the total number of subwords of length m of form α k 0 k β k considered before, is equal to

1 + 2 + . . . + (m -n + 1) = (m -n + 1)(m -n + 2) 2 .
Since 2 n-1 < m ≤ 2 n we obtain the desired lower bound.

Proof of Theorem 1.2. It follows from Propositions 3.1 and 3.2.

A consequence of Theorem 1.2 and Theorem 1.1 is the following result of transcendence.

Corollary 3.1. Let K be a finite field and (p

(2)
n ) n≥0 the sequence defined in (3). Let us consider the associated formal series over K:

f (T ) := n≥0 p (2) n T -n ∈ K[[[T -1 ]].
Then f is transcendental over K(T ).

Notice that, if K = F 2 then the formal series f coincide with 1/Π 2 and hence Corollary 3.1 implies Corollary 1.1.

Remark 3.2. In [7], the authors proved that the sequence p 2 is the fixed point of the morphism σ defined by σ(1) = 110 and σ(0) = 0.

In an unpublished note [5], Allouche showed that the complexity of the sequence p 2 satisfies, for all m ≥ 1, the following inequality:

p(p 2 , m) ≥ Cm log m,
for some strictly positive constant C.

3.2.

Proof of Theorem 1.3. In this part we study the sequence p q = (p (q) n ) n≥0 defined by the formula (2) in the case where q ≥ 3. In the following, we will consider the case q = p n , where p ≥ 3.

Proposition 3.3. Let q ≥ 3. For every positive integer m: p(p q , m) ≤ (2q + 4)m + 2q -3.

In particular, this proves the Theorem 1.3. Indeed, we do not have to find a lower bound for the complexity function, as the sequence p q is not eventually periodic (see Remark 3.5) and thus, by the inequality (1) we have that:

p(p q , m) ≥ m + 1, for any m ≥ 0.
In order to lighten the notations, we set in the sequel p n := p (q) n so that p q = p 0 p 1 p 2 • • • .

For every n ≥ 1, we denote by W n the factor of p q defined in the following manner:

W n := p q n -1 • • • p q n+1 -2 .
Let us fix W 0 := 0 q-2 = 00 • • • 0 q-2 and α 0 := q -2. Thus W 0 = 0 α 0 .

In other words, W n is the factor of p q occurring between positions q n -1 and q n+1 -2. Notice that |W n | = q n (q -1).

With these notations the infinite word p q may be factorized as follows:

p q = 1 00 • • • 0 W 0 (-1)00 • • • 0 W 1 (-1) • • • 00100 • • • 0 W 2 (-1)00 • • • .
In the following, we prove some lemmas that we use in order to bound from above the complexity function of p q . Lemma 3.7. Let k and n be two positive integers such that:

k ∈ 2(q n -1), q n+1 -2 .
Then there is no set J ⊂ N * such that k = j∈J (q j -1). In other words, p k = 0.

Proof. We argue by contradiction and we assume that there exists a set J such that k = j∈J (q j -1). Since k < q n+1 -1, then obviously J must be a subset of {1, 2, 3, . . . , n}. Consequently

k = j∈J (q j -1) ≤ n j=1 (q j -1). Then k ≤ n j=1 (q j -1) = q q n -1 q -1 -n < 2(q n -1) < k
which is absurd.

Lemma 3.8. Let k and n be two positive integers such that: k < q n -1.

Then k can be written as j∈J (q j -1) if and only if k + (q n -1) can be written as j∈I (q j -1), where I and J are finite subsets of N * . Moreover, J ∪ {n} = I.

Remark 3.3. This is equivalent to say that p k = -p k+(q n -1) for k and n two positive integers such that k < q n -1.

Proof. The proof is similar to that of Lemma 3.1 (just replace 2 by q).

If W = a 1 a 2 • • • a l ∈ {0, 1, -1} l then set W := (-a 1 )(-a 2 ) • • • (-a l ).
Lemma 3.9. For every n ≥ 1 we have the following:

W n = (-1) W 0 W 1 • • • W n-1 0 αn
with α n = (q n+1 -1) -2(q n -1).

Proof. Obviously, the word W n begins with -1 since p q n -1 = -1. In order to prove the relation above it suffices to split W n into subwords as follows:

W n = p q n -1 -1 0 • • • 0 W ′ 0 p (q n -1)+(q-1) p (q n -1)+(q 2 -2) W ′ 1 p (q n -1)+(q 2 -1) • • • p (q n -1)+(q 3 -2) W ′ 2 • • • p (q n -1)+(q n-1 -1) • • • p (q n -1)+(q n -2) W ′ n-1 p 2(q n -1) • • • p q n+1 -2 0 αn .
Since p (q n -1)+k = -p k , for every k < q n -1 (by Lemma 3.8), we obtain that W ′ i = W i , for 0 ≤ i ≤ n -1. Lemma 3.10 ends the proof.

Since the subword W n ends with 0 αn , we can define U n as prefix of W n such that W n := U n 0 αn , for every n ≥ 1. Notice that |U n | = q n -1.

Lemma 3.10. For every n ≥ 1, we have

U n+1 = U n U n 0 αn . Proof. By Lemma 3.9, U n = (-1) W 0 W 1 • • • W n-1 . Consequently: U n+1 = (-1) W 0 W 1 • • • W n-1 Un W n = U n U n 0 αn = U n U n 0 αn .
Remark 3.4. Since q ≥ 3 we have α n ≥ |U n | for every n ≥ 1. Moreover (α n ) n≥1 is a positive and increasing sequence.

Lemma 3.11. For every n ≥ 1, let A n := {U n , U n , 0 α i , i ≥ n}. Then p q ∈ A N n . Proof. Let n ≥ 1.
By definition of W n and U n , the infinite word p q can be factorized as:

p q = 1W 0 W 1 • • • W n-1 Vn W n W n+1 • • • . By Lemma 3.9, since U n = (-1) W 0 W 1 • • • W n-1 then the prefix V n = U n . Also, W n+1 = U n U n 0 αn 0 α n+1 , W n+2 = U n U n 0 αn U n U n 0 αn+α n+1 +α n+2
. Keeping on this procedure, W n can be written as a concatenation of U n , U n and 0 α i , i ≥ n. More precisely, p q can be written in the following manner:

p q = U n U n 0 αn Wn U n U n 0 αn+α n+1 W n+1 U n U n 0 αn U n U n 0 αn+α n+1 +α n+2 W n+2 • • • .
Proof of Proposition 3.3. Let m ∈ N. Then there exists a unique positive integer n, such that:

q n-1 -1 ≤ m < q n -1.
By Lemma 3.11 and the Remark 3.4, between the words U n and U n (when they do not occur consecutively), there are only blocks of zeros of length greater than α n ≥ |U n | = q n -1 and thus greater than m. Hence, all distinct factors of length m appear in the following words:

U n U n , U n U n , 0 αn U n , 0 αn U n , U n 0 αn and U n 0 αn . In U n U n we may find at most |U n U n | -m + 1 = 2|U n | -m + 1 factors at length m.
In U n U n we may find at most m -1 new different factors of length m. More precisely, they form the set i( U n , ε, U n ) + .

In 0 αn U n (respectively 0 αn U n , U n 0 αn , U n 0 αn ) we may find at most m (respectively m -1) new different factors (they belong to i(0 αn , ε, U n ) + ∪ {0 m }, respectively i(0 αn , ε, U n ) + , i(U n , ε, 0 αn ) + and i( U n , ε, 0 αn ) + ).

Consequently, the number of such subwords is at most 2|U n | + 4m -3. Since U n = q n -1 = q(q n-1 -1) + q -1 ≤ qm + q -1 we obtain that: p(p q , m) ≤ 2(qm + q -1) + 4m -3 ≤ (2q + 4)m + 2q -3.

Remark 3.5. It is not difficult to prove that p q is not eventually periodic. Indeed, recall that p q = W 0 W 1 W 2 • • • . Using Theorem 3.9 and the Remark 3.4, (7)

p q = A 1 0 l 1 A 2 0 l 2 • • • A i 0 l i • • • ,
where A i , i ≥ 1, are finite words such that A i = 0 |A i | and (l i ) i≥1 is a strictly increasing sequence.

Remark 3.6. This part concerns the case where q ≥ 3. If the characteristic of the field is 2, that is, if q = 2 n , where n ≥ 2, then, in the proof we have that -1 = 1, but the structure of p q remain the same. We will have certainly a lower complexity, but p q is still on the form (7), and thus p(p q , m) ≤ (2q + 4)m + 2q -3.

Closure properties of two classes of Laurent series

It is natural to classify Laurent series in function of their complexity. In this section we study some closure properties for the following classes:

P = {f ∈ F q ((T -1 )), there exists K such that p(f, m) = O(m K )}
and, more generally,

Z = {f ∈ F q ((T -1 )), such that h(f ) = 0}.
Clearly, P ⊂ Z. We recall that h is the topological entropy defined in Section 2.

We have already seen, in Theorem 1.1, that the algebraic Laurent series belong to P and Z. Also, by Theorem 1.2 and 1.3, 1 Πq belongs to P. Hence, P, and more generally Z, seem to be two important objects of interest for this classification.

The main result we will prove in this section is Theorem 1.4. In the second part, we will prove the stability of P and Z under Hadamard product, formal derivative and Cartier operator. Proposition 4.1. Let f and g be two Laurent series belonging to F q ((T -1 )). Then, for every integer m ≥ 1, we have:

p(f, m) p(g, m) ≤ p(f + g, m) ≤ p(f, m)p(g, m). Proof. Let f (T ) := i≥-i 1 a i T -i and g(T ) := i≥-i 2 b i T -i , i 1 , i 2 ∈ N.
By definition of the complexity of Laurent series (see Section (2.1)), for every m ∈ N:

p(f (T ) + g(T ), m) = p( i≥0 c i T -i , m),
where c i := (a i + b i ) ∈ F q . Thus we may suppose that

f (T ) := i≥0 a i T -i and g(T ) := i≥0 b i T -i .
We denote by a := (a i ) i≥0 , b := (b i ) i≥0 and c := (c i ) i≥0 .

For the sake of simplicity, throughout this part, we set x(m) := p(f, m) and y(m) := p(g, m). Let L f,m := {U 1 , U 2 , . . . , U x(m) } (resp. L g,m := {V 1 , V 2 , . . . , V y(m) }) be the set of different factors of length m of the sequence of coefficients of f (respectively of g). As the sequence of coefficients of the Laurent series f + g is obtained by the termwise addition of the sequence of coefficients of f and the sequence of coefficients of g, we deduce that:

L f +g,m ⊆ {U i + V j , 1 ≤ i ≤ x(m), 1 ≤ j ≤ y(m)}
where L f +g,m is the set of all distinct factors of length m occurring in c, and where the sum of two words with the same length

A = a 1 • • • a m and B = b 1 • • • b m is defined as A + B = (a 1 + b 1 ) • • • (a m + b m )
(each sum being considered over F q ). Consequently, p(f +g, m) ≤ p(f, m)p(g, m).

We shall prove now the first inequality using Dirichlet's principle. Notice that if x(m) < y(m) the inequality is obvious.

Assume now that x(m) ≥ y(m). Remark that if we extract x(m) subwords of length m from b, there is at least one word which appears at least Consider all distinct factors of length m of a: U 1 , U 2 , . . . , U x(m) , that occur in positions i 1 , i 2 , . . . , i xm . Looking in the same positions in b, we have x(m) factors of length m belonging to L g,m . Since x(m) ≥ y(m), by the previous remark, there is one word W which occur at least x(m) y(m) times in b. Since we have U i + W = U j + W if U i = U j , the conclusion follows immediately.

Remark 4.1. In fact, the first inequality may also be easily obtained from the second one, but we chose here to give a more intuitive proof. Indeed, if we denote

f := h 1 + h 2 , g := -h 2 , where h 1 , h 2 ∈ F q ((T -1 )), the first relation follows immediately, since p(h 2 , m) = p(-h 2 , m), for any m ∈ N. Remark 4.2. If f ∈ F q ((T -1
)) and a ∈ F q [T ] then, obviously, there exists a constant C (depending on the degree of the polynomial a) such that, for any m ∈ N,

p(f + a, m) ≤ p(f, m) + C.
Remark 4.3. Related to Proposition 4.1, one can naturally ask if it is possible to saturate the inequalities in Proposition 4.1. By Remark 4.1, it suffices to show that this is possible for one inequality. In the sequel, we construct two explicit examples of Laurent series of linear complexity such that their sum has quadratic complexity.

Let α and β be two irrational numbers such that 1, α and β are linearly independent over Q. For any i ∈ {α, β} we consider the following rotations:

R i : T 1 → T 1 x → {x + i},
where T 1 is the circle R/Z, identified to the interval [0, 1). We may partition T 1 in two intervals I 0 i and I 1 i , delimited by 0 and 1 -i. We denote by ν i the coding function:

ν i (x) = 0 if x ∈ I 0 i ; 1 if x ∈ I 1
i . We define a := (a n ) n≥0 such that, for any n ≥ 0,

a n = ν α (R n α (0)) = ν α ({nα}) and b := (a n ) n≥0 such that, for any n ≥ 0, b n = ν β (R n β (0)) = ν β ({nβ}).
Let us consider f (T ) = n≥0 a n T -n and g(T ) = n≥0 b n T -n be two elements of F 3 ((T -1 )). We will prove that, for any m ∈ N, we have:

(8) p(f + g, m) = p(f, m)p(g, m).
We thus provide an example of two infinite words whose sum has a maximal complexity, in view of Proposition 4.1.

A sequence of form (ν(R n α (x))) n≥0 is a particular case of rotation sequences. It is not difficult to see that the complexity of the sequence a satisfies p(a, m) = m + 1 for any m ∈ N and hence a is Sturmian. For a complete proof, the reader may consult the monograph [START_REF] Fogg | Substitutions in Dynamics, Arithmetics and Combinatorics[END_REF], but also the original paper of Morse and Hedlund [START_REF] Morse | Symbolic dynamics[END_REF], where they prove that every Sturmian sequence is a rotation sequence.

Let m ∈ N. Let L a,m := {U 1 , U 2 , . . . , U m+1 }
and respectively L b,m := {V 1 , V 2 , . . . , V m+1 } be the set of distinct factors of length m that occur in a, respectively in b.

In order to prove the relation (8), we show that

(9) L a+b,m = {U i + V j , 1 ≤ i, j ≤ m + 1}.
Let I := [0, 1). It is well-known (see for example Proposition 6.1.7 in [START_REF] Fogg | Substitutions in Dynamics, Arithmetics and Combinatorics[END_REF]) that, using the definition of the sequence a (respectively of b), we can split I in m + 1 intervals of positive length J 1 , J 2 , . . . , J m+1 (respectively

L 1 , L 2 , . . . , L m+1 ) corresponding to U 1 , U 2 , . . . , U m+1 (respectively V 1 , V 2 , . . . , V m+1 ) such that: {nα} ∈ J k if and only if a n a n+1 • • • a n+m-1 = U k (respectively {nβ} ∈ L k if and only if b n b n+1 • • • b n+m-1 = V k .)
In other words, {nα} ∈ J k (resp. {nβ} ∈ L k ) if and only if the factor U k (resp.V k ) occurs in a (resp. b) at the position n. Now we use the well-known Kronecker's theorem which asserts that the sequence of fractional parts ({nα}, {nβ}) n≥0 is dense in the square [0, 1) 2 since by assumption 1, α and β are linearly independent over Q.

In particular, this implies that, for any pair (i, j) ∈ {0, 1, . . . , m + 1} 2 , there exists a positive integer n such that ({nα}, {nβ}) ∈ J i × L k . This is equivalently to say that, for any pair of factors (U i , V j ) ∈ L a,m × L b,m , there exists n such that

U i = a n a n+1 • • • a n+m-1 and V k = b n b n+1 • • • b n+m-1 .
This proves Equality (9) and more precisely, since we are in characteristic 3, we have the following equality:

Card L a+b,m = Card L a,m • Card L b,m = (m + 1) 2 .
We point out the following consequence of Proposition 4.1.

Corollary 4.1. Let f 1 , f 2 , . . . , f l ∈ F q ((T -1 )). Then for every m ∈ N and for every integer i ∈ [1; l] we have the following:

p(f i , m) j =i,1≤j≤l p(f j , m) ≤ p(f 1 + f 2 + • • • + f l , m) ≤ 1≤j≤l p(f j , m).
Notice that these inequalities can be saturated, just generalizing the construction above (choose l Sturmian sequences of irrational slopes α 1 , α 2 , . . . , α l , such that 1, α 1 , α 2 , . . . , α l are linearly independent over Q).

We shall prove next that the sets P and Z are closed under multiplication by rationals. Let us begin with a particular case, that is the multiplication by a polynomial. Proposition 4.2. Let b(T ) ∈ F q [T ] and f (T ) ∈ F q ((T -1 )). Then there is a positive constant M (depending only on b(T )), such that for all m ∈ N:

p(bf, m) ≤ M p(f, m). Proof. Let b(T ) := b 0 T r + b 1 T r-1 + • • • + b r ∈ F q [T ] and f (T ) := i≥-i 0 a i T -i ∈ F q ((T -1 )), i 0 ∈ N. Then b(T )f (T ) = b(T )   -1 i=-i 0 a i T -i + i≥0 a i T -i   = b(T ) -1 i=-i 0 a i T -i + b(T )   i≥0 a i T -i   . (10) Now, the product b(T )( i≥0 a i T -i ) = T r (b 0 + b 1 T -1 + b 2 T -2 + • • • + b r T -r )( i≥0 a i T -i ) := T r ( j≥0 c j T -j ) (11)
where the sequence c := (c j ) j≥0 is defined as follows:

c j = b 0 a j + b 1 a j-1 + • • • + b j a 0 if j < r b 0 a j + b 1 a j-1 + • • • + b r a j-r if j ≥ r.
According to definition of complexity (see Section 2.1) and to relations (10) and (11), for every m ∈ N, we have

p (b(t)f (T ), m) = p   b(T )( i≥0 a i T -i ), m   = p   ( j≥r c j T -j ), m   .
Our aim is to count the number of words of form c j c j+1 • • • c j+m-1 , when j ≥ r. By definition of c, we notice that for j ≥ r these words depend only on a j-r a j-r+1 • • • a j+m-1 and of b 0 , b 1 , • • • , b r , which are fixed. The number of words a j-r a j-r+1 • • • a j+m-1 is exactly p(f, m + r). By Lemma 2.1 we obtain:

p(f, m + r) < p(f, r)p(f, m) = M p(f, m), where M = p(f, r). More precisely, we may bound up M by q r , since this is the number of all possible words of length r over an alphabet of q letters.

Proposition 4.3. Let r(T ) ∈ F q (T ) and f (T ) = n≥-n 0 a n T -n ∈ F q ((T -1 )).
Then for every m ∈ N, there is a positive constant M , depending only on r and n 0 , such that:

p(rf, m) ≤ M p(f, m). Proof. Let f (T ) := i≥-i 0 a i T -i ∈ F q ((T -1
)), i 0 ∈ N and m ∈ N. By Proposition 4.1, we have:

p(r(T )f (T ), m) ≤ p r(T )( -1 i=-i 0 a i T -i ), m • p   r(T )( i≥0 a i T -i ), m   . Proposition 4.2 implies that p r(T )( -1 i=-i 0 a i T -i ), m ≤ R
where R does not depend on m. Thus, we may assume that f (T ) =

i≥0 a i T -i .
The proof of Proposition 4.3 is decomposed into five steps.

Step 1. Since r(T ) ∈ F q (T ), the sequence of coefficients of r is eventually periodic. Thus, there exist two positive integers S and L and two polynomials p 1 ∈ F q [T ] (with degree equal to S -1) et p 2 ∈ F q [T ] (with degree equal to L -1) such that r may be written as follows:

r(T ) = P (T ) Q(T ) = p 1 (T ) T S-1 + p 2 (T ) T S+L-1 (1 + T -L + T -2L + • • • ). Hence r(T )f (T ) = 1 T S-1 p 1 (T )f (T ) g(T ) + p 2 (T ) 1 T S+L-1 f (T )(1 + T -L + T -2L • • • ) h(T ) := n≥0 f n T -n . ( 12
)
Let us denote by d = (d(n)) n≥0 the sequence of coefficients of g(T ) and by e = (e n ) n≥0 the sequence of coefficients of h(T ). Clearly f := (f n ) n≥0 is such that f n = d n + e n , for every n ∈ N.

Fix m ∈ N. Our aim is to bound from above p(f, m). First, assume that m is a multiple of L. More precisely, we set m = kL, where k ∈ N.

In order to bound the complexity of f, we will consider separately the sequences e and d.

Step 2. We study now the sequence e, defined in (12). In order to describe the sequence e, we shall study first the product

f (T )(1+T -L +T -2L +• • • ) = ( i≥0 a i T -i )(1+T -L +T -2L +• • • ) := j≥0 c j T -j .
Expanding this product, it is not difficult to see that:

c l = a l if l < L and c kL+l = a l + a l+L + • • • + a kL+l , for k ≥ 1 and 0 ≤ l ≤ L -1.
By definition of c n , n ∈ N, we can easily obtain:

c n+L -c n = a n+L .
Consequently, for all s ∈ N:

(13) c n+sL -c n = a n+sL + a n+(s-1)L + • • • + a n+L .
Our goal is now to study the subwords of c with length m = kL. Let j ≥ 0 and let c j c j+1 c j+2 • • • c j+kL-1 be a finite factor of length m = kL. Using identity (13), we may split the factor above in k words of length L as follows:

c j c j+1 c j+2 • • • c j+kL-1 = c j c j+1 • • • c j+L-1 D 1 c j+L c j+L+1 • • • c j+2L-1 D 2 • • • ... c j+(k-1)L c j+(k-1)L+1 • • • c j+kL-1 D k
where the words D i , 2 ≤ i ≤ k depend only on D 1 and a. More precisely, we have:

D 2 = (c j + a j+L )(c j+1 + a j+L+1 ) • • • (c j+L-1 + a j+2L-1 ) . . . D k = (c j + a j+L + • • • + a j+(k-1)L )(c j+1 + a j+L+1 + • • • + a j+(k-1)L+1 ) • • • (c j+L-1 + a j+2L-1 + • • • + a j+kL-1 ).
Consequently, the word c j c j+1 c j+2 • • • c j+m-1 depends only on D 1 , which is a factor of length L, determined by r(T ), and on the word

a j+L • • • a j+kL-1 , factor of length kL -L = m -L of a.
Now, let us return to the sequence e. We recall that ( 14)

n≥0 e n T -n = p 2 (T ) T S+L-1 j≥0 c j T -j .
Using a similar argument as in the proof of Proposition 4.2 and using the identity (14), a factor of the form e j e j+1 • • • e j+m-1 , j ∈ N, depends only on the coefficients of p 2 , which are fixed, and on

c j-L+1 • • • c j-1 c j • • • c j+m-1 .
Hence, the number of distinct factors of the form e j e j+1 • • • e j+m-1 depends only on the number of distinct factors of the form a j+1 a j+2 • • • a j+(k-1)L and on the number of factors of length L that occur in c.

Step 3. We describe now the sequence d, defined in (12). Doing the same proof as for Proposition 4.2, we obtain that the number of words d j • • • d j+m-1 , when j ∈ N, depends only on the coefficients of p 1 , which are fixed, and on the number of distinct factors

a j-S+1 • • • a j • • • a j+m-1 .
Step 4. We now give an upper bound for the complexity of f, when m is a multiple of L.

According to steps 2 and 3, the number of distinct factors of the form

f j f j+1 • • • f j+m-1 , j ∈ N,
depends on the number of distinct factors of form a j-S+1 a j+2 • • • a j+m-1 and on the number of factors of length L that occur in c.

Consequently, p(rf, m) ≤ p(f, m + S -1)q L , and by Lemma 2.1 p(f, m + S -1) ≤ p(f, m)p(f, S -1) ≤ q S-1 p(f, m).

Finally, p(rf, m) ≤ q L+S-1 p(f, m).

Step 5. We now give an upper bound for the complexity of f, when m is not a multiple of L.

In this case, let us suppose that m = kL + l, 1 ≤ l ≤ L -1. Using Lemma 2.1 and according to Step 4:

p(rf, m) = p(rf, kL + l) ≤ p(rf, kL)p(rf, l) ≤ p(rf, kL)p(rf, L -1) ≤ q L-1 p(rf, kL) ≤ q S+2L-2 p(f, m).

A criterion for linear independence of Laurent series.

As a consequence of Theorem 1.4, we give a criterion of linear independence over F q (T ) for two Laurent series in function of their complexity.

Proposition 4.4. Let f, g ∈ F q ((T -1 )) be two irrational Laurent series such that:

lim m→∞ p(f, m) p(g, m) = ∞.
Then f and g are linearly independent over the field F q (T ).

Proof. We argue by contradiction. Assume there exist polynomials A(T ), B(T ), C(T ) over F q , not all zeros, such that:

A(T )f (T ) + B(T )g(T ) + C(T ) = 0.
Next use the fact that addition with a rational function and multiplication by a rational function do not increase the asymptotic order of complexity. Indeed, since A(T ) = 0 because g(T ) / ∈ F q (T ), we would have

f (T ) + C(T ) A(T ) = - B(T ) A(T ) g(T ).
However, Propositions 4.1 and 4.3 would imply that the complexity of the left-hand side of this inequality is asymptotically larger than the one of the right-hand side.

Let us now give an example of two Laurent series linearly independent over F q (T ). Their sequences of coefficients are generated by non-uniform morphisms and we study their subword complexity in function of the order of growth of letters, using a classical result of Pansiot [START_REF] Pansiot | Subword Complexities and Iteration[END_REF]. Notice that, the following sequences are non-automatic and hence, the associated Laurent series are transcendental over F q (T ). Now we consider the formal series whose coefficients are the sequences generated by the morphisms above:

f (T ) = n≥0 a n T -n = 1 T 3 + 1 T 7 + 1 T 11 + 1 T 12 + • • • ∈ F q [[T -1 ]]
and

g(T ) = n≥0 b n T -n = 1 T 1 + 1 T 3 + 1 T 4 + 1 T 6 + • • • ∈ F q [[T -1 ]].
Since lim m→∞ p(f, m)/p(g, m) = +∞, Proposition 4.4 implies that f and g are linearly independent over F q (T ).

4.2.

Other closure properties. In this section we prove that the classes P and Z are closed under a number of actions such as: Hadamard product, formal derivative and Cartier operator. be two Laurent series in F q ((T -1 )). The Hadamard product of f and g is defined as follows:

f ⊙ g = n≥-min(n 1 ,n 2 ) a n b n T -n .
As in the case of addition of two Laurent series (see Proposition 4.1) one can easily obtain the following.

Proposition 4.5. Let f and g be two Laurent series belonging to F q ((T -1 )). Then, for every m ∈ N, we have:

p(f, m) p(g, m) ≤ p(f ⊙ g, m) ≤ p(f, m)p(g, m).
The proof is similar to the one of Proposition 4.1. The details are left to the reader. 4.2.2. Formal derivative. As an easy application of Proposition 4.5, we present here the following result. First, let us recall the definition of the formal derivative.

Definition 4.1. Let n 0 ∈ N and consider the Laurent series:

f (T ) = +∞ n=-n 0 a n T -n ∈ F q ((T -1
)). The formal derivative of f is defined as follows:

f ′ (T ) = +∞ n=-n 0 (-n mod p)a n T -n+1 ∈ F q ((T -1 )).
We prove then the following result.

Proposition 4.6. Let f (T ) ∈ F q ((T -1 )) and k be a positive integer. If f (k) is the derivative of order k of f , then there exists a positive constant M , such that, for all m ∈ N, we have:

p(f (k) , m) ≤ M p(f, m).
Proof. The derivative of order k of f is almost the Hadamard product of the series by a rational function. By definition of p(f, m), we may suppose that 4.2.3. Cartier's operators. In the fields of positive characteristic, there is a natural operator, the so-called "Cartier operator" that plays an important role in many problems in algebraic geometry and arithmetic in positive characteristic [16,17,[START_REF] Derksen | A Skolem-Mahler-Lech theorem in positive characteristic and finite automata[END_REF][START_REF] Sharif | Algebraic functions over a field of positive characteristic and Hadamard products[END_REF]. In particular, if we consider the field of Laurent series with coefficients in F q , we have the following definition.

f (T ) := n≥0 a n T -n ∈ F q [[T -1 ]]. Then: f (k) (T ) = n≥k ((-n)(-n -1) • • • (-n -k + 1)a n )T -n-k := T -k n≥k b n a n T -n , where b n := (-n)(-n -1) • • • (-n -k + 1) mod p. Since b n+p = b n , the sequence (b n ) n≥0 is periodic of period p.
Definition 4.2. Let f (T ) = i≥0 a i T -i ∈ F q [[T -1 ]
] and 0 ≤ r < q. The Cartier operator Λ r is a linear transformation such that:

Λ r ( i≥0 a i T -i ) = i≥0 a qi+r T -i .
The classes P and Z are closed under this operator. More precisely, we prove the following result.

Proposition 4.7. Let f (T ) ∈ F q [[T -1 ]] and 0 ≤ r < q. Then there is M such that, for every m ∈ N we have the following:

p(Λ r (f ), m) ≤ qp(f, m) q .
Proof. Let a := (a n ) n≥0 be the sequence of coefficients of f and m ∈ N. In order to compute p(Λ r (f ), m), we have to look at factors of the form a qj+r a qj+q+r • • • a qj+(m-1)q+r , for all j ∈ N. But these only depend on factors of the form a qj+r a qj+r+1 • • • a qj+(m-1)q+r .

Using Lemma 2.1, we obtain that: p(Λ r (f ), m) ≤ p(f, (m -1)q + 1) ≤ qp(f, m -1) q ≤ qp(f, m) q .

Cauchy product of Laurent series

In the previous section, we proved that P and Z are vector space over F q (T ). This raises naturally the question whether or not these classes form a ring; i.e., are they closed under the usual Cauchy product? There are actually some particular cases of Laurent series with low complexity whose product still belongs to P. In this section we discuss the case of automatic Laurent series. However, we are not able to prove whether P or Z are or not rings or fields. 5.1. Products of automatic Laurent series. A particular case of Laurent series stable by multiplication is the class of k-automatic series, k being a positive integer:

Aut k = {f (T ) = n≥0 a n T -n ∈ F q ((T -n )), a = (a n ) n≥0 is k-automatic}.
Since any k-automatic sequence has at most a linear complexity, Aut k ⊂ P. A theorem of Allouche and Shallit [9] states that the set Aut k is a ring.

In particular, this implies that, if f and g belong to Aut k , then p(f g, m) = O(m). Notice also that, in the case where k is a power of p, the characteristic of the field F q ((T -1 )), the result follows from Christol's theorem.

Remark 5.1. However, we do not know whether or not this property is still true if we replace Aut k by ∪ k≥2 Aut k . More precisely, if we consider two Laurent series f, g ∈ (∪ k≥2 Aut k ) we do not know if the product f g is still in P. The next subsection gives a particular example of two Laurent series belonging to (∪ k≥2 Aut k ) and such that the product f g is still in P.

5.1.1. Some lacunary automatic Laurent series. We consider now some particular examples of lacunary series. More precisely, we focus on the product of series of form:

f (T ) = n≥0 T -d n ∈ F q ((T -1 )).
It is not difficult to prove that p(f, m) = O(m). The reader may refer to [START_REF] Gheorghiciuc | The subword complexity of finite and infinite binary words[END_REF] for more general results concerning the complexity of lacunary series. The fact that the complexity of f is linear is implied also by the fact that f ∈ Aut d . Notice also that f is transcendental over F q (T ) if q is not a power of d. This is an easy consequence of Christol's theorem and a theorem of Cobham [19].

In this section we will prove the following result.

Theorem 5.1. Let d and e be two multiplicatively independent positive integers (that is log d log e is irrational) and let f (T ) = n≥0 T -d n and g(T ) = n≥0 T -e n be two Laurent series in F q ((T -1 )). Then:

p(f g, m) = O(m 4 ).
Remark 5.2. The series f and g are linearly independent over F q (T ). More generally, any two irrational Laurent series, d-automatic and respectively e-automatic, where d and e are two multiplicatively independent positive integers, are linearly independent over F q (T ). This follows by a Cobham's theorem.

Let us denote by h(T ) := f (T )g(T ). Then h(T ) = n≥0 a n T -n where the sequence a = (a n ) n≥0 is defined as follows:

a n := (the number of pairs (k, l) ∈ N 2 that verify n = d k + e l ) mod p.

The main clue of the proof is the following consequence of the theory of S-unit equations (see [START_REF] Ta | [END_REF] for a proof).

Lemma 5.1. Let d and e be two multiplicatively independent positive integers. There is a finite number of solutions (k 1 , k 2 , l 1 , l 2 ) ∈ N 4 , k 1 = k 2 , l 1 = l 2 , that satisfy the equation:

d k 1 + e l 1 = d k 2 + e l 2 .
Obviously, we have the following consequence concerning the sequence a = (a n ) n≥0 :

Corollary 5.1. There exists a positive integer N such that, for every n ≥ N we have a n ∈ {0, 1}. Moreover, a n = 1 if and only if there exists one unique pair (k, l) ∈ N 2 such that n = d k + e l .

We prove now the Theorem 5.1. For the sake of simplicity, we consider d = 2 and e = 3, but the proof is exactly the same in the general case.

Proof. Let b := (b n ) n≥2 and c := (c n ) n≥2 be the sequences defined as follows:

b n = 1 if there exists a pair (k, l) ∈ N 2 such that n = 2 k + 3 l , 2 k > 3 l ; 0 otherwise, c n = 1 if there exists a pair (k, l) ∈ N 2 such that n = 2 k + 3 l , 2 k < 3 l ; 0 otherwise.
Let us denote by h 1 (T ) := n≥2 b n T -n and resp. h 2 (T ) := n≥2 c n T -n the series associated to b and c. Using Corollary 5.1, there exists a polynomial P ∈ F q [T ], with degree less than N , such that h can be written as follows:

h(T ) = h 1 (T ) + h 2 (T ) + P (T ).

By Remark 4.2, there is C ∈ R such that, for any m ∈ N:

p(h, m) ≤ p(h 1 + h 2 , m) + C.
In the sequel, we will show that p(h 1 , m) = p(h 2 , m) = O(m 2 ). Theorem 5.1 will then follow by Proposition 4.1.

We study now the subword complexity of the sequence of coefficients b := (b n ) n≥2 . The proof is similar to the proofs of Theorems 1.2 and 1.3. The complexity of the sequence c can be treated in essentially the same way as for b.

Step 1. For all n ≥ 1, we denote by W n the factor of b that occurs between positions 2 n + 1 and 2 n+1 , that is:

W n := b 2 n +3 0 b 2 n +2 b 2 n +3 1 • • • b 2 n+1 .
We also set W 0 := 1.

Observe that

|W n | = 2 n .
With these notations the infinite word b can be factorized as:

(15) b = 1 W 0 10 W 1 1010 W 2 10100000 W 3 • • • = W 0 W 1 W 2 • • • .
Step 2. Let n ≥ 1 and m n be the greatest integer such that 2 n + 3 mn ≤ 2 n+1 . This is equivalently to say that m n is such that

2 n + 3 mn < 2 n+1 < 2 n + 3 mn+1 .
Notice also that m n = n⌊log 3 2⌋.

With these notations we have (for n ≥ 5):

W n = 1010 5 1 • • • 10 α i • • • 10 αm n 10 βn ,
where

α i = 2 • 3 i-1 -1, for 1 ≤ i ≤ m n , and β n = 2 n -3 mn ≥ 0.
Let us denote by U n the prefix of W n such that W n := U n 0 βn . Notice that (m n ) n≥0 is an increasing sequence. Hence (α mn ) n≥0 is increasing. Consequently, U n ≺ p U n+1 and more generally, U n ≺ p W i , for every i ≥ n + 1.

Step 3. Let M ∈ N. Our aim is to bound from above the number of distinct factors of length M occurring in b. In order to do this, we will show that there exists an integer N such that all these factors occur in

W 0 W 1 • • • W N
or in the set A 0 := {Z ∈ A M ; Z is of the form 0 j P or 0 i 10 j P, P ≺ p U N , i, j ≥ 0, }.

Let N = ⌈log 2 (M + 1)⌉ + 3. Doing a simple computation we obtain that α m N ≥ M . Notice also that, for any i ≥ N we have

α m i ≥ M.
This follows since (α mn ) n≥0 is an increasing sequence.

Let V be a factor of length M of b. Suppose that V does not occur in the prefix W 0 W 1 • • • W N . Then, by (15), V must occur in W N W N +1 • • • . Hence, V must appear in some W i , for i ≥ N + 1, or in i≥N i(W i , ε, W i+1 ).

Let us suppose that V occurs in i≥N i(W i , ε, W i+1 ). Since W i ends with 0 αm i 10 β i , with α m i ≥ M , and since W i+1 begins with U N and |U N | = 3 m N + 1 ≥ M , we have that

A M ∩ ( i≥N i(W i , ε, W i+1 )) ⊂ A 0 .
Hence, if V occurs in i≥N i(W i , ε, W i+1 ) then V ∈ A 0 .

Let us suppose now that V occurs in some W i , for i ≥ N +1. By definition of W i and α i , for i ≥ N + 1 and by the fact that we have:

W i = 1010 5 1 • • • 10 αm N 10 α m N +1 • • • 10 αm i 10 β i = U N 0 α m N +1 • • • 10 αm i 10 β i .
By assumption, V does not occur in W 0 W 1 • • • W N ; hence V cannot occur in U N which by definition is a prefix of W N . Consequently, V must be of the form 0 r 10 s , r, s ≥ 0. Indeed, since α m N ≥ M , all blocks of zeros that follow after U N (and before the last digit 1 in W i ) are all longer than M . But the words of form 0 r 10 s , r, s ≥ 0 belong also to A 0 .

Hence, we proved that if V does not occur in the prefix W 0 W 1 • • • W N , then V belongs to A 0 , as desired.

Step 4. In the previous step we showed that all distinct factors of length M occur in the prefix W 0 W 1 • • • W N or in the set A 0 .

Since

|W 0 W 1 • • • W N | = N i=0 2 i = 2 N +1 -1
and since N = ⌈log 2 (M + 1)⌉ + 3 we have that:

2 N +1 -1 ≤ 2 log 2 (M +1)+5 -1 = 32M + 31,
and the number of distinct factors that occur in W 0 W 1 • • • W N is less or equal to 32M + 31. Also, by an easy computation, we obtain that the cardinality of the set A 0 is

Card A 0 = M 2 2 + 3M 2 .
Finally, p(b, m) = p(h 1 , m) = O(m 2 ). In the same manner, one could prove that p(h 2 , m) = O(m 2 ). This achieves the proof of Theorem 5.1, in view of Proposition 4.1.

5.2.

A more difficult case. Set θ(T ) := 1 + 2 n≥1 T -n 2 ∈ F q ((T -1 )), q ≥ 3.

The function θ(T ) is related to the classical Jacobi theta function. The sequence of coefficients of θ(T ) corresponds to the characteristic sequence of squares and one can easily prove that: p(θ, m) = Θ(m 2 ).

In particular this implies the transcendence of θ(T ) over F q (T ), for any q ≥ 3. Notice that this implies the transcendence over Q(T ) of the same Laurent series but viewed as an element of Q((T -1 )).

Since θ(T ) ∈ P, it would be interesting to know whether or not θ 2 (T ) belongs also to P. Notice that

θ 2 (T ) = n≥1 r 2 (n)T -n
where r 2 (n) is the number of representations of n as sum of two squares of integers mod p.

In the rich bibliography concerning Jacobi theta function (see for instance [START_REF] Duverney | Sommes de deux carrï¿ 1 2 s et irrationalitï¿ 1 2 de valeurs de fonctions thï¿ 1[END_REF][START_REF] Hardy | An Introduction to the Theory of Numbers[END_REF]), there is the following well-known formula:

r 2 (n) = 4(d 1 (n) -d 3 (n)) mod p
where d i (n) denotes the number of divisors of n congruent to i modulo 4, for each i ∈ {1, 3}.

In particular, by an easy consequence of Fermat's 2-squares theorem we can deduce that r 2 (n) = 0 if n is a prime of the form 4k + 3 and r 2 (n) = 8 mod p if n is a prime of the form 4k + 1.

More generally, if

n = 2 γ p α 1 1 p α 2 2 • • • p α k k q β 1 1 q β 2 2 • • • q β l l
, where p i ≡ 1 [4] et q j ≡ 3 [4] then r 2 (n) = 0 if there exists an odd β j in the decomposition of n; 4(α 1 + 1)(α 2 + 1) • • • (α k + 1) mod p if all β j are even.

Using these properties, we may easily deduce that r 2 (n) is a multiplicative function of n. Recall that we would like to study the subword complexity of r 2 (n) n≥0 , that is the number of distinct factors of form r 2 (j)r 2 (j + 1) • • • r 2 (j + m -1), when j ∈ N. Hence, it would be useful to describe some additive properties of r 2 (n) n≥0 ; for instance, it would be interesting to find some relations between r 2 (j + N ) and r 2 (j), for some positive integers j, N . This seems to be a rather difficult question about which we are not able to say anything conclusive.

Conclusion

It would be also interesting to investigate the following general question.

Is it true that Carlitz's analogs of classical constants all have a "low" complexity (i.e., polynomial or subexponential)?

The first clue in this direction are the examples provided by Theorems 1.1, 1.2 and 1.3. Notice also that a positive answer would reinforce the differences between R and F q ((T -1 )) as hinted in our introduction. When investigating these problems, we need, in general, the Laurent series expansions of such functions. In this context, one has to mention the work of Berthï¿ 1 2 [12, 13, 14, 15], where some Laurent series expansions of Carlitz's functions are described.

When a Laurent series has a "low" complexity, the combinatorial structure of its sequence of coefficients is rich and this can be used to derive some interesting Diophantine properties. Using this principle, bounds for irrationality measures can be obtained for elements of the class of Laurent series with at most linear complexity.

Conjecture 1. 1 . 2 .

 12 Let α be one of the classical constants: π, e, log 2, ζ(3) and √ The complexity of the real number α satisfies: p(α, b, m) = b m , for every positive integer m and every base b ≥ 2.

  lim m→∞ p(α, b, m) m = +∞, for any base b ≥ 2.

  m→∞ p(ξ, b, m) -m = +∞, for any base b ≥ 2.

Example 2 . 2 .

 22 Let us consider the formal series f

4. 1 .

 1 Proof of Theorem 1.4. The proof of Theorem 1.4 is a straightforward consequence of Propositions 4.1 and 4.3 below.

  times. For every fixed m, there exist exactly x(m) different factors of a. The subwords of c will be obtained adding factors of length m of a with factors of length m of b.

Example 4. 1 .

 1 Consider the infinite word a = 000100010001110 • • • ; a = (a n ) n≥0 = σ ∞ (0) where σ(0) = 0001 and σ(1) = 11. If we look to the order of growth of 0 and 1 we have that |σ n (0)| = 3 n + 5 • 2 n-2 and |σ n (1)| = 2 n . Hence, the morphism σ is exponentially diverging (see the Section (2.3)). Consequently, by Pansiot's theorem mentioned above, p(a, m) = Θ(m log m). Consider next b = 010110101111010 • • • ; b = (b n ) n≥0 = φ ∞ (0), where φ(0) = 0101 and φ(1) = 11. It is not difficult to see that φ is polynomially diverging (see Section (2.3)) since |φ n (0)| = (n + 1)2 n and |φ(1) n | = 2 n . By Pansiot's theorem, p(b, m) = Θ(m log log m).

4. 2 . 1 .

 21 Hadamard product. Let f (T ) := n≥-n 1 a n T -n , g(T ) := n≥-n 2 b n T -n

  Hence, let us denote by g(T ) the series whose coefficients are precisely given by (b n ) n≥0 . Thus there exists a positive constant M such that: p(g, m) ≤ M. By Proposition 4.5, p(f (k) , m) ≤ p(g, m)p(f, m) ≤ M p(f, m), which completes the proof.

Acknowledgements

I would like to express my gratitude to my advisor Boris Adamczewski for his very valuable comments, suggestions and corrections during the preparation of this article. I also thank Jean-Paul Allouche for sending me his unpublished note concerning the problem studied in Section 3, and Julien Cassaigne for suggesting the idea used in Remark 4.3.

[1] B. Adamczewski, On the expansion of some exponential periods in an integer base, to appear in Math. Ann. [