On the reduction of a random basis

¹ LIAFA, Université Denis Diderot, Case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France; akhavi@liafa.jussieu.fr
² LABRI, Université Bordeaux I, 351 cours de la Libération, 33405 Talence Cedex, France; marckert@labri.fr
³ LMV UMR 8100, Université Versailles-Saint-Quentin, 45 avenue des États-Unis, 78035 Versailles Cedex, France; Alain.Rouault@math.uvsq.fr

Received: 6 October 2006
Revised: 23 October 2007
Revised: 9 July 2009

Abstract

For p ≤ n, let b₁⁽ⁿ⁾,...,b_p⁽ⁿ⁾ 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 b₁⁽ⁿ⁾,...,b_p⁽ⁿ⁾ 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) → +∞.