Katja Klumpp
email: katja.klumpp@inrae.fr

Carbon, Nitrogen and Phosphorus Cycling in Cropland and Grassland Ecosystems

Croplands and grasslands have a multifunctional role in biomass production for livestock and human needs. However, some of those systems are either constrained by the availability of resources such as nutrients and water, or being characterized by nutrient losses, or inefficiencies in internal nutrient cycling and poor synchronization of nutrient availability with plant demand and nutrient supply. With the increase in global demand for agricultural and food products, the development of new sustainable agricultural strategies reducing negative environmental impacts has become most important. However, given the geographic spread of grasslands and croplands, accompanied by differences in crops, cropping systems and agricultural practices imply the definition of site (region)-specific approaches.

.

.

The special issue provides an overview of C-N-P cycling for an array cropland and grassland ecosystems in relation management practices worldwide. It includes 11 original research articles that provide insights of possible solutions and proxies when hoping to improve C-N-P cycling through sustainable management. These papers are broadly focused on farming system design, crop rotation, N management, residue management, and grassland management.

N cycle and Fertilization. Fertilizer supply in excess of plant demand increases greenhouse gas emission (i.e., nitrous oxide (N 2 O) and nitrogen leaching from the root

zone. Nitrification inhibitors have been widely used to reduce N loss and to improve N-use efficiency in a wide variety of soil that varies from fertilized arable to pasture soils. Although previously assessed [START_REF] Rose | A re-evaluation of the agronomic effectiveness of the ni-trification inhibitors DCD and DMPP and the urease inhibitor NBPT[END_REF][START_REF] Singh | Decomposition of dicyandiamide (DCD) in three contrasting soils and its effect on nitrous oxide emission, soil respiratory activity, and microbial biomass-An incuba-tion study[END_REF], the interaction between the inhibitory effect under different soil properties and soil nitrification potential remain poorly understood. The paper by Mukhtar and Lin [START_REF] Mukhtar | Soil Nitrification Potential Influences the Performance of Nitrification Inhibitors DCD and DMPP in Cropped and Non-Cropped Soils[END_REF] evaluates the effect of soil nitrification potential (NP) on the efficiency of nitrification inhibitors (NI, dicyandiamide (DCD) and 3,4-dimethypyrazole phosphate (DMPP) application rates for different temperature ranges among land-use type. Among land-use types, authors tested eight cropped and non cropped soils of different climate regions of Taiwan. Temperature did not appear to have effect on inhibition effect of NI products, suggesting a wider range of application possibilities. The inhibitory effect for both chemical products, however, decreased with soil nitrification potential, implying lower application rates for soils with low NP rates.

In addition, biological nitrification inhibition (BNI) has been attracting attention as a technology for effective N utilization in cropping systems and pasture [START_REF] Coskun | Nitrogen transformations in modern agriculture and the role of biological nitrification inhibition[END_REF]. Brachiaria cultivars have been reported to suppress nitrifier populations by releasing nitrification inhibitors from roots through exudation [START_REF] Byrnes | Biological nitrification inhibition by Brachiaria grasses mitigates soil nitrous oxide emissions from bovine urine patches[END_REF]. The article by Nakamura et al. [START_REF] Nakamura | The Contribution of Root Turnover on Biological Nitrification Inhibition and Its Impact on the Ammonia-Oxidizing Archaea under Brachiaria Cultivations[END_REF] evaluated the biological nitrification inhibition of root exudates for different Brachiaria cultivars with respect to root biomass production and root turnover of cultivars. Here, authors monitored root growth in relation to changes in ammonia-oxidizing bacteria (AOB) and ammoniaoxidizing archaea (AOA) numbers, subsequent nitrification rate, and available nitrogen (N) content under seven germplasm lines of Brachiaria. Biological inhibitory effect on nitrification was mostly evident in AOA, and not in AOB for three Brachiaria cultivations.

Cropping Techniques to Improve Nutrient Cycles. Biomass mass production can be also limited by phosphorus and nitrogen, in particular under acidic and nutrient-poor soil conditions. Various mechanisms exist to mitigate P deficiency and/or stress [START_REF] Bulmer | Extent and Mechanism of Interaction between Phosphate and Citrate in a Calcareous Soil[END_REF]. Several studies have reported the beneficial effect of cereal-legume intercropping for P and N acquisition [START_REF] Brooker | Improving intercropping: A synthesis of research in agronomy, plant physiology and ecology[END_REF]. Among legume crops, Vigna unguiculata L. Walp (Cowpea) was suggested to combine both provision of proteins for alimentations and improvement of P status via its significant acid and alkaline phosphatase activity when used as intercrop [START_REF] Fraser | Quantification of bacterial non-specific acid (phoC) and alkaline (phoD) phosphatase genes in bulk and rhizosphere soil from organically managed soy-bean fields[END_REF]. In order to analyze the compromise between intercropping and inorganic fertilization, Mndzebele et al. [START_REF] Mndzebele | Effects of Cowpea-Amaranth Intercropping and Fertiliser Application on Soil Phosphatase Activities, Available Soil Phosphorus, and Crop Growth Response[END_REF] evaluated the benefits of acid and alkaline phosphatase activity of cowpea intercropping in Amaranthus cruentus under varying levels of NPK fertilization. Treatments included non-N-fertilized control, and N applied with 25%, 50%, and 100% of the recommended NPK levels. The cowpea and amaranth plants grown without fertilizer or 25% NPK had the highest rhizospheric phosphatase activity, while 100% NPK application exhibited the least. Plant tissue phosphorus concentration in plant biomass increased proportionately to the increased fertilizer application of up to 50% of the recommended NPK level. The higher phosphatase activity from the low fertilizer application treatments indicated the beneficial effect of cowpea intercropping and low fertilization.

In addition, intercropping with chickpea (Cicer arietinum L.) might ease the P or N deficiency in alkaline soil. The paper by Latati et al. [START_REF] Latati | Species Interactions Improve Above-Ground Biomass and Land Use Efficiency in Intercropped Wheat and Chickpea under Low Soil Inputs[END_REF] assessed the performance chickpea intercrop with durum wheat on soil properties and biomass production improvements for alkaline soils (pH varying from 7.5 to 8.5) in northern Algeria. Both the aboveground biomass and grain yield and, consequently, the amount of N taken up by intercropped durum wheat increased significantly (44%, 48%, and 30%, respectively) compared with sole cropping. Moreover, intercropped chickpea considerably increased N (49%) and P (75%) availability in durum wheat rhizosphere, grain yield, and resource N-and P-use efficiency, underlining the beneficial effect of chickpea intercropping.

Besides nutrient improvements, intercropping may be used as agricultural practice to improve the soil organic matter in nutrient imbalanced degraded long-term monocultures. Depending on main crop, many kinds of intercrops can be applied, improving one or several aspects of soil properties. Accordingly, combined methods might sometimes be useful to restore soil fertility. To restore soil properties and N-P-K cycling of a degraded coffee tree plantation, the article by Pham et al. [START_REF] Pham | Proposed Techniques to Supplement the Loss in Nutrient Cycling for Replanted Coffee Plantations in Vietnam[END_REF] analyses a series of "rejuvenation strate-gies" for coffee. Among combined treatments seeking to increase survival rate of seedlings on replanted land, authors assessed biochemical (NPK fertilizer) and organic treatments (i.e., liming) combined in short-term crop intercropping (Mexican marigold, Tagetes erecta) and microbial organic fertilizer (manure), and green manure applications. Among treatments, the burying of green manure and intercropping combined with microbial fertilizer performed the best on the fertilities of replanted coffee soil. In addition, tillage practices and liming had an effect, underlining the need to carefully study combined methods when liking to restore soil fertility.

Land-Use Strategies. In recent decades, research on land-use strategies related to C sequestration and greenhouse gases emissions has gained importance [START_REF] Lal | Soil carbon sequestration to mitigate climate change[END_REF][START_REF] Lal | Saving global land resources by enhancing eco-efficiency of agroecosystems[END_REF], with the emphasis on combining food and fiber production. In particular, the growth of multistemmed woody material, such short-rotation coppice (SRC, with poplar, Populus L. spp.), has become an issue in Northern and Central Italy due to increasing limitations in terms of rapid decline of biomass production over years, a high water demand, and high destruction costs. A shift from an SRC stand to other land uses into a silvo-arable alley-cropping system (ACS) has gain interest in Central Europe [START_REF] Quinkenstein | Ecological benefits of the alley cropping agroforestry system in sensitive regions of Europe[END_REF]. The article of Pecchioni et al. [START_REF] Pecchioni | Carbon Budget of an Agroforestry System after Being Converted from a Poplar Short Rotation Coppice[END_REF] assessed the C storage potential of alley-cropping systems (poplar and sorghum, Sorghum bicolor L. Moench) compared to the classical short-rotation coppice cultivation system for Central Italy. In the first year of the transition, converting the SRC into an ACS, a greater C storage was observed in pure tree belowground biomass compared to the silvoarable. The incorporation of residues and tillage disturbance in the alley has led to high respiratory losses during transition phases. However, additional years of measurement are necessary to determine turnover and extent of C losses.

In some areas, traditional land-use changes do comprise management practices, such as biomass burning, residue removal, conventional tillage, clean cultivation, monoculture, and intensive grazing; some of them leading to soil degradation [START_REF] Powers | Diversity and structure of regenerating tropical dry forests in Costa Rica: Geographic patterns and environmental drivers[END_REF]. This process might be more intense in areas of poor temporal and spatial distribution of rainfall, such as in seasonally dry tropical forests (i.e., found in five continents, South America, northern Paraguay, part of Argentina, southwest of Bolivia, and Northeast Brazil). Questions on sustainable land-use strategies to supply both fiber and protein production and soil health and fertility (i.e., soil carbon and nitrogen) has gained interest in recent years. The article by Andrade et al. [START_REF] Andrade | Land-Use Effect on Soil Carbon and Nitrogen Stock in a Seasonally Dry Tropical Forest[END_REF] evaluates effects of four main land uses on soil C/N stocks in a semi-arid region of Brazil. Among analyzed land uses, authors visited dense and open caatinga (i.e., area protected from cattle grazing and under forest regeneration), long-term pastures, and arable land cultivated with rain-fed maize (Zea mays. L.) or bean (Phaseolus vulgaris). The study underlines that, though most of the land uses were established for more than 10 years, land-use effects on total organic carbon and nitrogen content were mostly observed in the top soil layer (0-10 cm) rather than the deeper soil layers. Those results foster the possibilities to produce biomass and proteins in dry tropical forests on Neosols with very low total organic carbon stock when applying different land uses. Nonetheless, additional studies are recommended to quantify the carrying capacity of livestock when maintaining a thinned forest.

Integrated Livestock-Cropping Systems. Sustainable intensification though the inclusion on livestock in conventional arable systems have shown several medium-and long-term advantages [START_REF] Carvalho | Managing grazing animals to achieve nutrient cycling and soil improvement in no-till integrated systems[END_REF][START_REF] Burke | Spatial Variability of Soil Properties in the Shortgrass Steppe: The Relative Importance of Topography, Grazing, Microsite, and Plant Species in Controlling Spatial Patterns[END_REF]. Numerous studies underline the improvements of soil fertility and nutrient cycling related to integrated crop-livestock systems (ICLS). Further integration of trees may also deliver diversification of the producer's income sources, consideration for animal welfare, and rational water use. The paper by Carpinelli et al. [START_REF] Carpinelli | Spatial and Temporal Distribution of Cattle Dung and Nutrient Cycling in Integrated Crop-Livestock Systems[END_REF] evaluated impacts of the presence of trees exerted on excreta distribution, as well as nutrient cycling for an ICLS under humid subtropical climate in Southern Brazil. Authors' objectives were to map the distribution of cattle dung in two ICLS, i.e., with and without trees, and to quantify soil nutrient cycling related to dung dry matter decomposition. The nutrient from cattle dung was less in systems with trees compared to systems without trees, partly related to lower animal stocking densities in systems with trees. Tree sys-tems seemed, however, to foster a more homogeneous spatial distribution of the dung compared to ICLS without trees, underlining the need to further progress in sustainable fertilization management.

Grassland Systems. Descriptions and quantification of the spatial heterogeneity in plant and soil properties and their role in biogeochemical cycling, nutrient losses related to grazing livestock, and management are extremely limited [START_REF] Westoby | Plant Ecological Strategies: Some Leading Dimensions of Variation Between Species[END_REF]. Hence, to define sustainable management recommendations, an improved understanding of the impacts of different management practices on the expression of spatial heterogeneity such as the occurrence and degree variability and spatial pattern of plant and soil, is required. The article of Bloor et al. [START_REF] Bloor | Spatial Heterogeneity of Vegetation Structure, Plant N Pools and Soil N Content in Relation to Grassland Management[END_REF] have carried out a spatially explicit sampling campaign and geostatistical analyses to quantify the spatial heterogeneity of the biomass and N in plants and soil for three grassland managements (mowing, cattle grazing, and sheep grazing) within a long-term grassland experiment in France. Compared to the sheep-grazed field, the cattlegrazed field had a higher degree of spatial structure and a more coarse-grained pattern of spatial heterogeneity in plant properties. Both grazing managements showed spatial asynchrony in above-and belowground responses to grazing. These findings demonstrate the importance of herbivore species identity for the spatial uncoupling of nutrient cycles at the field scale.

For grassland in mountain areas, soil functioning is particularly affected by the combination of livestock grazing and the inter-and intra-annual variability in precipitation and temperature [START_REF] Craine | Timing of climate variability and grassland productivity[END_REF]. Among soil processes there are processes of N-turnover such as nitrification and denitrification processes both being regulated by temperature and soil moisture, as well as C availability [START_REF] Niklaus | Effects of plant species diversity and composition on nitrogen cycling and the trace gas balance of soils[END_REF]. Subsequently, it is essential to assess the potential and rates of de/nitrification as having severe effects on soil activity and fertility. The article of Debouk et al. [START_REF] Debouk | Plant Functional Diversity, Climate and Grazer Type Regulate Soil Activity in Natural Grasslands[END_REF] investigated the importance of environmental factors (climatic, management, and soil) and plant functional diversity (PFT composition and interactions) on soil activity and fertility along a climatic gradient in the Northern Iberian Peninsula. Analyses comprise six extensively managed grasslands, ranging from semi-arid up to alpine grasslands with a low-intensity seasonal grazing, varying from warm continental in the low-altitude sites, to cold temperate conditions in the high-altitude sites. Among tested factors, management variables explained most of the variability (96.5%) in soil activity and fertility compared to plant function types (PFT; grasses, legumes, and non-legume forbs), which accounted for 27% of the total variability. The soil activity and fertility is, accordingly, a mixture of environmental variables (soil-climate-agricultural practices) and related PFT diversity.

The PFTs and related strategies (e.g., growth, nutrient uptake) can be associated with a set of plant functional traits such as leaf traits [START_REF] Westoby | Plant Ecological Strategies: Some Leading Dimensions of Variation Between Species[END_REF], which depend themselves on the relative abundance of the species in the assemblage (e.g., specific leaf area (SLA), leaf dry matter content (LDMC). However, relationships between community-level leaf traits and soil processes, such as soil C inputs and subsequent soil C sequestration, remain to be further explored. The article of Kohler et al. [START_REF] Kohler | Tradeoff between the Conservation of Soil C Stocks and Vegetation Productivity in Temperate Grasslands[END_REF] examined a set of seven temperate grasslands in Normandy (France), differing in age (i.e., from a 1-year temporary grassland to old permanent grasslands >30 years) and management practices for the relation between traits, annual net primary productivity, C allocation to belowground, and soil organic C. A higher biomass production occurred under low soil organic C stocks. This negative relation between production and soil organic C could be linked to plant community functioning, and particularly leaf dry matter content, but also grassland age. Hence, analyses suggest a direct effect of management and grassland age on plant community, which in turn affects plant tissue quality and subsequent soil organic C.

In conclusion, several strategies facilitate the (re-) coupling of C-N-P cycles. This special issue contains articles for an array of cropland and grassland agroecosystems and management practices worldwide. Articles embrace various objectives and methodologies, on how new sustainable agricultural strategies can contribute to reduce negative environmental impacts. Similarly, this special issue demonstrates ways to address the complexity of nutrient cycling and its current and future challenges, allowing guiding field and on-farm adoption of (best) management practices.

Acknowledgments:

We thank all authors who submitted their valuable papers to the Special Issue, entitled "Carbon, Nitrogen and Phosphorus Cycling in Cropland and Grassland Ecosystems", of Agronomy.

Funding: This research received no external funding.

Institutional Review Board Statement: Not applicable.

Informed Consent Statement: Not applicable.

Author Contributions: K.K. wrote this editorial for the introduction of the Special Issue, entitled "Carbon, Nitrogen and Phosphorus Cycling in Cropland and Grassland Ecosystems", of Agronomy, and edited the Special Issue. All authors have read and agreed to the published version of the manuscript.

Conflicts of Interest:

The author declares no conflict of interest.


Aseem Baranwal

James Currie

Lucas Mol

Pascal Ochem

Narad Rampersad

Jeffrey Shallit

Antisquares and Critical Exponents

Keywords: antisquare, critical exponent, binary complement, binary word, avoidability, repetition threshold, enumeration, minimal forbidden word

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Let x be a finite nonempty binary word. We say that x is an antisquare if there exists a word y such that x = y y, where the overline denotes a morphism that maps 0 → 1 and 1 → 0. For example, 011100 is an antisquare. The order of an antisquare y y is defined to be |y|, where |y| denotes the length of y.

Avoidance of antisquares has been studied previously in combinatorics on words. For example, [START_REF] Mousavi | Decision algorithms for Fibonacci-automatic words, I: Basic results[END_REF] proved that the infinite Fibonacci word

f = 01001010 • • • ,
the fixed point of the morphism 0 → 01, 1 → 0, has exactly four antisquare factors, namely, 01, 10, 1001, and 10100101. More generally, all the antisquares in Sturmian words have recently been characterized in [START_REF] Hieronymi | Decidability for Sturmian words[END_REF]. On the other hand, [START_REF] Ng | New results on pseudosquare avoidance[END_REF] classified those infinite binary words containing the minimum possible numbers of distinct squares and antisquares.

It is easy to see that no infinite binary word, except the trivial families given by (0 + ϵ)1 ω and (1 + ϵ)0 ω , can contain at most one distinct antisquare. (Here the notation x ω refers to the right-infinite word xxx • • • .) However, once we move to two distinct antisquares, the situation is quite different. We have the following: Proposition 1. There are exponentially many finite binary words of length n having at most two distinct antisquares, and there are uncountably many infinite binary words with the same property.

Proof: It is easy to see that every binary word in {1000, 10000} * has only the antisquares 01 and 10, which proves the first claim.

For the second, consider the uncountable set of infinite words {1000, 10000} ω . (Here, by S ω for a set S of nonempty finite words, we mean the set of all infinite words arising from concatenations of elements of S.) Furthermore, it is easy to see that if an infinite binary word, other than 001 ω and its complement, contains exactly two antisquares, then these antisquares must be 01 and 10. Call a binary word good if it contains no antisquare factors, except possibly 01 and 10. This suggests studying the following problem.

Problem 2. Find the repetition threshold for good words.

The repetition threshold for a class of (finite or infinite) words is defined as follows. First, we say that a finite word w = w[1.

.n] has period p ≥ 1 if w[i] = w[i + p] for 1 ≤ i ≤ n -p. The smallest period of a word w is called the period, and we write it as per(w). The exponent of a finite word w, written exp(w) is defined to be |w|/ per(w). We say a word (finite or infinite) is α-free if the exponents of its nonempty factors are all < α. We say a word is α + -free if the exponents of its nonempty factors are all ≤ α. The critical exponent of a finite or infinite word x is the supremum, over all nonempty finite factors w of x, of exp(w); it is written ce(x). Finally, the repetition threshold for a language L of infinite words is defined to be the infimum, over all x ∈ L, of ce(x).

The critical exponent of a word can be either rational or irrational. If it is rational, then it can either be attained by a particular finite factor, or not attained. For example, the critical exponent of both • the Thue-Morse word t = 0110100110010110100101100 • • • , fixed point of the morphism 0 → 01, 1 → 10; and

• the variant Thue-Morse word vtm = 2102012101202102012021012 • • • , fixed point of the morphism 2 → 210, 1 → 20, 0 → 1 is 2, but it is attained in the former case and not attained in the latter. If the critical exponent α is attained, we typically write it as α + .

In 1972, [START_REF] Dejean | Sur un théorème de Thue[END_REF] wrote a classic paper on combinatorics on words, where she determined the repetition threshold for the language of all infinite words over {0, 1, 2}-it is 7 4 + -and conjectured the value of the repetition threshold for the languages Σ * k for k ≥ 4, where Σ k = {0, 1, . . . , k -1}. Dejean's conjecture was only completely resolved in 2011, in [START_REF] Rao | Last cases of Dejean's conjecture[END_REF] and [START_REF] Currie | A proof of Dejean's conjecture[END_REF], independently.

The repetition threshold has been studied for many classes of words. To name a few, there are the • Sturmian words, studied in (Carpi and Luca, 2000, Prop. 15);

Antisquares and Critical Exponents

3

• palindromes, studied in Shallit (2016);

• rich words, studied in [START_REF] Currie | The repetition threshold for binary rich words[END_REF];

• balanced words, studied in [START_REF] Rampersad | Critical exponents of infinite balanced words[END_REF][START_REF] Dvořáková | On minimal critical exponent of balanced sequences[END_REF]; and

• complementary symmetric Rote words, studied in [START_REF] Dvořáková | Complementary symmetric Rote sequences: the critical exponent and the recurrence function[END_REF].

For variations on and generalizations of repetition threshold, see [START_REF] Ilie | A generalization of repetition threshold[END_REF]; Badkobeh and Crochemore (2011); [START_REF] Fiorenzi | Bounds for the generalized repetition threshold[END_REF]; [START_REF] Samsonov | On Abelian repetition threshold[END_REF]; [START_REF] Mousavi | Repetition avoidance in circular factors[END_REF]. The goal of this paper is to study the repetition threshold for two classes of infinite words:

• AO ℓ , the binary words avoiding all antisquares of order ≥ ℓ;

• AN n , the binary words with no more than n antisquares.

It turns out that there is an interesting and subtle hierarchy, depending on the values of ℓ and n.

Our work is very similar in flavor to that of [START_REF] Shallit | Simultaneous avoidance of large squares and fractional powers in infinite binary words[END_REF], which found a similar hierarchy concerning critical exponents and sizes of squares avoided. The hierarchy for antisquares, as we will see, however, is significantly more complex.

In this paper, in Sections 2 and 3, we solve Problem 2, and show that the repetition threshold for good words is 2 + α, where α = (1 + √ 5)/2 is the golden ratio. Proving that the repetition threshold for a class of infinite words equals some real number β generally consists of two parts: first, an explicit construction of a word avoiding β + powers. This is often carried out by finding an appropriate morphism h whose infinite fixed point x (or an image of x under a second morphism) has the desired property. Second, if β is rational, then one can prove there is no infinite word avoiding β-powers by a breadth-first or depth-first search of the infinite tree of all words. If β is irrational, however, one must generally be more clever.

In Section 4 we determine the repetition threshold for binary words avoiding all antisquares of order ≥ ℓ, and in Section 5 we determine the repetition threshold for binary words with no more than n antisquares. In Section 6 we completely characterize the minimal antisquares; i.e., the binary words that are antisquares but have the property that all proper factors are good. This characterization is then used in Section 7, where we determine the growth rate of the number of good words of length n. In this section we also show that the repetition threshold between polynomial and exponential growth for good words avoiding α-powers is α = 15 4 ; i.e., there are exponentially many such words avoiding 15 4 + -powers, but only polynomially many that avoid 15 4 -powers.

2 A good infinite word with critical exponent 2 + α

Consider the morphisms below:

φ: 0 → 001 g: 0 → 01 1 → 01 1 → 11.
Let us write φ ω (0) for the (unique) infinite fixed point of φ that starts with 0. We claim that the infinite word w = g(φ ω (0)) does not have antisquares other than 01 and 10, and has critical exponent 2 + α, where α = (1 + √ 5)/2. The infinite word w is Fibonacci-automatic, in the sense of [START_REF] Mousavi | Decision algorithms for Fibonacci-automatic words, I: Basic results[END_REF], so we can apply the Walnut theorem-prover [START_REF] Mousavi | Automatic theorem proving in Walnut[END_REF] to establish this claim. For more about Walnut, see [START_REF] Shallit | The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words with Walnut[END_REF].

We start with the Fibonacci automaton for φ ω (0), as displayed in Figure 1. Let us name the above automaton FF.txt, and store it in the Word Automata Library of Walnut. We can verify the correctness of this automaton as follows. First, we claim that φ ω (0) = 0f . To see this, let f denote the morphism that maps 0 → 010, 1 → 01; i.e., the morphism f is the square of the Fibonacci morphism. One can easily verify the identities φ n (0) = 0f n (0)0 -1 and φ n (01) = 0f n (10)0 -1 by simultaneous induction, whence follows the claim. We can then use Walnut to verify the correctness of the automaton FF with the command

eval verifyFF "?msd_fib FF[0]=@0 & Ai FF[i+1]=F[i]":
which returns TRUE.

Now we can use

Walnut to create a Fibonacci automaton for w.

morphism g "0->01 1->11": image GF g FF:

The resulting automaton is called GF.txt and is displayed in Figure 2.

0/0 0 1/1 1 2/0 0 3/0 1 4/1 0 5/1 1 0, 1 6/1 0 7/0 1 1 0 0 8/1 1 1 9/1 0 1 0 1 10/0 0 1 0 Fig. 2: Fibonacci automaton for w = g(φ ω (0)).
Theorem 3. The word w does not contain antisquares other than 01 and 10, and has critical exponent 2 + α.

Proof: We write a Walnut formula asserting that there exists an antisquare of order ≥ 2, as follows:

eval antisq "?msd_fib Ei,n (n>=2) & At (t<n) => GF[i+t]!=GF[i+n+t]":
This returns FALSE, so there are no antisquares of order ≥ 2.

We now compute the periods that are associated with factors that have exponent ≥ 3.

eval gfper "?msd_fib Ei (p>=1) & (Aj (j<=2 * p) => GF[i+j]=GF[i+j+p])":
The predicate above produces the automaton in Figure 3, which shows that these periods are of the form 10010 * in Fibonacci representation.

6

Aseem Baranwal et al.

Next, we compute the pairs (n, p) such that w contains a factor of length n + p with period p of the form 10010 * and n + p is the longest length of any factor with this period. reg pows msd_fib "0 * 10010 * "; def maximalreps "?msd_fib Ei (Aj (j<n

) => GF[i+j] = GF[i+j+p]) & (GF[i+n] != GF[i+n+p])": eval highestpow "?msd_fib (p>=1) & $pows(p) & $maximalreps(n,p) & (Am $maximalreps(m,p) => m <= n)":
The automaton produced by the predicate highestpow is given in Figure 4. The strings accepted by this automaton, omitting the leading [0, 0], are as follows:

0 [0,0] 1 [1,0] 2 [0,0] 3 [0,1] 4 [0,0] 5 [0,0] 6 [1,0] 7 [0,1] 8 [1,1] 9 [0,1] [0,0] 10 [0,0] 11 [1,0] [0,0] [1,0] [0,0]
•

[1, 0][0, 0][0, 1][0, 0][0, 0][0, 1] • [1, 0][0, 0][0, 1][0, 0][0, 0][1, 1][0, 0] • [1, 0][0, 0][0, 1][0, 0][1, 0][0, 1]([1, 0][0, 0]) k [0, 0][1, 0][0, 0], k ≥ 0 • [1, 0][0, 0][0, 1][0, 0][1, 0][0, 1]([1, 0][0, 0]) k [0, 0][0, 0], k ≥ 0.
These correspond, respectively, to the values

• (n, p) = (13, 6) = (2F 6 -3, 2F 4 ) • (n, p) = (23, 10) = (2F 7 -3, 2F 5 ) • (n, p) = (F 2k+10 + F 3 + 3≤i≤k+3 F 2i , F 2k+8 + F 2k+5 ) = (2F 2k+9 -3, 2F 2k+7 ) for k ≥ 0 • (n, p) = (F 2k+9 + 3≤i≤k+3 F 2i-1 , F 2k+7 + F 2k+4 ) = (2F 2k+8 -3, 2F 2k+6 ) for k ≥ 0.
where we have used the well-known Fibonacci identities

F 2 + F 4 + F 6 + • • • + F 2t = F 2t+1 -1 F 1 + F 3 + F 5 + • • • + F 2t-1 = F 2t .
Now the exponent of these finite factors is (n + p)/p, which is

2F j + 2F j-2 -3 2F j-2
for j ≥ 6. These quotients tend to 2 + α from below, and hence the critical exponent is 2 + α.

Optimality of the previous construction

In this section we show that the critical exponent of the word constructed in Section 2 is best possible; i.e., that every infinite good word has critical exponent at least 2 + α. It is somewhat easier to work with bi-infinite words, so we begin with results concerning bi-infinite words and then explain at the end of the section how to obtain the desired result for right-infinite words. If S is a set of nonempty finite words, then by ω S ω we mean the set of bi-infinite words made up of concatenations of the elements of S.

Theorem 4. Every bi-infinite binary word avoiding 4-powers and {11, 000, 10101} has the same set of factors as f .

Proof: First, we check that f avoids 4-powers and {11, 000, 10101}.

Now consider a bi-infinite binary word w avoiding 4-powers and {11, 000, 10101}. Since w avoids 11, we have w ∈ ω {01, 0} ω . Thus there exists a bi-infinite word v such that w = h(v), where h is the morphism 0 → 01, 1 → 0. Now it suffices to show that the pre-image v also avoids 4-powers and {11, 000, 10101}. Clearly, v avoids 4-powers, since otherwise w = h(v) would contain a 4-power. Now we show by contradiction that v avoids every factor in {11, 000, 10101}.

• If v contains 11, then v contains 110. So w contains h(110) = 0001-a contradiction, since w avoids 000.

• If v contains 000 then w contains h(000) = 010101-a contradiction, since w avoids 10101.

• Proof: Notice that F is closed under bitwise complement and reversal. Let w be a bi-infinite binary word avoiding 4-powers and F . Suppose that w contains 001011.

• Since 1001 ∈ F and 0110 ∈ F , the word w contains 00010111.

• Since 0000 and 1111 are 4-powers, the word w contains 1000101110.

This is a contradiction since 1000101110 ∈ F . So w avoids 001011. By considering the complement, the word w also avoids 110100. Now suppose that w contains 110111011.

• Since 0110 ∈ F , the word w contains 11101110111.

• Since 1111 is a 4-power, the word w contains 0111011101110.

• Since 0011 ∈ F and 1100 ∈ F , the word w contains 101110111011101.

This is a contradiction since 101110111011101 ∈ F . So w avoids 110111011. By considering the complement, the word w also avoids 001000100. Thus, w avoids 4-powers and 0110,1100,1001,010101,101010,001011,110100,110111011, 001000100}.

F ′ = {0011,
Notice that F ′ is closed under complement and reversal. By symmetry, we now suppose that w contains 11. Notice that 111, 11011, and 1101011 are the only possible factors of w that start with 11, end with two identical letters, and contain two identical letters only as a prefix and a suffix. In particular, the word w avoids 00. Moreover, the blocks of consecutive 1's have length 1 or 3. So w ∈ ω {01, 11} ω . Thus w = g(v) for some bi-infinite binary word v.

Since w avoids 4-powers, the word v also avoids 4-powers. Moreover,

• g(11) = 1111 is a 4-power,

• g(000) = 010101 belongs to F ,

• g(10101) = 1101110111 contains 110111011 ∈ F ′ .

So v also avoids {11, 000, 10101}. By Theorem 4, the word v has the same set of factors as f . That is, the word w has the same set of factors as g(f ).

Theorem 6. Every good bi-infinite binary word has critical exponent at least 2 + α.

Proof: Suppose that w is a good bi-infinite binary word; that is, it contain no antisquares except possibly 01 and 10. Also assume w has critical exponent smaller than 2+α. Consider the set F from Lemma 5 and notice that F \ {101110111011101, 010001000100010} contains only antisquares. So w avoids 4-powers and F \ {101110111011101, 010001000100010}. Moreover, w avoids 101110111011101 = (1011) 15/4 since 15/4 > 2 + α. By symmetry, w also avoids 010001000100010. So w avoids 4-powers and F . By Lemma 5, w has the same set of factors as either g(f ) or g(f ). So w has critical exponent 2+α.

Corollary 7. Every (right-) infinite good binary word has critical exponent at least 2 + α.

Proof: Let w be an infinite good binary word, and let RecFac(w) denote the set of its recurrent factors. That is, the set RecFac(w) consists of the factors of w that appear infinitely often in w. Then for any y ∈ RecFac(w), we see that y has arbitrarily large two-sided extensions in RecFac(w). By a 'two-sided' analogue of König's infinity lemma, there exists a bi-infinite word w ′ such that every factor of w ′ is an element of RecFac(w). By Theorem 6, the bi-infinite word w ′ has critical exponent at least 2 + α, and thus so does the infinite word w.

The class AO ℓ

Instead of avoiding all antisquares of order greater than one, we could consider avoiding arbitrarily large antisquares.

Proposition 8. Every infinite binary word avoiding 7 3 -powers contains arbitrarily large antisquares.

Proof: By a result of [START_REF] Karhumäki | Polynomial versus exponential growth in repetition-free binary words[END_REF], we know that every infinite binary word avoiding 7 3 -powers can be written in the form

x 1 µ(x 2 µ(x 3 µ(• • • )) • • • )
, where x i ∈ {ϵ, 0, 1, 00, 11} and µ is the Thue-Morse morphism, defined by µ : 0 → 01, 1 → 10. It follows that every such word must contain arbitrarily large factors of the form µ n (0). But every word µ n (0) for n ≥ 1 is an antisquare.

On the other hand, we can prove the following result on the class AO ℓ of binary words avoiding antisquares of order ≥ ℓ: Theorem 9. There exists an infinite β + -free binary word containing no antisquare of order ≥ ℓ for the following pairs (ℓ, β):

(a) (2, 2 + α) (b) (3, 8/3) (c) (5, 5/2) (d) (6, 7/3)
These are all optimal.

Proof: Item (a) was already proved in Section 2. For each of the remaining pairs (ℓ, β), we apply a morphism ξ ℓ to any ternary squarefree infinite word w and check that it has the desired properties. The morphisms are given in Table 1. The columns are ℓ, where the word contains no antisquares of order ≥ ℓ; β, where the word avoids β + powers; s, the size of the uniform morphism; and the morphism.

ℓ β s morphism name morphism 3 8/3 36 ξ 3 0 → 001001010011001010010011001001010011 1 → 001001010010011001010011001010010011 2 → 001001010010011001001010011001010011 5 5/2 19 ξ 5 0 → 0010110100101101011 1 → 0010110100101100101 2 → 0010110011001010011 6 7/3 37 ξ 6 0 → 0010011010010110100110110011010011011 1 → 0010011010010110100110110010011010011 2 → 0010011010010110100110110010011001011
Tab. 1: Morphisms generating words in AO ℓ .

To verify the β + -freeness of ξ ℓ (w) we use (Mol et al., 2020, Lemma 23). In order to do so, we check that ξ ℓ is synchronizing and that ξ ℓ (u) is β + -free for every squarefree ternary word u of length t, where t is specified by (Mol et al., 2020, Lemma 23). In order to show that ξ ℓ (w) contains no antisquares of order ≥ ℓ, we find a length m such that if v and its complement are both factors of ξ ℓ (w), then |v| ≤ m. We can then check that ξ ℓ (w) contains no antisquares of order ≥ ℓ by exhaustively checking all factors of length at most 2m. The parameters t and m for each ξ ℓ are given in Table 2 The optimality of item (a) was already proved in Section 3. The optimality of the remaining items can be established by depth-first search. For each pair (ℓ, β), a longest word containing no antisquares of order ≥ ℓ, but avoiding β-powers (instead of β + ), is given in Table 3. The columns give ℓ, β, the length L of a longest such word, and a longest such word.

The class AN n

In this section, we consider the class AN n of binary words containing no more than n distinct antisquares as factors.

Theorem 10. There exists an infinite β + -free binary word containing no more than n antisquares for the following pairs (n, β):

(a) (2, 2 + α) (b) (3, 3) (c) (6, 8/3) (d) (9, 38/15) (e) (10, 5/2) (f) (15, 17/7) (g) (16, 7/3).
These are all optimal.

Proof: Item (a) was already proved in Section 2. For the remaining cases, the proof is similar to that of Theorem 9: for each pair (n, β), we apply a morphism ζ n to any ternary squarefree infinite word w and check that it has the desired properties. The morphisms are given in Table 4. The columns are n, the largest number of allowed antisquares; β, where the word avoids β + powers; s, the size of the uniform morphism; and the morphism. Tab. 4: Morphisms generating words in ANn.

To verify the β + -freeness of ζ n (w) we use (Mol et al., 2020, Lemma 23). In order to do so, we check that ζ n is synchronizing and that ζ n (u) is β + -free for every squarefree ternary word u of length t, where t is specified by (Mol et al., 2020, Lemma 23) The optimality of item (a) was already proved in Section 3. The optimality of the remaining items can be established by depth-first search. For each pair (n, β), a longest word containing at most n antisquares, but avoiding β-powers (instead of β + ), is given in Table 6. The columns give n, β, the length L of a longest such word, and a longest such word.

Minimal antisquares

Consider the language L of all finite good words. In this section we determine the minimal antisquares or minimal forbidden factors for L [START_REF] Mignosi | Words and forbidden factors[END_REF]. These are the words w such that w is an antisquare, but w properly contains no antisquare factors, except possibly 01 and 10. This characterization will be useful for enumerating the number of length-n words in L.

The goal is to prove the following theorem:

Theorem 11. The minimal antisquares are, organized by order n, as follows:

• n = 1: {01, 10}

• n = 2: {0011, 0110, 1001, 1100}

• n = 3: {010101, 101010}

• n = 4: ∅

• n ≥ 5: all the 2n conjugates (cyclic shifts) of 0 n-2 101 n-2 01.

We start with some basic results about antisquares.

Lemma 12. If x is an antisquare, so is every conjugate of x.

Proof: Write x as ayay for some (possibly empty) word y. Then a cyclic shift by one symbol gives yaya, which is clearly an antisquare. Repeating this argument |x| times gives the result.

Lemma 13. A word w is a minimal antisquare if and only if all conjugates of w are minimal antisquares.

Proof: Let w = uu. Let us prove the forward direction first. Assume, contrary to what we want to prove, that w is a minimal antisquare, but some rotation of w contains a shorter antisquare, other than 01 and 10.

Let rs be an antisquare of minimum length with |rs| > 2 that is not a factor of w, but is a factor of some rotation of w. Then we can write w = sxr with r, s, x ̸ = ϵ. There are three cases to consider:

|r| ≥ |u|: Let t be defined by r = tu. Then w = uu = sxtsxt, where rs = tsxts is an antisquare. If t = ϵ, then rs = sxs; hence w = sxsx contains the antisquare sxs. This is a contradiction, since we assumed w does not have a shorter antisquare, but sxs is an antisquare in w with s, x ̸ = ϵ. Therefore t ̸ = ϵ.

Since w and rs are both antisquares, they have even length. Therefore |x| is even. Consider the factorization x = x 1 x 2 with |x 1 | = |x 2 |. Then rs = tsxts = tsx 1 x 2 ts is an antisquare, where |tsx 1 | = |x 2 ts|. Therefore, tsx 1 must end with ts and x 2 ts must begin with ts, giving the antisquare tsts, which is not 01 or 10 (since t, s ̸ = ϵ), and is shorter than rs. This contradicts our assumption that rs is the smallest such antisquare.

|s| ≥ |u|: Let s be defined by s = ut. Then w = uu = txrtxr. Now rs = rtxrt is an antisquare, and hence the complement rs = rtxrt is also an antisquare. Let r ′ = rtxr and s ′ = t. So we can write w = txrtxr = s ′ xr ′ where r ′ s ′ is an antisquare of the same length as rs, and |r ′ | > |u|. This reduces the problem to the previous case. and the remaining cases correspond to certain conjugates of 0 n 101 n 01 for n ≥ 3, already listed in the statement of the theorem.

Seven runs: then x = 0 i 1 j 0 k 1 i+l 0 j 1 k 0 l . Again, if i, j ≥ 2, or j, k ≥ 2, or k, l ≥ 2, then x contains a shorter antisquare 0011 or 1100. Since i + l ≥ 2, the same argument rules out k ≥ 2 and j ≥ 2. So the only cases remaining are 1,1,1,1),(1,1,1,n),(n,1,1,1),(n,1,1,n)} for n ≥ 2. The first case (1, 1, 1, 1) corresponds to 010110101, which has the antisquare 0110, and it is easy to verify that the remaining cases are certain conjugates of 0 n+1 101 n+1 01 for n ≥ 3, already listed in the statement of the theorem.

(i, j, k, l) ∈ {(
It now remains to handle the case of more than 7 runs. By Lemma 14 x has at least 10 runs. This involves a rather tedious examination of cases, based on the following three simple observations: Proof: If condition (a) is not satisfied, then z consists of isolated occurrences of numbers ≥ 2, separated by blocks of consecutive 1's. We assume this in what follows.

If z both begins and ends with a number ≥ 2, then zz satisfies (a). Thus we may assume that z either begins or ends with 1 (or both).

Suppose z contains the block 1111. Then zz contains the block b1111c for b, c ≥ 1, and hence satisfies (b). Thus we may assume that the maximal 1-blocks in z are of length 1, 2, or 3.

Suppose all the maximal 1-blocks of z are of length 1 or 3. If z begins with 1 and ends with b ≥ 2, then z cannot be of odd length, and similarly if z ends with 1 and begins with b ≥ 2. So z must begin and end with 1.

Fig. 1 :

 1 Fig. 1: Fibonacci automaton for φ ω (0).

Fig. 3 :

 3 Fig. 3: Automaton for periods associated with 3 + -powers in w.

Fig. 4 :

 4 Fig. 4: Automaton for pairs (n, p) associated with highest powers in w.

  If v contains 10101 then v contains 0101010, since v avoids 11. So w contains h(0101010) = 01001001001. Since w avoids 11, we see that w contains 010010010010 = (010) 4 -a contradiction, since w avoids 4-powers. Lemma 5. Every bi-infinite binary word avoiding 4-powers and F = {0011, 0110, 1100, 1001, 010101, 101010, 1000101110, 0111010001, 101110111011101, 010001000100010} has the same set of factors as g(f ) or g(f ).

  Longest words avoiding β-powers and containing no antisquares of order ≥ ℓ.

  n

  (a) if r(x) contains two consecutive terms, both ≥ 2, then x contains the shorter antisquare 0011 or 1100; (b) if r(x) contains six consecutive terms a1bc1d with a ≥ c and b ≤ d, then x contains the shorter antisquare 0 c 10 b 1 c 01 b or its complement. (c) if r(x) contains an interior occurrence of 2, then x contains the antisquare 0110 or 1001. Suppose x = uu. If z = r(u) is of odd length, then zz = r(x). If z = r(u) is of even length, then writing z = ayb with a, b single numbers, we have r(x) = ay(a + b)yb. When we speak of a maximal 1-block in what follows, we mean one that cannot be extended by additional 1's to the left or right. It now suffices to prove the following two lemmas: Lemma 16. Let z ∈ N * , and suppose |z| ≥ 5 is odd. Then zz contains either (a) two consecutive terms that are ≥ 2, or (b) six consecutive terms a1bc1d with a ≥ c and b ≤ d.

  Since |z| ≥ 5, we know z has a prefix of the form 1c1d and a suffix of the form a1b1, where a, b, c, d ≥ 1. Hence zz contains the block a1b11c1d. If b ≤ c, then the block a1b11c fulfills condition (b); if b ≥ c, then the block b11c1d fulfills condition (b). Thus there must be a maximal 1-block of length 2 in z. Then zz contains two blocks, one of the form a1b11c and one of the form b11c1d, where a, d ≥ 1 and b, c ≥ 2. If b ≤ c, then the block a1b11c fulfills condition (b); if b ≥ c, then the block b11c1d fulfills condition (b).

  . Parameters for checking correctness of ξ ℓ .

	morphism ℓ	β	t	m
	ξ 3 ξ 5 ξ 6	3 8/3 8 5 5/2 10 16 6 6 7/3 14 26
	Tab. 2:

  . In order to show that ζ n (w) contains at most n distinct antisquares, we find a length m such that if v and its complement are both factors of ζ n (w), then |v| ≤ m. We can then enumerate the antisquares appearing in ζ n (w) and check that there are at most n of them. The parameters t and ℓ for each ζ n are given in Table5.

	morphism n	β	t	m
	ζ 3 ζ 6 ζ 9 ζ 10 ζ 15 ζ 16	3 6 9 38/15 9 17 3 6 4 8/3 8 6 10 5/2 10 17 15 17/7 11 12 16 7/3 14 13
	Tab. 5: Parameters for checking correctness of ζn.

  Longest words with at most n antisquares and avoiding β-powers.

		β	L	example
	5	3	17	00101001010010011
	8	8/3	52	0010010100110010100110011010011001101011001101011011
	9 38/15 407 00100101001101001010011010011001101001010011001010011 00110100101001101001100110101100110100101001101001100 11010010100110010100110011010010100110100110011010110 01101001010011010011001101001010011010011001101011001 10100101001101001100110100101001100101001100110100101 00110100110011010110011010010100110100110011010010100 11001010011001101001010011010011001101001010011001010 011001101001010011001101001101011011
	14	5/2	92	001101001011001101100110100101100110110011010011 01100110100101100110110011010011011001101100
	15 17/7 156 0010110011010010110010011010011001001101001011001001 1001011001001101001011001001101001100100110100101100 1001100101100100110100101100100110010110010011001001
	16	7/3	38	00101100101101001011001101001011001011
		Tab. 6:

* The research of JC is supported by NSERC Grant 2017-03901. † The research of NR is supported by NSERC Grant 2019-04111. ‡ The research of JS is supported by NSERC Grant 2018-04118.

Aseem Baranwal et al. |s| < |u|, |r| < |u|: In this case we can write u = sy and u = zr where y, z ̸ = ϵ. This means that u ends in r and u begins with s, implying that w contains the antisquare rs. This contradicts the assumption that w does not contain a shorter antisquare.

The reverse direction is easy. If w contains a shorter antisquare, other than 01 and 10, then at least one rotation of w also has the same antisquare.

We introduce some terminology. A run in a word is a maximal block of consecutive identical symbols. The run-length encoding r : Σ * → N * , where N = {1, 2, 3, . . .} is a map sending a word x to the list of the lengths of the consecutive runs in x. For example, r(access) = 1212.

Lemma 14. If a nonempty word x is an antisquare, then the number of runs it contains must be congruent to 2 or 3 (mod 4).

Proof: Write x = uu and consider the runs in u. If u has 2k + 1 runs, then so does u. Furthermore, u ends in a different letter than the start of u. Hence x has 4k 2 runs.

Otherwise u has 2k runs. Then the last letter of u is the same as the first letter of u. Hence x has 4k -1 runs.

Lemma 15. The word 0 k 10 1 k 01 is a minimal antisquare for k ≥ 3.

Proof: It is easy to see that x = 0 k 10 1 k 01 is an antisquare. Suppose k ≥ 3 and suppose x has an antisquare proper factor w other than 01 and 10. Now x has six runs, so by Lemma 14 we know that w has either two, three, or six runs.

If w has two runs, it must be of the form a i a i for i ≥ 2, but inspection shows that x has no factor of that form.

If w has three runs, it must be of the form a i a i+j a j for some i, j ≥ 1. The only possibility is i = 1, i + j = k, j = 1, which forces k = 2, a contradiction.

Finally, if w has six runs, then w = 0 ℓ 101 ℓ 01 for some ℓ < k, which would not be a factor of x.

We are now ready to complete the proof of Theorem 11. We say x has an interior occurrence of y if we can write x = wyz for nonempty words w, z.

Proof Proof of Theorem 11.: By combining Lemmas 12, 13, and 15, and verifying the listed cases for n ≤ 4, we see that all the words given in the statement of the theorem are minimal antisquares.

It now remains to see that there are no other minimal antisquares. The idea is to classify antisquares x by the number of runs. In what follows, we assume, without loss of generality, that x begins with 0.

Two runs: then x = 0 i 1 i for some i ≥ 1. If i ≥ 3 then x contains the antisquare 0011. So the only minimal antisquares are 01 and 0011.

Three runs: then x = 0 i 1 i+j 0 j . If either i or j is at least 2, then x contains the antisquare 0011 or 1100. So the only minimal antisquare is 0110.

Six runs: then x = 0 i 1 j 0 k 1 i 0 j 1 k . If i, j ≥ 2 then x contains the antisquare 0011, and similarly if j, k ≥ 2 and k, i ≥ 2. It follows that (i, j, k) ∈ {(1, 1, 1), (1, 1, n), (1, n, 1), (n, 1, 1)} for n ≥ 2. The cases (1, 1, 2), (1, 2, 1), (2, 1, 1) are ruled out by an antisquare of the form 1001 or 0110. So (i, j, k) ∈ {(1, 1, 1), (1, 1, n), (1, n, 1), (n, 1, 1)} for n ≥ 3. The case (1, 1, 1) corresponds to the word 010101, Aseem Baranwal et al. Proof: If condition (a) is not satisfied, then z consists of isolated occurrences of numbers ≥ 2, separated by blocks of consecutive 1's. We assume this in what follows.

If z begins and ends with 1, then z ′ has an interior occurrence of 2, so (c) is satisfied. So assume this is not the case.

If z begins 1b with b ≥ 2, then by the previous paragraph it must end in c ≥ 2. Then z ′ has an occurrence of (c + 1)b, so (a) is satisfied. Exactly the same argument works if z ends with b1 with b ≥ 2. So assume neither of these hold.

If z has an interior occurrence of 11111, then z ′ has an occurrence of c11111, fulfilling condition (b). If z begins 11111c for c ≥ 1, it must end with d ≥ 2, so z ′ has an occurrence of (d + 1)1111c, fulfilling (b). The analogous argument holds if z ends c11111. So all maximal 1-blocks in z are of length ≤ 4.

Now we consider the case that z has a maximal block of the form 1111. If this occurrence is interior in z, then z ′ contains the block b1111c for b, c ≥ 1, and hence satisfies (b). If z has the prefix 1111, then z cannot end in 1 by above. Hence, since z has even length, it must contain another maximal 1-block of even length, which must be interior. Since we have already ruled out the possibility of an interior occurrence of 1111, it must be an interior 1-block of size 2. But then z ′ has a block of the form a1b11c1d where a, d ≥ 1 and b, c ≥ 2. As in the previous lemma, if b ≤ c, then the block a1b11c fulfills condition (b); if b ≥ c, then the block b11c1d fulfills condition (b). The analogous argument holds if the occurrence of 1111 is a suffix. Hence z contains no maximal 1-block of size 4.

Thus we may assume that the maximal 1-blocks in z are of length 1, 2, or 3.

If z has a maximal 1-block of size 2, then since |z| is even, it must have a second maximal 1-block of size 2. Then z ′ has a factor of the form a1b11c1d where a, d ≥ 1 and b, c ≥ 2, and by the argument above, this satisfies condition (b).

Hence all the maximal 1-blocks of z are of size 1 or 3. Hence all the maximal 1-blocks of z are size 1 or 3. Since z has even length, exactly one of its first and last symbols must be 1. We know from above that z cannot begin 1b or end b1 with b ≥ 2. Applying the two lemmas to the case where x = u u and z = r(u) completes the proof of Theorem 11.

Enumerating words with only two distinct antisquares

In this section we obtain some enumeration results for good words. Here the notation ω x refers to the left-infinite word • • • xxx.

Proposition 18. If a bi-infinite good word w contains the factor 001011, then w = ω 0101 ω .

Proof: Consider a maximal factor of w of the form 0 k 101 k , with 2 ≤ k < ∞. By maximality and by symmetry, we can assume that w contains 0 k 101 k 0. This factor is not extendable to the right:

• 0 k 101 k 00 contains the antisquare 1100 as a suffix.

• 0 k 101 k 01 is an antisquare. This is a contradiction to k < ∞, so w = ω 0101 ω .

Theorem 19. There are Θ(ψ n ) good words of length n, where ψ . = 1.465571231876768 is the supergolden ratio, root of the equation X 3 = X 2 + 1.

Proof: Let F = {0011, 1100, 0110, 1001, 010101, 101010, 001011, 110100}. By Theorem 11, F contains the minimal antisquares of order 2 and 3, and the minimal antisquares of order at least 4 contain 001011 or 110100. Thus, the binary words avoiding F are exactly the good words that avoid {001011, 110100}.

By Proposition 18, there are not enough good words containing 001011 to contribute to the growth rate of good words. This also holds for good words containing the symmetric factor 110100. Thus, good words and binary words avoiding F have the same growth rate.

To enumerate binary words avoiding F , we instead enumerate the 'Pansiot codes' of these words. If

For example, the binary word 010 is the Pansiot code for the two binary words 0011 and 1100.

The Pansiot codes of binary words avoiding F are the binary words avoiding {010, 101, 11111, 01110}. These words consist of blocks of 0's of length at least 2 and blocks of 1's of length 2 or 4. Consider the number C n of such words ending with 00. They are obtained from shorter words by adding a suffix 0, 1100, or 111100. From the relation

Next we show that the threshold exponent at which the number of good words becomes exponential is 15 4 . (For overlap-free words, the threshold is 7 3 ; see [START_REF] Karhumäki | Polynomial versus exponential growth in repetition-free binary words[END_REF].) Theorem 20. Let w be any squarefree word over the alphabet {0, 1, 2}. Apply the map h that sends

The resulting word is good, and has exponent at most 15 4 , and it is exactly 15 4 if |w| ≥ 5.

Aseem Baranwal et al.

Proof:

The goodness of h(w) can be seen by inspection. Regarding the exponent 15 4 , suppose that h(w) contains a 15 4 power zzzz ′ , where z ′ is a prefix of z. Note that in h(w) the factor 101 can only occur at the 'boundary' between h(a) and h(b), where a, b ∈ {0, 1, 2}. So we have two cases:

Case 1: z contains 101. Write z = x101y. Then h(w) contains the square 01yx101yx1, where 01yx1 = h(Z) for some factor Z of w. Then w contains the square ZZ, which is a contradiction.

Case 2: z does not contain 101. Clearly z = h(a) or z = h(a)0 for some a ∈ {0, 1, 2} is not possible, so z is contained within some h(a), where a ∈ {0, 1, 2}. The only such 15 4 -power is h(2)0 = (0100) 3 010, which establishes the claim.

Corollary 21. There are exponentially many length-n 15 4 + -free good words.

To show that there are only polynomially many length-n good words avoiding 15 4 -powers we need a version of the results in Section 3 for finite words rather than bi-infinite words. Let g and φ be defined as in Section 2 and let g ′ be the morphism that maps 0 → 01 and 1 → 00.

Lemma 22. Let w be a 4-free word of length ≥ 15 that contains no antisquares other than 01 and 10. Then w can be written as either w = w 1 g(v)w 2 or w = w 1 g ′ (v)w 2 for some v, where |w 1 |, |w 2 | ≤ 5.

Proof: By a finite search, one verifies that any w satisfying the hypotheses of the lemma has a prefix of length ≤ 9 that contains either 0001 or 0111. Suppose it contains 0111. Since w avoids the antisquares 0110 and 1001 and the 4-powers 0000 and 1111 we can write w = w 1 0111z, where z is a prefix of a word in {0001, 01, 0111} * and |w 1 | ≤ 5. We claim that z does not contain 0001. Note that |z| ≥ 6.

If z has 0001 as a prefix, then w contains the antisquare 111000. Suppose z has 01 as a prefix. If z has 010001 as a prefix, then w contains the antisquare 0111010001. If z has 01010 as a prefix, then w contains the antisquare 101010, so necessarily z has 010111 as a prefix. Finally, it may be the case that z has 0111 as a prefix. Applying this argument repeatedly to the suffix of w following this new occurrence of 0111, until we no longer have such a suffix of length at least 6, we see that z does not contain 0001. It follows that w can be written as w = w 1 xw 2 , where x ∈ {01, 0111} * (and hence x ∈ {01, 11} * ), and |w 2 | ≤ 5. Thus w = w 1 g(v)w 2 for some v, as required.

A similar argument shows that if w contains 0001 then w = w 1 g ′ (v)w 2 for some v, where |w 1 | ≤ 5 and |w 2 | ≤ 5.

In what follows we will consider words of the form g(v); the analysis for g ′ (v) is similar.

Lemma 23. Let n ≥ 1 and y = g(φ n (x)) for some binary word x with |x| ≥ 5. If y is 15 4 -free, then x is 4-free and can be written in the form x = px ′ s where |p| ≤ 2, |s| ≤ 1 and x ′ has no 000 or 11.

Proof: Clearly x is 4-free. Suppose x contains an occurrence of 000 that is neither a prefix nor a suffix of x. Then φ(x) contains the 4-power 01(001) 3 0 = (010) 4 and hence y contains a 4-power, which is a contradiction. Suppose x contains an occurrence of 11 of the form x = u11v, where |u| ≥ 2 and |v| ≥ 1. Then φ(x) contains 0101 and hence, extending this occurrence of 0101 to the left and right with blocks 001 and 01 and avoiding 4-powers, we see that φ(x) contains 00101010. Indeed, extending two blocks to the left and one block to the right suffices. If n = 1 then g(00101010) contains the 15 4 -power (1011) 3 101, which is a contradiction. If n > 1, then φ(00101010) contains the 4-power (01001) 4 and hence y contains a 4-power, which is a contradiction.

Lemma 24. Let w be a 15 4 -free word of length ≥ 33 that contains no antisquares other than 01 and 10. Then w can be written in the form Theorem 25. There are polynomially many length-n good words avoiding 15 4 -powers.

Proof: Let w be such a word of length n, where n ≥ 33. By Lemma 24 w can be written in the form E) be the maximum number of possible choices for w 1 (resp. w 2 , u i , v i , V ). Then the number of words w is at most AB(CD) r E. There is a constant ρ such that r ≤ ρ log n, so the number of words w is at most ABEn ρ log(CD) . A similar calculation applies when G = g ′ .

Further work

In this paper we have studied antisquares. This situation has an obvious generalization to patterns with morphic and antimorphic permutations, as studied in [START_REF] Currie | Unary patterns with permutations[END_REF]. This could be the subject of a future study.

A companion paper to this one is [START_REF] Currie | Complement avoidance in binary words[END_REF], which investigates complement avoidance in binary words.


Malo Gaubert

Benoit Combès

Jean-Christophe Ferré

Alice Dufey

Raphaël Chouteau

Anne Kerbrat

Elise Bannier

Virginie Callot

J.-C Ferré

Simultaneous brain and cervical spinal cord MP2RAGE for T1 measurement: robustness and sensitivity for tissue modification assessment in multiple sclerosis in a multicenter context

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Recent optimisations of T1 quantification through magnetization-prepared two rapid acquisition gradient echoes (MP2RAGE; [START_REF] Marques | MP2RAGE, a Self Bias-Field Corrected Sequence for Improved Segmentation and T1-Mapping at High Field[END_REF]) allow to perform both brain and cervical spinal cord acquisitions simultaneously with good trade-off between acquisition time, robustness and accuracy [START_REF] Rasoanandrianina | Regional T Mapping of the Whole Cervical Spinal Cord Using an Optimized MP2RAGE Sequence[END_REF][START_REF] Forodighasemabadi | An Optimized MP2RAGE Sequence for Studying Both Brain and Cervical Spinal Cord in a Single Acquisition at 3T[END_REF]. This sequence is of particular interest to investigate tissue microstructural modifications in pathologies such as multiple sclerosis (MS) [START_REF] Demortière | Improved Cervical Cord Lesion Detection with 3D-MP2RAGE Sequence in Patients with Multiple Sclerosis[END_REF][START_REF] Mchinda | 3D-MP2RAGE T1 mapping to characterize regional cervical spinal cord impairments in ALS and MS patients[END_REF]. In order to spread out the use of the MP2RAGE sequence, we evaluated the reproducibility and variability in two different centres.

Methods

The data included in this work were collected in the context of the multicentric MSTRACTS (NCT04220814), OSV-IRM (NCT05107232) and T1-M3C-SEP (FLI-RE2) studies. Six healthy controls (HC; F/M: 4/2, mean age 38.9 years) were scanned 3 times each (separated sessions), in two different centres both equipped with 3T Siemens scanners (Prisma with 20 channels in centre 1, Vida with 64 channels in centre 2 ). Additionally 26 HC (centre 1/2: 20/6) were scanned one time (F/M: 19/7, mean age 39.2 years). The same acquisition protocol was performed in both centres and included MP2RAGE and B1 map acquisitions covering both brain and cervical spinal cord (cSC). The acquisition parameters were previously described in [START_REF] Rasoanandrianina | Regional T Mapping of the Whole Cervical Spinal Cord Using an Optimized MP2RAGE Sequence[END_REF]4000ms TR, 243×300mm² FOV, 176 slabs, 6/8 partial Fourier (PF) factor 0.9×0.9×1mm 3 voxel size, TI1/TI2 = 650/2000ms, ɑ1/ɑ2=4/5°, GRAPPA 2). After B1 correction [START_REF] Massire | High-Resolution Multi-Parametric Quantitative Magnetic Resonance Imaging of the Human Cervical Spinal Cord at 7T[END_REF], mean T1 values were extracted in different regions including brain white matter (bWM), deep grey matter (dGM) and cortical grey matter (cGM; all computed using CAT12 [ [START_REF] Ashburner | Voxel-Based Morphometry--the Methods[END_REF]]) and all cSC segments (computed using the SCT toolbox [(De [START_REF] Leener | SCT: Spinal Cord Toolbox, an Open-Source Software for Processing Spinal Cord MRI Data[END_REF]). We evaluated the variability between centres and subjects using linear mixed-effects models with subject as random effect and centre as fixed effect. The coefficients of variation (CV) and the intraclass correlations (ICC) of between-session and between-participant variabilities were computed according to [START_REF] Combès | Measurement of Magnetization Transfer Ratio (MTR) from Cervical Spinal Cord: Multicenter Reproducibility and Variability[END_REF]. In order to interpret these results with respect to potential application in MS pathology, we also reported exploratory analyses based on the extraction of T1 values in the same regions for 5 MS patients (centre 1/2: 3/2, same acquisition protocol and image processing) without cSC lesions.

Results

For the whole dataset collected in HC, the mean (and standard deviation) T1 values in the brain were 1281.5 (28.8), 1176.5 (20) and 823.9 (21.1) ms for cGM,dGM, and bWM, respectively and were ranging from 921 (22.6) to 954 (30.5) ms over the 7 cSC segments (see Fig. 1) For the brain, we observed evidence of centre differences for the three regions (all p<.01). Nevertheless, the estimated differences between centres were low, ranging from 4.71 (bWM) to 25.31 (dGM) ms (ie. 0.57 to 1.98% of the mean). Between-participant CV were 2.1, 1.7 and 1.8%, and between-session CV were 0.2, 2.2 and 0.5% for bWM cGM and dGM, respectively. Between-session ICC were .01, .61 and .06 for the same regions.

For the SC, we observed evidence of centre differences for all vertebrae (all p<.05), except C4, C5 and C7 (p=.149, .163, .062, resp.). The estimated mean differences were also low, ranging from 9.6 (C5) to 20.2 (C1) ms (ie. 1.03 to 2.15%). To simplify the results, T1 values from C3 to C5 levels were averaged. In this region, between-participant and between-session CV were 1.5 and 1.6%, while between-session ICC was .53.

MS patients showed a mean T1 value increase ranging from 19.5 (cGM) to 44.2 (dGM) ms for the brain, and from 14 (C7) to 122.7 (C3) ms for the cSC compared to the mean in all HC. Fig. 2 shows that, for each region, the majority of patients (coloured triangles) have higher T1 values than the third quartile of HC.

Discussion

Our results showed that, even if differences exist between the two centres, the variability is low, especially for bWM (0.57 %) and central cSC segments (1.03 %). Moreover, the T1 variability is primarily explained by between-participant variability for the brain and by both session-and participant-variabilities for cSC. The differences between scanners were found to be less important than the differences observed between HC and MS patients with no cSC lesions. Overall, our results highlight the multicenter robustness of simultaneous brain and cervical spinal cord acquisition and its potential for further applications in multicenter MS studies to assess regional tissue impairment.

Figures

Figure 1 :

 1 Figure 1: Mean T1 values for all healthy controls grouped by centre (Centre 1 in orange, Centre 2 in blue) for the regions of interest located in the brain and the cervical spinal cord. Boxplots display the median, the first and third quartiles. Black bars display the mean of all healthy controls for each centre and each region. Legend: WM=white matter; GM=grey matter; SC=spinal cord; ms=millisecond.

Figure 2 :

 2 Figure 2: Mean T1 values for all healthy controls grouped by centre (Centre 1 in orange, Centre 2 in blue) and the 5 MS patients for the regions of interest located in the brain and the cervical spinal cord. Boxplots display the median, the first and third quartiles in the HC group.Triangles represent the mean signal for each MS patient. Dots represent outliers for healthy controls. Legend: WM=white matter; GM=grey matter; SC=spinal cord; ms=millisecond.

Acknowledgements

This work was partly funded by the France Life Imaging (FLI RE2) (ANR-11-INBS-0006 grant from the French "Investissements d'Avenir" program). The authors would like to thank L.Pini, C. Costes, V. Gimenez, MP. Ranjeva and C. Guillemot, L. Patier, G. Morrisse, V. Even, C. Picot for study logistics.