Question regarding fundamental region of a lattice

[Peter_Newman]

Hello,

I want to prove that for any lattice $\Lambda = \Lambda(B)$ (the $B$ is a basis) the orthogonalized parallelepiped $P(B^*) = B^*\left[-0.5,0.5\right)^n$ is a fundamental region of a lattice.

If I wanted to show this, I would try to establish a volume argument here. After all, the determinant of a lattice is no more than the volume of the fundamental region, by definition. Now I already know that $det(\Lambda) = |det(B)| = |det(B^*U)| = \prod ||b_i^*||$. The $B = B^{*}U$ is just the Gram-Schmidt composition as matrix, $B^*$ is an orthogonal matrix and $U$ is an upper triangular matrix containing the Gram-Schmidt coefficients. So now we go on, by asking what is the volume of $P(B^*)$, that is the determinant $det(B^*)$ and that is just the product again $\prod ||b_i^*||$. So here we have a direct relationship between $vol(P(B))$ and $vol(P(B^*))$. If we already know that $P(B)$ is a fundamental region, then we can conclude from the volume argument that $P(B^*)$ is also a fundamental region.

This raises two questions for me. First, is this meant as a "proof" in the right way? Second, can we formalize this a little better, make it a little more concrete?

 

[pasmith]

This is largely unnecessary.

It is straightforward that if $B$ is a basis, then $B^{*}$ is a basis. Thus if $P(B)$ is a fundamental region for $\Lambda (B)$ then $P(B^{*})$ is a fundamental region for $\Lambda(B^{*})$, because anything you can prove for an arbitrary lattice $\Lambda(B)$ also holds for the lattice $\Lambda(B^{*})$.

 

[Peter_Newman]

Hello @pasmith, thank you for your reply! I can understand what you write. I would then like to ask whether the argument about the volume would be correct, or how one leads the proof about the volume concretely.

 

[pasmith]

I think reference to volume is not necessary. The result follows from the 1D case: for every $x \in \mathbb{R}$ there exists a unique $N \in \mathbb{Z}$ and a unique $r \in [a, a + b)$ such that $x = Nb + r$.

 

[Peter_Newman]

I think reference to volume is not necessary. The result follows from the 1D case: for every $x \in \mathbb{R}$ there exists a unique $N \in \mathbb{Z}$ and a unique $r \in [a, a + b)$ such that $x = Nb + r$.

Yes, I agree on that. But the hint for the proof is to consider the volume of $P(B^*)$

 

[Peter_Newman]

Well, I'm still interested in a solution. The hint for the solution is given: "Notice that the volume of $P(B^*)$ is $\prod_i ||b_i^*||$, as expected". I am interested if my suggestion from above is correct so far :)

 

[Peter_Newman]

[...] anything you can prove for an arbitrary lattice $\Lambda(B)$ also holds for the lattice $\Lambda(B^{*})$.

@pasmith I thought about this sentence again and wondered how you could justify it. I would refer this to the "arbitrary", then $\Lambda(B^*)$ is "only" a special case of $\Lambda(B)$. Is that what you meant by that?

 

[pasmith]

Yes.

 

[Office_Shredder]

The volume argument isn't enough. A fundamental region has to contain a single lattice point, and tile the whole space (I think there are other similar definitions). A 100x0.01 rectangle in 2 dimensions is not a fundamental region of the integer lattice, but does have a volume of 1. In this case if you center it at the origin it contains many more than 1 lattice point (which means when you shift it, it overlaps with itself in the x direction, and misses space in the y direction)

 

[Peter_Newman]

Thank you @Office_Shredder for your answer! So if you continue the thought you would have to check if there is an overlap. If there is no overlap, then it is a fundamental region.

Then one would have to show that e.g. $x = \Lambda(B) + P(B^*)$ is unique? or?

 

[Office_Shredder]

What does x= mean there? The right hand side is a set of approximately the whole space (depending on whether it is a fundamental region or not)

 

[Peter_Newman]

Sorry, I had forgotten to mention that here. The $x$ stands for $x \in span(B)$.

 

[Peter_Newman]

A fundamental region has to contain a single lattice point, and tile the whole space

Good. Then the question would be how to show that $P(B^*)$ is a fundamental region of $\Lambda(B)$.

The other question: how to show that $P(B^*)$ is a fundamental region of $\Lambda(B^*)$ (note the change here) is not difficult.

My problems are with the first question: how to show that $P(B^*)$ is a fundamental region of $\Lambda(B)$.

For this, I would define $x = P(B^*) + \Lambda(B)$ and check that every $x \in R^n$ can be uniquely represented by $P(B^*) + \Lambda(B)$. However, this is not so simple...

 

[Office_Shredder]

Given that you have the right volume, if the lattice shifts don't intersect they have to cover the whole space. Consider an enormous sphere, so that effects around the surface don't matter, then you have an equal number of non intersecting volumes using this region vs a region you know is a fundamental unit (all the lattice shifts in the sphere) which both have the same volume, and the latter leaves no empty space, so the former can't leave empty space either.

Suppose $z\in x+P\cap y+P$ for $x,y$ lattice points and z any arbitrary point. Then $z=x+p_1=y+p_2$ for $p_1,p_2\in P$. Hence $x-y=p_2-p_1$.

$x-y$ is another lattice point, so a contradiction can be generated by showing you can't get a lattice point by adding two elements of the region (I've been a little sloppy here, you can add two elements from the surface of the region and get a lattice point, the real issue is if you can add two interior points. I'll let you think it over)

 

[Peter_Newman]

Suppose $z\in x+P\cap y+P$ for $x,y$ lattice points and z any arbitrary point. Then $z=x+p_1=y+p_2$ for $p_1,p_2\in P$. Hence $x-y=p_2-p_1$.

Hey @Office_Shredder, thanks for your answer! I would also proceed similarly. See below:

For this, I would define $x = P(B^*) + \Lambda(B)$ and check that every $x \in R^n$ can be uniquely represented by $P(B^*) + \Lambda(B)$. However, this is not so simple...

We would have to show uniqueness and assume that there is an overlap, then let $x_1 = P(B^*) + \Lambda(B)$ and $x_2 = P(B^*) + \Lambda(B)$. If there is an overlap, then it means that $x_1 = x_2$, this is noting else then
$$x_1 = P(B^*) + \Lambda(B) = a_1 b_1^* + ... + a_n b_n^* + a_1'b_1 + ... + a_n'b_n$$
and
$$x_2 = P(B^*) + \Lambda(B) = c_1 b_1^* + ... + c_n b_n^* + c_1'b_1 + ... + c_n'b_n$$
with $a_i,c_i \in$ [0,1) and $a_i', c_i' \in \mathbf{Z}$.

The problem now is that once here we have the Gram Schmidt vectors and the basis vectors. You could try to rewrite the basis vectors, but I think that makes things even more difficult. Even if I am sure that this is the way for the proof. But what happens next?

The other question: how to show that $P(B^∗)$ is a fundamental region of $Λ(B^∗)$ (note the change here) is not difficult.

This can be shown relatively easy with the idea from above, this is easier since we only have one "sort" of vectors. The calculation of uniqueness works out excellently here!

 

[Office_Shredder]

The $a_i$ and $c_i$ are actually in $[-0.5,0.5)$.

This is actually important (though obviously shifting a fundamental region doesn't change its fundamentalness) because you can rearrange to
$\sum m_i b_i = \sum x_k b^*_m$ where $m_i$ are integers, and $x_k\in [-1,1)$. I would recommend assuming $x_k\neq -1$ for your first pass at the proof, as it just adds technical annoyance. The goal is to prove all the coefficients are zero. Remember that $b^*_k$ is orthogonal to many of the $b_i$s, which should help you go through step by step and prove that the coefficients must all be zero.

 

[Peter_Newman]

Hey! Yes the coefficients should be in $[-0.5,0.5)$. according to the original definition, that is correct. But as you also say, the interval is not necessarily crucial, so I thought I'd just try it for [0,1) first. You probably mean [0,1) instead of [-1,1], right?

The goal is to prove all the coefficients are zero.

Yes that's what I wanted to show. My next step would be:

$$x_1 = P(B^*) + \Lambda(B) = a_1 b_1^* + ... + a_n b_n^* + a_1'b_1 + ... + a_n'b_n$$
$$x_2 = P(B^*) + \Lambda(B) = c_1 b_1^* + ... + c_n b_n^* + c_1'b_1 + ... + c_n'b_n$$

$$x_1 = x_2 $$
$$a_1 b_1^* + ... + a_n b_n^* + a_1'b_1 + ... + a_n'b_n = c_1 b_1^* + ... + c_n b_n^* + c_1'b_1 + ... + c_n'b_n$$
$$a_1 b_1^* + ... + a_n b_n^* -(c_1 b_1^* + ... + c_n b_n^*) = c_1'b_1 + ... + c_n'b_n - (a_1'b_1 + ... + a_n'b_n)$$
$$(a_1 - c_1)b_1^* + ... + (a_n - c_n)b_n^* = (c_1' - a_1')b_1 + ... + (c_n' - a_n')b_n$$

At this point, however, we have the problem that two kinds of vectors appear and we have to decide what to transform. One idea would be to replace the $b_i$'s by Gram Schmidt vectors, but this would introduce new coefficients. Here I don't see a solution to move forward right now....

 

[Office_Shredder]

Hey! Yes the coefficients should be in $[-0.5,0.5)$. according to the original definition, that is correct. But as you also say, the interval is not necessarily crucial, so I thought I'd just try it for [0,1) first. You probably mean [0,1) instead of [-1,1], right?

If you add two arbitrary numbers in $[-.5,.5)$ the sum could be anywhere in $[-1,1)$

 

[Peter_Newman]

Regarding my post #17, I would continue by writing $b_i$'s in the Gram Schmidt version. This results on the right hand side in:

$$(a_1 - c_1)b_1^* + ... + (a_n - c_n)b_n^* = (c_1' - a_1')b_1 + ... + (c_n' - a_n')b_n$$
$$(a_1 - c_1)b_1^* + ... + (a_n - c_n)b_n^* = (c_1' - a_1')b_1^* + ... + (c_n' - a_n')(b_n^* + \sum_{i=1}^{n-1} db_i^*)$$

where $d$ is arbitrary Gram Schmidt constant.
If one compares the coefficients e.g. for $b_n^*$ this is
$$(a_n - c_n) = (c_n' - a_n')$$
and since the right hand side is an integer number we can say $(c_n' - a_n') = 0$ and then we have $a_n = c_n$.

We can proceed in that manner and obtain that for all other coefficients we have $a_i = c_i$. This shows then that $x_1 = x_2$ are unique since the coefficients are all equal.

Is this right so far, or did I miss something?

 

[Office_Shredder]

That looks right to me.

 

[Peter_Newman]

Excellent. Then I would say the proof is complete. Thank you @Office_Shredder!