Швейцер конкурс 2010

[Navid]

Пусть $P$ простое число и $N(P)$ быть число решений сравнения

$$x^x \equiv 1 \pmod P$$

доказать, что существуют положительное действительное число $ c\leq 1/2 $ и простое число $ p_0$ Такое, что для всех $ P\geq p_0$ у нас есть $ N(P) \leq P^c$ .

[Sonic86]

Надо уточнить, откуда $x$. Верно ли, что $1\leqslant x\leqslant P(P-1)$?

Navid в сообщении #937406 писал(а):

существуют положительное действительное число $ c\leq 1/2 $ и простое число $ p_0$ Такое, что для всех $ P\geq p_0$ у нас есть $ N(P) \leq P^c$ .

Это равносильно тому, что существует простое число $p_0$ такое, что для всех $ P\geq p_0$ $ N(P) \leq \sqrt{P}$.

[Sonic86]

Если считать, что $1\leqslant x\leqslant P(P-1)$, то элементарно получается число решений равным $\sigma(P-1)\geqslant P$.
Значит будем считать, что автор имел ввиду $1\leqslant x\leqslant P-1$, хотя это несколько странно.
И тогда просто так не получается:

Пусть $\delta(x)$ - это степень числа $x$, т.е. $a=\delta (x)\Leftrightarrow a\mid P-1\wedge (\exists g)x\equiv g^a \pmod P$, где $g$ - первообразная.
Тогда $x^x\equiv 1\pmod P \Leftrightarrow P-1\mid x\delta (x)$ и

$$N(x^x\equiv 1\pmod P, 1\leqslant x\leqslant P-1)=\sum\limits_{d=\delta(x)\mid P-1}N(P-1\mid xd)=\sum\limits_{d\mid P-1}\sum\limits_{x=1}^{P-1}N(P-1\mid xd, d=\delta(x))$$

Используя только тривиальные оценки
$N(P-1\mid xd, d=\delta(x))\leqslant N(P-1\mid xd)$
$N(P-1\mid xd, d=\delta(x))\leqslant N(d=\delta(x))$
получаем
$\sum\limits_{x=1}^{P-1}N(P-1\mid xd, d=\delta(x))\leqslant \sum\limits_{x=1}^{P-1}N(\frac{P-1}{d}\mid x)=d$
$\sum\limits_{x=1}^{P-1}N(P-1\mid xd, d=\delta(x))\leqslant \sum\limits_{x=1}^{P-1}N(d=\delta(x))=\varphi\left(\frac{P-1}{d}\right)\leqslant \frac{P-1}{d}$
то есть

$$N(x^x\equiv 1\pmod P, 1\leqslant x\leqslant P-1)\leqslant \sum\limits_{d\mid P-1}\min\left\{d;\frac{P-1}{d}\right\}\leqslant 2\sum\limits_{d\mid P-1, d\leqslant \sqrt{P-1}}d$$

И все, застряли. Жалкие потуги найти $\sum\limits_{d\mid n, d\leqslant \sqrt{n}}d$ в завуалированном виде были в теме topic61189.html , но там ничего толком не вышло.
И это нам даст оценку типа $O(\sqrt{P})$, что немного больше того, что хотелось бы

upd:

Sonic86 в сообщении #937724 писал(а):

И все, застряли

А нет, на самом деле очевидно, что эта сумма содержит $\leqslant\frac{\tau(n)}{2}+1$ слагаемых, причем каждое из них $\leqslant \sqrt{n}$, так что имеем тривиальную оценку

$$\sum\limits_{d\mid n, d\leqslant \sqrt{n}}d\leqslant\sqrt{n}\left(\frac{\tau(n)}{2}+1\right)=O(\sqrt{n}\ln n),$$

т.е. недалеко от цели. Константу уменьшить если что будет несложно, надо только логарифм добить.

[ex-math]

Sonic86
Тау логарифмом не оценишь, только в среднем.

[Sonic86]

ex-math в сообщении #937940 писал(а):

Sonic86
Тау логарифмом не оценишь, только в среднем.

Да, значит пока только $O(n^{\frac{1}{2}+\epsilon})$

(Оффтоп)

$\tau(n) \approx \leq \exp \frac{\ln n\ln 2}{\ln\ln n}=n^{ \frac{\ln 2}{\ln\ln n}}=O(n^\epsilon)$
Это больше любой степени логарифма. Ага...

upd: проверил для $n\leqslant 10^4$: $\lim\limits_{n\to\infty}\frac{1}{\sqrt{n}}\sum\limits_{d\mid n, d\leqslant \sqrt{n}}d = +\infty$. Так что нужна оценка точнее, чем тривиальная.

[Navid]

Большое спасибо за ваши обсуждения ...
я должен пересмотреть постановку задачи и критерии $ c< 1/2$ должны быть заменены в соответствии с критериями $ c\leq 1/2$

[Navid]

Общая идея этой проблемы на основе corrolary 3 и теоремы 4 настоящей статьи .... и хороший леммы Гараев

real.mtak.hu/8959/1/1003.1997v1.pdf