On the probability of generating a lattice (Q2437315)

Motivated by an analysis of the success probability of quantum algorithms for solving the discrete logarithm problem in infrastructures obtained from number fields, the paper under review studies the problem of determining the probability that \(m\) vectors selected uniformly at random from \({\mathcal L} \cap [0,B)^n\) generate the (full-rank) lattice \({\mathcal L} \subset {\mathbb R^n}\), when \(B\) is chosen appropriately large. To state the main theorem precisely, assume that \(B \geq 8 n^{ n \over 2 } \nu({\mathcal L})\) and \(B_1 \geq 8 n^2 (n+1) B\), where \(\nu({\mathcal L})\) is the covering radius of \(\mathcal L\) (i.e., the smallest \(r\) such that translates by \(\mathcal L\) of a ball of radius \(r\) covers \({\mathbb R}^n\)), and that \(n\) vectors are selected uniformly at random from \({\mathcal L} \cap [0,B)^n\) and \(n+1\) vectors from \({\mathcal L} \cap [0,B)^n\). If the vectors are sampled independently then the probability that they generate \(\mathcal L\) is at least \[ \left( \prod_{ j=2 }^{ n+1 } \zeta(j)^{ -1 } - {1 \over 4} \right) \prod_{ k=0 }^{ n-1 } \left( 1 - n^{ k \over 2 } {{ \left( 4 n^{ n \over 2 } + 1 \right)^k } \over { \left( 4 n^{ n \over 2 } - 1 \right)^n }} \right) . \] This means that \(2n+1\) vectors suffice to generate \(\mathcal L\) with constant probability, provided that \(B\) is chosen sufficiently large. The authors conjecture that the quantity \(2n+1\) in this statement can be replaced by \(n+1\).