# In what bases is the language $a^n$ regular?

Given $$a\in\mathbb{N}$$, I wondered for what bases $$b$$ is the following language regular

$$\{a_ka_{k-1}\ldots a_0\mid \exists n\in\mathbb{N},\ a_0+a_1b+a_2b^2+\ldots+a_kb^k=a^n\}$$

I think it's regular only for bases which are a rational power of $$a$$, but I couldn't come up with any proof of that.

Is that correct? How can you prove it/find a counterexample?

• You can prove this by considering the number of words of length $\leq n$. Commented Mar 22, 2021 at 15:54
• @YuvalFilmus how? Can you elaborate more please? Commented Mar 22, 2021 at 15:58
• There is a modulus $m$ such that for $n \equiv a \pmod{m}$, the number of words of length $\leq n$ is of the form $\sum_i P_i(n) \lambda_i^n$, where $P_i$ are polynomials. In your case you can count the number of words of length $\leq n$ exactly, so with some work you might be able to show that your language isn't regular. Commented Mar 22, 2021 at 16:01
• There might be nicer proofs. Commented Mar 22, 2021 at 16:02
• You might be interested in link.springer.com/article/10.1007/BF01746527.
– orlp
Commented Mar 22, 2021 at 17:21

Putting orlp's comment and the Wikipedia article linked in another comment in an answer, this is a direct application of Cobham's Theorem. The theorem states that the representations of a set of natural numbers $$S$$ in two multiplicatively independent bases $$b_1$$ and $$b_2$$ form regular languages iff the set $$S$$ is a finite union of arithmetic progressions (alternatively, $$S$$ eventually ends up repeating).

Multiplicative independence of two numbers $$m$$ and $$n$$ means that there exist no integer powers $$p,q>0$$ such that $$m^p=n^q$$. From this, your assertion that these two bases $$m$$ and $$n$$ have to be rational powers of each other can easily be seen.

Your sequence does not end up repeating, so only its representations in multiplicatively dependent bases will be regular, of which one base trivially is $$a$$.

For proofs of Cobham's Theorem, see the section §Demonstrations ("Proofs") on the French Wikipedia and its linked articles, of which a very short and recent proof is by Krebs.