2
$\begingroup$

Let $\alpha_1, \alpha_2, \dots$ be an infinite sequence of real numbers such that any finite subset is linearly independent over $\mathbb{Q}$. Let $f(N)$ be the number of tuples $(m_1, \dots, m_N)$ with $m_i \in \mathbb{Z}$, $|m_i| \leq N$. for which $$\left|\sum_{i=1}^{N} m_i \alpha_i \right|< \frac{1}{N^{100}}.$$

(where 100 could be your favorite constant, or maybe something sublinear if that's not possible). Is there any known way to put an asymptotic upper bound on $f(N)$ better than the trivial one of $(2N+1)^N$?

For concreteness (or if it makes the question possible to answer!) you could take the $\alpha_i$ to be the square roots of square free integers (ordered however you like, although I do have a particular ordering in mind). If that doesn't work, any effectively computable $\alpha_i$ would be welcome.

It seems that one might be able to say something of the sort using Evertse's quantitative subspace theorem but it isn't really clear to me how. Any pointers (or even conjectures) here would be greatly appreciated!

EDIT: I just noticed something, though it's not super useful: If one takes $\alpha_1 = 1$, $\alpha_k = \log p_k$ ($p_k$ the $k$th prime), then for large $N$, for each $i$ it cannot be the case that just $m_1$ and $m_i$ are non-zero by a quantitative Baker's theorem. So we have at least $f(N) \leq (2N + 1)^N - (N-1)(2N+1)^2$. This isn't super useful for me since this has the same asymptotics as the trivial bound, but might be helpful to think about.

$\endgroup$
  • 1
    $\begingroup$ Interesting question, but you probably want to specify it more, otherwise one can say that $f(N)\leq(2N+1)^N$ is a trivial upper bound. $\endgroup$ – GH from MO Mar 18 '17 at 16:51
  • 1
    $\begingroup$ Well, if $\alpha_1=1$, then for any choice of $m_2,\dots,m_N$ there is at most one good choice of $m_1$, so in this case $f(N)\leq (2N+1)^{N-1}$. This is still trivial, of course. $\endgroup$ – GH from MO Mar 18 '17 at 17:49
3
$\begingroup$

There is a lower bound $f(N)>N^{N-101}$. To see this suppose without loss that $\alpha_1=1$. Then consider all the $N^{N-1}$ values of $\sum_{i=2}^{N} m_i\alpha_i\bmod 1$ with $|m_i|\leq N/2$. There is an interval of length $N^{-100}$, which contains at least $N^{N-101}$ of these values, and taking differences we obtain $N^{N-101}$ sums $\left|\sum_{i=2}^{N} (m_i-m'_i)\alpha_i\bmod 1\right|<N^{-100}$ with $|m_i-m_i'|\leq N$.

In general there is a matching upper bound. Suppose that your sequence has the property that the discrepancy of $\{\sum_{i=2}^{1000} m_i\alpha_i\bmod 1: |m_i|<N\}$ is $\mathcal{O}(N^{-100})$. Then no matter how you choose $m_{1001}, \ldots, m_N$, the first 1000 coefficients are determined in $\ll N^{899}$ ways, so you get an upper bound of magnitude $(2N+1)^{N-101}$. So there is a matching upper bound for almost all sequences. I don't know about a concrete example, but there is a vast literature on discrepancy, and linear combinations of irrational numbers is sufficiently natural so that someone has probably treated it somewhere.

$\endgroup$
  • $\begingroup$ Thanks, this is very helpful! One thing I don't quite see though is how you handle the fact that in these sums with $< N^{-100}$ fractional part, the integer part may be on the order of $N^2$ ($N$ terms in the sum times a maximum value of $N$ for $|m_i - m_i'|$) and even really $N^3$ if we assume that $|\alpha_n|$ is on the order of $n$. In this case we won't be able to cancel out the integer part since $|m_1|$ can be at most $N$. I guess you could run this argument with $|m_i| < N^{1/3}$ and get a similar lower bound, but would there be a corresponding upper bound? $\endgroup$ – Izaak Meckler Mar 19 '17 at 17:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.