4
$\begingroup$

(If anyone has a better title please change it!)

Given two finite words $v,w$ in the alphabet $\{a,b\}$, define the $v$-proportion of $w$ to be the largest number of letters in $w$ which can be covered by (not necessarily disjoint) copies of the word $v$ divided by the length of $w$. Denote this quantity by $Pr(w;v)$.

As an example, $Pr(a^7ba^7b;a^4)=7/8$, but $Pr(a^7ba^7b;a^8)=0$.

I would like to find a family of finite words $w_i$ in the alphabet $\{a,b\}$ with the following properties:

For every $n$, $\limsup_i Pr(w_i,a^n)=\alpha_n>0$ but $\limsup_n \alpha_n=0$.

$\endgroup$
1
  • 1
    $\begingroup$ Do an interleaving of sequences with repetition. Suppose you have a sequence of words that works and gives you nice alphas below n, all of value > 1/n, and you want alpha_n to be less than 1/n. Insert a^nb^(n^2) into your sequence at every nth position. Gerhard "Is Feeling Very Sketchy Today" Paseman, 2017.02.21. $\endgroup$ Feb 21, 2017 at 19:33

1 Answer 1

3
$\begingroup$

Try $w_0 = b$, $w_1 = bab$, $w_2 = baba^2bab$, $w_3 = baba^2baba^3baba^2bab$, and recursively $w_{i+1} = w_ia^{i+1}w_i$.

Then $\displaystyle \limsup_{i \rightarrow \infty} Pr(w_i,a^n) = \lim_{i \rightarrow \infty} \frac{2^{i + 2 - n} +n - i -3}{3\cdot 2^i - i - 2} = \frac{2^{2-n}}{3} \rightarrow_n 0$.

-Danny "Likes Anything That Resembles a Zimin Word" Rorabaugh

$\endgroup$
3
  • $\begingroup$ Maybe we should get together on some hyperidentities: mathoverflow.net/a/84606 . Gerhard "Lots More Words To Cover" Paseman, 2017.02.24. $\endgroup$ Feb 24, 2017 at 23:55
  • $\begingroup$ I'm not sure I can prove the values you claim, but I'm happy that they answer the original question. $\endgroup$
    – DavidHume
    Mar 2, 2017 at 15:41
  • $\begingroup$ In fact a little bodged calculation suggests the first few values in n should be 2/3, 1/2, 1/3, 5/24, 1/8, 7/96, 1/24... $\endgroup$
    – DavidHume
    Mar 2, 2017 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.