Questions tagged [integer-lattices]

A lattice in $\mathbb R^n$ is a discrete subgroup of $\mathbb R^n$ or, equivalently, it is a subgroup of $\mathbb R^n$ generated by linearly independent vectors. Lattices have applications in geometric number theory, e.g. via Minkowski's theorem.

In geometry and group theory, a lattice in $\Bbb R^n$ is a subgroup of the additive group $\Bbb R^n$ that is isomorphic to the additive group $\Bbb Z^n$ and that spans the real vector space $\Bbb R^n$. In other words, for any basis of $\Bbb R^n$, the subgroup of all linear combinations with integer coefficients of the basis vectors forms a lattice. A lattice may be viewed as a regular tiling of a space by a primitive cell.

Lattices have many significant applications in pure mathematics, particularly in connection to Lie algebras, number theory, and group theory. They also arise in applied mathematics in connection with coding theory, in cryptography because of conjectured computational hardness of several lattice problems, and in the physical sciences. For instance, in materials science and solid-state physics, a lattice is a synonym for the "frame work" of a crystalline structure, a 3-dimensional array of regularly spaced points coinciding in special cases with the atom or molecule positions in a crystal.

894 questions
1
vote
1 answer

Lattice formed by a linear congruence

Let there be a linear congruence $a+b y \equiv 0 \pmod{m}$, with $y$ and $m$ ($m$ is a prime) values known. Do all the integer $(a,b)$ pairs satisfying the congruence form a lattice? If yes, how can I find two vectors (i.e. the basis) which generate…
1
vote
1 answer

Basis condition in lattices

Let $\Lambda$ be a lattice in $\mathbb{R}^n$ (i.e. a discrete subgroup spanning the whole space). Given a basis $e_1,\dots,e_n$ of the lattice, we can consider the fundamental parallelogram $P$ induced by these vectors. The following result…
Klaus
  • 4,105
1
vote
0 answers

Is Pick's formula true for a general (non-integer-vertices) lattice?

Does Pick's formula hold for non-integer lattices (nodes with non-integer coordinates)? I heard that it holds for any lattice (given lattice is: we take two groups of parallel lines and intersect them - so we have a lattice based by a fundamental…
1
vote
1 answer

Lattice points below a curve

Assume a curve represented by a function $f(b)=0.5(\sqrt{N-b^2}-b+1)$ with $1\leq b \leq \sqrt{\frac{N}{2}}$. I want to count the lattice points below this curve, more specifically, I would like a closed form expression. I can assume this figure to…
RTn
  • 299
1
vote
0 answers

Bound for the minimal vector of an indefinite lattice

Let $L$ be a positive definite lattice. Then we have different bounds for the norm of the minimal vector of $L$. But if $L$ is indefinite of determinant $\det(L)=d$ and rank $r$, does it exists a bound $M$, depending only on $d$ and $r$, on the…
user84976
  • 674
1
vote
1 answer

When is the Dirichlet region of a lattice a rectangle?

Given a lattice $L$ defined by its generators $w_1$ and $w_2$, how can we tell if the Dirichlet region of $L$ is a rectangle? For example, the Dirichlet region for $L = (w_1, w_2) = \left(1, \frac 1 2 e^{i \pi / 3}\right)$ looks like a…
1
vote
1 answer

How to check if elements form a primitive system of a lattice

Given a collection of vectors $V = \{v_1, v_2, ..., v_k \}$ belonging to a lattice $L$ with basis $B$, is there an efficient procedure that can determine whether or not $V$ forms a primitive system for $L$? This means that if $L$ has rank $n \geq…
Latrace
  • 153
1
vote
2 answers

Can points on an integer lattice form the vertices of a regular hexagon

Is it possible for six points in the integer lattice to form the vertices of a regular hexagon
user413048
1
vote
1 answer

Enum algorithm of BKZ lattice reduction algorithm

I am trying to understand the Basic Enumeration algorithm of BKZ algorithm for lattice reduction. At this point I understand all the algorithm except line 8 where we set $u_t \leftarrow \text{round}(c_t)$. This step corresponds when we move down in…
Leafar
  • 1,723
1
vote
1 answer

Is it true that for a lattice $L$, $\mathbb{R}L = \mathbb{R}^{n}$?

I have as a definition A lattice $L \subseteq \mathbb{R}^{n}$ is a subgroup that is free of rank $n$ such that $\mathbb{R}L = \mathbb{R}^{n}$. I don't know if I am misinterpreting the statement, but taking $\mathbb{Z}^{2} \subseteq…
Jacob Bond
  • 1,275
1
vote
0 answers

Coexistance of certain vectors in a lattice

I'm currently working on the SVP (Shortest Lattice Vector Problem) as a part of a paper that I'm writing. I've been trying to prove ( or disprove) the following without too much success : Question : Does there exist a lattice such that when we…
0
votes
1 answer

show that L^+ is non-empty

I want to show that $L^+$ is non-empty where $L$ is a full-rank integer lattice and $L^+$ denotes the set of elements of $L$ having positive coordinates I have an indication that I did not understand $L \otimes \mathbb{Q} ⊆ \mathbb{Z}^n \otimes…
mehyeddine
  • 21
  • 4
0
votes
0 answers

shortest vector in lattice with linearly dependent integer vectors as generators

I have a lattice generated by $m$ integer vectors such that each generator lies in $\mathbb{R}^n$ for $m > n$. This clearly implies that these vectors are linearly dependent. For lattices generated by linearly independent vectors, Minkowski's…
0
votes
0 answers

Proof for the successive minima being achieved by linearly independent lattice vectors?

In https://arxiv.org/abs/2305.19777, there is a fact stated as folklore. Here it is. Fact 2.7 (Folklore). For any $q\in\mathbb{N}$, lattice $\mathcal{L}\in\mathbb{R}^n$ of rank $k$ there exist linear independent vectors $u_1,\dots,u_k\in\mathcal{L}$…
Marc Dinh
  • 193
  • 7
0
votes
0 answers

Complete a set of vectors to a basis of a given lattice

Suppose $B \in \mathbb{R}^{n \times k}$ is a basis for a lattice $L$ of dimension $k$ ($n \geq k$ and the basis vectors are on the columns of $B$). Suppose also we have a set of $n$-vectors $\{ v_{(1)}, v_{(2)}, \cdots, v_{(\ell)} \}$, $1 \leq \ell…
Latrace
  • 308