# Boolean Functions

## Contents

# Introduction

Let 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 .
A function is called a *Boolean function* in dimenstion *n* (or *n-variable Boolean function*).

Given , the support of *x* is the set .
The Hamming weight of *x* is the size of its support ().
Similarly the Hamming weight of a Boolean function *f* is the size of its support, i.e. the set .
The Hamming distance of two functions *f,g* is the size of the set .

# 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 of the form

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, .

## Trace representation

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

with Γ_{n} set of integers obtained by choosing one element in each cyclotomic coset of 2 ( mod 2^{n}-1), *o(j)* size of the cyclotomic coset containing *j*, *A _{j} ∈ 𝔽_{2o(j)}, Tr_{𝔽2o(j)/𝔽2} trace function from 𝔽_{2o(j) to 𝔽2.
}*

Such representation is also called the univariate representation .

*f* can also be simply presented in the form where *P* is a polynomial over the finite field F_{2n} but such representation is not unique, unless *o(j)=n* for every *j* such that *A _{j}*≠0.