Регулярность унарных языков с длинами слов сумма двух соотв. три квадрата

9

Я думаю об унарных языках Lk , где Lk - множество всех слов, длина которых равна сумме k квадратов. Формально: Легко показать, что L 1 = { a n 2n N 0 } не является регулярным (например, с леммой Пампинга). Кроме того, мы знаем, что каждое натуральное число является суммой четырех квадратов, из чего следует, что при k 4 все языки L k являются регулярными, поскольку L k = L ( a ) .

Lk={ann=i=1kni2,niN0(1ik)}
L1={an2nN0}
k4LkLk=L(a)

Теперь меня интересуют случаи и k = 3 :k=2k=3

, L 3 = { п 1 2 + п 2 2 + п 3 2 | п 1 , п 2 , п 3N 0 } .L2={an12+n22n1,n2N0}L3={an12+n22+n32n1,n2,n3N0}

К сожалению, я не могу показать, являются ли эти языки регулярными или нет (даже с помощью теоремы Лежандра о трех квадратах или теоремы Ферма о суммах двух квадратов ).

Я вполне уверен, что по крайней мере не является регулярным, но несчастливое мышление не является доказательством. Любая помощь?L2

Дэнни
источник
Возможно, наши справочные вопросы ( обычные , не регулярные ) имеют полезные ссылки .
Рафаэль

Ответы:

8

Давайте начнем с . Известно, что верхняя плотность целых чисел, которые являются суммой двух квадратов, равна 0. Если бы L 2 был регулярным, то он был бы в конечном итоге периодическим, и поэтому, поскольку его верхняя плотность равна 0, он конечен. Но мы знаем, что в L 2 есть сколь угодно большие целые числа , поэтому L 2 не может быть регулярным.L2L2L2L2

Что касается , рассмотрим слова w k = 1 4 k 7 . Я утверждаю , что для к < л , слова ш к , ш л неэквивалентны. Действительно, w k 1 4 k 8L 3, а w 1 4 k 7L 3 . Тогда критерий Майхилла-Нерода показывает, что L 3 нерегулярно.L3wk=14k7k<wk,wwk14k8L3w14k7L3L3

Юваль Фильмус
источник
5

Предположим, что регулярно. Тогда его дополнение, которое по теореме Лежандра о трех квадратах равно { a n | n = 4 k ( 8 l + 7 ) , k , l N } . По теореме Париха это означало бы, что множество длин S = { 4 k ( 8 l + 7 ) | k , l N }L3{an | n=4k(8l+7),k,lN}S={4k(8l+7) | k,lN}является полу-линейным, то есть конечное объединение линейных множеств S я = { а я + г Ь I | r N } .i=1NSiSi={ai+rbi | rN}

Рассмотрим два элемента при k 1 > k 2 , и пусть r : = k 1 - k 2 . Если s 1 , s 2 оба находятся в одном и том же S i , то либоs1=4k1(8l1+7),s2=4k2(8l2+7)Sk1>k2r:=k1k2s1,s2Si или 2 s 2 - s 1 (в зависимости от того, s 1 < s 2 или s 1 > s 2 ). Но2s1s22s2s1s1<s2s1>s2

  • , где l = 4 r - 1 ( 8 l 1 + 7 ) - l 2 ,2(4k1(8l1+7))(4k2(8l2+7))=4k2(8l7)l=4r1(8l1+7)l2
  • , где l = 2 l 2 - 4 г л 1 .2(4k2(8l2+7))(4k1(8l1+7))=4k2(8l74r+14)l=2l24rl1

Ни один из них не находится в , поэтому s 1 , s 2 должны быть в разных членах объединения. Но это невозможно, так как S - конечное объединение и существует бесконечно много разных k .Ss1,s2Sk

Следовательно, не является регулярным.L3

Клаус Дрегер
источник