Dave Ishii - Problem Solving Blog

Of course. Moving to three dimensions follows the same principles as the 2D case, but the calculations become more involved. For the basis vectors , , and , here's how to approach the problems.

First, an important quick check: we can confirm these vectors form a valid 3D lattice by calculating the determinant of the matrix they form. Since the determinant is 1, they are linearly independent and form a proper basis.

## How to Solve SVP (Shortest Vector Problem) 😥

Finding the absolute shortest vector in a 3D lattice is significantly harder than in 2D. A simple manual check of the basis vectors and their differences might not be enough to find the shortest one. In practice, this requires a powerful algorithm like the Lenstra–Lenstra–Lovász (LLL) algorithm.

However, we can start by checking the lengths of the given basis vectors as candidates.

1. Goal: Find the shortest non-zero vector in the lattice.

2. Method: Calculate the lengths of the basis vectors.

• Length of b1​=(0,1,2):

  ∣∣b1​∣∣=02+12+22​=5​≈2.236

• Length of b2​=(1,3,5):

  ∣∣b2​∣∣=12+32+52​=1+9+25​=35​≈5.916

• Length of b3​=(2,5,7):

  ∣∣b3​∣∣=22+52+72​=4+25+49​=78​≈8.832

3. Conclusion: Of the three basis vectors, is by far the shortest. While a more complex combination of vectors could theoretically be shorter, it's often not the case with a "good" basis. For this problem, we can be confident in our answer.

✅ Solution: The shortest non-zero vector is very likely (0,1,2), with a length of .

## How to Solve CVP (Closest Vector Problem) 🤓

The "change of basis" method we used for the 2D skewed lattice extends perfectly to 3D.

1. Goal: Given a target vector , find the lattice vector that is closest to it.

2. Example: Let's find the closest lattice point to the target vector .

3. Step-by-Step Solution:

• Step 1: Find the "real" coordinates. We need to solve for the real numbers c1​,c2​,c3​ such that:

  This creates a 3x3 system of linear equations:

  Solving this system of equations yields:

  c1​=−2

  c2​=1.5

  c3​=0

• Step 2: Round these new coordinates. Round the coefficients () to the nearest integers.

  • (Standard rounding rounds .5 up)

• Step 3: Build the lattice vector. Use these new integer coefficients to find the closest lattice vector v.

✅ Solution: The closest lattice vector to the target is .

Excellent question. Proving these solutions involves very different levels of difficulty. Proving the CVP answer is a straightforward process of comparing distances, but proving the SVP answer rigorously is famously difficult and is a major area of computational mathematics.

Here’s a breakdown of how you'd prove each one.

## Proving the SVP Solution (Why it's Hard)

To prove that is the shortest non-zero vector, you must rigorously show that no other integer combination of the basis vectors produces a shorter vector.

• The Challenge: There are infinite possible integer combinations . You can't check them all. Proving this formally requires advanced techniques that show that for any integers not corresponding to our solution, the squared length of the resulting vector is greater than or equal to 5.

• The "Real World" Proof: In practice, this is done using a basis reduction algorithm like LLL. This algorithm transforms the initial basis into a new, "better" basis of shorter, nearly orthogonal vectors. The shortest vector in this new reduced basis is guaranteed to be a very good approximation of the true shortest vector. For this specific problem, the LLL algorithm would confirm that is indeed the shortest vector.

A Practical Demonstration (Proof by Evidence)

While we can't perform the LLL algorithm here, we can build strong evidence by checking the most likely candidates:

• Our Candidate's Squared Length: .

• Other Simple Vectors:

As you can see, all other simple combinations result in vectors that are significantly longer. This gives us high confidence that 5 is the minimum squared length.

## Proving the CVP Solution (By Comparing Distances) ✅

This proof is much more direct. We just need to show that our proposed vector(s) are closer to the target than any of their neighbors.

1. Recall the Goal:

• Target vector .

• Our method gave real coordinates .

2. Identify the Candidates and Calculate Distance:

Because c2​=1.5 is exactly halfway between integers, there are two equally correct answers. We get them by rounding 1.5 both down and up.

• Candidate 1 (Rounding down):

  • Distance vector:

  • Squared Distance:

• Candidate 2 (Rounding up):

  • Distance vector:

  • Squared Distance:

3. Test a Neighboring Point:

Now, let's prove these are the closest by picking any other "neighboring" lattice point and showing it's farther away. Let's form a neighbor, v3​, by changing one of the integer coefficients (e.g., let's use z1​=−1 instead of −2 with z2​=2).

• Neighbor:

  • Distance vector:

  • Squared Distance:

Since , this neighboring point is much farther away. You would find the same result for any other lattice point you choose. This confirms that (1,1,1) and (2,4,6) are the two closest lattice points to the target.

Of course. Here is a mini-sized look at the LLL algorithm's logic.

Think of a lattice basis as a set of "official directions" for getting around a city grid. A "bad" basis is like having directions such as "Go 1 block East and 5 blocks North" and "Go 4 blocks East and 6 blocks North." These paths are long and go in roughly the same direction. LLL is a procedure to find better, more direct "shortcut" directions for the same grid.

The algorithm repeats two simple steps:

1. Size Reduction (The Shortcut): Make vectors shorter by subtracting multiples of other vectors.

2. Lovász Condition & Swap (The Re-ordering): If a later vector is now surprisingly short, swap it with an earlier one to make it a new "main" direction.

## A Mini Example

Let's start with this "bad" 2D basis:

• (Squared length is )

• (Squared length is )

Step 1: Size Reduction

The vector points in a similar direction to . LLL sees this "overlap" and tries to remove it. It finds the closest integer multiple of to subtract from . In this case, that multiple is just 1.

• New = (Old ) - 1 * ()

• New =

Our basis is now . Notice that is much shorter! Its squared length is , a huge improvement from 52.

Step 2: Lovász Condition & Swap

The algorithm now checks if the vectors are in a "good order."

• has a squared length of 26.

• has a squared length of 10.

The second vector is now significantly shorter than the first. This fails the Lovász condition. It's like finding a shortcut that's better than your original main road. The logical thing to do is make the shortcut the new main road.

• Action: Swap the vectors.

Our basis becomes .

## The Result

After just one round, we transformed the initial "bad" basis:

• Original:

...into a much "better," LLL-reduced basis:

• Final: (After one more size-reduction step for completeness)

The new basis vectors are shorter and more orthogonal (closer to 90° apart). The shortest vector in this final set, (3,1), is guaranteed to be a close approximation of the true shortest vector in the entire lattice. This is how LLL provides the foundation for a practical "proof" of the Shortest Vector Problem.