Proving the conjecture of O'Donnell in certain cases and disproving its general validity (Q2217489)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Proving the conjecture of O'Donnell in certain cases and disproving its general validity |
scientific article |
Statements
Proving the conjecture of O'Donnell in certain cases and disproving its general validity (English)
0 references
29 December 2020
0 references
For a binary function \(f\colon \{-1,+1\}^n \rightarrow \{-1,+1\}\), one defines the Fourier coefficient of \(f\) at the subset \(S\subseteq\{1,n\}\) by: \[ \widehat f(S) = \frac 1{2^n}\sum_{x\in \{-1,+1\}^n } f(x)\prod_{s\in S} x_s \] so that inversion formula works: \[ f(x) = \sum_{S\subseteq\{1,n\} } \widehat f(S) \prod_{s\in S} x_s. \] the degree of \(f\) is \(\max_{\widehat f(S)\not=0}{\vert S \vert }\). In a note of 2012, O'Donnell conjecture the inequality: \[ \sum_{i=1}^n \widehat f(\{i\} ) \leq d \binom{d-1}{\lfloor\frac{d-1}2\rfloor} 2^{1-d} \] for a binary function of degree \(d\). The inequality is correct for \(d=1\) and \(d=n-1\) (Q.~ Wang, 2020). In the paper under review, the authors use the notion of resilience of Boolean functions to examine the validity of that conjecture. They prove the inequality is correct in the case of the degree less than 4, and providing a counter example for the degree \(4\) in 7 variables.
0 references
Boolean functions
0 references
O'Donnell's conjecture
0 references
resiliency
0 references
Walsh transform
0 references
0 references