5
$\begingroup$

This is problem 1(e) from Homework 1 of the course about Analysis of Boolean functions at CMU in 2012 as well as problem 1.1(n) on p.34 of Ryan O'Donnell's Analysis of Boolean Functions.

Compute the Fourier expansion of the hemi-icosahedron function $HI: \{-1,1\}^6 \to \{-1,1\}$, defined as follows: $HI(x)$ is 1 if the number of $1$'s in $x$ is $1,2,$ or $6$. $HI(x)$ is $-1$ if the number of $-1$'s is $1, 2,$ or $6$. Otherwise, $HI(x)$ is $1$ if and only if one of the ten facets of the following diagram has all three of its vertices $1$:

enter image description here

My question: Is there a quicker way to see that the solution should be the answer I got below by brute force? I get how to calculate the Fourier expansion by brute force in general, but I don't feel like I have been very successful at trying to exploit symmetries in special cases like these.

My attempt at a solution

I wasn't sure how to predict how the coefficients might cancel out nicely, and I didn't want to feel dumb by making no attempt, so I did it by brute force. What I got as the final result was: $$\frac{1}{4}[x_3x_4x_6 + x_3x_4x_5 + x_2x_5x_6 + x_2x_3x_5 + x_2x_4x_6 + x_1x_5x_6 + x_1x_4x_5 + x_1x_3x_6 + x_1x_2x_3 + x_1x_2x_4 - x_6 -x_5 -x_4 -x_3 +\frac{1}{2} -\frac{1}{2}x_1 -\frac{1}{2}x_2 +\frac{1}{2}x_1x_2 ] $$ This doesn't give the right answers and seems pretty obviously to be the result of an algebra mistake (which seems kind of inevitable when attempting to solve such a large problem by brute force using pen and paper).

So, basically arguing by wanting my answer to look less ugly, and hoping that this would work, I guessed that the actual answer, from which the one I calculated deviates for terms of degree $\le 1$, is the following: $$\frac{1}{4}[x_3x_4x_6 + x_3x_4x_5 + x_2x_5x_6 + x_2x_3x_5 + x_2x_4x_6 + x_1x_5x_6 + x_1x_4x_5 + x_1x_3x_6 + x_1x_2x_3 + x_1x_2x_4 - x_6 -x_5 -x_4 -x_3 -x_2 - x_1] $$

This actually seems to work for all of the inputs I have tested. Basically it seems like there is a degree three term for each of the ten facets of the hemi-icosahedron, plus a correction term for each of the six variables for some reason. But why or how should I have predicted this result?

$\endgroup$
  • 3
    $\begingroup$ It's easy to see that the function is self-dual (i.e. f(x)=-f(-x)). Ex. 3 from the same homework yields that terms of even degree should be zero. So, it is enough to compute terms of degree 1,3 and 5. Don't know how to do it without bruteforce. $\endgroup$ – Yuri Kombarov Aug 8 '16 at 12:38
  • $\begingroup$ Well the fact that it is self-dual is a big help already -- I appreciate your insight. $\endgroup$ – Chill2Macht Aug 8 '16 at 14:15
  • 3
    $\begingroup$ If you restrict the input to $x$ with three $+1$'s, then you can write $HI$ as $-1$ plus a sum of indicators, one for each facet of an actual icosahedron (not just the facets in the drawing), where each facet's indicator indicates that all three of its incident vertices are $+1$. The insight there is that when the input has three $+1$'s, there are exactly zero or exactly two facets of the icosahedron that have three $+1$'s incident to them. I suspect similar reasoning will lead to a fairly nice solution, since the others cases where the number of $+1$'s is fixed are also easily characterized. $\endgroup$ – Andrew Morgan Aug 9 '16 at 6:17
  • 2
    $\begingroup$ Note that HI is a property of the hemi-icosohedron graph invariant of graph isomorphisms. We can use this to obtain other symmetries of the function from swapping coordinates. The discrete rotations of the hemi-icosohedron map a singleton to any other singleton, so all Fourier coefficients of degree 1 are equal, and map any set of 5 elements to any other set of 5 elements, so all Fourier coefficients of degree 5 are equal. Finally, the rotations map any triangle to any other triangle, and any `non triangle' to any non-triangle, so there are really only 4 different coefficients to compute. $\endgroup$ – Jacob Denson Feb 27 '17 at 3:00
  • 3
    $\begingroup$ Also, we can cheat even further by using the fact the sum of the fourier coefficients squared is 1, so we can calculate the coefficients of degree 1 and 3, and then notice that the squares of these coefficients sum up to one, hence the coefficients of degree 5 vanish. $\endgroup$ – Jacob Denson Feb 27 '17 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.