Страница 1 из 1
Рекуррентность в конечном поле
Добавлено: 13 май 2023, 17:35
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, но это не помогло найти
Рекуррентность в конечном поле
Добавлено: 13 май 2023, 19:28
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 возможно кто-то из них ещё раскладывается.
Рекуррентность в конечном поле
Добавлено: 13 май 2023, 21:47
zykov
Посмотрел эти 6 полиномов. Для каждого есть ненулевой пример (если не ошибся).
Значит они не подходят и значит ниже 124 степени нет.
Рекуррентность в конечном поле
Добавлено: 14 май 2023, 12:38
Ian
zykov писал(а):Над полем по модулю 5 возможно кто-то из них ещё раскладывается.
Спасибо. Конечно многие раскладываются
[math]\left( {{x}^{2}}+1\right) =(x+2)(x+3)а в чем была проверка дальше? Надо же проверить может ли предполагаемый делитель степени m дать , после исходных m членов опубликованной последовательности, все остальные члены опубликованной последовательности.
Рекуррентность в конечном поле
Добавлено: 14 май 2023, 15:19
zykov
Например [math]x-1 и [math]x+1 уже не подходят для начальной подпоследовательности "1, 0".
[math]x^2+1 не подходит для "1, 0, 3".
Аналогично, два многочлена 30 порядка не подошли для первых 31 элементов и один многочлен 60 порядка не подошел для первых 61 элемента.
Т.е. он не то что все не дал, он даже самый первый не дал.
Рекуррентность в конечном поле
Добавлено: 14 май 2023, 15:41
Ian
действительно, что-то с данными, ожидалась рекуррентность невысокого порядка, не более 10го
Спасибо!
Рекуррентность в конечном поле
Добавлено: 14 май 2023, 16:16
zykov
Наверно ещё может оказаться, что какое-то произведение некоторых из этих делителей подойдёт...
Рекуррентность в конечном поле
Добавлено: 14 май 2023, 16:36
zykov
Большие (порядка 30 и 60) тоже наверно так можно разложить. Так что количество возможных комбинаций делителей будет большим.
Может кто и подойдёт.
Перебором как-то долго. Может есть способ быстрее?
Рекуррентность в конечном поле
Добавлено: 14 май 2023, 17:53
Ian
Не нужно. Если характеристический многочлен рекуррентного соотношения умножить на другой, то новому соотношению более высокого порядка -удовлетворяет и прежняя последовательность
Рекуррентность в конечном поле
Добавлено: 14 май 2023, 19:03
zykov
Ian писал(а):Source of the post Если характеристический многочлен рекуррентного соотношения умножить на другой, то новому соотношению более высокого порядка -удовлетворяет и прежняя последовательность
Ну вот
[math]x^{124}-1 и удовлетворяет.
По отдельности
[math]x^2+1 и полином 30-ой степени не удовлетворяют, но их произведение может удовлетворять.
А может какой делитель полинома 30-ой степени умноженный на делитель полинома 60-ой степени будет удовлетворять, хотя оба делителя не удовлетвоярют по отдельности.
Так что ещё неизвестно. Может есть и кокроче.
Рекуррентность в конечном поле
Добавлено: 17 май 2023, 01:06
zykov
Ian писал(а):Source of the post ожидалась рекуррентность невысокого порядка, не более 10го
Нашлась рекурентность порядка 5:
[math]{{x}^{5}}+{{x}^{4}}+{{x}^{3}}+2 {{x}^{2}}+x-1(Складываешь 5 подряд идущих, предпоследний с весом 2, получаешь 6-ой.)
Рекуррентность в конечном поле
Добавлено: 18 май 2023, 07:50
Ian
zykov писал(а):Нашлась рекурентность порядка 5:
(Складываешь 5 подряд идущих, предпоследний с весом 2, получаешь 6-ой.)
Спасибо! По описанию- это другой многочлен
[math]-{{x}^{5}}+{{x}^{4}}+2{{x}^{3}}+ {{x}^{2}}+x+1Ну такая конвенция о соответствии многочленов и рекуррентных уравнений, введенная в посте 1 (и в книгах). Это для того, чтобы геометрическая прогрессия, знаменатель которой- корень многочлена -удовлетворяла уравнению.
И вот еще такая мысль. Если бы он был неприводимым, то был бы множителем одного из тех длинных, которых найдены Вами ранее. Тогда один из тех длинных тоже годился бы. Вывод: он приводим, является произведением двух сомножителей степеней 2 и 3. Каких?
Рекуррентность в конечном поле
Добавлено: 18 май 2023, 13:51
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.)
Рекуррентность в конечном поле
Добавлено: 18 май 2023, 17:19
Ian
Ой не сходится. Больше проверенных фактов. Что на что умноженное равно чему? Вы же понимаете, каждое такое умножение проверяю по часу. Вот ваш пост 2 был просто идеален, за него спасибо
А , понял [math](x-1)(x-3)(x^3 +3x^2+2x+3)=x^5-x^4-2x^3-x^2-x-1
Рекуррентность в конечном поле
Добавлено: 19 май 2023, 02:10
zykov
Оказывается, зря я писал програмку.
Maxima вполне умеет работать с многочленами по модулю.
- mod5.png (11.21 KiB) 13615 просмотра