Lector and mentor of Boolean functions

Studies of Boolean functions

The mentor is a rather dubious soft property of a BF. But it seems surprisingly interesting.
It is found in three steps: Creating a family matrix, getting the senior nobles of its rows, and getting their prefects.
The first digits of the prefects form the mentor.

Ж 24 ↦ Ж 25

Ж 93 ↦ Ж 93

Ж 128 ↦ Ж 151

Ж 249 ↦ Ж 239

The following images are the 4-ary equivalents of those above. The results are either the same as above, or the complement.

Ж 24 ↦ Ж 25

Ж 93 ↦ Ж 93

Ж 128 ↦ Ж 150

Ж 249 ↦ Ж 238

Walsh permutations

A Boolean function has a unique mentor for a given arity. The map between mentors can be expressed by four different Walsh permutations.
(That is, because a BF can be denoted by its truth table or by its Zhegalkin index. In the images above, they are shown red and green.)
In all there are six Walsh permutations, which shall be denoted by Cyrillic letters: Ж (Zhe), Ч (Che), Ш (Sha), Ю (Yu), Я (Ya), Щ (Shcha)
Their degree is $d=2^{arity}$ , i.e. they correspond to invertible binary $d\times d$ matrices.
(The letter Ж is used in two different ways: On its own it represents the permutation. Followed by an integer it represents a BF, identified by its Zhegalkin index.)

Ч = Ж·Ш·Ж = Я·Ж = Ж·Ю map between truth tables
Ш = Ж·Ч·Ж = Ю·Ж = Ж·Я map between Zhegalkin indices

Ю = Ж·Я·Ж = Ш·Ж = Ж·Ч map from truth tables to Zhegalkin indices
Я = Ж·Ю·Ж = Ч·Ж = Ж·Ш map from Zhegalkin indices to truth tables

Ч and Ш are both self-inverse. Ю and Я are inverse to each other.

The matrix of Щ is part of a top right Sierpinki triangle. Its diagonals follow a negated XOR pattern. (See image.)
The matrix of Ш is almost the same, but with the top right entry inverted.
The matrix of Ч is a family matrix. Its top row is related to that of the Ш matrix. The calculation involves the Zhegalkin twin and reversing the truth table.

top row of Ч matrix calculated in Python

This code uses the Python library discrete helpers.

from discretehelpers.boolf import Boolf


def fun(arity):
    linear = ~Boolf(multi_xor=range(arity))    # negated XOR of all arguments (top row of Щ matrix)
    right_bit = Boolf(multi_and=range(arity))  # AND of all arguments
    boolf = (linear ^ right_bit).reverse       # their XOR (top row of Ш matrix), then reversed
    return boolf.twin(arity).reverse           # its Zhegalkin twin, then reversed


for i in range(1, 5):
    boolf = fun(i)
    print(i, boolf, boolf.zhe)

1 Boolf('01') 2
2 Boolf('1000') 15
3 Boolf('1110 1001') 233
4 Boolf('1111 1110 1110 1000') 59521

relationship between the matrix patterns
The red family matrix has the pattern of Ч. The green matrix shows the twins of the red rows, and has the pattern of Ю and Я. The blue matrix shows the twins of the green columns, and has the pattern of Ш.

vectors of Walsh permutations calculated in Python

This code uses the Python library discrete helpers.

import numpy as np

from discretehelpers.boolf import Boolf
from discretehelpers.sig_perm import SigPerm


for arity in range(1, 6):
    length = 2 ** arity

    linear = ~Boolf(multi_xor=range(arity))    # negated XOR of all arguments (top row of Щ matrix)
    right_bit = Boolf(multi_and=range(arity))  # AND of all arguments
    boolf = (linear ^ right_bit).reverse       # their XOR (top row of Ш matrix), then reversed
    boolf = boolf.twin(arity).reverse          # its Zhegalkin twin, then reversed (top row of Ч matrix)

    vector_che = []
    vector_yu = []
    matrix_yu = np.zeros([length, length], dtype=int)

    for i in range(length):
        sigperm = SigPerm(valneg_index=i, perm_index=0)

        family_boolf = boolf.apply_sigperm(sigperm)
        vector_che.append(family_boolf.tt(arity).intval)

        twin = family_boolf.twin(arity)
        vector_yu.append(twin.tt(arity).intval)
        matrix_yu[:, i] = twin.tt(arity)

    reverse_vector_sha = []
    for i in range(length):
        row = list(matrix_yu[i, :])
        reverse_row = row[::-1]
        boolf = Boolf(reverse_row)
        twin = boolf.twin(arity)
        reverse_vector_sha.append(twin.tt(arity).intval)
    vector_sha = reverse_vector_sha[::-1]

    print(f'\n# arity {arity}')
    print(f'vector_che_{arity} = {vector_che}')
    print(f'vector_yu_{arity} = {vector_yu}')
    print(f'vector_sha_{arity} = {vector_sha}')

# arity 1
vector_che_1 = [2, 1]
vector_yu_1 = [2, 3]
vector_sha_1 = [1, 3]

# arity 2
vector_che_2 = [1, 2, 4, 8]
vector_yu_2 = [15, 10, 12, 8]
vector_sha_2 = [1, 2, 4, 8]

# arity 3
vector_che_3 = [151, 107, 109, 158, 121, 182, 214, 233]
vector_yu_3 = [233, 189, 219, 158, 231, 182, 214, 151]
vector_sha_3 = [1, 2, 4, 9, 16, 33, 65, 151]

# arity 4
vector_che_4 = [6015, 11199, 19935, 36591, 29175, 45819, 54525, 59646, 32535, 48939, 57165, 61326, 63345, 64434, 64980, 65256]
vector_yu_4 = [59521, 48321, 55969, 40945, 59017, 47053, 55211, 38654, 59497, 48253, 55931, 40814, 58991, 46970, 55164, 38504]
vector_sha_4 = [1, 2, 4, 9, 16, 33, 65, 150, 256, 513, 1025, 2310, 4097, 8466, 16660, 38504]

# arity 5
vector_che_5 = [2541715455, 1807728639, 1843388415, 2666524671, 2046294015, 3069967359, 3606969855, 3925802751, 2140667775, 3211526079, 3748528095, 4020174831, 4151967735, 4223074299, 4258725885, 4276748286, 2147456895, 3221187519, 3758058975, 4026506991, 4160715255, 4227839739, 4261402365, 4278184446, 4286545815, 4290756459, 4292861805, 4293914526, 4294440825, 4294704054, 4294835670, 4294901481]
vector_yu_5 = [3900735489, 3166748673, 3667959809, 2683367425, 3867707393, 3083652097, 3618286081, 2533359361, 3899162753, 3162292417, 3665469601, 2674913521, 3866003593, 3078343885, 3615337131, 2523529214, 3900729473, 3166731457, 3667950241, 2683334641, 3867700873, 3083631565, 3618274731, 2533321214, 3899156713, 3162275005, 3665459931, 2674880414, 3865997031, 3078323126, 3615325654, 2523490711]
vector_sha_5 = [1, 2, 4, 9, 16, 33, 65, 150, 256, 513, 1025, 2310, 4097, 8466, 16660, 38505, 65536, 131073, 262145, 589830, 1048577, 2162706, 4259860, 9830505, 16777217, 33620226, 67174660, 151389705, 268501264, 554832417, 1091834945, 2523490711]

See the fixed points of Ч and Ш ordered by weight: Ч, Ш

1-ary

The permutations are all six Walsh permutations of degree 2. Ч = (0, 2, 1, 3) Ш = (0, 1, 3, 2) Щ = I (neutral permutation)

permutations

2-ary

Ч = Ш = I (neutral permutation) Ю = Я = Ж Щ = (0, 1, 2, 3, 4, 5, 6, 7, 9, 8, 11, 10, 13, 12, 15, 14)

3-ary

Ж: twins

Ч: T to T

Ю: T to Z

Я: Z to T

Ш: Z to Z

Щ: beginning of senior Ш

code

# vectors of the Walsh permutations

vector_zhe   = [255, 170, 204, 136, 240, 160, 192, 128]

vector_che   = [151, 107, 109, 158, 121, 182, 214, 233]
vector_yu    = [233, 189, 219, 158, 231, 182, 214, 151]
vector_ya    = [255, 170, 204, 119, 240,  95,  63, 233]
vector_sha   = [  1,   2,   4,   9,  16,  33,  65, 151]

vector_shcha = [  1,   2,   4,   9,  16,  33,  65, 150]

# sequences

perm_zhe = [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]

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

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

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

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

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

Place 199 can be used to check, if the permutations are correct: Ж(199) = 217 Ч(199) = 174 Ю(199) = 206 Я(199) = 79 Ш(199) = 209 Щ(199) = 208 (See image.)

Permutation Я is related to quarter sharpness, which is seen in these images.

4-ary

code

# vectors of the Walsh permutations

vector_zhe   = [65535, 43690, 52428, 34952, 61680, 41120, 49344, 32896, 65280, 43520, 52224, 34816, 61440, 40960, 49152, 32768]

vector_che   = [ 6015, 11199, 19935, 36591, 29175, 45819, 54525, 59646, 32535, 48939, 57165, 61326, 63345, 64434, 64980, 65256]
vector_yu    = [59521, 48321, 55969, 40945, 59017, 47053, 55211, 38654, 59497, 48253, 55931, 40814, 58991, 46970, 55164, 38504]
vector_ya    = [65535, 43690, 52428, 30583, 61680, 24415, 16191,  5654, 65280, 22015, 13311,  4454,  4095,  1370,   828, 65256]
vector_sha   = [    1,     2,     4,     9,    16,    33,    65,   150,   256,   513,  1025,  2310,  4097,  8466, 16660, 38504]

vector_shcha = [    1,     2,     4,     9,    16,    33,    65,   150,   256,   513,  1025,  2310,  4097,  8466, 16660, 38505]

seminars

The mentor is not simply a bijection between Boolean functions, but between the truth tables for a given arity.
The permutation from Zhegalkin indices to those of their n-ary mentors is Ш_n. The beginning of Ш_n+1 is Щ_n. (This letter has a little hook on the right.)
These two permutations are very similar. They are equal in the first half, and differ by exchanged neighbors in the second.

Neighboring Zhegalkin indices (i.e. 2·n and 2·n+1) denote complements.
So although there is no mentor bijection between Boolean functions, there is one between pairs of complements.
Complement and mentor partition the set of all Boolean functions into blocks of size 4 or 2. Such a block shall be called (big or small) seminar.
The Zhegalkin indices in a big seminar are $\{a,a+1,b,b+1\}$ with even $a$ and $b$ , so it can be represented by the pair $(a,b)$ .
An example of a seminar is {138, 139, 156, 157}, represented as (138, 156). See image. In the permutation it is represented by the pair (69, 78).

The pairs $\left({\frac {a}{2}},{\frac {b}{2}}\right)$ are the cycles of a self-inverse Walsh permutation of degree $2^{arity}-1$ . (For arity 3 the degree is 7, and the permuted integers are 0...127.)
For arities 1 and 2 this permutation is neutral. For arity 3 is has 64 fixed points (of 128 places, i.e. 1/2). For arity 5 it has 1024 fixed points (of 32768 places, i.e. 1/32).

mentor permutation

15×15 matrix corresponding to the Walsh permutation for arity 4.

The first 64 entries of the sequence are the fixed points. The next 64 entries form these 32 cycles:

[ 64,  75], [ 65,  74], [ 66,  73], [ 67,  72], [ 68,  79], [ 69,  78], [ 70,  77], [ 71,  76], 
[ 80,  91], [ 81,  90], [ 82,  89], [ 83,  88], [ 84,  95], [ 85,  94], [ 86,  93], [ 87,  92], 
[ 96, 107], [ 97, 106], [ 98, 105], [ 99, 104], [100, 111], [101, 110], [102, 109], [103, 108],
[112, 123], [113, 122], [114, 121], [115, 120], [116, 127], [117, 126], [118, 125], [119, 124]

The permutation for arity 4 corresponds to the 15×15 matrix shown on the right.
It is described by this vector: (1, 2, 4, 8, 16, 32, 75, 128, 256, 512, 1155, 2048, 4233, 8330, 19252)

The matrix is always that of Ш or Щ without the top row and left column.

For arity 3 the Boolean functions in big seminars are the sharp ones (i.e. those with odd weight). See images.

For a given arity, each seminar is part of a chunky seminar. For arity 3 they all have size 16. E.g. (142, 152), (230, 240), 14, 24, 102, 112 are all part of this.

chains

The permutations Ю and Я have fewer fixed points and longer cycles than Ч and Ш.
A cycle of Ю shall be called chain. (Cycles of Я are the same, but reversed.)
The XOR of all entries of a chain is one of the fixed points, and shall be called anchor. The fixed points are nobles.

tables of chains: 3-ary (4 fixed points), 4-ary (8 fixed points)

3-ary partitions: chain, chain length, chain quadrants, reduced chain quadrants, chunky chain, anchor