Skip to main content

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])

Filter by
Sorted by
Tagged with
8 votes
1 answer
2k views

Polynomial-time quantum algorithms for lattice problems (GapSVP, SIVP, LWE)

The author of a recent preprint claims to have found polynomial-time quantum algorithms for solving the following lattice problems: the Decisional Shortest Vector Problem (GapSVP), the Shortest ...
en-drix's user avatar
  • 93
6 votes
1 answer
343 views

Why do symmetries of K3 surfaces lie in the Mathieu group $M_{24}$?

I'm having trouble following some steps of this argument from the appendix of Eguchi, Ooguri and Tachikawa's paper Notes on the K3 surface and the Mathieu group M24: Now let us recall that the ...
John Baez's user avatar
  • 21.6k
3 votes
0 answers
51 views

Arithmetic lattices are finitely presented

In the book "Kazhdan's Property (T)" by Bekka-de la Harpe-Valette, the following is stated on p.6 of the introduction: "Of course, it is classical that arithmetic lattices are finitely ...
studiosus's user avatar
  • 295
3 votes
1 answer
88 views

Seeking Article "Generating random lattices according to the invariant distribution" by M. Ajtai

I am searching for a specific article titled "Generating random lattices according to the invariant distribution" authored by Ajtai. Despite being widely cited in various papers, I have been ...
LATTICE's user avatar
  • 31
0 votes
0 answers
28 views

Integral representation of completely alternating homogeneous functionals on semi-lattice of continuous functions

For a long time I've been interested in G. Choquet seminal work "Theory of capacities" (Annales de l’institut Fourier, tome 5 (1954), p. 131-295). More precisely part 53 about integral ...
Vladimir B.'s user avatar
3 votes
1 answer
226 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?
Turbo's user avatar
  • 13.7k
6 votes
1 answer
188 views

What is the smallest $\mathbb{Z}[x]$ multiple of $(x-1)^n$ in the coefficient vector $\ell_1$ sense?

Define a norm $\lVert p \rVert_1$ for $p\in \mathbb{Z}[x]$ as the sum of absolute values of the coefficients of $p$, as expressed in the ordinary monomial basis. What is the smallest norm of a ...
vujazzman's user avatar
  • 163
1 vote
2 answers
265 views

Does $\mathbb Z^n$ contain $A_n$?

Are there any positive integer $n > 3$ such that the root lattice $A_n$ is contained in $\mathbb Z^n$?
WKC's user avatar
  • 646
4 votes
0 answers
135 views

Vanishing of $\ell^2$-Betti numbers of $\mathrm{GL}(n,\mathbb{Z})$ for $n\geq 3$

$\DeclareMathOperator\GL{GL}$In a paper I read the following claim: By the work of Borel the $\ell^2$-Betti numbers of the cocompact lattices of $\GL(n,\mathbb{R})$ are known to all vanish when $n ≥ 3$...
Marcos's user avatar
  • 577
2 votes
1 answer
118 views

Kripke frame, lattice and some intermediate logics

For a given finite and rooted intuitionistic Kripke frame $\mathcal{F}$, let $\log(\mathcal{F})=\{\phi : \mathcal{F}\vDash \phi\}$ and assume $S=\{\log(\mathcal{F}): \mathcal{F} \text{ is finite and ...
4869's user avatar
  • 47
5 votes
1 answer
331 views

Lattice generated by parabolics

Let $G$ be a semisimple Lie group of split-rank one and let $\Gamma$ be a non-cocompact lattice which is torsion-free. For the group $G=\mathrm{SL}_2(\mathbb{R})$ it then follows that $\Gamma$ is ...
Nandor's user avatar
  • 119
0 votes
0 answers
59 views

What is the lattice point distribution over binary quadratic forms?

Let $f(x,y)=x^2+ny^2$ be the binary quadratic form of interest and consider the lattice points $S=\{ (x,y,f(x,y)) \in \mathbb{N}^3 \}$. For simplicity, we keep things only on quadrant I of the ...
ReverseFlowControl's user avatar
0 votes
0 answers
78 views

Lattice not contained in any connected subgroup is not contained in any positive dimensional subgroup

Let $ G $ be a simple Lie group and let $ \Gamma $ be a lattice in $ G $. If $ \Gamma $ is not contained in any connected subgroup of $ G $ does that imply that $ \Gamma $ is not contained in any ...
Ian Gershon Teixeira's user avatar
0 votes
0 answers
47 views

Kirszbraun-like extension of periodic functions

Let $\Lambda \subset \Lambda' \subset \mathbb{R}^n$ be lattices. Let $f : \Lambda' \rightarrow \mathcal{H}$ be a $a$-Lipschitz function, where $\mathcal{H}$ is a finite-dimensional Hilbert Space. ...
jetSett's user avatar
0 votes
0 answers
118 views

Roots in indefinite lattice of K3 surfaces

Anyone who likes $K3$ surfaces cares about lattices of the form $$ (2d)\cdot y^2 - 2x \cdot z$$ (namely the mukai pairing on $H^*_{alg}(K3)$ of picard $1$ with polarization $d$). Inside we have ...
user135743's user avatar
6 votes
1 answer
232 views

Do lattices of small co-volume always exist in rational, connected, simply connected, nilpotent Lie groups?

Given a connected, simply connected, rational, nilpotent Lie group $G$, is there a lattice of arbitrarily small co-volume in $G$? If $G$ is Carnot, the answer is "yes" by applying a ...
Kyle's user avatar
  • 243
2 votes
0 answers
104 views

Efficient decoding of the E8/Leech lattice

Background: Our goal is to quantize a sequence of floating point numbers generated i.i.d. from a standard Gaussian source and minimize the MSE reconstruction error. We can use two bits for each sample....
nalzok's user avatar
  • 121
1 vote
0 answers
97 views

Number of points in a ball in positive characteristic

Let $w_1,\cdots,w_n$ be of elements of $\Omega$, that is the completion of $\overline{\mathbb F_q\left(\left(\frac1T\right)\right)}$ for the topology induced by the $-\deg$ valuation. Assume that $w_1,...
joaopa's user avatar
  • 3,759
2 votes
1 answer
330 views

Lattices and noncommutative algebras in noncommutative geometry

This a question that I've asked in mathematics stack exchange without having received any response : I am interested in the relation between lattices and noncommutative algebras in the context of ...
Esmond's user avatar
  • 136
0 votes
1 answer
130 views

How common is it that the number of the shortest vectors in a lattice is exactly two?

The lattice $\Gamma$ in $\mathbf{R}^{m}$ with the lattice basis $\{ke_{k}\}_{k=1}^{m}$ has exactly two shortest vectors: $\pm e_{1}$. My question is the following: Among all the lattices with fixed ...
Castle's user avatar
  • 21
4 votes
0 answers
200 views

Automorphism group of a Lorentzian lattice

Consider the even integral lattices $L_n:=Z\times Z\times Z^{n-2}$ (where $Z$ is the set of integers) with elements $x=(x_+,x_-,x_d)$ and inner product $$(x,y):=x_+y_-+x_-y_++2x_d\cdot y_d.$$ Its ...
Arnold Neumaier's user avatar
3 votes
1 answer
188 views

Exponential growth of shortest vector norm for successive lattices corresponding to powers of a matrix

Let $A\in M_{2\times 2}(\mathbb{Z}) $ be a two by two integer matrix such that $0,\pm 1$ are not eigenvalues of $A$ and $\left|\det(A)\right|>1$. I am interested in the growth of the norm shortest ...
an_ordinary_mathematician's user avatar
5 votes
1 answer
125 views

Expected value of the length of the shortest non-zero vector in a lattice?

$\DeclareMathOperator\SL{SL}$What is the expected value of the length of the shortest non-zero vector in a (unimodular) lattice? I.e., let $G=\SL_n(\mathbb{R})$ with Haar measure $\mu$, $\Gamma=\SL_n(...
yoyo's user avatar
  • 507
2 votes
0 answers
157 views

Will Coppersmith's method work for this bivariate modular polynomial shape?

I have a bivariate modular polynomial of shape $$f(x,y)=x^2y-g(x)\equiv 0\bmod q$$ where $q=(2p-1)(2p+1)$ is a product of two primes $2p-1$ and $2p+1$, $g(x)\in\mathbb Z[x]$ is of degree four and $f(...
Turbo's user avatar
  • 13.7k
9 votes
1 answer
704 views

Where has this structure been observed?

$\newcommand{\M}{\mathcal{M}}$Let $M$ be a monoid. Consider the following structure: $R_X,R_Y:\mathbb{Z}^2 \to M$ satisfying the following "compatiblity-relation": $$R_X (x, y) \cdot R_Y (x +...
Asaf Shachar's user avatar
  • 6,621
4 votes
0 answers
110 views

Advice on results for balls on regular $N$-dimensional grids

I have obtained some results regarding balls on regular $N$-dimensional grids. I would like expert opinion on wether the results are significant or interesting enough for (trying to) publish them in a ...
Luis Mendo's user avatar
1 vote
0 answers
56 views

Condition on the minimality of Minkowski units

I am interested in to undrestand when the Minkowski units in real biquadratic number fields are minimal in the log unit lattices. I have read some pieces of literature online which are investigating ...
user511994's user avatar
4 votes
0 answers
126 views

Characterizing the D4 lattice as a sphere packing

Suppose I pack spheres in $\mathbb{R}^4$ in such a way that each touches 24 others. (All spheres in my question are assumed to have equal radius and be non-overlapping.) Does this packing ...
John Baez's user avatar
  • 21.6k
3 votes
1 answer
172 views

About finitely generated lattices in Lie groups

Let $G$ be a connected Lie group. Let $\Gamma$ a lattice in $G$ not necessarily uniform (cocompact). Is it true that $\Gamma$ is finitely generated?
M. Han's user avatar
  • 65
6 votes
0 answers
229 views

What can lattices tell us about lattices?

A general group-theoretic lattice is usually defined as something like A discrete subgroup $\Gamma$ of a locally compact group $G$ is a lattice if the quotient $G/\Gamma$ carries a $G$-invariant ...
Mark Schultz-Wu's user avatar
0 votes
0 answers
135 views

Genus of quadratic form

I am trying to understand the genus of a lattice from Conway and Sloane textbook. They said two quadratic forms $Q_1$ and $Q_2$ lie in the same genus if they are equivalent over $\mathbb{R}$ and over ...
vent's user avatar
  • 1
3 votes
0 answers
123 views

group generated by unipotents in arithmetic subgroup is finitely generated

Let $G$ be a semisimple algebraic $\mathbb{Q}$-group and $\Gamma$ an arithmetic subgroup of $G$. In particular $\Gamma$ is finitely generated. Denote by $\Gamma^{u}$ the set of unipotent elements in $\...
Geoffrey Janssens's user avatar
2 votes
1 answer
182 views

The sum of $q^{-2}$ over nonzero Gaussian integers

I'm reading about the Weierstrass zeta function. In this context, $\phi(z)=\zeta(z)-\pi\bar{z}$ is periodic over the lattice $$\mathcal{L}=\{a+bi\mid a,b\in\mathbb{Z}\}.$$ If we take $w\in\mathcal{L}\...
isz's user avatar
  • 31
5 votes
0 answers
142 views

Is fundamental group of a finite volume, negatively curved, cusped manifold a non-uniform lattice?

$\DeclareMathOperator\Mob{Mob}$Some background: (1) A Riemannian manifold $M$ is pinched negatively curved if there is a constant $\tau<\kappa<0$ such that all the sectional curvatures are ...
Yanlong Hao's user avatar
6 votes
1 answer
197 views

Preserve validity between the two Kripke frames

The background of our discussion is intuitionistic logic, i.e. the following definitions are intuitionistic Kripke frame. For $n \geq 1$, let $\mathcal{C}_n$ denote the frame which is shown in Fig.1. ...
mahu's user avatar
  • 63
7 votes
1 answer
322 views

Extremal problem for 2-dimensional lattices

Given a lattice $L$ in a Banach space $(B,\|\;\|)$, one denotes by $\lambda_1(L)$ the least norm of a nonzero element in $L$, and by $\lambda_k$ the least $\lambda$ such that there is a linearly ...
Mikhail Katz's user avatar
  • 15.5k
2 votes
1 answer
148 views

Cocompact lattices in $\mathrm{Sp}(n, 1)$

This is a continuation from my previous question. I am reading the following paper of Cowling-Haagerup, and I was wondering whether there are uniform lattices in $\mathrm{Sp}(n, 1)$. Is there some way ...
kobeahibe's user avatar
  • 111
4 votes
0 answers
106 views

Questions related to a paper of Cowling-Haagerup and uniform lattices of $\mathrm{Sp}(1,n)$

I am reading the following paper of Cowling and Haagerup for my master’s thesis. I am new to this area so I am not very conversant. So I do apologize if the questions are silly. Question 1. In the ...
kobeahibe's user avatar
  • 111
1 vote
0 answers
30 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$ ...
Turbo's user avatar
  • 13.7k
8 votes
1 answer
350 views

Outer automorphisms of finitely generated linear groups

Is there an example of a finitely generated subgroup $\Gamma \subset \mathrm{GL}_n(\mathbb{C})$ such that the group of outer automorphisms $\mathrm{Out}(\Gamma)$ contains finite subgroups of unbounded ...
AlekseiG's user avatar
  • 163
2 votes
1 answer
523 views

Kissing number lower bound vs. upper bound - precise meanings?

According to en.wikipedia.org, https://en.wikipedia.org/wiki/Kissing_number#Some_known_bounds It says the kissing numbers $K$ have lower bound $K_L$ and upper bound $K_S$: $$ K_L < K < K_U. $$ I ...
zeta's user avatar
  • 337
0 votes
1 answer
176 views

Leech lattice shortest vector vs other 23 cases and E8 cases

In this paper by Viazovska, she said that: "The E8-lattice sphere packing 𝒫E8 is the union of open Euclidean balls with centers at the lattice points and radius $1/\sqrt{2}$." So I think ...
zeta's user avatar
  • 337
0 votes
0 answers
22 views

Reference on high dimensional polytopes with E8 symmetry

I'm starting to work with high dimensional polytopes. I am interested in uniform polytopes of 16-dimension and of 8-dimension (especially Elte and Gosset polytopes that have E8 symmetry). ...
Dac0's user avatar
  • 295
7 votes
2 answers
335 views

Relation between different $E_8$ matrices

There are several rank-8 square matrices known to be related to $E_8$: Cartan $E_8$ matrix https://en.wikipedia.org/wiki/E8_(mathematics)#Cartan_matrix $$M_1=\left [\begin{array}{rr} 2 & -1 &...
Марина Marina S's user avatar
5 votes
2 answers
624 views

A note on orders in quaternion algebras

Definition. An algebra $B$ over a field $F$ is a quaternion algebra if there exists $i,j\in B$ such that $1,i,j,ij$ is a basis for $B$ as a vector space over $F$, where $i^2=a,j^2=b;a,b\in F^\times$. ...
Hussein Eid's user avatar
2 votes
0 answers
87 views

decidability special case of column generation problem

I have the following problem: Input: sub-spaces $V_1, \dots, V_d$ of $\mathbb{Z}^{d}$ Question: are there $v_i \in V_i$ such that the matrix $(v_1, \dots, v_d)$ has determinant $\pm 1$ (equivalently, ...
Armin Weiß's user avatar
1 vote
1 answer
97 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 ...
elsnar's user avatar
  • 127
3 votes
1 answer
140 views

Cohomology of cocompact lattices in hyperbolic spaces

I have a (maybe too naive) hope that cocompact torsion-free arithmetic lattices in hyperbolic spaces $X \neq \mathbb{H}_\mathbb{R}^2$ are uniquely determined by their cohomology with coefficients in $\...
TSU's user avatar
  • 131
2 votes
0 answers
204 views

Modular inverse computation - avoiding Euclidean algorithm

Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime. If we already know ...
Turbo's user avatar
  • 13.7k
4 votes
1 answer
274 views

The function $f(g):=\sum_{\gamma \in \text{SL}(2,\mathbb Z)}\frac{1}{\|g\gamma \|^4}$ for $g\in \text{SL}(2,\mathbb R)$

For $g\in \text{SL}(2,\mathbb R)$ and the Hilbert-Schmidt norm $\|\cdot\|$ (square root of sum of squares), define $$f(g):=\sum_{\gamma \in \text{SL}(2,\mathbb Z)}\frac{1}{\|g\gamma \|^4}.$$ It is ...
taylor's user avatar
  • 435

1
2 3 4 5
14