Linear and noble Boolean functions

Studies of Boolean functions

arity  |  n {\displaystyle n} | 1  | 2  | 3  | 4  | 5

|
|
|
|
|
|

linear  |  2 n + 1 {\displaystyle 2^{n+1}} | 4  | 8  | 16  | 32  | 64
noble  |  2 2 n − 1 {\displaystyle 2^{2^{n-1}}} | 2  | 4  | 16  | 256  | 65536

Among the truth tables for a given arity, the linears and the nobles are important subsets.

Each linear can be assigned a patron, which is noble. Each noble can be assigned a prefect, which is linear.

For arity 3 they form a bijection. For higher arities the nobles outnumber the linears (i.e. the patrons of the linears are a subset of the nobles).

## Contents

* 1 overview
* 2 3-ary
* 3 4-ary
* 3.1 linear to patron (noble)
* 3.2 noble to prefect (linear)

## overview

[edit | edit source]

2-ary

linears  (truth tables and Zhegalkin indices)

| nobles
3-ary

linears  (truth tables and Zhegalkin indices)

| nobles
4-ary

| linears  (truth tables)

linears  (Zhegalkin indices)

nobles

## 3-ary

[edit | edit source]

nobles in tesseract

| dihedral symmetry | mirror symmetry
quadrants

0  (even, evil) |  3  (odd, odious)
2  (even, odious) |  1  (odd, evil)
halves

even
Walsh functions | odd
complements of Walsh functions
all

## 4-ary

[edit | edit source]

### linear to patron (noble)

[edit | edit source]

There are 32 nobles, which form 10 factions. (Even and odd faction for each Walsh weight 0...4.) Their patrons are 32 nobles, which also form 10 factions (among the 44 noble factions).

Their juniors are the 3-ary Boolean functions with consul 0.

list

The faction is determined by Walsh weight and parity (or quadrant), and represented by variants of the quadrant colors.
A good sort order is first by quadrant, and then by Walsh weight.

| Walsh
weight  | Walsh
index  | ¬ | leader  | Q | linear  | patron (noble)

|
|
|
|
|
|

truth table  |  | Ж  | truth table  |  |
0  | 0  | 0  | 0  | 0  | .... .... .... ....  | 0  | 0  | .... .... .... ....  | 0  | 0
2  | 3  | 0  | 1  | 0  | .!!. .!!. .!!. .!!.  | 26214  | 6  | .... .!!. .!!. .!!.  | 26208  | 102
2  | 5  | 0  | 2  | 0  | .!.! !.!. .!.! !.!.  | 23130  | 18  | ...! ..!. .!.! !.!.  | 23112  | 90
2  | 6  | 0  | 3  | 0  | ..!! !!.. ..!! !!..  | 15420  | 20  | ...! .!.. ..!! !!..  | 15400  | 60
2  | 9  | 0  | 4  | 0  | .!.! .!.! !.!. !.!.  | 21930  | 258  | ...! .!.! ..!. !.!.  | 21672  | 84
2  | 10  | 0  | 5  | 0  | ..!! ..!! !!.. !!..  | 13260  | 260  | ...! ..!! .!.. !!..  | 13000  | 50
2  | 12  | 0  | 6  | 0  | .... !!!! !!!! ....  | 4080  | 272  | .... .!!! .!!! ....  | 3808  | 14
4  | 15  | 0  | 7  | 0  | .!!. !..! !..! .!!.  | 27030  | 278  | .... ...! ...! .!!.  | 26752  | 104
1  | 1  | 1  | 0  | 1  | !.!. !.!. !.!. !.!.  | 21845  | 3  | .!!. !.!. !.!. !.!.  | 21846  | 85
1  | 2  | 1  | 1  | 1  | !!.. !!.. !!.. !!..  | 13107  | 5  | .!!. !!.. !!.. !!..  | 13110  | 51
1  | 4  | 1  | 2  | 1  | !!!! .... !!!! ....  | 3855  | 17  | .!!! !... !!!! ....  | 3870  | 15
3  | 7  | 1  | 3  | 1  | !..! .!!. !..! .!!.  | 26985  | 23  | .!!! !!!. !..! .!!.  | 27006  | 105
1  | 8  | 1  | 4  | 1  | !!!! !!!! .... ....  | 255  | 257  | .!!! !!!! !... ....  | 510  | 1
3  | 11  | 1  | 5  | 1  | !..! !..! .!!. .!!.  | 26265  | 263  | .!!! !..! !!!. .!!.  | 26526  | 103
3  | 13  | 1  | 6  | 1  | !.!. .!.! .!.! !.!.  | 23205  | 275  | .!!. !!.! !!.! !.!.  | 23478  | 91
3  | 14  | 1  | 7  | 1  | !!.. ..!! ..!! !!..  | 15555  | 277  | .!!. !.!! !.!! !!..  | 15830  | 61
1  | 1  | 0  | 0  | 2  | .!.! .!.! .!.! .!.!  | 43690  | 2  | ...! .!.! .!.! .!.!  | 43688  | 170
1  | 2  | 0  | 1  | 2  | ..!! ..!! ..!! ..!!  | 52428  | 4  | ...! ..!! ..!! ..!!  | 52424  | 204
1  | 4  | 0  | 2  | 2  | .... !!!! .... !!!!  | 61680  | 16  | .... .!!! .... !!!!  | 61664  | 240
3  | 7  | 0  | 3  | 2  | .!!. !..! .!!. !..!  | 38550  | 22  | .... ...! .!!. !..!  | 38528  | 150
1  | 8  | 0  | 4  | 2  | .... .... !!!! !!!!  | 65280  | 256  | .... .... .!!! !!!!  | 65024  | 254
3  | 11  | 0  | 5  | 2  | .!!. .!!. !..! !..!  | 39270  | 262  | .... .!!. ...! !..!  | 39008  | 152
3  | 13  | 0  | 6  | 2  | .!.! !.!. !.!. .!.!  | 42330  | 274  | ...! ..!. ..!. .!.!  | 42056  | 164
3  | 14  | 0  | 7  | 2  | ..!! !!.. !!.. ..!!  | 49980  | 276  | ...! .!.. .!.. ..!!  | 49704  | 194
0  | 0  | 1  | 0  | 3  | !!!! !!!! !!!! !!!!  | 65535  | 1  | .!!! !!!! !!!! !!!!  | 65534  | 255
2  | 3  | 1  | 1  | 3  | !..! !..! !..! !..!  | 39321  | 7  | .!!! !..! !..! !..!  | 39326  | 153
2  | 5  | 1  | 2  | 3  | !.!. .!.! !.!. .!.!  | 42405  | 19  | .!!. !!.! !.!. .!.!  | 42422  | 165
2  | 6  | 1  | 3  | 3  | !!.. ..!! !!.. ..!!  | 50115  | 21  | .!!. !.!! !!.. ..!!  | 50134  | 195
2  | 9  | 1  | 4  | 3  | !.!. !.!. .!.! .!.!  | 43605  | 259  | .!!. !.!. !!.! .!.!  | 43862  | 171
2  | 10  | 1  | 5  | 3  | !!.. !!.. ..!! ..!!  | 52275  | 261  | .!!. !!.. !.!! ..!!  | 52534  | 205
2  | 12  | 1  | 6  | 3  | !!!! .... .... !!!!  | 61455  | 273  | .!!! !... !... !!!!  | 61726  | 241
4  | 15  | 1  | 7  | 3  | !..! .!!. .!!. !..!  | 38505  | 279  | .!!! !!!. !!!. !..!  | 38782  | 151
sequences

truth tables of linears:
`0, 26214, 23130, 15420, 21930, 13260, 4080, 27030, 21845, 13107, 3855, 26985, 255, 26265, 23205, 15555, 43690, 52428, 61680, 38550, 65280, 39270, 42330, 49980, 65535, 39321, 42405, 50115, 43605, 52275, 61455, 38505`

Zhegalkin indices of linears:
`0, 6, 18, 20, 258, 260, 272, 278, 3, 5, 17, 23, 257, 263, 275, 277, 2, 4, 16, 22, 256, 262, 274, 276, 1, 7, 19, 21, 259, 261, 273, 279`

truth tables (and Zhegalkin indices) of patrons:
`0, 26208, 23112, 15400, 21672, 13000, 3808, 26752, 21846, 13110, 3870, 27006, 510, 26526, 23478, 15830, 43688, 52424, 61664, 38528, 65024, 39008, 42056, 49704, 65534, 39326, 42422, 50134, 43862, 52534, 61726, 38782`

noble indices (juniors) of patrons:
`0, 102, 90, 60, 84, 50, 14, 104, 85, 51, 15, 105, 1, 103, 91, 61, 170, 204, 240, 150, 254, 152, 164, 194, 255, 153, 165, 195, 171, 205, 241, 151`

details for each faction

The numbers next to the images correspond to the truth tables.
The linears are in the left columns, their patrons in the middle, and their twins on the right.  (So the Zhegalkin indices of the linear functions are in the columns on the right.)

| Walsh
weight  | Walsh
index  | faction
size  |  | Walsh  | patron  | twin  |  | ¬ Walsh  | patron  | twin

|
|
|
|
|
|
|
|
|
|

Q  |  |  |  |  |  |  |  | Q  |  |  |  |  |  |  |
0  | 0  | 1  |  | 0  |  | 0  |  | 0  | 0  |  | 0  |  | 3  |  | 65535  |  | 65534  | 255  |  | 1
1  | 1  | 4  |  | 2  |  | 43690  |  | 43688  | 170  |  | 2  |  | 1  |  | 21845  |  | 21846  | 85  |  | 3
2  | 3  | 6  |  | 0  |  | 26214  |  | 26208  | 102  |  | 6  |  | 3  |  | 39321  |  | 39326  | 153  |  | 7
3  | 7  | 4  |  | 2  |  | 38550  |  | 38528  | 150  |  | 22  |  | 1  |  | 26985  |  | 27006  | 105  |  | 23
4  | 15  | 1  |  | 0  |  | 27030  |  | 26752  | 104  |  | 278  |  | 3  |  | 38505  |  | 38782  | 151  |  | 279
3-ary noble indices  (juniors)

The factions are shown in ten different colors, which are variants of the quadrant colors.  (There are three shades of red and green, and two shades of blue and yellow.)

truth tables | Zhegalkin indices

The following images show that pairs of complementary factions are in the same principality.

quadrants 0 and 3

| king  | 0  | 3808  | 26752

|
|
|

king index  | 0  | 14  | 104

The patrons of the 8 even Walsh functions (quadrant 0) are the red entries in these 3 principalities.
The patrons of their complements (quadrant 3) are the green entries.

truth tables

|  |
Zhegalkin indices

|  |
quadrants 1 and 2

| king  | 5760  | 10920

|
|

king index  | 22  | 42

The patrons of the 8 odious Walsh functions (quadrant 2) are the yellow entries in these 2 principalities.
The patrons of their complements (quadrant 1) are the blue entries.

truth tables

Zhegalkin indices

### noble to prefect (linear)

[edit | edit source]

There are 256 nobles. A prefect is one of the 32 linears. Every linear is the prefect of 8 nobles.

list  (32 × 8 matrix)

This table is an extension of the one shown above (from linear to patron). The leftmost noble column is equal to that of patrons.
But here the assignment goes in the other direction. Each of the nobles on the right has the prefect on the left. E.g. the nobles 3870 and 2600 have prefect Ж 17.

The nobles are represented by the integer values of their truth tables, which are also their Zhegalkin indices.
The small numbers to their right are the juniors 0...255.
They correspond to 3-ary Boolean functions, so among them are also linears and nobles. The linears are highlighted in bold, and the nobles with a box.

The background colors of the nobles denote the noble quadrants.
The tiny red numbers are the king indices. Together with the noble quadrants they denote the noble factions.  (The eleven king indices are 0, 2, 6, 8, 14, 22, 26, 42, 44, 104, 110.)

| Walsh
weight  | Walsh
index  | ¬ | leader  | Q | prefect (linear)  | nobles

|
|
|
|
|
|

| Ж  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0 | (0) | 854  | 3  | (110) | 1334  | 5  | (110) | 1632  | 6  | (6) | 4382  | 17  | (110) | 4680  | 18  | (6) | 5160  | 20  | (6) | 6014  | 23  | (104)
2  | 3  | 0  | 1  | 0  | 26214  | 6  | 26208  | 102  | (14) | 25910  | 101  | (26) | 25430  | 99  | (26) | 24576  | 96 | (8) | 30590  | 119  | (8) | 29736  | 116  | (26) | 29256  | 114  | (26) | 28958  | 113  | (14)
2  | 5  | 0  | 2  | 0  | 23130  | 18  | 23112  | 90  | (14) | 22814  | 89  | (26) | 24446  | 95  | (8) | 23592  | 92  | (26) | 19286  | 75  | (26) | 18432  | 72 | (8) | 20064  | 78  | (26) | 19766  | 77  | (14)
2  | 6  | 0  | 3  | 0  | 15420  | 20  | 15400  | 60  | (14) | 16254  | 63  | (8) | 14622  | 57  | (26) | 14920  | 58  | (26) | 11574  | 45  | (26) | 11872  | 46  | (26) | 10240  | 40 | (8) | 11094  | 43  | (14)
2  | 9  | 0  | 4  | 0  | 21930  | 258  | 21672  | 84  | (14) | 22526  | 87  | (8) | 20894  | 81  | (26) | 21192  | 82  | (26) | 17846  | 69  | (26) | 18144  | 70  | (26) | 16512  | 64  | (8) | 17366  | 67  | (14)
2  | 10  | 0  | 5  | 0  | 13260  | 260  | 13000  | 50  | (14) | 12702  | 49  | (26) | 14334  | 55  | (8) | 13480  | 52  | (26) | 9174  | 35  | (26) | 8320  | 32  | (8) | 9952  | 38  | (26) | 9654  | 37  | (14)
2  | 12  | 0  | 6  | 0  | 4080  | 272  | 3808  | 14  | (14) | 3510  | 13  | (26) | 3030  | 11  | (26) | 2176  | 8  | (8) | 8190  | 31  | (8) | 7336  | 28  | (26) | 6856  | 26  | (26) | 6558  | 25  | (14)
4  | 15  | 0  | 7  | 0  | 27030  | 278  | 26752  | 104  | (104) | 27606  | 107  | (6) | 28086  | 109  | (6) | 28384  | 110  | (110) | 31134  | 121  | (6) | 31432  | 122  | (110) | 31912  | 124  | (110) | 32766  | 127  | (0)
1  | 1  | 1  | 0  | 1  | 21845  | 3  | 21846  | 85  | (42) | 22016  | 86 | (2) | 20576  | 80  | (2) | 21302  | 83  | (44) | 17480  | 68  | (2) | 18206  | 71  | (44) | 16766  | 65  | (44) | 16936  | 66  | (22)
1  | 2  | 1  | 1  | 1  | 13107  | 5  | 13110  | 51  | (42) | 12384  | 48  | (2) | 13824  | 54 | (2) | 13654  | 53  | (44) | 8744  | 34  | (2) | 8574  | 33  | (44) | 10014  | 39  | (44) | 9288  | 36  | (22)
1  | 4  | 1  | 2  | 1  | 3855  | 17  | 3870  | 15  | (42) | 3144  | 12  | (2) | 2600  | 10  | (2) | 2430  | 9  | (44) | 7680  | 30 | (2) | 7510  | 29  | (44) | 6966  | 27  | (44) | 6240  | 24  | (22)
3  | 7  | 1  | 3  | 1  | 26985  | 23  | 27006  | 105  | (22) | 27176  | 106  | (44) | 27720  | 108  | (44) | 28446  | 111  | (2) | 30816  | 120  | (44) | 31542  | 123  | (2) | 32086  | 125  | (2) | 32256  | 126 | (42)
1  | 8  | 1  | 4  | 1  | 255  | 257  | 510  | 1  | (42) | 680  | 2  | (2) | 1224  | 4  | (2) | 1950  | 7  | (44) | 4320  | 16  | (2) | 5046  | 19  | (44) | 5590  | 21  | (44) | 5760  | 22  | (22)
3  | 11  | 1  | 5  | 1  | 26265  | 263  | 26526  | 103  | (22) | 25800  | 100  | (44) | 25256  | 98  | (44) | 25086  | 97  | (2) | 30336  | 118  | (44) | 30166  | 117  | (2) | 29622  | 115  | (2) | 28896  | 112  | (42)
3  | 13  | 1  | 6  | 1  | 23205  | 275  | 23478  | 91  | (22) | 22752  | 88  | (44) | 24192  | 94  | (44) | 24022  | 93  | (2) | 19112  | 74  | (44) | 18942  | 73  | (2) | 20382  | 79  | (2) | 19656  | 76  | (42)
3  | 14  | 1  | 7  | 1  | 15555  | 277  | 15830  | 61  | (22) | 16000  | 62  | (44) | 14560  | 56  | (44) | 15286  | 59  | (2) | 11464  | 44  | (44) | 12190  | 47  | (2) | 10750  | 41  | (2) | 10920  | 42  | (42)
1  | 1  | 0  | 0  | 2  | 43690  | 2  | 43688  | 170  | (42) | 43518  | 169  | (2) | 44958  | 175  | (2) | 44232  | 172  | (44) | 48054  | 187  | (2) | 47328  | 184  | (44) | 48768  | 190  | (44) | 48598  | 189  | (22)
1  | 2  | 0  | 1  | 2  | 52428  | 4  | 52424  | 204  | (42) | 53150  | 207  | (2) | 51710  | 201  | (2) | 51880  | 202  | (44) | 56790  | 221  | (2) | 56960  | 222  | (44) | 55520  | 216  | (44) | 56246  | 219  | (22)
1  | 4  | 0  | 2  | 2  | 61680  | 16  | 61664  | 240  | (42) | 62390  | 243  | (2) | 62934  | 245  | (2) | 63104  | 246  | (44) | 57854  | 225  | (2) | 58024  | 226  | (44) | 58568  | 228  | (44) | 59294  | 231  | (22)
3  | 7  | 0  | 3  | 2  | 38550  | 22  | 38528  | 150  | (22) | 38358  | 149  | (44) | 37814  | 147  | (44) | 37088  | 144  | (2) | 34718  | 135  | (44) | 33992  | 132  | (2) | 33448  | 130  | (2) | 33278  | 129  | (42)
1  | 8  | 0  | 4  | 2  | 65280  | 256  | 65024  | 254 | (42) | 64854  | 253  | (2) | 64310  | 251  | (2) | 63584  | 248  | (44) | 61214  | 239  | (2) | 60488  | 236  | (44) | 59944  | 234  | (44) | 59774  | 233  | (22)
3  | 11  | 0  | 5  | 2  | 39270  | 262  | 39008  | 152  | (22) | 39734  | 155  | (44) | 40278  | 157  | (44) | 40448  | 158 | (2) | 35198  | 137  | (44) | 35368  | 138  | (2) | 35912  | 140  | (2) | 36638  | 143  | (42)
3  | 13  | 0  | 6  | 2  | 42330  | 274  | 42056  | 164  | (22) | 42782  | 167  | (44) | 41342  | 161  | (44) | 41512  | 162  | (2) | 46422  | 181  | (44) | 46592  | 182 | (2) | 45152  | 176  | (2) | 45878  | 179  | (42)
3  | 14  | 0  | 7  | 2  | 49980  | 276  | 49704  | 194  | (22) | 49534  | 193  | (44) | 50974  | 199  | (44) | 50248  | 196  | (2) | 54070  | 211  | (44) | 53344  | 208  | (2) | 54784  | 214 | (2) | 54614  | 213  | (42)
0  | 0  | 1  | 0  | 3  | 65535  | 1  | 65534  | 255  | (0) | 64680  | 252  | (110) | 64200  | 250  | (110) | 63902  | 249  | (6) | 61152  | 238  | (110) | 60854  | 237  | (6) | 60374  | 235  | (6) | 59520  | 232  | (104)
2  | 3  | 1  | 1  | 3  | 39321  | 7  | 39326  | 153  | (14) | 39624  | 154  | (26) | 40104  | 156  | (26) | 40958  | 159  | (8) | 34944  | 136  | (8) | 35798  | 139  | (26) | 36278  | 141  | (26) | 36576  | 142  | (14)
2  | 5  | 1  | 2  | 3  | 42405  | 19  | 42422  | 165  | (14) | 42720  | 166  | (26) | 41088  | 160  | (8) | 41942  | 163  | (26) | 46248  | 180  | (26) | 47102  | 183  | (8) | 45470  | 177  | (26) | 45768  | 178  | (14)
2  | 6  | 1  | 3  | 3  | 50115  | 21  | 50134  | 195  | (14) | 49280  | 192  | (8) | 50912  | 198  | (26) | 50614  | 197  | (26) | 53960  | 210  | (26) | 53662  | 209  | (26) | 55294  | 215  | (8) | 54440  | 212  | (14)
2  | 9  | 1  | 4  | 3  | 43605  | 259  | 43862  | 171  | (14) | 43008  | 168 | (8) | 44640  | 174  | (26) | 44342  | 173  | (26) | 47688  | 186  | (26) | 47390  | 185  | (26) | 49022  | 191  | (8) | 48168  | 188  | (14)
2  | 10  | 1  | 5  | 3  | 52275  | 261  | 52534  | 205  | (14) | 52832  | 206  | (26) | 51200  | 200 | (8) | 52054  | 203  | (26) | 56360  | 220  | (26) | 57214  | 223  | (8) | 55582  | 217  | (26) | 55880  | 218  | (14)
2  | 12  | 1  | 6  | 3  | 61455  | 273  | 61726  | 241  | (14) | 62024  | 242  | (26) | 62504  | 244  | (26) | 63358  | 247  | (8) | 57344  | 224 | (8) | 58198  | 227  | (26) | 58678  | 229  | (26) | 58976  | 230  | (14)
4  | 15  | 1  | 7  | 3  | 38505  | 279  | 38782  | 151  | (104) | 37928  | 148  | (6) | 37448  | 146  | (6) | 37150  | 145  | (110) | 34400  | 134  | (6) | 34102  | 133  | (110) | 33622  | 131  | (110) | 32768  | 128 | (0)
3-ary subprefects  (16 × 16 matrices)

The right side of the following table shows the same information as the table above.
Entries of one color in one matrix are the eight juniors in a row of the table above.  (Linears are highlighted in bold, and the nobles with a crown.)

The left side of the table shows the prefects of all 3-ary Boolean functions. (And the great prefects as sort keys.)
It can be seen, that the preimages of the 4-ary prefects are a refinement of the 3-ary prefects. This motivates the term subprefect.

|  | prefects  | leader  | signed
Walsh
indices  | subprefects

|
|
|
|

0  |  | 0  |  |  | 0

|

| ¬1
| 1
| ¬0
0  |  | 4  |  |  | 9

|

| ¬8
| 8
| ¬9
2  |  | 2  |  |  | 5

|

| ¬4
| 4
| ¬5
2  |  | 6  |  |  | 12

|

| ¬13
| 13
| ¬12
1  |  | 1  |  |  | 3

|

| ¬2
| 2
| ¬3
1  |  | 5  |  |  | 10

|

| ¬11
| 11
| ¬10
3  |  | 3  |  |  | 6

|

| ¬7
| 7
| ¬6
3  |  | 7  |  |  | 15

|

| ¬14
| 14
| ¬15

A more detailed version of this table can be seen here.
*[¬]: parity
*[Q]: quadrant