Hostname: page-component-6898cfcb55-kwdml Total loading time: 0 Render date: 2026-11-11T14:24:09.793Z Has data issue: false hasContentIssue false

On the reduction of a random basis

Published online by Cambridge University Press:  22 September 2009

Ali Akhavi
Affiliation:
LIAFA, Université Denis Diderot, Case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France; akhavi@liafa.jussieu.fr
Jean-François Marckert
Affiliation:
LABRI, Université Bordeaux I, 351 cours de la Libération, 33405 Talence Cedex, France; marckert@labri.fr
Alain Rouault
Affiliation:
LMV UMR 8100, Université Versailles-Saint-Quentin, 45 avenue des États-Unis, 78035 Versailles Cedex, France; Alain.Rouault@math.uvsq.fr
Get access

Abstract

For p ≤ n, let b1(n),...,bp(n) be independent random vectors in $\mathbb{R}^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}^{(n)},\ldots, \widehat b_p^{(n)}$ 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 $r_j^{(n)} = \Vert \widehat b^{(n)}_{n-j+1}\Vert^2 / \Vert \widehat b^{(n)}_{n-j} \Vert^2$ , j = 1,...,p - 1. We show that as n → +∡ the process $(r_j^{(n)}-1,j\geq 1)$ tends in distribution in some sense to an explicit process $({\mathcal R}_j -1,j\geq 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(n) → +∞.

Information

Type
Research Article
Copyright
© EDP Sciences, SMAI, 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable