On the reduction of a random basis

Akhavi, Ali ; Marckert, Jean-François  ; Rouault, Alain

ESAIM: Probability and Statistics, Tome 13 (2009), pp. 437-458

Résumé

For $p\le n$, let $b_1^{\left(n\right)},...,b_p^{\left(n\right)}$ be independent random vectors in ${ℝ}^n$ with the same distribution invariant by rotation and without mass at the origin. Almost surely these vectors form a basis for the euclidean lattice they generate. The topic of this paper is the property of reduction of this random basis in the sense of Lenstra-Lenstra-Lovász (LLL). If ${\widehat{b}}_1^{\left(n\right)},...,{\widehat{b}}_p^{\left(n\right)}$ is the basis obtained from $b_1^{\left(n\right)},...,b_p^{\left(n\right)}$ by Gram-Schmidt orthogonalization, the quality of the reduction depends upon the sequence of ratios of squared lengths of consecutive vectors $r_j^{\left(n\right)}=\parallel {\widehat{b}}_{n-j+1}^{\left(n\right)}{\parallel }^2/{\parallel {\widehat{b}}_{n-j}^{\left(n\right)}\parallel }^2$, $j=1,...,p-1$. We show that as $n\to \infty$ the process $(r_j^{\left(n\right)}-1,j\ge 1)$ tends in distribution in some sense to an explicit process $({ℛ}_j-1,j\ge 1)$; some properties of the latter are provided. The probability that a random random basis is $s$-LLL-reduced is then showed to converge for $p=n-g$, and $g$ fixed, or $g=g\left(n\right)\to +\infty$.

Détail

DOI : 10.1051/ps:2008012

Classification : 15A52, 15A03, 60B12, 60F99, 06B99, 68W40
Keywords: random matrices, random basis, orthogonality index, determinant, lattice reduction