View source for Seal (discrete mathematics)

{{Boolf header}}
<templatestyles src="Collapsible with classes/style.css" />
__NOTOC__
'''''Seal''''' is a neologism for a mathematical object, that is essentially a subgroup of {{w|nimber}} addition.<br>
<span style="opacity: .7;">The addition of nimbers is the [[w:Bitwise_operation#XOR|bitwise XOR]] of non-negative integers.
For a finite set <math>\{0,...,2^n-1\}</math> it forms the [[w:Elementary abelian group|Boolean group]] {{w|Cyclic group|Z}}<sub>2</sub><sup>n</sup>.</span>

A seal shall be defined as a Boolean function whose [[Families of Boolean functions#family matrix|family matrix]] is also the matrix of an {{w|equivalence relation}}.<br>
This implies, that the Boolean function is [[Boolf-term#odd|odd]] <small>(i.e. that the first entry of it's truth table is ''true'')</small>, and that it is the unique odd function in its [[Boolf-hard#family|family]].

A seal is also a periodic set partition. The members of its family shall be called its '''blocks'''.

{| class="collapsible-with-classes collapsible open"
!colspan="3"| seal 1001 0000 0110 0000 &nbsp; {{zhe|4471}}
|-
|colspan="3"|
This seal has adicity 4, and is shown with <span style="opacity: .7;">(the lowest possible)</span> arity 4, i.e. with a truth table of length 16.<br>
The 16×16 matrix on the left is its family matrix.<br>
It also describes a {{w|Partition of a set|partition}} of the set <math>\{0 \ldots 15\}</math> into four blocks, which are shown in different colors.<br>
On the right the set partition is shown as a {{w|graph coloring|vertex coloring}} of the {{w|tesseract}} graph. &nbsp; <small>(The 4×4 matrix shows essentially the same.)</small> 
|- style="vertical-align: top;"
| [[File:4-ary seal Zhe 4471, matrix.svg|270px]]
|style="padding-left: 100px;"| [[File:4-ary seal Zhe 4471, tesseract.svg|270px]]
| [[File:4-ary seal Zhe 4471, diamond.svg|150px]]
|}

<span style="opacity: .5;">The weight of a Boolean function is be the quotient of the sum and the length of its truth table.</span><br>
The weight of a seal is <math>\frac{1}{2^d}</math>, where <math>d</math> is its '''depth'''.<br>
The unique seal with depth 0 is the tautology. The seals with depth 1 are the negated variadic {{w|exclusive or|XOR}}s with one or more arguments.

{{Collapsible START|negated binary Walsh matrix|collapsed light gap-below}}
The seals with depth 1 are the positive rows of a negated binary {{w|Walsh matrix}}. &nbsp; <small>(The tautology with depth 0 is in the top row.)</small>
[[File:Variadic logical NXOR.svg|thumb|left]]
{{Collapsible END}}

==cccurences==

The fixed points of [[Walsh permutation]]s are seals.<br>
The symmetry of Boolean functions is related to seals.

==equivalenc classes==
===house===

Each seal belongs to a {{boolf-prop|faction}}, which shall be called its '''house'''. A house can also be seen as a {{boolf-prop|clan}} of seal blocks.<br>
<small>So a house can the represented by the [[smallest Zhegalkin index]] of the faction or the clan. &nbsp; <span style="opacity: .5;">(That of the faction is easier to calculate.)</span></small>

==antipode==

The seals with arity ''a'' form a symmetric Hasse diagram, whose top node is the tautology.<br>
From top to bottom the layers are ''depth'' = 0...''a''. From bottom to top they are ''rank'' = 0...''a''. The number of seals in layer ''n'' is <math>\mathrm{Oak}(a, n)</math>.<br>
For the given arity each seal has a Walsh spectrum. It's non-zero entries are <math>2^{rank}</math> <small>(the weight of the seal's finite truth table)</small>.<br>
Their pattern describes another seal in the opposite layer of the Hasse diagram, which shall be called its '''''antipode'''''.<br>
When a seal in house ''x'' has an antipode in house ''y'', then all seals in ''x'' have antipodes in ''y''.
Each house has an antipode for a given arity.

The following seal is the antipode of the example shown above. Their depth (and rank) is 2, and both are on the middle layer of the Hasse diagram.

{| class="collapsible-with-classes collapsible collapsed"
!colspan="3"| seal 1000 1000 0001 0001 &nbsp; {{zhe|1807}}
|-
|colspan="3"|
The Walsh spectrum for arity 4 is (4, 0, 0, 4, 0, 0, 0, 0, 0, 4, 4, 0, 0, 0, 0, 0).<br>
Its non-zero entries form the pattern <code>1001 0000 0110 0000</code> of the antipode Ж 4471.
|- style="vertical-align: top;"
| [[File:4-ary seal Zhe 1807, matrix.svg|270px]]
|style="padding-left: 100px;"| [[File:4-ary seal Zhe 1807, tesseract.svg|270px]]
| [[File:4-ary seal Zhe 1807, diamond.svg|150px]]
|}

1001 0000 0000 1001 {{zhe|1911}} has cohort {0, 3, 12, 15}. So for arity 4 it is its own antipode. <small>(See [[c:File:4-ary cohort, 1001 0000 0000 1001.svg|this]] file.)</small>

==cohort and legion==

While a seal has different antipodes for each arity, they all start with the same binary pattern, and then continue with zeros.<br>
In other words, all antipodes of a seal can be described as the same finite set of integers <small>(which corresponds to an entry of sequence ''Rose'')</small>.<br>
This set of integers shall be called '''''cohort'''''. Every cohort belongs to a '''legion'''. <small style="opacity: .7;">[[Legion and cohort of Boolean functions|Cohort and legion]] are properties of Boolean functions in general &ndash; not just of seals.</small>

The cardinalities of cohort and legion are a powers of two.<br>
The exponent for the cohort is '''depth'''. The exponent for the legion shall be called '''''gravity'''''.<br>
<small>Gravity is similar to valency. The pyramids ''TwistedLiana'' and ''Lonicera'' have it as one of their dimensions.</small>

==integer representations==

{{Collapsible START|truth tables and Zhegalkin indices &nbsp; <small>(Hasse diagrams of Venn diagrams)</small>|collapsed wide gap-below}}

For both arities the green integers on the right correspond to the same seal on the left.<br>
E.g. the green 1 corresponds to the tautology, the green 7 to <math>\neg(A \oplus B)</math>, and the green 15 to <math>\neg(A \lor B)</math>.

{| class="wikitable" style="width: 100%; text-align: center;"
!
! truth tables &nbsp; <small>(entries of ''Rose'')</small>
! Zhegalkin indices &nbsp; <small>(entries of ''Tulip'')</small>
|-
! arity 2
| [[File:2-ary seals as Venn diagrams.svg|170px]]
| [[File:2-ary seals as Venn diagrams, twins.svg|170px]]
|-
! arity 3
| [[File:3-ary seals as Venn diagrams.svg|400px]]
| [[File:3-ary seals as Venn diagrams, twins.svg|400px]]
|}
{{Collapsible END}}

{{Collapsible START|sequences ''Rose'' and ''Tulip''|collapsed wide}}
{{Seal integer representations}}
{{Collapsible END}}

==quantities==

{{Collapsible START|overview of sequences, triangles and pyramids|collapsed wide strong gap-below}}
{{Seal sequences}}
{{Collapsible END}}

<!------------------------------------------------------------------------------------------>
{{Collapsible START| seals and houses by ''arity'' and ''depth'': &nbsp; symmetric triangles ''Oak'' and ''Elm'' |collapsed wide light followed}}
The triangle ''Oak'' (left) shows the number of seals by arity (rows) and depth (columns). These are {{w|Gaussian binomial coefficient|2-binomial coefficients}}. &nbsp; <small style="opacity:.7;">Arity ''n'' is short for [[Boolf-term#adicity|adicity]]  &le; ''n''.</small><br>
The triangle ''Elm'' (right) shows the corresponding numbers of equivalence classes. &nbsp; <small style="opacity: .5;">(Not to be confused with Pascal's triangle.)</small>
{{Seal triangles Oak and Elm}}
E.g. there are <math>\mathrm{Oak}(4, 2) = 35</math> 4-ary seals of depth 2, and they belong to <math>\mathrm{Elm}(4, 2) = 6</math> different equivalence classes.
{{Collapsible END}}

{{Collapsible START| blocks ''a''&hairsp;×&hairsp;''d'': &nbsp; triangles ''MapleMinor'' and ''Sycamore'' |collapsed wide followed}}
{{Seal triangles MapleMinor and Sycamore|a|d}}
{{Collapsible END}}

{{Collapsible START| seals ''a''&hairsp;×&hairsp;''d'': &nbsp; triangles ''Oak'' and ''Maple'' |collapsed wide followed}}
{{Seal triangles Oak and Maple|a|d}}
{{Collapsible END}}

{{Collapsible START|houses ''a''&hairsp;×&hairsp;''d'': &nbsp; triangles ''Elm'' and ''Lime''|collapsed wide}}
{{Seal triangles Elm and Lime|a|d}}
{{Collapsible END}}

<!------------------------------------------------------------------------------------------>
{{Collapsible START|seals ''a''&hairsp;×&hairsp;''v'': &nbsp; triangles ''Ash'' and ''Aspen''|collapsed wide followed gap-above}}
{{Seal triangles Ash and Aspen|a|v}}
{{Collapsible END}}

{| class="collapsible-with-classes collapsible collapsed wide light"
!colspan="2"| triangle ''Birch'' with row sums ''Aster''
|-
|colspan="2"|
These sequences count seals whose adicity and valency are equal.<br>
<math>\mathrm{Aster}(n)</math> is the number of seals whose adicity and valency is ''n''.
Among them <math>\mathrm{Birch}(n, d)</math> are those with depth ''d''.
|-
| {{Seal triangle Birch|n|d}}
| 
{{multiple image
 | align = right  | total_width = 800
 | image1 = Number pyramid Liana; arity minus valency is 0.png
 | image2 = Number pyramid Ivy; adicity minus valency is 0.png
 | footer = ''Birch'' as a side of ''Liana'' and ''Ivy''
}}
|}

<!------------------------------------------------------------------------------------------>
{{Collapsible START|illustrated examples: {{spaces|5}} ''Oak'', ''Maple'' <small>(seals with arity 5)</small> {{spaces|5}} ''MapleMinor'', ''Sycamore'' <small>(blocks with adicity 4)</small>|collapsed strong wide gap-above gap-below}}
{{Seal triangle Maple examples}}
{{Collapsible END}}

===number pyramids===

See [[pyramid Liana]]. These pyramid pairs are refinements of ''Oak'' and ''Maple'', adding axes for valency and gravity.

[[Category:Seal (discrete mathematics)]]