2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Множества квадратичных вычетов как объединения двух сдвигов
Сообщение22.10.2017, 18:06 


08/09/13
210
Среди задач (как я понял, не решённых) одного семинара трёхлетней давности я нашёл одну особо меня заинтересовавшую: доказать, что множество квадратичных вычетов в простом поле ${\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$, которые хочется проверить для больших, но хотелось бы для начала выяснить, не изучена ли уже эта область, и не лежат ли все эти вопросы где-то на поверхности, где я их просто не вижу.

 Профиль  
                  
 
 Re: Множества квадратичных вычетов как объединения двух сдвигов
Сообщение23.10.2017, 08:24 


08/09/13
210
А, нет, точная формула вполне себе выводиться, $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})$. Только подскажите, пожалуйста, как это доказывается.

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

 Профиль  
                  
 
 Re: Множества квадратичных вычетов как объединения двух сдвигов
Сообщение23.10.2017, 09:33 


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

 Профиль  
                  
 
 Re: Множества квадратичных вычетов как объединения двух сдвигов
Сообщение23.10.2017, 18:23 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Множества квадратичных вычетов как объединения двух сдвигов
Сообщение23.10.2017, 19:58 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Множества квадратичных вычетов как объединения двух сдвигов
Сообщение23.10.2017, 23:14 


08/09/13
210
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$
Звучит ещё сложнее начального, но хоть какое-то преобразование... И, опять же, результат о возможности выведения точного количества решений здесь ещё более неочевиден и интересен, чем изначальная задача.

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

 Профиль  
                  
 
 Re: Множества квадратичных вычетов как объединения двух сдвигов
Сообщение24.10.2017, 05:01 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Множества квадратичных вычетов как объединения двух сдвигов
Сообщение30.10.2017, 20:30 
Заслуженный участник


08/04/08
8556
Я буду считать, что тут рассматривается вопрос о вычислении числа троек последовательных квадратичных вычетов в $\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$ (и этот факт стал основным поводом для открытия этой темы)
Это интересно, но я не врубился, а как это связано с последовательными тройками квадратичных вычетов? :shock:

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}$ :shock:

(Оффтоп)

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$
Это, конечно, круто, я бы так не смог, но это число решений хоть в лоб, хоть через символы Лежандра м.б. вычислено гораздо проще.

 Профиль  
                  
 
 Re: Множества квадратичных вычетов как объединения двух сдвигов
Сообщение02.11.2017, 13:02 


08/09/13
210
Sonic86 в сообщении #1260547 писал(а):
Это интересно, но я не врубился, а как это связано с последовательными тройками квадратичных вычетов?

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

 Профиль  
                  
 
 Re: Множества квадратичных вычетов как объединения двух сдвигов
Сообщение02.11.2017, 21:20 
Заслуженный участник
Аватара пользователя


11/01/06
3822
Если фиксировать $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}$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group