Boolean Functions

Introduction

Let 𝔽₂^𝑛 be the vector space of dimension 𝑛 over the finite field with two elements. The vector space can also be endowed with the structure of the field, the finite field with 2^𝑛 elements, 𝔽_2^𝑛. A function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f : \mathbb{F}_2^n\rightarrow\mathbb{F}} is called a Boolean function in dimenstion 𝑛 (or 𝑛-variable Boolean function).

Given Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=(x_1,\ldots,x_n)\in\mathbb{F}_2^n} , the support of x is the set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle supp_x=\{i\in\{1,\ldots,n\} : x_i=1 \}} . The Hamming weight of 𝑥 is the size of its support (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_H(x)=|supp_x|} ). Similarly the Hamming weight of a Boolean function 𝑓 is the size of its support, i.e. the set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{x\in\mathbb{F}_2^n : f(x)\ne0 \}} . The Hamming distance of two functions 𝑓,𝑔 is the size of the set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{x\in\mathbb{F}_2^n : f(x)\neq g(x) \}\ (w_H(f\oplus g))} .

Representation of a Boolean function

There exist different ways to represent a Boolean function. A simple, but often not efficient, one is by its truth-table. For example consider the following truth-table for a 3-variable Boolean function 𝑓.

𝑥			𝑓(𝑥)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

Algebraic normal form

An 𝑛-variable Boolean function can be represented by a multivariate polynomial over 𝔽₂ of the form

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=\bigoplus_{I\subseteq\{1,\ldots,n\}}a_i\Big(\prod_{i\in I}x_i\Big)\in\mathbb{F}_2[x_1,\ldots,x_n]/(x_1^2\oplus x_1,\ldots,x_n^2\oplus x_n). }

Such representation is unique and it is the algebraic normal form of 𝑓 (shortly ANF).

The degree of the ANF is called the algebraic degree of the function, 𝑑°𝑓=max { |𝐼| : 𝑎_𝐼≠0 }.

Trace representation

We identify the vector space with the finite field and we consider 𝑓 an 𝑛-variable Boolean function of even weight (hence of algebraic degree at most 𝑛-1). The map admits a uinque representation as a univariate polynomial of the form

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=\sum_{j\in\Gamma_n}\mbox{Tr}_{\mathbb{F}_{2^{o(j)}}/\mathbb{F}_2}(A_jx^j), \quad x\in\mathbb{F}_{2^n}, }

with Γ_𝑛 set of integers obtained by choosing one element in each cyclotomic coset of 2 ( mod 2^𝑛-1), 𝘰(𝘫) size of the cyclotomic coset containing 𝘫, 𝘈_𝘫 ∈ 𝔽_2^𝘰(𝘫), Tr_{𝔽2^𝘰(𝘫)/𝔽2} trace function from 𝔽_{2^𝘰(𝘫) to 𝔽2.}

Such representation is also called the univariate representation .

𝑓 can also be simply presented in the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x))} where 𝘗 is a polynomial over the finite field F_2^𝑛 but such representation is not unique, unless 𝘰(𝘫)=𝑛 for every 𝘫 such that 𝘈_𝘫≠0.

The Walsh transform

The Walsh transform 𝑊_𝑓 is the descrete Fourier transform of the sign function of 𝑓, i.e. (-1)^𝑓(𝑥). With an innner product in 𝔽₂^𝑛 𝑥·𝑦, the value of 𝑊_𝑓 at 𝑢∈𝔽₂^𝑛 is the following sum (over the integers)

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W_f(u)=\sum_{x\in\mathbb{F}_2^n}(-1)^{f(x)+x\cdot u},}

The set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ u\in\mathbb{F}_2^n : W_f(u)\ne0 \}} is the Walsh support of 𝑓.

Properties of the Walsh transform

For every 𝑛-variable Boolean function 𝑓 we have the following relations.

• Inverse Walsh transform: for any element 𝑥 of 𝔽₂^𝑛 we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{u\in\mathbb{F}_2^n}W_f(u)(-1)^{u\cdot x}= 2^n(-1)^{f(x)};}
• Parseval's relation: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{u\in\mathbb{F}_2^n}W_f^2(u)=2^{2n};}
• Poisson summation formula: for any vector subspace 𝐸 of 𝔽₂^𝑛 and for any elements 𝑎,𝑏 in 𝔽₂^𝑛 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{u\in a+E^\perp}(-1)^{b\cdot u}W_f(u) = |E^\perp|(-1)^{a\cdot b}\sum_{x\in b+E}(-1)^{f(x)+a\cdot x},} for 𝐸^⟂ the orthogonal subspace of 𝐸,{𝑢∈𝔽₂^𝑛 : 𝑢·𝑥=0, for all 𝑥∈𝐸}.