Распределение степеней по модулю

[Руст]

Рассмотрим натуральное число $n$ и распределение $n$-х степеней по простым модулям $p$. Обозначим через

$$S_n(p)= \frac{\sum_{x=1}^{p-1} \{x^n\} }{p(p-1)/2},$$

где через $\{x^n\}=x^n \pmod p$ обозначено значение остатка при делении $n$-ой степени на $p$.
1. Доказать, что $S_n(p)=S_d(p), \ d=(n,p-1).$
Поэтому в дальнейшем рассматривается только случай, когда $n$ делит $p-1$.
2. Доказать, что $S_n(p)=1$, если $\frac{p-1}{n}$ чётное число.
3. Доказать, что $S_2(p)<1$, если $p\equiv 3 \pmod 4$.
4. Можете ли доказать, что $|S_n-1|<\frac{C}{\sqrt m} , \ m=\frac{p-1}{n}?$ ($C$ константа не зависящая от $p$)

[Феликс Шмидель]

1. Это верно, так как, $x^n=(x^{\frac{n}{d}})^d$, и все $\{x^{\frac{n}{d}}\}$ различны при разных $\{x\}$.

2. Если $\frac{p-1}{n}$-чётное число, то $(-1)^{\frac{p-1}{n}}=1$, поэтому $-1$ является $n$-ой степенью по модулю $p$. Значит числа $x^n$, при $x=1, 2,...,p-1$ можно сгруппировать попарно так, чтобы сумма остатков в каждой паре равнялась $p$.

[maxal]

Феликс Шмидель писал(а):

1. Это верно, так как, $x^n=(x^{\frac{n}{d}})^d$, и все $\{x^{\frac{n}{d}}\}$ различны при разных $\{x\}$.

Не факт, вообще говоря. Кто сказал, что $n/d$ взаимно-просто с $p-1$ ?
Например: $n=4,\ p=3,\ d=2$.

[Феликс Шмидель]

Да, уважаемый maxal, Вы правы. Лучше доказывать это введя первообразный корень $a$ по модулю $p$. Тогда $\{x^n\}=\{a^{ny}\}$, а $\{x^d\}=\{a^{dz}\}$, и между членами двух сумм можно установить взаимно-однозначное соответствие, определяемое соотношением: $ny-dz$ делится на $p-1$.

[maxal]

Доказательство пункта 1 такое:

Подсчитаем сколько решений имеет сравнение $x^n\equiv y\pmod{p}$ для фиксированного $y$. Пусть $z$ - примитивный корень по модулю $p$ так, что $x\equiv z^u\pmod{p}$ и $y\equiv z^v\pmod{p}$. Тогда исходное сранение равносильно сравнению $u n\equiv v\pmod{p-1}$, которое имеет решения только, если $v$ делится на $d$. Пусть $k=v/d$ - целое число, тогда последнее сравнение равносильно $u \frac{n}{d} \equiv k \pmod{\frac{p-1}{d}}$, которое имеет единственное решение относильно $u$ по модулю $\frac{p-1}{d}}$. Поэтому исходное сравнение имеет $d$ решений по модулю $p$ (при условии целочисленности $k$).

Теперь легко видеть, что сумма

$$\sum_{x=1}^{p-1} \{x^n\} = d \sum_{k\mid \frac{p-1}{d}} \{z^{k d}\}$$

не зависит от $n$, а только от $d$, что доказывает равенство $S_n(p)=S_d(p)$.

[Руст]

2. Случай $\frac{p-1}{2}$ чётное число. В этом случае $-1$ является $n$-ой степенью, а следовательно вместе с каждой $n$-ой степенью $y$ $n$-ой степенью является и $p-y$, т.е в среднем $n$-ые степени равны $p/2$, что и доказывает утверждение.
3. Элементарного доказательства я не знаю. Но через подсчёт числа классов дивизоров поля $Q(\sqrt{-p}) это показано например в "теории чисел" Боревича, Шафаревича.
Интересно, что $n=2$ является единственным случаем, когда $S_n(p)$ отклоняется от $1$ только в одну сторону как функция от $p$.
4. Это некоторая гипотеза, подтверждаемая численными экспериментами. Отметим, что Арнольд изучает такие средние фиксировав некоторое $a$ и рассматривая суммы степеней этого числа, вычисленного по модулю $p$ (у него $p$ не обязательно простое). При фиксированном $p$ эти подходы эквивалентны. Однако, когда меняем $p$ фиксировав $a=2$ (как у Арнольда) появится неоправданно высокие отклонения для чисел типа чисел Мерсена.

[juna]

По п. 3 Вы пытаетесь доказать, что для простого числа $p=4n+3$ удвоенная сумма квадратичных вычетов по модулю $p$ всегда меньше $\frac{p(p-1)}{2}$. Пусть $A$ - сумма квадратичных вычетов, $B$ - сумма квадратичных невычетов, тогда для доказательства $2A<\frac{p(p-1)}{2}$ с учетом $A+B=\frac{p(p-1)}{2}$ нужно показать, что $A<B$. Можно попытаться доказать точные формулы - $A=pn$, $B=p(n+1)$.
P.S. Случайно заметил, что Ваша задача (по крайней мере п.2) – это продвинутое обобщение моей задачи о латинских квадратах http://dxdy.ru/viewtopic.php?t=1897

[Феликс Шмидель]

Артамонов Ю.Н. писал(а):

Можно попытаться доказать точные формулы - $A=pn$, $B=p(n+1)$.

Хорошая гипотеза, но она неверна. Например, если $p=23$, то $A=4$, а не $5$.

[juna]

Вы правы, индукция была неполной.
Попытаюсь исправиться: $A=p(n-k)$, $B=p(n+k+1)$.
Интересно исследовать зависимость $k(n)$.

[Руст]

Артамонов Ю.Н. писал(а):

Вы правы, индукция была неполной.
Попытаюсь исправиться: $A=p(n-k)$, $B=p(n+k+1)$.
Интересно исследовать зависимость $k(n)$.

Раз есть интерес к этой теме я дам некоторые известные мне вещи. Вообще говоря эти отклонения существенным образом зависят от чётности $n$, т.е. для простых вида $p=8n+3$ и для $8n+7$ эти отклонения распределены несколько по разному.
Во первых замечу, что

$$A=\frac 12 \sum\limits_{x=1}^{p-1} (1+(\frac xp))x=\frac{p(p-1)}{4} - \frac 12 C, C=-\sum\limits_{x=1}^{p-1} x(\frac xp).$$

Вычислим $C$:

$$ C=-\sum\limits_{x=1}^{(p-1)/2} x(\frac xp)+(p-x)(\frac{p-x}{p})=\sum\limits_{x=1}^{(p-1)/2} (\frac xp)(p-2x)=p\sum_{x=1}^{(p-1)/2} (\frac xp) -(\frac 2p)\sum_{x \ even } x(\frac xp) $$

Отсюда получается

$$C=\frac{pD}{(2-(\frac 2p))},D=\sum\limits_{x=1}^{(p-1)/2} (\frac xp)=(2-(\frac 2p))h}.$$

Здесь $h$ число классов дивизоров для поля $Q(\sqrt{ -p}).$
Таким образом

$$A= p\frac{p-1-2h}{4}.$$

Для h получается, что сверху он ограничен величиной $c\sqrt p$, снизу нет точной оценки но похоже $c_1(p)^{1/2}/\ln(p)$$. Вот максимальные отклонения для $h/ \sqrt p$ при $p=3\pmod 8$ $p=991027$ $h=63$, $p=42143219$ $h=51949$, при $p=7 \pmod 8$ $p=17999503$ $h=795$, $p=58005991$ $h=16631.$
Т.е., чем больше $p$ тем больше отклонение $A/p$ от $(p-1)/4$, но оно ограничено сверху и снизу функцией растущей примерно как $ const \sqrt p $.

[juna]

Таким образом, исходя из Ваших рассуждений, получаем, что $k=\frac{h-1}{2}$ или
$k=\frac{1}{2}({\frac{\sum\limits_{x=1}^{\frac{p-1}{2}}(\frac{x}{p})}{2-(\frac{2}{p})}-1)$
К сожалению, при определении символов Лежандра все равно приходится считать квадратичные вычеты и невычеты.
Теперь становится понятно, откуда у Вас выплыла тема http://dxdy.ru/viewtopic.php?t=1686

[Феликс Шмидель]

Можно поподробнее, каким образом получилось

$$C=\frac{pD}{(2-(\frac 2p))},D=\sum_{x=1}^{(p-1)/2} (\frac xp)=(2-(\frac 2p))h}.$$

?

[Руст]

Вычислим $C$ заметив, что $(\frac{p-x}{p})=-(\frac xp):

$$ C=-\sum\limits_{x=1}^{(p-1)/2} x(\frac xp)+(p-x)(\frac{p-x}{p})=\sum\limits_{x=1}^{(p-1)/2} (\frac xp)(p-2x)=p\sum\limits_{x=1}^{(p-1)/2} (\frac xp) -(\frac 2p)\sum_{2x=y \ even } y(\frac yp)=pD-(\frac 2p)T $$

Учитывая, что

$$C=-\sum\limits_{y -even} y(\frac yp) -\sum\limits_{y -odd} y(\frac yp)=-T+\sum\limits_{y-even} (p-y)(\frac yp)=-2T+p\sum\limits_{y -even} (\frac 2p)=-2T+(\frac 2p)D.$$

Сопоставляя эти два соотношения получаем:

$$T=\frac{pD((\frac 2p)-1)}{2-(\frac 2p)},C=p\frac{D}{2-(\frac 2p)}.$$

То, что $C/p=h$, где $h$ число классов дивизоров для поля $Q(\sqrt{-p}).$ имеется в теории чисел Боревича, Шафаревича.
Таким образом

$$A= p\frac{p-1-2h}{4}.$$

Лучше было ввести инварианты:

$$J_n=\frac m2-\frac{1}{2p} \sum\limits_{y=\{x^n\}} y , \ \ m=\frac{p-1}{n} - odd.$$

Тогда $J_2=h$ положительная величина, распределённая в $c_1\sqrt m<h<c_2>0,c_2>0$. Примерно так же распределены эти инварианты при $n>2$, отличаясь оценкой снизу с отрицательной константой.

[Феликс Шмидель]

Уважаемый Руст, мне непонятны два последних равенства в строчке:

$$C=-\sum_{y -even} y(\frac yp) -\sum_{y -odd} y(\frac yp)=-T+\sum_{y-even} (p-y)(\frac yp)=-2T+p\sum_{y -even} (\frac 2p)=-2T+(\frac 2p)D.$$

В предпоследнем равенстве, непонятно куда исчезло $(\frac yp), а в последнем равенстве, непонятно куда исчез множитель $p$.

[Руст]

Обозначим через $T$ сумму по чётным $y$, а сумму по нечётным выразим через сумму по чётным (так как когда $y$ пробегает чётные вычеты $p-y$ пробегает нечётные):

$$C=-\sum_{y -even} y(\frac yp) -\sum_{y -odd} y(\frac yp)=-T+\sum_{y-even} (p-y)(\frac yp)=-2T+p\sum_{y -even} (\frac yp)=-2T+p(\frac 2p)D.$$

(Я набрал раньше $2$ вместо $y$). Последнее равенство расшифровывается так:

$$\sum_{y-even} (\frac yp)=\sum\limits_{x=1}^{(p-1)/2} (\frac{2x}{p})=(\frac 2p)\sum\limits_{x=1}^{(p-1)/2} (\frac xp) =(\frac 2p)D.$$