Наименьший квадратичный невычет

[mathematician123]

Для простого числа $p$ обозначим $f(p)$ наименьший положительный квадратичный невычет по модулю $p$. Докажите, что $f(p) < 2\sqrt{p}$, если $p \equiv 3 \pmod{4}$.

[RIP]

Для любого простого $p>2$ легко доказать, что $f(p)<\sqrt{p+\frac{1}{4}}+\frac{1}{2}$.

[mathematician123]

RIP
Интересно, как? Для $p \equiv 1 \pmod{4}$ я могу доказать, что $f(p) < \sqrt{p}$.

Возьмём некоторый квадратичный невычет $0 < m < p$. Рассмотрим множество пар натуральных чисел $(r, s)$, таких что $0 \le r, s < \sqrt{p}$. Количество таких пар $([\sqrt{p}] + 1)^2 > p$. Значит, найдутся две различные пары $(r_1, s_1)$ и $(r_2, s_2)$, для которых $r_1 + ms_1 \equiv r_2 + ms_2 \pmod{p}$. Откуда $(r_1 - r_2) \equiv m(s_2 - s_1) \pmod{p}$. Так как $m$ является квадратичным невычетом, то $r_1 - r_2$ либо $s_1 - s_2$ также является квадратичным невычетом. Но $-\sqrt{p} < r_1 - r_2, s_1 - s_2 < \sqrt{p}$. Поэтому $|r_1 - r_2|$, либо $|s_1 - s_2|$ является квадратичным невычетом, который меньше чем $\sqrt{p} $.

Но для $p \equiv 3 \pmod{4}$ это доказательство уже не работает, так как -1 является квадратичным невычетом.

[RIP]

Пока не буду писать док-во (оно короткое и простое), чтобы желающие могли подумать.

[Dendr]

RIP в сообщении #1591545 писал(а):

Для любого простого $p>2$ легко доказать, что $f(p)<\sqrt{p+\frac{1}{4}}+\frac{1}{2}$.

Машинная проверка говорит, что еще сильнее: $f(p)>\sqrt{p}$ только для $p=3, 7, 23$. Но можно ли вот это доказать - уже вопрос.

[Iosafat]

Dendr А код покажите?

[Dendr]

Ну как код... за минуту на коленке. И сильно далеко не заглядывал.

#include <iostream>
using namespace std;
int f(int p);
bool isPrime(int n);
int main()
{
    for (int k=3; k<10000; k++)
        if (isPrime(k))
    {
        int F=f(k);
        if (F*F>=k) cout<<k<<"\t"<<F<<"\t***\t"<<F*F<<" > "<<k<<endl;
    }
    return 0;
}
int f(int p)
{
    int half=p/2;
    int arr[p];
    for (int i=0; i<p; i++)
    {
        arr[i]=0;
    }
    for (int j=0; j<=half; j++)
    {
        int r=(j*j)%p;
        arr[r]=1;
    }
    for (int i=0; i<p; i++)
    {
        if (arr[i]==0) return i;
    }
}
bool isPrime(int n)
{
    if (n<2) return false;
    if (n<4) return true;
    for (int i=2; i*i<=n; i++)
        if (n%i==0) return false;
    return true;
}

[Iosafat]

Dendr Вы, пожалуйста только не ругайтесь.
g++ ./main.cpp

./main.cpp: In function ‘int f(int)’:
./main.cpp:32:1: warning: control reaches end of non-void function [-Wreturn-type]
   32 | }
      | ^

[RIP]

(оценки)

Из обобщённой гипотезы Римана следует, что $f(p)<2(\ln p)^2$.
Наилучшая доказанная оценка (D.A. Burgess): \large$f(p)<C(\varepsilon)p^{\frac{1}{4\sqrt{e}}+\varepsilon}$ для любого $\varepsilon>0$ (более точной оценки не помню).
Пример явной доказанной оценки (E. Treviño): $f(p)<1.1p^{1/4}\ln p$. Но это всё сложно.
Не очень сложно доказывается оценка \large$f(p)<Cp^{\frac{1}{2\sqrt{e}}}(\ln p)^{\frac{2}{\sqrt{e}}}$ (И.М. Виноградов). Но всё равно нужно повозиться.
Упомянутая мной оценка доказывается в пару строчек.

[Iosafat]

RIP Ну, не томите.

[mathematician123]

Сейчас анализировал случай $p \equiv 1 \pmod{4}$. Удалось доказать такое утверждение: если $p \equiv 1 \pmod{4}$, то в интервале $(1, \sqrt{p})$ содержится как минимум $\frac{p-1}{8\sqrt{p}}$ квадратичных невычетов.

Численные эксперименты тоже довольно интересные. Если искать простые числа, для которых в интервале $(1, \sqrt{p}) $ содержится меньше чем $\frac{\sqrt{p}}{3}$ квадратичных невычетов, то видно, что с какого-то момента компьютер начинает выдавать только простые вида $4k+3$. А если искать так, чтобы квадратичных невычетов было меньше чем $\frac{\sqrt{p}} {4}$, то начиная с примерно 38000 они вообще перестают появляться.

[RIP]

Известна оценка (Burgess): Для любого простого числа $p>2$ и для любых $M\in\mathbb{Z}$, $N\in\mathbb{N}$, $r\in\mathbb{N}$ верно

$$\left\lvert\sum_{x=M+1}^{M+N}\left(\frac{x}{p}\right)\right\rvert<CN^{1-\frac{1}{r}}p^{\frac{r+1}{4r^2}}(\ln p)^{\frac{1}{r}},$$

где $C$ — абсолютная постоянная ($C=20$ вроде бы достаточно). Так что на любом промежутке длины $N>p^{1/4+\varepsilon}$ квадратичных вычетов и невычетов асимптотически поровну.

[mathematician123]

RIP в сообщении #1591693 писал(а):

Так что на любом промежутке длины $N>p^{1/4+\varepsilon}$ квадратичных вычетов и невычетов асимптотически поровну.

Сейчас посчитал подальше. Последнее число вида $4k + 1$, для которого в интервале $(1, \sqrt{p}) $ находится меньше чем $\frac{\sqrt{p}}{3} $ невычетов равно примерно 38000. А последнее число вида $4k + 3$ - 1413551. И до трёх миллионов больше таких чисел не нашлось. Есть ли объяснение этому? То есть количество невычетов в интервале $(1, \sqrt{p})$ в случае $p \equiv 3 \pmod{4}$ медленнее стремится к $\frac{\sqrt{p}}{2}$, чем в случае $p \equiv 1 \pmod{4}$.

[RIP]

mathematician123 в сообщении #1591701 писал(а):

Есть ли объяснение этому?

Наверно, есть, но я не знаю.

[RIP]

На всякий случай напишу доказательство, которое я имел в виду.

Пусть $n=f(p)$. Тогда $n\lceil p/n\rceil\in(p,p+n)$ — квадратичный вычет. Следовательно, $\lceil p/n\rceil$ — квадратичный невычет, откуда $n\leqslant\lceil p/n\rceil<p/n+1$. Можно даже немного уточнить:

$$n^2-n<p \implies n^2-n+1\leqslant p \implies n\leqslant\sqrt{p-\frac{3}{4}}+\frac{1}{2}.$$

Если $p\equiv1\pmod{4}$, то можно рассмотреть $n\lfloor p/n\rfloor\in(p-n,p)$ и аналогично получить $n<p/n$.