In the Wikipedia article "Bent functions", there are some figures representing those Bent functions:

image 1 showing the figures

image 2 showing the figures

How do these figures represent a boolean function ?


1 Answer 1


The image description page for the larger image describes it pretty well.

Specifically, the line at the top of the figure:

0001 0001 0001 1110

shows the 4-ary Boolean function $f(x_1, x_2, x_3, x_4) = x_1 x_2 + x_3 x_4$ in a graphical form. Specifically, interpreting each possible input as a 4-bit binary number (e.g. $(0, 1, 0, 1) \mapsto 0101_2 = 5$), the corresponding square on the line (starting from square 0 on the left, and counting up to square 15 on the right) is colored red if the output of the function is 1, and white if it is 0.

The square below the shows the Walsh matrix of order 16, the rows of which correspond to the 16 linear 4-ary Boolean functions (a.k.a. the Walsh functions), using the same representation as for the top row. The squares marked with dots are those where the nonlinear function shown at the top differs from the linear function described by the row, and the number on the right counts the number of such dots on the line.

The second square below that is the complement of the Walsh matrix, showing the 16 non-linear affine 4-ary Boolean functions (i.e. functions which are linear except for the addition of a non-zero constant, which for Boolean functions can only be 1). The dots and the numbers have the same meaning as before.

Looking at the numbers of the right, one can see that the number of inputs at which the given function $f$ differs from each affine 4-ary Boolean function is either 6 or 10 = 16 − 6, demonstrating that $f$ is equidistant (in the sense of absolute number of differences modulo 16) from each affine 4-are Boolean function, and is therefore a bent function.

The other image just contains four smaller but otherwise similar subfigures, showing that each of the four 2-ary Boolean functions of Hamming weight one (i.e. producing the output 1 for only one set of inputs) is also a bent function.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.