Кратчайшие векторы решеток, связанных с линейным конгруэнтным генератором

Пусть $\varepsilon>0$ — фиксированное число, $\mathcal E\subset\mathbf R^s$ — полная решетка определителя $\Delta\in\mathbf Q$. Назовем ее $\varepsilon$-регулярной, если $\lambda_1(\mathcal E)>\Delta^{1/s}(h(\Delta))^{-\varepsilon}$, где $\lambda_1(\mathcal E)$ — длина ненулевого кратчайшего вектора решетки $\mathcal E$, а $h(\Delta)$ — максимум абсолютных величин числителя и знаменателя несократимой дроби для $\Delta$. В нашей работе рассматриваются две полные решетки пространства $\mathbf R^s$:
$\bullet$ решетка $\mathcal L(a,W)$, связанная с линейной конгруэнтной последовательностью
\begin{equation} (x_N),\quad x_{N+1}=ax_N\pmod W,\quad N=1,2,\ldots,
\end{equation}

$\bullet$ двойственная к ней решетка $\mathcal L^*(a,W)$.
Существует гипотеза, утверждающая, что при любом натуральном $s$, любом $0<\varepsilon<\varepsilon_0(s)$ и любом $W>W_0(s,\varepsilon)$ все решетки $\mathcal L(a,W)$ и $\mathcal L^*(a,W)$ при $a=0,1,\ldots,W-1$ являются $\varepsilon$-регулярными за исключением множества чисел $a$ мощности, не большей $W^{1-\varepsilon}$. В работе 1988 г. А. Фризом, Й. Хастадом, К. Каннаном, Дж. Лагариасом и А. Шамиром было доказано чуть более слабое утверждение в случае $s=3$ (число исключительных $a$ в их оценке не превосходит $W^{1-\varepsilon/2})$. Кроме того, с помощью рассуждений указанной работы легко проверить справедливость гипотезы в случаях $s=1$ и $s=2$. В нашей работе доказывается справедливость сформулированной гипотезы в случае $s=4$. Кроме того, с помощью рассуждений нашей работы можно слегка уточнить результат упомянутой выше работы, установив справедливость гипотезы в случае $s=3$. Все указанные утверждения имеют приложения в теории восстановления линейной конгруэнтной последовательности (1) по старшим разрядам ее нескольких первых элементов.