Probability of two Boolean functions being equal expressed in terms of the maximum Fourier coefficient

Question

This paper by Maslov et al. uses that the probability of two $n$-bit Boolean functions $l(x)$ and $g(x)$ being equal is bound in terms of $\hat{g}_\text{max}$, the largest Fourier coefficient of $g(x)$, in the following way (between Eq. (4) and (5) of the Methods section at the end of the paper): \begin{equation} \Pr[l(x)=g(x)]\leq\frac{1}{2}(1+\hat{g}_{\text{max}}). \end{equation} Here, the binary Fourier transform of the Boolean function $g : \{0,1\}^n\mapsto\{0,1\}$ is defined as (with $x\cdot y$ the bitwise inner product between $n$-bit strings $x,y\in\{0,1\}^n$) \begin{equation} \hat{g}(y)=2^{-n}\sum_{x\in\{0,1\}^n}(-1)^{x\cdot y+g(x)}, \end{equation} and $\hat{g}_\text{max}$ is defined as \begin{equation} \hat{g}_\text{max}=\max_{y\in\{0,1\}^n}|\hat{g}(y)|. \end{equation} I've tried understanding this myself, as well as going over literature concerning the Boolean Fourier transform (as, for example, these texts by Ryan O'Donnell (1 and 2) and Ronald de Wolf), but I haven't been able to see why the inequality holds. I got as far as realizing that the Fourier transform of $g(x)$ allows for the following relations: \begin{equation} g(x)=\frac{1}{2}\bigg(1-\sum_{y\in\{0,1\}^n}\hat{g}(y)(-1)^{y\cdot x}\bigg)\leq\frac{1}{2}(1+2^n\hat{g}_\text{max}). \end{equation} This, however, does not seem to be particularly useful. Any nudge in the right direction would be hugely appreciated!

Answer 1

As the RHS is independent of $l(x)$, the statement should only be true if $l(x)$ lies in a restricted subset of Boolean functions. I cannot read the paper linked, but I suspect it is intended to restrict $l(x)$ to linear functions, i.e. $l(x)=l_y(x)=x\cdot y$.

In that case it is easy to show $$Pr\left[l_y(x)=g(x)\right] = \frac12 \left(1 + \hat{g}(y)\right)$$ and the result follows by taking the absolute value, then the triangle inequality, then the max over all $y$.