Is $A$ regular if $A^{2}$ is regular?

Question

If $A^2$ is regular, does it follow that $A$ is regular?

My attempt on a proof:

Yes, for contradiction assume that $A$ is not regular. Then $A^2 = A \cdot A$.

Since concatenation of two non-regular language is not regular $A^2$ cannot be regular. This contradicts our assumption. So $A$ is regular. So if $A^2$ is regular then $A$ is regular.

Is the proof correct?

Can we generalize this to $A^3$, $A^4$, etc...? And also if $A^*$ is regular then $A$ need not be regular?

Example: $A=\lbrace 1^{2^i} \mid i \geq 0\rbrace$ is not regular but $A^*$ is regular.

Answer 1

Consider Lagrange's four square theorem. It states that if $B = \{1^{n^2}| n \geq 0\}$ then $B^4 = \{1^n | n \geq 0\}$. If $B^2$ is regular, take $A = B$ else take $A = B^2$. Either way, this proves the existence of irregular $A$ such that $A^2$ is regular.

Answer 2

Here is an example of a non-computable language $A$ such that $A^2 = \Sigma^*$. Take any non-computable $K$ (represented as a set of numbers, e.g. the codes of Turing machines that halt), and define $$ A = \{ w \in \Sigma^* : |w| \neq 4^k \text{ for all } k \in K \}. $$ So $A$ contains all words other than ones of length $4^k$ for some $k \in K$. If $A$ were computable then you could compute $K$: given $k$, determine whether $0^{4^k}$ (that is, $4^k$ zeroes) is in $A$ or not. Since we assumed $K$ is not computable, $A$ must also be non-computable.

Claim: $A^2 = \Sigma^*$. Let $w$ be any word of length $n$. If $n$ is not a power of $4$, then $w \in A$ and the empty word is in $A$, so $w \in A^2$. If $n$ is a power of $4$ then $n/2$ is not a power of $4$. Write $w = xy$, where $|x| = |y| = n/2$. Both $x,y \in A$ so $w = xy \in A^2$.

Answer 3

Your proof still makes a huge jump (arguing that concatenation of non-regular languages is non-regular).

If the Goldbach conjecture is true, then the answer to the question is no: Consider the non-regular language $A=\{1^p: p\text{ is a prime}\}$. Then by the Goldbach conjecture, $A^2=\{1^{2k}: k>1\}$, which is regular.

This doesn't solve the question entirely, but it gives strong evidence that the answer is no (otherwise the Goldbach conjecture is false). However, the answer may be very hard to prove, if this is the only known example.

Answer 4

The claim is wrong.

Let $D$ be non-regular language which is "sparse": if $x \in D$ then any other $y\in D$ satisfies $|y| > 4|x|$ (or $|x|>4|y|$)^$\dagger$. It's not too difficult to see that many non-regular languages can be sparse.

Now define $A = \Sigma^* \setminus D$. From closure properties (complementation), $A$ must be non-regular.

However, $A^2 = \Sigma^*$ $\ \ \ $ (can you see why?)

^$\dagger$ _{I think $|y|>2|x|$ is enough, but may cause some nasty edge cases. $|y|>2|x|+2$ should be enough though, so let's take $|y|>4|x|$ to be on the safe side.}

Answer 5

Take any nonregular $X \subseteq {1}^\ast$ and define $A=\{1\} \cup \{1^{2x}:x \in \mathbb N\} \cup \{1^{2x+1}:1^x \in X\}$.

It is easy to see $A$ is nonregular, while $A^2=1^{\ast}$.

Answer 6

Let $U\subseteq \mathbb{N}$ be any undecidable set, let $I = \{2u+1\mid u\in U\}\cup\{0,2,4,\dots\}$ and let $L = \{a^i\mid i\in I\}$. $L$ is undecidable so it certainly isn't regular. But $L^2 = \{a^{2n}\mid n\in \mathbb{N}\} \cup \{a^n\mid n\geq \min\,I\}$, which is regular because its complement is finite.

Answer 7

Another example, from a question that was marked as a duplicate of this, is to consider the non-regular language $\{a^k\mid m\text{ is composite}\}$. Any even number $n\geq 8$ is the sum of $n-4$ and $4$, which are both composite; any odd number $n\geq 13$ is the sum of $n-9$ and $9$, which are both composite ($n-9=2m$ for some $m\geq 2$). Therefore, $A^2 = \{a^8,a^{10}\}\cup\{a^k\mid k\geq 12\}$, which is regular because it's co-finite (it's the complement of $\{\epsilon,a,aa,\dots,a^6,a^7,a^9,a^{11}\}$).