Множества квадратичных вычетов как объединения двух сдвигов

[fractalon]

Среди задач (как я понял, не решённых) одного семинара трёхлетней давности я нашёл одну особо меня заинтересовавшую: доказать, что множество квадратичных вычетов в простом поле ${\mathbb F}_p$ не представимо в виде $\left\lbrace{a+b: a \in A, b \in B}\right\rbrace$ для $|A| \ge 2, |B| \ge 2$.
Я решил попробовать подступиться к ней от противного для самого простого случая $|B|=2$, то есть попробовать представить как можно большее подмножество квадратичных вычетов в виде $A \cup (A+x)$. Тут-то всё и началось.
Я взялся на компьютере посчитать $c_x^{(p)}=\max {\left\lbrace{ |A+(A+x)| : A \subset {\mathbb F}_p, A+(A+x) \subset Q_p }\right\rbrace}$, где $Q_p \subset {\mathbb F}_p$ - множество квадратичных вычетов.
Для простых вида $p=4k+3$ значения $c_x^{(p)}$ оказались независимыми от $x$, а для $p=4k+1$ значения $c_x^{(p)}$ незначительно (но не на константу) больше для $x$, являющихся квадратичными вычетами. Ну да это ладно, я не понимаю, почему это именно так, но ясно, что это связано с (не)квадратичностью $p-1$. Впрочем, почему для $p=4k+1$ все значения $c$ одинаквые - не понимаю. Если это очевидно, пожалуйста, объясните.

Главное другое - я, естественно, стал считать, чему же равно это самое $c^{(p)} = c_x^{(p)}$ для разных $p=4k+3$. Нащупать точные формулы для них через какие-то рациональные выражения не получилось, зато однозначно видно, что $\frac{c^{(p)}}{p} \to \frac{3}{8}$ при $p \to \infty$ (и этот факт стал основным поводом для открытия этой темы), причём стремление очень быстрое, чуть ли не по гиперболе. Есть ещё один забавный факт - для простых вида $p=8k+3$ значения $c^{(p)}$ монотонно убывают (проверял до $p<10^5$, чуть больше чем $2000$ простых), и то же самое для простых вида $8k+7$. Но для всего множества $p=4k+3$ график $c^{(p)}$ бесконечно колеблеться то вверх то вниз (в смысле "производной", если можно так выразиться).

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

[fractalon]

А, нет, точная формула вполне себе выводиться, $c^{(p)} = \left\lfloor{ \frac{3p+7}{8} }\right\rfloor$. Тем актуальнее становится вопрос - для таких точных формул наверняка должны быть элементарные доказательства.

Для количества решений уравнения $x^2-y^2 \equiv c \pmod p$ (то есть для размера множества $A$) удалось через тригонометрические суммы получить точное значение,
$\sum \limits_{t=0}^{p-1} {e_p (-tc) \sum \limits_{a,b} e_p((a-b)(a+b)t)} = \sum \limits_{t=0}^{p-1} {e_p (-tc) \sum \limits_u {\sum \limits_{v} {e_p (uvt)}}} = p^2 + \sum \limits_{t =1}^{p-1} {e_p (-t) p}={p^2}-p$,
так что ЧРУ получается точно $\frac{p+5}{4}$ для $p=4k+3$ (и тут, кстати, возникает эта самая маленькая зависимость от квадратичности -1), но для размера самой суммы множеств $A \cup (A+c)$ такой же трюк провернуть пока не получается.

Понял, что вопрос о $A \cup (A+C)$ сводится к числу решений системы уравнений
$a^2-b^2=1$
$a^2-c^2=2$
А он в свою очередь к числу решений
$xy=1$
$uv=2$
$x+\frac{1}{x}=z+\frac{1}{z}$
И тут, как я понял, всё должно быть просто - кажется, числа $x+\frac{1}{x}$ уникальны для пары $(x;\frac{1}{x})$. Только подскажите, пожалуйста, как это доказывается.

А, всё, понял, это банальная теорема Виета. Простите за шум без весомого повода. Тему можно закрывать.

[fractalon]

Впрочем, нет, уникальность $x+\frac{1}{x}$ ничего не даёт к ЧРУ типа $x+\frac{1}{x} \equiv z+\frac{2}{z}$, где знаменатели разные (я там опечатался случано и дальше потянул эту опечатку). А как такое можно было бы "взломать"?

[vpb]

У Вас в самом первом посте в 4-й строке напечатано $A\cup(A+x)$, а в 5-й $|A+(A+x)|$. Так и должно быть, или это опечатка?

[vpb]

Вот что в голову пришло. Я не совсем понял, какую именно задачу ТС рассматривает. Ясно, однако, что эта задача очень близка к такому примерно вопросу: сколько есть (квадратичных) вычетов $x$ по модулю $p$ , для которых оба числа $x+1$ и $x-1$ --- тоже вычеты? А этот вопрос можно переформулировать так: сколько есть точек на пространственной кривой над ${\mathbb F}_p$, заданной системой уравнений $y^2=x^2+1,\ z^2=x^2-1$ ? Как это решать, я, собственно, не знаю, сам не специалист, но какие книги надо читать для этого, примерно знаю. Во-первых, по элементарной теории чисел И.М. Виноградов "Основы теории чисел", Бухштаб "Теория чисел", есть и много других. По алгебраической теории чисел Боревич, Шафаревич "Теория чисел", гл.1. По основам алгебраической геометрии Шафаревич "Основы алгебраической геометрии", М.Рид "Алгебраическая геометрия для всех", Острик и Цфасман название не помню, про коники и эллиптические кривые популярные лекции. (возможно есть и более современные популярные изложения основ АГ, я не в курсе). Есть еще Н.Коблиц, р-адические числа, р-адический анализ, и дзета-функции (сам не читал). Есть еще книга С.А.Степанова, название совсем не помню. Вот вроде всё на русском языке, что в голову приходит.
Еще могу упомянуть, что задача эта, в целом, разрешимая. Сколько есть точек на кривой над конечным полем --- с этим разобрался еще А.Вейль где-то около 1940 г.

[fractalon]

vpb в сообщении #1258338 писал(а):

У Вас в самом первом посте в 4-й строке напечатано $A\cup(A+x)$, а в 5-й $|A+(A+x)|$

Опечатка, в пятой тоже должно быть $A \cup (A+x)$

vpb в сообщении #1258369 писал(а):

Вот что в голову пришло. Я не совсем понял, какую именно задачу ТС рассматривает. Ясно, однако, что эта задача очень близка к такому примерно вопросу: сколько есть (квадратичных) вычетов $x$ по модулю $p$ , для которых оба числа $x+1$ и $x-1$ --- тоже вычеты?

Да-да, напрямую связано. С этой стороны мой вопрос можно переформулировать так: для данного $c$ сколько есть квадратичных вычетов $x$ таких, что либо $x-c$ либо $x+c$ (либо они оба) - тоже квадратичный вычет.
Эту задачу пока получилось свести к числу решений уравнения $x+\frac{c}{x}=y+\frac{2c}{y}$ уже не в квадратичных вычетах, а вообще в любых вычетах. Её через замену $y=xt$ легко свести к вопросу о числе квадратичных вычетов среди чисел вида $x+\frac{2c^2}{x}-3c$. Там тоже по количеству всё довольно ровно получается, точную формулу, думаю, можно вывести.
То есть сейчас достаточно рассмотреть вопрос: а для данных $s,t \in {\mathbb F}_p$ сколько квадратичных вычетов есть среди чисел $x+\frac{s}{x}+t$
Звучит ещё сложнее начального, но хоть какое-то преобразование... И, опять же, результат о возможности выведения точного количества решений здесь ещё более неочевиден и интересен, чем изначальная задача.

За список книг спасибо. Я в основном теорией чисел в математике только и интересуюсь, так что Виноградов и Бухштаб в моей копилке давно уже лежат. А вот про "кривые" совсем ничего не знаю, несколько новых книг увидел, буду смотреть. Но всё-таки мне кажется, что эту задачу можно решить без каких-то мощных общих многочленных методов, а только в рамках квадратов и обратных величин.

[vpb]

Не знаю, может, и можно. Я не специалист, а думать сейчас над этим вопросом специально времени нет.

[Sonic86]

Я буду считать, что тут рассматривается вопрос о вычислении числа троек последовательных квадратичных вычетов в $\mathbb{F}_p$.

fractalon в сообщении #1258033 писал(а):

но хотелось бы для начала выяснить, не изучена ли уже эта область

http://onlinelibrary.wiley.com/doi/10.1112/jlms/s1-6.1.49/abstract
Вот Jacobsthal этим тоже занимался в 1906 году и Davenport и еще какая-то стая товарищей, больше ничего не нагуглил (но я сильно не пытался)
Всю статью скачать не дает
Остальные статьи даже 1-ю страницу не дает посмотреть - только за бабло. Так что в итоге точно узнать нельзя.

Можно легко выписать формулу для расчета через символы Лежандра, но там естественным образом вылазит $\sum\limits_{k=1}^{p-1}\left(\frac{k^3-k}{p}\right)$ (она же $\sum\limits_{k=1}^{p-1}\left(\frac{k-k^{-1}}{p}\right)$) и как ее считать - непонятно. В Айрленде и Роузене некоторые суммы с символами Лежандра обычно сводятся к гауссовым суммам, можно дальше копать по ссылкам, если это есть в открытом виде, конечно.

fractalon в сообщении #1258033 писал(а):

Главное другое - я, естественно, стал считать, чему же равно это самое $c^{(p)} = c_x^{(p)}$ для разных $p=4k+3$. Нащупать точные формулы для них через какие-то рациональные выражения не получилось, зато однозначно видно, что $\frac{c^{(p)}}{p} \to \frac{3}{8}$ при $p \to \infty$ (и этот факт стал основным поводом для открытия этой темы)

Это интересно, но я не врубился, а как это связано с последовательными тройками квадратичных вычетов?

upd:

fractalon в сообщении #1258033 писал(а):

зато однозначно видно, что $\frac{c^{(p)}}{p} \to \frac{3}{8}$ при $p \to \infty$

А как вообще Вы это получили, если очевидно, что $c^p_0=\max \left\{ |A+(A+0)| : A \subset {\mathbb F}_p, A+(A+0) \subset Q_p \right\}=$ $\max\limits_A \left\{ |A| : A \subset Q_p \right\}=\frac{p+1}{2}$

(Оффтоп)

fractalon в сообщении #1258198 писал(а):

Для количества решений уравнения $x^2-y^2 \equiv c \pmod p$ (то есть для размера множества $A$) удалось через тригонометрические суммы получить точное значение,
$\sum \limits_{t=0}^{p-1} {e_p (-tc) \sum \limits_{a,b} e_p((a-b)(a+b)t)} = \sum \limits_{t=0}^{p-1} {e_p (-tc) \sum \limits_u {\sum \limits_{v} {e_p (uvt)}}} = p^2 + \sum \limits_{t =1}^{p-1} {e_p (-t) p}={p^2}-p$

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

[fractalon]

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

Это интересно, но я не врубился, а как это связано с последовательными тройками квадратичных вычетов?

Объединение всех последовательных троек имеет (асимптотически) мощность около $\frac{3}{8} p$

[RIP]

Если фиксировать $c\in\{1,2,\dotsc,p-1\}$, $\varepsilon_{0},\varepsilon_{1},\varepsilon_{-1}\in\{\pm1\}$, то количество $x\in\mathbb{F}_p$, таких что $\left(\frac{x}{p}\right)=\varepsilon_{0}$, $\left(\frac{x+c}{p}\right)=\varepsilon_{1}$, $\left(\frac{x-c}{p}\right)=\varepsilon_{-1}$, равно

\[\delimitershortfall=-1pt \frac{1}{8}\sum_{x\in\mathbb{F}_p\setminus\{0,\pm c\}}\left(1+\varepsilon_{0}\left(\frac{x}{p}\right)\right)\left(1+\varepsilon_{1}\left(\frac{x+c}{p}\right)\right)\left(1+\varepsilon_{-1}\left(\frac{x-c}{p}\right)\right). \]

При этом полная сумма (по всем $x\in\mathbb{F}_p$) почти считается:

\[\begin{aligned}\delimitershortfall=-1pt &\sum_{x\in\mathbb{F}_p}\left(1+\varepsilon_{0}\left(\frac{x}{p}\right)\right)\left(1+\varepsilon_{1}\left(\frac{x+c}{p}\right)\right)\left(1+\varepsilon_{-1}\left(\frac{x-c}{p}\right)\right)\\ &\qquad=p-\varepsilon_{0}\varepsilon_{1}-\varepsilon_{0}\varepsilon_{-1}-\varepsilon_{1}\varepsilon_{-1}+\varepsilon_{0}\varepsilon_{1}\varepsilon_{-1}\sum_{x=0}^{p-1}\left(\frac{x\left(x^2-c^2\right)}{p}\right). \end{aligned}\]

Про суммы Якобшталя (или Якобсталя) $S(a)=\sum_{x=0}^{p-1}\left(\frac{x\left(x^2+a\right)}{p}\right)$ всё (или почти всё) известно. Если $p\equiv-1\pmod{4}$, то $S(a)=0$ для всех $a\in\mathbb{Z}$. Пусть $p\equiv1\pmod{4}$. Тогда:
1) $S\left(ab^2\right)=\left(\frac{b}{p}\right)S(a)$ для любых $a,b\in\mathbb{Z}$;
2) если $\left(\frac{a}{p}\right)=1$, $\left(\frac{b}{p}\right)=-1$, то $\frac{1}{2}S(a),\frac{1}{2}S(b)$ — это целые числа, такие что

\[ p=\left(\frac{1}{2}S(a)\right)^2+\left(\frac{1}{2}S(b)\right)^2. \]

Поскольку представление $p$ в виде суммы двух квадратов единственно (с точностью до тривиальных симметрий), то для $S\left(-c^2\right)=(-1)^{(p-1)/4}\left(\frac{c}{p}\right)S(1)$ есть не более четырёх возможностей. Какое именно значение нужно выбирать, сходу не помню. Помню только, что $S(1)\equiv-\dbinom{\frac{p-1}{2}}{\frac{p-1}{4}}\pmod{p}$. Можно попробовать поискать ответ в книжке B.C. Berndt, R.J. Evans, K.S. Williams «Gauss and Jacobi sums». В любом случае всегда $\bigl\lvert S(a)\bigr\rvert<2\sqrt{p}$.