# Introduction

Let ${\displaystyle \mathbb {F} _{2}^{n}}$ be the vector space of dimension n over the finite field with two elements. The vector space can also be endowed with the structure of the field, the finite field with ${\displaystyle 2^{n}{\mbox{ elements, }}\mathbb {F} _{2^{n}}}$. A function ${\displaystyle f:\mathbb {F} _{2}^{n}\rightarrow \mathbb {F} }$ is called a Boolean function in dimenstion n (or n-variable Boolean function).

Given ${\displaystyle x=(x_{1},\ldots ,x_{n})\in \mathbb {F} _{2}^{n}}$, the support of x is the set ${\displaystyle supp_{x}=\{i\in \{1,\ldots ,n\}:x_{i}=1\}}$. The Hamming weight of x is the size of its support (${\displaystyle w_{H}(x)=|supp_{x}|}$). Similarly the Hamming weight of a Boolean function f is the size of its support, i.e. the set ${\displaystyle \{x\in \mathbb {F} _{2}^{n}:f(x)\neq 0\}}$. The Hamming distance of two functions f,g is the size of the set ${\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 f.

x f(x)
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 n-variable Boolean function can be represented by a multivariate polynomial over ${\displaystyle \mathbb {F} }$ of the form

${\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 f (shortly ANF).

The degree of the ANF is called the algebraic degree of the function, ${\displaystyle d^{0}f=\max\{|I|:a_{I}\neq 0\}}$.