Details from the end of Lecture 5

Many thanks to Daniel Golovin for providing the Book proof of $|S|(1-\delta)^{|S|-1} \leq 1/\delta$ for each $|S| = 0, 1, ...$, the claim we needed to show that any function has at most $1/\epsilon \delta$ variables with $(1-\delta)$-attenuated influence at least $\epsilon$. His proof:

Fix any $|S|$. If $i \leq |S|$ then certainly $(1-\delta)^{|S| - 1} \leq (1-\delta)^{i - 1}$. Sum this fact over $i = 1...|S|$ to conclude $|S| (1-\delta)^{|S| - 1} \leq \sum_{i=1}^{|S|} (1-\delta)^{i-1}$. But $\sum_{i=1}^{|S|} (1-\delta)^{i-1} \leq \sum_{i = 1}^{\infty} (1-\delta)^{i-1} = 1/\delta$.

---

Re one thing I mentioned at the end of class: The constant functions $1$ and $-1$ pass the Håst-Odd test with probability $1/2$ (for every $\delta$). The reason is, the test picks some $x$, $y$, and $z$, but then also picks random signs $a,b,c \in \{-1,1\}$ and tests "$af(ax) \cdot bf(by) \cdot cf(cz) = 1$", which is equivalent to $f(ax)f(by)f(cz) = abc$. Now if $f$ is constant then so is $f(ax)f(by)f(cz)$, and then $abc$ is a random sign, which agrees with the constant with probability $1/2$.

Note also that the "acceptance constraint" in the Håst-Odd test is either of the form "$v_{i_1} v_{i_2} v_{i_3} = 1$" or "$v_{i_1} v_{i_2} v_{i_3} = -1$". I.e., it's a 3-variable "linear" equation where the right-hand side is either "0" or "1" (if you go back and interpret bits as $\mathbb{F}_2$ rather than $\{-1,1\}$).