Число решений сравнения f(x) = 0 mod p^n

[Сергей Михайлов]

Руст писал(а):

Например, утверждали, что решение на следующий уровень или не поднимается или поднимается p способами, когда P'(x)=0(mod p). На самом деле легко привести пример, для любого k=0,1,...,p, когда решение на следующий уровень поднимается k способами (k=0 - не поднимается, ...).

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

[Руст]

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

[Сергей Михайлов]

В этой ситуации, если 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).

[Руст]

Да ошибся надо было немного изменить. Дело в том, чтобы поднять 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).

[Сергей Михайлов]

А в этом случае, если 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.

[Руст]

Возможно объяснение не удачное. Когда производная делится на некоторую степень р уточнение решения по х идёт с отставанием, т.е. если
$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}$ по следующему модулю меняем х на более низком уровне (на более высоком ясно, что ничего не меняется).

[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=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$.

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

[Руст]

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}.$
Именно в этом смысле, количество возможных поднятий (т.е. количество решений с) может быть произвольным до р.

[Сергей Михайлов]

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, и тогда гипотеза справедлива.

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

[lofar]

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

Если $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$.

[Сергей Михайлов]

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

[bot]

Руст писал(а):

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 начнёт говорить - нет, их меньше...
Ну да, вроде слегка понятно стало, что меня смущало, хотя и сейчас смущает - я ведь бесконечно далёк от подобного рода оценок и не припомню, чтобы когда-нибудь с ними сталкивался.

[bot]

lofar писал(а):

Если $N$ имеет вид $N=\frac{p^t-1}{p-1}$, $t\in\mathbb N$, то существует унитарный многочлен ...

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

Сергей Михайлов писал(а):

Такой многочлен я строить умею: \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 \ $, в частности нет унитарного.