Questions tagged [euclidean-lattices]
The euclidean-lattices tag has no usage guidance.
96
questions
3
votes
1
answer
224
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?
- 13.7k
3
votes
2
answers
191
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, ...
- 149k
3
votes
1
answer
357
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 ...
- 149k
1
vote
0
answers
30
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$ ...
- 13.7k
1
vote
1
answer
95
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 ...
- 127
2
votes
0
answers
87
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,493
2
votes
0
answers
172
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 ...
- 435
4
votes
2
answers
177
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 ...
- 435
2
votes
1
answer
202
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 ...
- 435
3
votes
1
answer
245
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$-...
- 435
2
votes
0
answers
108
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
42
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
246
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,717
11
votes
0
answers
327
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.2k
2
votes
2
answers
132
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,553
1
vote
1
answer
134
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
359
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
1
vote
0
answers
76
views
Intersecting lattices with surfaces in R^d
Let us fix some bounded surface $S\subset \mathbb{R}^d$. Let $x_1,\ldots, x_m$ be some non-zero vectors in $\mathbb{R}^d$. I am interested is the maximum number of points that the lattice $L_m=\{\sum ...
- 2,248
3
votes
0
answers
89
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
177
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
380
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
32
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 $\...
- 13.7k
5
votes
2
answers
393
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.
- 2,689
1
vote
1
answer
163
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
125
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$:...
- 1,861
7
votes
2
answers
836
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,268
8
votes
3
answers
618
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,585
3
votes
2
answers
155
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+(...
- 573
4
votes
1
answer
106
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 ...
- 133
3
votes
0
answers
53
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,031
2
votes
0
answers
85
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\...
- 13.7k
4
votes
2
answers
2k
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
15
votes
0
answers
403
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 ...
- 30.1k
11
votes
1
answer
483
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 ...
- 149k
5
votes
0
answers
214
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,362
8
votes
0
answers
99
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 ...
- 3,975
3
votes
1
answer
159
views
Distance for $GL_n(\mathbb{R})/GL_n(\mathbb{Z})$
One can define the convergence of a sequence $(\Lambda_k)_k$ of full rank lattices as folow : $(\Lambda_k)\underset{k\rightarrow +\infty}{\longrightarrow} \Lambda \iff \forall k\in \mathbb{N} ,\exists ...
- 179
1
vote
1
answer
98
views
Existence of linearly indépendants vectors reaching each minima of a lattice
I was wondering : given a full rank lattice $\Lambda$ of $R^n$ (a discrete subgroup spanning $R^n$) the successive minima of $\Lambda$ are for $1\leqslant i \leqslant n$ $\lambda_i= \min\{r>0 \mid \...
- 179
5
votes
0
answers
806
views
Fractal covering of a plane with complex-base numeral systems - is periodicity necessary?
Taking a base $z$ positional numeral system with digits $a_k\in \{0,\ldots,n-1\}$:
$$s:\left\{(a_k)\in\{0,\ldots,n-1\}^{\mathbb{Z}}: \exists_K \forall_{k>K} \ a_k=0\right \}\to \sum_{k\in\mathbb{...
- 171
3
votes
0
answers
43
views
Periodicity of density of laminated lattices
In Sphere Packings, Lattices and Groups, Conway and Sloane explore laminated lattices. If we let $X_d$ be the set of $d$-dimensional Euclidean lattices where every pair of points are separated by ...
- 12.2k
3
votes
1
answer
90
views
Lattice basis reduction over rings of number fields
Can one use lattice basis reduction algorithms, such as LLL over (low-rank) module lattices over rings of number fields of degree greater than 1? Is there any work on lattice reductions over Euclidean ...
- 1,069
4
votes
1
answer
145
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.7k
2
votes
0
answers
118
views
Gap in Successive minima on lattice spanned by rational and integer combination of integer vectors
We are given a rank $r$ matrix $B\in\Bbb Z^{k\times n}$ where $0\leq r\leq k\leq n$ holds.
We have
$$\mathcal L_\Bbb Z=\{uB\in\Bbb Z^n:u\in\Bbb Z^k\}\subseteq\mathcal L_\Bbb Q=\{uB\in\Bbb Z^n:u\in\...
- 13.7k
2
votes
2
answers
103
views
Integer points spanned by real, rational and integer combination of integer vectors
We are given a rank $r$ matrix $B\in\Bbb Z^{k\times n}$ where $0\leq r\leq k\leq n$ holds.
We have $\mathcal L_\Bbb Z\subseteq \mathcal L_\Bbb Q\subseteq\mathcal L_\Bbb R$ where
$$\mathcal L_\Bbb Z=\...
- 13.7k
1
vote
1
answer
169
views
Closest vertex in a 3D fcc lattice
The 3D fcc (face-centered-cubic) lattice, which has the same packing ratio as the 3D hexagonal close packed lattice, has the following 12 vectors connecting each vertex with its neighbors:
$(1,-1,0),...
- 283
3
votes
1
answer
180
views
"Sparse" Theta Series
The number of integer points with a given norm in the integer grid $\mathbb{Z} \times \mathbb{Z}$ may be calculated via the generating function
$$\theta_3(q)^2= \left(\sum_{n \in \mathbb{Z}} q^{n^2}\...
- 800
11
votes
1
answer
546
views
The lattice handshake number ("nearly kissing" number)?
Update: I'm happy to say that this question has been made essentially obsolete by the breakthrough result of Serge Vlăduţ, who showed that the kissing number is exponentially large: https://arxiv.org/...
- 1,016
1
vote
1
answer
149
views
Densest sphere packing for a given lattice
There is a great deal of fascinating work on the sphere packing problem. I was wondering if there exist methods to find the densest possible packing of a sublattice of a given lattice. In particular, ...
2
votes
0
answers
51
views
Bound on the fundamental region of a sublattice of a Niemeier Lattice
I am working with an 18 dimensional lattice, $W$ say, primitively embedded into a given Niemeier lattice $\mathcal{N}_i$. I am trying to figure out the following: what is the smallest possible ...
6
votes
0
answers
226
views
Positive-definite lattice with O(n,n) Gram matrix generated by minimal vectors
Consider a positive-definite $2n$-dimensional lattice with minimum norm $\mu$. It is sometimes possible to find a generating set of minimal vectors for the lattice such that the Gram matrix takes the ...
- 271