A Boolean Fourier expansion expresses a real-valued function on the sign set 
as a linear combination
of the functions 
, indexed by subsets 
.
For a random variable 
with the discrete
uniform distribution on this set, the expansion is
 |
(1)
|
where its coefficients are
![f^^(S)=E[f(X)chi_S(X)].](/images/equations/BooleanFourierExpansion/NumberedEquation2.svg) |
(2)
|
The functions 
form an orthonormal basis
for the inner product ![E[f(X)g(X)]](/images/equations/BooleanFourierExpansion/Inline6.svg)
(O'Donnell 2021, pp. 24-25).
If 
is a nonconstant Boolean function with values
in 
,
its polynomial degree is the largest 
with 
. This is the total degree
of its representing multilinear polynomial
over 
.
Its average sensitivity is (O'Donnell 2021,
p. 52)
 |
(3)
|
For example, 
has just one nonzero coefficient,
,
and has polynomial degree and average
sensitivity equal to 2. The Gopalan-Servedio
conjecture concerns the coefficients 
.
