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.

In geometry and group theory, a lattice in $\Bbb R^n$ is a subgroup of the additive group $\Bbb R^n$ that is isomorphic to the additive group $\Bbb Z^n$ and that spans the real vector space $\Bbb R^n$. In other words, for any basis of $\Bbb R^n$, the subgroup of all linear combinations with integer coefficients of the basis vectors forms a lattice. A lattice may be viewed as a regular tiling of a space by a primitive cell.

Lattices have many significant applications in pure mathematics, particularly in connection to Lie algebras, number theory, and group theory. They also arise in applied mathematics in connection with coding theory, in cryptography because of conjectured computational hardness of several lattice problems, and in the physical sciences. For instance, in materials science and solid-state physics, a lattice is a synonym for the "frame work" of a crystalline structure, a 3-dimensional array of regularly spaced points coinciding in special cases with the atom or molecule positions in a crystal.

858 questions
30
votes
5 answers

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

Pick's theorem says that given a square grid consisting of all points in the plane with integer coordinates, and a polygon without holes and non selt-intersecting whose vertices are grid points, its area is given by: $$i + \frac{b}{2} - 1$$ where…
mau
  • 9,559
  • 3
  • 41
  • 70
22
votes
3 answers

Probability that a random pair of points are opposite corners of a square in an $n\times n$ integer lattice

Question: Find the probability that a random pair of lattice points are opposite corners of a square in an $n\times n$ integer lattice. Note: By a square in a lattice, I mean a square whose vertices are all lattice points. Motivation: I have a…
Peter Woolfitt
  • 20,914
  • 6
  • 54
  • 85
21
votes
1 answer

How many lattices does it take to cover a regular $n$-gon?

Given some positive integer $n\ge 3$, we can ask how many 2-dimensional lattices $L_1,\ldots,L_k$ are required such that their disjoint union contains all vertices of a regular $n$-gon. (We don't require that the lattices be centered at the…
RavenclawPrefect
  • 15,080
  • 2
  • 27
  • 97
20
votes
2 answers

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 is something someone has studied so hopefully…
user13255
19
votes
5 answers

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 x$, consisting of vectors with integer…
17
votes
1 answer

Hypercube and Hyperspheres

Let $n,k\in\mathbb{N}$. In this problem, the geometry of $\mathbb{R}^n$ is the usual Euclidean geometry. The lattice hypercube $ Q(n,k)$ is defined to be the set $ \{1,2,...,k\}^n \subseteq\mathbb{R}^n$. If we want to cover this hypercube with…
15
votes
2 answers

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}$ ways to select $k$ from a set of $n$ to go on the…
NaN
  • 1,377
  • 3
  • 12
  • 20
15
votes
2 answers

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 form represents all positive integers it suffices…
fretty
  • 10,858
  • 1
  • 24
  • 37
15
votes
2 answers

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 of the determinants of all the $m\times m$ minors…
Steven-Owen
  • 5,416
  • 7
  • 28
  • 55
14
votes
1 answer

How to count lattice points on a line.

How can we count the number of lattice point on a line, given that the endpoints of the lines are themselves lattice points? I really can't think of how counting lattice points would work, so please provide me some intuition on how lattice points…
Shaurya Gupta
  • 4,179
  • 8
  • 26
  • 45
13
votes
3 answers

Ballot counting when ties occurs exactly $r$ times

Ballot Problem with Fixed Number of Ties: Problem Statement: In an election, candidate A receives $m$ votes and candidate B receives $n$ notes. Let $m \ge n$. In how many ways can the ballots be counted so that ties occur exactly $r$ times ($r \le…
anecdote
  • 979
  • 5
  • 17
12
votes
1 answer

Question about Pick's Theorem

Is there a Pick's Theorem for a general lattice in $\mathbb{R}^{2}$?
user4269
  • 123
  • 3
12
votes
1 answer

Finding all 15-ominoes that tile the plane and have distinct internal adjacencies

Problem Description: This problem oddly came up in Minecraft with some friends. Not sure what the best terms are; but that's partly why I'm here. So a polyomino is built up from squares. This problem is to find 15-ominoes (pentdecominoes?) that…
12
votes
1 answer

Does every $4$-dimensional lattice have a minimal system that's also a lattice basis?

An full $n$-dimensional lattice $\Lambda$ is a discrete subgroup of $\mathbb{R}^n$ (equipped with some norm $\lVert \cdot \rVert$) containing $n$ linearly independent points. If $\Lambda = \{ A z, z\in \mathbb{Z}^n\}$ for $A \in GL(n,\mathbb{R})$,…
12
votes
2 answers

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 20×20 grid? This is a problem I was working on a…
Rustyn
  • 8,227
  • 3
  • 27
  • 47
1
2 3
57 58