We set $L_n = \lfloor n^{1/3} \rfloor$, where $\lfloor t \rfloor$ denotes the integer part of a real number $t$. Let $x, y \in \{0,1\}^n$ such that $x \neq y$. Set for $z \in \mathbb{C}$, $A_{x,y}(z) = \sum_{k=0}^{n-1}(x_k - y_k)z^k$. a. Justify the existence of $\theta_0 \in \left[-\frac{\pi}{L_n}, \frac{\pi}{L_n}\right]$ such that $\left|A_{x,y}\left(e^{i\theta_0}\right)\right| \geq \frac{1}{n^{L_n - 1}}$. b. Prove that $$\sum_{j=0}^{n-1} \left|\mathbb{E}\left[O_j(x)\right] - \mathbb{E}\left[O_j(y)\right]\right| \cdot \left|\frac{e^{i\theta_0} - (1-p)}{p}\right|^j \geq \frac{p}{n^{L_n - 1}}$$ c. Justify the existence of an integer $j_n(x,y)$ such that $0 \leq j_n(x,y) \leq n-1$ and $$\left|\mathbb{E}\left[O_{j_n(x,y)}(x)\right] - \mathbb{E}\left[O_{j_n(x,y)}(y)\right]\right| \geq \frac{p}{n^{L_n}} \exp\left(-\frac{1-p}{2p^2} \cdot \frac{\pi^2}{L_n^2} n\right).$$
We set $L_n = \lfloor n^{1/3} \rfloor$, where $\lfloor t \rfloor$ denotes the integer part of a real number $t$. Let $x, y \in \{0,1\}^n$ such that $x \neq y$. Set for $z \in \mathbb{C}$, $A_{x,y}(z) = \sum_{k=0}^{n-1}(x_k - y_k)z^k$.
a. Justify the existence of $\theta_0 \in \left[-\frac{\pi}{L_n}, \frac{\pi}{L_n}\right]$ such that $\left|A_{x,y}\left(e^{i\theta_0}\right)\right| \geq \frac{1}{n^{L_n - 1}}$.
b. Prove that
$$\sum_{j=0}^{n-1} \left|\mathbb{E}\left[O_j(x)\right] - \mathbb{E}\left[O_j(y)\right]\right| \cdot \left|\frac{e^{i\theta_0} - (1-p)}{p}\right|^j \geq \frac{p}{n^{L_n - 1}}$$
c. Justify the existence of an integer $j_n(x,y)$ such that $0 \leq j_n(x,y) \leq n-1$ and
$$\left|\mathbb{E}\left[O_{j_n(x,y)}(x)\right] - \mathbb{E}\left[O_{j_n(x,y)}(y)\right]\right| \geq \frac{p}{n^{L_n}} \exp\left(-\frac{1-p}{2p^2} \cdot \frac{\pi^2}{L_n^2} n\right).$$