Questions tagged [lattices]
Lattices in the sense of discrete subgroups of Euclidean spaces, as used in number theory, discrete geometry, Lie groups, etc. (Not to be confused with lattice theory or lattices as used in physics! For lattices (ordered sets), use the tag: [lattice-theory])
652 questions
1
vote
0
answers
99
views
Geometry of a $(d-1)$-dimensional lattice
Let $\mathbf u\in\mathbb Z^d$ be a primitive vector (i.e. $\gcd(u_i)=1$) and let $\Pi_{\mathbf u^\perp}$ be the orthogonal projection perpendicular to $\mathbf u$. I want to understand the geometry of ...
- 23.2k
1
vote
0
answers
97
views
3D generalization of lattice square grid problem
Consider the following problem: You're given set of lattice points $\{a_i\}_{i=1}^n=\{(x_i,y_i)\}_{i=1}^n$. You have to cover it with lattice square grid having minimum possible number of nodes.
That ...
- 1,171
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
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
7
votes
3
answers
416
views
Checking a generating set of $\mathbb{Z}^k$
Let $a_1, \ldots, a_n \in \mathbb{Z}^k$. I need to check if $a_1, \ldots, a_n$ is a generating set of $\mathbb{Z}^k$, that is, every vector $v \in \mathbb{Z}^k$ can be represented as an integer linear ...
- 5,590
10
votes
3
answers
903
views
Positive integer combination of non-negative integer vectors
A vector of positive integer numbers with $n$ coordinates is given $a=(a_1,\ldots,a_n)$. It holds that $a_1+\cdots+a_n$ is divisible by some positive integer number $k$. I have checked many cases and ...
- 399
5
votes
0
answers
376
views
Selmer Group of number fields and Ideal lattices
Let $K$ be a totally real number field of degree $n$ and dicriminant $d$, in this article of F.Lemmermeyer the selmer group of $K$ is defined as
$$\text{Sel}(K):=\{\alpha \in K^{\times}: (\alpha)=...
user115191
6
votes
0
answers
290
views
Formula for Schinzel circle with minimum radius
Schinzel's Theorem states that there are a set of circles with a given number of integer points on the circumference of the circle. The theorem includes the equation for an instance of circle given $n$...
3
votes
1
answer
623
views
What high dimensional lattices have Voronoi cells that have this property?
Which high-dimensional lattices (particularly $Z_n^*,D_n,D_n^*,A_n,A_n^*$), exhibit the following property shown in the attached diagram? Two 2D lattices are shown, with the lattice points in red, the ...
- 283
2
votes
0
answers
120
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.9k
2
votes
2
answers
105
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.9k
5
votes
2
answers
231
views
Bounded version of linear and quadratic Hasse--Minkowski theorem
The Hasse-Minkowski theorem states that if
$$Q(x_1,\ldots,x_n) = \sum_{i,j=1}^n a_{ij} x_ix_j$$
is a quadratic form with $a_{ij} \in \mathbb Z$ and $\det (a_{ij}) \neq 0$, then the equation
$$Q(x_1,\...
- 13.9k
1
vote
1
answer
183
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
16
votes
1
answer
664
views
Polynomials leaving invariant the Gaussian integers
It can easily be shown that if a complex polynomial $P$ leaves invariant $\mathbb{Z}$ ($P(\mathbb{Z}) \subseteq \mathbb{Z}$) then it must be a linear combination (with integer coefficients) of Hilbert ...
- 163
1
vote
0
answers
229
views
Geometric interpretation of k-th power of first n natural numbers and summation using Pick's theorem
I want to know is there any interesting properties of this approach or generalization to find $S_k(n)=1^k+2^k+3^k+\cdots+n^k$ by using Pick's Theorem $S=i+\tfrac{b}{2}-1$, where $i$-number of ...
- 19
1
vote
0
answers
129
views
Computing the successive minima of the following lattice in $\mathbb{R}^4$
Let us define the lattice $\Lambda$ in $\mathbb{R}^4$ defined by the matrix
$$
\Lambda = \begin{bmatrix}
A & 0 & 0 & 0 \\
0 & A & 0 & 0 \\
\gamma_1 & \gamma_2 &...
- 3,625
6
votes
2
answers
666
views
Counting points on lattices in inside a box- Geometry of numbers
Let $\Lambda$ be a lattice in $\mathbb{R}^n$, and let $|\mathbf{x}|$ denote the $L^2$ norm. There is a fairly standard argument involving successive minima to obtain an estimate on $N(R)$ which is the ...
- 3,625
9
votes
0
answers
133
views
Is there a reason nice coset representatives exist for Leech or E_8 lattice modulo 2?
Let $\Lambda$ be the Leech lattice. There is a nice set of coset representatives for $\Lambda/2 \Lambda$ given by short vectors [Conway and Sloane, Ch. 10, Theorem 28 or Ch. 23, Theorem 3]. The proof ...
2
votes
0
answers
189
views
Lattice Sieving in Number Field Sieve
I am currently going through Pollard's article on Lattice Sieving and have a few confusions. Firstly, how to figure that $C$ and $D$ in the two-dimensional array so that every $(c,d)$ pair corresponds ...
- 63
4
votes
0
answers
320
views
Using the Bruhat-Tits tree for unitary groups
For now I always worked in the setting of the Bruhat-Tits tree in the $SL(2)$ setting (like in the book of Serre), without any further background about Bruhat-Tits buildings. I would like to adapt ...
- 5,424
0
votes
1
answer
635
views
Mean square displacement for a random walker in a finite system
It is well known that for a simple random walk on a 2D square lattice extending to infinity the mean square displacement of the walk $\langle \mathbf r^2\rangle \propto N \, :(*)$ with $N$ the number ...
user88381
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
1
vote
1
answer
156
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
53
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 ...
5
votes
0
answers
107
views
How well can a rotation separate lattice vectors of equal norm in Z^d?
I'm interested in rotations $R$ that maximally separate integral lattice vectors of equal norm. This question is preliminary, and regards the scaling of those separations as norm goes to infinity.
...
- 271
0
votes
0
answers
290
views
Need any information about an affine lattice
Motivation - I was thinking about calculating the integrals from An interesting integral expression for $\pi^n$? using old plain Riemann sums. There, one needs integrating over that part of $[0,1]^n$ ...
- 18.4k
6
votes
0
answers
180
views
Shortest vector problem with a null vector constraint
Take $\mathbb{Z}^n$ equipped with two symmetric bilinear forms, one positive-definite $(\cdot,\cdot)_A : \mathbb{Z}^n \times \mathbb{Z}^n \to \mathbb{R}$ and one indefinite $(\cdot,\cdot)_J : \mathbb{...
- 271
3
votes
1
answer
763
views
Gauss' Circle Problem at $\left ( \frac{1}{2}, \frac{1}{2} \right ) $
GCP (Gauss' Circle Problem) asks for a closed form for the number of square-lattice points inside a circle, centered at the origin, of radius $r$.
Let's denote by $N(r)$ the number of these points. ...
- 193
1
vote
0
answers
71
views
Packing the box $[0,X^{\delta_1}] \times [0,X^{\delta_2}] \times [0,X^{\delta_3}] \subseteq \mathbb{R}^3$ with cubes
Let $0 < \delta_1 \leq \delta_2 \leq \delta_3 \leq 1$, and consider the box $B := [0,X^{\delta_1}] \times [0,X^{\delta_2}] \times [0,X^{\delta_3}] \subseteq \mathbb{R}^3$. Let $X > 3$ say. Is it ...
- 579
1
vote
1
answer
535
views
Proof claimed of Gauss' Circle Problem
I just wanted to ask wether this problem has already been proved or not.
I know that there are 2 other posts that deal with exactly the same question, but I decided to ask it again, since they are ...
- 193
11
votes
1
answer
442
views
Chromatic number of Voronoi diagrams of lattices
Let $L$ be a Euclidean lattice. Define a graph whose vertex set is $L$ and where two points $x,y\in L$ are declared to be adjacent whenever the cells of $x$ and $y$ in the Voronoi diagram of $L$ have ...
- 32.5k
0
votes
1
answer
218
views
Map homemade Leech lattice to classic one
In following question on MathOverflow I received construction of new Leech lattice provided by Noam Elkies. Let's call it $(E)$. This Leech lattice has nice feature that there is easy to see $24$ ...
user21230
5
votes
0
answers
743
views
Is this set empty?
Suppose we have two rank $n-1$ matrices in $\Bbb Z^{(n-1)\times n}$ given by
$$C=\begin{bmatrix}
c_{1}& -d_{1}& 0& 0&\dots 0& 0\\
0& c_{2}& -d_{2}& 0&...
- 13.9k
12
votes
2
answers
832
views
24 vectors in Leech lattice having scalar product $\frac{1}{4}$ pairwise
Two vectors from Leech lattice - as defined on wikipedia - have scalar product $\pm 32,\pm 16, \pm 8$ or $0$. Do there exist 24 vectors having scalar product 8 pairwise ? When we consider unit vectors ...
user21230
1
vote
0
answers
104
views
On dimension of Segre embedding of lattice translations
Consider three lattices $L_1$, $L_2$ in $\Bbb Z^{n+1}$ and $L$ in $\Bbb Z^{2n+1}$.
Let $L_1+v_1$, $L_2+v_2$ and $L+v$ be their respective translationsfor some $v_1,v_2\in\Bbb Z^{n+1}\backslash\{(0,\...
- 13.9k
1
vote
0
answers
168
views
$\mathsf{LLL}$ and linear diophantine equations
On page $8$ in these slides (http://www.math.unicaen.fr/~nitaj/LatticeMalaysia2014-2.pdf) it is told that if we want to solve $$x_1a_1+\dots+x_na_n=N$$ where $|x_i|<\frac{2^{n/4}N^\frac1{n+1}}{\...
- 13.9k
2
votes
1
answer
181
views
Counting prime points in a bounded region
Let $R$ be a semi-algebraic, compact region in $\mathbb{R}^n$ with positive Lebesgue measure. Let $N(R) = \# (R \cap \mathbb{Z}^n)$. Davenport's lemma asserts that we have
$$\displaystyle N(R) = \...
- 26.9k
2
votes
1
answer
229
views
Upper bound for a higher dimensional Ramanujan sum
Fix an integer vector $\mathbf m\in \mathbb Z^k$. Let $q$ be a positive integer.
Is there a "good" upper bound in terms of $q,\bf m$ for the exponential sum:
\[\sum_{\mathbf n} e\left(\frac{\langle m,...
- 106
6
votes
0
answers
183
views
Root system inside the indefinite even unimodular lattice $II_{10,2}$
I apologize for asking questions that seem likely to be answered in Conway & Sloane's "Sphere Packings, Lattices, and Groups" if I knew where to look.
Let $L$ be the unique* even unimodular ...
- 27.8k
0
votes
2
answers
318
views
Lattice question
Consider a lattice $\mathcal{L} = \mathbb{Z}v_1 \oplus \ldots \oplus \mathbb{Z}v_l$ in $\mathbb{R}^n$ and let $S_0$ be the set of edges of the fundamental unit of $\mathcal{L}$. We call a region $X$ ...
- 501
5
votes
0
answers
129
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 ...
- 501
13
votes
2
answers
697
views
in search of a transformation between determinants
Motivated by this MO question. Consider the two matrices $A_n$ and $B_n$ with entries $\binom{2j}i$ and $\binom{n+1}{2j-i}$, respectively; for $1\leq i, \,j\leq n$.
I can show $\det A_n=\det B_n=2^{\...
- 43.2k
2
votes
0
answers
90
views
Minimal diameter of a class in a number field
Let $\mathbb{K}$ be a number field of degree $n$, let $A = \mathcal{O}(\mathbb{K})$ be the ring of integers and consider the Minkowski embedding
$\mathbb{K} \rightarrow \mathbb{R}^n$ given by $x \...
- 375
5
votes
1
answer
206
views
Lattice with Voronoi cell inside a circle
This considers real-valued lattices in two dimensions.
I need to find the densest lattice $\Lambda$, i.e., the one with the smallest determinant of its generator matrix, such that the Voronoi cell of ...
- 129
1
vote
1
answer
216
views
Subgroup of $SL_2(O)$ with nice fundamental domain in complex upper half-plane
Let $O$ be the ring of $S$-integers in a real quadratic number field. Let $G$ be an $S$-arithmetic subgroup of $SL_2(O)$ whose intersection with $SL_2(\mathbb Z)$ is not of finite index in $SL_2(\...
- 119
2
votes
0
answers
92
views
On design of a (preferrably unimodular) matrix
Assume each entry is in $\Bbb Z$.
Say we want to solve $Ax=b$ where known $A$ is $n\times n$, unknown $x$ is $n\times1$ and $b$ is $n\times1$.
The absolute value of minors of augmented matrix $[A|b]$...
- 13.9k
6
votes
5
answers
4k
views
Package for the Closest Vector Problem (CVP)?
Let $A$ be a positive definite, real $n \times n$ matrix. This defines a norm on $\mathbb{R}^n$. Now I have a given point $p \in \mathbb{R}^n$ and I want to find the lattice point $x \in \mathbb{Z}^n$ ...
- 3,031
6
votes
1
answer
278
views
What is the automorphism group of the tensor square of the Leech lattice?
The tensor square of the Leech lattice is an even unimodular lattice of dimension 576 which, unless I am very mistaken, has no roots. Its automorphism group contains a group of shape $2 \cdot \mathrm{...
- 54.6k
7
votes
1
answer
370
views
Modularity of certain theta series associated to hyperbolic lattice
Let $L$ be an even hyperbolic lattice, i.e. a free $\mathbb{Z}$-module with a non-degenerate inner product $\cdot$ valued in $\mathbb{Z}$ of signature $(1,n)$ such that the norm of every vector is ...
- 1,493
1
vote
0
answers
50
views
Smallest non-zero element in a one-dimensional lattice-like grid [closed]
Given $n$ distinct positive real numbers $A = \{a_1 \ldots a_n\}$, I would like to find a positive lower bound for the absolute value of the non-zero elements of the $\mathbb{Z}$-span $$\langle A\...
- 1,241