Problem 1(a). In an LLL-reduced basis we have Therefore, and the desired inequality follows by moving the terms around and taking the root of both sides.
Problem 1(b). Similar to part (a), we get Let be s.t. Together with we get
Question. The inequality for part (b) is so similar to that of part (a). Is it possible to defined a ‘quotient lattice’ so that part (b) is part (a) applied to this quotient?
Problem 1(c). Let be any shortest vector, where is the Gram–Schmidt decomposition of the LLL-reduced basis and Writing we have Here, the first equality is due to Pythagorean theorem, and the second inequality is because is a non-zero lattice point and is a shortest non-zero lattice point.
It is easy to inductively prove backwards (from down to 1) using and the property that for all Let then for all
Problem 2. I prove the meta proposition that the two definitions are equivalent. This would be a good exercise to reactive the muscle of elementary calculus.
Let be the set of radius such that translations of by lattice points cover and define We want to show that (We should prove but this is implied by part (c).)
By the definition of for all and all there exists some s.t. This means whence which implies
Moreover, for all let For all since there exists s.t. which implies This gives us
We may thus conclude
Problem 2(a). Let be a shortest non-zero lattice point and suppose where is a lattice point. We now have for some s.t. This means is a lattice point. It cannot be zero, otherwise would be longer than lattice point Therefore,
Problem 2(b). The lattice has covering radius and minimum distance The former is due to having distance at least to any lattice point.
Problem 2(c). By homework 1 problem 3(c), translations of by lattice points cover For any we have whence (the ball is taken to be closed). Since translations of by lattice points cover we have
Problem 2(d). Choose the fundamental region and partition any covering ball into for lattice points Note that the translated partitions cover since is covering. Therefore, which implies Lastly,
Problem 3. It suffices to consider
Problem 3(a). We need
Problem 3(b). Consider the lattice generated by where is one of the polynomials. The determinant is We want LLL to return a vector of length less than and we analyse this in the next problem.
Problem 3(c). Let then and We need to set We know It suffices to set to be a positive integer s.t. which can be made polynomial in the input length. The rest is obvious.