Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
3answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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. ...