Words of the form $(a^n b)^n$ in a context-free language

Question

Question

For a language $L \subset \{a,b\}^*$, denote $N(L) = \{ n \geq 0 \mid (a^n b)^n \in L \}$. If $L$ is context-free, is $N(L)$ necessarily semilinear, meaning that $n \in N(L) \iff n+p \in N(L)$ for some constant $p \geq 1$ and large enough $n$?

Thoughts

If $L$ is regular, then $N(L)$ is semilinear. This can be shown e.g. by noticing that the syntactic congruence class of $a^n$ depends only on $n$ modulo some constant, and within each of these finitely many congruence classes, the class of $(a^n b)^k$ depends only on $k$ modulo another constant.

If $L$ is context-free, my first instinct was to repeatedly use Ogden's lemma or its generalizations to pump $(a^n b)^n$ into $(a^{n+k} b)^n$ for some fixed $k \geq 1$, and then try to pump the outer $n$. But we can't always pump only the $a$-parts: the grammar $$ S \to ab \mid aSa^+b $$ produces the language $L \subset (a^+b)^+$ where the $b$-symbols match the $a$-symbols of the first $a$-part, so if you pump away some of those $a$s, you have to remove some $b$s as well. Even if you manage to pump only $a$-runs, you may have to pump them by different amounts: the grammar $$ S \to a^*b S \mid S a^*b \mid MNb \\ M \to aaMa \mid b \\ N \to aNaa \mid b $$ produces $L \subset (a^* b)^+$ where some three consecutive $a$-runs $a^i$, $a^j$, $a^k$ satisfy $2j = i+k$. Pumping the middle run requires us to pump one of the others by twice that amount, or all three at the same time. Of course, all sorts of mixes of these examples are possible.

Parikh's theorem seems useless, since $N(L)$ doesn't tell us much about the Parikh vectors of $L$.

Answer 1

There exists a context-free language $M$, such that $N(M)$ is not semilinear. The construction is a modification of the construction I shared in the comments.

Indeed, consider the language $K := \{ a^{2i} ba^i \mid i \geqslant 1\}$. Obviously, $K$ is context-free. Therefore, $L := K^{+} (aa)^{*} ab$ also is. Finally, $M := L^{+}$ is also a context-free language. I claim that $N(M)$ is not semilinear.

Indeed, let's consider an arbitrary word of the type $(a^m b)^n$ from the language $L$ (here, $m$ and $n$ don't have to be equal). It necessarily has $m \geqslant 1$ and $n \geqslant 2$.

An arbitrary word from $L$ looks like $w_1 w_2 \ldots w_d a^{2t + 1} b$, where $d \geqslant 1$, $t \geqslant 0$ and all the words $w_i$ are in the language $K$. Hence, if the word $(a^m b)^n$ is in $L$, then $w_1 = a^m b a^{m/2}$ (and $m$ has to be even), $w_2 = a^{m/2} ba^{m/4}$, $w_3 = a^{3m/4} ba^{3m/8}$, $\ldots$, $w_d = a^{m \cdot p_d / 2^{d-1}} b a^{m \cdot p_d / 2^d}$. Here, $p_1$, $p_2$, $\ldots$, $p_d$ are the numerators of the fractions that appear in the definitions of $w_i$. For example, $p_1 = 1, p_2 = 1, p_3 = 3, p_4 = 5, p_5 = 11$, et cetera. It can be proven via induction that all $p_i$'s are odd. Moreover, $p_i / 2^{i-1}$ and $p_i / 2^i$ are successive binary approximations of $2/3$ and $1/3$ respectively (but this is not important here).

It is not hard to see that $n = d + 1$. Indeed, each $w_i$ contains exactly one letter $b$ and so does the word $a^{2t+1}b$. Moreover, $m$ is divisible by $2^d$ (because $p_d$ is odd). Finally, the last block of $a$-s contains exactly $(2t + 1) + (m \cdot p_d / 2^d)$ letters. On the other hand, it should contain $m$ letters. Therefore, $m$ can't be divisible by $2^{d+1}$: otherwise, the sum of an odd number $2t+1$ and an even number $m \cdot p_d / 2^d$ would be an even number $m$.

Hence, if a word $(a^m b)^n$ is in $L$, then $m \geqslant 1$, $n \geqslant 2$ and $m$ is exactly divisible by $2^{n-1}$ (in the sense that $m$ is divisible by $2^{n-1}$, but not by $2^n$). Moreover, the converse statement is true as well: if $m \geqslant 1$, $n \geqslant 2$ and $m$ is exactly divisible by $2^{n-1}$, then $(a^m b)^n \in L$.

Finally, consider a word of the type $(a^m b)^m \in M$. Suppose that $m$ is exactly divisible by $2^{n-1}$ for some $n \geqslant 2$. Recall that $M$ is a concatenation of several words from $L$. All these words should be of form $(a^m b)^{*}$ (and $(a^m b)^n$ is the only word of this form in the language $L$). Therefore, if $(a^m b)^m \in M$, then $m$ is divisible by $n$. Similarly to the above paragraph, the converse implication is also true.

All in all, $m \in N(M)$ if and only if one of the following conditions is true:

1. $m \equiv 2 \pmod 4$ and $m$ is divisible by $1 + 1 = 2$ (the second condition is redundant).
2. $m \equiv 4 \pmod 8$ and $m$ is divisible by $2 + 1 = 3$.
3. $m \equiv 8 \pmod {16}$ and $m$ is divisble by $3 + 1 = 4$ (the second condition is redundant).
4. $m \equiv 16 \pmod {32}$ and $m$ is divisible by $4 + 1 = 5$.
5. $m \equiv 32 \pmod {64}$ and $m$ is divisible by $5 + 1 = 6$ (the second condition is not completely redundant, but $6$ can be replaced with $3$).
6. Et cetera.

Intuitively, $N(M)$ doesn't look like a semilinear set at all.

Formally speaking, suppose that $N(M)$ is periodic with a period $\ell$. Then, $\ell$ can't be odd, as all numbers in $N(M)$ are even. Moreover, the case when $\ell \equiv 2 \pmod 4$ is also impossible. Indeed, we can pick a large enough number $q$ that is exactly divisible by $4$, but is not divisible by $3$. Then, $q \notin N(M)$, but $q - \ell \equiv 2 \pmod 4$, implying $q - \ell \in N(M)$.

Similarly, the case $\ell \equiv 4 \pmod 8$ is also impossible. Indeed, pick a large enough number $q$, such that $q \equiv 16 \pmod {32}$, $q \not\equiv 0 \pmod 5$ and $q \equiv \ell \pmod 3$ (this is possible by the Chinese remainder theorem). Then, $q \notin N(M)$. But, on the other hand, $q - \ell \equiv 4 \pmod 8$ and $q - \ell$ is divisible by $3$, implying $q - \ell \in N(M)$.

We can proceed in the same fashion: if $\ell \equiv 2^u \pmod {2^{u+1}}$, then we need to consider some large enough $q$, such that $q \notin N(M)$, but $q - \ell \in N(M)$. If $u$ is odd, then some $q$ satisfying $q \equiv 2^{u+1} \pmod {2^{u+2}}$ will do. If $u$ is even, then we can pick a $q$ with $q \equiv 2^{u+2} \pmod {2^{u+3}}$.

We can make the argument above slightly simpler by replacing $K^{+}$ in the definition of $L$ with $(KK)^+$, forcing $d$ to be even and $n = d + 1$ to be odd.