__
TR02-061 | 14th November 2002 00:00
__

#### A conjectured 0-1 law about the polynomial time computable properties of random lattices, I.

**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.