4
$\begingroup$

Let $\alpha_1, \ldots, \alpha_n$ be $\mathbb{Q}$-linearly independent real numbers. I want to show that for all $x_1, \ldots, x_n\in\mathbb{Z}$, $|x_i|<N$ we have some lower bound for $\left|\sum x_i\alpha_i\right|$. For how many $n$ and what range for $N$ can this be done in reasonable time? Should I use specialized software or standard computer algebra packages?

Note that I am not interested in the asymptotic behaviour or questions like NP-completeness, but in actual numbers. Moreover I do not want to find small values for linear forms, I want to prove that no extremely small values exist.

$\endgroup$
3
  • $\begingroup$ Well in many reasonable assumptions on the $\alpha_{i}$ you can use Baker's theorem. Probably for the $2$-dimensional case, the best results are in the Sarnak-Ubis paper (the so-called "Discrete Dani theorem"), but unfortunately, the multidimensional version of Sarnak-Ubis is yet to be written (it's missing some ingredients to be developed, most importantly equidistribution of non-maximal horospherical group orbits). $\endgroup$
    – Asaf
    Jun 3, 2016 at 11:47
  • $\begingroup$ The problem is that Baker gives only non-trivial bounds for $x_i$ above a rather large threshold, and to obtain a complete classification you somehow have to search the space below this threshold. In two dimensions you can apply continued fractions, which usually takes about as much time as the high-precision computation of $alpha_1, alpha_2$, which is fine. However, in higher dimensions you need something like LLL, and things start to get messy. $\endgroup$ Jun 3, 2016 at 20:57
  • $\begingroup$ Can you restate the problem as an en.wikipedia.org/wiki/Integer_programming? There are many free and open source packages that are extremely fast. $\endgroup$
    – yberman
    Mar 19, 2017 at 14:37

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.