PaperlayerView exact revision on arXiv

Source-linked AI summary

Palindromic Richness

Amy Glen, Jacques Justin, Steve Widmer, Luca Q. Zamboni

arXiv:0801.1656v3math.COcs.DM

TL;DR

Rich words occur in varied settings, motivating a unified study of their structure. The paper characterizes richness and periodic rich words, then examines balanced and wider rich-word classes; recurrent balanced rich words are precisely balanced episturmian words, and recurrent balanced weakly rich words on at least three letters are episturmian.

  • Problem

    Rich words appear in varied contexts, and the paper addresses the lack of a unified study of this class.

    Source: §1 · pp. 1–2

  • Method

    The paper characterizes rich words through palindromic complete returns, describes periodic rich words, and classifies recurrent balanced weakly rich words.

    Source: §1 · p. 2

  • Results

    Recurrent balanced rich words are precisely balanced episturmian words; recurrent balanced weakly rich words on at least three letters are episturmian.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Weakly rich words obey Fraenkel’s conjecture, while recurrent balanced words in a certain almost rich class are episturmian or have two distinct letters with the same frequency.

    Source: §1 · p. 2

    For periodic richness, neither having all conjugates rich nor being a rich product of two palindromes alone suffices.

    Source: §3 · p. 7

Abstract

from arXiv · show

In this paper, we study combinatorial and structural properties of a new class of finite and infinite words that are 'rich' in palindromes in the utmost sense. A characteristic property of so-called "rich words" is that all complete returns to any palindromic factor are themselves palindromes. These words encompass the well-known episturmian words, originally introduced by the second author together with X. Droubay and G. Pirillo in 2001. Other examples of rich words have appeared in many different contexts. Here we present the first unified approach to the study of this intriguing family of words. Amongst our main results, we give an explicit description of the periodic rich infinite words and show that the recurrent balanced rich infinite words coincide with the balanced episturmian words. We also consider two wider classes of infinite words, namely "weakly rich words" and almost rich words (both strictly contain all rich words, but neither one is contained in the other). In particular, we classify all recurrent balanced weakly rich words. As a consequence, we show that any such word on at least three letters is necessarily episturmian; hence weakly rich words obey Fraenkel's conjecture. Likewise, we prove that a certain class of almost rich words obeys Fraenkel's conjecture by showing that the recurrent balanced ones are episturmian or contain at least two distinct letters with the same frequency. Lastly, we study the action of morphisms on (almost) rich words with particular interest in morphisms that preserve (almost) richness. Such morphisms belong to the class of "P-morphisms" that was introduced by A. Hof, O. Knill, and B. Simon in 1995.

1 Introduction

The paper presents a unified study of rich words, whose factors contain the maximum number of distinct palindromes, and characterizes them through palindromic complete returns. It also develops results on almost rich and weakly rich words, balancedness, and morphisms.

1 Introduction

  • The paper situates rich words among examples including episturmian words, sequences with abundant palindromic prefixes, and words from other settings.The motivation for studying arbitrarily long palindromes includes modeling quasicrystals and Diophantine approximation.Source: §1 · pp. 1–2
  • All complete returns to palindromic factors characterize rich words, and periodic rich infinite words receive an explicit description.These are among the paper’s principal structural results.Source: §1 · p. 2
  • The paper introduces almost rich words with finitely many prefixes failing Property Ju, and weakly rich words whose complete returns to letters are palindromes.Both classes include rich words.Source: §1 · p. 2
  • Recurrent balanced rich infinite words are precisely balanced episturmian words; recurrent balanced weakly rich words on at least three letters are episturmian.The paper also relates these classes to Fraenkel’s conjecture.Source: §1 · p. 2
  • The paper studies morphisms acting on rich and almost rich words, especially those that preserve (almost) richness.The preserving morphisms belong to the class of P-morphisms.Source: §1 · p. 2

1.1 Notation and terminology

  • The notation section establishes basic word, palindrome, factor, recurrence, and morphism terminology used throughout.It defines finite and infinite words over an alphabet, along with factors, reversals, and morphism action.Source: §1.1 · p. 3

2 Definitions and basic properties

Richness can be recognized both by its maximal palindrome count and by palindromic complete returns. The section establishes basic closure and recurrence properties, including a criterion for recurrence.

2 Definitions and basic properties

  • A finite word is rich exactly when each prefix has a unioccurrent palindromic suffix, and richness is inherited by its factors.A rich finite word has exactly |w| + 1 distinct palindromic factors.Source: §2 · p. 4
  • Palindromic closure preserves richness, and rich words with the same palindromic factors are abelianly equivalent.Rich words can also be extended by letters on either side while remaining rich.Source: §2 · pp. 4–5
  • Recurrent rich infinite words need not be uniformly recurrent.The section gives morphic examples, including the Cantor word, of recurrent rich words that are not uniformly recurrent.Source: §2 · p. 5
  • A recurrent rich infinite word is recurrent exactly when its factor set is closed under reversal.Recurrent rich infinite words have infinitely many palindromic prefixes.Source: §2 · p. 5
  • A word is rich exactly when every complete return to a palindromic factor is itself a palindrome.Equivalently, rich finite words have |w| + 1 distinct palindromic factors; the complete-return criterion also applies to infinite words.Source: §2 · p. 6

3 Periodic rich infinite words

The section characterizes periodic rich infinite words through properties of their period. It also clarifies that neither condition in the characterization suffices by itself.

3 Periodic rich infinite words

  • A periodic word wω is rich exactly when w is a product of two palindromes and every conjugate of w is rich.The equivalence is stated in Theorem 3.1.Source: §3 · p. 6
  • (aabbaabab)ω and (abcba)ω are examples of periodic rich infinite words.Source: §3 · p. 6
  • Neither all conjugates being rich nor a rich period that is a product of two palindromes alone guarantees that wω is rich.The section gives counterexamples to both incomplete conditions.Source: §3 · p. 7

4 Some related words

Section 4 relates bounded palindromic defect to almost richness, then studies oddities and weakly rich words. It gives structural criteria for periodic and recurrent almost rich words, and identifies how weakly rich words differ from almost rich ones.

4.1 Defects & oddities

  • Defect counts missing palindromic factors, and an infinite word is almost rich when its defect is bounded; a prefix without a UPS increases defect by one.Extending a word by a letter from its alphabet can also increase its defect, including under palindromic closure.Source: §4.1 · p. 8
  • A periodic word wω is almost rich exactly when w is a product of two palindromes.Source: §4.1 · p. 8
  • If an almost rich word is recurrent, its factor set is closed under reversal.Source: §4.1 · p. 8
  • Oddities—non-palindromic complete returns to palindromes, up to reversal—are bounded by defect, though the bound can be strict.Source: §4.1 · p. 9
  • For uniformly recurrent words, infinitely many oddities are equivalent to having infinitely many palindromic factors and infinitely many defects.Uniform recurrence is needed for the implication from infinitely many oddities; the converse does not require it.Source: §4.1 · p. 9

4.2 Weakly rich words

  • Weakly rich words require palindromic complete returns only to letters; every binary word is weakly rich, and neither weakly rich nor almost rich contains the other.The two classes have examples outside the other class.Source: §4.2 · p. 10

5 Applications to balance

This section examines applications of balance to recurrent rich, weakly rich, and almost rich words. It characterizes recurrent balanced rich and weakly rich words, gives a frequency conclusion for recurrent balanced almost rich words with few oddities, identifies a periodic form for recurrent balanced skeletons meeting specified oddity and separation conditions, and establishes a Fraenkel-conjecture conclusion for a class of infinite words wider than rich.

5.1 Balanced rich words

  • Recurrent balanced rich infinite words are precisely the balanced episturmian words.With mutually distinct letter frequencies, such words are Sturmian or, up to letter permutation and shifts, have the form of Fraenkel’s sequence.Source: §5.1 · pp. 11–12

5.2 Balanced weakly rich words

  • For at least three letters, every recurrent balanced weakly rich word is a periodic episturmian word and is classified, up to letter permutation and shift, into two periodic forms.If its letter frequencies are mutually distinct, it is, up to letter permutation and shift, (Fk)ω.Source: §5.2 · pp. 12, 14

5.3 Balanced almost rich words

  • Applying ψa cannot decrease defects: if s = ψa(t), then D(s) ≥ D(t), so almost richness of s implies almost richness of t.The passage also states that oddities cannot decrease under ψa: O(s) ≥ O(t).Source: §5.3 · p. 15
  • A recurrent balanced infinite word on more than two letters with fewer oddities than letters is episturmian or has two letters with the same frequency.When a balanced word m = ψc(r) meets the fewer-oddities condition, r is a balanced skeleton with fewer oddities than letters in its alphabet.Source: §5.3 · pp. 15–16
  • A recurrent balanced skeleton over more than two letters, with fewer oddities than letters and no separating letter, has form (x(ab)^nax(ba)^nb)^ω up to shift, for n ≥ 1.Source: §5.3 · p. 16
  • With fewer oddities than letters, some letter has only palindromic complete returns, all of the same odd length.This is the starting structural observation in the proof of the skeleton classification.Source: §5.3 · p. 16
  • The part concludes that a class of infinite words wider than rich obeys Fraenkel’s conjecture.The passage describes this as another class of infinite words, without specifying its full definition here.Source: §5.3 · p. 17

6 Action of morphisms

Section 6 studies morphisms that preserve richness or almost richness, developing criteria for P-morphisms and linking morphism structure to richness, defects, and generated infinite words. It also establishes that morphisms satisfying the stated conditions for preserving almost richness belong to class P and relates this to an open question about primitive morphisms producing arbitrarily long palindromes.

6.1 Various results

  • The morphism ψa preserves richness in both directions for infinite words, episturmian morphisms strictly preserve infinite-word richness, and insertion morphisms and exponent-shortening transformations preserve richness.The ψa equivalence does not extend to finite words: the paper gives a non-rich finite word whose image is rich.Source: §6.1 · pp. 17–18
  • A richness-preserving morphism prolongable on a letter generates a rich infinite word, while strict palindrome preservation implies injectivity when the alphabet has more than one letter.Letter doubling strictly preserves palindromes and doubles finite defect, placing defects at positions 2pi − 1 and 2pi for each original defective position pi.Source: §6.1 · pp. 18–19

6.2 Class P morphisms

  • For a special standard P-morphism, the image of a rich infinite word is rich exactly when the image of a finite prefix containing all length-at-most-2 palindromes, followed by p, is rich.For a prolongable morphism, the same test applies to the shortest such prefix of its generated word. One example maps the Fibonacci word to a rich infinite word although its own generated words have infinitely many defects.Source: §6.2 · pp. 20–21
  • Special standard P-morphisms map finite-defect infinite words to almost-rich words, with the image defect equal to that of a specified finite prefix image.The prefix must have the original word’s finite defect and contain all palindromic factors of length at most 2.Source: §6.2 · p. 20
  • Special P-morphisms strictly preserve almost richness, and special standard P-morphisms do not decrease defect; thus a rich image under one implies a rich preimage.The defect inequality is D(s) ≥ D(t) when s is the morphic image of t.Source: §6.2 · pp. 21–22
  • Under the stated hypotheses, a non-erasing morphism that preserves richness must be of class P.The theorem’s assumptions include a condition on images of triples of distinct letters.Source: §6.2 · p. 22
  • The proof concludes that ϕ is a P-morphism.The argument treats cases with multiple non-palindromic images, exactly one such image, or only palindromic images.Source: §6.2 · p. 23
  • Condition (6.1) holds when ϕ is injective or strictly preserves richness.The passage says extending the theorem to non-primitive ϕ(x) requires appropriately reformulated conditions.Source: §6.2 · p. 24
  • Under Theorem 6.33’s conditions, any morphism preserving almost richness is of class P.The passage notes that preserving infiniteness of palindromic factors could replace preserving almost richness.Source: §6.2 · p. 24
  • The open question asks whether uniformly recurrent infinite words with arbitrarily long palindromes can arise from primitive morphisms, none of which is class P [19].The answer is believed to be no; it has been shown only for the periodic case and the 2-letter case.Source: §6.2 · p. 24

7 Concluding remarks

The concluding remarks recall a bound relating palindromic and factor complexity for uniformly recurrent words with factors closed under reversal. They note that words attaining this bound are rich, as recently proved in [8].

7 Concluding remarks

  • P(n) counts distinct palindromic factors of length n, while C(n) counts distinct factors of length n.These are the palindromic complexity and factor complexity functions, respectively.Source: §7 · p. 24
  • For uniformly recurrent words with factors closed under reversal, P(n) + P(n + 1) ≤ C(n + 1) − C(n) + 2 for all n ∈ N.Source: §7 · p. 24
  • Words attaining the upper bound in (7.1) for every n are rich, an assertion proved in [8].Such words can be viewed as containing the maximum number of palindromes.Source: §7 · p. 24
  • The proof in [8] uses another characterization of rich words to establish that the super reduced Rauzy graph is a tree.The characterization is useful for the key part of that proof.Source: §7 · p. 24
Loading 0801.1656v3…