Anti-power $j$-fixes of the Thue-Morse word
Recently, Fici, Restivo, Silva, and Zamboni introduced the notion of a $k$-anti-power, which is defined as a word of the form $w^{(1)} w^{(2)} \cdots w^{(k)}$, where $w^{(1)}, w^{(2)}, \ldots, w^{(k)}$ are distinct words of the same length. For an infinite word $w$ and a positive integer $k$, define...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2021-02-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/5483/pdf |
| _version_ | 1797269994313089024 |
|---|---|
| author | Marisa Gaetz |
| author_facet | Marisa Gaetz |
| author_sort | Marisa Gaetz |
| collection | DOAJ |
| description | Recently, Fici, Restivo, Silva, and Zamboni introduced the notion of a
$k$-anti-power, which is defined as a word of the form $w^{(1)} w^{(2)} \cdots
w^{(k)}$, where $w^{(1)}, w^{(2)}, \ldots, w^{(k)}$ are distinct words of the
same length. For an infinite word $w$ and a positive integer $k$, define
$AP_j(w,k)$ to be the set of all integers $m$ such that $w_{j+1} w_{j+2} \cdots
w_{j+km}$ is a $k$-anti-power, where $w_i$ denotes the $i$-th letter of $w$.
Define also $\mathcal{F}_j(k) = (2 \mathbb{Z}^+ - 1) \cap AP_j(\mathbf{t},k)$,
where $\mathbf{t}$ denotes the Thue-Morse word. For all $k \in \mathbb{Z}^+$,
$\gamma_j(k) = \min (AP_j(\mathbf{t},k))$ is a well-defined positive integer,
and for $k \in \mathbb{Z}^+$ sufficiently large, $\Gamma_j(k) = \sup ((2
\mathbb{Z}^+ -1) \setminus \mathcal{F}_j(k))$ is a well-defined odd positive
integer. In his 2018 paper, Defant shows that $\gamma_0(k)$ and $\Gamma_0(k)$
grow linearly in $k$. We generalize Defant's methods to prove that
$\gamma_j(k)$ and $\Gamma_j(k)$ grow linearly in $k$ for any nonnegative
integer $j$. In particular, we show that $\displaystyle 1/10 \leq \liminf_{k
\rightarrow \infty} (\gamma_j(k)/k) \leq 9/10$ and $\displaystyle 1/5 \leq
\limsup_{k \rightarrow \infty} (\gamma_j(k)/k) \leq 3/2$. Additionally, we show
that $\displaystyle \liminf_{k \rightarrow \infty} (\Gamma_j(k)/k) = 3/2$ and
$\displaystyle \limsup_{k \rightarrow \infty} (\Gamma_j(k)/k) = 3$. |
| first_indexed | 2024-04-25T01:57:13Z |
| format | Article |
| id | doaj.art-327ead3afe2740229d34073d23f5254d |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:13Z |
| publishDate | 2021-02-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-327ead3afe2740229d34073d23f5254d2024-03-07T15:44:09ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502021-02-01vol. 23 no. 1Analysis of Algorithms10.46298/dmtcs.54835483Anti-power $j$-fixes of the Thue-Morse wordMarisa GaetzRecently, Fici, Restivo, Silva, and Zamboni introduced the notion of a $k$-anti-power, which is defined as a word of the form $w^{(1)} w^{(2)} \cdots w^{(k)}$, where $w^{(1)}, w^{(2)}, \ldots, w^{(k)}$ are distinct words of the same length. For an infinite word $w$ and a positive integer $k$, define $AP_j(w,k)$ to be the set of all integers $m$ such that $w_{j+1} w_{j+2} \cdots w_{j+km}$ is a $k$-anti-power, where $w_i$ denotes the $i$-th letter of $w$. Define also $\mathcal{F}_j(k) = (2 \mathbb{Z}^+ - 1) \cap AP_j(\mathbf{t},k)$, where $\mathbf{t}$ denotes the Thue-Morse word. For all $k \in \mathbb{Z}^+$, $\gamma_j(k) = \min (AP_j(\mathbf{t},k))$ is a well-defined positive integer, and for $k \in \mathbb{Z}^+$ sufficiently large, $\Gamma_j(k) = \sup ((2 \mathbb{Z}^+ -1) \setminus \mathcal{F}_j(k))$ is a well-defined odd positive integer. In his 2018 paper, Defant shows that $\gamma_0(k)$ and $\Gamma_0(k)$ grow linearly in $k$. We generalize Defant's methods to prove that $\gamma_j(k)$ and $\Gamma_j(k)$ grow linearly in $k$ for any nonnegative integer $j$. In particular, we show that $\displaystyle 1/10 \leq \liminf_{k \rightarrow \infty} (\gamma_j(k)/k) \leq 9/10$ and $\displaystyle 1/5 \leq \limsup_{k \rightarrow \infty} (\gamma_j(k)/k) \leq 3/2$. Additionally, we show that $\displaystyle \liminf_{k \rightarrow \infty} (\Gamma_j(k)/k) = 3/2$ and $\displaystyle \limsup_{k \rightarrow \infty} (\Gamma_j(k)/k) = 3$.https://dmtcs.episciences.org/5483/pdfmathematics - combinatorics05a05, 68r15 |
| spellingShingle | Marisa Gaetz Anti-power $j$-fixes of the Thue-Morse word Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics 05a05, 68r15 |
| title | Anti-power $j$-fixes of the Thue-Morse word |
| title_full | Anti-power $j$-fixes of the Thue-Morse word |
| title_fullStr | Anti-power $j$-fixes of the Thue-Morse word |
| title_full_unstemmed | Anti-power $j$-fixes of the Thue-Morse word |
| title_short | Anti-power $j$-fixes of the Thue-Morse word |
| title_sort | anti power j fixes of the thue morse word |
| topic | mathematics - combinatorics 05a05, 68r15 |
| url | https://dmtcs.episciences.org/5483/pdf |
| work_keys_str_mv | AT marisagaetz antipowerjfixesofthethuemorseword |