Abstract:
A measure $\mu_{n}$ on $n$-dimensional lattices with determinant $1$ was introduced about fifty years ago to prove the existence of lattices which contain points from certain sets. $\mu_{n}$ is the unique probability measure on lattices with determinant $1$ which is invariant under linear transformations with determinant $1$, where a linear transformation acts on a lattice point by point. Our main goal is to formulate a conjectured $0-1$ law about $\mu_{n}$. In the second part of the paper we will also give a method for generating a random lattice with the distribution $\mu_{n}$. As we will see, there are many known and proven $0-1$ laws concerning random structrues, but they are valid for a much smaller set of properties, e.g. first-order definable properties. The infinite sequence $\langle P_{n}\ |\ $, $n=1,2,\ldots \rangle $ is a property of lattices if for each $n$, $P_{n}$ is a set of $n$-dimensional lattices with determinant $1$. We say that a property $P_{n}$, $n=1,2,\ldots $ is polynomial time computable (p.t.c.) if there is a probabilistic Turing machine $T$ so that given a lattice with {\it any} basis as an input $T$ decides with high probability in polynomial time whether $P_{n}$ holds. The conjecture states that for any p.t.c. property if the integer $n$ is sufficiently large then the probability $\mu_{n}(P_{n})$ is either close to $0$ or close to $1$. More precisely we have $\lim_{n \rightarrow\infty}\max \lbrace \mu_{n}(P_{n}),\mu_{n}(\neg P_{n}) \rbrace =1$. The conjecture implies $P\not= NP$ so there is not much hope for proving it, but it gives a way to create a large number of hard lattice problems. (E.g. it implies that for any fixed set $H$ of volume $1$ in $\err^{n}$ it cannot be decided in polynomial time whether a lattice contains a nonzero point from $H$.) We do not think that there is any reason to belive that it is easier to prove $P\not=NP$ through the conjecture than in any other way. Our goal is rather to give a way to create a large collection of computationally hard problems (by accepting a single statement.) As we will show some of these problems may be useful for cryptographic purposes.