[Solved]: Regularity of unary languages with word lengths the sum of two resp. three squares

Problem Detail: 

I think about unary languages $L_k$, where $L_k$ is set of all words which length is the sum of $k$ squares. Formally: $$L_k=\{a^n\mid n=\sum_{i=1}^k {n_i}^2,\;\;n_i\in\mathbb{N_0}\;(1\le i\le k)\} $$ It is easy to show that $L_1=\{a^{n^2}\mid n\in\mathbb{N_0}\}$ is not regular (e.g. with Pumping-Lemma).
Further, we know that each natural number is the sum of four squares which implies that for $k\ge 4$ all languages $L_k$ are regular since $L_k=L(a^*)$.

Now, I am interested in the cases $k=2$ and $k=3$:

$L_2=\{a^{{n_1}^2+{n_2}^2}\mid n_1,n_2\in\mathbb{N_0}\}$, $L_3=\{a^{{n_1}^2+{n_2}^2+{n_3}^2}\mid n_1,n_2,n_3\in\mathbb{N_0}\}$.

Unfortunately, I am not able to show whether this languages are regular or not (even with the help of Legendre's three-square theorem or Fermat's theorem on sums of two squares).

I am pretty sure that at least $L_2$ is not regular but unhappily thinking is not a proof. Any help?

Asked By : Danny

Answered By : Yuval Filmus

Let's start with $L_2$. It is known that the upper density of integers which are the sum of two squares is 0. If $L_2$ were regular then it would be eventually periodic, and so, since its upper density is 0, finite. But we know that there are arbitrarily large integers in $L_2$, so that $L_2$ cannot be regular.

Regarding $L_3$, consider the words $w_k = 1^{4^k 7}$. I claim that for $k < \ell$, the words $w_k,w_\ell$ are inequivalent. Indeed, $w_k 1^{4^k 8} \notin L_3$ while $w_\ell 1^{4^k 7} \in L_3$. The Myhill–Nerode criterion then shows that $L_3$ is irregular.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42867

 Ask a Question

 Download Related Notes/Documents