Novel Constructions of Words with Strong Avoidance Properties and their Combinatorial Analysis

Duaa Abdullah, Jasem Hamoud · 2025

Read Novel Constructions of Words with Strong Avoidance Properties and their Combinatorial Analysis by Duaa Abdullah, Jasem Hamoud (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-11403.txt.

Introduction

Combinatorics on words studies strings of symbols the way number theory studies integers, asking which patterns must appear and which can be avoided forever. Duaa Abdullah and Jasem Hamoud add new constructions in 2025. They define a class of infinite words, called strongly (k, δ)-free words, built by applying cyclic shift morphisms — rules that rewrite each symbol and rotate the output.

For these words they prove a theorem pinning down exactly which avoidance properties hold, with a detailed proof. They also pose a conjecture about the words' factor complexity, the count of distinct blocks of each length. The paper opens with a broad tour of the field and its ties to symbolic dynamics, then presents the new family as ground for further work on the structure of infinite words.

Catalog record

CREATORDuaa Abdullah, Jasem Hamoud
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-11403

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Novel Constructions of Words with Strong Avoidance Properties and their Combinatorial Analysis Duaa Abdullah, Jasem Hamoud Abstract This paper begins with a comprehensive overview of combinatorics on words and symbolic dynamics, covering their historical origins, fundamental concepts, and interconnections. Building upon this foundation, we introduce novel mathematical constructions related to pattern avoidance in infinite words. Specifically, we define Strongly ( k , δ ) (k,\delta) -Free Words generated via cyclic shift morphisms and present a theorem establishing specific avoidance properties for these words, along with a detailed proof. Furthermore, we propose a conjecture regarding their factor complexity. These original results contribute to the theoretical understanding of word structures and their combinatorial properties, opening avenues for further research in discrete mathematics. MSC Classification 2020: 68R15, 11B39, 05A05, 68R15, 37B10. Keywords: Construction, Word, Combinatorics, Analysis, Symbolic Dynamics. 1 Introduction Combinatorics on words, a vibrant subfield of discrete mathematics, has emerged as a cornerstone of both theoretical inquiry and applied computational research. Rooted in the study of symbol sequences and their structural properties, this discipline intersects profoundly with dynamical systems, formal languages, and algorithmic complexity. Recent decades have witnessed significant advances in pattern avoidance, morphic word generation, and connections to symbolic dynamics—a framework for analyzing dynamical systems through discretized state spaces. Despite these developments, critical challenges persist in constructing infinite words with tailored avoidance properties while preserving computational tractability, particularly when integrating algebraic symmetries such as cyclic permutations. Bridging this gap requires novel methodologies that harmonize combinatorial rigor with dynamical systems theory—a synthesis central to this work. The foundational contributions of Axel Thue [ 4 ] on repetition-free words catalyzed modern combinatorics on words, while subsequent efforts by Lothaire [ 3 ] , Perrin, and Allouche expanded its theoretical and applied horizons. Yet, existing paradigms remain constrained by their reliance on static alphabets and identity-based repetitions, limiting their adaptability to systems where symbol transformations inherently govern structural evolution. For instance, while classical k -power avoidance is well-studied, generalizations incorporating permutational twists—essential for modeling cyclic symmetries in biological sequences, cryptographic systems, or shift-invariant dynamical systems—remain underexplored. This study addresses this limitation by introducing twisted repetitions, where avoidance constraints intertwine with cyclic permutations, and by analyzing infinite words generated via cyclic shift morphisms [ 8 , 2 ] . In this paper, we establish three principal contributions. First, we define strongly (k,\delta) -free words, a generalization of power-free words where repetitions are prohibited under iterated permutations \delta of the alphabet. This framework subsumes classical avoidance (e.g., square-free words) while enabling nuanced control over symbol transformations. Second, we construct a family of infinite words through cyclic shift morphisms—2-uniform substitutions that iteratively append permuted symbols—and prove their avoidance properties. Specifically, Theorem 2.6 demonstrates that for an alphabet of size N\geq 3 and cyclic permutation \sigma , the generated word avoids strongly (3,\delta) -repetitions when \delta=\sigma^{j} and j\not\equiv 1\pmod{N} . Third, we conjecture the linear factor complexity of these words, aligning them with Sturmian-like sequences while broadening their applicability to symbolic dynamics. These results are rigorously validated through synchronization arguments, infinite descent, and structural analysis of morphic images. The implications of this work extend beyond combinatorics. By linking twisted repetitions to shift spaces in symbolic dynamics, we provide tools to classify dynamical complexity through forbidden patterns—a paradigm shift with potential applications in data compression, chaos theory, and biosequence analysis. Furthermore, our morphism-driven constructions offer algorithmic templates for generating sequences with guaranteed avoidance properties, relevant to coding theory and automata design. This paper is structured as follows: Section 1 synthesizes the history of combinatorics on words and symbolic dynamics, contextualizing their interplay. Section 2 introduces novel definitions and proves the central avoidance theorem, while Section 3 discusses broader implications and future directions, including unresolved conjectures and connections to shift space entropy. By unifying combinatorial and dynamical perspectives, this research not only advances the axiomatic foundations of word combinatorics but also opens interdisciplinary pathways for exploring complex systems through discrete mathematical lensess. 1.1 History of Combinatorics on Words Combinatorics on words, a vigorous and relatively recent topic within discrete mathematics, digs into the study of sequences of symbols or words, and their fundamental features. Although its formalization as a distinct field is comparatively recent, its roots are deeply embedded in various mathematical and scientific inquiries that span centuries. Axel Thue’s pioneering work at the turn of the twentieth century is frequently credited with the systematic study of words in the combinatorial sense. Thue investigated square-free words, which are sequences without two adjacent identical blocks of symbols, marked a significant turning point and laid the foundational groundwork for the field. As Roger Lyndon, a prominent figure in the area, noted, Thue’s contribution was not merely his theorems but his delineation of this new subject of study [ 6 ] . The larger discipline of combinatorics, which serves as the intellectual foundation for combinatorics on words, has a long wider and more diversified history. Combinatorics, at its core, is concerned with the counting, organization, and attributes of finite or discrete structures. Basic combinatorial concepts and enumerative problems can be traced back to ancient civilizations. For instance, the Rhind Papyrus, dating back to the 16th century BC, contains problems with combinatorial characteristics, such as those involving geometric series, which bear resemblance to later problems example, Fibonacci’s work on compositions.In a similar way ancient Indian writings, such as the Sushruta Samhita, show ancient combinatorial computations, such as calculating the number of possible combinations of various flavours. Greek mathematicians and philosophers, including Chrysippus and Hipparchus, also grappled with complex enumerative problems, some of which were later connected to sophisticated combinatorial numbers, for example, the Schröder–Hipparchus numbers. Archimedes, in his work on the Ostomachion, is thought to have considered configurations of tiling puzzles, another early instance of combinatorial thinking. During the Middle Ages, combinatorics was studied extensively, especially beyond Europe. In the 9th century, Indian mathematicians such as Mahavıra developed precise formulas for permutations and combinations, based on knowledge that may have existed in India since the mid-6th century AD. Scholars such as Rabbi Abraham ibn Ezra (c. 1140) developed features such binary coefficient symmetry, which Levi ben Gerson constructed a closed formula for in 1321.The arithmetical triangle, famously known as Pascal’s triangle, which graphically displays relationships among binomial coefficients, appeared in mathematical treatises from the 10th century onwards. The Renaissance witnessed a development in interest in compositions, in addition to other mathematical and scientific fields. The contributions of luminaries such as Blaise Pascal, Isaac Newton, Jacob Bernoulli, and Leonhard Euler were instrumental in shaping the emerging field. Their work laid much of the groundwork for what would later become enumerative and algebraic combinatorics. In more modern times, the efforts of mathematicians like J.J. Sylvester in the late 19th century and Percy MacMahon in the early 20th century further solidified these foundations. The concurrent rise of graph theory, often spurred by problems like the four-color problem, also contributed significantly to the development of combinatorial methods. The formal emergence of combinatorics on words as a distinct area of study can be seen as a confluence of these historical streams with more focused investigations into the properties of sequences. The work of Thue, though initially overlooked for several decades, was eventually recognized for its profound implications. His 1906

Read the complete text