Рекуррентность в конечном поле

[Ian]

У меня есть последовательность с периодом 124 , и это ее наименьший период, вот он:

Код: Выбрать все

1,0,3,0,4,3,4,2,2,2,0,2,3,1,1,3,1,2,4,3,2,0,3,2,3,2,3,0,3,1,2,0,3,4,3,1,4,1,2,2,2,3,2,4,0,0,4,0,2,1,4,2,3,4,2,4 ,2,4,3,4,0,2,3,4,1,4,0,1,0,2,2,2,4,2,1,3,3,1,3,2,0,1,2,4,1,2,1,2,1,4,1,3,2,4,1,0,1,3,0,3,2,2,2,1,2,0,4,4,0,4,2,3,0,2 ,1,0,2,0,2,0,1,0,4,2

составленная из остатков по модулю 5.
Естественно, она удовлетворяет рекуррентному уравнению 124-го порядка
[math]x_n=x_{n-124}(mod5) Как мне узнать, не удовлетворяет ли она уравнению меньшего порядка m, вида
[math]x_n=\sum_{k=1}^ma_kx_{n-k}(mod5), где [math]a_k=0,1,2,3,4.
Понятно, что тогда многочлен [math]x^m-\sum_{k=1}^ma_kx^{m-k} делит многочлен [math]x^{124}-1, это все в смысле умножения по модулю 5, но это не помогло найти

[zykov]

[math]\left( x-1\right) \, \left( x+1\right) \, \left( {{x}^{2}}+1\right) \, \left( {{x}^{30}}-{{x}^{29}}+{{x}^{28}}-{{x}^{27}}+{{x}^{26}}-{{x}^{25}}+{{x}^{24}}-{{x}^{23}}+{{x}^{22}}-{{x}^{21}}+{{x}^{20}}-{{x}^{19}}+{{x}^{18}}-{{x}^{17}}+{{x}^{16}}-{{x}^{15}}+{{x}^{14}}-{{x}^{13}}+{{x}^{12}}-{{x}^{11}}+{{x}^{10}}-{{x}^{9}}+{{x}^{8}}-{{x}^{7}}+{{x}^{6}}-{{x}^{5}}+{{x}^{4}}-{{x}^{3}}+{{x}^{2}}-x+1\right) \, \left( {{x}^{30}}+{{x}^{29}}+{{x}^{28}}+{{x}^{27}}+{{x}^{26}}+{{x}^{25}}+{{x}^{24}}+{{x}^{23}}+{{x}^{22}}+{{x}^{21}}+{{x}^{20}}+{{x}^{19}}+{{x}^{18}}+{{x}^{17}}+{{x}^{16}}+{{x}^{15}}+{{x}^{14}}+{{x}^{13}}+{{x}^{12}}+{{x}^{11}}+{{x}^{10}}+{{x}^{9}}+{{x}^{8}}+{{x}^{7}}+{{x}^{6}}+{{x}^{5}}+{{x}^{4}}+{{x}^{3}}+{{x}^{2}}+x+1\right) \, \left( {{x}^{60}}-{{x}^{58}}+{{x}^{56}}-{{x}^{54}}+{{x}^{52}}-{{x}^{50}}+{{x}^{48}}-{{x}^{46}}+{{x}^{44}}-{{x}^{42}}+{{x}^{40}}-{{x}^{38}}+{{x}^{36}}-{{x}^{34}}+{{x}^{32}}-{{x}^{30}}+{{x}^{28}}-{{x}^{26}}+{{x}^{24}}-{{x}^{22}}+{{x}^{20}}-{{x}^{18}}+{{x}^{16}}-{{x}^{14}}+{{x}^{12}}-{{x}^{10}}+{{x}^{8}}-{{x}^{6}}+{{x}^{4}}-{{x}^{2}}+1\right)
Это делители над полем действительных.
Надо проверить, подойдёт ли кто из них.
Над полем по модулю 5 возможно кто-то из них ещё раскладывается.

[zykov]

Посмотрел эти 6 полиномов. Для каждого есть ненулевой пример (если не ошибся).
Значит они не подходят и значит ниже 124 степени нет.

[Ian]

Над полем по модулю 5 возможно кто-то из них ещё раскладывается.

Спасибо. Конечно многие раскладываются [math]\left( {{x}^{2}}+1\right) =(x+2)(x+3)

а в чем была проверка дальше? Надо же проверить может ли предполагаемый делитель степени m дать , после исходных m членов опубликованной последовательности, все остальные члены опубликованной последовательности.

[zykov]

Например [math]x-1 и [math]x+1 уже не подходят для начальной подпоследовательности "1, 0".
[math]x^2+1 не подходит для "1, 0, 3".
Аналогично, два многочлена 30 порядка не подошли для первых 31 элементов и один многочлен 60 порядка не подошел для первых 61 элемента.

Т.е. он не то что все не дал, он даже самый первый не дал.

[Ian]

действительно, что-то с данными, ожидалась рекуррентность невысокого порядка, не более 10го
Спасибо!

[zykov]

Наверно ещё может оказаться, что какое-то произведение некоторых из этих делителей подойдёт...

[zykov]

Source of the post Конечно многие раскладываются [math](x^2+1)=(x+2)(x+3)

Большие (порядка 30 и 60) тоже наверно так можно разложить. Так что количество возможных комбинаций делителей будет большим.
Может кто и подойдёт.
Перебором как-то долго. Может есть способ быстрее?

[Ian]

Не нужно. Если характеристический многочлен рекуррентного соотношения умножить на другой, то новому соотношению более высокого порядка -удовлетворяет и прежняя последовательность

[zykov]

Source of the post Если характеристический многочлен рекуррентного соотношения умножить на другой, то новому соотношению более высокого порядка -удовлетворяет и прежняя последовательность

Ну вот [math]x^{124}-1 и удовлетворяет.
По отдельности [math]x^2+1 и полином 30-ой степени не удовлетворяют, но их произведение может удовлетворять.
А может какой делитель полинома 30-ой степени умноженный на делитель полинома 60-ой степени будет удовлетворять, хотя оба делителя не удовлетвоярют по отдельности.

Так что ещё неизвестно. Может есть и кокроче.

[zykov]

Source of the post ожидалась рекуррентность невысокого порядка, не более 10го

Нашлась рекурентность порядка 5: [math]{{x}^{5}}+{{x}^{4}}+{{x}^{3}}+2 {{x}^{2}}+x-1
(Складываешь 5 подряд идущих, предпоследний с весом 2, получаешь 6-ой.)

[Ian]

Нашлась рекурентность порядка 5:
(Складываешь 5 подряд идущих, предпоследний с весом 2, получаешь 6-ой.)

Спасибо! По описанию- это другой многочлен [math]-{{x}^{5}}+{{x}^{4}}+2{{x}^{3}}+ {{x}^{2}}+x+1
Ну такая конвенция о соответствии многочленов и рекуррентных уравнений, введенная в посте 1 (и в книгах). Это для того, чтобы геометрическая прогрессия, знаменатель которой- корень многочлена -удовлетворяла уравнению.
И вот еще такая мысль. Если бы он был неприводимым, то был бы множителем одного из тех длинных, которых найдены Вами ранее. Тогда один из тех длинных тоже годился бы. Вывод: он приводим, является произведением двух сомножителей степеней 2 и 3. Каких?

[zykov]

Тут повезло.
Кроме 4 множителей первой степени [math]x+1, [math]x+2, [math]x+3 и [math]x+4 многочлены 30 степени каждый разложились на простые множители третьей степени (по 10 штук) и многочлен 60 степени тоже разложился на 20 простых множителей 3 степени.
(Пришлось програмку написать, чтобы искать простые многочлены и потом проверять на какие делится большой.)
Потом делил большой на каждый из множителей и проверял, будет ли результат работать как рекурентный.
Только три множителя ломали рекурентность - два первого порядка [math]x+3 и [math]x+4, и один 3 порядка из многочлена 60 степени [math]x^3+4 x^2+x+2.
Вот их произведение и дало минимальную рекурентность.
(Это в моей нотации. Если надо перевернуть, то нужно будет поделить, чтобы при старшем члене было 1.)

[Ian]

Ой не сходится. Больше проверенных фактов. Что на что умноженное равно чему? Вы же понимаете, каждое такое умножение проверяю по часу. Вот ваш пост 2 был просто идеален, за него спасибо
А , понял [math](x-1)(x-3)(x^3 +3x^2+2x+3)=x^5-x^4-2x^3-x^2-x-1

[zykov]

Оказывается, зря я писал програмку.
Maxima вполне умеет работать с многочленами по модулю.

mod5.png (11.21 KiB) 13488 просмотра