Details from the end of Lecture 5

Many thanks to Daniel Golovin for providing the Book proof of $\mid S\mid (1-\delta {)}^{\mid S\mid -1}\le 1/\delta$ for each $\mid S\mid =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 $\mid S\mid$. If $i\le \mid S\mid$ then certainly $(1-\delta {)}^{\mid S\mid -1}\le (1-\delta {)}^{i-1}$. Sum this fact over $i=1...\mid S\mid$ to conclude $\mid S\mid (1-\delta {)}^{\mid S\mid -1}\le \sum _{i=1}^{\mid S\mid }(1-\delta {)}^{i-1}$. But $\sum _{i=1}^{\mid S\mid }(1-\delta {)}^{i-1}\le \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\left(ax\right)\cdot bf\left(by\right)\cdot cf\left(cz\right)=1$", which is equivalent to $f\left(ax\right)f\left(by\right)f\left(cz\right)=abc$. Now if $f$ is constant then so is $f\left(ax\right)f\left(by\right)f\left(cz\right)$, 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 ${}_2$ rather than $\{-1,1\}$).