Questions tagged [euclidean-lattices]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer
214 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?
41 votes
2 answers
2k views

Can we find lattice polyhedra with faces of area 1,2,3,...?

I asked this question two months ago on MSE, where it earned the rare Tumbleweed badge for garnering zero votes, zero answers, and 25 views over 61 days. Perhaps justifiably so! Here I repeat it with ...
3 votes
2 answers
188 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, ...
3 votes
1 answer
353 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 ...
2 votes
1 answer
376 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 ...
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 ...
4 votes
1 answer
244 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 $\...
1 vote
0 answers
29 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 vote
1 answer
93 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 ...
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_{...
2 votes
0 answers
170 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 ...
4 votes
2 answers
174 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 ...
2 votes
1 answer
197 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 ...
3 votes
1 answer
242 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$-...
2 votes
0 answers
105 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) $$ ...
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 ...
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{...
2 votes
2 answers
129 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 ...
0 votes
1 answer
350 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 ...
5 votes
2 answers
391 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.
1 vote
1 answer
133 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 ...
4 votes
1 answer
175 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 ...
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 ...
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, ...
3 votes
2 answers
281 views

Extremal lattices

Denote by $\mu_n$ the largest value such that there exists a lattice of determinant $1$ in $\mathbb R^n$ for which the distances between different lattice points are greater or equal to $\mu_n$. ...
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 $\...
1 vote
1 answer
162 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 ...
5 votes
0 answers
128 views

Lattice paths in polytopes

Let $P$ be a polytope in $\mathbb{R}^n$. Let $A_ix = b_i$ be the defining equations of its codimension $1$ faces. Is there an algorithm or some kind of criterion to decide if the lattice points inside ...
49 votes
4 answers
4k views

What fraction of the integer lattice can be seen from the origin?

Consider the integer lattice points in the positive quadrant $Q$ of $\mathbb{Z}^2$. Say that a point $(x,y)$ of $Q$ is visible from the origin if the segment from $(0,0)$ to $(x,y) \in Q$ passes ...
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$:...
8 votes
3 answers
616 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 &...
7 votes
2 answers
828 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 ...
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 ...
3 votes
2 answers
154 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+(...
11 votes
1 answer
481 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 ...
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 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\...
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. $...
0 votes
0 answers
882 views

Number of lattice points in a given triangle

Given a triangle with real coordinates, does anybody know how to find the number of lattice points contained within it? What if the points are only rational? I know Pick's formula can be used for the ...
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 ...
2 votes
0 answers
58 views

Configurations of minimal vectors for a 4-dimensional symplectic lattice

The possible configurations of minimal vectors for a 4-dimensional lattice are known for ages, but what about symplectic lattices ? If a 4-dimensional symplectic lattice $\Lambda$ has two minimal ...
5 votes
0 answers
213 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 ...
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 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 ...
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 \...
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{...
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 ...
11 votes
1 answer
541 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/...
3 votes
1 answer
475 views

The right conformal map to make a certain picture

This is a follow-up to a question I asked a year ago, which was helpfully answered by Anton Petrunin: Fitting a mesh to a density function. I am trying to come up with a way to make a picture of an ...
10 votes
2 answers
790 views

Fitting a mesh to a density function

Suppose I have a probability density function defined on a region in the plane (in my case, the pdf is of the form $f(x) = \alpha\|x\|^{-\beta}$, and the region is the unit disk). For large $N$, is ...