10
$\begingroup$

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!

$\endgroup$
  • $\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.