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$

3 Answers 3

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, 2020 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, 2020 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, 2020 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, 2021 at 11:52

Your Answer

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