# Questions tagged [lattices]

Lattices as they are used in number theory. (Not to be confused with lattice theory or lattices as used in physics!)

**2**

votes

**1**answer

68 views

### Lowering $i$th shortest vector of a lattice

LLL guarantees that we can find a basis $v_1,\dots,v_n$ of a lattice in $\mathbb R^n$ with
$$\|v_i\|\leq \gamma_{i,n} \det(\Lambda)^{1/(n-i+1)}$$ where $\gamma_i$ is a function only of $i$ and $n$.
...

**2**

votes

**0**answers

39 views

### Enumerating lattice points in a product of balls, in limit with dimension

Fix $(L_n)_n$ to be a sequence of lattices, each $L_n\subset \mathbb{R}^n$, where both the effective-inradius and effective-outradius go to 1 (i.e. the Voronoi region of the lattices approach a ball ...

**0**

votes

**0**answers

72 views

### Probabilistic Howgrave-Graham Bounds with Coppersmith Technique?

Howgrave-Graham condition says roots of $$f(x_1,\dots,x_n)\equiv0\bmod R$$ at an $R\in\mathbb N$ are roots of $$f(x_1,\dots,x_n)=0$$ over $\mathbb Z$ if $$\|f(x_1X_1,\dots,x_nX_n)\|<\frac{R}{\sqrt{\...

**5**

votes

**0**answers

145 views

### Divisor bound for $r_2$ off the origin

If $r_2(n)$ denotes the number of integer solutions to $a^2+b^2=n$, we have the "divisor bound" $r_2(n) = O(n^{\epsilon})$ for any $\epsilon>0$. Another way to state this is that the number of ...

**2**

votes

**1**answer

108 views

### Which lattices are rotatable into their scaled copy?

Let $L=\{\sum_i n_iv_i\mid n_i\in\mathbb Z\}$ be some lattice generated by $d$ independent vectors $(v_i)_1^d$ from $\mathbb R^d$. Call $L$ rotatable if for some $M$, a scalar multiple of some ...

**1**

vote

**0**answers

35 views

### Shortest Lattice Vector with restricted $x$

Let $\Lambda$ be a lattice with basis, $B$ consisting of vectors $b_i$, so that the elements of $\Lambda$ are of form, $y\in \Lambda \iff y=Bx=\sum_i b_ix_i$ for some $x_i\in\mathbb{Z}$.
My questions ...

**1**

vote

**1**answer

79 views

### Basis of cone lattice

I only want to know whether a construction that I use appears in literature and maybe has a name already.
Let $V$ be a $\mathbb Q$ vector space of dimension $d\in\mathbb N$.
A subset $C\subset V$ is ...

**2**

votes

**0**answers

195 views

### Algebraically independent vectors in tensor product

$\mathcal L$ and $\mathcal L'$ be full rank lattices in $\mathbb R^n$ with shortest vectors $v_1,\dots,v_n$ and $v_1',\dots,v_n'$ respectively where $$\|v_1\|_2\leq\dots\leq\|v_n\|_2$$
$$\|v_1'\|_2\...

**2**

votes

**0**answers

86 views

### Coppersmith's method to quadrivariate degree $2$ polynomials that behave as bivariate?

We have a polynomial $f(x_1,x_2,x_3,x_4)\in\mathbb Z[x_1,x_2,x_3,x_4]$ where the only monomials are either from set $$\{x_1,x_1x_2,x_2,x_3,x_3x_4,x_4\}$$ and we seek solutions $(x_1,x_2,x_3,x_4)\in\...

**1**

vote

**0**answers

50 views

### Method of Coppersmith optimal for multivariate?

It is shown that Coppersmith method yields optimal integer root extraction for univariate polynomials in https://arxiv.org/abs/1605.08065 and a follow up work attempts this for bivariate polynomials ...

**1**

vote

**2**answers

97 views

### Given an integer lattice, how to count the number of points whose norm is smaller than some bound $M$?

Let $\mathbf{b}_1, \mathbf{b}_2, ..., \mathbf{b}_n$ be linearly independent $m$-dimensional vectors whose entries belong to $[0, M] \cap \mathbb{Z}$, for some $M \in \mathbb{N}^*$. Of course, $n \le ...

**3**

votes

**0**answers

81 views

### Counting lattice points in adelic spaces

Let $\mathbb{A}$ denote the ring of adeles of $\mathbb{Q}$, let $\mu$ be the Haar measure of $\mathbb{A}$, and let $\|\cdot\|_{\infty}$ denote the sup-norm of the components in the Archimedean of $\...

**1**

vote

**0**answers

30 views

### Defining a notion of “volume of its lattice” for non-rational subspaces

Let $V\subseteq \Bbb R^n$ be a vector subspace. If $V$ is rational, i.e. has a basis consisting of elements in $\Bbb Z^n$, then there’s a well-defined notion of the “volume of the lattice of V”:
$$\...

**5**

votes

**0**answers

150 views

### What kind of locally symmetric space is a rational sphere

Using Dehn Surgery, we can construct compact hyperbolic $3$-manifolds with vanishing Betti numbers $b_1=b_2=0$, i.e., a rational homology $3$-sphere.
My question is the following.
Is there other ...

**1**

vote

**0**answers

66 views

### Shortest vectors in tensor product and maximal lattices in tensor product

$\mathcal L$ and $\mathcal L'$ be full rank lattices in $\mathbb R^n$ with shortest vectors $v_1,\dots,v_n$ and $v_1',\dots,v_n'$ respectively where $$\|v_1\|_2\leq\dots\leq\|v_n\|_2$$
$$\|v_1'\|_2\...

**2**

votes

**0**answers

99 views

### Can computers take uniform samples from a polytope?

For each $r \in \mathbb N $ write $\mathbb Z/ 10^r = \{a/10^r: a \in \mathbb Z\}$ and $P(r)$ for the lattice $(\mathbb Z/10^r)^N \subset \mathbb R^N$.
Suppose the plane $P \subset \mathbb R^N$ is ...

**2**

votes

**1**answer

183 views

### Is there a relation between the number of lattice points lie within these circles

Suppose we have a circle of radius $r$ centered at the origin $(0,0)$. The number of integer lattice points within the circle, $N$, can be bounded using Gauss circle problem .
Suppose that another ...

**3**

votes

**2**answers

316 views

### Can we count the number of integer lattice points in this case?

Gauss Circle problem gives the number of lattice points lie within a circle of radius $r$. This question points to a reference that estimates the number of lattice points in a $d−$dimensional ball.
$...

**0**

votes

**0**answers

84 views

### How well does convolution model $\mathbb Z$ multiplication?

In $\mathbb K[x]$ or $\mathbb K$ where $\mathbb K$ is a ring we can think of multiplication of polynomials as convolution. Over $\mathbb Z$ this line of thought has led to fast integer multiplication ...

**2**

votes

**0**answers

181 views

### Combinatorial and computational problem related to Weyl groups and the coroot lattice

Let $W$ be a Weyl group with root system $R$ and with set of positive roots $R^+$. Let $\tilde{R}^+$ be the set of $B$-cosmall roots, i.e. positive roots $\alpha$ which satisfy $\ell(s_\alpha)=2\...

**5**

votes

**1**answer

149 views

### Why is the number of Perfect Matchings in a triangular grid equivalent to the number of Royal Paths?

The sequence A006318 at OEIS stands for the Schröder numbers.
They describes the number of lattice paths from the southwest corner $(0,0)$ of an $n\times n$ grid to the northeast corner $(n,n)$, ...

**0**

votes

**0**answers

119 views

### Integral subspace generated by a positive semidefinite matrix

Take $\Sigma $ a real positive semidefinite matrix. Define $P$ to be the smallest projection with the property that for any $\mathbf{a}\in \mathbb{Z}^n$ with $\mathbf{a}^\dagger (I-P)^\dagger \Sigma (...

**3**

votes

**1**answer

129 views

### Lattice projections

I imagine the following result is folklore
Theorem. Those $k$-dimensional subspaces $\zeta \subset \mathbb{R}^n$ $(1 \leq k \leq n-1)$ for which the orthogonal projection of the lattice $\mathbb{Z}^n$...

**5**

votes

**0**answers

181 views

### Isomorphism classes of lattices

Suppose we have a $4 \times 6$ matrix $A$ of rank $4$ whose entries are rational numbers. Define
$$
V = \{x \in \mathbb R^6 \mid A \cdot x = 0\}
$$
and
$$
\Lambda = \{x \in \mathbb Z^6 \mid A \cdot ...

**6**

votes

**1**answer

186 views

### Problem with the vertices of a convex quadrilateral on integer lattice

I made the following observation and I am wondering if it is always true.
Let $x_1$, $x_2$, $x_3$ and $x_4$ be four positive integer points in the plane ($x_i\in\mathbb{Z^2_{\geq 0}}$) forming a ...

**2**

votes

**1**answer

75 views

### On the laplacian of connected, undirected, multigraphs without loops

Let $G$ be a connected, undirected multigraph, without loops.
Let $L_G = D_G - A_G$,
where $D_G= diag (val (v_1), \ldots , val (v_n) )$ where $n$ is the no. of vertices of $G$ and $val (v_i)$ ...

**0**

votes

**0**answers

41 views

### n-D Gauss circle problem over a rectangle

I would like to approximate the amount of points in $\left(2^{-a\cdot n}\mathbb{Z}^n\right)\cap B^n(0,1)\cap C^n$ where $a>0,\ B^n(0,1)$ is the unit nball and $C^n$ is some rectangular domain ...

**13**

votes

**1**answer

257 views

### Counting primitive lattice points

In Lemma 2 of [1], Heath-Brown proves the following (I state a simplified version of a more general result):
Let $\Lambda \subset \mathbb{Z}^2$ be a lattice of determinant $d(\Lambda)$. Then
$$\# ...

**4**

votes

**1**answer

660 views

### Do $G$-invariant non-degenerate quadratic forms come from $G$-invariant even lattices?

The following is a somewhat well-known fact: Given an even lattice $L$ with the pairing $\langle,\rangle: L\times L\to \mathbb{Z}$, we extend the pairing to $L\otimes \mathbb{Q}$ by tensoring with $\...

**0**

votes

**0**answers

56 views

### Can we solve this using LLL formulation?

Given $N=PQ$ where $P$ and $Q$ are primes and given $T=P+Q$ we can use quadratic equation to solve for factors $P$ and $Q$.
On other hand Coppersmith's class of algorithms use partial information ...

**0**

votes

**0**answers

46 views

### On fixed dimension integer programming complexity when LLL is perfect

Fixed dimension integer programming (both Lenstra's and Barvinok's) uses LLL which guarantees short vectors but not the shortest possible.
Suppose for a given integer programming problem find $x\in\...

**7**

votes

**1**answer

128 views

### Are there Type III codes with small but nonzero “index”?

Recall that a Type III code of rank $r$ is a linear subspace $C \subset \mathbb F_3^r$ which is self-dual for the standard inner product. (These occur only when $r$ is divisible by $4$.) Elements of $...

**10**

votes

**1**answer

171 views

### Is the “Ramond sector” invariant of a 3-framed lattice always divisible by 24?

For the purposes of this question, a rank-$r$ (integral) lattice is a full-rank discrete subgroup $L \subset \mathbb R^r$ such that $\langle \ell, \ell' \rangle \in \mathbb Z$ for all $\ell \in L$. It ...

**0**

votes

**0**answers

42 views

### Formalizing a projective additive construction of polytopes?

Given a polytope represented by $$Ax\leq b$$ where $A\in\Bbb Z^{m\times n}$, $x\in\Bbb Z^n$ and $b\in\Bbb Z^m$ with $N\geq 0$ number of integer points can we construct a polytope with $N+1$ integer ...

**12**

votes

**3**answers

569 views

### Is it possible to completely embed complete Heyting Algebras into upsets of a poset?

Let $H$ be a Heyting algebra. It is a well-known result that there is a partially ordered set (Kripke frame) X such that there is an embedding of Heyting algebras $f: H \to \mathsf{Up}(X)$, where $\...

**7**

votes

**1**answer

204 views

### Shortest vectors in a root lattice

Let $R$ be a simply-laced root system in a Euclidean vector space $E$, with inner product normalized so that every root has length $\sqrt{2}$. Let $L \subseteq E$ be the lattice spanned by $R$. Is ...

**3**

votes

**0**answers

49 views

### Lattice basis reduction over rings of number fields

Can one use lattice basis reduction algorithms, such as LLL over (low-rank) module lattices over rings of number fields of degree greater than 1? Is there any work on lattice reductions over Euclidean ...

**5**

votes

**0**answers

97 views

### Averaging number of lattice points in a box over a family of lattices

Consider the diophantine equation
$$ x_1y_1^3 + \dots + x_s y_s^3 = 0. $$
For fixed $\mathbf{y}$ with coprime coordinates this is a $s-1$ dimensional lattice $\Lambda(\mathbf{y})$. Let $N(X)$ denote ...

**2**

votes

**1**answer

319 views

### Maier Phenomena for Gauss Circle Problem

For an arithmetic function $\alpha(n)$, let $S_{\alpha}(x) = \sum_{n \le x} \alpha(n)$. When $\alpha$ is the indicator function of primes, Maier has shown that $$\limsup \frac{S_{\alpha}(x+\Phi(x))-S_{...

**9**

votes

**0**answers

182 views

### How to count integer lattice points close to a subspace of $\mathbb R^n$?

Consider $m$ linearly independent vectors in $n$-dimensional Euclidean space, $v_1,...,v_m \in \mathbb R^n$ where $1\leq m<n$, and let $U := {\rm span}(v_1,...,v_m)$ denote the $m$-dimensional ...

**1**

vote

**0**answers

184 views

### Sphere packings with antipodal (unequal) spheres

Let $\|\cdot\|_2$ denote the Euclidean norm, let $\langle \cdot, \cdot\rangle$ denote the standard dot product, and let $\mathcal{S}^{d-1} = \{\mathbf{x} \in \mathbb{R}^d: \|\mathbf{x}\|_2 = 1\}$ ...

**0**

votes

**0**answers

63 views

### Siegel's Mean Value Theorem by Macbeath and Rogers

It is claimed in an answer in mathoverflow to a question about Siegel's Mean value theorem (link- Siegel's Mean Value Theorem by Rogers and Macbeath) that there is mistake for the case $n=2$. I ...

**0**

votes

**0**answers

22 views

### A problem about Siegel Mean Value theorem by Rogers and Macbeath

In the paper Siegel's mean value theorem in geometry of numbers (link- https://mathscinet.ams.org/mathscinet-getitem?mr=0103183) Rogers and Macbeath claim in Theorem 1, page 147 that certain sets have ...

**7**

votes

**0**answers

164 views

### Subgroups of $\mathbb{Z}^{n}$ with rotational symmetries

Schmidt (https://projecteuclid.org/euclid.dmj/1077377618) showed that the number of $m$-dimensional subgroups of $\mathbb{Z}^{n}$ of covolume $\leq X$
is
$$c_{1}\left(m,n\right)X^{n}+O\left(X^{n-\...

**1**

vote

**2**answers

545 views

### Examples of groups for which Margulis superrigidity theorem applies

I am not an expert at all in the subject of Lie groups, lattices, arithmetic groups and rigidity. But, lately I am interested in Margulis superrigidity theorem, which in most versions can be stated as ...

**2**

votes

**1**answer

143 views

### Counting lattice points can some give all?

Given convex polytope $\mathcal P\subseteq\Bbb R^n$ with $\mathcal P_\Bbb Z\leq2^n$ integer points and given locations of $O(\log \mathcal P_\Bbb Z)$ integer points in some positions can we obtain $\...

**1**

vote

**0**answers

85 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 ...

**1**

vote

**0**answers

74 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 ...

**4**

votes

**1**answer

128 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 ...

**0**

votes

**0**answers

98 views

### Is there a transformation that scales or shifts number of lattice points?

Unitary transformation preserves volume of a polytope while $SL(n,\Bbb Z)$ preserves lattice points.
Let polytope $\mathcal K$ in $\Bbb R^n$ be presented with polynomial in $n$ linear inequalities.
...