View source for Mentors of Boolean functions

{{Boolf header}}
__NOTOC__

The mentor is a rather dubious [[Soft properties of Boolean functions|soft property]] of a BF. But it seems surprisingly interesting.<br>
It is found in three steps: Creating a [[Boolf-hard#family|family matrix]], getting the senior [[Noble Boolean functions|nobles]] of its rows, and getting their [[Boolf-hard#prefect|prefects]].<br>
The first digits of the prefects form the mentor.

{{Mentors of Boolean functions/illustrated examples 3-ary}}

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

{{Mentors of Boolean functions/illustrated examples 4-ary}}

==Walsh permutations==

A Boolean function has a unique mentor for a given arity.  The map between mentors can be expressed by four different [[Walsh permutation]]s.<br>
<small style="opacity: .7;">(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.)</small><br>
In all there are six Walsh permutations, which shall be denoted by Cyrillic letters: &nbsp;&nbsp;&nbsp;
Ж <small>(Zhe)</small>, &nbsp;&nbsp;&nbsp; Ч <small>(Che)</small>, Ш <small>(Sha)</small>, &nbsp; Ю <small>(Yu)</small>, Я <small>(Ya)</small>, &nbsp;&nbsp;&nbsp; Щ <small>(Shcha)</small><br>
Their degree is <math>d = 2^{arity}</math>, i.e. they correspond to invertible binary <math>d \times d</math> matrices.<br>
<small style="opacity: .7;">(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 matrix|Zhegalkin index]].)</small>

{{Mentors of Boolean functions/four WP relationships}}

Ч 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. <small style="opacity: .5;">(See [[c:File:Variadic5 antipode; ESAND (ESNOR twin).svg|image]].)</small><br>
The matrix of Ш is almost the same, but with the top right entry inverted.<br>
The matrix of Ч is a family matrix. Its top row is related to that of the Ш matrix. <small>The calculation involves the Zhegalkin twin and reversing the truth table.</small>

{{Mentors of Boolean functions/code Che matrix}}

{{Collapsible START|relationship between the matrix patterns|collapsed gap-above gap-below}}
The red family matrix has the pattern of Ч.<br>
The green matrix shows the twins of the red rows, and has the pattern of Ю and Я.<br>
The blue matrix shows the twins of the green columns, and has the pattern of Ш.<br>
[[File:Family of Zhe 38504.svg|400px|center]]
{{Collapsible END}}

{{Mentors of Boolean functions/code WP vectors}}

See the fixed points of Ч and Ш ordered by weight: [[Template:Boolf weight triangle; fixed points of Che|Ч]], [[Template:Boolf weight triangle; fixed points of Sha|Ш]]

===1-ary===

The permutations are all six Walsh permutations of degree 2. {{spaces|5}} Ч = (0, 2, 1, 3) {{spaces|5}} Ш = (0, 1, 3, 2) {{spaces|5}} Щ = I <small>(neutral permutation)</small>

{{Collapsible START|permutations|wide collapsed}}
{{Mentors of Boolean functions/illustrated WP 1-ary}}
{{Collapsible END}}

===2-ary===

Ч = Ш = I <small>(neutral permutation)</small> {{spaces|5}} Ю = Я = Ж {{spaces|5}} <small>Щ = (0, 1, 2, 3, &nbsp; 4, 5, 6, 7, &nbsp; 9, 8, 11, 10, &nbsp; 13, 12, 15, 14)</small>

===3-ary===

{{Mentors of Boolean functions/illustrated WP 3-ary}}

{{Collapsible START|code|collapsed light gap-above}}
{{Mentors of Boolean functions/code/3-ary}}
{{Collapsible END}}

{{Mentors of Boolean functions/small WP example 199}}

Permutation Я is related to quarter sharpness, which is seen in [[Boolf prop/3-ary/gradual sharpness 1 (quarter sharpness)|these images]].

===4-ary===

{{Mentors of Boolean functions/illustrated WP 4-ary}}

{{Collapsible START|code|collapsed light gap-above gap-below}}
{{Mentors of Boolean functions/code/4-ary}}
{{Collapsible END}}

==seminars==

The mentor is not simply a bijection between Boolean functions, but between the truth tables for a given arity.<br>
The permutation from Zhegalkin indices to those of their ''n''-ary mentors is '''Ш<sub>''n''</sub>'''. The beginning of Ш<sub>''n''+1</sub> is '''Щ<sub>''n''</sub>'''. <small style="opacity: .5; font-size: 60%;">([[w:Shcha|This letter]] has a little hook on the right.)</small><br>
These two permutations are very similar. They are equal in the first half, and differ by exchanged neighbors in the second.

Neighboring Zhegalkin indices <small>(i.e. 2·''n'' and 2·''n''+1)</small> denote complements.<br>
So although there is no mentor bijection between Boolean functions, there is one between pairs of complements.<br>
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''.<br>
The Zhegalkin indices in a big seminar are <math>\{ a, a+1, b, b+1 \}</math> with even <math>a</math> and <math>b</math>, so it can be represented by the pair <math>(a, b)</math>.<br>
<small>An example of a seminar is {138, 139, 156, 157}, represented as (138, 156). See [[c:File:Set of 3-ary Boolean functions 12855504354077768210885020350402125463028803369886765232947200.svg|image]]. <small style="opacity: .5;">In the permutation it is represented by the pair (69, 78).</small></small>

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

{{Collapsible START|mentor permutation|collapsed wide}}
[[File:Mentors 4; seminar permutation.svg|thumb|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:
<source lang="python" style="font-size: 60%;">
[ 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]
</source>

The permutation for arity 4 corresponds to the 15×15 matrix shown on the right.<br>
<small style="opacity: .5; font-size: 60%;">It is described by this vector: (1, 2, 4, 8, 16, 32, 75, 128, 256, 512, 1155, 2048, 4233, 8330, 19252)</small>

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

For arity 3 the Boolean functions in big seminars are the sharp ones <small>(i.e. those with odd weight)</small>. See {{Boolf prop 3-ary|seminar|images}}.

<small>For a given arity, each seminar is part of a {{Boolf prop 3-ary|chunky seminar}}. For arity 3 they all have size 16. {{Mentors of Boolean functions/example chunky seminar}}</small>

==chains==

The permutations Ю and Я have fewer fixed points and longer cycles than Ч and Ш.<br>
A cycle of Ю shall be called '''chain'''. <small style="opacity: .5;">(Cycles of Я are the same, but reversed.)</small><br>
The XOR of all entries of a chain is one of the fixed points, and shall be called '''anchor'''. The fixed points are [[Noble Boolean functions|nobles]].

'''tables of chains:''' [[Template:Mentors of Boolean functions/chains/3-ary|3-ary]] <small>(4 fixed points)</small>, [[Template:Mentors of Boolean functions/chains/4-ary|4-ary]] <small>([[Template:Mentors of Boolean functions/chains/4-ary/fixed|8 fixed points]])</small>

'''3-ary partitions:'''
{{Boolf prop 3-ary|chain}},
{{Boolf prop 3-ary|chain length}},
{{Boolf prop 3-ary|chain quadrants}},
{{Boolf prop 3-ary|reduced chain quadrants}},
{{Boolf prop 3-ary|chunky chain}},
{{Boolf prop 3-ary|anchor}}


[[Category:Mentors of Boolean functions]]