Linear and noble Boolean functions

Studies of Boolean functions

arity	$n$	1	2	3	4	5
linear	$2^{n+1}$	4	8	16	32	64
noble	$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).

overview

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

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

linear to patron (noble)

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)

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 noble indices 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 noble indices 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.