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

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.

• The first proof make a huge jump. What is your proof that $A$ is not regular implies $A^2$ is not regular? Proving that properly might lead you to intuition to help answer the rest of the question, if indeed it is true. Feb 16, 2013 at 8:09
• @DaveClarke Edited the proof. Feb 16, 2013 at 8:22
• How you manage to spell "Am i Correct?" that way is very intriguing. As a general advice: when hundreds of people read what you wrote, general decency demands that you pay attention to how you write... ;-) Feb 16, 2013 at 8:49
• @AndrejBauer The OP could be someone who is not a native speaker of English, and who might not have yet had the opportunity of getting instruction on formal English. This is no reason to discourage anyone, though it could be helpful to correct them. Feb 16, 2013 at 20:33

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.

• I don't understand this proof; could you elaborate a little? Feb 16, 2013 at 13:52
• Explaining this (beautiful) proof: We have that $B\notin REG$, and that $B^4\in REG$. Observe that $B^4=(B^2)^2$. Now, if $B^2\in REG$, then by taking $A=B$ we have a counterexample, and if $B^2\notin REG$ then by taking $A=B^2$ we have a counterexample. Feb 16, 2013 at 14:10
• Absolutely beautiful. Feb 16, 2013 at 14:56
• @YuvalFilmus, indeed, but I didn't have a proof and I didn't want to leave any doubt. Now I seem to have found one. "A number $n$ is a sum of two squares if and only if all prime factors of the form $4k+3$ have even exponent in the prime factorization of $n$." Let $n$ be the pumping length. Consider $w = (n!)^2$. Let $p$ be a prime of the form $4k+3$ and let $m$ be the length we choose to pump. Then, $w + (p-1)\frac{w}{m}\cdot m = pw$ has an odd exponent on $p$ and is thus not in $B^2$. Feb 16, 2013 at 20:04
• @JonasKölker, agree. Feb 20, 2014 at 15:23

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$.

• For beginners, a proof sketch for "$A$ undecidable" may be in order. Also, a small hurdle may be that you use $K$ as a formal language and as a set of numbers (which is fair, assuming suitable semantics for $K$, but maybe unfamiliar). Otherwise, very nice idea.
– Raphael
Feb 16, 2013 at 22:08

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.

• What can we conclude about the question? Feb 16, 2013 at 8:33
• Assuming the Goldbach conjecture -if $A^2$ is regular, than $A$ may still be non-regular. So: proving that the answer is "yes" would mean that the Goldbach conjecture is false (unlikely). Feb 16, 2013 at 8:36
• In the presence of "real" proofs, I don't think using an unproven conjecture is fair. Maybe the connection is interesting for some?
– Raphael
Feb 17, 2013 at 9:56
• Indeed, after the following answers, this is redundant. However, you can see a nice mathematical development here: an answer based on a well known conjecture, then a related answer (using Lagrange's theorem), which is based on a similar idea (decomposing a number to a sum). Feb 17, 2013 at 10:16
• In fact if you use primes and semiprimes, you can use Chen's theorem. Feb 17, 2013 at 19:42

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.

• I like how this question is getting increasingly more trivial proofs. Your idea of sparseness could be further simplified to a requirement that $1 \in A$ and $1^k \notin A \implies 1^{k-1} \in A$. Feb 16, 2013 at 20:19

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}$.

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.

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}\}$$).