On the reduction of a random basis
LIAFA, Université Denis Diderot, Case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France; email@example.com
2 LABRI, Université Bordeaux I, 351 cours de la Libération, 33405 Talence Cedex, France; firstname.lastname@example.org
3 LMV UMR 8100, Université Versailles-Saint-Quentin, 45 avenue des États-Unis, 78035 Versailles Cedex, France; Alain.Rouault@math.uvsq.fr
Revised: 23 October 2007
Revised: 9 July 2009
For p ≤ n, let b1(n),...,bp(n) be independent random vectors in 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 is the basis obtained from b1(n),...,bp(n) by Gram-Schmidt orthogonalization, the quality of the reduction depends upon the sequence of ratios of squared lengths of consecutive vectors , j = 1,...,p - 1. We show that as n → +∡ the process tends in distribution in some sense to an explicit process ; 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(n) → +∞.
Mathematics Subject Classification: 15A52 / 15A03 / 60B12 / 60F99 / 06B99 / 68W40
Key words: Random matrices / random basis / orthogonality index / determinant / lattice reduction.
© EDP Sciences, SMAI, 2009