Approximately satisfying simultaneous vector linear diophantine equations?

Question

Pick three $a,b,c$ vectors in $\mathbb Z^n$ uniformly with $\max(\|a\|_\infty,\|b\|_\infty)<T$ and $\|c\|_\infty<T^2$ and an $\epsilon>0$.

Assume $a$ and $b$ are coordinatewise coprime (that is every $a_i$ and $b_i$ are coprime at every $i\in\{1,\dots,n\}$). Then do we always have such $A$ and $B$ of absolute value $O(T)$ at general $n$ such that $\|Aa+Bb-c\|_\infty<T^{2(n-1)/n+\epsilon}$ at large enough $n$?

This is the intuition.

Essentially there are $T^2$ choices for $A,B$ and there are $T^{\frac{(2n−2)}n+\epsilon}$ choices for every coordinate of $Aa+Bb-c$ and since there are $n$ coordinates we have $T^2T^{{2n−2}+n\epsilon}=T^{2n+n\epsilon}$ choices. However typically $Aa+Bb-c$ is of size $T^2$ and so typically there are $T^{2n}$ choices. If $\epsilon>0$ then the heuristic that $$\frac{\{\mbox{number of choices for A,B}\}\times\{\mbox{number of vectors with }\infty\mbox{ norm GAP < }T^{\frac{2(n-1)}n+\epsilon}\}}{\mbox{number of length n vectors with coordinates of size }T^2}$$ $$\asymp\frac{T^2T^{(\frac{2(n-1)}n+\epsilon)n}}{T^{2n}}=T^{n\epsilon}$$ holds which is at least $1$ if $\epsilon>0$ implies the $\infty$ norm bound looks plausible.

Also the original problem was what is the probability that the bound holds for uniformly random vectors $a,b,c$ in $\mathbb Z^n$ with $\max(\|a\|_\infty,\|b\|_\infty)<T$ and $\|c\|_\infty<T^2$ and an $\epsilon>0$?

At $n=1$ we get $\frac6{\pi^2}$.

Update The original writeup had a miscalculation. I missed a $2$ in exponent (that made the problem silly which some poster answered) and a related $T^2$ part (it was very clear from the denominator that the heuristic assumed a $T^2$ part on $c$ and I had not written it down in post) and it became WWIII and the accepted answer was for that original problem.

Answer 1

Even allowing $A$ and $B$ to be real numbers, the vectors $A a + B b$ will all lie in some fixed plane $P$. But then, if $n \ge 3$, for all but $\epsilon$ of the possible values of $c$ one will have

$$\| A a + B b - c \|_{\infty} \gg T$$

where the constant depends only on $\epsilon$. So for $n \ge 3$ the probability will be zero even for this easier problem. Since in the comments you admit you just made up the exponent, there is not much motivation to think about precise asymptotics.

Answer 2

For $n=1$ the probability that such $A$, $B$ exist is at least $$\frac6{\pi^2}\left(1+\frac18\right)=68\%$$ since it can happen at least in the following two disjoint ways:

• $a$ and $b$ coprime
• $a$, $b$, $c$ are all even, and $a/2$, $b/2$ are coprime

Answer 3

If $n = 1$, then (as $(a,b)=1$) there exist $A$ and $B$ such that $Aa+Bb-c = 0$, so $\|Aa+Bb-c\|_{\infty} = 0$.

If $n > 1$,take $A=B=0$ and then $\|Aa+Bb-c\|_{\infty} = \|c\|_{\infty} < T$, which beats the suggested bound by a considerable margin.

Answer 4

This version (version 4 I think?) seems to have the exactly the same problem as solved by a previous answer. For a given $a$ and $b$ the vectors $Aa+Bb$ will still lie in a plane $P$, and so now for all but $\epsilon$ values of $c$ it will be the case that $\|Aa+Bb-c\| \gg T^2$ for some implicit constant depending on $\epsilon$.

"turbo" seems confused. As he says in the comments "If you dont want to answer just go away." An ironic response to someone who has now answered his question twice. I will follow his advice.