Zhegalkin matrix

Studies of Boolean functions

Ж

ANF   matrix   twins

noble   gentle

smallest Zhegalkin index

The Zhegalkin matrix is an infinite binary matrix.

It is closely related to the infinite integer matrix of Gray code permutation powers ( A195467) and to the algebraic normal form (ANF) of Boolean functions.
(Ivan Zhegalkin was the inventor of the ANF. The naming choices made here are new.)

Its colums are the truth tables of all Boolean functions. The column index is the Zhegalkin index of the respective Boolean function.

Its rows are a subset of the Walsh functions, namely the XORs of atoms forming a Sierpiński triangle ( A001317).

The columns of the 8×256 Zhegalkin matrix are the truth tables of the 256 3-ary Boolean functions.
The 8×256 matrix above are the colum indices in little-endian binary. On the left are the Sierpiński triangle and the row indices.

as rows of a binary Walsh matrix
This is a 256×256 binary Walsh matrix. Each row is the variadic XOR of the atoms shown in the 256×8 matrix on the left.

Zhegalkin permutation

sizes of finite Zhegalkin matrices

$n$	0	1	2	3	4
$2^{n}\times 2^{2^{n}}$	1×2	2×4	4×16	8×256	16×65536

For arity $n$ the map from ANFs to truth tables gives a finite Zhegalkin matrix of size $2^{n}\times 2^{2^{n}}$. (It is the top left corner of the infinite matrix.)

It can be interpreted as a permutation of the integers $0~...~2^{2^{n}}-1$, which shall be called Zhegalkin permutation $\Pi _{n}$.
Keys and values in Π_n shall be called Zhegalkin twins — e.g. 7 and 9 are Zhegalkin twins for arity 2.

It is a self-inverse Walsh permutation of degree 2ⁿ. The corresponding element of GL(2ⁿ, 2) is the lower Sierpiński triangle.
Π₂ is a Walsh permutation of degree 4, and permutes the integers 0 ... 15. The corresponding element of GL(4, 2) is the 4×4 lower Sierpiński triangle.

$\Pi$           A197819

Fixed points are in parentheses. k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 n 0 (0) (1) 1 (0) 3 (2) 1 2 (0) 15 10 5 12 3 (6) 9 (8) 7 2 13 4 11 (14) 1 row 3 of length 256:     0, 255, 170, 85 ... 84, 171, 254, 1 [0, 255, 170, 85, 204, 51, 102, 153, 136, 119, 34, 221, 68, 187, 238, 17, 240, 15, 90, 165, 60, 195, 150, 105, 120, 135, 210, 45, 180, 75, 30, 225, 160, 95, 10, 245, 108, 147, 198, 57, 40, 215, 130, 125, 228, 27, 78, 177, 80, 175, 250, 5, 156, 99, 54, 201, 216, 39, 114, 141, 20, 235, 190, 65, 192, 63, 106, 149, 12, 243, 166, 89, 72, 183, 226, 29, 132, 123, 46, 209, 48, 207, 154, 101, 252, 3, 86, 169, 184, 71, 18, 237, 116, 139, 222, 33, 96, 159, 202, 53, 172, 83, 6, 249, 232, 23, 66, 189, 36, 219, 142, 113, 144, 111, 58, 197, 92, 163, 246, 9, 24, 231, 178, 77, 212, 43, 126, 129, 128, 127, 42, 213, 76, 179, 230, 25, 8, 247, 162, 93, 196, 59, 110, 145, 112, 143, 218, 37, 188, 67, 22, 233, 248, 7, 82, 173, 52, 203, 158, 97, 32, 223, 138, 117, 236, 19, 70, 185, 168, 87, 2, 253, 100, 155, 206, 49, 208, 47, 122, 133, 28, 227, 182, 73, 88, 167, 242, 13, 148, 107, 62, 193, 64, 191, 234, 21, 140, 115, 38, 217, 200, 55, 98, 157, 4, 251, 174, 81, 176, 79, 26, 229, 124, 131, 214, 41, 56, 199, 146, 109, 244, 11, 94, 161, 224, 31, 74, 181, 44, 211, 134, 121, 104, 151, 194, 61, 164, 91, 14, 241, 16, 239, 186, 69, 220, 35, 118, 137, 152, 103, 50, 205, 84, 171, 254, 1]

In a finite Zhegalkin matrix, the columns with even/odd weight are in the left/right half.   (A truth table has a Zhegalkin twin with odd weight, iff its last digit is true.)
Boolean functions whose Zhegalkin index has even/odd weight shall be called evil/odious, which shall be called its depravity.

fixed points

number of fixed points

$n$	1	2	3	4	5
$2^{2^{n-1}}$	2	4	16	256	65536

The fixed points of Zhegalkin permutations correspond to noble Boolean functions.

$\Phi _{n}~~=~~\{i\mid \Pi _{n,~i}=i\}$           A358167

k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 n 0 0 1 0 2 2 0 6 8 14 3 0 30 40 54 72 86 96 126 128 158 168 182 200 214 224 254 row 4 of length 256:     0, 510, 680, 854 ... 64680, 64854, 65024, 65534 [0, 510, 680, 854, 1224, 1334, 1632, 1950, 2176, 2430, 2600, 3030, 3144, 3510, 3808, 3870, 4320, 4382, 4680, 5046, 5160, 5590, 5760, 6014, 6240, 6558, 6856, 6966, 7336, 7510, 7680, 8190, 8320, 8574, 8744, 9174, 9288, 9654, 9952, 10014, 10240, 10750, 10920, 11094, 11464, 11574, 11872, 12190, 12384, 12702, 13000, 13110, 13480, 13654, 13824, 14334, 14560, 14622, 14920, 15286, 15400, 15830, 16000, 16254, 16512, 16766, 16936, 17366, 17480, 17846, 18144, 18206, 18432, 18942, 19112, 19286, 19656, 19766, 20064, 20382, 20576, 20894, 21192, 21302, 21672, 21846, 22016, 22526, 22752, 22814, 23112, 23478, 23592, 24022, 24192, 24446, 24576, 25086, 25256, 25430, 25800, 25910, 26208, 26526, 26752, 27006, 27176, 27606, 27720, 28086, 28384, 28446, 28896, 28958, 29256, 29622, 29736, 30166, 30336, 30590, 30816, 31134, 31432, 31542, 31912, 32086, 32256, 32766, 32768, 33278, 33448, 33622, 33992, 34102, 34400, 34718, 34944, 35198, 35368, 35798, 35912, 36278, 36576, 36638, 37088, 37150, 37448, 37814, 37928, 38358, 38528, 38782, 39008, 39326, 39624, 39734, 40104, 40278, 40448, 40958, 41088, 41342, 41512, 41942, 42056, 42422, 42720, 42782, 43008, 43518, 43688, 43862, 44232, 44342, 44640, 44958, 45152, 45470, 45768, 45878, 46248, 46422, 46592, 47102, 47328, 47390, 47688, 48054, 48168, 48598, 48768, 49022, 49280, 49534, 49704, 50134, 50248, 50614, 50912, 50974, 51200, 51710, 51880, 52054, 52424, 52534, 52832, 53150, 53344, 53662, 53960, 54070, 54440, 54614, 54784, 55294, 55520, 55582, 55880, 56246, 56360, 56790, 56960, 57214, 57344, 57854, 58024, 58198, 58568, 58678, 58976, 59294, 59520, 59774, 59944, 60374, 60488, 60854, 61152, 61214, 61664, 61726, 62024, 62390, 62504, 62934, 63104, 63358, 63584, 63902, 64200, 64310, 64680, 64854, 65024, 65534]

illustration of fixed points $\Phi _{3}$ in permutation $\Pi _{3}$

Python code

Python functions

from sympy import binomial def sierpinski(n): return int(sum([(binomial(n, i) % 2) * 2 ** i for i in range(n + 1)])) def zhegalkin_perm(n, k): row_length = 1 << (1 << n) # 2 ** 2 ** n assert k < row_length string_length = 1 << n # 2 ** n k_binary = "{0:b}".format(k).zfill(string_length) reflected_result = 0 for i, binary_digit in enumerate(k_binary): if binary_digit == '1': s = sierpinski(i) reflected_result ^= s reflected_result_binary = "{0:b}".format(reflected_result).zfill(string_length) result_binary = reflected_result_binary[::-1] return int(result_binary, 2) def zhegalkin_fixed(n, k): if n == 0: assert k < 2 return k else: row_length = 1 << (1 << (n-1)) # 2 ** 2 ** (n-1) assert k < row_length p = zhegalkin_perm(n-1, k) p_xor_k = p ^ k shifted_k = row_length * k return p_xor_k + shifted_k

Walsh permutations and Sierpiński triangles

This code uses the Python library discrete helpers. from discretehelpers.walsh_perm import WalshPerm from discretehelpers.binv import Binv def anf_int_to_boolf(input_integer): from discretehelpers.boolf import Boolf input_indices = Binv(intval=input_integer).indices if input_indices == set(): return Boolf(False) result_boolf = Boolf(False) for i in input_indices: loop_indices = Binv(intval=i).indices loop_boolf = Boolf(multi_and=loop_indices) result_boolf = result_boolf ^ loop_boolf return result_boolf def create_sequence(arity): sequence = [] for i in range(2 ** 2 ** arity): boolf = anf_int_to_boolf(i) binv = Binv(boolf.truth_table(arity)) sequence.append(binv.intval) return sequence sequence_0 = create_sequence(0) # [0, 1] sequence_1 = create_sequence(1) # [0, 3, 2, 1] sequence_2 = create_sequence(2) # [0, 15, 10, 5, 12, 3, 6, 9, 8, 7, 2, 13, 4, 11, 14, 1] sequence_3 = create_sequence(3) # [0, 255, 170, 85 ... 84, 171, 254, 1] sequence_4 = create_sequence(4) # [0, 65535, 43690, 21845 ... 21844, 43691, 65534, 1] wp_0 = WalshPerm(perm=sequence_0) wp_1 = WalshPerm(perm=sequence_1) wp_2 = WalshPerm(perm=sequence_2) wp_3 = WalshPerm(perm=sequence_3) wp_4 = WalshPerm(perm=sequence_4) wp_0.matrix() # array([[1]]) wp_1.matrix() # array([[1, 0], # [1, 1]]) wp_2.matrix() # array([[1, 0, 0, 0], # [1, 1, 0, 0], # [1, 0, 1, 0], # [1, 1, 1, 1]]) wp_3.matrix() # array([[1, 0, 0, 0, 0, 0, 0, 0], # [1, 1, 0, 0, 0, 0, 0, 0], # [1, 0, 1, 0, 0, 0, 0, 0], # [1, 1, 1, 1, 0, 0, 0, 0], # [1, 0, 0, 0, 1, 0, 0, 0], # [1, 1, 0, 0, 1, 1, 0, 0], # [1, 0, 1, 0, 1, 0, 1, 0], # [1, 1, 1, 1, 1, 1, 1, 1]]) wp_4.matrix() # array([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # [1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # [1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], # [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], # [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], # [1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0], # [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0], # [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0], # [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0], # [1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0], # [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0], # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]])