This is a very short introductory survey of graph-theoretic properties of Boolean functions.
I don’t know who first studied Boolean functions for their own sake. However, the study of Boolean functions from the graph-theoretic perspective originated in Anna Bernasconi‘s thesis. More detailed presentation of the material can be found in various places. For example, Bernasconi’s thesis (e.g., see [BC]), the nice paper by P. Stanica (e.g., see [S], or his book with T. Cusick), or even my paper with Celerier, Melles and Phillips (e.g., see [CJMP], from which much of this material is literally copied).
For a given positive integer , we may identify a Boolean function
with its support
For each , let denote the set of complements , for , and let denote the complementary Boolean function. Note that
where denotes the complement of in . Let
denote the cardinality of the support. We call a Boolean function even (resp., odd) if is even (resp., odd). We may identify a vector in with its support, or, if it is more convenient, with the corresponding integer in Let
be the binary representation ordered with least significant bit last (so that, for example, ).
Let denote the $2^n\times 2^n$ Hadamard matrix defined by , for each such that . Inductively, these can be defined by
The Walsh-Hadamard transform of is defined to be the vector in whose th component is
where we define as the column vector where the th component is
A Boolean function of three variables cannot be bent. Let be defined by:
This is simply the function . It is even because
Here is some Sage code verifying this:
sage: from sage.crypto.boolean_function import * sage: f = BooleanFunction([0,1,0,1,0,1,0,1]) sage: f.algebraic_normal_form() x0 sage: f.walsh_hadamard_transform() (0, -8, 0, 0, 0, 0, 0, 0)
(The Sage method walsh_hadamard_transform is off by a sign from the definition we gave.) We will return to this example later.
Let be the Cayley graph of :
We shall assume throughout and without further mention that so has no loops. In this case, is an -regular graph having connected components, where
For each vertex , the set of neighbors of is given by
where is regarded as a vector and the addition is induced by the usual vector addition in . Let be the adjacency matrix of , so
Returning to the previous example, we construct its Cayley graph.
First, attach afsr.sage from [C] in your Sage session.
sage: flist = [0,1,0,1,0,1,0,1] sage: V = GF(2)ˆ3 sage: Vlist = V.list() sage: f = lambda x: GF(2)(flist[Vlist.index(x)]) sage: X = boolean_cayley_graph(f, 3) sage: X.adjacency_matrix() [0 1 0 1 0 1 0 1] [1 0 1 0 1 0 1 0] [0 1 0 1 0 1 0 1] [1 0 1 0 1 0 1 0] [0 1 0 1 0 1 0 1] [1 0 1 0 1 0 1 0] [0 1 0 1 0 1 0 1] [1 0 1 0 1 0 1 0] sage: X.spectrum() [4, 0, 0, 0, 0, 0, 0, -4] sage: X.show(layout="circular")
In her thesis, Bernasconi found a relationship between the spectrum of the Cayley graph ,
(the eigenvalues of the adjacency matrix ) to the Walsh-Hadamard transform . Note that and are related by the equation where . She discovered the relationship
between the spectrum of the Cayley graph of a Boolean function and the values of the Walsh-Hadamard transform of the function. Therefore, the spectrum of , is explicitly computable as an expression in terms of .
[BC] A. Bernasconi and B. Codenotti, Spectral analysis of Boolean functions as a graph eigenvalue problem, IEEE Trans. Computers 48(1999)345-351.
[CJMP] Charles Celerier, David Joyner, Caroline Melles, David Phillips, On the Hadamard transform of monotone Boolean functions, Tbilisi Mathematical Journal, Volume 5, Issue 2 (2012), 19-35.
[S] P. Stanica, Graph eigenvalues and Walsh spectrum of Boolean functions, Integers 7(2007)\# A32, 12 pages.
Here’s an excellent video of Pante Stanica on interesting applications of Boolean functions to cryptography (30 minutes):