A regularidade de idiomas unários com palavras possui a soma de dois resp. três quadrados

Penso nas línguas unárias , onde é um conjunto de todas as palavras cujo comprimento é a soma dos quadrados. Formalmente: É fácil mostrar que não é regular (por exemplo, com Pumping-Lemma). Além disso, sabemos que cada número natural é a soma de quatro quadrados, o que implica que para todas as línguas são regulares desde .L k k L k = { a n ∣ n = k ∑ i = 1 n i 2$L_k$$L_k$$k$L 1 = { a n 2 ∣ n ∈ N 0 } k ≥ 4 L k L k = L ( a ∗

$$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_k=L(a^*)$

Agora, estou interessado nos casos e :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}\}$

Infelizmente, não sou capaz de mostrar se essas línguas são regulares ou não (mesmo com a ajuda do teorema dos três quadrados de Legendre ou do teorema de Fermat em somas de dois quadrados ).

Tenho certeza de que pelo menos não é regular, mas infelizmente o pensamento não é uma prova. Qualquer ajuda?$L_2$

Vamos começar com . Sabe-se que a densidade superior de números inteiros, que é a soma de dois quadrados, é 0. Se fosse regular, seria eventualmente periódica e, portanto, uma vez que sua densidade superior é 0, finita. Mas sabemos que existem inteiros arbitrariamente grandes em , de modo que não pode ser regular.$L_2$$L_2$$L_2$$L_2$

Em relação a , considere as palavras . que para , as palavras são diferentes. De fato, enquanto . O critério Myhill – Nerode mostra então que é irregular.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$

Suponha que seja regular. O mesmo vale para o complemento, que pelo teorema de três quadrados de Legendre é . Pelo teorema de Parikh , isso implicaria que o conjunto de comprimentos é semi-linear, isto é, uma união finita dos conjuntos lineares .$L_3$$\{a^n\ |\ n=4^k(8l+7), k,l\in\mathbb{N}\}$$S=\{4^k(8l+7)\ |\ k,l\in\mathbb{N}\}$$\bigcup_{i=1}^NS_i$$S_i=\{a_i + rb_i\ |\ r\in\mathbb{N}\}$

Considere dois elementos com e deixe . Se estiverem no mesmo , também será ou (dependendo de ou ). Mas$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)$ , onde ,$l'=4^{r-1}(8l_1+7)-l_2$
• l ′ = 2 l 2 - 4 r l $2(4^{k_2}(8l_2+7))-(4^{k_1}(8l_1+7)) = 4^{k_2}(8l'-7*4^r+14)$ , onde .$l'=2l_2-4^rl_1$

Nenhum deles está em , então teria que estar em diferentes membros do sindicato. Mas isso é impossível, pois é uma união finita e existem infinitamente muitos diferentes .s 1 , s 2 S $S$$s_1,s_2$$S$$k$

Portanto, não é regular.$L_3$