Preview

Чебышевский сборник

Расширенный поиск
Том 19, № 3 (2018)
https://doi.org/10.22405/2226-8383-2018-19-3

Статьи

19-34 37
Аннотация

Обсудим некоторые тождества с участием $\mu(n)$ и $M(x) = \sum _{n \leq x}\mu (n)$, функции Мёбиуса и Мертенса. Они позволяют вычислить $M(N^d)$ для $d=1,2,3,\ldots\, $ как сумму $O_d \left( N^d(\log N)^{2d - 2}\right)$ членов, каждое произведение вида $\mu(n_1) \cdots \mu(n_r)$ с $r\leq d$ и $n_1, \ldots , n_r\leq N$. Докажем более общее тождество, в котором $M(N^d)$ заменяется на $M(g,K)=\sum_{n\leq K}\mu(n)g(n)$, где $g(n)$ – произвольная полностью мультипликативная функция, тогда как каждое $n_j$ имеет собственный диапазон суммирования $1,\ldots , N_j$. Это не ново, за исключением того, что в $N_1,\ldots , N_d$ произвольны, но наше доказательство (вдохновленное тождественным равенством Э. Майсселя, 1854) является новым. Мы главным образом заинтересованы в случае $d=2$, $K=N^2$, $N_1=N_2=N$, где тождество имеет вид $M(g, N^2) = 2 M(g,N) - {\bf m}^{\rm T} A {\bf m}$, при этом $A$ является матрицей $N\times N$ элементов $a_{mn}=\sum _{k \leq N^2 /(mn)}\,g(k)$, в то время как ${\bf m}=(\mu (1)g(1),\ldots ,\mu (N)g(N))^{\rm T}$. Наши результаты в разделах 2 и 3 данной статьи предполагают, что $g(n)$ равно $1$ для всех $n$. Теорема Фробениуса-Перрона применяется в этом случае: мы находим, что $A$ имеет одно большое положительное собственное значение, приблизительно $(\pi^2 /6)N^2$, с собственным вектором приблизительно ${\bf f} = (1,1/2,1/3,\ldots ,1/N)^{\rm T}$ T и что при больших значениях $N$ второе наибольшее собственное значение лежит в $(-0.58 N, -0.49 N)$. Раздел 2 включает оценки для следов $A$ и $A^2$ (хотя для ${\rm Tr}(A^2)$, мы пропустим часть доказательства). В разделе 3 обсуждаются способы аппроксимации ${\bf m}^{\rm T} A {\bf m}$, используя спектральное разложение $A$ или (альтернативно) формулу Перрона: последний подход приводит к контурному интегралу, включающему дзета-функцию Римана. Мы также рассматриваем использование тождества $A = N^{2\,} {\bf f}^{\,} \!{\bf f}^T -
\textstyle{1\over 2} {\bf u} {\bf u}^T + Z$, а $Z$ --- матрица $N\times N$ элементов $z_{mn} = - \psi(N^2 / (mn))$, причем $\psi(x)=x - \lfloor x\rfloor - \textstyle{1\over 2}$. Наши выводы представлены в разделе 4.

35-39 32
Аннотация
Приведем новое доказательство теоремы Б. М. Бредихина, которая была первоначально доказана путем распространения решения Линника через его дисперсионный метод задачи Харди и Литтлвуда.
46-60 24
Аннотация

Гипотеза Римана имеет много эквивалентных
переформулировок. Часть из них является арифметическими,
то есть утверждениями о свойствах целых или натуральных чисел.
Простейшую логическую структуру имеют переформулировки из
класса $\Pi_1^0$ арифметической иерархии, имеющие вид ``для любых
$x_1,\dots,x_m$ имеет место $A(x_1,\dots,x_m)$'',
где $A$ -- алгоритмически проверяемое отношение.
Примером может служить переформулировка гипотезы Римана в
виде утверждения о том,
что некоторое диофантово уравнение не имеет решений
(такое конкретное уравнение может быть явно указано).

Хотя логическая структура такой переформулировки очень проста,
известные способы построения такого диофантова уравнения
приводят к уравнениям, требующим для своей записи нескольких страниц.
С другой стороны, известны весьма краткие по записи
переформулировки, также принадлежащие классу $\Pi_1^0$.
Примерами могут служить три критерия справедливости гипотезы
Римана, которые предложили Ж.-Л.\,Николас,
Г.\,Робин, и Дж.\,Лагариас. Недостатком этих
переформулировок (по сравнению
с диофантовым уравнением) является использование более ``сложных''
констант и функций, чем натуральные числа и сложение и умножение,
достаточные для построения диофантова уравнения.

В работе приводится система из 9 условий, налагаемых на 9
переменных. Для формулировки этих условий используются только
сложение, умножение, возведение в степень (унарное,
с фиксированным основанием~2), функция ``остаток от деления'',
неравенства, сравнения по модулю и биномиальный коэффициент.
Вся система может быть явно выписана на одной странице.
Доказано, что построеная система условий несовместна в том и только том случае,
когда гипотеза Римана верна.

61-73 37
Аннотация

В статье рассмотрены некоторые элементы теории чисел и показано
каким образом они используются в современных системах защиты
информации. В качестве примеров выбраны наиболее известные
протоколы и алгоритмы, такие как протокол Диффи-Хэллмана для
создания парного ключа, алгоритмы шифрования с открытым ключом
RSA и Эль Гамаля. Рассмотрен обобщенный алгоритм Евклида,
являющийся одним из наиболее часто встречающимся примитивом из
теории чисел, используемом в криптографии. Приведены алгоритмы
электронной подписи RSA и Эль Гамаля. В заключение предложен
алгоритм электронной подписи, основанный на билинейном
преобразовании использующем упрощенный вид спаривания в явном
законе взаимности.

74-79 16
Аннотация
Дан вариант метода Хуа для оценки неполных рациональных тригонометрических сумм. Эти оценки являются нетривиальными для сумм с длинами превосходящими корень квадратный от длины полной суммы.
80-94 19
Аннотация

Пусть $a$ и $q$ - два положительных целых числа. В 1944 году Ю. В. Линник показал, что наименьшее простое число в арифметической прогрессии по модулю  $q$ меньше $Cq^L$ с положительными постоянными $C$ и $L$.
Опираясь на работу Хиз-Брауна, мы доказываем, что $L=5$ допустимо.

95-108 14
Аннотация

В работе изучается дзета-функция моноида квадратичных вычетов по простому модулю $p$. Моноид квадратичных вычетов задается равенством
$$
M_{p,2}=\left\{a\in\mathbb{N}\left| \left(\frac{a}{p}\right)=1\right.\right\}=\bigcup_{\nu=1}^{\frac{p-1}{2}}\left(r_\nu+p\mathbb{N}_0\right),
$$
где $\mathbb{N}_0=\{0\}\bigcup\mathbb{N}$ и $r_1<r_2<\ldots<r_{\frac{p-1}{2}}$ --- наименьшая положительная система квадратичных вычетов по модулю $p$, соответственно, $r_{\frac{p+1}{2}}<\ldots<r_{p-1}$ --- наименьшая положительная система квадратичных невычетов по модулю $p$.

Множество простых элементов моноида $M_{p,2}$ состоит из множества простых чисел $\mathbb{P}_p^{(1)}$ и множества псевдопростых чисел $\mathbb{P}_p^{(2)}\cdot\mathbb{P}_p^{(2)}$:
$$
P(M_{p,2})=\mathbb{P}_p^{(1)}\bigcup\left(\mathbb{P}_p^{(2)}\cdot\mathbb{P}_p^{(2)}\right),
$$
где множество простых чисел $\mathbb{P}$ разбивается на два бесконечных подмножества $\mathbb{P}_p^{(\nu)}$ $(\nu=1,2)$ и одноэлементное множество $\{p\}$:
$$
\mathbb{P}=\mathbb{P}_p^{(1)}\bigcup\mathbb{P}_p^{(2)}\bigcup\{p\}, \quad \mathbb{P}_p^{(\nu)}=\left\{q\in\mathbb{P}\left|\left(\frac{q}{p}\right)=3-2\nu\right.\right\} \quad (\nu=1,2).
$$
Моноид $M_{p,2}$ разлагается в произведение двух взаимно простых моноидов $M_{p,2}=M_{p,2}^{(1)}\cdot$ $\cdot M_{p,2}^{(2)}$, где
$$
M_{p,2}^{(\nu)}=\left\{a\in M_{p,2}\left| a=\prod_{j=1}^{n}q_j^{\alpha_j}, \, q_j\in\mathbb{P}_p^{(\nu)} \right.\right\}, \quad \nu=1,2.
$$
В статье изучаются свойства функции распределения простых элементов $\pi_{M_{p,2}^{(\nu)}}(x)$ для $\nu=1,2$. Отметим, что $\pi_{M_{p,2}}(x)=\pi_{M_{p,2}^{(1)}}(x)+\pi_{M_{p,2}^{(2)}}(x)$. Показано, что
$$
\pi_{M_{p,2}^{(1)}}(x)=\frac{1}{2}\li x+O\left(\frac{x^{\beta_1}}{2}+\frac{p-1}2xe^{-c_9\sqrt{\ln x}}\right)
$$
и
$$
\pi_{M_{p,2}^{(2)}}(x)=\frac{x\ln\ln x}{2\ln x}+O\left(\frac{x}{(1-\beta_1)\ln{x}}\right),
$$
где $\beta_1$ --- исключительный ноль исключительного характера $\chi_1$ по модулю $p$.

В заключении рассмотрены актуальные задачи с дзета-функциями моноидов натуральных чисел, требующие дальнейшего исследования.

109-134 12
Аннотация

В работе рассматриваются новые варианты двух асимптотических формул из теории гиперболической дзета-функции решёток.

Во-первых, получена новая асимптотическая формула для гиперболической дзета-функции алгебраической решётки, полученной растяжением в $t$ раз по каждой координате решётки состоящей из полных наборов алгебраически сопряженных целых алгебраических чисел, пробегающих кольцо целых алгебраических чисел чисто вещественного алгебраического поля степени $s$ для любого натурального $s\ge2$.

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

В первом случае показано, что главный член асимптотической формулы для гиперболической дзета-функции алгебраической решётки выражается через детерминант решётки, регулятор поля и значения дзета-функции Дедекинда главных идеалов и её производные до порядка $s-1$. Впервые выписана явная формула остаточного члена и дана его оценка.

Во втором случае главный член асимптотической формулы выражается через объём гиперболического креста и детерминант решётки. Даётся явный вид остаточного члена и уточненная его оценка.

В заключении описана суть метода параметризованных множеств, использованного при выводе асимптотических формул.

135-147 20
Аннотация

Основными алгоритмическими проблемами теории групп являются проблемы равенства, сопряженности слов и проблема изоморфизма групп.

В силу неразрешимости данных проблем в классе конечно определенных групп, основные алгоритмические проблемы и их различные обобщения исследуются в конкретных группах.

Группы Кокстера изучаются с 1934 года, а в алгебраическом аспекте -- с 1962 года.
В них алгоритмически разрешимы проблемы равенства и сопряженности слов, однако неразрешима проблема вхождения.

В 1983 году К. Аппель и П. Шупп определили класс групп Кокстера
экстрабольшого типа.
В 2003 году В. Н. Безверхний ввел в рассмотрение группы Кокстера с древесной структурой.

В статье рассматриваются обобщенные древесные структуры групп Кокстера, представляющие собой древесные произведения групп Кокстера экстрабольшого типа и групп Кокстера с древесной структурой.

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

Авторами статьи предлагается оригинальный метод доказательства алгоритмической разрешимости проблемы обобщенной сопряженности слов в обобщенных древесных структурах групп Кокстера. Данный метод использует подход Г. С. Маканина, примененный им для доказательства конечной порожденности нормализатора элемента в группах кос. Кроме того, в данной работе показывается, что централизатор конечно порожденной подгруппы в обобщенной древесной структуре групп Кокстера конечно порожден и существует алгоритм, выписывающий его образующие.



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-8383 (Print)