2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 
Сообщение17.04.2006, 11:21 


18/02/06
37
мех-мат МГУ
Руст писал(а):
Например, утверждали, что решение на следующий уровень или не поднимается или поднимается p способами, когда P'(x)=0(mod p). На самом деле легко привести пример, для любого k=0,1,...,p, когда решение на следующий уровень поднимается k способами (k=0 - не поднимается, ...).

Приведите, пожалуйста, пример с k \notin \{0, 1, p\}

 Профиль  
                  
 
 
Сообщение17.04.2006, 13:01 
Заслуженный участник


09/02/06
4382
Москва
Пусть $P(x)=x^p-1+ (x-1-p)(x-1-2p)...(x-1-kp)$. Тогда решение x=1 с первого уровня поднимается k способами до решения второго порядка.

 Профиль  
                  
 
 
Сообщение17.04.2006, 14:03 


18/02/06
37
мех-мат МГУ
В этой ситуации, если k > 1, то решение 1 по модулю p продолжается p способами до решения по модулю p^2. Действительно, для любого a: 0 \le a \le p-1 имеем
(1+ap)^p - 1 + (1+ap - 1-p)\cdot \ldots \cdot (1+ap -1 -kp) = (1 + C_p^1 ap + C_p^2a^2p^2 + \ldots + a^pp^p) - 1 + (a-1)(a-2)\cdot \ldots \cdot (a-k)p^k \equiv 0 (mod \, p^2).

 Профиль  
                  
 
 
Сообщение17.04.2006, 14:55 
Заслуженный участник


09/02/06
4382
Москва
Да ошибся надо было немного изменить. Дело в том, чтобы поднять k способами надо поднять решение как минимум k уровня на следующий:
$$P(x)=x^{p^k}-1+\prod_{i=1}^k (x-1-ip).$$
Решение x=1 удовлетворяет сравнению по модулю р в степени k, при подъёме до решения по модулю р в степени k+1 появляется k способов расширения решения из интервала (0,р) до интервала (0,p^2).
Этот пример может не самый удачный, но демонстрирует то, что при подъёме решения где производная делится на р, поднимается решение по степеням для х с отставанием, чем для P(x).

 Профиль  
                  
 
 
Сообщение17.04.2006, 15:31 


18/02/06
37
мех-мат МГУ
А в этом случае, если k > 1, то решение 1 по модулю p^k не продолжается по модулю p^{k+1}. Действительно, для любого a: 0 \le a \le p-1 имеем
(1+ap^k)^{p^k} - 1 + (1+ap^k - 1-p)\cdot \ldots \cdot (1+ap^k -1 -kp) = (1 + C_{p^k}^1 ap^k + \ldots ) - 1 + (ap^{k-1}-1)(ap^{k-1}-2)\cdot \ldots \cdot (ap^{k-1}-k)p^k \equiv Ap^k (mod \, p^{k+1}),
где A = \prod\limits_{i=1}^k(ap^{k-1} - i) \not\equiv 0 (mod \, p) при 1 < k < p.

 Профиль  
                  
 
 
Сообщение17.04.2006, 17:03 
Заслуженный участник


09/02/06
4382
Москва
Возможно объяснение не удачное. Когда производная делится на некоторую степень р уточнение решения по х идёт с отставанием, т.е. если
$P(x_N)=0(mod \ p^N), ord_p(P'(x_N))=k.$
то для нахождения решений $P(x_{N+1})=0(mod \ p^{N+1}),x_{N+1}=x_N+ap^{N-k}$ по следующему модулю меняем х на более низком уровне (на более высоком ясно, что ничего не меняется).

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


21/12/05
5903
Новосибирск
Нет времени разобраться в деталях, тем более, что не все посты безупречны. Всё же хочу ещё раз пояснить, что я писал.
Сергей Михайлов писал(а):
... И гипотетическая оценка числа решений выглядит так: n^c p^{N(1 - 1/n)}, здесь c - константа, зависящая, возможно, от p, но не от n, \, N, \, f.

А теперь посмотрим на мой пример. Возьмём на этот раз произвольное p в форме, близкой к той, как его интерпретировал Руст, только в его интерпретации степень гораздо больше, а модуль значительно меньше:
$$f_k(x)=\prod_{1\le i \le p^k, \ p |i} (x-i)$$
Для него имеем $deg=n=p^{k-1}$, а $mod=p^N$, где $N= p^{k-1}+ p^{k-2}+...+1=\frac{ p^k-1}{p-1}$. Этот многочлен имеет ровно $ p^{N-1}$ корней по модулю $p^N$, то есть каждый $p$-ый. Для $p=2$ - каждый второй вычет.
Иначе говоря верхняя оценка для числа корней не зависящая от полинома не может быть лучшей, чем $1/p$-я от модуля.
[Белый шрифт:
Если даже поставить очень сильное условие (на котором, как я понял, никто не настаивает), что ни один из коэффициентов полинома не делится на $p$, в частности все они отличны от нуля, то можно внести следующую поправку, которая существенно не изменит картины. Вместо ранее предлагаемого неэкономного увеличения степени лучше убрать из многочлена любой из множителей, скажем $x-p$ и сдвинуть аргумент на единицу. Степень уменьшится на 1, показатель $N$ уменьшится всего лишь на $k$ и по-прежнему сохранится 1/p–я доля корней среди всех вычетов. конец белого шрифта]
Как то я не вижу, чтобы это вписывалось в гипотетическую оценку Сергея Михайлова (а она ведь тоже не маленькая!) – у него из показателя $N$ вычитается больше 1, но зато присутствует множитель $n^c$, который при фиксированном $c$ну никак не сможет компенсировать это уменьшение показателя.
Руст писал(а):
Да вы вчера bot у ответили, а я оставил без ответа. Я не отвечаю на все ошибки здесь. Вы так и не поняли лемму Гензеля, что я махнул рукой. Например, утверждали, что решение на следующий уровень или не поднимается или поднимается p способами, когда P'(x)=0(mod p).

Похоже, Вы с чем-то путаете. Ну раз уж пошла такая пьянка, то давайте изложу доказательство. Буду писать $a \equiv_m b$ вместо $a \equiv b (mod \ m)$

Пусть $x \equiv_p x_0$ и $f(x) \equiv_{p^k} 0$, то есть $x$ – решение поднятое на $k$-й уровень с решения $x_0$ по модулю $p$. Продолжение решения $x$ на $k+1$-ый уровень согласно стандарту ищется в виде $x+tp^k$ из сравнения
$$\frac{f(x)}{p^k}+f’(x)t \equiv_p 0$$
Так как $f’(x)$ многочлен и $x \equiv_p x_0$, то $f’(x) \equiv_p f(’x_0)$, то последнее сравнение становится таким:
$$\frac{f(x)}{p^k}+f’(x_0)t \equiv_p 0$$
Отсюда и следует то, что я говорил – если $f’(x) \equiv_p 0$$ то количество способов поднятия решения с любого уровня на следующий может быть только $0, 1$ или $ p$.

ЗЫ. Несущественную часть забелил.

 Профиль  
                  
 
 
Сообщение26.04.2006, 11:06 
Заслуженный участник


09/02/06
4382
Москва
bot! Прочтите вначале то, что написали другие.
1. Нигде не предполагается, что все коэффициенты не делятся на р. Допускается даже равенство нулю (делимость на бесконечную степень р) для некоторых коэффициентов.
2. Вы всё ещё путаете N с конкретным значением зависящим от n.
3. То что вы пишите в конце верно. Однако, когда производная делится на некоторую степень простого числа р (допустим k), то подсчёт числа поднятий бессмыслен без учёта отставания приближения на степень k от степени приближения выполнения f(x)=0 (N). Т.е. искать решение по более высокому модулю делается только так: $f(x_{N+1})=0(mod \ p^{N+1}),x_{N+1}=x_N+cp^{N-k}.$
Именно в этом смысле, количество возможных поднятий (т.е. количество решений с) может быть произвольным до р.

 Профиль  
                  
 
 
Сообщение26.04.2006, 11:55 


18/02/06
37
мех-мат МГУ
bot писал(а):
Нет времени разобраться в деталях, тем более, что не все посты безупречны. Всё же хочу ещё раз пояснить, что я писал.
Сергей Михайлов писал(а):
... И гипотетическая оценка числа решений выглядит так: n^c p^{N(1 - 1/n)}, здесь c - константа, зависящая, возможно, от p, но не от n, \, N, \, f.

А теперь посмотрим на мой пример. Возьмём на этот раз произвольное p в форме, близкой к той, как его интерпретировал Руст, только в его интерпретации степень гораздо больше, а модуль значительно меньше:
$$f_k(x)=\prod_{1\le i \le p^k, \ p |i} (x-i)$$
Для него имеем $deg=n=p^{k-1}$, а $mod=p^N$, где $N= p^{k-1}+ p^{k-2}+...+1=\frac{ p^k-1}{p-1}$. Этот многочлен имеет ровно $ p^{N-1}$ корней по модулю $p^N$, то есть каждый $p$-ый.


Пример не противоречит гипотезе. Проверим, что число решений p^{N-1} не превосходит n^cp^{N(1-1/n)}. Действительно, 1) n = p^{k-1} \geq 2 при k \geq 2.
2) N = \frac{pn-1}{p-1} => отношение реального числа решений к гипотетической оценке равно n^{-c} p^{- N + 1 + N - N/n} = n^{-c} p^{1 - \frac{pn - 1}{(p-1)n}} = n^{-c} p^{1 - \frac{p}{p-1} + \frac{1}{(p-1)n}} \leq n^{-c} p^{-\frac{1}{p-1} + \frac{1}{(p-1)2} } =
n^{-c}p^{-\frac{1}{2(p-1)}}. Т.к. с ростом p величина p^{-1/(2p-1)} стремится к 1, то выражение p^{-1/2(p-1)} ограничено сверху некоторой абсолютной константой M. Достаточно, чтобы c удовлетворяло условию 2^c > M, и тогда гипотеза справедлива.

На самом деле, справедливость гипотезы удалось установить, используя современные оценки тригонометрических сумм. Доказательство напишу скоро.

 Профиль  
                  
 
 Тождество кольца вычетов по модулю p в степени N
Сообщение26.04.2006, 20:08 
Заслуженный участник
Аватара пользователя


28/09/05
287
Возможно, в виду Вашей задачи, это будет Вам интересно.

Если $N$ имеет вид $N=\frac{p^t-1}{p-1}$, $t\in\mathbb N$, то существует унитарный (т.е., с коэффициентом 1 при старшем члене) многочлен $f(x)\in\mathbb Z[x]$ степени $n = N(p-1)+1$ такой, что $f(z)=0$ для любого $z\in\mathbb Z_{p^N}$.

То есть, для таких $N$, многочлен $f(x)$ является тождеством кольца $\mathbb Z_{p^N}$. Можно показать, что унитарного тождества меньшей степени не существует.

Например, $x^4-2x^3-x^2+2x$ есть унитарное тождество наименьшей степени для кольца $\mathbb Z_8$.

 Профиль  
                  
 
 Re: Тождество кольца вычетов по модулю p в степени N
Сообщение26.04.2006, 23:03 


18/02/06
37
мех-мат МГУ
Такой многочлен я строить умею: \prod\limits_{i=1}^{i=p^t} (x + i). При любом натуральном x это выражение кратно p^t !, а в этот факториал p входит в степени N. А вот как показать, что для любого многочлена меньшей степени не может выполняться условие?

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


21/12/05
5903
Новосибирск
Руст писал(а):
bot! Прочтите вначале то, что написали другие.
1. Нигде не предполагается, что все коэффициенты не делятся на р. Допускается даже равенство нулю (делимость на бесконечную степень р) для некоторых коэффициентов.
2. Вы всё ещё путаете N с конкретным значением зависящим от n.
3. То что вы пишите в конце верно. Однако, когда производная делится на некоторую степень простого числа р (допустим k), то подсчёт числа поднятий бессмыслен без учёта отставания приближения на степень k от степени приближения выполнения f(x)=0 (N). Т.е. искать решение по более высокому модулю делается только так: $f(x_{N+1})=0(mod \ p^{N+1}),x_{N+1}=x_N+cp^{N-k}.$
Именно в этом смысле, количество возможных поднятий (т.е. количество решений с) может быть произвольным до р.


Да я читаю, со временем только туго. По этой причине не считаю возможным вдаваться в детали, если есть непонятки с самой постановкой задачи. Я считал, что мой пример с большим модулем и много меньшей степенью должен смутить автора вопроса и предполагал, что пример этот не признают. А по поводу N - что мешает взять то, которое захочу. Ниже буду брать другие.
С последним пунктом непонятки. Какова бы ни была производная, продолжения решения с более низкого уровня на следующий не может идти путём исправления решения, расположенного на более низком этаже, как написано у Вас в п.3, а что Вы имели в виду, когда говорили о возможности единственного продолжения при равенстве 0 производной на самом нижнем этаже, так и осталось для меня загадкой.
По первому пункту отвечаю забеливанием этого несущественного фрагмента, на котором и в самом сообщении не настаивал.

Теперь по поводу оценки. Действительно она не противоречит моей и автора вопроса это не смущает. Но ведь тогда ещё интереснее. Нифига себе получается диапазончик для числа решений - от 0 до почти всех или даже всех. Наверно против нуля возражать не станете, но на всякий случай приведу пример:
$g_k(x)=x^{p^{k-1}}f_k(\frac{1}{x})$ - у него нет корней даже по модулю p.
С другой стороны, оценка может и за модуль зашкалить. Не заметил ничего определённого о константе c, кроме её существования, но надо её, понятно, полагать положительной, впрочем это сразу видно и из сравнения оценки с моей: $c \ge \frac{1}{p}$. Ясно, что для многочлена $f_k$ с уменьшением N доля (равная $\frac{1}{p}$ ) корней среди вычетов сохраняется. Возьмём $N_1 \le p^{k-1}$ и $k \ge 1+\frac{1}{c}$, тогда оценка зашкаливает за модуль:
$n^cp^{N_1 - \frac{N_1}{n}} \ge p^{N_1}$
Таким образом, для многочлена заданной степени k с ростом модуля вплоть до огромной величины много много (одного много, как у физиков, мне кажется мало) большей степени многочлена оценка будет говорить, что все вычеты могут быть корнями и только где-то около p^N начнёт говорить - нет, их меньше...
Ну да, вроде слегка понятно стало, что меня смущало, хотя и сейчас смущает - я ведь бесконечно далёк от подобного рода оценок и не припомню, чтобы когда-нибудь с ними сталкивался.

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


21/12/05
5903
Новосибирск
lofar писал(а):
Если $N$ имеет вид $N=\frac{p^t-1}{p-1}$, $t\in\mathbb N$, то существует унитарный многочлен ...

Кстати да - мелькала мысль перемножить сдвинутые$f_k(x)$, да помешало желание построить многочлен со всеми коэффициентами, не делящимися на p. :D

Сергей Михайлов писал(а):
Такой многочлен я строить умею: \prod\limits_{i=1}^{i=p^t} (x + i). При любом натуральном x это выражение кратно p^t !, а в этот факториал p входит в степени N. А вот как показать, что для любого многочлена меньшей степени не может выполняться условие?


То есть произведение всех $f_t(x+i), \ i=0,1,...,p-1$
Показать, что меньшая степень невозможна, очень просто.
Рассмотрим матрицу Вандермонда $ \ W=W(1,2, ..., n) \ $. Её определитель равен $ \ 1! \ 2! \ ... \ (n-1)! \ $, а все алгебраические дополнения имеют (по меньшей мере) общий множитель $1! \ 2! \ ... \ (n-2)! \ $. Отсюда матрица $\ A=(n-1)! \ W^{-1} \ $ целочисленна. При $ \ n=p^t \ $ показатель $ \ p \ $ в $ \ (n-1)! \ $ равен $ \ N-t \ $, где $ \ N=\frac{p^t-1}{p-1} \ $. Отсюда и следует, что у всякого многочлена, тождественно равного нулю в кольце $ \ \mathbb Z_{p^N} \ $ и имеющего степень, меньшую $ \ p^t \ $, все коэффициенты делятся на $ \ p \ $, в частности нет унитарного.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 43 ]  На страницу Пред.  1, 2, 3

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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