3
$\begingroup$

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.

$\endgroup$

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.