On the reduction of a random basis

Issue		ESAIM: PS Volume 13, 2009


Page(s)		437 - 458
DOI		10.1051/ps:2008012
Published online		22 September 2009

ESAIM: PS, July 2009, Vol. 13, p. 437-458
DOI: 10.1051/ps:2008012

On the reduction of a random basis

Ali Akhavi¹, Jean-François Marckert² and Alain Rouault³

¹ 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 October 6, 2006. Revised October 23, 2007 and July 9, 2009. Published online 22 September 2009

Abstract
 For $p \leq n$ , let $b^{(n)}_1,\ldots,b^{(n)}_p$ 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 $b^{(n)}_1,\ldots,b^{(n)}_p$ 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, \ldots , p-1$ . We show that as $n\to \infty$ 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)\to +\infty$ .

Mathematics Subject Classification. 15A52, 15A03, 60B12, 60F99, 06B99, 68W40

Key words: Random matrices, random basis, orthogonality index, determinant, lattice reduction.

© EDP Sciences, SMAI 2009

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.