I had asked this question at MathOverflow and was pointed here.

I'm working on implementing Lenstra's algorithm. At the bottom of p.5 (at "construct $n+1$ linear functions"), he says to constrain each $g_i:\mathbb{R}^n\to\mathbb{R}$ by its value on each of $n+1$ vectors (namely, $v_0,\dots,v_n$). My question pertains to what Lenstra does after optimizing on each $g_i$ (eq.(16)'s paragraph).

Why should replacing $v_i$ with $x$ satisfying eq.(16) (that is, $\lvert g_i(x-v_j)\rvert>\frac{3}{2}\lvert g_i(v_i-v_j\rvert$) cause $vol(v_0,\dots,v_n)=\det(v_i-v_0)_{i\in[n]}$ to increase by a factor of $\frac{3}{2}$? I guess I'm not seeing exactly what about this choice of $g_i$ makes it so desirable to optimize over.

Is there a determinant identity that I'm missing that solves this? It seems that were $v_i$ to be replaced by $v_i=x$, the angles between some vectors could become quite slim, causing the determinant to perhaps even decrease.

Thanks in advance.


Your Answer

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

Browse other questions tagged or ask your own question.