Abstract
For a function $f:\{−1,1\}^n\to \{−1,1\}$ the relationship between the sum of its linear Fourier coefficients $\hat{f}(i)$ (defined by $\hat{f}(i)≔\frac{1}{2^n}\sum_{x\in \{−1,1\}^n} f(x)x_i$ for $i=1,2,\ldots,n$ and $x=(x_1,\ldots,x_n)$) and its degree $d$ is a problem in theoretical computer science related to social choice. In that regard, in 2012, O’Donnell conjectured that $\sum_{i=1}^n \hat{f}(i)\leq d\binom{d-1}{\lfloor \frac{d-1}{2} \rfloor}2^{1-d}$. In 2020, Wang (Wang, 2020) proved that the conjecture is equivalent to a conjecture about cryptographic resilient Boolean functions and proved that the conjecture is true for every $n$, when $d=1$ and $d=n−1$. In this paper, we contribute theoretically to this problem by showing that if the conjecture is true for some specific relatively small value $n_0$, which depends on $d$, then it is valid for any $n\geq n_0$. In particular, we show that the conjecture is correct for every $n$, when $d=2$ and $d=3$. However, despite these promising results, we present a counterexample when $d=4$, and so the conjecture is not true in general.
dr. Sadmir Kudin
Teaching Assistant
