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])
687 questions
3 votes
2 answers
317 views
Shortest vector in orthant of lattice
There are many great algorithms for enumeration of vectors in a lattice such as Fincke-Pohst-Kannan, extreme pruning etc, not to mention great implementations such as fplll. Let $L$ be high density (...
- 273
1 vote
1 answer
134 views
Reference request: every lattice is a direct summand of a diagonal one
I'm reading Wall's paper "On the orthogonal group of quadratic forms II", and I'm stuck at the following statement: "As each lattice is a direct summand of some $X$ such that the ...
- 147
2 votes
0 answers
58 views
Comparing $i$ th minima of a lattice and discrete subgroup
This is a continuation of the previous question Comparison between first minimum of a lattice and a discrete subgroup in function field. Let $\mathbb{F}_q(T)$ denote the function field over $\mathbb{F}...
- 151
2 votes
1 answer
141 views
Existence of an "optimal" short free family in an euclidean lattice
We define the successive minima in a lattice $L$ of rank $n$ as in Daniele Micciancio and Shafi Goldwasser, Complexity of lattice problems. A cryptographic perspective, The Kluwer International Series ...
- 41
0 votes
0 answers
58 views
Existence of rank 3 lattice of signature (1,2) containing two copies of $U$ intersecting in a positive vector
Let $U = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ denote the standard hyperbolic plane. I am trying to construct, for a given natural number $N$, an explicit example of a rank 3 lattice $...
- 1,943
1 vote
0 answers
61 views
Gluing lattices along isomorphic sublattices: determinant equalities or inequalities in indefinite signature
$\DeclareMathOperator\rank{rank}$I have the following question concerning lattices in the sense of free $\mathbb{Z}$-modules equipped with an integral symmetric bilinear form, possibly indefinite. Let ...
- 1,943
0 votes
0 answers
42 views
What is the complexity of solving a constrained Algebraic Riccati Equation over a finite field?
Let $T=\left[\begin{array}{cc}A&B\\C&D\end{array}\right]$ be an $(m+n)\times(m+n)$ matrix over a finite field ${\mathbb F}_{q}$, where $A$ is $m\times m$ and $D$ is $n\times n$. Consider the ...
- 21
2 votes
1 answer
169 views
Geometric/linear algebra proof of multiplicativity of ideal norm in ring of integers
For a number field $K/\mathbb Q$ (as a $\mathbb Q$-vector-space $V$, $n$-dimensional), we have the ring of integers $\mathscr O_K$ (a lattice = copy of $\mathbb Z^n$ in $V$). Ideals $I \subseteq \...
- 1,235
0 votes
1 answer
209 views
Principal prime ideals in imaginary quadratic number field
Let $K$ be an imaginary quadratic number field. If the class number of $K$ is greater than 1 there exist non-principal ideals. Some of the ideals that are principal have prime norm, i.e. they are ...
- 273
1 vote
0 answers
164 views
Structure of torsion in cocompact arithmetic groups
Source of considered construction: Morris - Introduction to Arithmetic Groups ; see (6.7.1). Let $F$ be a totally real algebraic number field and fix one real embedding $e: F \to \Bbb R$, such that $...
- 3,822
3 votes
1 answer
241 views
Struggling with what should be an easy identity about quadratic exponential sums $\frac 1 q \sum_{k = 0}^{q-1} e_q(k^2a -km)$
I took the last few weeks to read material from other textbooks, but I decided to circle around to Appendix A and build off of my first question. Let $$S(a,m;q) = \frac 1 q \sum_{k = 0}^{q-1} e_q(k^2a ...
- 619
1 vote
0 answers
214 views
Reduce linear code minimum distance to lattice closest vector (CVP)
There are many NP-complete problems, e.g. SAT, CVP, SIS, graph colouring, Minesweeper etc. By definition there are polynomial time reductions from one to another of these, at least in their decision ...
- 273
1 vote
1 answer
261 views
Counting lattice points inside a log sphere
Consider a generalization of the Gauss circle problem and let $$ N(r):= \#\lbrace (x,y,z)\in \Bbb Z^3_{\gt 0}\vert \ln^2(x)+\ln^2(y)+\ln^2(z)\le\ln(r) \rbrace $$ I found that $$N(r)=\left(\frac{2\pi}{...
- 621
1 vote
1 answer
242 views
Bourgain and Rudnick circle argument for lattice points in spherical caps
Currently, I'm reading the appendix of Bourgain and Rudnick's paper that considers bounds for eigenfunctions of the Laplacian on the flat torus. The proof breaks down for $d > 3$, but in the ...
- 619
9 votes
1 answer
280 views
Is every finite subgroup of a simple Lie group contained in a lattice?
For any simple Lie group $\mathrm{G}$ with a finite subgroup $\mathrm{H}$, does there exist a lattice $\Gamma$ with $\mathrm{H}\subseteq\Gamma\subset\mathrm{G}$?
- 3,213
8 votes
1 answer
257 views
What is geometrically special about an orthogonal lattice (and its $GL(n,{\mathbb Z})$ copies) among all integer lattices?
Let's assume we have a lattice $L \subset {\mathbb R}^n$, given by basis vectors $v^1,v^2,\ldots,v^n$, so $L = \{ \sum_{i=1}^n k_i v^i | k_i \in \mathbb Z \}$. Let's collect all basis vectors into a ...
- 1,426
0 votes
0 answers
84 views
Rational embeddings of positive definite kernels over the natural numbers? (Unit vectors with rational coordinates)
I am searching for rational embeddings of positive definite kernels $k$ symmetric, taking rational values and $k(n,n)=1$ such as $k(a,b) = \min(a,b)/\max(a,b)$ or $k(a,b) = 2\gcd(a,b)/(a+b)$ or $k(a,...
- 3,425
2 votes
1 answer
133 views
Lattice reduction in 3-dimensions with real basis vectors
There are several algorithms for lattice reductions in $n$-dimensions, LLL, etc. Here the lattice in question is in ${\mathbb R}^n$ and the basis vectors $b_1, \ldots, b_n$ are usually assumed to be ...
- 1,426
1 vote
0 answers
99 views
Regularity property for graded posets
Let $L$ be a finite graded lattice with rank function $r$. According to the definition on page 39 in the book "Combinatorial Theory" by Aigner, L is said to have the regularity property $(...
- 28.1k
1 vote
0 answers
62 views
submodular functions, graph cuts
Can every submodular function be represented as a restriction of a graph cut? More precisely, is the following true? Let $f:2^V \to [0,\infty)$ be submodular, symmetric with $f(\emptyset)=0$. Then, ...
3 votes
1 answer
248 views
Proving the intersection of lattices is finitely generated over non-discrete valuation ring
I am trying to loosely follow Casselman's "The Bruhat-Tits Trees of SL(2)" instead using the field $F=\mathbb R_\rho$, a quotient of a subring of the hyperreals. It has a non-archimedean ...
- 131
1 vote
1 answer
102 views
Can the CVP -> OptCVP reduction be extended to lattices with real basis?
In Theorem 8 of Micciancio’s lecture notes, a reduction from the Closest Vector Problem (CVP) to its optimization version (OptCVP) is given under the assumption that the lattice basis $B \in \mathbb{Z}...
- 21
2 votes
0 answers
96 views
Do unimodular triangulations have the greatest number of simplices of each dimension among all lattice triangulations?
Let $\Delta_m^n$ be the $n$-dimensional simplex in $\mathbb{R}^n$ with vertices $(0,...,0)$, $(m,0,...,0)$, ... , $(0,...,0,m)$ and let $\tau$ be a lattice triangulation of $\Delta_m$. I am trying to ...
- 428
1 vote
0 answers
75 views
The lattice of t-motives is really a lattice - reference needed
Let $q$ be a power of a prime $p$, $\Bbb F_q[\theta]$ the analog of $\Bbb Z$ in finite characteristic, $\Bbb R_\infty:=\Bbb F_q((\theta^{-1}))$ the analog of $\Bbb R$ and {$\Bbb C_\infty:=$ the ...
0 votes
0 answers
114 views
LLL algorithm for $\mathbb{Z}[X]$-lattices
I understand the LLL algorithm for finding approximate shortest vector in $\mathbb{Z}$-lattices (where the norm function is either $\ell_\infty$ or $\ell_2$), as well as finding the shortest vector in ...
3 votes
0 answers
78 views
Map from the set of bases of lattices in finite characteristic to Grassmannian
Let $q$ be a power of a prime $p$, $\Bbb F_q[\theta]$ the analog of $\Bbb Z$ in characteristic $p$, and $\Bbb C_\infty$ the analog of $\Bbb C$ in characteristic $p$. A lattice of rank $r$ in $\Bbb C_\...
3 votes
0 answers
142 views
How fast can we solve SVP using an SVP$_{\gamma}$ subroutine?
An $n$ dimensional lattice is the set of integer linear combinations of $n$ linearly independent vectors in $\mathbb{R}^{d}$ ($d\le n$). The $n$ independent vectors are called the basis of the lattice,...
- 169
3 votes
0 answers
109 views
Cusps of rank-one locally symmetric spaces
I've found in the literature these facts: Any closed flat manifold is virtually (i.e. finitely covered by) a torus, and any finite-volume real hyperbolic manifold has virtually (i.e. is finitely ...
- 81
1 vote
1 answer
228 views
Comparison between first minimum of a lattice and a discrete subgroup in function field
This is the continuation of the previous question Lattices in the extension field of local fields in positive characteristic. Let $\mathbb{F}_q(T)$ denote the function field over $\mathbb{F}_q$, where ...
- 151
9 votes
0 answers
251 views
I am looking for a copy of the Ph.D. thesis of P. E. Smith, Cambridge 1975 with title "On certain finite simple groups."
I believe his thesis constructs a 248-dimensional representation of the Dempwolff group and is related to the construction of the rank 248, even self-dual Smith-Thompson lattice. I have tried the ...
- 5,730
7 votes
2 answers
584 views
Question about the "integer lattice reachability problem", and whether it can be solved with generating function
Here is the 2-dimensional integer lattice reachability problem: Suppose we are in a 2d integer plane, and are starting from $(0, 0)$. We will add $n$ vectors, and each vector is from a pre-defined ...
- 171
3 votes
0 answers
73 views
Lattices of Voronoi's first kind in differential geometry
An $n$-dimensional Euclidean lattice $L$ is called of $\textbf{Voronoi's first kind}$ if it satisfies the $\textbf{obtuse superbasis}$ condition: There exist $x_0, \dots, x_n \in L$ such that $1) x_1, ...
- 327
5 votes
1 answer
479 views
Is there an efficient method to solve this optimization problem on the surface of the sphere?
Let $A$ be a non-singular matrix in $\mathbb{R}^{n \times n}$. Let $S^{n-1}$ denote the surface of the unit $n$-sphere in $\mathbb{R}^{n}$. Suppose we know that there exists an $x \in S^{n-1}$ such ...
- 51
3 votes
2 answers
177 views
Example of a lattice and its dual where the product of the length of their smallest vector is close to the dimension of the lattice?
Can you show an example of a lattice and its dual where the product of the length of their smallest vectors is close to the dimension of the lattice? Let $L$ be an $n$-dimensional lattice, and let $L^{...
- 169
1 vote
0 answers
78 views
Lower bounds on the degree of polynomials vanishing on lattice points in a ball
Is there a known lower bound on the degree $D$ of a Real polynomial $P$ of $d$ variables which is non-zero yet vanishes on all the lattice points in the closed ball of radius $r$ about the origin? How ...
- 111
3 votes
1 answer
340 views
Lattices in the extension field of local fields in positive characteristic
Let $\mathbb{F}_q(T)$ denote the function field over $\mathbb{F}_q$, where $q$ is a prime power. The norm in this field is defined by $ \left| \frac{f}{g} \right| = q^{\deg(f) - \deg(g)}, $ where $f, ...
- 151
1 vote
1 answer
249 views
Upper bound on number of lattice points in ball of $\mathbb Z^d$
There seems to be some folklore result that the number of lattice points in a $d$-dimensional ball of radius $R$ is $$V_d R^d + \mathcal O(R^{d-2})$$ and $V_d$ is the volume of the unit ball if $d$ ...
1 vote
1 answer
189 views
Fundamental set of Euclidean lattices in higher dimensions
We consider the space of $n$-dimensional Euclidean lattices. Define the $i$-th successive minimum of a lattice $\Lambda$ as $ \lambda_i(L) := \min \left\{ r \in \mathbb{R}_{>0} \mid \dim_{\mathbb{R}...
- 327
1 vote
0 answers
90 views
Covering the positive integer point lattice in $\mathbb{R}^2$ with sublattices
Let $P$ be the positive integer point lattice on the plane, that is, all points $(x,y)\in\mathbb{R}^2$ such that $x,y\in\mathbb{N}, x,y>0$. Take $a_i,b_i,c_i\in P$ such that $b_i=(b_{i,x},b_{i,y}) \...
- 1,068
2 votes
0 answers
153 views
Is it possible to transform a univariate congruence equation into a multivariable system of congruence equations for solving?
Considering a quadratic congruence equation $$ x^2 = d \pmod{p} \label{1}\tag{1} $$ I have a strange idea: what if we construct a system of congruence equations in multiple variables based on the ...
0 votes
0 answers
105 views
Determining if the two different dimension integer matrices are congruent
Given a matrix $A\in M_{6\times 6}(\mathbb{Z})$ that is symmetric and has determinant zero. I want to deterministically figure out if there exists a matrix $T\in M_{6\times 5}(\mathbb{Z})$ such that $...
- 514
3 votes
0 answers
152 views
What is the status of Mahler’s open problems (from 1946) about the irreducibility of star bodies?
A duplicate of this: I am reading Mahler’s Lattice points in $n$-dimensional star bodies II (1946), in which he poses the following (then) open problems about the irreducibility of star bodies: Do ...
- 327
0 votes
0 answers
72 views
Extended Euclidean in $NC^1$ to $2D$ shortest vector problem in $NC$
$LLL$ algorithm is vectorized version of Extended Euclidean algorithm for $\mathsf{GCD}$. Even the $m=2$ dimensions case known to Lagrange and Gauss does not have an $NC$ algorithm for shortest vector....
- 1
6 votes
1 answer
340 views
Conjecture closed form of summation over an integer lattice
Conjecture: $$\forall \Lambda,\ \exists P(x)\in \mathbb{Z}[x],\ S(\Lambda):=\sum_{k\in\Lambda}\prod_{j=1}^{n}\frac{1}{1+k_{j}^2}=\frac{\pi^{n}}{\sinh^{n}(\pi)\operatorname{d}(\Lambda)}P\left(\cosh\...
user500489
10 votes
0 answers
497 views
Does the Leech lattice predict the genus $70$ of the buckyball surface?
In "Symplectization, Complexification and Mathematical Trinities" by V. Arnold, he came up with various trinities, one of which being the three Platonic symmetry groups $T,O,I$ of order $12, ...
- 13k
2 votes
0 answers
133 views
Question about lattice with dense projection
Let $H\subset \operatorname{GL}(n,\mathbb{C})$ be a connected, semisimple algebraic group defined over $\mathbb{Q}$. Fix a number field $K$ with $[K:\mathbb{Q}]=3$ that is not totally real. Denote its ...
- 305
3 votes
0 answers
110 views
Congruences regarding $4n$-dimensional lattices
A sequence of integers $(a_n)_{n\geq 1}$ satisfies Gauss congruence if $$\sum_{d\mid n}\mu(d)a_{n/d}\equiv 0\pmod{n}$$ for every $n\geq 1$. Such sequences are also called Dold sequences, Newton ...
- 211
5 votes
1 answer
287 views
I believe that all facets of a Voronoi-cell of a lattice are centerally symmetric. Is my argument correct? Is this true?
So let $L$ be a full dimensional lattice in $\mathbb{R}^{n}$. Then the Voronoi-cell of the lattice are precisely the points in $\mathbb{R}^{n}$ that are at least as close to the origin, as to any ...
- 169
8 votes
0 answers
291 views
Discriminants and lattices in Algebraic geometry vs Geometry of numbers
(Post-writing, this question ended up being way more rambly than I intended. Sorry for that. There's a lot of closely related ideas I'm trying to unravel and it's hard to extract an individual ...
- 513
5 votes
1 answer
283 views
If a lattice can be embedded into $\mathbb Q^n,\langle-1\rangle^n$, then can it be embedded into $\mathbb Z^n,\langle -1 \rangle^n$?
Given a graph with negative integers on each vertex $\Gamma$ there is a corresponding intersection lattice denoted $Q_\Gamma$, a free $\mathbb Z$ module generated by the vertices, endowed with a ...
- 63