My question pertains to this paper by Terence Tao and Van Vu, https://arxiv.org/abs/math/0703307
Both my questions pertain to the argument presented in this paper in its section 6 (page 5). We are looking at a $ n-$ dimensional square random matrix $ M_n$ satisfying the conditions stated through Definitions 2.15, Definition 2.17 and Theorem 2.18 on page 3.
Now we are saying that lets assume the existence of a unit vector $ v \in \mathbb{R}^n$ such that for some $ B >10$ we have, $ \Vert M_n v\Vert < n^{-B}$ . The vector $ \tilde{v}$ is created by truncating each coordinate of $ v$ to the nearest multiple of $ n^{-B-2}$ . So if I understand this correctly then we have that for each coordinate $ i$ , $ \vert v_i – \tilde{v}_i\vert \leq \frac{1}{2n^{B+2}}$ . This is now supposed to imply a number of things which arent clear to me,
-
The paper claims, $ 0.9 \leq \Vert \tilde{v}\Vert \leq 1.1$ . Why?
If I just think directly then we have, $ \Vert \tilde{v}\Vert \leq \Vert v + (\tilde{v}-v)\Vert \leq \Vert v\Vert + \sqrt{n} \frac{1}{2n^{B+2}} = 1 + \frac{n^{-B-\frac{3}{2}}}{2}$ .For this to match the claim we need, $ \frac{n^{-B-\frac{3}{2}}}{2} = 0.1$ . But this is now incompatible with the initial statement that we need $ B>10$ . What am I missing?
-
The paper claims that the following is also true that, $ \Vert M_n \tilde{v}\Vert \leq 2n^{-B}$ . Why?
Just as above if I again think just directly then we have, that $ \Vert M_n \tilde{v}\Vert = \Vert M_n(v+(\tilde{v}-v))\Vert \leq \Vert M_n v \Vert + \Vert M_n (\tilde{v}-v)\Vert \leq n^{-B} + \Vert M_n \Vert \frac{n^{-B-\frac{3}{2}}}{2}$ . One way this can be compatible with the claim is if we have, $ \Vert M_n \Vert \leq 2n^{1.5}$ .
One might now go back to the “boundedness” part of Definition 2.15 and the first bullet point of Theorem 2.18 on page 3 to see that with probability $ 1$ the entries of the matrix $ M_n$ are integers bounded as $ n^C$ for some constant $ C>0$ . This gives by Frobenius norms, $ \Vert M_n \Vert \leq \Vert M_n \Vert_F \leq n^{1+C}$ . So for compatibility with the previous bound we need, $ n^{1+C} \leq 2n^{1.5}$ . But then such an equation is now an upperbound on the constant $ C$ and that is not something that Theorem 2.18 enforced. What am I missing?
