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,\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.

Publication
Discrete Applied Mathematics
Sadmir Kudin
Sadmir Kudin
Young Researcher
dr. Enes Pasalic
dr. Enes Pasalic
Full Professor, Head of the center

Related