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

9

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

L.k={zann=ja=1knja2),njaN.0(1jak)}
Łatwo to pokazać L.1={zan2)nN.0}nie jest regularny (np. z Pumping-Lemma).
Ponadto wiemy, że każda liczba naturalna jest sumą czterech kwadratów, co implikuje, że dlak4 wszystkie języki L.k są regularne od L.k=L.(za).

Teraz interesują mnie sprawy k=2) i k=3):

L2={an12+n22n1,n2N0}, L3={an12+n22+n32n1,n2,n3N0}.

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 L2nie jest regularne, ale nieszczęśliwe myślenie nie jest dowodem. Jakaś pomoc?

Danny
źródło
Być może nasze pytania referencyjne ( zwykłe , nieregularne ) mają przydatne wskazówki.
Raphael

Odpowiedzi:

8

Zacznijmy L2. Wiadomo, że górna gęstość liczb całkowitych, które są sumą dwóch kwadratów, wynosi 0. IfL2był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łkowiteL2, tak że L2 nie może być regularny.

Jeżeli chodzi o L3)rozważ słowa wk=14k7. Twierdzę, że zak<, słowa wk,wsą nierówne. W rzeczy samej,wk14k8L.3) podczas w14k7L.3). Kryterium Myhill – Nerode to pokazujeL.3) jest nieregularny.

Yuval Filmus
źródło
5

Przypuszczać L.3)jest regularny. Tak samo jest z jego dopełnieniem, którym jest twierdzenie Legendre'a o trzech kwadratach{an | n=4k(8l+7),k,lN}. Według twierdzenia Parikha oznaczałoby to, że zbiór długościS={4k(8l+7) | k,lN} jest półliniowy, tj. skończony związek i=1NSi zbiorów liniowych Si={ai+rbi | rN}.

Rozważ dwa elementy s1=4k1(8l1+7),s2=4k2(8l2+7)S z k1>k2, i pozwól r:=k1k2. Gdybys1,s2 oba są w tym samym Si, to też jest albo 2s1s2 lub 2s2s1 (w zależności od tego, czy s1<s2 lub s1>s2). Ale

  • 2(4k1(8l1+7))(4k2(8l2+7))=4k2(8l7), gdzie l=4r1(8l1+7)l2,
  • 2(4k2(8l2+7))(4k1(8l1+7))=4k2(8l74r+14), gdzie l=2l24rl1.

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

W związku z tym, L3 nie jest regularny.

Klaus Draeger
źródło