# What values of $\delta$ and $\eta$ are being used in LatticeReduce?

The Lenstra–Lenstra–Lovász algorithm has a parameter $\delta$ with $1/4 < \delta < 1$, where roughly speaking the closer $\delta$ is to 1 the longer it takes, but the better basis reduction you get. Options[LatticeReduce] returns {}, so what value of $\delta$ is LatticeReduce using? Is there any way to tell it which $\delta$ you want LLL executed with?

If Mathematica is using Nguyen-Stehle, then there is a second parameter $\eta$ with $1/2 < \eta < \sqrt{\delta}$. What is the default for that in LatticeReduce, and how can I change $\eta$?

• That other parameter is fixed to .51 and only changed for too-small $\delta$ (or maybe we change $\delta$, I forget). In any case it is not configurable. Nov 5 '15 at 17:50
• I should clarify: .51 is actually what they refer to as $\overline{\eta}$ rather than $\eta$. Computations are done with the former whereas results are guaranteed in terms of the latter. Nov 5 '15 at 18:22

In this comment, it is noted that LatticeReduce[] is now using the Nguyen-Stehle variant of LLL, so any results you might see from LatticeReduce[] can be different from a "classical" implementation of LLL.

Having said this, LatticeReduce[] does take options, but through a not too transparent interface:

SetSystemOptions["LatticeReduceOptions" ->
{"LatticeReduceRatioParameter" -> .75}];


The list of default option settings is accessible through SystemOptions["LatticeReduceOptions"]; the default setting of Automatic for "LatticeReduceRatioParameter" indicates that the choice is made internally, depending on the input matrix.

• (I should hasten to add that I picked all of this from Daniel Lichtblau. Maybe he'll have more to say when he sees this.) Nov 4 '15 at 9:56
• All correct. The Automatic setting is due to the fact that .75 is used for integer/rational input (the usual case) whereas .8 is used for Gaussian integer/rational input. The 3/4 default predates me and the 4/5 for Gaussians was from when I extended LatticeReduce to handle those (more than 20 years ago, from what I can see in the commit logs). Nov 4 '15 at 16:22
• @Daniel, I didn't know a different setting was needed for Gaussian integers! Do you know a reference for this? (The 0.75 setting was already in the original LLL paper, IIRC.) Nov 4 '15 at 17:14
• For Gaussians it need not be .8 but it is required to be larger than 1/2 if I remember correctly. You are correct that .75 is used in LLL (the paper). Here is a reference that I think is relevant: Huguette Napias. A generalization of the LLL-algorithm over Euclidean rings or orders. Journal de Theorie des Nombres de Bordeaux 8(2):387-396. 1996. There must be older knowledge though, since I implemented the Gaussian case a couple of years before that. Nov 4 '15 at 17:50