# The critical exponent function

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: $$$$x\in[0,1]\;\longmapsto \;\kappa_n(x)=\frac{1}{c_n(x)}$$$$ 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: $$$$\kappa: x\in[0,1]\;\longmapsto\; \sup_{n\ge 2}{\kappa_n(x)}\in[0,1]$$$$

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.

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.

• Do you mean $\limsup_{\ell\to\infty}(\sup \{\alpha:\, \text{there is a factor of length$\ell$which appears as an$\alpha$-power}\})$? – Alessandro Della Corte Dec 8 '20 at 21:51
• 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. – Ronnie Pavlov Dec 11 '20 at 3:37
• 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. – Alessandro Della Corte Dec 12 '20 at 21:35

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.

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.

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