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

16
votes
5answers
997 views

Pick's Theorem on a triangular (or hex) grid

Pick's theorem says that given a square grid (that is, all points in the plane with integer coordinates) and a polygon without holes and non selt-intersecting whose vertices are grid points, its area ...
15
votes
5answers
673 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 ...
12
votes
2answers
340 views

Show $\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$ by block-walking interpretation of Pascal's triangle

A combinatorial proof for the identity $$\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$$ is the following "committee" argument, which seems the most common. There are $\binom{n}{k}$ ...
12
votes
1answer
403 views

Proving a complicated inequality involving integers

Let $a,b,c,d$ be integers such that $$\left( \begin{matrix} a & b \\ c & d \end{matrix} \right) = \left( \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}\right) \mod 2$$ $$ ad-bc =1$$ ...
10
votes
1answer
220 views

Question about Pick's Theorem

Is there a Pick's Theorem for a general lattice in $\mathbb{R}^{2}$?
9
votes
2answers
1k 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 ...
9
votes
1answer
422 views

Path (Feynman) Integrals over Graphs

I was thinking about Feynman integrals the other day and in particular about discretizing the paths. Does anyone know the lay of the land about what happens when you do path integrals over, say, a ...
8
votes
2answers
437 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 ...
8
votes
2answers
222 views

Show that the matrix $A$ with integer entries is injective on the reals to $\mathbb{R}^m$ iff it is injective on the integer lattice.

Show that the $m \times n$ matrix $A$ with integer entries is an injective linear map from $\mathbb{R}^n$ to $\mathbb{R}^m$ iff it is injective as a linear map from $\mathbb{Z}^n$ to $\mathbb{Z}^m$. ...
8
votes
1answer
330 views

“Center-of-Mass” of lattice polygons (generalization of Pick's theorem)

Call a polygon with integer coordinates (in the Euclidean plane) a 'lattice polygon'. Pick's Theorem allows you to efficiently compute the number of lattice points inside this polygon given just its ...
7
votes
1answer
297 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 ...
7
votes
1answer
116 views

What is the limit $\lim\limits_{(x,y)\to(1,1),\ (x,y)\in S}(1-x^py^q)(1-x^ry^s)\sum_{p/q\le m/n\le r/s}x^my^n$?

Let $S=[0,1)^2$ and $m,n$ are positive integers and $p/q,r/s$ are positive rationals with $p/q<r/s$. What is the limit $$\lim\limits_{(x,y)\to(1,1),\ (x,y)\in S}(1-x^py^q)(1-x^ry^s)\sum_{p/q\le ...
7
votes
1answer
55 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? ...
6
votes
1answer
116 views

Power Functions on the Integers

Suppose $f:\mathbb{R}\to\mathbb{R}$ is of the form $f(x)=x^a$ for some $a\in\mathbb{R}^{+}$. If $f(\mathbb{Z})\subset\mathbb{Z}$, show that $a\in\mathbb{Z}$. Source: A friend posed this problem; not ...
6
votes
0answers
201 views

How small parallelograms are we guaranteed to get, when we select the two sides from different plane lattices?

This a shortened version (motivation from telecommunications stripped away) of a question I asked in MO in late May (no answers). I am mostly checking, if somebody has seen this or a related question ...
5
votes
1answer
184 views

Bézout's identity in higher dimensions?

I have an invertible rational matrix $C\in\text{GL}(n,\mathbb{Q})$ which works on lattice $\mathbb{Z}^{n}$. Can I write the resulting set in the following form $$C\cdot \mathbb{Z}^{n}=X\cdot ...
5
votes
1answer
2k views

Integer solutions (lattice points) to arbitrary circles

Wolfram Alpha will provide integer solutions to arbitrary circle equations. I'm trying to understand how it's able to calculate them, but despite a fair bit of digging I haven't found any discussion ...
5
votes
1answer
107 views

Complex elliptic curve for the “conjugate” lattice

Let $\Lambda$ be a lattice in $\mathbb{C}$, and $E=\mathbb{C}/\Lambda$ the corresponding complex elliptic curve. Let $\bar{\Lambda}$ be the "conjugate" lattice, i.e. the one obtained by conjugating ...
5
votes
1answer
262 views

Convergence of Sum over Integer Lattice

Does the sum $$\sum_{z \in \mathbb{Z}^3\setminus \{(0,0,0)\}} \left( \frac{1}{|{\bf x} - {\bf z}|^2} - \frac{1}{|{\bf z}|^2} \right)$$ converge pointwise or even uniformly for $\varepsilon < |{\bf ...
4
votes
1answer
229 views

Proving this identity $\sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}$ using lattice paths

How can I prove the identity $\sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}$? I have to prove it using lattice paths, it should be related to Catalan numbers The $n$th ...
4
votes
2answers
200 views

Guaranteeing an integer lattice point centroid

My question is this: Writing $n(4)$ to be the minimum number of integer lattice points in the plane so that some four of them must determine an integer lattice point centroid, show that $n(4)=13$. I ...
4
votes
1answer
138 views

What is the easiest way to describe the Leech lattice explicitly?

I am aware that the Leech lattice is the unique even unimodular lattice in $\mathbb{R}^{24}$ with no norm $2$ vectors. However I am after a way to describe this lattice explicitly without reference ...
4
votes
1answer
163 views

Is there an algorithm to find a basis for the lattice $V \cap \Bbb{Z}^n$ given a basis for $V \subseteq \Bbb{Q}^n$?

This might be a stupid/very simple question, but since I can't quite seem to come up with a nice trick I will ask it anyway. Assume that we have a vectorspace $V \subseteq \mathbb{Q}^n$ given in the ...
4
votes
1answer
319 views

Shortest Non-Zero Vector in Integer Lattices with Given Points

There are two questions related to the shortest non zero vector problem that have left me scratching my head. Please bear with me as I describe the problem. Disclaimer: this is homework. For the ...
4
votes
1answer
45 views

Lattice in a vector space of dim 2 over a valuated field.

I'm reading "Arbres, amalgames et SL2" of J.P. Serre, and something is not clear to me, but is to him :) Let $k$ be a field, with a discrete valuation $v$, ie a group epimorphism $v:k^\ast \to ...
4
votes
2answers
61 views

Looking for references on 'non-discrete lattices'

A lattice in $\mathbb{R}^n$ is a discrete subgroup that spans $\mathbb{R}^n$. Recently I've been running into a similar sort of object consisting of more than $n$ vectors in $\mathbb{R}^n$ and their ...
4
votes
0answers
104 views

Adelic lattices

Let $\mathbb{A} = \widehat{\mathbb{Z}} \otimes \mathbb{Q} \times \mathbb{R}$ be the adeles over $\mathbb{Q}$. In Deligne's article "Formes modulaires et representations de GL(2)" he states without ...
3
votes
1answer
2k 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 ...
3
votes
1answer
313 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
102 views

Generators of Special Linear Groups

Linear algebra and special-linear group experts please help: I learn that in principle one can generate this $M$ matrix form the $B_1$ and $B_2$ matrix below. Here $$ M=\begin{pmatrix} 0& 1& ...
3
votes
2answers
64 views

Are there 2D analogues for integer division and modular arithmetic?

Let's say you have a "parallelogram" of points $P = \{(0, 0), (0, 1), (1, 1), (0, 2), (1, 2)\}$. This parallelogram lies between $u = (2, 1)$ and $v = (-1, 2)$. Then for any point $n \in ...
3
votes
1answer
49 views

Lower-Bounding angles in integer Lattices

Given an $n \times n$ integer grid I chose any two grid points $a,b$, draw a line $l$ through $a$ and $b$ and measure the angle between $l$ and a horizontal line. I can do this for any grid point pair ...
3
votes
1answer
178 views

Theta series representation of lattices (Leech lattice, especially)

I'm reading now about theta series and its significance in researching self-dual, even lattices. Now, I found the wikipedia article about the Leech lattice, but I'm having trouble understanding where ...
3
votes
1answer
85 views

Nonzero element of minimal length in a lattice?

Given two linearly independent vectors $a,b\in\mathbb{R}^2$ we form the lattice $L=\{ma+nb|m,n\in\mathbb{Z}\}$. Now, a proof starts with "choose a nonzero vector in $L$ of smallest length...". Why ...
3
votes
1answer
123 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$ ...
3
votes
1answer
242 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
2answers
119 views

Smallest angle among two lines in $n \times n$ grid

Given an $n \times n$ grid, what is the minimum angle between any two distinct lines, each going through some grid point $p$ and at least one other grid point? My guess is the minimum is attained by ...
3
votes
1answer
268 views

Closest point to line in lattice

Given an $n$ x $n$ integer grid, I look at all possible lines through two grid points and I am interested in the minimum distance from any grid point (not on the line) to any line. I my guess is that ...
3
votes
1answer
89 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 ...
3
votes
1answer
82 views

Basis reduction and continued fractions

While reading several articles about lattice basis reduction I am left with a few questions. For one, I came across this piece of text Let $\alpha$ and $\beta \in \mathbb{R}$. Then there are two ...
3
votes
1answer
140 views

Classifying all ideals of a lattice $\mathbb{Z}[\sqrt{-d}]$

In Artin's Algebra he presents a method (that I am sure I am butchering) for classifying ideals of a given lattice $\mathbb{Z}[\sqrt{-d}]$ by taking any ideal $I$, choosing an element of minimum norm ...
3
votes
1answer
114 views

Closest vector problem for orthogonal lattices

Let's say I have a reduced basis $\mathcal{B}$ for an orthogonal lattice in $\mathbb{R}^n$, then the Shortest Vector Problem is trivial (the shortest vector in the basis). According to my intuition, ...
3
votes
2answers
263 views

Number of lattice points

Does there exist a formula for counting the number of lattice points not outside of a square , with the at most information available concerning the square are the position coordinates of the four ...
3
votes
0answers
24 views

Number of points in the diagonal of an $X \times Y$ square lattice box.

So assuming we have a $X \times Y$ lattice, Say for example a $3 \times 5$ like so * * * * * * * * * * * * * * * I need to find the number of points that each ...
3
votes
0answers
34 views

Nonplanar equilateral lattice “pentagons”

It is well-known that no two-dimensional point lattice contains a regular pentagon. (See for example http://mathworld.wolfram.com/LatticePolygon.html) The same is true for lattices in $\mathbb{R}^n$, ...
3
votes
0answers
275 views

continued fractions and convex hulls

If I remember correctly, there is a nice correspondence between continued fractions and convex hulls of lattice points in the plane. If $\theta>0$ is the slope of a line in $\mathbb{R}^2$ passing ...
2
votes
2answers
2k 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 ...
2
votes
3answers
44 views

Is it possible to make a regular 3-polygon by selecting $3$ points in $S$

I would appreciate if somebody could help me with the following problem: Let $\mathbb{Z}$ be the set of all integers and let $ S = \mathbb{Z} \times \mathbb{Z} $. Question: 1). Is it possible to ...
2
votes
2answers
96 views

Name for grid system

Is there a name for a type of grid you might find in Battleship? Where coordinates don't relate to points on a grid but rather the squares themselves?
2
votes
2answers
180 views

A problem involving the lattice grid.

Suppose that $22$ points are arbitrarily chosen from a $7\times 7$ lattice grid. We are to prove that there exists at least one rectangle in any $4$ points chosen from the above $22$. A general ...