Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2511.11069 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909901987512320 |
|---|---|
| author | Rukavicka, Josef |
| author_facet | Rukavicka, Josef |
| contents | Let $R(n)$ denote the number of rich words of length $n$ over a given finite alphabet. In 2017 it was proved that $\lim_{n\rightarrow\infty} \sqrt[n]{R(n)}=1$; it means the number of rich words has a subexponential growth. However, up to now, no subexponential upper bound on $R(n)$ has been presented. The current paper fills this gap. Let $\frac{1}{2}<λ<1$ and $γ>1$ be real constants, let $q$ be the size of the alphabet, and let $ϕ$ be a positive function with $\lim_{n\rightarrow\infty}ϕ(n)=\infty$ and $\lim_{n\rightarrow\infty}\frac{n}{ϕ(n)}=\infty$. Let $\ln^*(x)$ denote the iterated logarithm of $x>0$. We prove that there are $n_0$ and $c>0$ such that if $n>n_0$, \[f(n)=\sqrt[γ]{c\ln^*{(\frac{n}{ϕ(n)}}\ln{q})}\quad\mbox{ and }\quad B(n)=q^{\frac{n}{ϕ(n)}+\frac{n}{(2λ)^{f(n)-1}}}\mbox{}\] then $\lim_{n\rightarrow\infty}\sqrt[n]{B(n)}=1$ and $R(n)\leq B(n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_11069 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Subexponential upper bound on the number of rich words Rukavicka, Josef Combinatorics Discrete Mathematics 68R15 Let $R(n)$ denote the number of rich words of length $n$ over a given finite alphabet. In 2017 it was proved that $\lim_{n\rightarrow\infty} \sqrt[n]{R(n)}=1$; it means the number of rich words has a subexponential growth. However, up to now, no subexponential upper bound on $R(n)$ has been presented. The current paper fills this gap. Let $\frac{1}{2}<λ<1$ and $γ>1$ be real constants, let $q$ be the size of the alphabet, and let $ϕ$ be a positive function with $\lim_{n\rightarrow\infty}ϕ(n)=\infty$ and $\lim_{n\rightarrow\infty}\frac{n}{ϕ(n)}=\infty$. Let $\ln^*(x)$ denote the iterated logarithm of $x>0$. We prove that there are $n_0$ and $c>0$ such that if $n>n_0$, \[f(n)=\sqrt[γ]{c\ln^*{(\frac{n}{ϕ(n)}}\ln{q})}\quad\mbox{ and }\quad B(n)=q^{\frac{n}{ϕ(n)}+\frac{n}{(2λ)^{f(n)-1}}}\mbox{}\] then $\lim_{n\rightarrow\infty}\sqrt[n]{B(n)}=1$ and $R(n)\leq B(n)$. |
| title | Subexponential upper bound on the number of rich words |
| topic | Combinatorics Discrete Mathematics 68R15 |
| url | https://arxiv.org/abs/2511.11069 |