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
    0 references
    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

    Identifiers