1 - Boolean functions and key concepts

Summary

In this first chapter, we set the stage for the book by presenting many of its key concepts of the book and stating a number of important theorems that we prove here.

Boolean functions

Definition 1.1 A Boolean function is a function from the hypercube Ω_n : = {−1, 1}ⁿ into either {−1, 1} or {0, 1}.

Ω_n is endowed with the uniform measure ℙ = ℙⁿ = (½δ₋₁ + ½δ₁)^⊗n and E denotes the corresponding expectation. Occasionally, Ω_n will be endowed with the general product measure but in such cases the p is made explicit. E_p then denotes the corresponding expectation.

An element of Ω_n is denoted by either ω or ω_n and its n bits by x₁, …, x_n so that ω = (x₁,…, x_n).

For the range, we choose to work with {−1, 1} in some contexts and {0, 1} in others, and at some specific places we even relax the Boolean constraint (i.e., that the function takes only two possible values). In these cases (which are clearly identified), we consider instead real-valued functions f: Ω_n → ℝ.

A Boolean function f is canonically identified with a subset A_f of Ω_n via A_f : = {ω : f(ω) = 1}.

Remark Often, Boolean functions are defined on {0, 1}ⁿ rather than Ω_n = {−1, 1}ⁿ. This does not make any fundamental difference but, as we see later, the choice of {−1, 1}ⁿ turns out to be more convenient when one wishes to apply Fourier analysis on the hypercube.