3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ My answer shows that this question is fundamentally misguided when $n \ge 3$. Why would you vote it down and then edit your question without taking it into account? You can't just vote away the truth you know. $\endgroup$ – A million tiny pieces Jun 13 at 20:52
  • 1
    $\begingroup$ I have had similar issues in the past. The post represents a moving target, discussions which might document a proper evolution to a good question are elided, answers which shed light on issues are deleted along with the question, a revised question which might (or might not) be headed in a good direction arises, and (on my part) a general air of frustration arises. I have (with some small regret) adopted a policy of non involvement with such posts, as this behaviour seems to disregard the efforts I put into the question. I recommend such a policy here. This is too serious for a signature. $\endgroup$ – Gerhard Paseman Jun 14 at 21:03
  • 1
    $\begingroup$ I did not see the entire comment exchange but I did see a comment where you accused "a million tiny pieces" of being incoherent and you seem to have acknowledged voting the answer down. Since that answer was apparently correct without any edits required, one might hazard a guess that the reason for those comments being deleted was a million tiny pieces being generous to you not looking like a fool. $\endgroup$ – Pound Sterling Jun 14 at 21:51
  • 1
    $\begingroup$ Given that all the subsequence versions have had problems it seems less like a "typo" and more that that after several bites at the apple there is nothing here. I would recommend that other users follow @GerhardPaseman's advice since I don't see what anyone has to gain from futher interaction on this question. $\endgroup$ – Pound Sterling Jun 14 at 21:54
  • 1
    $\begingroup$ What I really want is certain portions of the past not to have happened. I don't expect you to change the past. You can change your behaviour on this forum. If you want my renewed involvement in your questions, I am willing to try on your next question provided we agree that both of us follow certain rules on the handling of this next question. I will not detail the rules now. I will say that the intent of the rules is to acknowledge and preserve efforts toward changing the question for the better. $\endgroup$ – Gerhard Paseman Jun 14 at 23:17
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I do not think the answer is perfect. Expected L infinity distance between plane and hypercube is not unparametrizable and because of all the hullabullooo going on here I accept this being wary of the moderator taboo. $\endgroup$ – Turbo Jun 14 at 1:03
  • 1
    $\begingroup$ I don't know what "moderator taboo" signifies, but FWIW, one thing we've noticed is the huge number of self-deleted posts coming from this and allied accounts, which (cumulatively speaking) is tantamount to self-vandalism, and is frustrating to users who are trying to interact. $\endgroup$ – Todd Trimble Jun 14 at 23:34
  • $\begingroup$ @ToddTrimble are you referring to the account behind this answer, or the account of the OP? $\endgroup$ – Yemon Choi Jun 15 at 13:45
  • $\begingroup$ @YemonChoi I meant Turbo. $\endgroup$ – Todd Trimble Jun 15 at 15:17
1
$\begingroup$

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
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks corrected. $\endgroup$ – Turbo Jun 14 at 18:24
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ok. ,,, but we are looking at $\infty$ norm gap between best bounded plane and a point in box. Is it that easy? In fact $A=B=0$ (as in your previous answer) gives $O(T^2)$. $\endgroup$ – Turbo Jun 14 at 20:46
  • $\begingroup$ may be some other user141920's answer. $\endgroup$ – Turbo Jun 14 at 21:12
  • $\begingroup$ Yes it is easy --- after scaling, it is the same as saying that a vector with $\|x\|_{\infty} < 1$ is some at least some constant distance away from most planes. $\endgroup$ – user141939 Jun 14 at 21:32
  • 1
    $\begingroup$ I don't understand your comment, but the point of my answer is that for all but $\epsilon$ choices of the parameter $\|aA+bB-c\| > \delta T^2$ so the probability is zero. $\endgroup$ – user141939 Jun 14 at 22:59
  • 1
    $\begingroup$ Your bound is $T^{2(n-1)/n + \epsilon}$ ($=o(T^2)$ for $n \ge 3$) --- are you seriously changing the question AGAIN to be a constant times $T^2$? $\endgroup$ – user141939 Jun 14 at 23:17

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.