Title question description: 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 the fundamental region has 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$ such that $$ D(N_1,L_{2,\min})\le \frac{K}{N_1}, $$ where $L_{2,\min}$ is the length of the shortes 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$.

enter image description here

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}$. Ideally I would like to apply Minkowski's bound to the direct sum of the lattices, but the determinant of a 2x2 real matrix is a quadratic form of signature (2,2), so I don't see how to select a usefully large convex region with small determinants (in absolute value). 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 effectively?

With the word effectively 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 effective :-)

The problem we really want to solve: Let $\Lambda_i, i=1,2,\ldots,U$ be lattices of complex (resp. real) $r\times n$ matrices, $n=rU$ of maximal possible rank $2rn$ (resp. $rn$). Select non-zero matrices $X_i$ from $\Lambda_i\cap B(N_i)$. Build an $n\times n$ matrix $X$ by putting these blocks on top of each other. What can we say about the minimal absolute value $D(N_1,N_2,\ldots,N_U)$ of $|\det X|$? We have generalizations of the pigeon hole bound, the best given by a graduate student in our group: http://arxiv.org/abs/1201.5744. He also has a construction based on algebraic number theory and Shidlovskii's bound from Diophantine approximation here: http://arxiv.org/pdf/1202.0675.pdf. That construction meets the pigeon hole bound in the case that $N_2,N_3,\ldots,N_U$ are small constants. Other researchers had earlier given somewhat similar constructions, but Shidlovskii's bound gives worse estimates to their $D$-function - Toni Ernvall managed to keep the matrix entries in a smaller field, which helped quite a bit. My gut feeling is that the constructions are closer to the optimal than the pigeon hole bound, because the latter is kinda trivial.

In the case $U=1$ the answer is known, because then we only need to select a single rank $2n^2$ of complex $n\times n$ matrices. If the said lattice is (a scaled version of) an order of a division algebra of index $n$ with an imaginary quadratic number field as a center, then the determinants will be bounded away from zero. Whenever $U>1$ the pigeon hole bound forces arbitrarily small determinants to occur.

Background: All this is related to the problem of estimating the performance of these lattices as signal sets for multiantenna radio communication: a single row = the signal of a single transmission antenna, $U$ is the number of simultaneous users, a lattice is the signal set of a fixed user. The study of the function $D(N_1,N_2,\ldots, N_U)$ is related to certain asymptotice figures of merit, but unfortunately the information-theory goes over my head. Some colleagues had hoped that it would be possible to have determinants bounded away from zero also, when $U>1$. The pigeon hole bound was our way of showing that they were asking too much. The math is not too hot, but it earned me a trip to ITW2010 in Cairo, so I got to see the pyramids!

  • $\begingroup$ Maybe you could clarify your argument bounding $D(N_1, \Lambda_{2, min})$. Your 'difference vector' $v_1$ is presumably the difference of vectors $x, y, \in \Lambda_1 \cap B(N_1/2)$ whose projections onto the line $v_2 ^\perp$ differ by $O(1\N_1)$. But this doesn't immediately yield an estimate on $|v_1|$. ie. the triangle inequality only gives us $|v_1| \leq 1/N_1 + |v_1 - proj_{v_2^\perp}v_1|$. So how are you uniformly estimating the second term on the RHS? Perhaps specifying precisely the dependancy of your constant $K$ would be helpful. $\endgroup$ – J. Martel May 30 '12 at 0:03
  • $\begingroup$ And just to make sure we're on the same page, the orthogonal projections of the vectors in $\Lambda_1 \cap B(N_1/2)$ onto the line $v_2^\perp$ all have lengths $\leq N_1/2$---which indeed is $\leq N_1$. $\endgroup$ – J. Martel May 30 '12 at 0:10
  • $\begingroup$ @J. Martel, thank you for your interest. I added an image together with a hopefully useful caption. I first left it out as I wanted to keep the size of the post smaller, but that was a mistake. I apologize for not being clear. $\endgroup$ – Jyrki Lahtonen May 30 '12 at 7:13
  • $\begingroup$ @J. Martel: I missed your first question. I might be willing to let the "constant" $K$ depend on the two lattices as long as it does not depend on $N_1$ or $N_2$. It may be possible to get an explicit constant valid for all choices of lattices. But then we might need to use bounds on the shortest vector of a lattice given the size of its fundamental region. That is ok in 2D, but becomes murky, when we generalize. $\endgroup$ – Jyrki Lahtonen May 30 '12 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.