2
$\begingroup$

According to the manual page on LatticeReduce, The product of the norms of lattice vectors will decrease. The claim seems to be true for small lattices, but, I cannot confirm this for higher dimensional lattices. For example,

dim = 10;
a = RandomInteger[{-10, 10}, {dim, dim}];
b = LatticeReduce[a];
N[Times @@ (Norm /@ #)] & /@ {a, b}

gives {7.6381410^12, 6.3690610^11}, as claimed. But,

dim = 50;
a = RandomInteger[{-10, 10}, {dim, dim}];
b = LatticeReduce[a];
N[Times @@ (Norm /@ #)] & /@ {a, b}

resulted in {3.5805410^81, 9.8595110^83}.

My question is: What is the measure of lattice complexity which LatticeReduce is really trying to minimize?

The $\delta(B)$ which is explained in DumpsterDoofus's answer to Mathematica Lattice Reduce Command is not decreasing in the above example.

I'm using Mathematica 13.0.1.

$\endgroup$
4
  • $\begingroup$ Good observation. A smaller example that is in conflict with the documentation is a={{1,3,-2},{2,0,3},{3,-1,0}}; b=LatticeReduce[a]; Times@@(Norm/@a)>=Times@@(Norm/@b) which gives False, so I agree that statement in the documentation is misleading. $\endgroup$
    – user293787
    Aug 18 at 3:55
  • $\begingroup$ A remark about the answer by @DumpsterDoofus that you mention: The command LatticeReduce preserves the determinant, Det[Transpose[a].a]===Det[Transpose[b].b]. Therefore the denominator in the quantity $\delta$ defined by @DumpsterDoofus does not actually change under LatticeReduce and was probably only included for conceptual reasons, to have the interpretation of measuring "cube-likeness". $\endgroup$
    – user293787
    Aug 18 at 3:56
  • $\begingroup$ Did you read the comments after this answer? It is pointed out there that $\delta$ is not actually minimized, and it refers to LLL for details. $\endgroup$
    – user293787
    Aug 18 at 3:57
  • $\begingroup$ Thanks. I missed the comment. As far as I tested in 50 dim lattice, $\delta$ almost always increased. I just wonder how MMA concludes the output is "better" than the input lattice. There must be some criterion .... Maybe I should read the original LLL paper. $\endgroup$
    – A. Kato
    Aug 18 at 4:15

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy