Questions tagged [euclidean-lattices]
The euclidean-lattices tag has no summary.
112 questions
3 votes
0 answers
142 views
How fast can we solve SVP using an SVP$_{\gamma}$ subroutine?
An $n$ dimensional lattice is the set of integer linear combinations of $n$ linearly independent vectors in $\mathbb{R}^{d}$ ($d\le n$). The $n$ independent vectors are called the basis of the lattice,...
- 169
3 votes
0 answers
73 views
Lattices of Voronoi's first kind in differential geometry
An $n$-dimensional Euclidean lattice $L$ is called of $\textbf{Voronoi's first kind}$ if it satisfies the $\textbf{obtuse superbasis}$ condition: There exist $x_0, \dots, x_n \in L$ such that $1) x_1, ...
- 327
3 votes
2 answers
177 views
Example of a lattice and its dual where the product of the length of their smallest vector is close to the dimension of the lattice?
Can you show an example of a lattice and its dual where the product of the length of their smallest vectors is close to the dimension of the lattice? Let $L$ be an $n$-dimensional lattice, and let $L^{...
- 169
1 vote
1 answer
189 views
Fundamental set of Euclidean lattices in higher dimensions
We consider the space of $n$-dimensional Euclidean lattices. Define the $i$-th successive minimum of a lattice $\Lambda$ as $ \lambda_i(L) := \min \left\{ r \in \mathbb{R}_{>0} \mid \dim_{\mathbb{R}...
- 327
1 vote
0 answers
90 views
Covering the positive integer point lattice in $\mathbb{R}^2$ with sublattices
Let $P$ be the positive integer point lattice on the plane, that is, all points $(x,y)\in\mathbb{R}^2$ such that $x,y\in\mathbb{N}, x,y>0$. Take $a_i,b_i,c_i\in P$ such that $b_i=(b_{i,x},b_{i,y}) \...
- 1,068
3 votes
0 answers
152 views
What is the status of Mahler’s open problems (from 1946) about the irreducibility of star bodies?
A duplicate of this: I am reading Mahler’s Lattice points in $n$-dimensional star bodies II (1946), in which he poses the following (then) open problems about the irreducibility of star bodies: Do ...
- 327
5 votes
1 answer
287 views
I believe that all facets of a Voronoi-cell of a lattice are centerally symmetric. Is my argument correct? Is this true?
So let $L$ be a full dimensional lattice in $\mathbb{R}^{n}$. Then the Voronoi-cell of the lattice are precisely the points in $\mathbb{R}^{n}$ that are at least as close to the origin, as to any ...
- 169
2 votes
0 answers
103 views
Theta series of well-rounded lattices
I've started looking into well-rounded Euclidean lattices and I was interested in learning whether their theta series have any interesting properties, but haven't found much in terms of bibliography ...
- 327
3 votes
2 answers
286 views
What's the name of this constant similar to that of Hermite's?
Recently i've been thinking about base reduction of lattices, and this constant similar to Hermites constant came up. Let $L$ be a lattice with basis $\mathbf{b}_{1},\ldots,\mathbf{b}_{n}$. We define ...
- 169
4 votes
0 answers
96 views
For which lattices L does the cluster of Voronoi regions abutting that of the origin have a lattice tiling of euclidean space?
Let L be a n-dimensional lattice (a discrete cocompact subgroup of n-space). Let V0 denote the Voronoi region of the origin, and let C denote the union of V0 with all the Voronoi regions that share a ...
- 3,555
12 votes
1 answer
303 views
Number of planes generated by integer vectors
For fixed dimension $d$ and large $R$ consider all non-zero integer vectors in the ball $B(0,R)\subset \mathbb{R} ^d$ of radius $R$ centered at the origin. The number of such vectors grows as $c_d\...
- 115k
3 votes
0 answers
212 views
Understanding why $\frac{\phi^5}{2}$ solves this 3D optimization problem, where $\phi$ is the golden ratio
I would like to understand the deep meaning of a solution which arises from an optimization problem discussed in a paper of mine since it can be simply stated as $\frac{\phi^5}{2}$, where $\phi := \...
- 1,915
8 votes
1 answer
692 views
Joining the $2^k$ points of $\{0,1\}^k$ with the shortest tree
Let $k$ be a given positive integer, and then consider the unit hypercube $\{0, 1\}^k \subset \mathbb{R}^k$ (i.e., a $k$-dimensional "cube" in the well-known Euclidean space). We need to ...
- 1,915
2 votes
0 answers
148 views
Are there other Euclidean lattices whose construction is based on number theoretic identities?
In the book of Conway and Sloane about Sphere packings and Lattices, which is referenced by the video of Borcherds a construction of the Leech Lattice based on the number theoretic identity: $$1^2+2^2+...
- 3,397
3 votes
1 answer
344 views
On shortest vector problem
Assume we have an oracle which gives the length of the shortest vector in a lattice. Given this oracle can we find the shortest vector in polynomial time?
- 1
3 votes
2 answers
279 views
Random walk to visible lattice points
Consider a random walk from the $\mathbb{Z}^2$ origin $(0,0)$ to visible (not blocked) lattice points $p$, with a parameter $r$ a given radius of a circle centered on $p$. With $p$ the previous point, ...
- 153k
3 votes
1 answer
443 views
Illumination from visible lattice points with inverse square intensity
It is well known that the number of $\mathbb{Z}^2$ lattice points visible from the origin is $6/\pi^2$, about $61$%. See, e.g., What fraction of the integer lattice can be seen from the origin?. I am ...
- 153k
1 vote
0 answers
54 views
Does $2$ variable linear Diophantine equation in $NC$ imply $2$ dimensional shortest vector is in $NC$?
Consider the Linear Diophantine in known $a,b,c\in\mathbb Z$ $$ax+by=c.$$ Above can be solve by Extended Euclidean which is not in $NC$ as far as we know. It is clear if Extended Euclidean is in $NC$ ...
- 1
1 vote
1 answer
161 views
Existence of some lattice path connecting all given lattice paths
My daily work concerns analysis on metric spaces and some time ago it turned out that the problem I am dealing with boils down to a certain combinatorial problem. I've checked a lot of examples and it ...
- 147
2 votes
0 answers
114 views
a counting problem on lattice
In $d$-dimensional lattice, we define a set $S_0$ be the zero point. At step $i\geq 1$: For each point $p\in S_{i-1}$, we can choose a single point $q$ who is a neighbour of $p$, and add $q$ into $s_{...
- 1,533
2 votes
0 answers
255 views
Mistake in Rogers' paper: "number of lattice points in a set" for the case $n=2$?
Let $f:\mathbb R^n\to \mathbb R$ be a nonnegative Borel measurable function, and let $f^*$ be the function obtained from $f$ by spherical symmetrization (see Rogers' paper: number of lattice points in ...
- 495
4 votes
2 answers
301 views
How large is the set of unimodular lattices whose sucesssive minima cannot be attained by a basis of lattice?
Recall that the $i$-th successive minimum of $L\in \mathcal L$ (space of full rank lattices in $\mathbb R^d$), denoted $\lambda_i(L)$ is the infimum of the radii of the balls containing $i$-linearly ...
- 495
2 votes
1 answer
318 views
Proof of generalized Siegel's mean value formula in geometry of numbers
Let $\mu$ be the Haar measure defined on the space of unimodular lattices, identified with $\text{SL}(d,\mathbb R)/\text{SL}(d,\mathbb Z)$. The classical Siegel's formula in geometry of numbers states ...
- 495
6 votes
2 answers
625 views
Successive minima and the basis of lattice
I am able to prove the following two propositions: Recall that the $i$-th successive minimum of $L\in \mathcal L$, denoted $\lambda_i(L)$ is the infimum of the radii of the balls containing $i$-...
- 495
2 votes
0 answers
132 views
Find the closest point of a lattice $\Lambda$ given the closest point for its union of cosets $\bigcup_i ({\bf r}_i+\Lambda)$
Suppose we have an $n$-dimensional lattice $\Lambda$, and a set of vectors ${\bf r}_i$, we can construct a union of cosets of $\Lambda$, denoted as $L$, as $$ L \equiv \bigcup_i ({\bf r}_i+\Lambda) $$ ...
- 163
1 vote
0 answers
67 views
How to construct lattices with largest possible number of Voronoi relevant lattice vectors?
Let M be the generator matrix of a $N$ dimensional lattice, and $V$ the set of Voronoi relevant vectors. The Voronoi cell for the origin can be written as $\text{Vor}_{\bf 0}(M)=\left\{{\bf x}: |{\bf ...
- 163
4 votes
1 answer
293 views
Relation between positive roots of $E_8$ and $\mathbb{F}_2^8 \setminus \{0\}$
There exists an explicit bijection (due to Cayley, that has built up a very nice table to describe this) between the positive roots of the lattice $E_7$ and $\mathbb{F}_2^6 \setminus \{0\}$ (where $\...
- 3,747
12 votes
0 answers
370 views
Lattices and stable homotopy groups of spheres
The number $65520$ arises in two very different scenarios: It occurs in the formula for the theta series of the Leech lattice: $$ \Theta_{\Lambda_{24}}(q) = 1 + \sum\limits_{m=1}^{\infty} \dfrac{...
- 12.7k
2 votes
2 answers
538 views
The range of each of successive minima for all unimodular lattices
Let $\mathcal L$ be the space of unimodular (covolume one) lattices in $\mathbb R^d$. The $i$-th successive minimum of $L\in \mathcal L$, denoted $\lambda_i(L)$ is the infimum of the radii of the ...
- 1,575
1 vote
1 answer
174 views
Relationships among lattices U14, C2xG23, A15+ and their Delaunay polytopes
Do you have any references explaining the relationships among the lattices U14, C2xG23 aka Q14, and A15+? Do you have any references explaining the relationships among these lattices and the 7D ...
- 53
0 votes
1 answer
569 views
Standard Gram matrices for lattices
I would like to define standard Gram matrices, and use them to help me understand the symmetries of lattices. I define "standard Gram matrix" as the Gram matrix g that minimizes the ...
- 53
0 votes
0 answers
160 views
Intersecting lattices with surfaces in ${\Bbb R}^d$
Let us fix some bounded surface $S\subset \mathbb{R}^d$. Let $x_1,\dots, x_m \in \mathbb{R}^d \setminus \{ 0_d \}$. I am interested in the maximum number of points that the lattice $$L_m = \left\{ \...
- 2,308
3 votes
0 answers
123 views
How to determine sublattices S of a root lattice R
Let $R$ be a root lattice of a irreducible root system $\Phi$. Suppose $W$ is a Weyl group of $\Phi$ and $S$ is a sublattice of $R$ which is $W$-stable and satisfies $|R/S|<\infty$. For example, ...
- 89
4 votes
1 answer
246 views
Structure of the permutation groups acting on the root systems of Niemeier lattices of type $A_{k}^n$
I have been doing research on the Niemeier lattices with root systems of type, $A_{k}^n$ and I am particularly interested in the finite groups permuting the constituent root systems. These groups ...
- 113
2 votes
1 answer
543 views
Tri-coloring of E8 lattice? Why is the Gram matrix of E8 not unique?
This question is about euclidean lattices, regular arrays of points in $\mathbb R^N$. Why are there 3 Gram matrices for the E8 lattice? They are not related by a similarity transformation; they have ...
- 53
0 votes
0 answers
50 views
On the shortest vectors of lattices generated by powers of generator matrices
Let $B\in\mathbb Z^{n\times n}$ generate a rank-$r$ lattice $\mathcal L_1\subseteq\mathbb Z^n$ and let $B^k\in\mathbb Z^{n\times n}$ generate lattice $\mathcal L_k\subseteq\mathbb Z^n$ assuming $\...
- 1
5 votes
2 answers
584 views
Lattices containing $A_n$ and $D_n$
How many lattices are there which contain both the $A_n$ and $D_n$ lattices of the same dimension as sublattices? So far, I’ve found examples in 1D, 3D, 8D, and 24D.
- 3,213
1 vote
1 answer
225 views
Minimal volume of fundamental domains of lattices
Consider a full rank integer lattice in $\mathbb{R}^n$. Let $v_1$ be the shortest non-zero vector in the lattice, $v_2$ be the shortest one among those not parallel to $v_1$, $v_3$ be the shortest one ...
- 591
4 votes
0 answers
154 views
Deep Holes of the tensor product of two lattices
Let $L_0, L_1$ be Euclidean lattices (say full rank) of dimension $n_i$. Let $\lambda_1(L_i)$ denote the length of the shortest vector of $L_i$, and let $\rho(L_i)$ denote the covering radius of $L_i$:...
- 2,456
7 votes
2 answers
1k views
what is the number of paths returning to 0 on the hexagonal lattice
I am looking for an estimation of the number of paths of length $n$ going from 0 to 0 on the hexagonal (or honeycomb) lattice. I can find plenty on references on self avoiding paths, but I am looking ...
- 1,362
8 votes
3 answers
720 views
What other lattices are obtainable from this noncommutative ring?
Here I will regard $SU(2)$ as the multiplicative group of unit quaternions. There are just three conjugacy classes of finite subgroups $G < SU(2)$ where $[G:C] > 2$ for all cyclic subgroups $C &...
- 3,735
3 votes
2 answers
208 views
Alternating 1D lattice sum
Are there any equivalent representations of the following (real valued) sum, in particular that are suitable for evaluation as $z\rightarrow0$ ? $$ S=\sum_{k=-\infty}^\infty \frac{i^k(z-2ik)}{(\rho^2+(...
- 583
4 votes
1 answer
141 views
Closed cobounded additive submonoid of $\mathbb{R}^n$
Let $M$ be a closed additive submonoid of $\mathbb{R}^n$ with $n\geq1$. Suppose also that there exists $r>0$ such that every ball of radius $r$ intersects $M$. I wonder if we can obtain more ...
- 153
3 votes
0 answers
71 views
Selfsimilar lattices in $\mathbb R^d$
Let $\Lambda\subset \mathbb R^d$ a discrete subgroup, up to diminishing $d$ we assume it is of the form $A\mathbb Z^d$ with $A\in GL(d)$. Up to dilation we assume that the shortest vector in $\Lambda\...
- 2,091
2 votes
0 answers
104 views
Shortest vectors in tensor product and maximal lattices in tensor product
$\mathcal L$ and $\mathcal L'$ be full rank lattices in $\mathbb R^n$ with shortest vectors $v_1,\dots,v_n$ and $v_1',\dots,v_n'$ respectively where $$\|v_1\|_2\leq\dots\leq\|v_n\|_2$$ $$\|v_1'\|_2\...
- 1
4 votes
2 answers
3k views
Can we count the number of integer lattice points in this case?
Gauss Circle problem gives the number of lattice points lie within a circle of radius $r$. This question points to a reference that estimates the number of lattice points in a $d−$dimensional ball. $...
- 225
16 votes
0 answers
467 views
The Monster Moonshine Module from the engineering or algorithmic point of view
From what I understand (see, e.g., this question), the Monster Moonshine Module is a kind if "third generation" (or "second quantization"?) after the Golay code (with automorphism group $M_{24}$) and ...
- 38.2k
11 votes
1 answer
585 views
Tiling with incommensurate triangles
Say that two triangles are incommensurate if they do not share an edge length or a vertex angle, and their areas differ. Suppose you'd like to tile the plane with pairwise incommensurate triangles. I ...
- 153k
5 votes
0 answers
235 views
Isomorphism classes of lattices
Suppose we have a $4 \times 6$ matrix $A$ of rank $4$ whose entries are rational numbers. Define $$ V = \{x \in \mathbb R^6 \mid A \cdot x = 0\} $$ and $$ \Lambda = \{x \in \mathbb Z^6 \mid A \cdot ...
- 1,372
8 votes
0 answers
127 views
Counting symmetric convex bodies with no nonzero lattice point in the interior
In order to estimate the size of the torsion in the algebraic $K$-groups of $\mathbb Q$ one needs to understand the homology of $\mathrm{GL}_n(\mathbb Z)$, or alternatively, the homology of the space ...
- 4,075