Lower bound on M in rationalapprox

[jd-foster]

Hi Christian,

Great package! I've been looking into the literature on simultaneous diophantine approximation and found something curious about the Hanrot implementation you've used for rationalapprox.

It appears that you need to ensure a lower bound on M of 2^(n(n+1)/4 in order that q = abs(B[1,1]) is in fact always non-zero. Otherwise, it can be zero and will of course 'blow up' the result. I came across this is practical examples and found the theoretical reason, I believe.

I can explain more if interested, but basically if you compare to the equivalent proof in Schrijver, he proves that (in the notation of the passage) that ||B(:,1)|| < C implies q ! = 0 (Schrijver uses 0 < \epsilon < 1 and we have our M equals his 2^(n(n+1)/4 \epsilon^(-n).

[chrisvwx]

Thanks for your positive comments on the package !

To be clear, is the lower bound on M that you suggest 2^(n(n+1)/4)? You wrote 2^(n(n+1)/4, which needs a closing paren somewhere. I don't have access to the Schrijver book to confirm

--

For the example in the help text for rationalapprox we have x = [0.3912641745333527; 0.5455179974014548; 0.1908698210882469] for which 2^(n*(n+1)/4)=8. For both M=10 and M=7 the function gives q=2. I.e. it's not clear to me how useful it is to restrict M to be greater than 2^(n(n+1)/4)

[chrisvwx]

James,

I will likely close this at some point if you have no more comments.

The rationalapprox function is not intended to be a powerful tool, rather as a simple demo of what one can do with lattice tools. The function is not the primary focus of the package and I do not plan to do extensive work to improve it.

[jd-foster]

Hi Chris,

Happy if you want to close this, I'm not pushing any changes. Yes, the lower bound is 2^(n(n+1)/4) (bracket in the exponent). I just wanted to share the observation, which essentially boils down to a difference between a theoretical guarantee and practical use. On larger dimensional problems, the short basis is much more sparse and you can't rely on the initial q to not be zero, but a user should always test for such things anyway. But thanks for putting together a nice reference implementation of this, it was very useful for me to see how it could be done.