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.
854
questions
0
votes
0
answers
11
views
Distribution of "good" and "bad" basis in lattice families?
I'm trying to learn more about lattice based cryptosystems.
One of the fundamental ideas behind lattice based cryptosystems is that there can be many equivalent basis for a single lattice.
Formally, ...
- 1
0
votes
0
answers
12
views
A question on lattice of Complex tori $\mathbb{C}/L$
Let $L$ be a Lattice in the complex plane $\mathbb{C}$ . Let $L=<1,\tau>$, where $\tau\in H $( Upper half plane). Given that $iL=L$. What are the possible values of $\tau$?
So , by hypothesis $i\...
- 610
0
votes
0
answers
18
views
$\{x \mid \exists y, \exists \text{ integral } z \text{ such that } x=Ay+Bz\}$ = $\{x \mid Dx \text{ is integral}; Cx=0\}$
From Alexander Schrijver's Theory of Linear and Integer Programming:
Theorem 4.1
Each rational matrix of full row rank can be brought into Hermite normal form by a series of elementary column ...
- 3
0
votes
0
answers
9
views
Proof of correctness of SVP algorithm for dimension 2
The shortest vector problem (SVP - $p$) consists of finding the shortest vector in a lattice, using the norm $|\!|.|\!|_p$.
For lattices of dimension 2 and using the euclidean norm, our professor ...
- 402
0
votes
0
answers
44
views
Finding small root of $y = ax + b$ over a finite field
Take $a, b \in \mathbb Z / p\mathbb Z$, $p$ being a large prime number.
Suppose there exists a small root $(x, y)$, $x = O(\sqrt p)$ and $y = O(\sqrt p)$ to the equation $y = ax + b \mod p$.
How could ...
0
votes
2
answers
35
views
What does "closed" mean with respect to lattice properties?
If a lattice $L$ is defined as an additive discrete subgroup of $\mathbb{R}^n$, then Nguyen on page 24 from "The LLL Algorithm - Survey and Applications", with respect to important ...
- 204
2
votes
1
answer
20
views
Iterating Lattice Points inside a Parallelepiped in $\mathbb{R}^n$
I have an invertible matrix $M\in\mathbb{R}^{n\times n}$ and I have a hypercuboid $I=I_1\times\ldots\times I_n$ which is a cartesian product of closed intervals, and I want to find all lattice points ...
- 6,235
0
votes
1
answer
49
views
Orthogonal group of Lorentzian lattice $I_{1, n}$ is infinite for $n\geq 2$
I am looking for a reference or an elementary proof of the following fact:
The orthogonal group of the lattice $I_{1,2} = I^+ \oplus 2 I^-$ is ifinite.
Here the Lorentzian lattice $I_{1,n}$ is given ...
- 4,937
2
votes
0
answers
51
views
Is a lattice countable?
I am studying lattices in the sense of a group in the context of number theory/cryptography. I wanted to note this briefly because lattices are not all the same.
There is a definition that a lattice ...
- 204
1
vote
0
answers
21
views
Computing a minimal sublattice containing two other sublattices, GCD of a lattice
I've been trying to read a paper regarding the analogue of a GCD for lattices, but I'm not sure I understand how to decipher this notion. This is given in Section 3.1 when the author discusses the '...
- 5,913
0
votes
1
answer
22
views
Any complex lattice is equivalent to a lattice of the form …
Follow-up question to this one.
A complex lattice consists of a pair of $\mathbb{R}$-linearly independent vectors of the real-vector space $\mathbb{C}$. We call two lattices $(\lambda_1,\lambda_2)$ ...
- 525
0
votes
1
answer
14
views
Any complex lattice admits a certain lattice basis
A complex lattice consists of a pair of $\mathbb{R}$-linearly independent vectors of the real-vector space $\mathbb{C}$. We call two lattices $(\lambda_1,\lambda_2)$ and $(\mu_1,\mu_2)$ equivalent if $...
- 525
0
votes
0
answers
21
views
Classification of two-dimensional complex lattices
A complex lattice consists of a pair of $\mathbb{R}$-linearly independent vectors of the real-vector space $\mathbb{C}$. We call two lattices $(\lambda_1,\lambda_2)$ and $(\mu_1,\mu_2)$ equivalent if $...
- 525
1
vote
0
answers
29
views
Generating set of a complex lattice contains a basis
Let $\Gamma\subset \mathbb{C}$ be a lattice, i.e. a set of the form $\gamma_1\mathbb{Z}+\gamma_2\mathbb{Z}$ where the set of complex numbers $\{\gamma_1, \gamma_2\}$ is $\mathbb{R}$-linearly ...
- 525
0
votes
0
answers
35
views
Tower of Abelian groups $L_1 \subset N_1 \subset L \subset N$ and their quotients [closed]
Let $L_1 \subset N_1 \subset L \subset N$ a tower of infinite, but finitely generated Abelian groups or equivalently $\mathbb{Z} $-modules of same finite rank. Since the notion of rank of $\mathbb{Z}$...
0
votes
0
answers
40
views
An inequality involving the Gram-Schmidt orthogonalization
I’m looking at a set of notes on the LLL algorithm, where we have the following setup: let $b_1,\dots,b_n\in\mathbb Z^n$ be a set of $\mathbb R$-linearly independent vectors, and let $\tilde b_1,\dots,...
0
votes
3
answers
41
views
Lattice with only isotropic vectors (does not exist)
Consider a lattice $ L:=(X, \phi)$, i.e. $X$ is a free $\mathbb Z$ module of finite rank and $\phi:X\times X\to \mathbb Z$ is a non-degenerate, symmetric, bilinear form.
An element $x \in X$ is said ...
- 4,937
1
vote
1
answer
104
views
Show that a vector satisfies some properties after basis change
This is the exercise 12-5 from Introduction to Riemannian manifolds of John Lee.
Let $(v,w)$ be a basis of $\mathbb{R}^2$ and let $\Lambda$ be the lattice generated by them.
Let $\tilde v$ be the ...
- 544
0
votes
0
answers
15
views
How "unorthogonal" can a LLL-reduced basis be?
I have been recently studying LLL-reduction. I get from the size condition and Lovasz condition that the basis are guaranteed to be somewhat orthogonal. But I couldn't figure out how orthogonal the ...
- 11
0
votes
0
answers
6
views
How far can two points be in the fundamental parallelepiped of a LLL-reduced basis?
Given the lengths $\{d_1, \dots, d_n\}$ of a LLL-reduced lattice basis $\{\mathbf{d}_1, \dots, \mathbf{d}_n\}$, how far can two points be in the fundamental parallelepiped of a LLL-reduced basis? I.e.,...
- 11
1
vote
0
answers
30
views
For polytopes in $\mathbb{R}^n$, bound number of lattice points by its volume?
Suppose we are considering polytopes in $\mathbb{R}^n$ given by equations of the form $Ax \le b$. Given that the polytopes are bounded, can we upper bound the number of lattice points of the polytope ...
- 2,304
0
votes
0
answers
7
views
How to estimate the order of magnitude of the solution to a closest vector problem?
Given a closest vector problem (CVP):
Let $\mathbf{B}=[\mathbf{b}_1, \mathbf{b}_2, \dots, \mathbf{b}_n]$ be the basis matrix of the lattice $\mathcal{L}(\mathbf{B})=\{\mathbf{Bx}|\mathbf{x} \in \...
- 11
0
votes
0
answers
28
views
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)}...
- 188
1
vote
1
answer
62
views
Unimodular matrices of size $n$
Recently, I answered this question on physics stack exchange. So, this motivated me to generated all unimodular matrices of size $n$. For n=1, it is trivial. While for $n=2$, one can pick $\vec{v} = (...
- 196
0
votes
1
answer
14
views
What is the similarity or difference between the lattices $\mathcal{L}_1$ and $\mathcal{L}_2$?
Consider the $2$-dimensional $\mathbb Q$-vector space $\mathbb Q^2$. Let $\{v,w \}$ be a basis of this vector space. Consider the following lattices
\begin{align}
&\mathcal{L}_1=\{iv+jw\},~i,j \in ...
- 165
1
vote
1
answer
56
views
Orthogonal complement of codimension one sublattice in $\Bbb Z^n$
Let $e_1,\dots,e_n$ be the standard basis of $\Bbb Z^n$, and consider the standard lattice structure given by $\langle e_i,e_j\rangle=\delta_{i,j}$. Suppose we have a sublattice $L\subset \Bbb Z^n$ of ...
- 1,974
0
votes
0
answers
17
views
Best lattice shape from the point of view of isometries
My question may not be well defined and I would appreciate any input that helps in clarifying it. I have put an image description of the question below.
Consider a discrete lattice $L$ of dimension $...
- 123
2
votes
0
answers
59
views
What lattices beyond the laminated lattices (particularly in $\le 24D$) belong to a slightly expanded category that includes "descendants" of Λ13_mid?
Back in 2016, in his proposed answer to the question asked at Packing of n-balls , achille hui ( https://math.stackexchange.com/users/59379/achille-hui ) gave the following definition of laminated ...
1
vote
0
answers
24
views
Reduced $O_K$-basis for a free $O_K$-module
Background:
let $L \subset \mathbb{Q}^n$ be a lattice (i.e. a finitely generated $\mathbb{Z}$-module). Then $L$ has a reduced basis, that is, a $\mathbb{Z}$-basis $v_1, \dots, v_r$ satisfying $\prod_{...
- 578
1
vote
0
answers
32
views
A lower bound on the number of integer lattice points inside a 0-symmetric convex body
I've been doing some reading around the number of points of $\mathbb{Z}^n$ inside an arbitrary rank $n$, $0$-symmetric convex body $K$. In particular, I came across Blichfeldt's remarkable bound:
$$
\...
- 658
0
votes
1
answer
25
views
Check whether a vector is within the fundamental parallelepiped of a lattice
I am studying mathematics of lattices and I came up with a question but I am still unable to answer it.
Given a integer lattice $\mathcal{L}(B) = \sum_{i=1}^nx_ib_i:x_i \in \mathbb{Z}$, and a point $t$...
- 1
0
votes
0
answers
22
views
How to calculate volume of root lattices $A_n$
Is there anywhere in the bibliography an explanation as to why the volume of the root lattice $A_n$ is $\sqrt{n+1}$?
$$A_n = \biggl\{(x_0,x_1,\dots,x_n) \in \mathbb{Z}^{n+1} : \sum_{i=0}^{n} x_i = 0\...
- 179
0
votes
1
answer
110
views
What does "randomized reductions" in the SVP problem mean?
The SVP problem in Lattice Cryptography is said to be NP-hard under "randomized reductions". What does the phrase "randomized reductions" mean?
Does it mean the "basis" ...
0
votes
0
answers
19
views
Bounding the distance of a target vector from a lattice
Given $n$ linearly independent vectors $b_1, \ldots, b_n \in \mathbb{Z}^m$, we define the lattice $\mathcal{L} = \{\sum_i x_i b_i \mid x_i \in \mathbb{Z}\}$.
Given a target vector $t \in \mathbb{Z}^m$,...
- 12.3k
1
vote
0
answers
43
views
Sum equal to product in $\mathbb{Z}/n\mathbb{Z}$ under constraints
I need to solve the following problem.
Let $A=\{a_0,a_1,a_2,\cdots,a_k\}$
Find $a_i$ such that:
$|A|\geq 3$
$a_i\in \mathbb{N}$ and $a_i\in [32,127]$
$p=\sum_i a_i$ is prime
and
$\sum_i a_i = \prod_i ...
- 304
0
votes
0
answers
15
views
Finding a lattice vector in $\mathcal{L}(b_1, \ldots, b_n)$ within a distance $(\|b_1\|^2 + \cdots + \|b_n\|^2)^{1/2}/2$ from a given point
Given a lattice $\mathcal{L} \subset \mathbb{R}^m$ with a $\delta$-LLL reduced basis $\{b_1, b_2, \ldots, b_n\}$ and a vector $x \in \mathbb{R}^m$, how do I find a lattice vector $\ell \in \mathcal{L}$...
- 12.3k
0
votes
1
answer
47
views
Probability for an uniform matrix $A \in \mathbb{Z}_q^{n\times m}$ to have $A \mathbb{Z}^m_q = \mathbb{Z}^n_q$ (q power of a prime $b>2$) [closed]
I will note $\mathbb{Z}_q = \mathbb{Z}/q\mathbb{Z}$.
I read in a lecture of Micciancio about lattices (exercice 5), that for any $q, m, n \in \mathbb{Z}$, we have $\mathbb{P}_{A \in \mathbb{Z}_q^{n \...
- 27
1
vote
1
answer
54
views
If $B$ is an integer matrix, does $\mathrm{det}(B^TB)$ has to be a perfect square?
Suppose $B \in \mathbb{Z}^{m \times n}$ be an integer matrix of rank $n$. I want to prove that $\mathrm{det}(B^TB)$ is a perfect square.
Of course if $m=n$, $\mathrm{det}(B^TB) = \mathrm{det}(B)^2$ ...
- 12.3k
0
votes
0
answers
50
views
Rotation property of dual lattice
The dual lattice is defined like this:
$$\Lambda^* = \{v \in \text{span}_\mathbb{R}(\Lambda): \langle v, w \rangle \in \mathbb{Z} \, \text{for all } w \in \Lambda\}$$
The dual lattice has the ...
- 204
1
vote
0
answers
29
views
Two variable Ehrhart polynomials
Is it possible to count the number of lattice points in a polytope that is scaled unevenly in two dimensions (or more generally mapped by some linear map) by some kind of two variable Ehrhart ...
- 7,659
0
votes
1
answer
33
views
Blichfeldt vs Minkowski Theorems (Mathematics of Lattices)
I am trying to study and understand the basic theorems about mathematics of lattices.
In particular, I understood statements and proofs of both Blichfeldt and Minkowski. My doubt was about their ...
- 1
0
votes
1
answer
50
views
Given a basis set of a lattice and the normalized shortest vector of this lattice, can we solve SVP efficiently (i.e. in poly time)?
Given a basis set B (say $m \times n$), denote the lattice by L(B), also given a unit vector $\vec{d} = \frac{1}{\lambda_1}\vec{u}$, say $\vec{u}$ is the unique shortest vector of L(B). In other words,...
- 1
0
votes
0
answers
28
views
convex polyhedral cone interpretation
According to my text, a convex polyhedral cone in $N_{\mathbb{R}}$, is a set of the form $\sigma = \big \lbrace \: a_1n_1+\cdots +a_rn_r \mid a_i\in \mathbb{R}_{\geq 0} \: \big \rbrace$ generated by a ...
- 325
0
votes
1
answer
25
views
Are these two conditions always equivalent for the lattice $\mathbb Z^d$ for any property (P)?
Consider the lattice $\mathbb Z^d$ in $\mathbb R^d$ and the following two statements:
Let $(P)$ be a property on vectors in $\mathbb R^d$ and let $1\le k \le d$.
(1) For any $k$ linearly independent ...
- 379
0
votes
0
answers
23
views
generator of the lattice $L\subset \Bbb{C}$
Let $L\subset \Bbb{C}$ be a lattice, assume there is a $\gamma \in \Bbb{C}$ such that $\gamma L = L$, prove the following two facts:
(1) $\gamma$ must be roots of unity
(2) if $\gamma$ is not real, ...
- 4,284
0
votes
1
answer
39
views
Standard reference for a fundamental theorem on classification of root lattices
In Schuett-Shioda's Mordell-Weil Lattices, the authors refer to a fundamental theorem on root lattices:
Theorem 2.25 Any positive-definite even integral root lattice is isometric to an orthogonal sum ...
- 9,309
1
vote
0
answers
24
views
Number of elements in $\text{SL}(d,\mathbb Z)$ with bounded $2$-norm
I wonder if there are good estimate for the number of elements in $\text{SL}(d,\mathbb Z)$ with $2$-norm bounded by $T$ as $T \to \infty$, namely
$$\#\{g\in SL(d,\mathbb Z):\|g\|_2:=\sqrt{ \sum_{ij}g_{...
- 379
0
votes
1
answer
24
views
Upper Bound on the shortest non-zero non-negative vector in an integer lattice
Suppose we have an integer lattice of full rank $L\subseteq\Bbb{Z}^n$, say of determinant $D$.
Do we have a nice bound on the smallest non-zero vector $x\in L$ s.t. $x_i\geq0$ for all $i$? Perhaps ...
- 746
0
votes
0
answers
40
views
Estimating number of lattice points on a hyperbola
Given a hyperbola $$y = x + \frac n x \tag 1$$ and a range $x \in (a,b)$, how do we find the number of lattice points lying in the range that the hyperbola passes through? A lattice point is a point $(...
- 2,182
2
votes
0
answers
42
views
Intersecting a lattice with a linear subspace.
Let $ W $ be a linear subspace of $ \mathbb{R}^n $.
Let $ \Gamma $ be the $ \mathbb{Z} $ span of some set of linearly independent vectors $ v_1, \dots, v_k $ in $ \mathbb{R}^n $.
Is there any ...
- 5,682