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 
.
