Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 491, № 1, стр. 19-22

О ПАРАМЕТРЕ СТОХАСТИЧНОСТИ КВАДРАТИЧНЫХ ВЫЧЕТОВ

М. Р. Габдуллин 1*

1 Математический ннститут им. В.А. Стеклова Российской академии наук
Москва, Россия

* E-mail: gabdullin.mikhail@yandex.ru

Поступила в редакцию 14.11.2019
После доработки 20.11.2019
Принята к публикации 12.12.2019

Полный текст (PDF)

Аннотация

Следуя В.И. Арнольду, определим параметр стохатичности S(U) множества $U \subseteq {{\mathbb{Z}}_{M}}$ как сумму квадратов расстояний между соседними элементами множества U. В работе изучается параметр стохастичности множества ${{R}_{M}}$ квадратичных вычетов по модулю M. Мы сравниваем $S({{R}_{M}})$ со средним значением $s(k) = s(k,M)$ величины S(U) по всем k-элементным подмножествам $U \subseteq {{\mathbb{Z}}_{M}}$. Доказано, что: а) для множества модулей положительной нижней плотности справедливо неравенство S(RM) < $s\left( {\left| {{{R}_{M}}} \right|} \right)$; б) для бесконечно многих модулей $S({{R}_{M}}) > s\left( {\left| {{{R}_{M}}} \right|} \right)$.

Ключевые слова: квадратичные вычеты, параметр стохастичности

Рассмотрим произвольное множество U в кольце вычетов ${{\mathbb{Z}}_{n}}$. Пусть

$U = {\text{\{ }}0 \leqslant {{u}_{1}} < {{u}_{2}} < \ldots < {{u}_{k}} < n{\text{\} }}$
и ${{u}_{{k + 1}}} = n + {{u}_{1}}$ (тем самым мы “склеили” $[0,n)$ в окружность). Для исследования случайности распределения точек множества U среди всех вычетов В.И. Арнольд (см. [1, §9]) вводит параметр стохастичности

$S(U) = \sum\limits_{i = 1}^k {{{{({{u}_{{i + 1}}} - {{u}_{i}})}}^{2}}} .$

Несложно видеть, что S(U) минимально, когда точки идут через равные интервалы, и максимально, когда все собираются в одном месте. Поэтому слишком малые или слишком большие значения S(U) свидетельствуют о неслучайном поведении множества U. Имея в виду указанные два экстремальных случая, мы будем говорить, что для точек множества U имеет место отталкивание (или притяжение), если S(U) меньше (соответственно больше) среднего значения параметра стохастичности среди всех k-элементных подмножеств ${{\mathbb{Z}}_{n}}$.

М.З. Гараев, С.В. Конягин и Ю.В. Малыхин [2] обобщают параметр стохастичности. Пусть q > 0; положим

${{S}_{q}}(U) = \sum\limits_{i = 1}^k {{{{({{u}_{{i + 1}}} - {{u}_{i}})}}^{q}}} .$

Обозначим через ${{N}_{l}}(U)$, $l \geqslant 1$, число лакун длины l во множестве U, т.е. количество таких элементов $x \in {{\mathbb{Z}}_{n}}$, что $x \in U,x + 1,\; \ldots ,\;x + l - 1 \notin U$, $x + l \in U$. Тогда

(1)
${{S}_{q}}(U) = \sum\limits_{l \geqslant 1} {{{N}_{l}}} (U){{l}^{q}}$
(и, в частности, $S(U) = \sum\limits_{l \geqslant 1}^{} {{{N}_{l}}(U){{l}^{2}}} $). Авторы доказывают, что если $\left| U \right| = k < n$ и $\frac{k}{{\sqrt n }} \to \infty $, то для среднего значения ${{s}_{q}}(k,n)$ величины ${{S}_{q}}(U)$ для множества U из k элементов справедливо равенство

${{s}_{q}}(k,n) = \frac{{{{k}^{2}}}}{n}\sum\limits_{l = 1}^\infty {{\left( {1 - \frac{k}{n}} \right)}^{{l - 1}}}{{l}^{q}}(1 + o(1)).$

Отметим, что эта асимптотическая формула согласуется со следующими эвристическими соображениями: вероятность того, что некоторая точка случайного множества из k элементов будет началом лакуны длины l, равна ${{\left( {\frac{k}{n}} \right)}^{2}}{{\left( {1 - \frac{k}{n}} \right)}^{{l - 1}}}$, и поэтому в среднем величина ${{N}_{l}}(U)$ должна быть близка к $\tfrac{{{{k}^{2}}}}{n}{{\left( {1 - \frac{k}{n}} \right)}^{{l - 1}}}$.

Кроме того, авторы отмечают, что в случае q = 2 величину $s(k): = {{S}_{2}}(k,M)$ можно выписать явно.

Предложение 1. Имеем

$s(k) = \frac{{M(2M - k + 1)}}{{k + 1}}.$

В работе [2] оцениваются величины ${{S}_{q}}(G)$ в случае, когда n = p – простое число, а множество $G$ является подгруппой ${{G}_{t}} \subset \mathbb{Z}_{p}^{ * }$ порядка $t$, т.е. состоит из d-х степеней чисел от 1 до p – 1, где d = = $\tfrac{{p - 1}}{t}$. Основным результатом работы [2] является

Теорема A. Существует константа c > 0 такая, что при $q \in (0,4)$ и $d \leqslant exp(c\sqrt {{\text{log}}p} )$ справедлива асимптотическая формула

${{S}_{q}}({{G}_{t}}) = {{S}_{q}}\left( {\frac{{p - 1}}{d}} \right)(1 + o(1)),\quad p \to \infty .$

Таким образом, большие мультипликативные подгруппы $\mathbb{Z}_{p}^{ * }$ с точки зрения поведения величины ${{S}_{q}}(G)$ близки к случайным множествам соответствующего размера.

В настоящей работе изучается параметр стохастичности для множества ${{R}_{M}}$ квадратичных вычетов по модулю M. Мы доказываем отталкивание квадратичных вычетов для множества модулей положительной нижней плотности (здесь и везде далее мы имеем в виду нижнюю асимптотическую плотность, т.е. величину d(A) = , $A \subseteq \mathbb{N}$), а также их притяжение для бесконечно многих модулей. Перейдем к точным формулировкам. Пусть c0 и C0 – абсолютные положительные постоянные, причем c0 достаточно мало, а C0 достаточно велико. Обозначим через $\Omega $ множество чисел M таких, что $M = Am$, где $m = {{p}_{1}} \ldots {{p}_{t}}$, причем $t \geqslant 0.4{\text{loglog}}M$ и ${{p}_{1}} < {{p}_{2}} < \ldots < {{p}_{t}}$ – различные простые числа, большие ${{2}^{{{{C}_{0}}t}}}$, а число $A$ бесквадратно, $(A,m) = 1$ и $A \leqslant {{2}^{{{{c}_{0}}t}}}$.

Основным результатом данной работы является

Теорема 1. Существует абсолютная постоянная c > 0 такая, что при $M \in \Omega $ имеет место асимптотическая формула

(2)
$S({{R}_{M}}) = m{{2}^{{t + 1}}}{{A}^{2}}{{\left| {{{R}_{A}}} \right|}^{{ - 1}}} - {{A}^{2}}{{\left| {{{R}_{A}}} \right|}^{{ - 1}}}m + E,$
где

$\begin{gathered} E \ll m{{2}^{{3t}}}{{A}^{4}}p_{1}^{{ - c}} + m{{A}^{2}}\left| {{{R}_{A}}} \right|{{2}^{{ - t}}} = o(m), \\ M \to \infty ,\quad M \in \Omega . \\ \end{gathered} $

Кроме того, множество $\Omega $ имеет положительную нижнюю плотность.

С другой стороны, для модулей $M \in \Omega $ предложение 1 дает нам

(3)
$\begin{gathered} s\left( {\left| {{{R}_{M}}} \right|} \right) = m{{2}^{{t + 1}}}{{A}^{2}}{{\left| {{{R}_{A}}} \right|}^{{ - 1}}} - \\ - \,Am + O({{A}^{2}}{{\left| {{{R}_{A}}} \right|}^{{ - 1}}}m{{2}^{{2t}}}p_{1}^{{ - 1}}). \\ \end{gathered} $

Таким образом, главные члены в полученных асимптотических формулах $S({{R}_{M}})$ и $s\left( {\left| {{{R}_{M}}} \right|} \right)$ совпадают. Отсюда мы получаем аналог теоремы А.

Следствие 1. Имеем

$S({{R}_{M}}) = s\left( {\left| {{{R}_{M}}} \right|} \right)(1 + o(1)),\quad M \to \infty ,\quad M \in \Omega .$

Сравнивая вторые члены в (2) и (3), мы улавливаем отталкивание квадратичных вычетов.

Следствие 2. При всех достаточно больших $M \in \Omega $ с $A \geqslant 3$ справедливо

$S({{R}_{M}}) < s\left( {\left| {{{R}_{M}}} \right|} \right).$

Кроме того, для модулей вида $M = Ap$, где p – простое и $(A,p) = 1$, мы можем написать асимптотику с меньшим остаточным членом, что позволяет нам установить притяжение квадратичных вычетов по бесконечно многим модулям.

Теорема 2. Пусть $M = Ap$, $(A,p) = 1$. Тогда

$S({{R}_{M}}) = 2{{f}_{A}}(0.5)p + O({{A}^{4}}{{p}^{{1 - c}}}),$
где fAрациональная функция, определяемая числом A.

Коэффициенты рациональной функции fA можно выписывать явно. Пусть ${{s}_{1}},\; \ldots ,\;{{s}_{{|{{R}_{A}}|}}}$ – последовательные расстояния между квадратичными вычетами по модулю $A$, пронумерованные вычетами по модулю $\left| {{{R}_{A}}} \right|$. Тогда

${{f}_{A}}(y) = \frac{{F(y)}}{{Q(y)}},$
где $Q(y) = {{Q}_{A}}(y) = 1 + y + \; \ldots \; + {{y}^{{|{{R}_{A}}| - 1}}}$, а F(y) = FA(y) = = $\sum\limits_{k = 0}^{|{{R}_{A}}|} {{{\beta }_{k}}} {{y}^{k}}$ – возвратный многочлен с коэффициентами ${{\beta }_{0}}\, = \,{{\beta }_{{|{{R}_{A}}|}}}\, = \,\sum\limits_i {s_{i}^{2}} $ и ${{\beta }_{k}}\, = \,2\sum\limits_{i = 1}^{|{{R}_{A}}|} {{{s}_{i}}{{s}_{{i + k}}}} $ при 0 < k < $\left| {{{R}_{A}}} \right|$ (мы считаем, что индексы i чисел ${{s}_{i}}$ вычисляются по модулю $\left| {{{R}_{A}}} \right|$). Отметим, что поведение функции fA в окрестности точки y = 1 является определяющим фактором для притяжения или отталкивания квадратичных вычетов.

Из предложения 1 (или из (3) при t = 1) для модулей того же вида находим

$s\left( {\left| {{{R}_{M}}} \right|} \right) = \left( {\frac{{4{{A}^{2}}}}{{\left| {{{R}_{A}}} \right|}} - A} \right)p + O({{A}^{2}}{{\left| {{{R}_{A}}} \right|}^{{ - 1}}}).$

Численная проверка показывает, что

$2{{f}_{A}}(0.5) < \frac{{4{{A}^{2}}}}{{\left| {{{R}_{A}}} \right|}} - A$
при всех $3 \leqslant A \leqslant 100$, $A \ne 89$, и
$2{{f}_{A}}(0.5) > \frac{{4{{A}^{2}}}}{{{\text{|}}{{R}_{A}}{\text{|}}}} - A$
при A = 89. Таким образом, из теоремы 2 вытекает следующее утверждение.

Следствие 3. Имеем

$\mathop {\underline {\lim } }\limits_{M \to \infty } \frac{{S({{R}_{M}})}}{{s\left( {\left| {{{R}_{M}}} \right|} \right)}} < 1 < \mathop {\overline {\lim } }\limits_{M \to \infty } \frac{{S({{R}_{M}})}}{{s\left( {\left| {{{R}_{M}}} \right|} \right)}}.$

Из неравенства Коши–Буняковского следует, что

$\mathop {\overline {\lim } }\limits_{M \to \infty } \frac{{S({{R}_{M}})}}{{s\left( {\left| {{{R}_{M}}} \right|} \right)}} \geqslant 0.5.$

В то же время мы не знаем, конечен ли верхний предел $\mathop {\overline {\lim } }\limits_{M \to \infty } \tfrac{{S({{R}_{M}})}}{{s\left( {\left| {{{R}_{M}}} \right|} \right)}}$. Отметим, что в недавней работе Ф. Арьяна [3] доказано, что в случае бесквадратных M справедлива оценка

$S({{R}_{M}}) \ll M \cdot {{2}^{{\omega (M)}}}logM\prod\limits_{p|M} {\left( {1 + \frac{1}{{\sqrt p }}} \right)} \left( {1 - \frac{1}{p}} \right).$

Обсудим основные идеи доказательства теоремы 1 (теорема 2 доказывается аналогично, но технически несколько проще). Зафиксируем $\alpha \in \left( {0,\tfrac{1}{{10}}} \right)$ и достаточно малое число ${{\varepsilon }_{0}} > 0$. Положим ${{d}_{1}}: = \tfrac{{\alpha A}}{{2\left| {{{R}_{A}}} \right|}}{{2}^{t}}{\text{log}}{{p}_{1}}$ и ${{d}_{2}}: = \tfrac{A}{{\left| {{{R}_{A}}} \right|}}p_{1}^{{{{\varepsilon }_{0}}}}$. Мы записываем величину $S({{R}_{M}})$ в виде $\sum\limits_{l \geqslant 1} {{{N}_{l}}} ({{R}_{M}}){{l}^{2}}$ (см. (1)) и разбиваем эту сумму на три части. Далее мы находим асимптотику для вклада от малых лакун длины $l \leqslant {{d}_{1}}$ в терминах функции fA, определяемой числом A, и показываем, что вклад средних (длины $l \in ({{d}_{1}},{{d}_{2}}]$) и больших (длины $l > {{d}_{2}}$) лакун соответственно асимптотически мал; более точно, мы доказываем, что

$S({{R}_{M}}) = m \cdot {{2}^{t}}{{f}_{A}}({{y}_{t}}) + O(m \cdot {{2}^{{4t}}}{{A}^{4}}p_{1}^{{ - {{c}_{1}}}}),$
где ${{c}_{1}} > 0$ – некоторая абсолютная постоянная и ${{y}_{t}} = 1 - {{2}^{{ - t}}}$. Наконец, мы показываем, что fA(1) = = $2{{A}^{2}}{{\left| {{{R}_{A}}} \right|}^{{ - 1}}}$, $f_{A}^{'}(1) = {{A}^{2}}{{\left| {{{R}_{A}}} \right|}^{{ - 1}}}$ и $f_{A}^{{''}}(y) \ll {{A}^{2}}\left| {{{R}_{A}}} \right|$ при $y \in ({{y}_{t}},1)$ в предположении $\left| {{{R}_{A}}} \right| \ll {{2}^{t}}$. После этого первое утверждение теоремы 1 получается разложением функции fA в ряд Тейлора в окрестности точки y = 1. Наконец, тот факт, что множество $\Omega $ имеет положительную нижнюю плотность, доказывается с помощью некоторых комбинаторных рассуждений и методов решета.

Отметим, что для нахождения асимптотики для вклада от малых лакун можно использовать предельное распределение расстояний между квадратичными вычетами, которое было найдено в работе П. Курлберга и З. Рудника [4] для бесквадратных модулей и в работе П. Курлберга [5] для произвольных модулей. Пусть 0 = u1 < u2 < ... < ${{u}_{{{{R}_{M}}}}}$ < M – множество квадратичных вычетов по модулю M. Следующий результат был получен в работе [5].

Теорема B. При $t \geqslant 0$ имеем

$\begin{gathered} {{\left| {{{R}_{M}}} \right|}^{{ - 1}}}\# \{ j \in \{ 1, \ldots ,\left| {{{R}_{M}}} \right|\} :{{u}_{j}} - {{u}_{{j - 1}}} > tM{{\left| {{{R}_{M}}} \right|}^{{ - 1}}}\} = \\ = {{e}^{{ - t}}} + o(1) \\ \end{gathered} $
при $\omega (M) \to \infty $, причем эта оценка равномерна при $t \in [0,{{t}_{0}}]$ для любого фиксированного ${{t}_{0}} > 0$.

Тем не менее, слагаемое o(1) в правой части помешает нам найти второй член в асимптотике для $S({{R}_{M}})$; поэтому мы используем другие соображения (и рассматриваем модули специального вида).

Доказательство теоремы 1 позволяет также получить нижнюю оценку (довольно слабую) на плотность множества $\Omega $; мы не стремились выписать ее явно и оптимизировать.

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

ИСТОЧНИК ФИНАНСИРОВАНИЯ

Исследование выполнено за счет гранта Российского научного фонда (проект 19–11–00001).

Список литературы

  1. Арнольд В.И. Группы Эйлера и арифметика геометрических прогрессий. М.: МЦНМО, 2003.

  2. Гараев М.З., Конягин С.В., Малыхин Ю.В. Асимптотика суммы расстояний между степенными вычетами по простому модулю. Тр. МИАН. 2012. Т. 276. С. 1–13.

  3. Aryan F. Distribution of squares modulo a composite number // Int. Math. Res. Not. IMRN 2015. V. 23. P. 12405–12431, https://arxiv.org/pdf/1502.05062.pdf.

  4. Kurlberg P., Rudnick Z. The Distribution of Spacings between Quadratic Residues // Duke Math. J. 1999. V. 100. P. 211–242.

  5. Kurlberg P. The Distribution of Spacings between Quadratic Residues. II // Israel J. Math. 2000. V. 120. Pt. A. P. 205–224.

Дополнительные материалы отсутствуют.

Инструменты

Доклады Российской академии наук. Математика, информатика, процессы управления