Exploring the Relationship Between Lattice Successive Minima and Basis Vectors

In summary, the definition of the ##i##-th successive minima of a lattice is given by ##\lambda_i(\Lambda) = inf\left\{r > 0 | \text{ Linear independent lattice vectors } v_1,...,v_i \text{ with } ||v_j|| \leq r \text{ for } j = 1,2,...,i\right\} \quad \text{ for } i = 1,...,n##. From this definition, it can be shown that the ##i##-th successive minimum is at most as large as the largest lattice basis vector ##b_i##. This can also be proven by considering a basis ##b_1,...,
  • #1
Peter_Newman
155
11
Hello,

I've been thinking a bit about the definition of the ##i##-th successive minima of a lattice (denoted with ##\lambda_i(\Lambda)##), and I would argue that the ##i##-th successive minimum is at most as large as the largest lattice basis vector ##b_i##.

More formally:

##\lambda_i(\Lambda) \leq \max_{i} ||b_i||##

So purely intuitively I would say that makes sense, but is there any way to show this?

Now you could also come up with the idea to claim that the following holds:

##\lambda_i(\Lambda) \leq ||b_i||##

Is there a way to prove this here, I can't find one at the moment unfortunately, while I'm also not sure if this is even possible...

I would be very grateful for any helpful comments!
 
Physics news on Phys.org
  • #2
What is your definition of the successive minima? The one I know makes this really obvious.
 
  • Skeptical
Likes Peter_Newman
  • #3
There are different definitions. I would suggest this one:

## \lambda_i(\Lambda) = inf\left\{r > 0 | \text{ Linear independent lattice vectors } v_1,...,v_i \text{ with } ||v_j|| \leq r \text{ for } j = 1,2,...,i\right\} \quad \text{ for } i = 1,...,n##
Office_Shredder said:
The one I know makes this really obvious.
Which one do you have?
 
Last edited:
  • #4
That's the one I know.So if you pick ##i## basis vectors, they are independent. That's an example of a set of vectors used in the definition of ##\lambda_i## What does that say about the length of the longest vector compared to ##\lambda_i##?
 
  • #5
Office_Shredder said:
That's the one I know.So if you pick ##i## basis vectors, they are independent. That's an example of a set of vectors used in the definition of ##\lambda_i## What does that say about the length of the longest vector compared to ##\lambda_i##?
By definition I would say that ##\lambda_i## has to be less or equal to that longest vector. Is this ok? Basis vector alone makes no shortest vector, but it could...
 
  • #6
Yeah, that's the whole proof
 
  • Like
Likes Peter_Newman
  • #7
Thanks, so this proofs ##\lambda_i(\Lambda) \leq \max_{i} ||b_i||##. This also makes sense from the definition!

Then I have another question about this ##\lambda_i(\Lambda) \leq ||b_i||##, how would one prove or argue this. I'm bothered by the ##i## in the vector (##b_i##) here, because that implies some sort of "sorting" of the vectors...
 
  • #8
You have bad notation with that max, having the index be the same as the left hand side. I would say given a basis ##b_1,...,b_n## of the lattice, for ##1\leq i \leq n##, ##\lambda_i \leq \max_{j} ||b_j||##. In fact, we even know ##\lambda_i \leq \max_{j\leq i} ||b_j||##. (Or same for the max over any ##i## of the basis vectors) In the case where the basis is ordered such that ##||b_1|| \leq ||b_2|| \leq ... \leq ||b_n||##, this implies ##\lambda_i \leq ||b_i||##
 
  • Informative
Likes Peter_Newman
  • #9
Office_Shredder said:
You have bad notation with that max, having the index be the same as the left hand side.
Yes, that' s true, I agree!

Office_Shredder said:
I would say given a basis ##b_1,...,b_n## of the lattice, for ##1\leq i \leq n##, ##\lambda_i \leq \max_{j} ||b_j||##. In fact, we even know ##\lambda_i \leq \max_{j\leq i} ||b_j||##. (Or same for the max over any ##i## of the basis vectors) In the case where the basis is ordered such that ##||b_1|| \leq ||b_2|| \leq ... \leq ||b_n||##, this implies ##\lambda_i \leq ||b_i||##
That's a good way of putting it! Thank you!
 

1. What is a lattice?

A lattice is a mathematical structure that consists of a set of points in n-dimensional space that are arranged in a regular pattern. These points are called lattice points and are connected by straight lines to form a grid-like structure.

2. What is the successive minima of a lattice?

The successive minima of a lattice is a set of numbers that measure the "thickness" of the lattice in different directions. These numbers are determined by finding the shortest distance between the origin and the closest lattice point, and then repeating the process with each subsequent lattice point until all lattice points have been considered. The smallest of these distances is the first successive minimum, and the second smallest is the second successive minimum, and so on.

3. How are lattice and successive minima related?

The lattice and successive minima are related because the successive minima provide important information about the structure and properties of the lattice. For example, the first successive minimum can be used to determine the volume of the fundamental parallelepiped, which is a fundamental unit of the lattice. The successive minima also play a role in applications such as cryptography and coding theory.

4. What is the significance of the successive minima in lattice-based cryptography?

In lattice-based cryptography, the successive minima are used to measure the security of a lattice-based scheme. A larger successive minimum indicates a stronger lattice structure, which is desirable for cryptographic purposes. The successive minima are also used in algorithms for solving hard mathematical problems, which are the basis of many lattice-based cryptographic schemes.

5. How are the successive minima calculated?

The successive minima are calculated using a technique called the Hermite Normal Form (HNF) algorithm. This algorithm transforms the basis of the lattice into a more convenient form, making it easier to calculate the successive minima. The HNF algorithm is an important tool in lattice theory and is used in various applications, including cryptography and coding theory.

Similar threads

  • Linear and Abstract Algebra
Replies
7
Views
766
  • Linear and Abstract Algebra
Replies
20
Views
1K
Replies
1
Views
620
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
16
Views
4K
  • Linear and Abstract Algebra
Replies
2
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Atomic and Condensed Matter
Replies
2
Views
2K
  • Linear and Abstract Algebra
Replies
8
Views
1K
  • Quantum Physics
2
Replies
54
Views
10K
Back
Top