Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 studied during the history. Of course, all answers, suggestions and comments are welcome.

A detailed description of the question: Select two lattices $\Lambda_1$ and $\Lambda_2$ (here a lattice=additive free abelian group without accumulation points) of maximal rank two in the real plane. We normalize the lattices in such a way that their fundamental regions have area $=1$. Let $B(r)$ be a disk of radius $r$ centered at the origin. Let $N_1,N_2>0$ be two parameters. Select one non-zero vector $\vec{v}_1$ from $B(N_1)\cap \Lambda_1$ and another $\vec{v}_2$ from $B(N_2)\cap \Lambda_2$. Consider the area of the parallelogram with sides $\vec{v}_i,i=1,2.$ Let $D(N_1,N_2)$ be the minimum area of such parallelograms. We want to make the function $D(N_1,N_2)$ as large as possible by selecting the lattices $\Lambda_1$ and $\Lambda_2$ in a clever way. The simplest form of my question is: what can we say about the asymptotic behavior of $D(N_1,N_2)$ as the parameters $N_1,N_2\to\infty$ (either separately or jointly)? As additional questions I would like to ask: Does this ring a bell? What kind of methods have been used in studying this problem? What methods would you use?

What we know about the problem: The pigeon hole principle tells us that there is a constant $K$ (may depend on the lattices, but not on the scale parameters $N_1, N_2$) such that $$ D(N_1,L_{2,\min})\le \frac{K}{N_1}, $$ where $L_{2,\min}$ is the length of the shortest vector of $\Lambda_2$. The proof is easy. Fix a short non-zero vector $\vec{v}_2$ from $\Lambda_2$. The orthogonal projections of the vectors from $\Lambda_1\cap B(N_1/2)$ on to the line $\perp\vec{v}_2$ have lengths $\le N_1/2$. As there are $O(N_1^2)$ points in $\Lambda_1\cap B(N_1/2)$, some of those projections are within $O(1/N_1)$ of each other. Let $\vec{v}_1$ be the difference vector. As it is the difference between two vectors of length $\le N_1/2$, we have $\vec{v}_1\le N_1$.

selecting a pair of lattice points with nearby projections

In the above image the short arrow is the vector $\vec{v}_2$. The black line is the subspace generated by it, and the grey line is the orthogonal complement. The dots mark the points of the lattice $\Lambda_1$. Two points with nearby projections have been singled out by using larger dots. As is their difference vector $\vec{v}_1$, whose projection is then predictably very short. I also drew another copy (= the other arrow) of $\vec{v}_2$ to begin at the endpoint of $\vec{v}_1$. The two copies of $\vec{v}_2$ are a pair of parallel edges of the parallelogram. The small parallelogram has base $=|\vec{v}_2|$ and height = the length of the projection of $\vec{v}_1$ on the grey line. When drawing this image, I was selecting the lattice points from a square shaped region as opposed to a disk. The effects of that change can be absorbed into the constant $K$, and can IMHO be ignored.

Using real quadratic number fields and Liouville's theorem it is easy to construct lattices $\Lambda_1$ and $\Lambda_2$ in such a way that we always have $$ D(N_1,N_2)\ge \frac{K'}{N_1N_2}. $$ In this sense the pigeon hole bound from the previous paragraph has the correct order, when $N_2=L_{2,\min}$. In light of this I think a natural main question would be

Is their a known upper bound $D(N_1,N_2)\le f(N_1,N_2)$ where both $N_1$ and $N_2$ appear in an essential role?

With the word essential I mean that a bound should decrease, when we increase either $N_1$ or $N_2$. For example, in the above application of the pigeon hole principle we can trivially switch their roles to get a symmetric function $D(N_1,N_2)\le K\max\{N_1,N_2\}^{-1}$, but this is not useful :-)

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.