← All problems

Conjecture on generating a lattice with n+1 random vectors

14 years old · traced to

Let n∈Nn\in\mathbb{N}. For a full-rank lattice Λ⊂Rn\Lambda\subset\mathbb{R}^n, write det⁡(Λ)\det(\Lambda) for its determinant and λ1(Λ)\lambda_1(\Lambda) for the length of a shortest nonzero vector. For B>0B>0, choose vectors independently and uniformly from Λ∩[0,B)n\Lambda\cap[0,B)^n.

Lattice-generation conjecture. For every n∈Nn\in\mathbb{N}, there exists a constant 0<cn<10<c_n<1 and a rational function fn∈R(x,y)f_n\in\mathbb{R}(x,y) satisfying

∀x0>0 ∀y0∈(0,x01/n]:sup⁡{fn(x,y)∣0<x≤x0, y0≤y≤x1/n}<∞\forall x_0>0\ \forall y_0\in\bigl(0,x_0^{1/n}\bigr]:\quad \sup\bigl\{f_n(x,y)\mid 0<x\leq x_0,\ y_0\leq y\leq x^{1/n}\bigr\}<\infty

such that, whenever B>fn(det⁡(Λ),λ1(Λ))B>f_n(\det(\Lambda),\lambda_1(\Lambda)), the probability that n+1n+1 chosen vectors generate Λ\Lambda is at least cnc_n. Moreover, cnc_n can be chosen close to

∏k=2n+1ζ(k)−1.\prod_{k=2}^{n+1}\zeta(k)^{-1}.

The conjecture strengthens the paper's proved result, which uses 2n+12n+1 samples from two windows of different sizes. It is motivated by numerical evidence and predicts that n+1n+1 samples from a single sufficiently large window suffice with a dimension-dependent constant success probability.

References
  1. Felix Fontein and Pawel Wocjan, “On the Probability of Generating a Lattice”, arXiv:1211.6246 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.