# Showing an equivalence of $|\langle \textbf{z}, x \rangle| < R$

Let us consider the following event: for a fixed $$x \in \mathbb{R}^n$$ with $$\|x\|=1$$ and $$\textbf{z} \sim N(0,\textbf{I}_n)$$, $$A_x(\textbf{z}) = \{\exists w \in \mathbb{R}^n \text{ such that } \|w - \textbf{z}\| \le R, \text{ and } \text{sign}(\langle w, x\rangle) \ne \text{sign}(\langle \textbf{z}, x\rangle) \}.$$ I am trying to show that $$A_x(\textbf{z}) \text{ happens } \iff |\langle \textbf{z}, x\rangle| < R.$$

($$\implies$$) This direction is readily done as follow. Suppose $$A_x(\textbf{z})$$ happens. Then there exists $$w \in \mathbb{R}^n$$ such that $$\|w - \textbf{z}\| \le R$$ and $$\text{sign}(\langle w, x\rangle) \ne \text{sign}(\langle \textbf{z}, x\rangle)$$. Therefore, $$R \ge \|w - \textbf{z}\| \ge |\langle (w - \textbf{z}), x\rangle | \ge |\langle \textbf{z}, x\rangle |$$ where the third inequality uses $$\text{sign}(\langle w, x\rangle) \ne \text{sign}(\langle \textbf{z}, x\rangle)$$.

However, I am not sure why the reverse direction is true. Here is my attempt.

($$\impliedby$$) Suppose $$R\ge |\langle \textbf{z}, x\rangle |$$. Then our goal is to find $$w \in \mathbb{R}^n$$ satisfying (i) $$\|w - \textbf{z}\| \le R$$ and (ii) $$\text{sign}(\langle w, x\rangle) \ne \text{sign}(\langle \textbf{z}, x\rangle)$$. I was trying to construct $$w$$ by setting $$w = -a\textbf{z}$$ for some positive constant $$a$$. By doing so, the condition (ii) is automatically satisfied. And I was hoping that (i) can be satisfied by carefully choosing $$a$$. However, this only works under the condition of $$\|\textbf{z}\| \le R$$, not $$|\langle \textbf{z}, x\rangle | \le R$$. This is becuase, by setting $$w = -a\textbf{z}$$, we have $$\|w - \textbf{z}\| = (1+a)\|\textbf{z}\|.$$ In order for this to be less or equal to $$R$$, $$a + 1 \le \frac{R}{\|\textbf{z}\|} \iff a \le \frac{R-\|\textbf{z}\|}{\|\textbf{z}\|}.$$ Since $$a$$ is positive, we need $$\|\textbf{z}\| < R$$.

You can simply let $$w=z-R\cdot \text{sign}(\langle z,x\rangle)x$$. Then we have that $$\|w-z\|=R\|x\|=R$$ and $$\langle w,x\rangle=\langle z,x\rangle-R\cdot\text{sign}(\langle z,x\rangle).$$ We can see that $$\langle w,x\rangle\langle z,x\rangle=|\langle z,x\rangle|^2-R\cdot |\langle z,x\rangle|\le 0$$ so $$\langle w,x\rangle$$ and $$\langle z,x\rangle$$ cannot be both positive or negative.