Nadia Brauner
email: nadia.brauner@grenoble-inp.fr

Yves Crama
email: yves.crama@uliege.be

Etienne Delaporte
email: etienne.delaporte@outlook.com

Vincent Jost
email: vincent.jost@grenoble-inp.fr

Luc Libralesso
email: luc.libralesso@grenoble-inp.fr

Do balanced words have a short period?

Keywords: Balanced words, congruence words, exact covering systems, constant gap sequences, Graham-Hubert theorem, Fraenkel's conjecture, m-balanced

  L'archive ouverte pluridisciplinaire

Introduction

Balanced sequences and balanced words have attracted the attention of many researchers in discrete mathematics or number theory, but also in application fields like scheduling, maintenance, queueing, or apportionment (see, e.g., [START_REF] Altman | Balanced sequences and optimal routing[END_REF][START_REF] Herrmann | Finding optimally balanced words for production planning and maintenance scheduling[END_REF][START_REF] Brauner | Small deviations, JIT sequencing and symmetric case of Fraenkel's conjecture[END_REF][START_REF] Kubiak | Fair sequences[END_REF][START_REF] Kubiak | Proportional Optimization and Fairness[END_REF]). Yet, in spite of this wealth of literature, balanced words and their properties are still poorly understood. A most striking, and best known illustration of this assertion is provided by a conjecture initially formulated by Fraenkel (as mentioned in [START_REF] Tijdeman | Exact covers of balanced sequences and Fraenkel's conjecture[END_REF]) for exact covers by Beatty sequences.

Fraenkel's conjecture was later extended to balanced words (Altman, Gaujal and Hordijk [START_REF] Altman | Balanced sequences and optimal routing[END_REF]). Although Fraenkel's conjecture has been established for words on a small number of letters (up to N = 7 letters [START_REF] Barát | Partitioning the positive integers to seven Beatty sequences[END_REF]), its general case remains stubbornly open.

Our objective in this research was to get a better grasp of the vectors of densities associated with balanced words. For this purpose, we have conducted computational experiments in which we have generated all such vectors up to a certain size. Out of the numerical results came a conjecture that we believe to be new and of potential interest to the mathematical community.

Graham [START_REF] Graham | Covering the positive integers by disjoint sets of the form {[nα + β] : n = 1, 2[END_REF] made important observations about how balanced words arise out of balanced words on 2 letters and congruence words. Our study was guided by the following question "Which balanced words remain after cleaning those explained by the construction of Graham?" This note is organized as follows: in Section 2, we review the literature required for our study. In Section 3 we explain why Fraenkel's conjecture is not sufficient, to the best of our understanding, to reduce the study of balanced words to the study of congruence words. In Section 4 we claim our main contributions: the conjecture about the short period of balanced words, as well as a simple construction for generating some balanced words by deleting a letter in a congruence word.

In Section 5 we investigate balanced words with N ≤ 6 letters, providing a complete list of these words under the validity of our main conjecture. We also exhibit that our simple construction explains many of the balanced words that do not arise from Graham's construction.

The proof of our conjecture for N = 4 letters is provided in the Appendix.

Background

We briefly introduce the definitions that are needed in the sequel. The reader is referred to [START_REF] Tijdeman | Exact covers of balanced sequences and Fraenkel's conjecture[END_REF][START_REF] Tijdeman | Periodicity and almost-periodicity[END_REF][START_REF] Sano | m-Balanced words: A generalization of balanced words[END_REF][START_REF] Vuillon | Balanced words[END_REF] for details and additional information. Each word is naturally associated with a partition of Z into a finite family of sequences {S i } i∈{1,...,N } , where S i is the set of integers that W maps to the letter i. The word is D-periodic if and only if all sequences S i are Dperiodic. Provided that all densities δ(S i ) exist, the density (vector) of W is δ(W ) = (δ(S 1 ), . . . , δ(S N )).

A D-periodic word is completely defined by its restriction to the interval {1, ..., D}. Therefore, when presenting examples, we usually describe a periodic word by a finite string X of integers or letters, such as X = 1213112231 or X = abacaabbca. The word itself is W = (X) * , where the star operator indicates infinite repetition of the string X.

Notice that with this setting, we identify (01) * and (10) * . In other words, this defines a word up to a common shift of all its sequence, which is sufficient and more convinient, for the issues addressed in this paper. Definition 2.3. A factor in a word W is a finite sequence of consecutive letters of W . Equivalently, a factor is the image by W of a finite interval of integers. Definition 2.4. A balanced sequence is a sequence S such that, for every pair I 1 and I 2 of intervals of integers of the same length, the difference between the number of elements of the sequence in the two intervals is at most 1: that is, if

I 1 = {i 1 , . . . , i 1 + t} and I 2 = {i 2 , . . . , i 2 + t}, then -1 ≤ |I 1 ∩ S| -|I 2 ∩ S| ≤ 1.
A word is balanced if all its associated sequences are balanced.

Balanced sequences and words have been extensively studied [START_REF] Altman | Balanced sequences and optimal routing[END_REF][START_REF] Tijdeman | Exact covers of balanced sequences and Fraenkel's conjecture[END_REF][START_REF] Tijdeman | Periodicity and almost-periodicity[END_REF].

A structural theorem about balanced sequences from [START_REF] Morse | Symbolic Dynamics[END_REF] implies that every balanced sequence S has a density. Moreover if the density δ(S) is irrational, then the balanced sequence S is not periodic.

We now introduce an important class of balanced words which have been named in several ways: congruence words, exact covering systems, constant gap words, exact covering congruences [START_REF] Graham | Covering the positive integers by disjoint sets of the form {[nα + β] : n = 1, 2[END_REF]. Of course this proposition can be used to characterize congruence words, by requiring the above condition for each of its letters.

Graham [START_REF] Graham | Covering the positive integers by disjoint sets of the form {[nα + β] : n = 1, 2[END_REF] observed that congruence words can be used to build balanced words from balanced words, as follows.

Definition 2.7. Let W be a word on letters {1, ..., N }, let A be a word on letters {N + 1, ..., M }, and let j ∈ {1, ..., N }. Consider the word W A,j on M -1 letters obtained by replacing in W the k-th occurrence of letter j by the k-th letter of the word A, for all k ∈ Z (we set the convention that the 0-th occurrence of letter j in W is the one with smallest non-negative position). If A is a congruence word, the word W A,j is a congruence substitution of the word W . Definition 2.8. V is a congruence expansion of W if there is a finite sequence of words W = W 1 , . . . , W k = V such that for all i in {1, . . . k -1}, the word W i+1 is a congruence substitution of W i . Proposition 2.9. [START_REF] Graham | Covering the positive integers by disjoint sets of the form {[nα + β] : n = 1, 2[END_REF] Any congruence expansion of a balanced word is also a balanced word. Extending a theorem by Graham [START_REF] Graham | Covering the positive integers by disjoint sets of the form {[nα + β] : n = 1, 2[END_REF] for irrational densities, Hubert [START_REF] Hubert | Suites équilibrées[END_REF] established an important property of non-periodic balanced words (see also Altman et al. [START_REF] Altman | Balanced sequences and optimal routing[END_REF]): Proposition 2.9 provides a construction for all non-periodic balanced words.

Theorem 2.11. [START_REF] Hubert | Suites équilibrées[END_REF] If W is a non-periodic balanced word, then W is a congruence expansion of a balanced word on two letters.

However, not all balanced words are congruence expansions of balanced words on 2 letters. The most famous among such words are the following [START_REF] Altman | Balanced sequences and optimal routing[END_REF][START_REF] Tijdeman | Exact covers of balanced sequences and Fraenkel's conjecture[END_REF]: Definition 2.12. The Fraenkel word on N letters is the periodic balanced word

F N recursively defined by F 1 = 1, F N = F N -1 N F N -1 if N ≥ 2 and F N = (F N ) * for all N .
For example F 3 = 1213121. The density vector of

F N is φ N , with φ N i = 2 N -i 2 N -1 for i = 1, . . . , N .
Conjecture 2.13 (Fraenkel's conjecture). For all N ≥ 3, if W is a balanced word on N letters such that all components of its density vector are pairwise distinct, then its density vector is φ N . Conjecture 2.13 has been proved for N ≤ 7 (see Altman et al. [START_REF] Altman | Balanced sequences and optimal routing[END_REF], Barát and Varjú [START_REF] Barát | Partitioning the positive integers to seven Beatty sequences[END_REF], Tijdeman [START_REF] Tijdeman | Fraenkel's conjecture for six sequences[END_REF]), but it remains open for larger values of N .

We end our literature review with the concept of projection of a word on a subset of its letters, since we will show later that removing a letter in a congruence word generates a balanced word.

Definition 2.14. Given a word W = {S i } i∈{1,...,N } on N letters and X ⊆ {1, ..., N }, the projection W -X of W on {1, ..., N } \ X is defined by reading W , skipping letters in X.

To refer to a position in the projected word (as it is undefined with the above definition), we will refer to the associated position in the original word.

It is known for instance that if W is balanced and letter a has density at least 1/2, then W -a is still a balanced word [START_REF] Altman | Balanced sequences and optimal routing[END_REF]. Moreover, if W is balanced and letter a has density at least 2/3, then W -a is a congruence word [START_REF] Simpson | Disjoint covering systems of rational Beatty sequences[END_REF].

The following generalization of balancedness was proposed and studied by [START_REF] Sano | m-Balanced words: A generalization of balanced words[END_REF].

Definition 2.15. For a sequence S ⊆ Z, an interval X = {a, ..., b} is a S-chain if a -1 ∈ S and b + 1 ∈ S. For a word W and a letter s, a factor X is a s-chain if X is directly preceeded and directly followed by an s.

Definition 2.16. For a non-negative integer m, a sequence S ⊆ Z is m-balanced, if for every S-chain X and every interval X such that

|X | = |X| + m + 1, we have |X ∩ S| ≥ |X ∩ S| + 1.
0-balanced sequences are exactly congruence sequences (or contain one element). 1-balanced sequences are exactly balanced sequences.

Fraenkel conjecture is not sufficient to reduce balanced words to congruence words

We should note that the converse of Proposition 2.9 is not valid in general:

if a congruence expansion of a word W is balanced, it does not mean that W itself is balanced, as in the following example. Remark 3.2. Tijdeman [START_REF] Tijdeman | Periodicity and almost-periodicity[END_REF] asks what are the balanced words on more than two letters. He goes on to observe that, for such words:

"Obviously each letter has again a density. If the densities of two letters are equal, then they can first be identified as one letter with double density, and then the latter letter can be replaced alternately by the first and second letter. It is therefore a crucial question to determine the balanced words the letters of which have distinct densities, so-called Fraenkel words."

This comment seems to suggest that, by identifying letters of equal density in a balanced word, one obtains again a balanced word. However, this is in contradiction with Example 3.1. Indeed, for this example, the density of W A,e is 6 11 , 3 11 , 1 11 , 1 11 , with the last two densities (of a and b) being equal. By identifying the letters a and b, however, one obtains the density (of W ) 6 11 , 3 11 , 2 11 , and there is no balanced word with these densities.

As we will see in Section 4, Example 3.1 does indeed arise from a congruence word by deleting one letter (of density 1/12). In Section 5 however, we exhibit balanceable density vectors for which no construction seems to be known.

Main new statements

Building upon Theorem 2.11, we concentrate in the sequel on the case of periodic words and their (necessarily rational) densities. We tried and list all balanced words on N = 4, 5 or 6 letters using a computer. To this aim, we had to restrict our attention to words with a relatively small period D. Our experiments led us to the following conjecture: Note that the set of words that satisfy condition (2) is finite for each fixed N .

In the next section, we refine Conjecture 4.1 for N ≤ 6, by listing all balanceable density vectors that do not come from congruence expansions of other balanced words. A careful study of these vectors led us to observe that several such density vectors look very much like density vectors of congruence words. Indeed, they arise just by deleting a letter of lowest density in a congruence word. These examples motivate the following observation: Theorem 4.2. If {S a } a∈{1,...,N } is a congruence word, then the projected word obtained by deleting any of its letter a ∈ {1, ..., N } is balanced.

To prove this Theorem, we first claim it in the most general form allowed by our proof. (that is W projected on R and S), the sequence S is (m + 1)-balanced.

A weaker version of Lemma 4.3 already appears in [START_REF] Sano | m-Balanced words: A generalization of balanced words[END_REF] (as Theorem 4.2: "If we remove a sequence in a m-balanced word W and if W is also billiard, then we obtain a m + 1-balanced word"; most interestingly, Lemma 4.3 claims that the billiard assumption can be relaxed).

Let us deduce Theorem 4.2 from Lemma 4.3. In a congruence word, all sequences are disjoint and 0-balanced. Hence, removing any sequence in a congruence word leaves the other sequences 1-balanced.

Proof. of Lemma 4.3. Let S be the sequence of integers corresponding to S in W -T . Assume that S is not (m + 1)-balanced in W -T . Denote by s and t the letters corresponding to sequences S and T . Since S is not (m + 1)-balanced, there exists a s-chain X in W -T and a factor X such that

| X | = | X| + m + 2 and | X ∩ S| ≤ | X ∩ S|. There exists a s-chain X ⊇ X of W -T such that | X | ≥ | X| + m + 2 and | X ∩ S| = | X ∩ S|.
X (resp. X ) is the projection of a s-chain X (resp. X ) of W . Both are uniquely defined by the fact that they are s-chain in W . We have

| X | ≥ | X| + m + 2 and | X ∩ S| = | X ∩ S| and | X| = | X ∩ S| + | X ∩ R| and | X | = | X ∩ S| + | X ∩ R|. Hence |X ∩ R| -|X ∩ R| ≥ m + 2.

Small values of N

For simplicity, we call density vector (or density, for short) any vector δ ∈ Q N such that N i=1 δ i = 1, and we assume that density vectors are defined up to a permutation of their components. Definition 5.1. A density vector δ = (δ 1 , . . . , δ N ) ∈ Q N is balanceable if there exists a balanced word W on N letters such that δ(W ) = δ. For a balanceable density δ, the period of δ, denoted D(δ), is the smallest period of a balanced word with density δ.

For a density vector with pairwise distinct components, Conjecture 2.13 implies Conjecture 4.1. If the components take at most two distinct values, the density vector is of the form (α/k 1 , ..., α/k 1 , (1 -α)/k 2 , ..., (1 -α)/k 2 ) for some α ∈ (0, 1) and two integers k 1 , k 2 . Hence the vector is balanceable and validates case (1) in Conjecture 4.1.

The case N ≤ 3

The following results are well-known and can be found for instance in Altman et al. [START_REF] Altman | Balanced sequences and optimal routing[END_REF] or Tijdeman [START_REF] Tijdeman | Fraenkel's conjecture for six sequences[END_REF].

Proposition 5.2. For N = 2 letters, the balanceable density vectors are exactly the vectors of the form: (α, 1 -α), for all 0 < α < 1.

Proposition 5.3. For N = 3 letters, the balanceable density vectors are exactly the vectors of the form: (α/2, α/2, 1-α), for all 0 < α < 1. The only balanceable vector not in this infinite list is φ 3 = (4/7, 2/7, 1/7).

These results immediately imply that Conjecture 4.1 holds when N ≤ 3.

The case N = 4

Altman et al. [START_REF] Altman | Balanced sequences and optimal routing[END_REF] establish several results on balanceable vectors of four densities, including a proof of Fraenkel's conjecture. The Appendix of [START_REF] Altman | Balanced sequences and optimal routing[END_REF] also provides a list of balanceable vectors for N = 4. This list is actually complete: Theorem 5.4. For N = 4 letters, the balanceable density vectors are exactly the vectors in the following classes:

1) All vectors of the form

( α 3 , α 3 , α 3 , 1 -α), ( α 2 , α 4 , α 4 , 1 -α), ( α 2 , α 2 , 1 -α 2 , 1 -α 2 ),
for all 0 < α < 1.

2) Five balanceable vectors which are not in the previous infinite classes, namely: All of them can be constructed from Theorem 4.2 (increasing both the number of letters and the period by 1 yields the density vector of a congruence word, e.g.

(6/12, 3/12, 1/12, 1/12, 1/12) in the first case).

The case N = 5

For N = 5, Fraenkel's conjecture has been proved by Tijdeman [START_REF] Tijdeman | Fraenkel's conjecture for six sequences[END_REF]. We have verified by computer the following conjecture for all vectors with a period D ≤ 130.

Conjecture 5.6. For N = 5, the balanceable vectors which are not density vectors of a congruence expansion of some balanced word on N ≤ 4 letters are: Those we cannot construct from Theorem 4.2 are boxed.

The case N = 6

The case N = 6 is similar to the previous ones. The following conjecture has been tested by computer for all density vectors with a period D ≤ 80.

Conjecture 5.7. For N = 6, the balanceable vectors which are not density vectors of a congruence expansion of some balanced word on N ≤ 5 letters are: Those we cannot construct from Theorem 4.2 are boxed.

Conclusion 270

Most balanced words seem to arise from balanced words on two letters by congruence expansion. Those which don't come from a word on two letters seem to have a period D satisfying D ≤ 2 N -1. Among them, several come from deleting a letter in a congruence word. However there remain balanced words on 5 and 6 letters for which no particular structure seems to be known.

275

In the last 2 decades, attention on balanced words focused on Fraenkel's conjecture, providing proofs for up to 7 letters. We argue however, that even proving this conjecture might not be sufficient to understand balanced words, and that new constructions are needed to obtain a satisfying structural description of balanced words.

A. Proof of Theorem 5.2

If a balanced word on 4 letters is not periodic, it is a congruence expansion of a word on 2 letters (see Theorem 2.11) and hence, it is of the form

α 3 , α 3 , α 3 , 1 -α , α 2 , α 4 , α 4 , 1 -α , α 2 , α 2 , 1 -α 2 , 1 -α 2 .
Notice that the density vector of a (periodic balanced) word on 4 letters with

exactly 2 distinct values is of the form α 2 , α 2 , 1-α 2 , 1-α 2 or 1 -α, α 3 , α 3 , α 3
. If a balanced word on 4 letters has a density vector with 4 distinct values then, by [START_REF] Altman | Balanced sequences and optimal routing[END_REF], this vector is Proof. Assume that W contains a factor I with k + 1 x's and no y. Partition W into factors of size |I|. By balancedness, in each such factor, there are at least k x's and at most one y. By periodicity, a factor with k + 1 x's and no y appears sufficiently often so that δ x > k |I| and δ y < 1 |I| . Hence, δ x > kδ y . Assume that between two consecutive y, there are at most k x's. Partition W in factors starting with a y and with no other y inside. Each factor contains at most k x's. Approximating the densities (which exist either by periodicity or by balancedness) on any number of consecutive such factors, one obtains

δ x ≤ kδ y .
Lemma A.4. Let W be a periodic balanced word, and x and y be two letters of W and k be an integer. Then δ x < kδ y if and only if there exists a factor starting and ending with a y and no other y and strictly less than k x's.

Proof.

Assume there exists a factor I starting and ending with a y and no other y and strictly less than k x's. Partition W into factors of size |I|.

By balancedness, in each such factor, there are at most k x's and at least one y. By periodicity, a factor with strictly less than k x's between 2 y's appears sufficiently often so that δ x < k |I| and δ y > 1 |I| . Hence, δ x < kδ y . Assume that between two consecutive y, there are at least k x's. Partition W in factors starting with a y and with no other y inside. Each factor contains at least k x's. We thus obtain that δ x ≥ kδ y .

In particular, the case k = 1 means that there is a factor spanned by 2 y and containing no x.

Notice that Lemmas A.2 to A.4 also apply to Beatty sequences but they cannot be generalized to non balanced sequences. The following lemma is an immediate consequence of the last two lemmas.

Lemma A.5. Let W be a periodic balanced word, and x and y be two letters of W with densities δ x = δ y . Then, letters x and y alternate in W .

Let X be a factor. The notation X means that we do not make any assumption on the order of the letters of X. For instance abcb represents either abcb or acbb.

Claim 1. A periodic balanced word on 4 letters, with exactly 3 distinct densities and containing aaa as a factor, has densities of the form (1 -α, α 2 , α 4 , α 4 ).

Proof. If a periodic balanced word W on 4 letters contains the factor aaa, then by Lemma A.2, δ a ≥ 2/3. In this case, Simpson's Theorem [START_REF] Simpson | Disjoint covering systems of rational Beatty sequences[END_REF] indicates that the word W induced by removing a is a congruence word on 3 letters. The unique possible density vectors of a congruence word on 3 letters are

( 1 3 , 1 3 , 1 3 ) and ( 1 2 , 1 4 , 1 4
), see [START_REF] Altman | Balanced sequences and optimal routing[END_REF]. Therefore, W has a density vector of the form We assume in the sequel that W does not contain bab as a factor. Assume that W contains CAD. If CAD is followed by A, then W = (CADA) * with density vector ( 8 14 , 4 14 , 1 14 , 1 14 ). If CAD is followed by C then W = (DCA) * with density vector ( 611 , 3 11 , 1 11 , 1 11 ). If W contains no CAD, then it contains DAC and the same reasonning applies.

(1 -α, α 3 , α 3 , α 3 ) or (1 -α, α 2 , α 4 , α 4
We assume in the sequel that W does not contain baab as a factor. Claim 5. There does not exist a balanced word W on 4 letters, with exactly 3 distinct densities, such that δ a > δ b and δ a < 2δ c .

Proof.

In W , let X be a factor spanned by 2 consecutive c and containing exactly one a. X exists because of the condition δ a < 2δ c (Lemma A.4 with k = 2). Moreover, since δ a > δ c , there also exists a word with two a and no c. Because of the conditions on the density, X contains one a, zero or one d and one or two b. Since W does not contain bab (Claim 3), X = cbabc.

• Case 1. X = cabc Then, between 2 consecutive c there are at most 3 letters. Moreover, since δ a > δ c , there are 2 consecutive c with 2 a in between. Hence, every 3 letters contain at least an a.

A factor containing d must be of the form cdabc or cbadc (always an a and a b and at most 3 letters between two c and every 3 letters contains an a).

Since δ b ≥ δ c , there are at most 3 letters between two b and hence the previous factors expand to bcdabc or cbadcb which contradicts balancedness of a on 3 letters.

• Case 2. X = cabbdc where abbd means that those letters can be in any order. In this case, 4 letters contain at least one b.

Since δ a > δ b , there exists a factor with 2 a and no b. Because of the previous condition, this factor is of length at most 3. It implies that W contains aa or aca or ada. Hence, every 3 letters contain an a. This is in contradiction with X = cabbdc which is a 6 letters word with only one a. We now prove that W cannot contain both badc and bc. Suppose W contains a factor the form badcXbc or bcXbadc for some factor X. Since If W contains cbadabc, then it is extended to dacbadabcad. But W also contains cabadac or cadabac. In the former case, it contains both cabad and cad and in the latter case, it contains dabac and dac, which contradicts the previous paragraph.

If W contains cabadabc, then it is extended to cabadabcad which contains both cabad and cad again leading to a contradiction. Similarly, cbadabac

Definition 2 . 1 .

 21 A sequence is a subset of Z. A sequence S is D-periodic, where D is a positive integer, if S = {x + D : x ∈ S}. The period of a periodic sequence is the smallest D for which it is D-periodic. The density δ(S) of a sequence S is δ(S) := lim t→∞ {|I ∩ S|/|I| : I = {a, ..., t}, a ∈ Z}, provided the limit exists. Definition 2.2. A word on N letters is a function W : Z → {1, ..., N }, or equivalently, a (left-and right-unbounded) string of symbols on the alphabet {1, ..., N }. The word W is D-periodic if W (k + D) = W (k) for all k ∈ Z, and the period of a word is the smallest positive integer D (if any) for which it is D-periodic.

Definition 2 . 5 .

 25 A congruence word is a word {S i } i∈{1,...,N } such that all sequences S i are congruence sequences, that is, sequences of the form S i = {a i n + b i : n ∈ Z}, where a i , b i are arbitrary integers, a i = 0.Congruence sequences and words can be characterized in a way that shows that they are balanced: Proposition 2.6. [1] A sequence S ⊆ Z is a congruence sequence if and only if for every pair of intervals I 1 and I 2 of almost equal length (i.e. ||I 1 | -|I 2 || ≤ 1), the balance condition holds (i.e. ||I 1 ∩ S| -|I 2 ∩ S|| ≤ 1).

Example 2 . 10 .

 210 The word W = (abacaba) * is balanced and A = (de) * is a congruence word. Then, W A,c = (abadabaabaeaba) * is a balanced word obtained by substituting occurrences of the letter c by d and by e, alternatively.

Example 3 . 1 .

 31 The word W = (dcdedcdedcd) * is not balanced. If we use the congruence word (ab) * to expand W on the letter e, we obtain the balanced word W A,e = (dcdadcdbdcd) * on four letters.

Conjecture 4 . 1 .

 41 If a word W on N letters is balanced, then either (1) W is a congruence expansion of a balanced word on two letters, or(2) W is D-periodic for some D ≤ 2 N -1.

Lemma 4 . 3 .

 43 Let m ∈ Z + and S, T be two disjoint sequences, such that S is m-balanced and T is (m + 3)-balanced. Let R be the sequence Z \ (S ∪ T ), and W be the word formed with the three sequences R, S, T . Then, in the word W -T

  Also we know that X is a s-chain and X verifies |X ∩S| = |X ∩S|. Since S is m-balanced, it implies that |X | ≤ |X| + m (since otherwise, one would have |X ∩ S| ≥ |X ∩ S| + 1). We have |X| = |X ∩ S| + |X ∩ R| + |X ∩ T | and |X | = |X ∩S|+|X ∩R|+|X ∩T | and |X∩S| = |X ∩S| and |X ∩R|-|X∩R| ≥ m+2. Then, |X | ≤ |X| + m implies that |X ∩ T | + m + 2 ≤ |X ∩ T | + m and hence |X ∩ T | -|X ∩ T | ≥ 2. So there exists a t-chain Y ⊆ X such that |Y ∩ T | = |X ∩ T |. We also have that |Y ∩ S| ≤ |X ∩ S| and |Y ∩ R| + (m + 2) ≤ |X ∩ R|. Finally, adding up the counts of the three sequences to compare their length, the t-chain Y and the factor sX s serve as a certificate for non (m + 3)balancedness of the sequence T : Y is a t-chain and |Y | + m + 4 ≤ |sX s| and |sX s ∩ T | = |Y ∩ T |.

  ). Assuming 3 distinct densities, only remains the latter. W can be viewed as a word on C and D where one can exchange a and b in C or D. Extending C with the conditions on a and b leads to abcabab. Therefore, 7 letters contain at most one d and hence DD contradicts balancedness of d on 7 letters. Extending D leads to bcabdabca and hence 8 letters contain at most 3 a and 3 b. But CC = cababcabab contradicts the balancedness of a and b on 8 letters. Therefore, C and D alternate in W and hence the density vector is ( assume in the sequel that δ a > δ b . Claim 3. A balanced word W on 4 letters with δ a > δ b and exactly 3 distinct densities cannot contain bab as a factor. Proof. Suppose that W contains bab. Since δ a > δ b , there exists a factor with two a and no b. Consider a longest factor X with this property. If |X| = 2 then X = aa, and every 2 letters contains an a. Hence around c, one has aca which contradicts the maximality of X. Hence |X| ≥ 3 which, together with bab contradicts balancedness of b on 3 letters.

Claim 4 .

 4 A balanced word W on 4 letters with δ a > δ b and exactly 3 distinct densities and containing baab as a factor has density vector either ( The word W contains baab implies δ b > δ c by Lemma A.3 with k = 1. Hence we have δ c = δ d . Because of baab, between 2 b's, there are at most 3 letters and every two consecutive letters contain an a. Let A = baa and C = baca and D = bada Word W can be viewed as a word on A, C and D each of them appearing at least once. AA = baabaa is impossible since it contradicts the balancedness of a on 5 letters because of the existence of bacab. Since δ c = δ d , C and D alternate by Lemma A.5 and hence W contains CAD or DAC around an A. In both cases, W contains a factors of 9 letters with no d and a factor of 9 letters with no c. Therefore W can contain neither DCD nor CDC (9 letters with 2 d and 9 letters with 2 c which contradicts the balancedness of c and d). ACA (and ADA) is incompatible with CD and DC. Indeed, ACA = baabacabaa contains 9 letters with 6 a. But both CD and DC (necessarily followed by a b) imply 9 letters with 4 a. This contradicts balancedness for a on 9 letters.

•

  Case 3. X = cabdc and δ b > δ c . Hence, there are at most 4 letters between two consecutive c. Since δ b > δ c , there exists 2 b between 2 consecutive c. Moreover, between 2 b, there is at least one a and bab is forbidden. Therefore, W contains cabbdc and Case 2 applies. • Case 4. cabdc and δ b = δ c . Word W contains bacab (2 b with no d, no aa because of bc or dc, no bacb because already done in Case 1). Therefore, W contains bcadb or bdacb (only one a between two consecutive b). Hence, between 2 a there are one or two letters. Extending bcadb leads to abcadba and then to dabcadbac: the first letter is a d because aa is forbidden and there are at least 3 letters between two consecutive b or c. The last letter is a c because there are at most 4 letters between 2 c. Therefore, we know that there are 4 or 5 letters between 2 d (bacab and dabcad) and 3 or 4 letters between 2 c and between 2 b.

••

  Case 1. X = caabaac and δ b = δ c . Every 5 letters contain at least 3 a and there are at most 6 letters between 2 c. Therefore, every d is included in the factor aacabaadacaa up to a symmetry. But δ b = δ c implies that every 7 letters contain at least a b which is not the case in the previous factor. • Case 2. X = cabaac and δ b = δ c . Then the only other possibility between two c up to a symmetry is cabadac (at most 5 letters between 2 c and every 4 letters contain at least 2 a). Denote A = caaba and A = cabaa and B = cabada and B = cadaba. W can be viewed as a word on letters A, A, B and B. The factor AA = c[aabacaa]bac contradicts balancedness for a on 7 letters with B or B followed by a c by definition (the same for A A). BB = caba[dacabad]ac or BB or B B contradict balancedness for d on 7 letters with A or A followed by ca by definition. AA = caa[bacab]aa or BB contradict balancedness for b on 5 letters with cab[adaca]. AA = cabaacaaba has already been considered in Case 1 (exchanging the role of b and c since δ b = δ c ). Therefore, A or A alternate with B or B which implies densities verifying ( Case 3. X = cabadac and δ b = δ c . Then W contains caabac or caabaac (balancedness of c when there is no d between two consecutive c). This has already been considered in the previous cases. If X contains 4 a, the reasoning is similar. It cannot contain more a's because of caabac or caabaac. • Case 4. W contains aa and δ c = δ d . There exists 2 consecutive c with only one b in between (δ c > 2δ b and there also exists 2 consecutive c with 2 b in between (δ c < δ b ). Letters c and d alternate. Therefore W contains A = ca * ba x dbac and B = ca l ba y dca with l ≤ 2. in A there are at least 5 + x letters between two c. Hence, 4 + x ≤ l + 2 + y for balancedness of c. Since l ≤ 2, one obtains y ≥ x. In B, there are y + 3 ≥ x + 3 letters without a b and in A, there are 3 + x letters with two b contradicting balancedness on b. • Case 5. W does not contain aa and δ c = δ d . There exists 3 a between 2 consecutive c. Therefore W contains caaabdc or caaabbdc and hence, every 3 letters contain at least an a. There exists a factor with one b between 2 c. Therefore, if W contains caaabbdc then, it contains cabadac or cadabac (at least 5 letters between 2 c). Therefore, there exists 4 consecutive letters with no b. But there exists 2 b between consecutive c therefore, W contains cbadabc or cabadabc or cbadabac.We now prove that W cannot contain both cabad and cad. Suppose W is of the form cabadXcad for some word X. Since c and d alternate, there are the same number µ of c and d in X. In dXcad there are µ + 2 times the letter d and in abadS, there are µ times letter c and both words have the same length. This is in contradiction with δ c = δ d . Similarly, one can prove that W cannot contain both dabac and dac (exchange the roles of c and d in the proof).

  Let s and t be two integers. Let S be a periodic balanced sequence.S has density δ S > t/s if and only if there exists an interval of s integers with at least t + 1 elements from S.Proof. Suppose the last condition holds. By balancedness, each interval of

	see that the density of S is at most t/s.
	Moreover, the converse is true if S is periodic:
	Lemma A.2.
	8 15 , 4 15 , 2 15 , 1 15 .

size s has at least t elements. Partition the integers into a sequence of intervals of size s. Let D be a period of S. In every set of D consecutive intervals of size s, there is at least one interval with at least t + 1 elements. Hence the density is at least t/s + 1/Ds. Lemma A.3. Let W be a periodic balanced word, and x and y be two letters of W and k be an integer. Then δ x > kδ y if and only if there exists a factor containing k + 1 x's and no y.

Acknowledgments.

This work has been partially supported by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025).

We therefore consider the remaining case, i.e. a periodic balanced word W on 4 letters with exactly 3 distinct densities δ a ≥ δ b ≥ δ c ≥ δ d . One has δ a > δ c and δ b > δ d .

The sketch of the proof of Theorem 5.2 follows from the claims hereunder:

• If W contains aaa, then its density vector is of the form 1 -α, α 2 , α 4 , α

4

(Claim 1)

• if W does not contain aaa,

-If δ a = δ b then the densities are ( Proof. Suppose that any interval of s integers contains at most t elements from S. By partitionning the integers into a sequence of intervals of size s, we

We therefore consider in the sequel that W contains no aaa. Proof. The condition δ a > 2δ c implies that there exists a factor with at least 3 a between 2 c (Lemma A.3 with k = 2). Let X be such a factor. Then, X is of the form X = cX c where X contains no c and contains at least 3 a. extends to dacbadabac which contains both dac and dabac.

615