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?

  • $\begingroup$ Maybe our reference questions (regular, not regular) have useful pointers. $\endgroup$
    – Raphael
    Commented May 22, 2015 at 13:04

2 Answers 2


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.


Suppose $L_3$ is regular. Then so is its complement, which by Legendre's three-square theorem is $\{a^n\ |\ n=4^k(8l+7), k,l\in\mathbb{N}\}$. By Parikh's theorem, this would imply that the set of lengths $S=\{4^k(8l+7)\ |\ k,l\in\mathbb{N}\}$ is semi-linear, i.e. a finite union $\bigcup_{i=1}^NS_i$ of linear sets $S_i=\{a_i + rb_i\ |\ r\in\mathbb{N}\}$.

Consider two elements $s_1 = 4^{k_1}(8l_1+7), s_2 = 4^{k_2}(8l_2+7)\in S$ with $k_1>k_2$, and let $r:=k_1-k_2$. If $s_1,s_2$ are both in the same $S_i$, then so is either $2s_1-s_2$ or $2s_2-s_1$ (depending on whether $s_1<s_2$ or $s_1>s_2$). But

  • $2(4^{k_1}(8l_1+7))-(4^{k_2}(8l_2+7)) = 4^{k_2}(8l'-7)$, where $l'=4^{r-1}(8l_1+7)-l_2$,
  • $2(4^{k_2}(8l_2+7))-(4^{k_1}(8l_1+7)) = 4^{k_2}(8l'-7*4^r+14)$, where $l'=2l_2-4^rl_1$.

Neither of these are in $S$, so $s_1,s_2$ would have to be in different members of the union. But this is impossible, since $S$ is a finite union, and there are infinitely many different $k$.

Therefore, $L_3$ is not regular.


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.