<p>You are right about Zhegalkin polynomials, which are called Algebraic Normal Form (ANF) in the Boolean functions literature. Such representation is unique.</p>

<p>$$f(x) = \bigoplus_{u\in GF(2^n)} a_u x^u = \bigoplus_{u\in GF(2^n)} a_u x_1^{u_1} \ldots x_n^{u_n},$$</p>

<p>where $a_u \in GF(2)$ are coefficients of the monomials, $u$ is the binary mask defining the form of the monomial and $x=x_1,\ldots,x_n$ are the variables. $x^u$ is just a shorthand for bitwise powers.</p>

<p>The <strong>linear</strong> (over $GF(2)$) mapping which transforms the truth table of a Boolean function into the table of $2^n$ coefficients $a_u$ is called Möbius transform:</p>

<p>$$a_u = \bigoplus_{x \preceq u} f(x),$$</p>

<p>where $x \preceq u$ means that $x \&amp; u = x$.</p>

<p>Möbius transform is also the inverse of itself.</p>

<p>It's matrix is the Kronecker "power" of this matrix:</p>

<p>$$\pmatrix{
1 &amp; 1 \\
1 &amp; 0 
}^{(n)}$$</p>

<p>From this one can derive a simple recursive algorithm performing the Mobius transform in time $n2^n$.</p>

<p>Some methods of cryptanalysis are using ANF. They exploit low degrees of the ANFs in a cryptographic primitive. For example, if you can prove an upper-bound on the degree of a cipher, you know that for $u$ with high Hamming weight the coefficient $a_u = \bigoplus_{x \preceq u} f(x)$ is zero. So you get a property of $f$ which distinguishes it from random function.</p>

CC BY-SA 3.0
2018-04-10T18:35:59.137Z
2018-04-10T18:41:26.887Z
2018-04-10T18:41:26.887Z
Fractalic
<p>Well done on your independent discovery.</p>

<p>This is a Hadamard matrix of Sylvester type, written in a different order. There is a massive literature on this topic. It is used in coding theory, cryptography, is directly related to Reed-Muller codes of degree 1, it can be used to obtain best affine approximations of functions, etc.</p>

<p>Ryan O'Donnell's notes on Analysis of Boolean functions available <a href="http://www.contrib.andrew.cmu.edu/~ryanod/" rel="noreferrer">here</a> which are now published as a book, Claude Carlet's chapters on Boolean 
functions <a href="http://www.math.univ-paris13.fr/~carlet/chap-fcts-Bool-corr.pdf" rel="noreferrer">here</a> are easily accessible online.</p>

<p>Just use the order $[1,X,Y,XY,Z,ZX,ZY,ZXY]$ which corresponds to lexicographic order over the integers, and apply the corresponding permutation to the columns as well. </p>

<p>In that order your matrix is simply the 3-fold Kronecker product $$H_2 \otimes H_2\otimes H_2$$of the basic 2 by 2 Hadamard matrix.</p>

<p>$$
H_2=\left(\begin{array}{cc} 1 &amp; 1 \\ 1 &amp; -1 \end{array}
\right),
$$</p>

<p>This <a href="https://arxiv.org/pdf/1305.0860.pdf" rel="noreferrer">paper</a> considers efficient evaluation of Hadamard representation coefficients.</p>

CC BY-SA 3.0
2018-04-01T08:15:45.947Z
2018-04-01T11:22:33.873Z
2018-04-01T11:22:33.873Z
kodlu
<p>I came up with this linear transformation to map boolean functions to polynomials and it seems to have some nice properties. I was wondering if there is any reference describing this (and/or similar) mappings and their application. </p>

<p>For three variables, the transformation matrix is given below: </p>

<p><a href="https://i.sstatic.net/fArfh.gif" rel="noreferrer"><img src="https://i.sstatic.net/fArfh.gif" alt="enter image description here"></a></p>

<p>I have posted this with some details and a description for reducing 3-SAT to checking the existence of specific term in an ordinary polynomial product on math.stackexchange (<a href="https://math.stackexchange.com/a/2710462/7138">here</a>). I have not got much feedback there. I was wondering if someone here could help. </p>

<p>If this is not the right forum to ask this sort of questions, or more details are needed, please let me know in comments.</p>

<p>EDIT: I found similarities to Zhegalkin polynomials and the $f:\left \{ -1,1 \right \}^n \rightarrow \left \{ -1,1 \right \}$ representation described <a href="http://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf" rel="noreferrer">here</a> with the difference that this is a $f:\left \{ -1,1 \right \}^n \rightarrow \left \{ 0,1 \right \}$ representation.   </p>

<cc.complexity-theory><computability><sat><boolean-functions><polynomials>
a polynomial representation of boolean functions
mghandi
# a polynomial representation of boolean functions

(Asked by: username_0 on 2018-03-31)

I came up with this linear transformation to map boolean functions to polynomials and it seems to have some nice properties. I was wondering if there is any reference describing this (and/or similar) mappings and their application.

For three variables, the transformation matrix is given below:

[![enter image description here](https://i.sstatic.net/fArfh.gif)](https://i.sstatic.net/fArfh.gif)

I have posted this with some details and a description for reducing 3-SAT to checking the existence of specific term in an ordinary polynomial product on math.stackexchange ([here](https://math.stackexchange.com/a/2710462/7138)). I have not got much feedback there. I was wondering if someone here could help.

If this is not the right forum to ask this sort of questions, or more details are needed, please let me know in comments.

EDIT: I found similarities to Zhegalkin polynomials and the $f:\left \{ -1,1 \right \}^n \rightarrow \left \{ -1,1 \right \}$ representation described [here](http://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf) with the difference that this is a $f:\left \{ -1,1 \right \}^n \rightarrow \left \{ 0,1 \right \}$ representation.

**Tags:** cc.complexity-theory, computability, sat, boolean-functions, polynomials

---

## 2 answers

### Answer by username_2 on 2018-04-01. Score: 9 | Accepted answer

Well done on your independent discovery.

This is a Hadamard matrix of Sylvester type, written in a different order. There is a massive literature on this topic. It is used in coding theory, cryptography, is directly related to Reed-Muller codes of degree 1, it can be used to obtain best affine approximations of functions, etc.

Ryan O'Donnell's notes on Analysis of Boolean functions available [here](http://www.contrib.andrew.cmu.edu/~ryanod/) which are now published as a book, Claude Carlet's chapters on Boolean
functions [here](http://www.math.univ-paris13.fr/~carlet/chap-fcts-Bool-corr.pdf) are easily accessible online.

Just use the order $[1,X,Y,XY,Z,ZX,ZY,ZXY]$ which corresponds to lexicographic order over the integers, and apply the corresponding permutation to the columns as well.

In that order your matrix is simply the 3-fold Kronecker product $$H\_2 \otimes H\_2\otimes H\_2$$of the basic 2 by 2 Hadamard matrix.

$$
H\_2=\left(\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}
\right),
$$

This [paper](https://arxiv.org/pdf/1305.0860.pdf) considers efficient evaluation of Hadamard representation coefficients.


---

### Answer by username_1 on 2018-04-10. Score: 2

You are right about Zhegalkin polynomials, which are called Algebraic Normal Form (ANF) in the Boolean functions literature. Such representation is unique.

$$f(x) = \bigoplus\_{u\in GF(2^n)} a\_u x^u = \bigoplus\_{u\in GF(2^n)} a\_u x\_1^{u\_1} \ldots x\_n^{u\_n},$$

where $a\_u \in GF(2)$ are coefficients of the monomials, $u$ is the binary mask defining the form of the monomial and $x=x\_1,\ldots,x\_n$ are the variables. $x^u$ is just a shorthand for bitwise powers.

The **linear** (over $GF(2)$) mapping which transforms the truth table of a Boolean function into the table of $2^n$ coefficients $a\_u$ is called Möbius transform:

$$a\_u = \bigoplus\_{x \preceq u} f(x),$$

where $x \preceq u$ means that $x \& u = x$.

Möbius transform is also the inverse of itself.

It's matrix is the Kronecker "power" of this matrix:

$$\pmatrix{
1 & 1 \\
1 & 0
}^{(n)}$$

From this one can derive a simple recursive algorithm performing the Mobius transform in time $n2^n$.

Some methods of cryptanalysis are using ANF. They exploit low degrees of the ANFs in a cryptographic primitive. For example, if you can prove an upper-bound on the degree of a cipher, you know that for $u$ with high Hamming weight the coefficient $a\_u = \bigoplus\_{x \preceq u} f(x)$ is zero. So you get a property of $f$ which distinguishes it from random function.


---

