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

1
vote
1answer
49 views

How can I tell if two points projected onto a tiled hyperplane are in the same tile?

I have a hyperplane defined by two vectors in $\mathbb{Z}^3$ and I have tiled the hyperplane by parallelograms defined by the two vectors. Then I have two lattice points that I want to project down ...
0
votes
1answer
48 views

Lattice formed by a linear congruence

Let there be a linear congruence $a+b y \equiv 0 \pmod{m}$, with $y$ and $m$ ($m$ is a prime) values known. Do all the integer $(a,b)$ pairs satisfying the congruence form a lattice? If yes, how can I ...
0
votes
0answers
48 views

Determinant of a superlattice

I'm beginning to study lattices and cannot solve the following exercise from the book: Let $\Lambda=\left\langle\mathbb{Z}^n,\left(\frac{a_1}q,\ldots,\frac{a_n}q\right)\right\rangle$, where ...
1
vote
1answer
66 views

Basis condition in lattices

Let $\Lambda$ be a lattice in $\mathbb{R}^n$ (i.e. a discrete subgroup spanning the whole space). Given a basis $e_1,\dots,e_n$ of the lattice, we can consider the fundamental parallelogram $P$ ...
4
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 ...
4
votes
2answers
257 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
194 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 ...
1
vote
1answer
232 views

What happens when the basis vectors of an integer lattice are not linearly independent?

The definition of a lattice requires basis vectors that are not linearly independent. Why? Specifically the following three vectors are linearly independent and form the basis of a lattice: ...
6
votes
1answer
123 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 ...
0
votes
0answers
66 views

Orthogonality in a lattice

Let $\Lambda$ be a lattice with a quadratic form $q$ of signature (3,19). Let $\Lambda_{\mathbb{R}}:=\Lambda\otimes \mathbb{R}$ and $W\subset \Lambda_{\mathbb{R}}$ a positive subspace of dimention 3. ...
2
votes
1answer
35 views

dist($av$, $L$) = $a \cdot $ dist($v$, $L$)?

If $L$ is a lattice subspace and $v$ is the closest lattice point to $L$, why does dist($av$, $L$) = $a \cdot $ dist($v$, $L$)? I saw this step in a proof that every lattice has a lattice basis. (I ...
5
votes
1answer
198 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 ...
2
votes
2answers
215 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 ...
16
votes
5answers
846 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 ...
1
vote
1answer
293 views

How do you construct a lattice from its basis or its Gram Matrix?

I'm really having trouble trying to understand this. A few weeks back, I got pretty interested in sphere packing and I'm trying to grasp the idea of using a matrix to represent the basis of a lattice. ...
3
votes
1answer
160 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 ...
0
votes
1answer
67 views

Lattice generated by elements of minimal length

I'm following Miranda's book on algebraic curves and Riemann surfaces. In the section where he talks about the automorphisms group of the complex tori he claims the following: Let $L$ be a lattice in ...
2
votes
1answer
122 views

Planar cross section of leech lattice?

I was wondering what any planar cross sections of the leech lattice would look like. I don't know much about this topic at all, I'm just quite curious. Is there any way to find out?
2
votes
0answers
51 views

Automorphisms of a lattice and changing to a nicer $\mathbb{Z}$-base

Suppose I have an integral lattice $L$ with an arbitrary $\mathbb{Z}$-base, equipped with a positive-definite nondegenerate symmetric bilinear form $\langle\cdot,\cdot\rangle$, and an isometry $\nu$ ...
0
votes
2answers
250 views

Finding a basis for a complex lattice given a nondivisible vector in the lattice

If I am given some lattice defined as, say $$L=\{Az_1+Bz_2\ |\ A,B \in\mathbb{Z}\}$$ and a vector $v=az_1+bz_2$ , where $\gcd(a,b)=1$, I would like to find another vector $\,w\in L\,$ such that ...
2
votes
0answers
126 views

Lattice Reduction Problem: Minimizing the “Longest” Basis Vector

Suppose we have a basis for an integer lattice formed by the vectors $\vec v_1, \vec v_2, \ldots,\vec v_n$. Then let $A$ be the augmented matrix $( \vec v_1| \space \vec v_2| \cdots |\space \vec ...
1
vote
1answer
92 views

Solution count of quadratic form congruence over $\Bbb Z / 8 \Bbb Z$

Let $(L,q)$ be an even Lorentzian lattice of signature $(1,l-1)$, i.e., $q(\lambda) \in \Bbb Z$ for all $\lambda \in L$ and the (non-degenerate) quadratic form $q$ is of type $(1,l-1)$ (the ...
0
votes
1answer
572 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 ...
1
vote
0answers
141 views

solution count of quadratic form congruences

Let $(L,q)$ be an even Lorentzian lattice of signature $(1,l-1)$, i.e., $q(\lambda) \in \Bbb Z$ for all $\lambda \in L$ and the (non-degenerate) quadratic form $q$ is of type $(1,l-1)$ (the ...
3
votes
1answer
164 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
1answer
152 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$ ...
2
votes
0answers
51 views

A certain labeling of lattice points on the plane [duplicate]

Possible Duplicate: A stronger version of discrete “Liouville’s theorem” Let each lattice point of the plane be labeled by a positive real number . Each of these numbers is the arithmetic ...
3
votes
2answers
355 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 ...
0
votes
1answer
425 views

Proving Binomial Identities Using Bijections To Lattice Paths

How can I derive a bijection to show that the following equality holds? $2\displaystyle\sum\limits_{j=0}^{n-1} \binom{n-1+j}{j} = \binom{2n}{n}$ In class, we've been deriving bijections using ...
3
votes
1answer
371 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 ...
1
vote
1answer
45 views

Multiplications by unimodular matrices

I feel like this must have an obvious answer, but my knowledge of integer arithmetic is limited. Given an (integer) matrix $A$ of dimension $m \times n$ and an unimodular matrix $U_l$ of dimension $m ...
2
votes
0answers
75 views

Term for intersection of lattice and convex region?

Is there a special term or convenient phrase for the restriction of a convex region to points of a lattice? This is motivated by wanting to talk about the feasible points of a discrete problem. I'd ...
4
votes
1answer
170 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 ...
3
votes
3answers
784 views

Finding a basis for the solution space of a system of Diophantine equations

Let $m$, $n$, and $q$ be positive integers, with $m \ge n$. Let $\mathbf{A} \in \mathbb{Z}^{n \times m}_q$ be a matrix. Consider the following set: $S = \big\{ \mathbf{y} \in \mathbb{Z}^m \mid ...
7
votes
0answers
234 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 ...
2
votes
0answers
281 views

Probability distribution of a self avoiding walk

Preliminary: Consider a walk on the lattice $\mathbb{Z}_d$ lattice of length $N$. In a normal random walk, if we let $N$ get large the end position has a probability distribution (PDF) that looks ...
2
votes
1answer
746 views

A hyperbola passing through integer lattice points

Prove that for any $n\geq 0$, there is a hyperbola that passes through exactly $n$ lattice points (= points with integer coordinates) and find an example. For example it is easy to see that the ...
1
vote
1answer
338 views

Integral point inside a quadrilateral

Given four points in $\mathbb{R}^2$, is there an efficient method to determine if the convex hull contains an integral point $(m,n)\in\mathbb{Z}^2$? If it helps, I can assume the convex hull is a ...
1
vote
2answers
175 views

A book useful to learn lattices (discrete groups)

Does anyone know a good book about lattices (as subgroups of a vector space $V$)?
2
votes
0answers
41 views

Bijection between $\operatorname{GL}_n(F)/\operatorname{GL}_n(O)$ and lattices in $F^n$

I've come across mention of a bijection between lattices in $F^n$ ($F$ a field, in my case $\mathbb{C}(\!(t)\!)$) and elements of $\operatorname{GL}_n(F)/\operatorname{GL}_n(O)$, where $O$ is the ring ...
1
vote
0answers
118 views

Norm of the generators of a fractional ideal.

Let $\mathcal{O}_l=\mathbb{Z}[\frac{1+\sqrt{-l}}{2}]$ with $l$ a prime number congruent to 3 mod 4. Let $\mathfrak{a}$ be a non-principal fractional ideal of $\mathcal{O}_l$. My questions are: Why ...
1
vote
0answers
376 views

How many amplitude levels does a squared QAM constellation have?

In the above question, I choose terminology from communication engineering, but I will precisely define all the involved quantities below. It is a geometric question and I am not sure if it is ...
1
vote
0answers
97 views

A variant of the “closest vector problem” (CVP) in lattice-based cryptography

Consider a public-key scheme on lattices, such as GGH. The private key is a basis $\mathbf{B} \in \mathbb{Z}^{m \times n}$ of a lattice $\mathcal{L}$ with good properties (such as short nearly ...
9
votes
2answers
621 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
268 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$. ...
12
votes
1answer
417 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$$ ...
6
votes
1answer
3k 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
120 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 ...
1
vote
1answer
153 views

Number of matrices with weakly increasing rows and columns

I'm curious as to how many matrices there are of size $m \times n$ with elements of the set $\{1, \ldots , k\}$ such that each row and column is weakly increasing? The answer should be expressable as ...
2
votes
1answer
144 views

Bounding the number of integer solutions of the following inequality

Let $r\geq 1$ be a real number, $-1\leq x\leq 1$ a real number and $y>2$ a real number. We consider this data to be fixed. How can I obtain an upper bound on the number of $(a,b,c,d)\in ...