Regularność języków jednoargumentowych o długości słowa suma dwóch resp. trzy kwadraty

Myślę o językach jednoargumentowych $L_k$, gdzie $L_k$ jest zbiorem wszystkich słów, których długość jest sumą $k$kwadraty. Formalnie:

$$L_k=\{a^n\mid n=\sum_{i=1}^k {n_i}^2,\;\;n_i\in\mathbb{N_0}\;(1\le i\le k)\}$$ Łatwo to pokazać $L_1=\{a^{n^2}\mid n\in\mathbb{N_0}\}$nie jest regularny (np. z Pumping-Lemma).
Ponadto wiemy, że każda liczba naturalna jest sumą czterech kwadratów, co implikuje, że dla$k\ge 4$ wszystkie języki $L_k$ są regularne od $L_k=L(a^*)$.

Teraz interesują mnie sprawy $k=2$ i $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}\}$.

Niestety nie jestem w stanie wykazać, czy te języki są prawidłowe, czy nie (nawet przy pomocy twierdzenia Legendre'a o trzech kwadratach lub twierdzenia Fermata o sumach dwóch kwadratów ).

Przynajmniej jestem tego pewien $L_2$nie jest regularne, ale nieszczęśliwe myślenie nie jest dowodem. Jakaś pomoc?

Zacznijmy $L_2$. Wiadomo, że górna gęstość liczb całkowitych, które są sumą dwóch kwadratów, wynosi 0. If$L_2$były regularne, to ostatecznie będzie okresowe, a zatem, ponieważ jego górna gęstość wynosi 0, skończona. Ale wiemy, że istnieją dowolnie duże liczby całkowite$L_2$, tak że $L_2$ nie może być regularny.

Jeżeli chodzi o $L_3$rozważ słowa $w_k = 1^{4^k 7}$. Twierdzę, że za$k < \ell$, słowa $w_k,w_\ell$są nierówne. W rzeczy samej,$w_k 1^{4^k 8} \notin L_3$ podczas $w_\ell 1^{4^k 7} \in L_3$. Kryterium Myhill – Nerode to pokazuje$L_3$ jest nieregularny.

Przypuszczać $L_3$jest regularny. Tak samo jest z jego dopełnieniem, którym jest twierdzenie Legendre'a o trzech kwadratach$\{a^n\ |\ n=4^k(8l+7), k,l\in\mathbb{N}\}$. Według twierdzenia Parikha oznaczałoby to, że zbiór długości$S=\{4^k(8l+7)\ |\ k,l\in\mathbb{N}\}$ jest półliniowy, tj. skończony związek $\bigcup_{i=1}^NS_i$ zbiorów liniowych $S_i=\{a_i + rb_i\ |\ r\in\mathbb{N}\}$.

Rozważ dwa elementy $s_1 = 4^{k_1}(8l_1+7), s_2 = 4^{k_2}(8l_2+7)\in S$ z $k_1>k_2$, i pozwól $r:=k_1-k_2$. Gdyby$s_1,s_2$ oba są w tym samym $S_i$, to też jest albo $2s_1-s_2$ lub $2s_2-s_1$ (w zależności od tego, czy $s_1<s_2$ lub $s_1>s_2$). Ale

• $2(4^{k_1}(8l_1+7))-(4^{k_2}(8l_2+7)) = 4^{k_2}(8l'-7)$, gdzie $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)$, gdzie $l'=2l_2-4^rl_1$.

Żadnego z nich nie ma $S$, więc $s_1,s_2$musieliby należeć do różnych członków związku. Ale to niemożliwe$S$ jest skończonym związkiem i istnieje nieskończenie wiele różnych $k$.

W związku z tym, $L_3$ nie jest regularny.