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^nmid n=sum_{i=1}^k {n_i}^2,;;n_iinmathbb{N_0};(1le ile k)} $$ It is easy to show that $L_1={a^{n^2}mid ninmathbb{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 $kge 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_2inmathbb{N_0}}$, $L_3={a^{{n_1}^2+{n_2}^2+{n_3}^2}mid n_1,n_2,n_3inmathbb{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?
Further, we know that each natural number is the sum of four squares which implies that for $kge 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_2inmathbb{N_0}}$, $L_3={a^{{n_1}^2+{n_2}^2+{n_3}^2}mid n_1,n_2,n_3inmathbb{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
