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.

Filter by
Sorted by
Tagged with
2
votes
0answers
17 views

Finding the closest point in a root lattice

Let $L_n$ be a crystallographic root lattice, embedded inside $\mathbb{R}^n$. This means that $L_n$ is the $\mathbb{Z}$-span of the simple roots $\alpha_1, \ldots, \alpha_n \in \mathbb{R}^n$, which ...
2
votes
0answers
53 views

Square root “base”

In normal base system (say binary), you'll do P = [1,2,4,8, ...] then a value can be represented as coefficients $\{a_i\}$ where $$N=\sum_{i=0}^n a_i\cdot P_i$$ ...
4
votes
0answers
52 views

Circle-to-circle contacts on a hexagonal grid.

In OEIS sequences A047932 and A263135, coins are placed in a "spiral" on the faces or vertices of a hexagonal grid respectively, and the number of coin-to-coin contacts are counted. The ...
1
vote
1answer
24 views

Upper bound of lattice points of $\mathbb{R}^d$ in a given annulus

Suppose we have $\Gamma$ which is a lattice of $\mathbb{R}^d$ ($rk(\Gamma) = d$), and $| \cdot |$ a norm on $\mathbb{R}^d$. We consider as well $c_1, c_2 > 0$, and the annulus $S = \{ P \in \Gamma \...
0
votes
0answers
107 views

modular flow/horocyclic flow in positive first quadrant acting on image of lattice

I'm referencing some of dynamics on the space of lattices and number theory. Consider the modular flow in $\Bbb R^2_+:$ $$\pmatrix{e^{e^s} & 0 \\ 0 & e^{e^{-s}}}\big(x,y\big):= \bigg(x^{e^s}, ...
2
votes
1answer
53 views

Understanding unfamiliar notation related to algebraic geometry and combinatorics

I'm reading a paper$^\dagger$ and having a bit of trouble understanding some of their notation. The notation is introduced on the bottom of the first page. Let $N \cong \mathbf{Z}^n$ be a lattice, ...
2
votes
0answers
35 views

Unitary matrix acting on integer-valued vectors

Let $n\in\mathbb{N}_{\geq 1}$ be given. Consider the vector space $\mathbb{C}^n$ and its standard basis $\{e_j\}_{j=1,\dots,n}$. Let $U$ be a unitary matrix, with columns $u_1,\dots,u_n$, and regard ...
0
votes
0answers
33 views

Points of square lattice inside a circle

Background: I'm reading a paper about Brownian Motion. Problem: I have a square lattice of mesh size $\frac{1}{\lceil \epsilon^{-1} \rceil}$ where $\epsilon > 0$. Given a circle with radius $r$, ...
1
vote
0answers
49 views

Moore-Penrose over $\mathbb{Z}_p$ that minimizes Euclidean norm $\|Ax-b\|_2$

Assume you have an overdetermined equation system $Ax = b$ over $Z_p$ with $p$ prime, that is $A \in \mathbb{Z}_p^{m \times n}$, $x \in \mathbb{Z}_p^{n}$, $b \in \mathbb{Z}_p^{m}$ ($x$ unknown) and ...
0
votes
0answers
15 views

Is $\Lambda(q)^{\bot}(A) = \{y \in \mathbb{Z}^m: Ay = b \mod q\}$ also a lattice?

Given a matrix $\bf{A} \in \mathbb{Z}_q^{n \times m}$, then $$\Lambda_q^{\bot}(A) = \{y \in \mathbb{Z}^m: Ay = 0 \mod q\}$$ is a q-ary lattice. I am wondering whether $$\Lambda_q^{\bot}(A) = \{y \...
0
votes
0answers
8 views

Same generator matrix implies same lattice?

Say there exists some lattice $L$ with a generator matrix $A$, As well, there exists some lattice $J$ with a generator matrix $B$, If $A=B$, is it necessarily the case that $L=J$? I know that the ...
0
votes
0answers
25 views

How can I compute the number of solutions to an under-constrained equation over some integers?

I have system of under-constrained equations over a fixed set of integers, defined as follows, how can I find the number of solutions to this problem? A computational reference will do (in-fact ...
0
votes
0answers
6 views

Modeling that there is no feasible solution to a linear system in mixed integer programming

My question is about how to construct a mixed integer programming to model that there is no feasible solution to a given linear system. Specifically, given $x\in \mathbb{R}^{n}$ and $z\in \{0,1\}^{d}$,...
0
votes
0answers
10 views

What is the relationship between lattice of invariant subspaces $Lat(A+B)$, $Lat(A)$ and $Lat(B)$ where $A$ and $B$ are bounded linear operators?

I a studying about the lattice of invariant subspaces of a Hilbert space and get stuck. I am trying to find some results from lattice theory or other majors (for example algebra or dynamical systems) ...
0
votes
0answers
19 views

Matrix-vector multiplication in $(Z_q[X]/(X^n+1)$ using NTT representation

Let $R_q = Z_q[x]/(X^n+1)$, $n=256$, $q$ large prime be a polynomial ring, and let $A \in R_q^{K \times L}$ be a matrix of polynomials in this ring and $v \in R_q^{L}$ a vector of polynomials. Now we ...
2
votes
1answer
44 views

How can I calculate the Eisenstein series of a complex lattice?

Suppose I have a lattice $\Lambda = \mathbb{Z}+\frac{3}{2}i\mathbb{Z}$. How would I go about calculating $G_{2n}(\Lambda)$ for a given $n \in \mathbb{N}$?
1
vote
0answers
75 views

Eight points in the plane, cyclic quadrilaterals with twelve distinct circumcircles. Minimal integer-coordinate solution?

Here is a follow-up to this question. In the original question, it was asked whether eight points can be arranged in the plane to constitute the vertices of more than eight cyclic quadrilaterals. ...
0
votes
0answers
20 views

Translate polygon to cover at least 2 lattice points

Let $S$ be a polygon (not necessarily convex) in the plane, of area greater than $1$. Show that it is possible to translate $S$ in the plane so that it covers at least $2$ lattice points. Any thoughts ...
1
vote
0answers
44 views

Weighted projective space as toric variety

I am trying to solve exercise 3.3.10 from Cox' book on toric varieties. I have no trouble with part (a), but it seems to me that for part (b) I have to wirte down the variety $X_{\Sigma}$ explicitly, ...
5
votes
2answers
82 views

Combinatorics on divisors

Consider the set $D$ of all divisors of $10000$. What is the number of subsets $H \subseteq D$ containing at least two elements such that for every $a, b \in H$, $a \mid b$ or $b \mid a$? I tried ...
1
vote
0answers
32 views

Voronoi Cell of the Dual Lattice?

A lattice is a discrete (we may assume full-rank) subgroup of $\mathbb{R}^n$, often written as the image of $\mathbb{Z}^n$ under a particular matrix $\mathbf{B}\in\mathbb{R}^{n\times n}$ (a basis of ...
3
votes
0answers
38 views

If an animal tiles the plane via translation, can it do so in a lattice configuration?

It is known that if a polyomino tiles the plane using only translated copies, then it has at least one such tiling where the centroids of each tile form a lattice; see for instance the paper Arbitrary ...
1
vote
0answers
54 views

Size of $ \mathbb{Z}^m/\Lambda$, for $\Lambda \subset \mathbb{Z}^m$

To be specific my question is how to determine $| \mathbb{Z}^m/\Lambda_q^{\bot}(A)|$ which $$\Lambda_q^{\bot}(A) = \{y =\mathbb{Z}^m \mid Ay =0 \bmod q \}$$ for full rank $A_{q}^{n*m}$ that $m\geq n$ ...
1
vote
0answers
14 views

Estimate the volume of symmetric convex set in $\mathbb R^n$ in terms of the number of lattice points contained in the convex set.

Suppose $K$ is a convex set in $\mathbb R^n$ which is symmetric with respect to the origin. Minkowski's theorem tells us that if the volume of $K$ is greater than $2^n$, then $K$ contains a nonzero ...
3
votes
1answer
56 views

Find all walks that visit all natural numbers exactly $l$ times, and are formed by repeating a finite sequence of steps

I am interested in integer "walks" $x_n\in\mathbb{Z}$, $n\geq0$, on the grid of integers with the following properties: Given integer parameters $l\geq1,\ \ s_0,s_1,...,s_{d-1}$, : The &...
0
votes
0answers
10 views

Complexity of quantization in interesting lattices

Quantization or the closest vector problem in general lattices is known to be NP-hard. Are there any computational complexity results for interesting classes of lattices? E.g., do we know the ...
0
votes
1answer
182 views

Is this a new Primality Test? [closed]

Every $n \in \mathbb{Z}$ is prime if all lattice points on $x+y=n$ are visible from the origin. Graphed points on $x+y=n$ not visible from the origin for potential primes. ...
4
votes
0answers
47 views

Milnor's example for hearing the shape of drums

I heard that the first counter example for the Kac's question "Can we hear the shape of drums?" is given by John Milnor, as two 16-dimensional tori that are isospectral but not isometric. I ...
1
vote
0answers
173 views

Difference between squares of lattice points on a circle. Is this truly impossible?

Introduction Above are five triangles that all have the same value r and thus B, E, H, K, and N are all points on a circle with radius r. Triangle ABC is a right angled isosceles triangle. All ...
3
votes
1answer
45 views

Proving if $\gamma\in SL(2,\mathbb{Z})$ has order $6$, then $\gamma$ is conjugate to $\begin{bmatrix}0 & -1\\ 1 & 1\end{bmatrix}^{\pm1}$

I am reading Diamond's book on modular forms, and I came across the proof that the stabilizers of elliptic points on the upper half-plane are cyclic. To prove that, Diamond starts to show that a ...
1
vote
1answer
62 views

Minkowski Theory: The embedding of fractional ideal is a full rank lattice.

I encountered this question when studying the proof towards Minkowski bound. Let $K/\mathbb{Q}$ be a number field of degree $n$. Let $r$ and $s$ be the number of real and complex embedding of $K$ ...
0
votes
0answers
31 views

Intersection points convex hull and grid

I am trying to find the intersection points of the boundary of a convex hull of a finite set $S$ and a grid in multiple dimensions. How can I do this?
0
votes
0answers
19 views

How can I construct an element in a particular “quadrant” of a lattice (preferably short)?

I previously asked this question on Math Overflow here with no luck. Given a basis for a full-rank lattice $\mathcal{L} \subset \mathbb{R}^n$ I want to find a vector with totally positive entries, in ...
1
vote
1answer
41 views

A Conway quadratic (form) equation in four variables

In the Sensual Quadratic Form page 44, J.H. Conway is discussing isospectral lattices of dimension 4 when he states the following: ''... we find all solutions of the equation(s) $x^2+7y^2+13z^2+19w^2=...
0
votes
1answer
44 views

Why $\mathbb Z(\sqrt2)$ is not a lattice?

The set $\mathbb Z(\sqrt2) = \{a + b\sqrt2 : a, b \in \mathbb Z\}$ is not a lattice, according to the book of Robeldo = because when you replace $a, b \in \mathbb Z$ by $a, b \in \mathbb R$ we do ...
0
votes
1answer
57 views

Discriminant of integral basis

Let $A=\mathbb{Z}\alpha_1+...+\mathbb{Z}\alpha_n$, $B=\mathbb{Z}\beta_1+...+\mathbb{Z}\beta_n$, be two lattices, s.t. $A\subseteq B$. Then $d(\alpha_1,...,\alpha_n)=c^2d(\beta_1,...,\beta_n)$, where $...
2
votes
2answers
53 views

Bound on the shortest non-zero vector in any full rank n-dimensional lattice $\Lambda \subseteq \mathbb{R}^n$ with respect to the $1$-norm.

How can i prove $$\lambda_1 \; \leq \; (n! \; det(\Lambda))^{\frac{1}{n}} \approx \frac{n \; det{(\Lambda)}^\frac{1}{n}}{e}.$$ Here $\Lambda_1$ is shortest non-zero vector. My initial thought was ...
1
vote
0answers
27 views

A semigroup $\mathbb{N}\mathcal{A}$ is saturated in $M$ if and only if $\mathbb{N}\mathcal{A}=\text{Cone}(\mathcal{A})\cap M$

I'll first recall some definitions here for convenience. Given a finite set $S$ in a real vector space $V$, $$\text{Cone}(S)=\{\sum\limits_{u\in S} \lambda_u u\mid \lambda_u\geq 0\}.$$ An affine ...
2
votes
1answer
88 views

Every distance squared between two points in $\mathbb{Z}^n$ is clearly all $\in \mathbb{N}$. Is the converse true (upto isomorphism)?

Every distance squared between two points in $\mathbb{Z}^n$ is clearly all $\in \mathbb{N}$. Is the converse true (upto isomorphism)? The title was rather informal, so clarifying the question: Is ...
0
votes
0answers
15 views

Number of integer points inside a cover of a set made using disjoints integer rectangles or parallelograms

I Have some problems prooving facts about tessellations in $\mathbb{Z}^d$. I will introduce some notation before stating my problem. Given $A,B\subseteq \mathbb{Z}^d$, with $C(A,B)$ I will denote a ...
2
votes
1answer
41 views

Expression of sum of squares as a sum of a specific form

This question is a follow-up of this one. Let $x,y \in \mathbb{Z}$, and suppose that $x^2+y^2 \ge 4$, and that $x,y$ are not both odd. Do there exist $a,b,c,d \in \mathbb{Z}$ such that $ (a+d)^2+(b-c)^...
1
vote
1answer
27 views

Are the singular values of matrices in $SL_2(Z)$ dense in $(0,1)$?

Given a $2 \times 2$ real matrix $A$, we denote by $\sigma_1(A) \le \sigma_2(A)$ its singular values. If $\det A=1$, then $0<\sigma_1(A)\le 1$. Define $X=\{\sigma_1(A) \, | \, A \in SL_2(Z)\}$. Is $...
1
vote
1answer
60 views

Efficiently find at least one lattice point $(x,y)$ on hyperbola of equation $axy+bx+cy+d=0$

Even after a lot of search on internet, I didn't come up with a solution. I need an algorithm to efficiently find at least one lattice point on hyperbola of equation $axy+bx+cy+d=0$. Lattice point ...
0
votes
0answers
15 views

Lattice Inclusion

I've seen the following corollary, and I don't understand something fundamental about one of the definitions. Corollary: If $L_1\subset L_2$ is an inclusion of lattices and $D = [L_2:L_1]$ then $L_1\...
0
votes
1answer
26 views

Conditions under which the Lattice Generated by a Subset of Lattice Vectors is Equivalent to the Original Lattice

In general, the sublattice $L_2$ generated by subset of vectors of $L_1$ need not have the same rank as $L_1$. Even if it does, it may be a proper sublattice of $L_1$. However, if the rank and ...
0
votes
0answers
46 views

Visibility of points on a rectangular lattice under a certain distance from the origin

If I have points a rectangular lattice such that each point takes the form of $(a+bi,c+dj)$ with $i,j\in \Bbb Z$ (for some given $a,b,c,d\in\Bbb Z$), and $b,d>0$. How can I find the number of ...
0
votes
0answers
12 views

Transforming computable numbers into analytic functions using diophantine equations?

By Matiyasevich's theorem, any enumerable set $\mathbf{S}$ can be expressed as solutions of a diophantine equation in the integers. These can always be expressed as degree 4 polynomials in the ...
0
votes
2answers
23 views

How many positive integral solutions exist for $2a+3b-c = 0$ where $a$ ranges from $0$ to $5$, $b$ from $0$ to $10$ and $c$ from $0$ to $40$?

I was stuck with this particular problem. I tried finding a solution by attempting to find the coefficient of $x^0$ in $(1+x^2 +\dots+x^{10})(1+x^3 +\dots+x^{30})(1+x^{-1} +\dots+x^{-40})$ but for ...
1
vote
0answers
36 views

The canonical metric on the space of lattices in $\mathbb R^n$

Let $\Lambda_1, \Lambda_2$ be two lattices on $\mathbb R^n$, (is there/)what is a canonical way to define the distance between $\Lambda_1, \Lambda_2$ such that the metric gives the topology on the ...
0
votes
1answer
20 views

What is the minimum of a translated lattice?

Given a lattice $\mathcal{L}$ with minimum $\lambda_1(\mathcal{L})$, how can we describe the minimum of a translated lattice $t + \mathcal{L}$ for some $t \in \text{span}(\mathcal{L})$, $t \notin \...

1
2 3 4 5
14