2
$\begingroup$

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.

Thanks.

|cite|improve this question
$\endgroup$
  • 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 '19 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 '19 at 14:54
2
$\begingroup$

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?

|cite|improve this answer
$\endgroup$
  • $\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 '19 at 15:01
  • $\begingroup$ Right, this is also what I state above. $\endgroup$ – Yuval Filmus Aug 1 '19 at 15:04
  • $\begingroup$ @yuval-filmus What about asking your interesting question at cs.stackexchange.com ? $\endgroup$ – J.-E. Pin Sep 2 '19 at 13:50
  • $\begingroup$ @J.-E.Pin Good idea! Here it is. $\endgroup$ – Yuval Filmus Sep 2 '19 at 14:09
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I’m not sure this example is simpler than what the OP was suggested. $\endgroup$ – Yuval Filmus Aug 1 '19 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 '19 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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