3
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ You can prove this by considering the number of words of length $\leq n$. $\endgroup$ Mar 22, 2021 at 15:54
  • $\begingroup$ @YuvalFilmus how? Can you elaborate more please? $\endgroup$ Mar 22, 2021 at 15:58
  • $\begingroup$ 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. $\endgroup$ Mar 22, 2021 at 16:01
  • $\begingroup$ There might be nicer proofs. $\endgroup$ Mar 22, 2021 at 16:02
  • 3
    $\begingroup$ You might be interested in link.springer.com/article/10.1007/BF01746527. $\endgroup$
    – orlp
    Mar 22, 2021 at 17:21

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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