Algorithms

Вычислительный анализ количественных характеристик некоторых аппроксимационных свойств разрешимых групп Баумслага–Солитэра

Е. А. Туманова

Ивановский государственный университет, ул. Ермака, д. 39, г. Иваново, 153025 Россия

Аннотация: Пусть $G_{k} = \langle a, b; a^{-1}ba = b^{k} \rangle$, где $k \ne 0$. Известно, что если $p$ — некоторое простое число, то группа $G_{k}$ аппроксимируется конечными $p$-группами тогда и только тогда, когда $p \mid k - 1$. Известно также, что если $p$ и $q$ — простые числа, не делящие $k - 1$, $p < q$ и $\pi = \{p, q\}$, то группа $G_{k}$ аппроксимируется конечными $\pi$-группами тогда и только тогда, когда $(k,q) = 1$, $p \mid q - 1$ и порядок числа $k$ в мультипликативной группе поля $\mathbb{Z}_{q}$ является $p$-числом. В настоящей статье исследуется вопрос о количестве двухэлементных множеств простых чисел, удовлетворяющих условиям последнего критерия. Более точно, пусть $f_{k}(x)$ — количество множеств $\{p, q\}$ таких, что $p < q$, $p \nmid k - 1$, $q \nmid k - 1$, $(k, q) = 1$, $p \mid q - 1$, порядок $k$ по модулю $q$ является $p$-числом и $p$, $q$ выбираются среди первых $x$ простых чисел. Установлено, что если $2 \leq |k| \leq 10000$ и $1 \leq x \leq 50000$, то почти для всех рассматриваемых $k$ функция $f_{k}(x)$ может быть достаточно точно приближена функцией $\alpha_{k}x^{0,85}$, где коэффициент $\alpha_{k}$ — свой для каждого $k$ и $\{\alpha_{k} \mid 2 \leq |k| \leq 10000\} \subseteq (0,28; 0,31]$. Также исследована зависимость величины $f_{k}(50000)$ от $k$ и предложен эффективный алгоритм проверки двухэлементного множества простых чисел на соответствие условиям последнего критерия. Полученные результаты могут иметь приложения в теории сложности вычислений и алгебраической криптографии.

Ключевые слова: группы Баумслага–Солитэра, аппроксимируемость конечными $\pi$-группами, аппроксимация функций, анализ алгоритмов.

УДК: 004.421, 512.54, 519.25, 519.65

Поступила в редакцию: 26.04.2021
Исправленный вариант: 28.05.2021
Принята в печать: 02.06.2021

DOI: 10.18255/1818-1015-2021-2-136-145