La regularidad de los idiomas unarios con longitudes de palabras la suma de dos resp. tres cuadrados

Pienso en los idiomas unarios , donde L k es un conjunto de todas las palabras cuya longitud es la suma de k cuadrados. Formalmente: L k = { a n ∣ n = k ∑ i = 1 n i 2$L_k$$L_k$$k$ Es fácil demostrar que L 1 = { a n 2 ∣ n ∈ N 0 } no es regular (p. Ej. Con Pumping-Lemma). Además, sabemos que cada número natural es la suma de cuatro cuadrados, lo que implica que para k ≥ 4 todos los idiomas L k son regulares ya que 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^*)$

Ahora, estoy interesado en los casos y k = 3 :$k=2$$k=3$

, L 3 = { a n 1 2 + n 2 2 + n 3 2 ∣ n 1 , n 2 , n 3 ∈ N 0 } .$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}\}$

Desafortunadamente, no puedo mostrar si estos idiomas son regulares o no (incluso con la ayuda del teorema de tres cuadrados de Legendre o el teorema de Fermat sobre sumas de dos cuadrados ).

Estoy bastante seguro de que al menos no es regular, pero lamentablemente pensar no es una prueba. ¿Alguna ayuda?$L_2$

Comencemos con . Se sabe que la densidad superior de los enteros que son la suma de dos cuadrados es 0. Si L 2 fuera regular, entonces sería eventualmente periódico y, por lo tanto, dado que su densidad superior es 0, finito. Pero sabemos que hay enteros arbitrariamente grandes en L 2 , por lo que L 2 no puede ser regular.$L_2$$L_2$$L_2$$L_2$

Con respecto a , considere las palabras w k = 1 4 k 7 . Afirmo que para k < ℓ , las palabras w k , w ℓ no son equivalentes. De hecho, w k 1 4 k 8 ∉ L 3 mientras que w ℓ 1 4 k 7 ∈ L 3 . El criterio de Myhill – Nerode muestra que L 3 es irregular.$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$

Supongamos que es regular. Entonces también lo es su complemento, que según el teorema de tres cuadrados de Legendre es { a n | n = 4 k ( 8 l + 7 ) , k , l ∈ N } . Según el teorema de Parikh , esto implicaría que el conjunto de longitudes S = { 4 k ( 8 l + 7 ) | k , $L_3$$\{a^n\ |\ n=4^k(8l+7), k,l\in\mathbb{N}\}$$S=\{4^k(8l+7)\ |\ k,l\in\mathbb{N}\}$es semi-lineal, es decir, una unión finita de conjuntos lineales S i = { a i + r b i | r ∈ N } .$\bigcup_{i=1}^NS_i$$S_i=\{a_i + rb_i\ |\ r\in\mathbb{N}\}$

Considere dos elementos con k 1 > k 2 , y sea r : = k 1 - k 2 . Si s 1 , s 2 están ambos en el mismo S i , entonces tambié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$ o 2 s 2 - s 1 (dependiendo de si s 1 < s 2 o s 1 > s 2 ). Pero$2s_1-s_2$$2s_2-s_1$$s_1<s_2$$s_1>s_2$

• , donde l ′ = 4 r - 1 ( 8 l 1 + 7 ) - $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$ no es regular.