# A regular language derived from another

This is similar to a previous question I asked, but doesn't seem aminable to the same technique. Given a regular language $$A$$, show the following language is regular: $$\{x|\exists y \; |y| = 2^{|x|} and \; xy \in A\}$$

I'm aware of the notion of regularity preserving functions, and that it would suffice to show that $$f(x) = 2^x$$ satisfies the property that for an ultimately periodic set $$U$$, $$f^{-1}(U) = \{m|f(m) \in U\}$$ is ultimately periodic. I'm struggling to $$f$$ has this property, but the book from which this comes implies a solution not using this is possible. It appears to be looking for a construction.

I can see that by repeated application of the idea behind the Pumping Lemma, if $$A$$ has DFL with $$k$$ states, that for any $$x$$ with $$|x| \geq k$$ then $$\exists y \; |y| = 2^{|x|} and \; xy \in A\ \implies \exists y \; |y| \leq k \; and \; xy \in A\$$

But this doesn't give anything going in the opposite direction, that shows that some suitably short $$y$$ guarantees the existence of a $$y$$ of the required length.

Any help in solving this, or hint at how to progress would be very helpful.

In order to show that $$f$$ is regularity preserving, it suffices to show that $$f^{-1}(U)$$ is eventually periodic for $$U = \{ n : n \equiv b \pmod{a} \}$$, where $$a$$ is a prime power (here we are using the Chinese remainder theorem and the fact that the eventually periodic sets are closed under intersection).
For $$f(n) = 2^n$$, we consider two cases:
• If $$a = 2^k$$ then $$f(n) \equiv 0 \pmod{a}$$ for large enough $$n$$.
• If $$a = p^k$$ for an odd prime $$p$$, then $$(2,a) = 1$$, and so we can think of $$2$$ as an element of the multiplicative group $$\mathbb{Z}_a^\times$$. In particular, $$2^n \bmod a$$ is periodic, the period being the order of $$2$$ in the group.