Regelmäßigkeit von unären Sprachen mit Wortlängen die Summe von zwei resp. drei Quadrate

Ich denke an unäre Sprachen , wobei aus allen Wörtern besteht, deren Länge die Summe von Quadraten ist. Formal: Es ist leicht zu zeigen, dass nicht regulär ist (z. B. mit Pumping-Lemma). Ferner wissen wir, dass jede natürliche Zahl die Summe von vier Quadraten ist, was impliziert, dass für alle Sprachen regulär sind, da .L k k L k = { a n ∣ n $L_k$$L_k$$k$L 1 = { a n 2 | n ∈ N 0 } k ≥

$$L_k=\{a^n\mid n=\sum_{i=1}^k {n_i}^2,\;\;n_i\in\mathbb{N_0}\;(1\le i\le k)\}$$ $L_1=\{a^{n^2}\mid n\in\mathbb{N_0}\}$
$k\ge 4$L k = L ( a *$L_k$$L_k=L(a^*)$

Jetzt interessieren mich die Fälle und :k = $k=2$$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}\}$

Leider kann ich nicht zeigen, ob diese Sprachen regulär sind oder nicht (selbst mit Hilfe von Legendres Drei-Quadrat-Theorem oder Fermats Theorem auf Summen von zwei Quadraten ).

Ich bin mir ziemlich sicher, dass zumindest nicht regelmäßig ist, aber unglückliches Denken ist kein Beweis. Irgendeine Hilfe?$L_2$

Beginnen wir mit . Es ist bekannt, dass die obere Dichte von ganzen Zahlen, die die Summe zweier Quadrate sind, 0 ist. Wenn regulär wäre, wäre es schließlich periodisch und daher, da seine obere Dichte 0 ist, endlich. Wir wissen jedoch, dass es in beliebig große ganze Zahlen , so dass nicht regulär sein kann.$L_2$L 2 L $L_2$$L_2$$L_2$

Betrachten Sie in Bezug auf die Wörter . Ich behaupte, dass für die Wörter sind. In der Tat ist während . Das Myhill-Nerode-Kriterium zeigt dann, dass unregelmäßig ist.w k = 1 4 k 7 k < ℓ w k , w ℓ w k 1 4 k 8 ∉ L 3 w ℓ 1 4 k 7 ∈ L 3 L $L_3$$w_k = 1^{4^k 7}$$k < \ell$$w_k,w_\ell$$w_k 1^{4^k 8} \notin L_3$$w_\ell 1^{4^k 7} \in L_3$$L_3$

Angenommen, ist regulär. Dann , so ist sein Komplement, die von Legendre ist drei Quadrate - Satz ist { a n | n = 4 k ( 8 l + 7 ) , k , l ≤ N } . Nach dem Satz von Parikh würde dies bedeuten, dass die Menge der Längen S = { 4 k ( 8 l + 7 ) | ist k , l ∈ N$L_3$$\{a^n\ |\ n=4^k(8l+7), k,l\in\mathbb{N}\}$$S=\{4^k(8l+7)\ |\ k,l\in\mathbb{N}\}$ist , dh eine endliche Vereinigung ⋃ N i = 1 S i linearer Mengen S i = { a i + r b i | r ∈ N } .$\bigcup_{i=1}^NS_i$$S_i=\{a_i + rb_i\ |\ r\in\mathbb{N}\}$

$s_1 = 4^{k_1}(8l_1+7), s_2 = 4^{k_2}(8l_2+7)\in S$$k_1>k_2$$r:=k_1-k_2$$s_1,s_2$$S_i$$2s_1-s_2$$2s_2-s_1$$s_1<s_2$$s_1>s_2$

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

$S$$s_1,s_2$$S$$k$

$L_3$