All Questions
Tagged with lattices convex-geometry
22 questions
33
votes
3
answers
2k
views
Polar body of a convex body that avoids a lattice
Let $K \subset {\bf R}^d$ be a symmetric convex body (an open bounded convex neighbourhood of the origin with $K = -K$) with the property that $K + {\bf Z}^d \neq {\bf R}^d$, i.e. the projection of $K$...
- 114k
18
votes
1
answer
911
views
Is the ball reducible in some high dimension?
Let $K$ be a bounded symmetric ($-K=K$) open convex body in $\mathbb R^n$. The critical determinant $d(K)$ of $K$ is the least possible volume $|\operatorname{det}(a_1\dots a_n)|$
of the fundamental ...
- 61.9k
14
votes
2
answers
883
views
Lattice points and convex bodies
Given are two convex bodies $K, L \subset \mathbb{R}^n$ that contain the origin as an interior point. Assume the number of integer points contained in $\lambda K$ equals the number of integer points ...
- 13.5k
10
votes
3
answers
985
views
Approximate volume computation and lattice point enumeration - hardness
Both volume computation and lattice point enumeration of convex polyhedron are $\#P$ hard. However there is a randomized polytime algorithm for constant factor approximation for volume computation.
...
- 13.9k
9
votes
1
answer
946
views
Reference request: Ehrhart's conjecture on the geometry of numbers
Conjecture (Ehrhart). If a convex body $K \subset {\mathbb R}^n$ has its barycenter at the origin and contains no other point with integer coordinates, the volume of $K$ is less than or equal to $(n +...
- 13.5k
8
votes
3
answers
2k
views
Listing lattice points in a simplex
Let $n \in \mathbf{Z}_{\geq 1}$. Is there an algorithm which, given a simplex $\Delta \subset \mathbf{R}^n$ specified as the convex hull of $v_0,\dots,v_n \in \mathbf{Z}^n$, computes the set $\Delta \...
- 3,009
8
votes
1
answer
224
views
Translative packing constant strictly larger than lattice packing constant
Simply put, my question is this: what is the smallest dimension, if any,
where we can know for sure that a convex body exists whose translative
packing constant is strictly larger than its lattice ...
- 5,971
8
votes
0
answers
315
views
Minkowski's convex body theorem for ellipsoids
Minkowski's theorem states that if $K\subseteq\mathbb{Z}^n$ is a convex compact set, $K=-K$, and $\mathrm{volume}(K)\geq 2^n$, then $K$ contains a nonzero integral vector.
Can this bound be improved ...
- 219
6
votes
2
answers
982
views
Decomposing polyhedral cones into "direct sums" and a polynomial
This question consists of two parts. I'm not breaking it up into two separate ones because posing the second question would essentially require me two rewrite the first one. Also, to some extent, the ...
- 3,513
6
votes
1
answer
337
views
Edges of the contact polytope of the Leech lattice
Let $P\subset\Bbb R^{24}$ be the contact polytope of the Leech lattice, that is, $P$ is the convex hull of the 196,560 shortest vectors of $\Lambda_{24}$.
Question: What are the edges of $P$?
Let'...
- 13.6k
6
votes
2
answers
994
views
Minkowski successive minima inequality for a lattice base?
Let $\Lambda$ be a lattice of $\mathbb{R}^n$, and $\lambda_i$ be the radius of the smallest ball containing $i$ linearly independent lattice vectors.
The Minkowski successive minima inequality says ...
- 403
5
votes
1
answer
753
views
Bounding the number of lattice points inside an $n$-dimensional ellipsoid
I am wondering if it is possible to produce an upper and/or lower bound on the number of integer lattice points that lie inside an $n$-dimensional ellipse.
That is, given an $n$-dimensional ellipsoid ...
- 379
5
votes
1
answer
329
views
A question of compactness in the geometry of numbers
Given a star body $S \subset \mathbb{R}^n$ with the origin as interior point, the critical determinant of $S$---usually denoted as $\Delta(S)$---is the infimum of the determinants of all lattices ...
- 13.5k
4
votes
1
answer
150
views
On necessary condition for no integer points in polytope
For a convex polytope $\mathcal K$ in $\Bbb R^n$ presented by $O(n^c)$ linear inequalities is it true that for $|\mathcal K\cap \Bbb Z^n|=0$ it is necessary that at least one axis of John's ellipsoid ...
- 13.9k
4
votes
0
answers
94
views
Getting more out of Minkowski's convex body theorem in the case of non-convex bodies
Problem. In number theory one generally proves the finiteness of the Picard group of a number field using Minkowski's convex body theorem. The actual body $S_p$ of interest in the proof, depending on ...
- 141
3
votes
0
answers
281
views
Improvements to Minkowski's second theorem
Let $L$ be a (full rank) lattice in $\mathbb{R}^t$ and let $K$ be a convex body. Minkowski's second theorem states that
$$
\frac{2^t}{t!} \det(L) \leq \lambda_1 \cdot \ldots \cdot \lambda_t \text{Vol}(...
- 502
3
votes
0
answers
383
views
A question on the theorem of Minkowski-Hlawka
The Minkowski-Hlawka theorem (as stated by Gruber in his lovely book Convex and Discrete Geometry) says that if $S$ is a Jordan measurable set in $\mathbb{R}^n$ with volume < 1. Then there is a ...
- 13.5k
2
votes
1
answer
159
views
Counting lattice points can some give all?
Given convex polytope $\mathcal P\subseteq\Bbb R^n$ with $\mathcal P_\Bbb Z\leq2^n$ integer points and given locations of $O(\log \mathcal P_\Bbb Z)$ integer points in some positions can we obtain $\...
- 13.9k
2
votes
0
answers
111
views
Can computers take uniform samples from a polytope?
For each $r \in \mathbb N $ write $\mathbb Z/ 10^r = \{a/10^r: a \in \mathbb Z\}$ and $P(r)$ for the lattice $(\mathbb Z/10^r)^N \subset \mathbb R^N$.
Suppose the plane $P \subset \mathbb R^N$ is ...
- 1,955
1
vote
1
answer
90
views
Affine semigroup generating a lattice
This is a cross-post from MSE.
Everything is assumed to be finite-dimensional. Let $S$ be a finitely generated affine semigroup (i.e. a subsemigroup of a lattice $N$ of a Euclidean space). Assume that ...
- 1,374
1
vote
0
answers
124
views
Number of lattice points in a structural symmetric convex body
Let $f$ is a convex symmetric function on the interval $[-a,a]$, i.e., $f(-x)=f(x)$ for $\forall \, x\in [-a,a]$. Then we consider a $n$-dimensional convex body in Euclidean space
\begin{equation}
\...
- 550
1
vote
0
answers
53
views
Is it possible that a convex cone and its closure both induce vector lattices?
Given a convex cone $P\subset X$ where $X$ is a $K$-vector space, $K=\mathbb{R}\text{ or }\mathbb{C}$ is a field.
Suppose that $P$ satisfies positive element stipulations.
(1) $X=P-P$.
(2) $P\cap-P=...
- 8,071