Proving the conjecture of O’Donnell in certain cases and disproving its general validity

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,\dots ,n$ and $x=(x_1,\dots ,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)\le d(\genfrac{}{}{0ex}{}{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\ge 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

Assistant with PhD

dr. Enes Pasalic

Full Professor, Head of the center