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

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

При решении одной задачи мне потребовалось оценить число решений сравнения
f(x) \equiv 0 (mod \, p^n), f \in \mathbb{Z}[x], p - \text{простое}, 0 \leq x < p^n.
Для n = 1 ответ естествено известен. Число решений не превосходит степени f.
При произвольном n известно, что если x_0 таково, что
0 \leq x_0 < p, f(x_0) \equiv 0 (mod \, p), f'(x_0) ] \not\equiv 0 (mod \, p), то существует единственное
y \text{со свойствами:} 0 \leq y < p^n, f(y) \equiv 0 (mod \, p^n), y \equiv x_0 (mod \, p), т.е. решение по модулю p можно "поднять" до решения по модулю p^n единственным образом для хорошего многочлена и хорошего решения.
Но хотелось бы получить оценку в случае произвольного многочлена. Уверен, вопрос не новый и какие-нибудь результаты в этом направлении есть. Буду благодарен за любые факты или ссылки.
Приведите $\LaTeX$ код к корректному виду. В соответствии с правилами. //Администратор cepesh.

[maxal]

В общем случае число решений можно ограничить только p^n. Потому как, если все коэффициенты многочлена делятся на p^n, то каждый элемент \mathbb{Z}_{p^n} будет удовлетворять сравнению f(x)\equiv 0\pmod{p^n}.

Приведите $\LaTeX$ код к корректному виду. В соответствии с правилами. //Администратор cepesh.

[Руст]

Для этого не требуется делимость коэффициентов даже на р. Например уравнение:

$$x^{(p-1)p^{n-1}}=1$$

имеет почти столько же решений и не один коэффициент не делится на р.

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

maxal писал(а):

В общем случае число решений можно ограничить только p^n. Потому как, если все коэффициенты многочлена делятся на p^n, то каждый элемент \mathbb{Z}_{p^n} будет удовлетворять сравнению f(x)\equiv 0\pmod{p^n}.

Да, сразу не сообразил исключить эту ситуацию из рассмотрения. Оценку нужно получить для ситуации, когда сравнение не вырождается в сравнение по меньшему модулю, т.е. когда не все коэффициенты многочлена делятся на p.

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

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

Для этого не требуется делимость коэффициентов даже на р. Например уравнение:
$$x^{(p-1)p^{n-1}}=1$$ имеет почти столько же решений и не один коэффициент не делится на р.</div><!-- quote end --> Это понятно. Для n=1, если deg f > p, то может так случиться, что сравнение имеет все возможные p решений, и оценка сверху степенью теряет смысл. Аналогично в вашем примере: степень многочлена настолько велика, что почти все возможные значения являеются решениями. А хочется получить нетривиальную оценку, когда степень мала по сравнению с [math]p^n.

[Руст]

Для этого случая есть ограничение на рост числа сравнений. Она дается теоремой Игуса о рациональности ряда Пуанкаре. Об этом говорится в первой главе книжки Боревич, Шафаревич "Теория чисел".

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

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

Для этого случая есть ограничение на рост числа сравнений. Она дается теоремой Игуса о рациональности ряда Пуанкаре. Об этом говорится в первой главе книжки Боревич, Шафаревич "Теория чисел".

Поискал в книжке Боревич, Шафаревич "Теория чисел" (изд. 1972г). В первой главе нашел только в качестве упражнения "доказать рациональность ряда Пуанкаре для многочленов одной переменной".
Ряд Пуанкаре для многочлена f есть \phi(t) = \sum\limits_{m=0}^{\infty} c_mt^m, где c_m - есть число решений сравнения f(x) \equiv 0 (mod \, p^m).
Доказательство там не приведено. Оценок не написано. Или вы имеете в виду, что эти оценки как-то легко получаются из того, что \phi(t) рациональна?

Приведите $\LaTeX$ код к корректному виду. В соответствии с правилами. //Администратор cepesh.

[Руст]

В книге 1985 г. говорится, что это эквивалентно существованию рекурентного соотношения между этими коэффициентами ряда Пуанкаре. В принципе это (эквивалентность) легко доказать и самому. Рост самих чисел отсюда (из линейных рекурентных соотношений) легко оценивается. На самом деле в соглассии с леммой Гензеля максимальные по модулю из характеристических чисел должны быть равными p в степени размерность пространства решений.

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

Посмотрел в издании за 1985г. Мне кажется должно быть что-то проще. Там речь идет о многочлене многих переменных с целыми p-адическими коэффцициентами. Мне же нужна одна переменная и коэффициенты самые что ни на есть обычные.

[Руст]

В этом случае размерность пространства решений равна 0, т.е. имеется конечное число решений. Есть лемма Гензеля, которое указывает, начиная с которого все решения по модулю р в степени n получаются продолжением решений по модулю n-1, т.е. начиная с которого последовательность коэффициентов с(m) стабилизируется.

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

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

В этом случае размерность пространства решений равна 0, т.е. имеется конечное число решений. Есть лемма Гензеля, которое указывает, начиная с которого все решения по модулю р в степени n получаются продолжением решений по модулю n-1, т.е. начиная с которого последовательность коэффициентов с(m) стабилизируется.

Какая конкретно формулировка у леммы Гензеля, о которой вы говорите, в таком случае? Я всегда думал, что лемма Гензеля - это утверждение о "подъеме" решений, которое я написал в первом посте.

[Руст]

Приведу не самый общий вид леммы Гензеля (необходимый для вашего случая):
0 \leq x_0 < p, f(x_0) \equiv 0 (mod \, p^{2k+1}), f'(x_0) \not\equiv 0 (mod \, p^{k+1}), то существует единственное
y \text{со свойствами:} 0 \leq y < p^n, f(y) \equiv 0 (mod \, p^n), y \equiv x_0 (mod \, p^{k+1}), т.е. решение по модулю $p^{2k+1}$ можно "поднять" до решения по модулю p^n единственным образом для хорошего многочлена и хорошего решения.
(трансформировал ваш случай к=0, на произвольного натурального к)

[bot]

Руст, способ подъёма (единственное оно или $p$ штук) зависит от значения производной по модулю $p$, а не по $p^{k+1}$
Собственно maxal уже ответил - число корней может быть любым в пределах от $0$ до $p^n$
Это легко понять из "деревянности" этого поднятия:
Если $f'(x_0) \ \not\equiv \ 0 (mod \, p}),$ то любое решение $ x$ по модулю $ p^k $, сравнимое с $x_0$ по модулю $p$ продолжается до решения по модулю $p^{k+1}$ единственным образом.
Если же $f'(x_0) \ \equiv \ 0 (mod \, p}),$ то это же решение либо вообще дальше не продолжается, либо продолжается $p$ способами.

[Руст]

Во первых, кроме первого "якобы" замечания, вы мне не противоречите. Поэтому, вроде и отвечать ничего. Я указал только случай единственного поднятия в случае, когда производная в данной точке равно 0 по модулю р, наподобии первого случая ВТФ, который хотел доказать Сорокин. В этом случае производная равна нулю по модулю р, но по модулю р в квадрате отлична от нуля. Поэтому, мы ничего не можем сказать о возможности поднятия после первого знака (может не подниматься), а после второго можем.

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

У меня появилась некая рабочая гипотеза. Пытаюсь доказать или опровергнуть.
Пусть f(x) \in \mathbb{Z}[x], \, \deg f = n, p - простое, и не все коэффициенты f делятся на p. Тогда сравнение f(x) \equiv 0 (mod \, p^N) имеет не более n^{c} p^{N(1 - 1/n)} решений на отрезке [0, p^N], где c - некоторая константа, не зависящая ни от n, ни от N, ни от многочлена f (возможно, зависящая от p).
Как видно из предыдущих постов, для хорошего многочлена справедлива просто оценка n. Если взять многочлен f(x) = x^n, то решением соответствующего сравнения будут все числа вида ap^{N/n}, a = 0, 1, \ldots, p^{N (1 - 1/n)} (если N/n - не целое, берем целую часть). Это конечно ничего не доказывает, но демонстрирует, откуда я взял рабочую гипотезу.

Приведите $\LaTeX$ код к корректному виду. В соответствии с правилами. //Администратор cepesh.