I encounter the following question.

$\textbf{Problem}$: For almost all Matrix $M\in\mathcal M_{m\times n}(\mathbb R),$ all $y\in \mathbb R^m$ and any $N$, small $\epsilon>0$, there exists a constant $C$, depending on $\epsilon$ and $M$, and $p\in \mathbb Z^m$ , $q\in \mathbb Z^n$ satisfying $|q|<N$, such that the following inequality holds

$$|Mq-p-y|\leq N^{-(\frac{n}{m}-\epsilon)}. $$

This can be considered as a quantitative version of Kronecker theorem https://en.wikipedia.org/wiki/Kronecker%27s_theorem

The case m=1 is known to be true. A closely related result is http://arxiv.org/abs/1512.00679, but still quite different.

  • $\begingroup$ And what exactly is your difficulty with the standard proof via trigonometric sums? I tried to make a back of envelope computation and it seemed to work just fine but I surmise you've tried it too, so am I missing some subtlety? $\endgroup$ – fedja Jan 7 '16 at 3:37
  • 1
    $\begingroup$ Thanks fedja. I am not an expert of number theory. Could you please let me know your computation? Thanks. $\endgroup$ – John Galt Jan 7 '16 at 4:23
  • $\begingroup$ Done. Feel free to ask questions if any step gives you trouble :-) $\endgroup$ – fedja Jan 7 '16 at 15:24

As far as I understand the question, we need to consider matrices $M=(m_{ij})$ with entries in $[0,1]$ (the integer part does not matter), look at the vectors of $Mq$ modulo $1$ again with $\|q\|_\infty\le N$ (the exact choice of the norm is not important because it merely changes the constant in the final answer) and to show that one of them is $r$-close (again, in the $\ell^\infty$ norm) to a given vector $y$ with $r$ about $N^{\varepsilon}N^{-n/m}$.

Pick up a smooth function $\psi(t)$ supported on $[-1,1]$ and infinitely smooth there such that $\int\psi=1$. Put $\Psi(x)=r^{-m}\prod_{i=1}^m\psi(x_i/r)$ and consider the periodic function $\Phi(x)=\sum_{p\in\mathbb Z^m}\Psi(x-p-y)$. Then we need to show that there exists $q$ with $\Phi(Mq)\ne 0$ unless $M$ belongs to some exceptional set of matrices of measure $N^{-\delta}$, say (then, considering $N=2^k$ and using Borel-Cantelli, we'll arrive at the statement equivalent to the desired one).

Decompose $\Phi(x)$ into its Fourier series $\sum_{\ell\in\mathbb Z^m}c_\ell e(\ell\cdot x)$ where, as usual, $e(t)=e^{2\pi i t}$ and notice that all $|c_\ell|\le 1$, $c_0=1$, and $c_\ell$ are extremely small and decay fast for $\|\ell\|_\infty>r^{-\beta}$ with any fixed $\beta>1$ (the exact condition we need is that the sum of $|c_\ell|$ with $\ell$ in that range is much less than $1$). Now just consider the sum $\sum_{q:\|q\|_\infty\le N}\Phi(Mq)$ and treat each exponent separately. When $\ell=0$, we will get $N^n$. When $\|\ell\|_\infty>r^{-\beta}$, we will get something much smaller even if we add all those terms up. It remains to investigate the sum $$ \sum_{\ell:0<\|\ell\|_{\infty}\le r^{-\beta}}\left|\sum_q e(\ell\cdot Mq)\right|\,. $$ To this end, we'll just estimate its average over $M$. Passing $M$ to $\ell$, we and using the fact that $\left|\sum_q e(z\cdot q)\right|\le C\prod_{j=1}^n\min(N,\|z\|^{-1})$, where $\|z\|$ is the distance from $z$ to the nearest integer, we immediately get the bound $C\log^n N$ for the average of each term in our sum. Thus, the total average is at most $Cr^{-\beta m}\log^n N$, so outside a set of matrices of measure $N^{-\delta}$, we have the whole sum not exceeding $CN^\delta r^{-\beta m}\log^n N$, which is still below $N^n$ if we have $r=N^{\varepsilon}N^{-\frac nm}$ and choose $\beta$ and $\delta$ sufficiently close to $1$ and $0$ respectively depending on $\varepsilon$.


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.