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

[Руст]

Вы же рассматриваете многочлен от одной переменной, т.е. множество решений должно быть конечно за исключением некоторых "вырожденных" случаев.

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

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

Вы же рассматриваете многочлен от одной переменной, т.е. множество решений должно быть конечно за исключением некоторых "вырожденных" случаев.

Множество решений естественно конечно, т.к. ищутся решения на отрезке [0, p^N - 1]. Но тривиальная оценка сверху p^N меня не устраивает.

[Руст]

Я имел в виду ограничено константой, не зависящей от N, в частности не больше n при p>n.

[bot]

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

Но тривиальная оценка сверху p^N меня не устраивает.

А что Вы будете, например, делать с таким простеньким одночленом: p^{n-1} x?
У него ведь корней p^{n-1} по модулю p^n

Повторюсь - при подъёме корня x_0 с любого уровня на следующий ведь важно лишь знать, равна нулю производная по модулю p или нет, а если равна, то дальше можно рубить ветви или множить их за счёт поправки этого корня x_0 в самом основании дерева.

Не проверял, но кажется достаточно очевидным, что для любого k \leq p^n существует многочлен с целыми коэфициентами степени не выше p, имеющий ровно k корней по модулю p^n
При этом возможно избежать делимости коэффициентов на p

[Руст]

bot писал(а):

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

Но тривиальная оценка сверху p^N меня не устраивает.

А что Вы будете, например, делать с таким простеньким одночленом: p^{n-1} x?
У него ведь корней p^{n-1} по модулю p^n

Повторюсь - при подъёме корня x_0 с любого уровня на следующий ведь важно лишь знать, равна нулю производная по модулю p или нет, а если равна, то дальше можно рубить ветви или множить их за счёт поправки этого корня x_0 в самом основании дерева.

Не проверял, но кажется достаточно очевидным, что для любого k \leq p^n существует многочлен с целыми коэфициентами степени не выше p, имеющий ровно k корней по модулю p^n

Во первых многочлен фиксирован степени n, соответственно коэффициенты не могут изменяться от увеличения N. Вы здесь вместо N стали употреблять n.
Назовём многочлен невырожденным по модулю p если младший коэффициент не делится на р. Тогда любое решение сравнения по модулю р однозначно (единственным образом) поднимается до решения по модулю р в степени N, если производная не сравнима с 0 по модулю р. Когда производная сранима с нулём по модулю р в степени к, но не сравнима по модулю р в степени к+1 то однозначность поднятия мы можем гарантировать только если исходное решение удовлетворяется и по модулю p^(2k+1) и начиная с сравнения с исходным от p^(k+1).

[bot]

bot писал(а):

...

Уж лучше бы жевал.
Странно, что мой бред относительно возможности заполнить сплошь промежуток от 0 до $p^n$ никто не заметил, например, явно не реализуемо $p^n-1$. Возможностей-то много, но не настолько же.

А вот относительно подъёма, я не брежу:
Если $f'(x_0) \equiv 0$, то любое решение $x $по модулю $p^k$ , сравнимое с $x_0$ по модулю $p$ либо не поднимается на следующий уровень, либо продолжается в $p $ экземплярах, единственности подъёма не будет, независимо от сравнения этой производной с $0$по более высоким модулям.

Кое-что (хотя и не так глобально) относительно нетривиальных оценок числа решений:
Настаиваю на том, что ничего существенно лучшего, чем сказал maxal, не придумаешь. Вот пример (для простоты берём $p=2$):

$f_n(x)=(x+1)(x+3)(x+5)...(x+2^n-1)$
Его степень равна $2^{n-1}$, и он имеет $2^{2^n-2}$ корней по модулю $2^{2^n-1}$, то есть все нечётные.
Аналогичные многочлены можно взять для $p \neq 2$

Например, при $n=4$ этот многочлен степени $8$ имеет $2^{14}$ корней по модулю $2^{15}$

Относительно неделимости коэффициентов на $p$: странное это условие. Это что же все степени должны присутствовать, то есть нулевые коэффициенты недопустимы? Это ещё не всё: сдвиг аргумента сохраняет число корней, а это свойство нет. Что можно выжать из этого условия?

В вышеуказанном примере можно легко избавиться от чётности коэффициентов многочлена (сдвигом не пробовал, а путём незначительного увеличения степени - запросто) - достаточно его умножить на $(x+1)^{2^{n-1}-1}$, тогда в примере с $f_4$ будем иметь многочлен степени $15$ с нечётными коэффициентами имеющий $2^{14}$ корней по модулю $2^{15}$

[Руст]

Вообще переменные первым начал путать автор задачи. Поэтому для определённости, ещё раз упомяну своё аонимание об обозначениях: n cтепень многочлена, N степень простого числа по которому ищется количество решений сравнения.
Ваш многочлен со сдвигом имеет вид:

$$f_k(x)=\prod_{1\le i<p^k,p\not |i} (x-i) =x^{(p-1)p^{k-1}}-1 (mod \ p^k), \ \ n=(p-1)p^k $$

и совпадает с большой точностью с приведённым мною. Соответственно количество решений сравнения: $f_k(x)=0 (mod \ p^N) 1\le p^N $ дается формулой:
$(p-1)p^{N-1} \ if \ N\le k, \ else \ n=(p-1)p^k.$
Как видите количество решений не превышает степени многочлена (из-за невырожденности).

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

bot писал(а):

bot писал(а):

...

Уж лучше бы жевал.
Странно, что мой бред относительно возможности заполнить сплошь промежуток от 0 до $p^n$ никто не заметил, например, явно не реализуемо $p^n-1$. Возможностей-то много, но не настолько же.

Заметили, заметили. Но решили, что вы и сами все поймете, когда еще раз перечитаете

bot писал(а):

А вот относительно подъёма, я не брежу:
Если $f'(x_0) \equiv 0$, то любое решение $x $по модулю $p^k$ , сравнимое с $x_0$ по модулю $p$ либо не поднимается на следующий уровень, либо продолжается в $p $ экземплярах, единственности подъёма не будет, независимо от сравнения этой производной с $0$по более высоким модулям.

Тут я с вами полностью согласен. Каждое решение по модулю p либо поднимется до решения по модулю p^2 p способами, либо не поднимется вообще. Аналогично каждое решение по модулю p^2 и т.д. Но эту информацию мне не удалось пока то применить для получения оценки лучше тривиальной.

bot писал(а):

Кое-что (хотя и не так глобально) относительно нетривиальных оценок числа решений:
Настаиваю на том, что ничего существенно лучшего, чем сказал maxal, не придумаешь. Вот пример (для простоты берём $p=2$):

$f_n(x)=(x+1)(x+3)(x+5)...(x+2^n-1)$
Его степень равна $2^{n-1}$, и он имеет $2^{2^n-2}$ корней по модулю $2^{2^n-1}$, то есть все нечётные.
Аналогичные многочлены можно взять для $p \neq 2$

Например, при $n=4$ этот многочлен степени $8$ имеет $2^{14}$ корней по модулю $2^{15}$

Пример хороший. Однако он не противоречит гипотетической оценке, которую я хочу доказать. Дело в том, что ситуация, где я хочу применить оценку такова, что степень многочлена значительно меньше модуля. Сейчас попробую написать это более конкретно. Вот у вас степень многочлена \deg f = 2^{n-1} \quad mod = 2^{2^n - 1}, т.е. грубо говоря модуль и степень связаны соотношением log(mod) \sim \deg f. А применяться оценка будет в ситуации log(mod) \sim (\deg f) ^2.

bot писал(а):

Относительно неделимости коэффициентов на $p$: странное это условие. Это что же все степени должны присутствовать, то есть нулевые коэффициенты недопустимы? Это ещё не всё: сдвиг аргумента сохраняет число корней, а это свойство нет. Что можно выжать из этого условия?

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

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

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

Вообще переменные первым начал путать автор задачи. Поэтому для определённости, ещё раз упомяну своё понимание об обозначениях: n cтепень многочлена, N степень простого числа по которому ищется количество решений сравнения.

Все верно. Условие такое. В плюс к нему: найдется коэффициент многочлена не делящийся на p. И гипотетическая оценка числа решений выглядит так: n^c p^{N(1 - 1/n)}, здесь c - константа, зависящая, возможно, от p, но не от n, \, N, \, f.

[Руст]

Я пропустил р в степени к в последнем сообщении. Оценка полностью доводится до нормального.
Пусть наибольший делитель коэффициентов делится на р в степени m (максимальная степень, и это число можно назвать степенью приведения), то число решений сравнения по модулю р в степени N выражается через число решений по модулю р в степени N-m для приведённого многочлена (сокращённого на общий делитель) умножением на р в степени m. Поэтому, нет смысла останавливаться на пнеприведённом случае.
Далее введём степень вырождения l как максимальная степень на которую делится свободный коэффициент. В случае, когда свободный коэффициент равен нулю будем считать, что степень вырождения бесконечный. Это единственный случай, когда число решений неограниченно растёт. Действительно, обозначив число решений сравнения M(P,N) получаем: $P(x)=R(x)x^r, M(P,N)\le \sum_{i\ge 0} p^{(r-1)i}M(R,N-ri).$
Соответственно рост как $M(R,N)p^{N(1-1/r)}.$
Остается оценить когда нет бесконечного вырождения. Покажем, что в этом случае количество решений ограничено. Правда из-за неограниченности степени вырождения может оказаться больше любой степени n, т.е. в оценке должен присутствовать l.
Рассмотрим вначале случай решений делящихся на р (они существуют только при l>0).
При этом легко вычисляется максимальная степень р на которую может делится решение:
$P(x)=a_0+a_1x+...+a_nx^n, j=max(i|i\ge ord_p(a_0)-ord_p(a_1),ord_p(a_k)+ki>ord_p(a_0), k>1).$
Это приводит к сумме вариантов решений для случая, когда l=0.
В этом случае решения не делятся на р и оцениваются таким образом. Продолжения решений будем искать в виде:

$$x_{q+1}=x_q+a_qp^q,1\le\a_q\le p-1, P(x_{q+1})=P(x_q)+P'(x_q)ap^q+P''(x_q)a_q^2p^{2q}/2+..., ord_p(P'(x_q))=k.$$

Отсюда видно, что если решение для $x_q$ удовлетворяется с точностью до р в степени k+q то по нему получается единственное решение с точностью до степени k+q+1, если q>k. Соответственно в этом случае количество решений ограничено числом
$(p-1)p^{2k}, p^k\le n<p^{k+1}.$
В общем получается такая оценка
$M(P,N)\le (r+1)p^{N(1-1/r)}ln^2(p-1).$

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

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

В общем получается такая оценка
$M(P,N)\le (r+1)p^{N(1-1/r)}ln^2(p-1).$

а что такое r в этой оценке?
что такое r понял. Этот вопрос снимается

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

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

Это приводит к сумме вариантов решений для случая, когда l=0.
В этом случае решения не делятся на р и оцениваются таким образом. Продолжения решений будем искать в виде:

$$x_{q+1}=x_q+a_qp^q,1\le a_q\le p-1, P(x_{q+1})=P(x_q)+P'(x_q)ap^q+P''(x_q)a_q^2p^{2q}/2+..., ord_p(P'(x_q))=k.$$

А что если P'(x_q) = 0?

[Руст]

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

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

так может у них нет общего корня. для многочлена это решение сравнения. а для производной - корень.

[Руст]

Если так, то это решение не размножится, так как это означает, что х точный корень производный, а для P(x) выполняется сравнение только с точностью до некоторой степени, а дальше нет.
Ещё с вырожденными решениями у меня есть неточности и надо проделать более аккуратно. Для этого в терминологии я бы внёс следующие уточнения: степенью вырождения назвал бы минимальный номер коэффициента отличного от нуля r, а показателем вырождения максимальную степень р на которую делится этот коэффициент. В подсчёте решений разделил на числа M(P,N,i) - количество решений сравнения P(x)=0(mod p^N) с показателем вырождения i (делящихся на p^i и не делящихся на p^(i+1)). Тогда можно выписать точные равенства для решения вырожденных уравнений (а не неравенства, когда все решения объединены) и проделать аккуратно число решений.
Да вы вчера bot у ответили, а я оставил без ответа. Я не отвечаю на все ошибки здесь. Вы так и не поняли лемму Гензеля, что я махнул рукой. Например, утверждали, что решение на следующий уровень или не поднимается или поднимается p способами, когда P'(x)=0(mod p). На самом деле легко привести пример, для любого k=0,1,...,p, когда решение на следующий уровень поднимается k способами (k=0 - не поднимается, ...). Я не всегда отвечаю даже в случае, когда оппонент ошибочно отвергает меня (не раз было с Сорокиным), когда вижу, что мои аргументы до него всё равно не доходят.