Let $\varepsilon>0$ be a fixed real number, $\mathcal E\subset\mathbf R^s$ be a full rank lattice with determinant $\Delta\in\mathbf Q$. We call this lattice $\varepsilon$-regular if
$\lambda_1(\mathcal E)>\Delta^{1/s}(h(\Delta))^{-\varepsilon}$, where
$\lambda_1(\mathcal E)$ is the length of the shortest nonzero vector of $\mathcal E$ and
$h(\Delta)$ is the maximum of absolute values of the numerator and the denominator of the irreducible rational
fraction for $\Delta$.
In this paper, we consider two full rank lattices in the space $\mathbf R^s$:
the lattice $\mathcal L(a,W)$ connected with the linear congruent sequence
\begin{equation}
(x_N),\quad x_{N+1}=ax_N\pmod W,\quad N=1,2,\ldots,
\end{equation}
and the lattice $\mathcal L^*(a,W)$ dual to $\mathcal L(a,W)$.
There is a conjecture which states that for any natural number $s$, any real number
$0\varepsilon\varepsilon_0(s)$, and any natural number
$W>W_0(s,\varepsilon)$, the lattices $\mathcal L(a,W)$ and $\mathcal L^*(a,W)$
are $\varepsilon$-regular for all $a=0,1,\ldots,W-1$
excluding some set of numbers $a$ of cardinality at most $W^{1-\varepsilon}$.
In the case $s=3$, A. M. Frieze, J. Hestad, R. Kannan, J. C. Lagarias,
and A. Shamir in a paper published in 1988 proved a more weak assertion
(in their estimate the number of exceptional values $a$ is at most
$W^{1-\varepsilon/2}$). Using the methods of this paper,
it is not difficult to prove the conjecture for $s=1$ and $s=2$.
In our paper, we prove the conjecture for $s=4$. With the help of our methods
we improve the result of the paper mentioned above and prove the conjecture
for $s=3$.
Our result can be applied to the reconstruction of a linear congruent sequence (1)
if the high-order bits of its first $s$ elements are given.
