1
$\begingroup$

I'm reading Fundamental Problems of Algorithmic Algebra by Chee-Keng Yap and could not solve the following problem.

The shortest k-sequence (where k > 2 is the dimension of the lattice) need not form a basis of the lattice.

With following definition of a shortest k-sequence:

We define $u ∈ Λ$ to be a shortest vector in $Λ$ if it has the shortest length among the non-zero vectors of $Λ$. More generally, we call a sequence $(u_1 , u_2 , . . . , u_k )$ for $k ≥ 1 $, of vectors a shortest k-sequence of $Λ$ if for each $i = 1, . . . , k$; $u_i$ is a shortest vector in the set $Λ \setminus Λ(u_1 , u_2 , . . . , u_{i−1} )$.

$\endgroup$
2
  • 1
    $\begingroup$ just do exercise 1.7 on page 222 for $n=5$ $\endgroup$
    – Will Jagy
    Commented Apr 4, 2022 at 1:00
  • $\begingroup$ Thank you, i hope my solution is correct. $\endgroup$
    – ASP
    Commented Apr 4, 2022 at 14:09

1 Answer 1

0
$\begingroup$

I was able to solve it thanks to the comment from Will Jagy.

Exercise 1.7: (Dubé) Consider $e_1 , e_2 , . . . , e_{n−1} , h $where $e_i$ is the elementary n-vector whose ith component equals 1 and all other components equal zero, and $h = (\frac{1}{2} , \frac{1}{2}, . . . ,\frac{1}{2} )$. Show that this set of vectors form a basis for the lattice $Λ = \mathbb{Z} ∪ ( \frac{1}{2} + \mathbb{Z})$. What is the shortest n-sequence of Λ? Show that for $n ≥ 5$, this shortest n-sequence is not a basis for $Λ$.

For $n=5$ the shortest 5-sequence is $(e_1, e_2, e_3, e_4, e_5)$, since $\|h\| = \sqrt{0.5^5} \approx 1.118$ is bigger than $\|e_5\| = 1$ and $e_5 = -e_1 -e_2 -e_3 -e_4 + 2*h$. The shortest sequence is not a base for the lattice since you cant generate $h$ with just integer coefficients.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .