2
$\begingroup$

It is a known fact [1] that, for every $c\in (1,\infty]$, it is possible to find a finite alphabet $\mathcal{A}$ and a word $w\in \mathcal{A}^\omega$ such that $w$ has critical exponent $c$. It looks natural to define what I would call the critical exponent function in two steps as follows.

Step 1

For every integer $n\ge2$, the $n$-critical exponent function $\kappa_n$ is defined by: \begin{equation} x\in[0,1]\;\longmapsto \;\kappa_n(x)=\frac{1}{c_n(x)} \end{equation} where $c_n(x)$ is the critical exponent of the $n$-base expansion of $x$ (and it is intended $\frac{1}{\infty}=0$). Notice that $\kappa_n$ is not affected by the possible ambiguity in the expansion of some rational points (the critical exponent is $\infty$ for both the possible expansions).

The range of $\kappa_n$ is $\left[0,\frac{4}{7}\right]$ for $n=3$, $\left[0,\frac{5}{7}\right]$ for $n=4$ and $\left[0,\frac{n-1}{n}\right]$ when $n=2$ or $n\ge 5$. This is due to a result by Rao [2] covering the last cases of a general conjecture by Dejean on repetition thresholds for finite alphabets [3].

Step 2

The critical exponent function $\kappa$ is defined by: \begin{equation} \kappa: x\in[0,1]\;\longmapsto\; \sup_{n\ge 2}{\kappa_n(x)}\in[0,1] \end{equation}

It is easily seen that $\kappa$ vanishes on absolutely normal real numbers. Therefore, $\kappa$ is Lebesgue-measurable and $\int_0^1 \kappa(x)dx=0$.

Looks like $\kappa$ has several unusual properties (it recalls loosely Conway's base-13 function). Almost every question about it I can think of seems non-trivial. I propose three of them.

Q1: Which Baire class (if any) does $\kappa$ belong to?

Q2: Does $\kappa$ have fixed and/or periodic points (apart from the trivial fixed point 0)?

Q3: Does $\kappa$ attain the value 1?

[1]: Krieger, D., & Shallit, J. (2007). Every real number greater than 1 is a critical exponent. Theoretical computer science, 381(1-3), 177-182.

[2]: Rao, M. (2011). Last cases of Dejean's conjecture. Theoretical Computer Science, 412(27), 3010-3018.

[3]: Dejean, F. (1972). Sur un théorème de Thue. Journal of Combinatorial Theory, Series A, 13(1), 90-99.

$\endgroup$
1
$\begingroup$

I was thinking about Q3, and have a silly thought/question. The definition of critical exponent is apparently a supremum over all $w$ of the maximum "power" of $w$ appearing, but there's a natural related definition using a limsup (in terms of the length of $w$). Is it obvious that you can't get limsup 1 for a single {0,1} sequence (i.e. base 2 expansion)? I see how to get 1 + $\epsilon$ for any $\epsilon$, but not yet how to get 1.

The relevance to your Q3 is that if a single base-2 expansion for x has "limsup critical exponent 1," then the base-$2^n$ expansions will have $\kappa_n$ approaching $1$, which would give a "yes" answer to Q3.

$\endgroup$
3
  • 1
    $\begingroup$ Do you mean $\limsup_{\ell\to\infty}(\sup \{\alpha:\, \text{there is a factor of length $\ell$ which appears as an $\alpha$-power}\})$? $\endgroup$ Dec 8 '20 at 21:51
  • $\begingroup$ I was thinking of $\limsup_{\ell \rightarrow \infty} (\sup\{\alpha : \textrm{ there exists a word $w$ of length $\ell$ whose $\alpha$-power appears as a factor}\})$, but I think that this is probably equivalent to yours. $\endgroup$ Dec 11 '20 at 3:37
  • $\begingroup$ It is (I assume you rather meant that, in your hypothesis, $\kappa_{2^n}(x)\to 1$). And no, it isn't obvious to me that you can't have a binary sequence whose "limsup" critical exponent is 1. $\endgroup$ Dec 12 '20 at 21:35
0
$\begingroup$

I think Ronnie's question is of independent interest, and I think the answer is that one can construct an example where the eventual/limsup critical exponent is one (giving also "yes" to Q3). I didn't do the math, but I'll outline my thoughts about how a construction might go. An intense numerology session would be needed to get it closer to a proof. The problem sounds like something someone would've thought about already.

So, we want to construct $x \in \{0,1\}^\omega$ such that $$ \limsup_{\ell \rightarrow \infty} ( \sup \{ \alpha \;|\; \mbox{there exists a word $w$ of length $\ell$ whose $\alpha$-power appears as a factor in $x$}) = 1 $$ Equivalently, we want to show that there is an $x \in \{0,1\}^\omega$ such that for all $\epsilon > 0$ there exists $\ell$ such that no word longer than $\ell$ is an $(1+\epsilon)$-power. It's enough to show this for $\epsilon < 1$, in which case it is just a bound on how quickly a word can repeat, since an $1+\epsilon$ power for $\epsilon < 1$ is just a word of the form $uwu$.

Say a set of words $W \subset \{0,1\}^*$ is mutually unbordered if no two words from $W$ can overlap nontrivially, i.e. whenever $uw = w'v$ and $w, w' \in W$, we have $w = w'$ or $|u| \geq |w'|$. Let's use the set $W = \{1^n 0 w 0 \;|\; w \in \{0,1\}^{n-2}\}$. These words have length $2n$ and there are $\Theta(2^n)$ of them. If you construct $x \in \{0,1\}^\omega$ from a concatenation of these words, then it is easy to see that a word of length at least $4n$ can repeat only if we use the same word from $W$ twice. Thus we could avoid repeating words of length $4n$ for an exponentially long time by simply not using the same word from $W$ twice.

Now, pick some small $\epsilon > 0$ to begin with, pick $n$ suitably for this $\epsilon$ to get the set $W$, and pick another parameter $h$. Let's promise ourselves that $x$ is built from the words $W$. By the same argument of not repeating a word, we can avoid too quick repeats of words in the length range $[2(h+1)n, \Theta(\epsilon n2^n)]$, by picking every $h$th $W$-word suitably, for example just allocate half of $W$ for this repeat-avoidance and enumerate through that set. This gives us an exponential time to come up with something clever.

I have nothing clever up my sleeve, but let's just use the same idea: while every $h$th word is picked already, we have full freedom over the rest. And now we effectively have a massive alphabet, so it should be very easy to perform the same idea, and I think it's clear that we can make the interval of lengths of words those repeats are avoided overlap the previous one. Don't forget to to decrease $\epsilon$ a bit.

$\endgroup$
0
$\begingroup$

I post a tentative answer to my own question 1.:

  1. Define $\kappa_{n,h}$ as the function which associates to $x\in[0,1]$ the number $\frac 1 {c_{x,h}}$, where $c_{x,h}$ is the maximum of the set of rational numbers $q$ such that the $n$-base expansion of $x$ has a $q$-power in its prefix of length $h$. The function $\kappa_{n,h}$ is constant on every cylinder set $[w]$ where $w\in\{1,\dots,n\}^h$, so it is Baire 1.

  2. $\lim_{h\to\infty}\kappa_{n,h}=\kappa_{n}$ pointwise, so that $\kappa_n$ is Baire 2.

  3. Define $\gamma_n=\max\{\kappa_2,\dots,\kappa_n\}$. Since passing to the max over a finite set preserves Baire class, $\kappa=\lim_{n\to\infty}\gamma_n$, $\kappa$ is Baire 3.

$\endgroup$
1
  • $\begingroup$ Update: $\kappa_n$ is upper semicontinuous and thus Baire 1 for every $n$, so that the previous argument shows that $\kappa$ is Baire 2. $\endgroup$ Mar 31 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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