Skip to content

Instantly share code, notes, and snippets.



Last active Aug 2, 2019
What would you like to do?
This is a translation into linear maps of Knuth's ``computational'' reformulation [1] of Huang's proof of the Sensitivity Conjecture [2].
Let $(V_n)_{n \ge 0}$ be the sequence of $\RR$-vector spaces defined inductively by
V_0 = \RR, \quad V_{n+1} = V_n \oplus V_n.
Each space $V_n$ has an obvious basis $(e_p)_{p \in Q^n}$ indexed on $Q^n = \bool^n$.
Let $(\varepsilon_p : V_n \to \RR)_{p \in Q^n}$ be the dual linear functionals.
Let $f_n : V_n \to V_n$ be the linear map defined inductively by
f_0 = 0, \quad f_{n+1}(v, w) = (f_n v + w, v - f_n w).
By induction $f_n^2 v = n v$.
Moreover $|\varepsilon_q (f_n e_p)|$ is 1 if $p$ and $q$ are adjacent vertices of the hypercube graph $Q^n$ (which we denote by $p \sim q$) and 0 otherwise.
Now let $g_n : V_{n-1} \to V_n$ be defined by
g_n v = (f_{n-1} v + \sqrt n v, v).
Then $g_n$ is injective, so its image is a subspace of $V_n$ of dimension $\dim V_{n-1} = 2^{n-1}$.
Furthermore for any $w = g_n v$ in this image we have
f_n w
& = f_n (f_{n-1} v + \sqrt n v, v) \\
& = (f_{n-1} f_{n-1} v + \sqrt n f_{n-1} v + v, f_{n-1} v + \sqrt n v - f_{n-1} v) \\
& = (\sqrt n f_{n-1} v + n v, \sqrt n v) \\
& = \sqrt n w.
Let $H$ be a subset of $Q^n$ of cardinality at least $2^{n-1} + 1$.
The restriction of the basis of $V_n$ to $H$ spans a subspace $W$ of $V_n$ of dimension at least $2^{n-1} + 1$.
Since the image of $g_n$ has dimension $2^{n-1}$ and $2^{n-1} + 1 + 2^{n-1} > 2^n$, we can find some nonzero vector $y$ belonging to both $W$ and the image of $g_n$, so that $f_n y = \sqrt n y$.
Now write $y = \sum_{p \in H} y_p e_p$ and let $q \in H$ be an index with $|y_q|$ maximal.
|\sqrt n y_q|
& = |\varepsilon_q (\sqrt n y)| \\
& = \big|\varepsilon_q \big(f_n \big(\sum_{p \in H} y_p e_p \big)\big)\big| \\
& \le \sum_{p \in H} |\varepsilon_q (f_n e_p)| |y_p| \\
& = \sum_{p \in H, p \sim q} |y_p| \\
& \le \sum_{p \in H, p \sim q} |y_q| \\
& = |\{\,p \in H \mid p \sim q\,\}| |y_q|
and therefore $q$ has at least $\sqrt n$ neighbors in $H$.
[1]: \url{}
[2]: \url{}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment