| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях) Множества с экстремальным свойством произведения и его вариации Ю. Н. Штейниковab a Национальный исследовательский центр "Курчатовский институт", г. Москва b Федеральный научный центр Научно-исследовательский институт системных исследований Российской академии наук, г. Москва
Англоязычная версия:
Mathematical Notes, 2023, Volume 114, Issue 6, Pages DOI: https://doi.org/10.1134/S0001434623110676 
Реферативные базы данных:
  Посвящается светлой памяти Хавьера Силлеруело. 1. ВведениеВ данной работе мы рассматриваем задачи, предложенные в статье Форда [1], а также используем подходы и аргументы рассуждений из указанной статьи. Произведением множеств $A$ и $B$ называется множество $AB$, которое по определению есть Обозначим через $[N]$ интервал натуральных чисел $\{1,2, \dots,N \}$, и пусть $M_N=|[N][N]|$. Одна из давних классических задач Эрдёша о таблице умножения ставит вопрос об отыскании правильного порядка роста величины $M_N$ при $N \to \infty$. Эрдёш установил [2], что где
$$
\begin{equation*}
2\theta=\frac{1}{2} - \frac{1+\log\log 2}{\log 4}=0.08607\dotsc\,.
\end{equation*}
\notag
$$
Форд уточнил этот результат и доказал помимо всего прочего [3], что величина $M_N$ имеет порядок
$$
\begin{equation}
M_N \asymp \frac{N^2}{(\log N)^{2\theta} (\log\log N)^{3/2}}.
\end{equation}
\tag{1}
$$
Некоторые направления дальнейших исследований были предложены Силлеруело с соавторами в статье [4]. Они рассматривали случай произвольных подмножеств $A$ интервала $[N]$ и исследовали размер множеств $A/A$, $AA$ для так называемых случайных подмножеств и из некоторых других классов. В этой же работе был поставлен следующий вопрос. Заметим, что если $|AA| \sim |A|^2/2$, то величина $|A|$ не может расти по порядку быстрее чем $M_N^{1/2}$. С другой стороны, Форд [1] доказал существование множества $A \subset [N]$ со свойством $|AA| \sim |A|^2/2$, обладающего размером близким к $M_N^{1/2}$. Тем самым он получил отрицательный ответ на указанный выше вопрос. Им доказана такая теорема [1]. Теорема 1. Пусть $D>7/2$. Тогда для каждого $N \geqslant 10$ найдется множество $A \subset [N]$ размера для которого $|AA| \sim |A|^{2}/2$ при $N \to \infty$. Из оценки по порядку (1) и оценки (2) можно вывести, что показатель степени у логарифма в теореме точный. Данный результат основан на тщательном анализе структуры множества $[N][N]$ и опирается на результаты работ [3], [5]. Возникает вопрос об уточнении степени повторного логарифма в исходной оценке теоремы 1. Цель настоящей работы – доказать такую теорему. Теорема 2. Пусть $D>13/4$. Тогда при достаточно большом $N$ найдется множество $A \subset [N]$ размера для которого $|AA| \sim |A|^{2}/2$ при $N \to \infty$. При выводе этого результата используется техника и рассуждения из статьи [1] с некоторой модификацией конструкции доказательства. Согласно [3] большинство элементов $[N][N]$ имеет асимптотически $\log\log N /\log 2 $ простых сомножителей. Поэтому, как и в работе [1], мы будем рассматривать числовые множества $A$, элементы которых имеют асимптотически $\log\log N /\log 4 $ простых делителей. Аргументы доказательства и оценки будем производить аккуратнее. Этот подход и позволит в итоге получить содержание теоремы 2. Кратко опишем некоторые этапы доказательства теоремы 2. Как и в [1], доказательство проводится в 3 этапа. Опишем кратко их в нижеследующих пунктах. 1) Рассматриваем множество $A$ согласно [1] и выписываем оценку на размер этого множества. 2) Получаем оценку сверху на мультипликативную энергию множества $A$. Показываем, что данная величина не “слишком большая”. Напомним, что мультипликативная энергия множества $A$, обозначаемая как $E(A)$, по определению задается следующим образом:
$$
\begin{equation}
E(A):=|\{ a_1,a_2, b_1,b_2 \in A \colon a_1b_1=a_2b_2 \}|.
\end{equation}
\tag{4}
$$
Верхнюю оценку для $E(A)$ мы получаем по схеме, предложенной в статье [1], с небольшим усовершенствованием. 3) Выбираем случайные подмножества нулевой плотности $A'$ во множестве $A$. Данные подмножества $A'$ будут иметь асимптотически наименьшую возможную мультипликативную энергию: $E(A') \sim 2|A'|^2$. Отсюда будет следовать, что множество $A'A'$ имеет почти максимальный размер, т.е. $|A'A'| \sim |A'|^2/2$. Это и составляет содержание теоремы 2. Работа организована следующим образом. В разделе 2 мы выводим предварительные утверждения и определения. Далее в разделе 3 мы выводим нашу основную теорему 2. 2. Предварительные утвержденияНапомним некоторые общепринятые обозначения, которые используются в этой работе. Через $p$ будем обозначать простое число, через $\omega(n)$ обозначим число простых делителей числа $n$, $\omega(n,t)$ – число простых делителей $p \leqslant t$ числа $n$. Пусть $p_{j}(m)$ обозначает $j$-й по величине простой делитель $m$. Для сокращения формул иногда для функции $\log\log (\cdot)$ будем использовать стандартное обозначение $\log_{2}(\cdot)$. Обозначим
$$
\begin{equation}
\pi(x,k)=\{1 \leqslant n \leqslant x \colon \omega(n)=k \}.
\end{equation}
\tag{5}
$$
В статье мы будем использовать оценку количества чисел с заданным значением $\omega(n,t)$. Соответствующее утверждение может быть найдено в работе [6]. Лемма 3. Пусть $x \geqslant 3$ и $1 \leqslant k \leqslant C\log\log x$ для некоторого фиксированного $C>0$ и по определению $y=k/{\log\log x}$. Тогда имеет место где Далее мы представим (см., например, [4]) простое неравенство, связывающее размер произведения $AA$ и мультипликативную энергию множества $A$: Нам также потребуется один результат об оценке суммы мультипликативной функции. Лемма 4. Пусть $f$ – действительнозначная мультипликативная функция такая, что $ 0 \leqslant f(p^a) \leqslant 1.9^a$ для всех простых чисел $p$ и натуральных $a$. Тогда для любого $x > 1$ справедлива оценка Это утверждение есть следствие теоремы Хальберстама и Рихтера. В явном виде это утверждение содержится в [7; теорема 01]. В статье будет применяться специальный случай функции $f(n)= \lambda^{\omega(n)}$ или $f(n)=\lambda^{\omega(n,t)}$. Применяя предыдущую лемму к функции $f(n)=\lambda^{\omega(n,t)}$ и используя простую выкладку, мы получаем неравенство
$$
\begin{equation}
\sum_{n \leqslant x} \lambda^{\omega(n,t)} \ll x (\log t)^{\lambda - 1}.
\end{equation}
\tag{9}
$$
3. Доказательство теоремы 2Доказательство теоремы существенным образом опирается на идеи и методы, предложенные в статье [1] и разбивается на несколько этапов. 3.1. Определение множества $A$В этом пункте для удобства изложения мы приводим некоторые обозначения, определения и оценки из работы [1]. Обозначим $K=[{\log\log N}/{\log 4}]$. Определим множество $A$ следующим образом:
$$
\begin{equation}
A=\biggl\{ \frac{N}{2} \leqslant n \leqslant N\colon \mu(n) \neq 0,\, \omega(n)=K,\, \omega(n,t)\leqslant \frac{\log_2 t}{\log 4}+2 (3 \leqslant t \leqslant N) \biggr\}.
\end{equation}
\tag{10}
$$
Следующим шагом мы оцениваем размер множества $A$. Нижняя оценка на размер множества $A$ может быть получена с помощью величин $N_{k}(N,\alpha, \beta)$:
$$
\begin{equation}
N_{K}(N,\alpha, \beta)=|\{ m \leqslant x\colon \omega(m)=K,\,\log_{2}p_{j}(m) \geqslant \alpha j- \beta\text{ для всех } j \}|,
\end{equation}
\tag{11}
$$
изученных подробно в статье [8]. Положим $\alpha=\log 4$, $\beta= 2 \log 4$. Несложно установить (как сделано в [1]), что условие вытекает из условия для всех имеющихся индексов $j$ числа $m$. Оценка снизу на величину $N_{K}(N,\alpha, \beta)$ получена в [8], и она остается справедливой при дополнительных ограничениях, что числа $n$ бесквадратные и находятся в интервале $[{N}/{2}, N]$. Поэтому мы можем получить и нижнюю оценку на величину $A_k$. Для получения оценки на множество $N_{K}(N,\alpha, \beta)$ остается проверить справедливость соотношений для введенных параметров из [8; теорема 1]:
$$
\begin{equation*}
u=2, \qquad v=\frac{\log\log N}{\log 4}, \qquad w=\frac{\log\log N}{\log 4} - K+3, \qquad A=1.1, \qquad \varepsilon=0.1.
\end{equation*}
\notag
$$
В итоге получаем следующую оценку: Вспоминая, что $K=[{\log\log N}/{\log 4} ]$, мы заключаем, что
$$
\begin{equation}
|A| \gg \frac{N}{(\log N)^{\theta}(\log_{2}N)^{3/2}}.
\end{equation}
\tag{13}
$$
3.2. Оценка мультипликативной энергии множества $A$Параметризация решений уравнения и их свойстваВ этом пункте наша цель – получение верхней оценки на значение энергии $E(A)$ множества $A$. Согласно [4] каждой четверке $(a_1,b_1,a_2,b_2) \in A \times A \times A \times A$, удовлетворяющей равенству $a_1b_1=a_2b_2$, сопоставим другую четверку. Пусть $d=\operatorname{gcd}(a_1,b_1)$. Тогда все $(a_1,b_1,a_2,b_2)$ делятся на $d$. Определим числа $a_1'$, $a_2'$, $b_1'$, $b_2'$ следующим образом:
$$
\begin{equation*}
a_1'=\frac{a_1}d, \qquad b_1'=\frac{b_1}d, \qquad a_2'=\frac{a_2}d, \qquad b_2'=\frac{b_2}d,
\end{equation*}
\notag
$$
и также $\operatorname{gcd}(a_1',b_1')=\operatorname{gcd}(a_2',b_2')=1$. Теперь определим четверку $(\beta_{1,1},\beta_{1,2},\beta_{2,1},\beta_{2,2})$ формулами
$$
\begin{equation}
\beta_{1,1}=\operatorname{gcd}(a_1', a_{2}'), \quad\ \beta_{1,2}=d\operatorname{gcd}(a_1', b_{2}'), \quad\ \beta_{2,1}=d\operatorname{gcd}(b_1', a_{2}'), \quad\ \beta_{2,2}= \operatorname{gcd}(b_1', b_{2}').
\end{equation}
\tag{14}
$$
Легко видеть, что выполнены равенства
$$
\begin{equation}
a_1=\beta_{1,1}\beta_{1,2}, \qquad b_1=\beta_{2,1}\beta_{2,2}, \qquad a_2=\beta_{1,1}\beta_{2,1}, \qquad b_2=\beta_{1,2}\beta_{2,2}.
\end{equation}
\tag{15}
$$
Также отметим, что
$$
\begin{equation}
\operatorname{gcd} (\beta_{1,1},\beta_{1,2})=\operatorname{gcd} (\beta_{2,1},\beta_{2,2})=\operatorname{gcd} (\beta_{1,1},\beta_{2,1})=\operatorname{gcd} (\beta_{1,2},\beta_{2,2})=1.
\end{equation}
\tag{16}
$$
Итак, мы сопоставили каждому решению $(a_1,b_1,a_2,b_2)$ четверку $(\beta_{1,1},\beta_{1,2},\beta_{2,1},\beta_{2,2})$. Обратно, если знаем четверку $(\beta_{1,1},\beta_{1,2},\beta_{2,1},\beta_{2,2})$, то мы по формулам выше восстанавливаем четверку $(a_1,b_1,a_2,b_2)$. Исходя из формул (15) и того, что $a_1,a_2,b_1,b_2 \in [N/2,N]$, мы получаем такие неравенства
$$
\begin{equation*}
\frac12 \leqslant \frac{\beta_{1,1}}{\beta_{2,2}}, \frac{\beta_{1,2}}{\beta_{2,1}} \leqslant 2.
\end{equation*}
\notag
$$
Далее без ограничения общности считаем, что $\min(\beta_{1,1},\beta_{2,2}) \gg N^{1/2}$, и пусть Тогда из вышестоящих соотношений вытекает
$$
\begin{equation}
\frac T2 \leqslant \beta_{1,2},\beta_{2,1} \leqslant 4T, \qquad \frac{N}{8T} \leqslant \beta_{1,1},\beta_{2,2} \leqslant \frac{2N}T.
\end{equation}
\tag{18}
$$
Целью следующего пункта является доказательство следующей леммы. Лемма 5. Для множества $A$, определенного в (10) справедливо неравенство 3.3. Доказательство леммы 5Пусть $(a_1,b_1,a_2,b_2) \in A$ – произвольный набор, отвечающий решению $a_1b_1=a_2b_2$. Данному набору $(a_1,b_1,a_2,b_2)$ по формулам (14) мы однозначно сопоставили набор $(\beta_{1,1}, \beta_{2,2}, \beta_{1,2},\beta_{2,1})$. Обозначим указанное множество таких четверок через $\mathfrak{P}$. Согласно соотношениям (18) мы рассмотрим все четверки из $\mathfrak{P}$ удовлетворяющих вышеупомянутым соотношениям для некоторой величины $T \ll N^{1/2}$. Обозначим это множество $\mathfrak{P}_{T}$. Далее используем схему, предложенную в [1]. Пусть четверка $(\beta_{1,1},\beta_{2,2}, \beta_{1,2},\beta_{2,1})$ соответствует $(a_1,a_2, b_1,b_2)$. Мы знаем, что
$$
\begin{equation}
\begin{gathered} \, \omega(a_1),\omega(a_2), \omega(b_1),\omega(b_2)=K, \\ \omega(a_1,4T), \omega(a_2,4T), \omega(b_1,4T),\omega(b_2,4T) \leqslant\frac{\log_{2}(4T)}{\log 4}+2, \end{gathered}
\end{equation}
\tag{20}
$$
Для удобства обозначим через Тогда, исходя из формул (15) и (16), получаем в виде следствия соотношения
$$
\begin{equation}
\begin{gathered} \, \omega(\beta_{1,1})+\omega(\beta_{1,2})+ \omega(\beta_{2,1})+\omega(\beta_{2,2})=2K, \\ \omega(\beta_{1,2})=\omega(\beta_{2,1}), \qquad \omega(\beta_{1,1})= \omega(\beta_{2,2}) \\ \omega(\beta_{1,1},4T)+\omega(\beta_{1,2},4T)+ \omega(\beta_{2,1},4T)+\omega(\beta_{2,2},4T) \leqslant 2z_{T}. \end{gathered}
\end{equation}
\tag{21}
$$
Поскольку $\beta_{1,2}, \beta_{2,1} \leqslant 4T$, то
$$
\begin{equation*}
\omega(\beta_{1,2},4T)=\omega(\beta_{1,2}), \omega(\beta_{2,1},4T)=\omega(\beta_{2,1}).
\end{equation*}
\notag
$$
Далее, фиксируем $\lambda_{1}=1/2$, $\lambda_{2}=1/\log 4$. Введем величину $U_{T}$ по определению следующим выражением:
$$
\begin{equation}
\begin{aligned} \, \notag U_{T} &=\sum_{\beta_{1,1}, \beta_{2,2} \leqslant 2N/T} \sum_{\beta_{1,2}, \beta_{2,1} \leqslant 4T}\lambda_{2}^{\omega(\beta_{1,1})+\omega(\beta_{1,2})+\omega(\beta_{2,1})+\omega(\beta_{2,2}) - 2K} \\ \notag &\qquad\qquad \times \lambda_{1}^{\omega(\beta_{1,1},4T)+\omega(\beta_{1,2},4T)+ \omega(\beta_{2,1},4T)+\omega(\beta_{2,2},4T)-2z_{T}} \\ &\qquad=\lambda_{1}^{-2z_{T}}\lambda_{2}^{-2k}\biggl(\sum_{\beta \leqslant 4T} \lambda_{2}^{\omega(\beta)}\lambda_{1}^{\omega(\beta)} \biggr)^{2}\biggl(\sum_{\beta \leqslant 2N/T} \lambda_{2}^{\omega(\beta)}\lambda_{1}^{\omega(\beta,4T)} \biggr)^{2}. \end{aligned}
\end{equation}
\tag{22}
$$
Установим связь $U_{T}$ с набором четверок $(\beta_{1,1},\beta_{2,2}, \beta_{1,2},\beta_{2,1}) \in \mathfrak{P}_{T} $, удовлетворяющих соотношениям (18), (21). Отметим следующий факт. Каждый такой набор $(\beta_{1,1},\beta_{2,2},\beta_{1,2},\beta_{2,1}) \in \mathfrak{P}_{T}$ входит в величину $U_T$ с весом $\geqslant 1$. Далее, заметим, что определение величины $U_T$ не учитывает два равенства
$$
\begin{equation*}
\omega(\beta_{1,2})=\omega(\beta_{2,1}), \qquad \omega(\beta_{1,1})= \omega(\beta_{2,2}).
\end{equation*}
\notag
$$
В дальнейших рассуждениях мы будем использовать это свойство в наших аргументах. Для удобства обозначим через $T_1=4T$, $T_2=2N/T$ и будем их считать фиксированными. Введем также параметр $\delta>0$, являющимся достаточно малым, но фиксированным действительным числом, который выберем потом. Рассмотрим два случая. Случай 1. Пусть $\omega(\beta_{1,2})=\omega(\beta_{2,1}) \geqslant \delta \log\log T_1$. Для удобства обозначим $t=\omega(\beta_{1,2})$ и будем считать его фиксированным. Четверки $(\beta_{1,1},\beta_{2,2}, \beta_{1,2},\beta_{2,1}) \in \mathfrak{P}_{T}$, которые относятся к этому случаю будем называть нормальными. Введем по определению множество
$$
\begin{equation}
M_{l}=\bigl\{ (\beta_{1,2},\beta_{2,1})\colon \beta_{1,2},\beta_{2,1} \leqslant T_1 \colon \omega(\beta_{1,2})=t-l,\, \omega(\beta_{2,1})=t+l \bigr\}.
\end{equation}
\tag{23}
$$
Рассмотрим для произвольной нормальной четверки соответствующую пару $(\beta_{1,1},\beta_{2,2})$ и зафиксируем ее. Для этой пары $(\beta_{1,1},\beta_{2,2})$ множество $(\beta_{1,2},\beta_{2,1})$ лежит в $M_0$. А теперь для пары $(\beta_{1,1},\beta_{2,2})$ и произвольного $l \in [1, \delta^{1/2}(\log\log T_1)^{1/2}]$ рассмотрим множество четверок
$$
\begin{equation}
V_{l}:=(\beta_{1,1},\beta_{2,2}, \beta_{1,2},\beta_{2,1}), \qquad \text{где} \quad (\beta_{1,2},\beta_{2,1}) \in M_l.
\end{equation}
\tag{24}
$$
Далее, мы отмечаем, что четверки из множества $V_l$ входят в величину $U_T$ с таким же весом, что и нормальные четверки. Однако ясно, что при $l \neq 0$ четверки из $V_l$ не удовлетворяют соотношению $\omega(\beta_{1,2})=\omega(\beta_{2,1})$. Следующим шагом мы покажем, что размер множеств $M_l$ по порядку не отличается от размера $M_0$. Сформулируем это в виде отдельного утверждения. Лемма 6. Для $l \in [1, \delta^{1/2}(\log\log T_1)^{1/2}]$ и в вышеуказанных обозначениях справедливо неравенство $|M_l| \gg |M_0|$. Доказательство. Заметим, что для рассматриваемых $l \in [1, \delta^{1/2}(\log\log T_1)^{1/2}]$ выполнено $|M_l|=|\pi(T_1,t-l)|\,\pi(T_1,t+l)|$. Оценим сверху отношение ${|M_0|}/{|M_l|}$, применяя формулу (6) и несложные выкладки. Получаем Зная, что $t \geqslant \delta \log\log T_1$, мы легко получаем нужное неравенство. Лемма доказана. Пусть теперь $t$ произвольно и $t \geqslant \delta \log\log T_1$. Из леммы 6 и предыдущих рассуждений мы можем сделать следующий вывод. Количество нормальных четверок $(\beta_{1,1}, \beta_{2,2},\beta_{1,2},\beta_{2,1})$ по порядку не больше, чем $U_T/(\log\log T_1)^{1/2}$. Величина $U_T$ легко оценивается с помощью леммы 4, и соответствующая оценка была приведена в работе [1]. Мы берем оценку из этой работы: Поэтому количество нормальных четверок $(\beta_{1,1}, \beta_{2,2},\beta_{1,2},\beta_{2,1}) $ по порядку не превосходит величины
$$
\begin{equation}
\frac{N^2}{(\log N)^{2\theta}(\log T_1)(\log\log T_1)^{1/2}}= \frac{N^2}{(\log N)^{2\theta}(\log T)(\log\log T)^{1/2}}.
\end{equation}
\tag{25}
$$
Случай 2. Пусть теперь $\omega(\beta_{1,2}), \omega(\beta_{2,1})=t \leqslant \delta \log\log T_1$. В этом случае количество $\beta_{1,2}$, также как и $\beta_{2,1}$, оценивается сверху величиной $|\pi(T_1,t)|$. Пользуясь формулой (6) и несложными выкладками при достаточно малом (но фиксированном) $\delta>0$ получаем, что множество таких пар $(\beta_{1,2},\beta_{2,1})$ оценивается сверху как
$$
\begin{equation*}
\sum_{l \leqslant \delta \log\log T_1 } |\pi(T_1,l)|^2 \ll \frac{T_1^2}{(\log T_1)^{1.2}}.
\end{equation*}
\notag
$$
Теперь оценим сверху число возможных значений для $\beta_{1,1}, \beta_{2,2}$. Воспользуемся тем, что
$$
\begin{equation*}
\omega(\beta_{1,1}), \omega(\beta_{2,2}) \leqslant \frac{\log\log T_2}{\log 4}+2.
\end{equation*}
\notag
$$
Поэтому, пользуясь формулой (6), количество возможностей для каждого $\beta_{1,1}, \beta_{2,2}$ оценивается сверху величиной $\ll {T_2}/{(\log N)^{\theta}}$. Отсюда заключаем, что множество всевозможных четверок $(\beta_{1,1}, \beta_{2,2},\beta_{1,2},\beta_{2,1})$ в данном случае по порядку не превосходит величины
$$
\begin{equation}
\frac{N^2}{(\log N)^{2\theta}(\log T_1)^{1.2}}=\frac{N^2}{(\log N)^{2\theta}(\log T)^{1.2}}.
\end{equation}
\tag{26}
$$
Первая величина в формулах (25), (26) в рассмотренных двух случаях является доминирующей. Отсюда заключаем, что общее число четверок $(\beta_{1,1}, \beta_{2,2},\beta_{1,2},\beta_{2,1})$ из множества $\mathfrak{P}_{T}$ оценивается по порядку величиной
$$
\begin{equation*}
\frac{N^2}{(\log N)^{2\theta}(\log T)(\log\log T)^{1/2}}.
\end{equation*}
\notag
$$
Остается просуммировать последнее выражение по $T$, являющегося степенью двойки. В итоге мы получаем, что число всевозможных исходных четверок $(\beta_{1,1}, \beta_{2,2},\beta_{1,2},\beta_{2,1})$ при условии $\beta_{1,2},\beta_{2,1} \ll N^{1/2}$ не превосходит по порядку Случай же $\beta_{1,1}, \beta_{2,2} \ll N^{1/2}$ разбирается полностью аналогично и с такими же оценками. Вспоминая неравенство (13), окончательно получаем
$$
\begin{equation*}
E(A) \ll \frac{N^2 (\log\log N)^{1/2}}{(\log N)^{2\theta}} \ll |A|^{2}(\log\log N)^{3.5}.
\end{equation*}
\notag
$$
Лемма 5 доказана. 3.4. Выбор случайных подмножествДальнейшие рассуждения близки к рассуждениям из работ [4] и [1]. Пусть имеется произвольное конечное множество $A \subset [N]$ и известна мультипликативная энергия $E(A) \leqslant |A|^2f(N)$, где функция $f(N)$ существенно меньше $|A|$. Пусть $A'$ – подмножество $A$, состоящее из случайно выбранных элементов, определяемое следующим образом. Каждый элемент $a \in A$ принадлежит $A'$ с вероятностью $\rho=o(1/f(N))$ и все такие события независимы в совокупности. Покажем, что с вероятностью, стремящейся к 1 при $N \to \infty$, выполнены следующие свойства:
$$
\begin{equation*}
|A'| \sim \rho |A|, \qquad E(A') \sim 2|A'|^2, \qquad |A'A'| \sim \frac{|A'|^2}2.
\end{equation*}
\notag
$$
Покажем лишь соотношение $E(A') \sim 2|A'|^2$. Возьмем случайное множество $A'$. Рассмотрим четверки
$$
\begin{equation*}
(a_1,a_2,a_3,a_4)\colon a_i \in A'\colon a_1a_2=a_3a_4,
\end{equation*}
\notag
$$
число которых составляет величину энергии $E(A')$. Среди них есть тривиальные четверки, когда $a_1=a_3$ или $a_1=a_4$. В оставшихся четверках, которые мы назовем нетривиальными, все числа $a_1$, $a_2$, $a_3$, $a_4$ различны. Количество тривиальных четверок асимптотически выражается величиной $2|A'|$. Теперь оценим сверху математическое ожидание числа нетривиальных четверок. В каждой такой четверке каждый из $a_i$ попадает в $A'$ с одинаковой вероятностью $\rho$ и все соответствующие четыре события независимы в совокупности. Отсюда получаем, что математическое ожидание числа таких нетривиальных четверок не превосходит $\rho^4E(A)$. Поскольку с вероятностью, стремящейся к 1 при $N \to \infty$, выполнено $|A'| \sim \rho|A|$, то в этом случае $\rho^4 E(A)=o(|A'|^2)$. Поэтому с вероятностью, стремящейся к 1, выполнено $E(A')\sim 2|A'|^2$. В свою очередь выражение $|A'A'| \sim |A'|^2/2$ вытекает из указанного соотношения на энергию $E(A')$. Для нашего случая достаточно взять $\rho=o((\log\log N)^{7/4})$, и отсюда получается утверждение теоремы 2. На этом мы завершаем доказательство. Автор благодарен С. В. Конягину, И. Д. Шкредову, М. А. Королеву, а также всем участникам семинаров по теории чисел в МИАН им. В. А. Стеклова и НИИСИ РАН за ценные обсуждения и советы при подготовке данной работы. 
Цитирование в формате AMSBIB
\RBibitem{Sht23} |
|
||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|