<p><strong>Definitions:</strong></p>

<p>Consider a polytope $P \subset \mathbb{R}^n$ with a nonempty interior to be $P : \{x \in \mathbb{R}^n | Ax \le B\}$ for appropriate real $n \times m$ matrix $A$ and $m \times 1$ vector $B$.</p>

<p>Furthermore consider a lattice $L$ to be all points spanned by positive integer linear combinations of a basis set of vectors $\mathbb{B} = V_1, V_2, ..., V_b$ where $V_i \in \mathbb{R}^n$, so that $L = \{\sum_{i}{c_i \times V_i} | c_i \in \mathbb{Z}^+\}$.</p>

<p><strong>Referenced work:</strong></p>

<p><a href="http://www.renyi.hu/~barany/cikkek/rsurv.pdf" rel="nofollow">Random points and lattice points in convex bodies</a> I Bárány et al</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.1583&amp;rep=rep1&amp;type=ps" rel="nofollow">Sampling Lattice Points</a> R Kannan et al</p>

<p><strong>Problem:</strong></p>

<p>The above referenced work illustrates how one might randomly sample integer lattice points within the body of a polytope and use the results to approximate the size of the polytope, which is known to be $\#P$ hard to calculate in the general case. Furthermore they give sufficient conditions for when the sampling procedure will output a reasonable approximation (within polynomial factors).</p>

<p>These two papers assume the input lattice is the integer lattice $\mathbb{Z}^n$. For my application, I want lattice points spanned by a separate basis set.</p>

<p><strong>Question:</strong></p>

<p>While the general procedures used in the above papers to sample random integer lattice points seems adaptable to other lattices, the bounds necessary for nearly-uniform sampling may not. Do the same bounds and sampling procedures hold immediately for other basis vectors?</p>

<p>More directly, I am seeking a quick (polynomial time) nearly-uniformal sampling procedure that can output points in $P \cap L$ with inputs $A, B, n, $ and $\mathbb{B}$.</p>

CC BY-SA 3.0
2014-01-04T14:26:32.670Z
Why can't you apply an affine transformation to space that takes the lattice to the integer lattice ${\mathbb{Z}^n}$ and the convex polytope to a different convex polytope?
Peter Shor 
CC BY-SA 3.0
2014-01-05T01:40:14.593Z
Not all lattices can be mapped to $\mathbb{Z}^n$. For example, if the lattice is spanned by the basis $\{<0,1>, <1,0>\}$ there is no transform between the two if $n > 2$.
Ross Snider
CC BY-SA 3.0
2014-01-05T01:58:33.010Z
All full-dimensional lattices can be mapped to ${\mathbb{Z}}^n$. If the lattice isn't full-dimensional, you can take the intersection of the polytope with the subspace spanned by the lattice, and obtain a smaller-dimensional problem.
Peter Shor 
<co.combinatorics><lattice><integer-lattice>
Nearly-uniformally sampling lattice points from a basis that lie on the interior of a polytope
Ross Snider
# Nearly-uniformally sampling lattice points from a basis that lie on the interior of a polytope

(Asked by: username_0 on 2014-01-04)

**Definitions:**

Consider a polytope $P \subset \mathbb{R}^n$ with a nonempty interior to be $P : \{x \in \mathbb{R}^n | Ax \le B\}$ for appropriate real $n \times m$ matrix $A$ and $m \times 1$ vector $B$.

Furthermore consider a lattice $L$ to be all points spanned by positive integer linear combinations of a basis set of vectors $\mathbb{B} = V\_1, V\_2, ..., V\_b$ where $V\_i \in \mathbb{R}^n$, so that $L = \{\sum\_{i}{c\_i \times V\_i} | c\_i \in \mathbb{Z}^+\}$.

**Referenced work:**

[Random points and lattice points in convex bodies](http://www.renyi.hu/~barany/cikkek/rsurv.pdf) I Bárány et al

[Sampling Lattice Points](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.1583&rep=rep1&type=ps) R Kannan et al

**Problem:**

The above referenced work illustrates how one might randomly sample integer lattice points within the body of a polytope and use the results to approximate the size of the polytope, which is known to be $\#P$ hard to calculate in the general case. Furthermore they give sufficient conditions for when the sampling procedure will output a reasonable approximation (within polynomial factors).

These two papers assume the input lattice is the integer lattice $\mathbb{Z}^n$. For my application, I want lattice points spanned by a separate basis set.

**Question:**

While the general procedures used in the above papers to sample random integer lattice points seems adaptable to other lattices, the bounds necessary for nearly-uniform sampling may not. Do the same bounds and sampling procedures hold immediately for other basis vectors?

More directly, I am seeking a quick (polynomial time) nearly-uniformal sampling procedure that can output points in $P \cap L$ with inputs $A, B, n, $ and $\mathbb{B}$.

**Tags:** co.combinatorics, lattice, integer-lattice

> **Comments:**
> **username_1**: Why can't you apply an affine transformation to space that takes the lattice to the integer lattice ${\mathbb{Z}^n}$ and the convex polytope to a different convex polytope?  
> **username_0**: Not all lattices can be mapped to $\mathbb{Z}^n$. For example, if the lattice is spanned by the basis $\{<0,1>, <1,0>\}$ there is no transform between the two if $n > 2$.  
> **username_1**: All full-dimensional lattices can be mapped to ${\mathbb{Z}}^n$. If the lattice isn't full-dimensional, you can take the intersection of the polytope with the subspace spanned by the lattice, and obtain a smaller-dimensional problem.  

---

## 0 answers

