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.

Improve this question
$\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
    Commented 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$
    – Jan-Christoph Schlage-Puchta
    Commented 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
    Commented Mar 19, 2017 at 14:37

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .