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

0
votes
1answer
70 views

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 ...
4
votes
1answer
331 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 ...
12
votes
2answers
343 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}$ ...
1
vote
0answers
30 views

integer programming with bounded dimension

We know that integer programming with bounded dimension or fixed number of variables can be solved in polynomial time by Lenstra's result(from results of the LLL algorithm). After heavy foraging i ...
0
votes
0answers
72 views

Transforming FCC, BCC and HCP lattice types to cubes.

I was wondering if it is possible to transform the FCC, BCC and HCP into SC, or simple cubic lattices while preserving the lengths between the nodes? I would like to transform each into this: ...
3
votes
0answers
36 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$, ...
2
votes
1answer
51 views

Lattice points in spheres

Let $\mathbb{R}^n$ have the standard Euclidean metric and call a point $P = (x_1, \ldots,x_n)\in\mathbb{R}^n$ a lattice point if for all $i$, $x_i\in\mathbb{Z}$. Allowing small number theoretic ...
0
votes
0answers
54 views

Ideals in cubic fields

I've been studying number fields, and the ideals of their integer rings, and I have a question. First, I know the following in the quadratic case. If a $\mathbb{Z}$-basis for the integer ring is ...
1
vote
1answer
24 views

What is a good introduction to quantities such as the norm of a lattice and of short vectors in the context of lattice reduction?

I am trying to make sense of different notations used in measuring lattices, in particular before and after a basis reduction. In particular, I am trying to get bounds and estimates for the size of ...
1
vote
0answers
98 views

Lattice theory in mathematics and physics

I have undertaken a project examining lattice model and trying to construct algorithm that could work on all lattice (in physical sense, or crystal structure). I notice there is a branch in ...
1
vote
0answers
30 views

Inclusion-minimality of a lattice basis

An integer lattice is a subgroup of $\mathbb{Z}^n$. Since $\mathbb{Z}$ is PID, each lattice has a well-defined rank and a generating set of rank many elements is a basis. I wonder if there is a way ...
2
votes
1answer
48 views

Question regarding polygons

Can you prove, that if a equilateral lattice n-gon is constructible, then there will be such a polygon for which the sides have minimal length?
3
votes
1answer
90 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 ...
0
votes
1answer
89 views

Lattice Squares; Basic Interesting Facts and Problems

I'm going to write an article in an educational magazine for middle school students, about the game Square It. The purpose of the game is to make lattice squares: I want to introduce the game, and ...
1
vote
0answers
68 views

A lattice-theoretic question related to noncommutative tori

[NCG] So I'm trying to pin down a fairly well-known bit of noncommutative-geometric folklore that says that for $\Theta \in M_N(\mathbb{Q})$ skew-symmetric, the corresponding noncommutative $N$-torus ...
2
votes
1answer
80 views

Proof of the finite number of Bravais lattices?

I've been taught that there are a finite number of Bravais lattices in 1, 2 and 3 dimensions. I am wondering if there is a proof of this fact. Maybe this is obvious and I am only missing certain key ...
2
votes
1answer
560 views

Find point on line that has integer coordinates

Given a 2D line e.g. (3,10) -> (8.3,16.5), how can I find any point on that line that has has whole-number coordinates? I can easily iteratively walk along one ...
0
votes
1answer
117 views

Lattices in the complex plane

Consider the ring $R=\mathbb{Z}[\sqrt{-2}]$. It is a lattice in the complex plane: the set of points with integer coordinates with respect to the basis: $1,\sqrt{2}i$. Each mesh of the lattice is a ...
2
votes
2answers
60 views

Find lattice points on a planar curve

I have the following curve in the plane: $$y = \frac{c-x}{6x+1}$$ Given a constant value $c \in \Bbb N$; is there a technique(s) I can apply to find lattice points on this curve?
0
votes
1answer
21 views

What's the maximum number of sums of $ak_1,..,ak_m, b\ell_1,…,b\ell_m$ needed to solve for $a$ or $b$?

Given a set of integer multiples of $a$ and $b$, $ak_1,..,ak_m, b\ell_1,...,b\ell_m$, what is the maximum number of finite sums of the multiples you can create such that no sum of all multiples of $a$ ...
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
105 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 ...
1
vote
0answers
41 views

Why the following observations regarding lattices hold?

The following is an excerpt of a recent paper on lattice cryptography: Let $n$ and $q$ be integers [...], and let $\beta > 0$ . Given a uniformly random matrix $A \in \mathbb Z^{n \times m}_q$ ...
0
votes
0answers
77 views

Obstruction to construct the set of vectors in lattice

Lets consider a lattice $\mathbb{Z}^n$ with some unimodular scalar product $\mathbb{Z}^n \times \mathbb{Z}^n \mapsto \mathbb{Z}$ and the set of vectors $e_0,\ldots,e_k$ with conditions: $$ ...
0
votes
2answers
368 views

Lattice Paths from $(1, 1) \to (x, y)$

Moderator Note: This is a current contest question on Brilliant.org. Let $S$ be the set of $\{(1,1), (1,−1), (−1,1), (1,0), (0,1)\}$-lattice paths which begin at $(1,1),$ do not use the same ...
2
votes
2answers
97 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?
1
vote
1answer
84 views

Fundamental volume of quotient group

I came across this rule in my old notes, but I need an explanation to how it could possibly originate: The theorem says that for any lattice $L$ in $\mathbb{R}^n$, the order of the quotient group, ...
3
votes
1answer
83 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 ...
0
votes
0answers
171 views

Its just one point… How do I find it?

Okay so here is the deal... I have a CLOSED convex polyhedron $Ax \le b$ (where $x$ is in $R^n$) and it has i vertices denoted $V_i$ such that $V_i = (x_{i1}, x_{i2}, \ldots, x_{iN})$ where $0 \le ...
2
votes
1answer
63 views

Lattices in $\mathbb{C}$

I have the following assignment: consider the map $$|\cdot|:\mathbb{Z}[i]\longrightarrow \mathbb{N},\qquad |a+ib|:=a^2+b^2$$ 1) Prove that $|\alpha|<|\beta|$ iff $|\alpha|\leq |\beta|-1$ and ...
0
votes
1answer
167 views

Mapping Between Sequences: Example

Take $0\leq r < m$, and let all values be nonnegative and integer. Consider the function on a sequence ${x(n)}$, $\Phi_mx(mn+r)=mx(n)+\frac{r}{m}(x(n+1)-x(n))$, where we consider $x(0)=0$. As an ...
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 ...
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 ...
1
vote
1answer
170 views

Does “short integer solution” lattice problem admit hard instances with q=2?

Let $q$ be a prime, $m,n$ be integers with $m>n$, and $\beta$ be a real number. Moreover, let $A$ be a matrix in $\mathbb Z^{n \times m}_q$. In the "short integer solution" (SIS) lattice problem, ...
1
vote
1answer
154 views

How tell if a polyhedron contains a lattice point

So given a polyhedron $Ax \le b$ Is there an Algorithm or formula to determine whether said polyhedron contains a lattice point (integer point) I was thinking a couple things: brute force ...
1
vote
2answers
484 views

Monotonic Lattice Paths and Catalan numbers

Can someone give me a cleaner and better explained proof that the number of monotonic paths in an $n\times n$ lattice is given by ${2n\choose n} - {2n\choose n+1}$ than Wikipedia I do not understand ...
0
votes
0answers
56 views

Determinant of a Lattice Code

For a binary $[n,k,d]$ code $C$ with lattice $\Lambda (C)$ I want to show that $det(\Lambda (C)) = 2^{n-2k}$. I'm having a little trouble with demonstrating this and it would help me very much ...
0
votes
1answer
68 views

Generating vectors of the face-centered cubic lattice

I can't find a reference for a set of generating vectors for the Tetrahedral-octahedral honeycomb lattice. I would like to know the "canonical" set and if possible a more general set described by ...
7
votes
1answer
304 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
91 views

What is a good way to simplicize the integer lattice?

I have a function $f$ defined on the positive integer lattice in $\mathbb{R}^n$ (i.e. the vectors in $\mathbb{R}^n$ whose coordinates are all nonnegative integers). I want to extend the domain of $f$ ...
1
vote
5answers
83 views

Represent any number with two factorials

I was wondering if it is possible to represent any positive integer with x! - y! ? If not, is there any proof?
2
votes
0answers
42 views

When does a simplex have an interior lattice point?

Given $r$ vectors $v_1, \dots, v_r$ in $\mathbb{Z}^n$, is there an easy way (in terms of the entries of the $v_i$) to determine if there is a point of $\mathbb{Z}^n$ in the interior of the simplex ...
0
votes
2answers
155 views

Counting lattice points interior to a polygon

If I define an integer lattice $\Lambda \subseteq \mathbb{Z}^2$ with a basis given by $$\omega_{1} = a \hat{i} + b\hat{j}, \;\;\; \omega_{2} = -b \hat{i} + a\hat{j}$$ How can I count how many lattice ...
1
vote
1answer
43 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
43 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
41 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
55 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$ ...
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 ...
4
votes
2answers
201 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 ...
0
votes
0answers
91 views

Counting lattice points in a square region

We have a lattice which is spanned by the vectors $(a,b)$ and $(-b,a)$, where $a,b \in \mathbb{N}$. Now we have a square region centered at $(0,0)$ having sides of length $2r+1$ for $r\in \mathbb{N}$. ...