Seal (discrete mathematics)

From Wikiversity
Jump to navigation Jump to search

Seal is a neologism for a mathematical object, that is essentially a subgroup of nimber addition.

The addition of nimbers is the bitwise XOR of non-negative integers. For a finite set it forms the Boolean group Z2n.

A seal shall be defined as a Boolean function whose family matrix is also the matrix of an equivalence relation.
This implies, that the Boolean function is odd (i.e. that the first entry of it's truth table is true), and that it is the unique odd function in its family.

seal 1001 0000 0110 0000

The 16×16 matrix on the left is the family matrix of the Boolean function shown in red.
It also describes a partition of the set into four blocks, which are shown in different colors.
On the right the set partition is shown as a vertex coloring of the tesseract graph.   (The 4×4 matrix shows essentially the same.)


The weight of a Boolean function is be the quotient of the sum and the length of its truth table.
The weight of a seal is , where is its depth.
The unique seal with depth 0 is the tautology. The seals with depth 1 are the negated variadic XORs with one or more arguments.

triangles by arity and depth

The following triangle (left) shows the number of seals by arity (rows) and depth (columns).   The triangle on the right shows the corresponding numbers of clans.

triangle Sloane'sA022166 and its row sums Sloane'sA006116
(2-binomial coefficients)
triangle Sloane'sA076831 and its row sums Sloane'sA076766
(not to be confused with Pascal's triangle)
        0    1     2      3      4     5    6    7
                                                            
0       1                                                     1
1       1    1                                                2
2       1    3     1                                          5
3       1    7     7      1                                  16
4       1   15    35     15      1                           67
5       1   31   155    155     31     1                    374
6       1   63   651   1395    651    63    1              2825
7       1  127  2667  11811  11811  2667  127    1        29212
        0   1   2   3    4    5    6    7

0       1                                         1
1       1   1                                     2
2       1   2   1                                 4
3       1   3   3   1                             8
4       1   4   6   4    1                       16
5       1   5  10  10    5    1                  32
6       1   6  16  22   16    6    1             68
7       1   7  23  43   43   23    7    1       148

E.g. there are Sloane'sA022166(4, 2) = 35 4-ary seals of depth 2, and they fall into Sloane'sA076831(4, 2) = 6 different clans.

One may be interested in all Boolean functions in the seal families. Their number for arity n is Sloane'sA182176(n).