2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Антибиективнось
Сообщение23.02.2018, 13:10 


24/12/13
351
Докажите, что для любого заданного простого $p$, существуют два целых числа $a$ и $b$, такие, что сравнение $x^3+ax+b \equiv 0 \pmod p$ неразрешимо.

 Профиль  
                  
 
 Re: Антибиективнось
Сообщение23.02.2018, 19:51 
Аватара пользователя


07/01/16
1426
Аязьма
Утверждение: существует не менее $(p-1)$ различных по модулю $p$ пар $(a,b)$, удовлетворяющих условию

 Профиль  
                  
 
 Re: Антибиективнось
Сообщение24.02.2018, 03:17 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
Удалил.

 Профиль  
                  
 
 Re: Антибиективнось
Сообщение24.02.2018, 13:27 


26/08/11
2057
Конечно существуют, причем много и не только по простому модулю. Годится любое $a\equiv 2 \pmod 3$
В частности, напр. при $a=-1$, $f(x)=x^3-x\pmod p$ не образует полную группу вычетов, т.к $f(0)=f(1)=f(-1)=0$

 Профиль  
                  
 
 Re: Антибиективнось
Сообщение24.02.2018, 22:24 
Аватара пользователя


07/01/16
1426
Аязьма
Видимо, для всех $p\neq3$, количество различных по модулю $p$ пар $(a,b)$, удовлетворяющих условию, равно $\frac 1 3 (p^2-1)$. Доказать не возьмусь, результат тупого счета для $p<61$

-- 24.02.2018, 22:28 --

Shadow в сообщении #1294086 писал(а):
Годится любое $a\equiv 2 \pmod 3$
ну да, то есть таких пар, грубо говоря, треть от общего количества

 Профиль  
                  
 
 Re: Антибиективнось
Сообщение06.03.2018, 23:19 
Заслуженный участник


08/04/08
8556
rightways в сообщении #1293898 писал(а):
Докажите, что для любого заданного простого $p$, существуют два целых числа $a$ и $b$, такие, что сравнение $x^3+ax+b \equiv 0 \pmod p$ неразрешимо.
waxtep в сообщении #1294208 писал(а):
для всех $p\neq3$, количество различных по модулю $p$ пар $(a,b)$, удовлетворяющих условию, равно $\frac 1 3 (p^2-1)$.
Доказать можно вручную, только немного длинно получилось.

(уродское доказательство)

Рассматриваем $p\geqslant 5$. $\pmod p$ я буду опускать для краткости
При $b\equiv 0$ все многочлены принимают нулевое значение - неприводимых нет.
При $a\equiv 0$ сравнение $x^3+b\equiv 0$ разрешимо при любом $b$ при $p\equiv -1\pmod 3$ и только для $\frac{p-1}{3}$ значений при $p\equiv 1\pmod 3$. Значит число неприрводимых многочленов вида $x^3+b$ равно $\frac{1+\left(\frac{p}{3}\right)}{2}\left(p-1-\frac{p-1}{3}\right) = \frac{1+\left(\frac{p}{3}\right)}{3}(p-1)$.
При $a,b\not\equiv 0$:
$x^3+ax+b= 0 \Leftrightarrow bu^3+au^2+1=0\Leftrightarrow u^3+ab^{-1}u^2+b^{-1}=0$
Можно также умножить на $c^3$: $(cu)^3+ab^{-1}c(cu)^2+c^3b^{-1}=0$. Выберем $c=ab^{-1}$, заменим $cu=t$. Свободный член $C=a^3b^{-4}$. Получим уравнение $t^3+t^2+C=0$. Т.е. неприводимость почти произвольного кубического многочлена свелась к проверке неприводимости многочлена $t^3+t^2+C$ по модулю $p$. Причем сразу заметим, что уравнение $C=a^3b^{-4}\pmod p$ имеет ровно $p-1$ решений при $a,b,C\not\equiv 0$. Классы решений не пересекаются.
$f(t):=t^3+t^2$. Многочлен $t^3+t^2+C$ неприводим $\Leftrightarrow -C \not\in \operatorname{Im}f$, а число неприводимых многочленов = $p-|\operatorname{Im}f|$.
Число различных значений кубического многочлена $|\operatorname{Im}f|=$ число всех значений $p$ минус число $N_2$ двоек одинаковых значений $f$ плюс число $N_3$ троек одинаковых значений $f$. Кубический многочлен в любом поле не может принимать более трех одинаковых значений, поэтому одинаковые четверки рассматривать не надо.
$N_2=\frac{1}{2}N(f(x)\equiv f(y), x\not\equiv y)$
$x^3+x^2\equiv y^3+y^2\Leftrightarrow$ делим на $y-x$
$y^2+xy+x^2+x+y\equiv 0$, $g(x,y):=y^2+xy+y^2+x+y$,
Выделяем полный квадрат (подробности опускаю): $g(x,y)\equiv 0\Leftrightarrow 3u^2+v^2\equiv 2$
Число решений $N(3u^2+v^2\equiv 2)$ легко вычисляется через символы Лежандра (метод подробно изложен в Айрленде, Роузене):
$N(3u^2+v^2\equiv 2)=p-\left(\frac{-3}{p}\right)=p-\left(\frac{p}{3}\right)$.
$N(g(x,y)\equiv 0, x\not\equiv y) = N(g(x,y)\equiv 0) - N(3x^2+2x\equiv 0)$.
$N_2=\frac{1}{2}\left(p-\left(\frac{p}{3}\right) - 2\right)$
$N_3=\frac{1}{3!}N(g(x,y)\equiv g(y,z)\equiv g(z,x), x\not\equiv y\not\equiv z\not\equiv x)$
Для любого условия $S=S(x,y,z)$, симметричного по всем переменным, имеем $N(S,x\not\equiv y\not\equiv z\not\equiv x) = N(S) - 3N(S, z\equiv x)+2N(S, x\equiv y\equiv z)$
$N(S)=N(f(y)\equiv f(x), f(z)\equiv f(x)) = N(g(x,y)\equiv 0, g(z,x)\equiv 0)$
Вычитаем одно уравнение из другого, получаем $x+y+z+1\equiv 0$. Выражаем $z$ и подставляем:
$g(x,z)=(z+1)(x+z)+x^2\equiv (-y-x)(-y-1)+x^2=y^2+xy+x^2+x+y$ - получаем то же самое уравнение.
$N(S, z\equiv x) = N(g(x,y)\equiv g(y,z)\equiv g(z,x), z\equiv x)=$ $N(g(x,y)\equiv 0, 3y^2+2y \equiv 0) = 3$
$N(S, x\equiv y\equiv z)=N(3y^2+2y\equiv 0)=2$
$N_3=\frac{1}{6}\left(N(g(x,y)\equiv 0) - 3\cdot 3+2\cdot 2\right)=\frac{p-\left(\frac{p}{3}\right)-5}{6}$
И тогда $|\operatorname{Im}(f)|=p-N_2+N_3=p-\frac{1}{2}\left(p-\left(\frac{p}{3}\right) - 2\right)+\frac{p-\left(\frac{p}{3}\right)-5}{6}=\frac{2p+\left(\frac{p}{3}\right)}{3}$.
Число неприводимых многочленов вида $t^3+t^2+C$ равно $p-\frac{2p+\left(\frac{p}{3}\right)}{3}=\frac{p-\left(\frac{p}{3}\right)}{3}$
Число неприводимых многочленов вида $x^3+ax+b, a,b\not\equiv 0$ равно $(p-1)\frac{p-\left(\frac{p}{3}\right)}{3}$
Общее количество неприводимых многочленов: $(p-1)\frac{p-\left(\frac{p}{3}\right)}{3}+\left(1+\left(\frac{p}{3}\right)\right)\frac{p-1}{3}=\frac{p^2-1}{3}$ - получаем требуемое.
Но там у меня еще ошибка в расчете $N_2$, искать ее сил нет.



С другой стороны, если нормально выучить алгебру, то достаточно знать теорему 3.25. из книги Лидла, Нидеррайтера про конечные поля:
Лидл, Нидеррайтер Конечные поля писал(а):
3.25. Теорема. Число $N_q(n)$ нормированных неприводимых многочленов степени $n$ в кольце $\mathbb{F}_q[x]$ задается формулой:
$$N_q(n)=\frac{1}{n}\sum\limits_{d|n}\mu(d)q^{n/d}$$

Т.е. число неприводимых многочленов степени 3 над $\mathbb{F}_p$ равно $\frac{p^3-p}{3}$. Остается только сделать замену $x\to x-\frac{a}{3}$, от которой многочлен $x^3+ax^2+bx+c$ перейдет в $x^3+px+q$, причем эта замена преобразует ровно $p$ разных многочленов вида $x^3+ax^2+bx+c$ в один многочлен вида $x^3+px+q$. В результате число таких неприводимых многочленов будет равно $\frac{p^3-p}{3p}=\frac{p^2-1}{3}$.

Add 08.03.2018
А вообще все просто: число неприводимых многочленов - это число всех многочленов минус число приводимых. Кубический многочлен приводим $\Leftrightarrow$ он имеет корень, т.е. имеет вид $(x+a)(x+b)(x+c)$ или имеет вид $(x^2+ax+b)(x+c)$, где $x^2+ax+b$ неприводим. Число обеих типов многочленов легко считается, число всех многочленов - тоже. Просто упрощаем многочлен и получаем $\frac{p^3-p}{3}$.

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

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



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

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


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

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