2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Обобщение Фибоначчи по простому модулю и циклы де Брёйна
Сообщение29.11.2014, 22:34 


08/09/13
210
Доброе время! Возникла такая вот гипотеза (которую проверил для чисел до $10^5$):
для любого простого числа $p$ существует константа $c$ такая, что последовательность, определённая как $F_0=0$, $F_1=1$, $F_n=cF_{n-2}+cF_{n-1}$, если её элементы взять по модулю $p$ (то есть взять остатки от деления $F_n$ на $p$) образует почти полный цикл де Брёйна, то есть первые $p^2$ остатков от деления членов $F_n$ на $p$ содержат среди себя все возможные двухэлементные непрерывные подпоследовательности (кроме $0 0$, иначе последовательность зациклилась бы).

Например, для $p=5$ таким значением будет $c=2$ и, соответственно, удовлетворять условию будут числа вида $F_n=2F_{n-2}+2F_{n-1}$. Значениями последовательности по модулю $p$ в этом случае будут:

$0, 1, 2, 1, 1, 4,$
$0, 3, 1, 3, 3, 2,$
$0, 4, 3, 4, 4, 1,$
$0, 2, 4, 2, 2, 3,$
$0, 1, 2, 1, 1, 4,$
$0, 3, 1, 3, 3, 2$
...и так далее...

Ну, да это ладно, прелесть в другом. Прелесть в том, что примерно для половины чисел $p$ минимальным значением $c$ является первообразный корень (слово "примерно" тут, конечно же, означает, что доля таких $p$, видимо, стремится к $\frac{1}{2}$). Экспериментально пока установлено, что для чисел, меньших $100000$, доля таких составляет $0.498645$.

Хотелось бы узнать мнение знатоков, есть ли в математике уже такие результаты, или, может быть, тут вообще всё тривиально и я чего-то туплю?

Пока нет времени исследовать всё подробно, вот я и решил осведомиться, не изобретаю ли велосипед.

 Профиль  
                  
 
 Re: Обобщение Фибоначчи по простому модулю и циклы де Брёйна
Сообщение03.12.2014, 10:27 
Заслуженный участник


12/08/10
1608
1. Вам важнее то, что $-c$ - первообразный корень.
2. Можно переформулировать задачу так:
У одного из многочленов вида $x^2-cx-c$ корень - примитивный элемент поля $F_{p^2}$(порождающий элемент мультипликативной группы).
Ну или у многочлена $x^p+x^{p-1}+1$ один из корней примитивный элемент.

получается интересный вывод: произведение всех неприводимых многочленов вида $x^2-cx-c$ и $x+2$ равно $x^p+x^{p-1}+1$ (по модулю $p$)

 Профиль  
                  
 
 Re: Обобщение Фибоначчи по простому модулю и циклы де Брёйна
Сообщение03.12.2014, 11:12 


23/02/12
3110
Null в сообщении #939450 писал(а):
получается интересный вывод: произведение всех неприводимых многочленов вида $x^2-cx-c$ и $x+2$ равно $x^p+x^{p-1}+1$ (по модулю $p$)

Это не задача, а гипотеза. Задачей является ее доказать.

 Профиль  
                  
 
 Re: Обобщение Фибоначчи по простому модулю и циклы де Брёйна
Сообщение03.12.2014, 21:45 
Модератор
Аватара пользователя


11/01/06
5660
fractalon в сообщении #938067 писал(а):
Доброе время! Возникла такая вот гипотеза (которую проверил для чисел до $10^5$):
для любого простого числа $p$ существует константа $c$ такая, что последовательность, определённая как $F_0=0$, $F_1=1$, $F_n=cF_{n-2}+cF_{n-1}$, если её элементы взять по модулю $p$ (то есть взять остатки от деления $F_n$ на $p$) образует почти полный цикл де Брёйна, то есть первые $p^2$ остатков от деления членов $F_n$ на $p$ содержат среди себя все возможные двухэлементные непрерывные подпоследовательности (кроме $0 0$, иначе последовательность зациклилась бы).

Другими словами, существует такое $c$, что многочлен $x^2-cx-c$ над $\mathrm{GF}(p)$ является примитивным.

 Профиль  
                  
 
 Re: Обобщение Фибоначчи по простому модулю и циклы де Брёйна
Сообщение04.12.2014, 08:40 
Заслуженный участник


12/08/10
1608
maxal, я тоже самое написал. Просто бывают другие примитивные многочлены. Еще бы найти какой-нибудь критерий примитивности.

vicvolf, то что вы выделили не гипотеза, а доказанное утверждение.

Можно доказывать что один из многочленов $x^2+x+c$ - примитивный.

 Профиль  
                  
 
 Re: Обобщение Фибоначчи по простому модулю и циклы де Брёйна
Сообщение06.12.2014, 14:56 
Заслуженный участник


12/08/10
1608
Вроде как удалось доказать что если $\frac{\varphi(p+1)}{2}+\varphi(p-1)>\frac{p-1}{2}$, то решения есть, но к сожалению так выполняется не всегда.
Доказательство:
Работаем в поле $F_{p^2}$, р -нечетное, простое.
1. Если $x^{p-1}$ -порядка $p+1$ и $x^{p+1}$ -порядка $p-1$, то $x$ - порядка $p^2-1$.
Действительно: Если $x$ -порядка m, то $m|p^2-1$, $m=kl$, где $k|p+1$, $l|p-1$. Но тогда
$x^{(p-1)k}=1$, откуда $p+1|k$ и $x^{(p+1)l}=1$, откуда $p-1|l$,а значит $p^2-1|kl$.

2. $y^p$ -операция сопряжения. Откуда
$t(x)=x^p+x\in F_p$
$n(x)=x^{p+1}\in F_p$
$b(x)=x^{p-1}+x^{1-p}+2\in F_p$. т.к.$b(x)=\frac{t^2(x)}{n(x)}$

3.Множество значений $x^{p-1},x \in F^*_{p^2}$ - циклическая группа по умножению. В ней $\varphi(p+1)$ порождающих элементов. Пусть они образуют множество $S$
Если $x\in S$, то $\frac{1}{x}\in S$
$ S\cap F_p=\varnothing$ т.к. иначе $x^{(p-1)(p-1)}=1$, но порядок $x^{p-1}$ равен $p+1$.
Для любого $x^p\in S$ $n(x)$ - квадратичный невычет в $F_p$ иначе $(x^{p+1})^{\frac{p-1}{2}}=1$ и порядок $x^{p-1}$ делит $\frac{p+1}{2}<p+1$

4. Рассмотрим множество $B=\{x+x^{-1}+2|x\in S\}$. В нем $\frac{\varphi(p+1)}{2}$ элементов.
$B\subset F_p$
В $B$ все элементы - квадратичные невычеты в $F_p$.
Иначе $y=x^{p-1}+x^{1-p}+2=(x^{\frac{p-1}{2}}+x^{\frac{1-p}{2}})^2$,$x\in F_{p^2}$. Так как квадратных корней из числа $y$ только 2, то $x^{\frac{p-1}{2}}+x^{\frac{1-p}{2}}\in F_p$
$x^{\frac{p-1}{2}}+x^{p\frac{p-1}{2}}\in F_p$ - сумма сопряженных. Вычтем.
$x^{\frac{1-p}{2}}-x^{p\frac{p-1}{2}}=x^{\frac{1-p}{2}}(1-x^{\frac{p^2-1}{2}})\in F_p$
Если $1-x^{\frac{p^2-1}{2}}=0$ то порядок $x^{p-1}$ делит $\frac{p+1}{2}$ - противоречит определению $S$.
$(1-x^{\frac{p^2-1}{2}})\in F_p$ Значит $x^{\frac{1-p}{2}}\in F_p$
Для всех $z\in F^*_p, z^{1-p}=1$ Значит $(x^{p-1})^{\frac{p-1}{2}}=1$ - порядок $x^{p-1}$ делит $\frac{p-1}{2}$ - противоречит определению $S$

5. Пусть $A$ - множество первообразных корней $F_p$. Они все квадратичные невычеты в $F_p$.
Если $|A|+|B|>\frac{p-1}{2}$, то множества $A$ и $B$ пересекаются, так как квадратичных невычетов $\frac{p-1}{2}$.
Тогда если их пересечение содержит $c$, то $x^2+cx+c$ - искомый.
Действительно пусть $b(z)=c$. Такой $z$ существует по построению $B$.
Порядок $z^{p-1}$ Равен $p+1$. n(z) и с - невычеты. Значит существует $k\in F_p$, такое что $c=k^2 n(z)=n(kz)$. $-k$ - тоже подходит.
Порядок $(kz)^{p-1}=z^{p-1}$ равен $p+1$. Порядок $(kz)^{p+1}=n(kz)=c$ равен $p-1$. Значит порядок $kz$ равен $p^2-1$
$b(kz)=b(z)=c$ Значит $s(kz)^2=b(kz)n(kz)=c^2$. Значит $s(kz)=\pm c$. Заменив знак $k$ знак $s(kz)$ поменяется. Значит можно подобрать $k$ такое что $s(kz)=-c$. Тогда $x=kz$ - корень $x^2-s(x)x+n(x)=0$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group