m-aperiodic words on three-letter alphabet

Толық мәтін

Introduction

The work is devoted to the study of sets of aperiodic words over a finite alphabet. The set of aperiodic words can be considered as a dictionary of some finite formal language.

Data on the existence of an infinite word in a two- or three-letter alphabet, which does not contain subwords that are cubes or, respectively, squares, were first obtained by A. Thue in 1906.  [1]. An example of an infinite sequence of irreducible words, each of which is the beginning of the next and does not contain squares of words in an alphabet of two letters, was constructed by S. I. Adyan (Lemma 1 from [2]). In an article by S. E. Arshon in 1937. [3] the existence of an n-digit asymmetric repetition-free sequence for an alphabet of at least three letters has been proven. In the monograph by S. I. Adyan  [4] it has been proven that in an alphabet of two symbols there exist infinite 3-aperiodic sequences. The problem of studying such sequences is considered by S. I. Adyan in connection with his study of the Burnside problem [5–7]. A. M. Shur found out which properties of ordinary words are preserved during the transition to infinite ones, and which ones are modified, lost or replaced by new ones, and studied the set of all cubeless Z-words in a two-letter alphabet  [8–10]. In the monograph by A. Yu. Olshansky [11], the infinity of the set of 6-aperiodic words in a two-letter alphabet was proved and an estimate was obtained for the number of such words of any given length.

We have improved A. Yu. Olshansky’s estimate [11] of the number of 6-aperiodic words in the 2-letter alphabet [12], and also made a report on the topic of aperiodic words [13]. Then research on this issue continued.

In [14], a theorem was proven about the infinity of the set of m-aperiodic words for  in a two-letter alphabet and an estimate of the number of such words was obtained. The case of a three-letter alphabet was considered only in one case: in [15], an estimate was obtained for the number of 6-aperiodic words.

In this article, the set of m-aperiodic words in the three-letter alphabet will be studied: the infinity of the set of m-aperiodic words for $m\ge 4$ in three letters alphabet and an estimate of the number of such words was obtained. The results may be useful when encoding information in space communication sessions.

Generalizations of aperiodicity, when not only the powers of some subwords are excluded, were studied in [16].

Main result

We consider that a periodic word with period H is any subword of some word Н^р, р > 0.

As an example of a periodic word with period ab,  we consider the word ababa .

A l-aperiodic word is a word X in which there are no nontrivial subwords of the form  Y^l.

S.I. Adyan [4] proved that in an alphabet of two letters there are infinitely many arbitrarily long 3-aperiodic words.

S. E. Arshon established the existence of words of any length free from squares in a three-letter alphabet [3].

A. Yu. Olshansky in [11] considered a set of 6-aperiodic words. He proved that such words of any length exist and obtained an estimate for the function $f\left(n\right)$ – number of 6-aperiodic words of length $n$. There were more of them than ${\left(\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^n$. In [12], we improved A. Yu. Olshansky’s estimate of the number of 6-aperiodic words over a 2-letter alphabet.

In [15], we proved a theorem about the infinity of the set of m-aperiodical words under a period limitation $m\ge 4$ in a two-letter alphabet and obtained a lower estimate for the number of such words.

It is of interest to us to estimate the number of m-aperiodic words in an alphabet of three letters.

When proving the theorem, we will use the method used by A. Yu. Olshansky [11].

Theorem. In the three-letter alphabet there are arbitrarily long m-aperiodical words for $m\ge 4$ and number $f\left(n\right)$ there are more such words of length  than ${\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^n$.

Proof. We consider the three-letter alphabet {a, b, c}. In this alphabet we will study m-aperiodic words for $m\ge 4$. We will investigate the function $f\left(n\right)$ number of m-aperiodic words of length n.

First we prove the inequality $f(n+1)>(5/2)f\left(n\right)$ using the method of mathematical induction.

We note that there are exactly three m-aperiodic words a, b, c of length one and nine m-aperiodic words aa, ab, ac, ba, bb, bc, ca, cb, cc of length 2 in the three-letter alphabet for $m\ge 4$. Thus, in this case we have $f\left(1\right)=3$, $f\left(2\right)=9$.

Then for n = 1 the inequality holds $f\left(2\right)>\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\cdot f\left(1\right)$ and the resulting estimate is as a base of induction

Now we need to take the induction step. We assume that the inequality $f\left(n\right)>(5/2)f(n-1)$ is true for all values not exceeding n, and establish its validity in the case $f(n+1)>(5/2)f\left(n\right).$

Any m-aperiodic word of length $n+1$ can be obtained by assigning the letters a, b or c to the right of the m-aperiodic word of lengt $n$.  This produces $3f\left(n\right)$ words of X length $n+1$.

Some of these words contain degrees $A^m$. We try to discard such words containing subwords of period m.

When assigning a new letter to the right, you can only get a word like $X\equiv Y{A}^m$, containing a word of period m, since otherwise the beginning of length $n$ of the word X of length $n+1$ contains a periodic subword of period m: $A^m$.

For words A of length 1 (there are only three such words), there are at most $3f(n-m+1)$ words of $X\equiv Y{A}^m$ type, where the word Y m is aperiodic and $\left|Y\right|=n-m+1$, A is one of the words a, b, c.

As shown above, there are only nine words A of length 2. Then the number of words of the form $X\equiv Y{A}^m$ length $n+1$ is no more than $9f(n-2m+1)$, where the word Y is m-aperiodic and has a length $n-2m+1$.

We further reason in the same way and obtain an estimate for the number of words of length n + 1 (a strict inequality, since it is easy to indicate words that, when obtaining an estimate for the number of words of the form $X\equiv Y{A}^m$, already with a length of 1 word A, we discarded in excess to obtain an estimate):

$f(n+1)>3f\left(n\right)-3f(n-m+1)-3^{2}f(n-2m+1)-3^{3}f(n-3m+1)-\mathrm{...}$

Since the estimate is valid by inductive assumption $f\left(n\right)>{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^k\cdot f(n-k),$ applying it, we see:

$f(n+1)>3f\left(n\right)-\left(3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m+1}f\left(n\right)+3^2{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-2m+1}f\left(n\right)+3^3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-3m+1}f\left(n\right)+\mathrm{...}\right).$

We transform the resulting inequality:

$f(n+1)>f\left(n\right)(3-\left(3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m+1}+3^2{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-2m+1}+3^3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-3m+1}+\mathrm{...}\right)$.

Obviously, $\sqrt[m]{3}<\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.$, therefore the geometric progression in brackets is decreasing with the denominator  $3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}$ with the limitation $m\ge 4$.

For the expression S in parentheses on the right side, we apply the formula for the sum of a decreasing geometric progression

$S=3-\frac{3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m+1}}{1-3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}}$.

To prove the theorem, we need an estimate of the expression in brackets on the right side of the inequality $S>\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.$.

We substitute the expression obtained above for S into the inequality and perform elementary transformations:

$\frac{3-9{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}-3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m+1}+3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m+1}-\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}{1-3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}}>0$.

We will simplify the resulting inequality:

$\frac{3-9{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}-\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}{1-3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}}>0$.

Since the inequality $1-3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}>0$ holds for $m\ge 4$, it remains to check the validity of the inequality :

$3-9{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}-\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.>0$.

The validity of this inequality is established by direct calculation at $m=4$, and $m\ge 4$ at it is even more true, since ${\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}<{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-3}$ for such m. Consequently, it has been proven that the inequality $f(n+1)>\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.f\left(n\right)$ holds for any natural values of the number n, subject to $m\ge 4$.

The theorem is proven.

Conclusion

The question of estimating the number of aperiodic words under various conditions continues to be studied. The set of m-aperiodic words for $m\ge 4$ in a three-letter alphabet is considered and an estimate is obtained for the function of the number of such words of any given length. 

Благодарности. Работа выполнена в рамках госзадания ИВМ СО РАН (базовый проект № 0287-2021-0002). Работа поддержана Красноярским математическим центром, финансируемым Минобрнауки РФ (Соглашение 075-02-2024-1429).

Acknowledgment. The work was performed in the framework of the state assignment of ICM SB RAS, project no. 0287-2021-0002. This work is supported by the Krasnoyarsk Mathematical Center and financed by the Ministry of Science and Higher Education of the Russian Federation (Agreement No. 075-02-2024-1429).

Авторлар туралы

Vladimir Senashov

Хат алмасуға жауапты Автор.
Email: sen1112home@mail.ru

doctor of physic and mathematic sciences, professor, leader researcher

Әдебиет тізімі

Қосымша файлдар