As title.

I consider finding a specific L to fulfill the condition stated to prove the statement, however, I have no luck in finding one.

A senior gave me a hint that Lagrange's four square theorem might help, but I don't see how I can utilize it.


  • 5
    $\begingroup$ That's a pretty direct hint. What are there four of in your problem statement? In a similar vein, you can use Helfgott's theorem on the weak Golbach conjecture. $\endgroup$
    – Yonatan N
    Aug 1, 2019 at 5:15
  • $\begingroup$ You utilise it by finding L which is irregular because of a restriction to the length, but adding several has no difficult restrictions. Is a^k where k is square a regular language? $\endgroup$
    – gnasher729
    Aug 1, 2019 at 14:54

2 Answers 2


Let us prove a more general result:

For each $m \geq 2$ there is a language $L$ such that $L,L^2,\ldots,L^{m-1}$ are not regular but $L^m$ is regular.

The language we construct will be unary, that is, of the form $L = \{a^n : n \in S\}$, where $S \subseteq \mathbb{N}$ is $$ S = \{ km : k \geq 0 \} \cup \{ m^k + 1 : k \geq 1 \}. $$ Let $1 \leq p \leq m-1$, and consider $p \cdot S$, i.e., the set of all sums of $p$ elements from $S$. Since all elements in $S$ are equivalent to either $0$ or $1$ modulo $m$, if $a \in S$ is equivalent to $p$ modulo $m$ then it must have the form $$a = m^{k_1} + 1 + \cdots + m^{k_p} + 1. $$ The base $m$ representation of $a$ thus has at most $p+1$ non-zero digits (it could have fewer if some of the $k_i$ are equal). It is easy to check that a vanishing fraction of numbers have this property.

Let $L_{m,p} = \{ a^{km+p} : k \geq 0\}$. It follows that $L' = L^p \cap L_{m,p}$ is an infinite language with vanishing density, and so it cannot be regular (since regular unary languages are eventually periodic, and so if they have vanishing density they must be finite). Since $L_{m,p}$ is regular, it follows that $L^p$ isn't regular.

In contrast, $m \cdot S$ is cofinite — it contains all integers which are at least $m^2-1$ — and so $L^m$ is regular.

The language constructed above has the "regularity profile" $\{k : k \geq m\}$. This is the set of powers $k \geq 1$ such that $L^k$ is regular ($L^0$ is always regular). This prompts the following question:

What regularity profiles are possible?

Any regularity profile is closed under addition, but are there any other constraints?

  • $\begingroup$ I took the trivial case m=2, and if you take L=a^n, n even or n=2^k+1, then L^2, L^3, L^4 etc. are all regular. Or L=a^k, k even or prime. $\endgroup$
    – gnasher729
    Aug 1, 2019 at 15:01
  • $\begingroup$ Right, this is also what I state above. $\endgroup$ Aug 1, 2019 at 15:04
  • $\begingroup$ @yuval-filmus What about asking your interesting question at cs.stackexchange.com ? $\endgroup$
    – J.-E. Pin
    Sep 2, 2019 at 13:50
  • $\begingroup$ @J.-E.Pin Good idea! Here it is. $\endgroup$ Sep 2, 2019 at 14:09

Unless you must deal with unary regular languages, there is no need for complex math ...

Just pick an irregular language that is able to "capture and mask" the concatenation of itself; e.g. over $\Sigma = \{a,b \}$

$L = \{ (a^ib^j) (a^n b^n) \mid i, j \geq 1, n \geq 1\} \; \cup \; $ $ \{ (a^ib^j)^k \mid i, j \geq 1, k \neq 2\}$

$LLLL$ is equal to ....

  • $\begingroup$ I’m not sure this example is simpler than what the OP was suggested. $\endgroup$ Aug 1, 2019 at 15:14
  • $\begingroup$ @YuvalFilmus There is no math behind it but only a "masking effect" :-), this one is simpler $L = \{ a^i\; b\; a^p \;b \mid p \in \text{Prime} \} \cup \{ (a^i\; b)^k \mid k \neq 2 \}$ but "uses" primes. $\endgroup$
    – Vor
    Aug 1, 2019 at 17:00

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.