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.

learn more… | top users | synonyms

3
votes
1answer
3k views

How can I find the number of the shortest paths between two points on a 2D lattice grid?

How do you find the number of the shortest distances between two points on a grid where you can only move one unit up, down, left, or right? Is there a formula for this? Eg. The shortest path between ...
16
votes
5answers
889 views

Every integer vector in $\mathbb R^n$ with integer length is part of an orthogonal basis of $\mathbb R^n$

Suppose $\vec x$ is a (non-zero) vector with integer coordinates in $\mathbb R^n$ such that $\|\vec x\| \in \mathbb Z$. Is it true that there is an orthogonal basis of $\mathbb R^n$ containing $\vec ...
9
votes
2answers
666 views

Elementary proof that if $A$ is a matrix map from $\mathbb{Z}^m$ to $\mathbb Z^n$, then the map is surjective iff the gcd of maximal minors is $1$

I am trying to find an elementary proof that if $\phi$ is a linear map from $\mathbb{Z}^n\rightarrow \mathbb{Z}^m$ represented by an $m \times n$ matrix $A$, then the map is surjective iff the gcd ...
5
votes
2answers
4k views

Lattice paths and Catalan Numbers

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a ...
11
votes
2answers
2k views

Integer lattice points on a sphere

Suppose we have a sphere centered at the origin of $\mathbb{R^{n}}$ with radius $r$. Are there known theorems that state the number of integer lattice points that lie on the sphere? It seems like this ...
4
votes
1answer
400 views

Which internal angles can a lattice polygon have?

I am wondering if for a lattice polygon an internal angle can take any value? If no which ones not and why? I guess there will be some restrictions due to the discrete nature of the grid but I am ...
3
votes
1answer
167 views

Bounds for the size of a circle with a fixed number of integer points

I know that there are infinitely many rational points on the (unit) circle. I am interested in the following question: How large has the radius of a circle to be, such that there are at least $n$ ...
0
votes
1answer
58 views

show that L^+ is non-empty

I want to show that $L^+$ is non-empty where $L$ is a full-rank integer lattice and $L^+$ denotes the set of elements of $L$ having positive coordinates I have an indication that I did not understand ...
9
votes
2answers
671 views

Generalizing the 290 theorem.

I have only just come across the remarkable theorem of Conway about universal quadratic forms over $\mathbb{Z}$; namely that in determining whether a integer coefficient, positive definite quadratic ...
2
votes
2answers
179 views

Prove that $\mathcal{O}_3$ and $\mathcal{O}_7$ are euclidean domains

For a non-square integer $d$ such that $d \equiv 1 \mod 4,$ we define the set $$\mathcal{O}_d := \left\{\frac{a + b\sqrt{d}}{2}:a,b \in \mathbb{Z}, a \equiv b \mod 2 \right\}.$$ Prove that ...
7
votes
1answer
65 views

Orbits of action of $SL_m(\mathbb{Z})$ on $\mathbb{Z}^m$

I'm considering the action of $SL_m(\mathbb{Z})$ on $\mathbb{Z}^m$: if $A\in SL_m(\mathbb{Z})$ and $v\in\mathbb{Z}^m$, then $Av\in\mathbb{Z}^m$. My question is: what are the orbits of this action? ...
2
votes
2answers
53 views

Expression from generators of Special Linear Groups II

I wonder whether one can generate this $t$ matrix form the $A_1$ and $A_2$ matrix below. Here $$ t=\begin{pmatrix} 1& 1& 0\\ 0& 1& 0\\ 0& 0& 1 \end{pmatrix} $$ from: $$ ...
3
votes
1answer
108 views

Bounding the density of finite coprime sets

I am currently running into a problem related to coprime numbers. Consider a set of $d$-dimensional integer vectors, $z \subset \mathbb{Z}^d$ such that each component $z_i$ is bounded by another ...
2
votes
1answer
50 views

Boundedness condition of Minkowski's Theorem

Statement: "Let L be a lattice in $R^n$ and $S\subset R^n$ be a convex, bounded set symmetric about the origin. If $Volume(S) > 2^ndet(L)$, then S contains a nonzero lattice vector. Moreover, if ...
4
votes
2answers
656 views

Projection of a lattice onto a subspace

Let $G$ be a $n \times n$ matrix with real entries and let $\Lambda = \{x^n \colon \exists i^n \in \mathbb{Z}^n \text{ such that } x^n = G \cdot i^n\}$ define a lattice. I am interested in projecting ...
3
votes
1answer
417 views

Good textbooks for lattice and coding theory

I am looking for good textbooks for lattice and coding theory. Lattice and coding theory are very interesting on their own, but I have application of the theory to K3 surfaces & modular forms (and ...
3
votes
0answers
155 views

The $n$-shortest lattice vectors problem in $\mathcal{R}^2$

I am looking for an algorithm to compute the $n$ shortest lattice vectors in $\mathcal{R}^2$. The problem statement is as follows: Given a lattice $L: \{ m \vec{u}+n\vec{v} \} \in \mathcal{R}^2$, a ...
2
votes
2answers
111 views

$x+y\sqrt{2}$ infimum ($x,y\in \mathbb{Z}$)

I've looked for help with this question but I have not found anything, I hope this is not a duplicate. Define the set $A=\{\mid x+y\sqrt{2}\mid \ : x,y\in \mathbb{Z}\ \mbox{and} \mid ...
1
vote
2answers
318 views

How to find the number of squares formed by given lattice points?

Let us say that we are N integer coordinates (x, y) - what would our approach be if we were supposed to find the number of squares we could make from those given n points? Additionally, if we were to ...
1
vote
2answers
181 views

A book useful to learn lattices (discrete groups)

Does anyone know a good book about lattices (as subgroups of a vector space $V$)?
1
vote
1answer
769 views

Lattice Paths to $(2n, 2n)$ that do not go through $(n,n)$

I know that from the origin to $(x,y)$ there are $${x+y \choose x} = {x+y \choose y}$$ Lattice paths. The question is finding the number of paths from the origin to $(2n, 2n)$ not passing through ...
0
votes
1answer
45 views

Newton-Raphson For Integer Factorization

Per my earlier question on Naive Grouping for factorization here, below is the modified Newton-Raphson method (integers only) for the polynomial $N -x^2 - yx - x = 0$. ...
0
votes
0answers
81 views

Naive Grouping for Factorization

I have a naive grouping method for factorization. I am curious as to its novelty and aspects of the code below that will increase its efficiency. The method is best described with an example: For n ...
0
votes
0answers
6 views

Given a random unit cell's defining vectors in a random basis, what kind of lattice am I looking at?

So, as stated in the title, I have a lattice basis $B \in \mathbb{R}^{3\times 3}$ (given as a non-singular Matrix containing its unit cell vectors) which is arbitrarily rotated, scaled and reflected. ...
0
votes
1answer
637 views

Index of a sublattice in a lattice and a homomorphism between them

I am asked to show that if $\phi_A$ is the homomorphism from $\mathbb{Z}^k \rightarrow \mathbb{Z}^k$ given by $\phi_A(x)=xA$ then the index of $\phi(\mathbb{Z}^k)$ in $\mathbb{Z}^k$ is finite if ...
0
votes
1answer
108 views

topology on n-colorings of a lattice?

Consider the collection of all $n$-colorings of $\mathbb{Z^{d}}$ (i.e. the collection of all ways to color each lattice point one of $n$ colors). What are some non-trivial ways to define a topology on ...