A dozen scores of operations.
Version of Sunday 20 January 2013.
Dave Barber's other pages.

§ 1. Like many mathematical articles, this one begins with a set, specifically S5 = { 0, 1, 2, 3, 4 }. Variables representing elements of this set are written a, b, c et cetera. Appearing also in the discussion are integers i, j, k, m and n, which are not necessarily elements of S5. Any arithmetic involving the members of S5 is done in modulo 5.

The principal undertaking is to introduce 240 ("dozen score" = 12 × 20) binary operations over this set, the operations satisfying two cancellation properties that can be explained after some notation is established. Each operation is denoted by a nonnegative integer followed by the nabla symbol: 0∇, 1∇, 2∇ … 239∇. Variables representing operations are written Z, Y, X et cetera. For an example of such an operation, here is the table that defines 58∇:

58∇second input
01234
first
input
010432
132104
204321
321043
443210

First-order cancellativity (FOC) is the well-known property where:

For the dozen-scores, FOC can also be described as: As a result of FOC, no value is repeated within any row of the table, nor within any column. A Latin square results.

Second-order cancellativity (SOC) is achieved when:

The effect of SOC is that no value can be repeated on a diagonal that "wraps around"; this is reminiscent of the toroidal topology.

There are 240 binary operations on S5 that satisfy both FOC and SOC, and they are the target of this report. They are all listed in a large table, and formatted as a C-language array.

This report generally uses prefix notation for applications of the operations, but infix notation is equally valid and sometimes clearer:

Z (a, b) ⇔ a Z b

Parentheses and the comma are retained in the prefix notation to reduce confusion, because the arguments are sometimes expressions involving more than one symbol.


§ 2. The nabla numbers of the dozen-scores are based on an obvious manner of lexicographic ordering. The table below is explicit about how the properties of operations m∇ and n∇ are used to establish a relation between integers m and n.

dozen-score lexicographic ordering
first
criterion
• If m∇(0, 0) < n∇(0, 0), then m < n.
• If m∇(0, 0) > n∇(0, 0), then m > n.
• If m∇(0, 0) = n∇(0, 0), then use the second criterion.
second
criterion
• If m∇(0, 1) < n∇(0, 1), then m < n.
• If m∇(0, 1) > n∇(0, 1), then m > n.
• If m∇(0, 1) = n∇(0, 1), then use the third criterion.
third
criterion
• If m∇(0, 2) < n∇(0, 2), then m < n.
• If m∇(0, 2) > n∇(0, 2), then m > n.
• If m∇(0, 2) = n∇(0, 2), then use the fourth criterion.
fourth
criterion
• If m∇(0, 3) < n∇(0, 3), then m < n.
• If m∇(0, 3) > n∇(0, 3), then m > n.
• If m∇(0, 3) = n∇(0, 3), then use the fifth criterion.
fifth
criterion
• If m∇(0, 4) < n∇(0, 4), then m < n.
• If m∇(0, 4) > n∇(0, 4), then m > n.
• If m∇(0, 4) = n∇(0, 4), then use the sixth criterion.
sixth
criterion
• If m∇(0, 4) < n∇(0, 4), then m < n.
• If m∇(0, 4) > n∇(0, 4), then m > n.
• If m∇(0, 4) = n∇(0, 4), then m = n.


§ 3. The dozen-scores sometimes do, and sometimes do not, exhibit familiar algebraic properties.

Because of SOC, the operations are strictly non-commutative: if Z (a, b) equals Z (b, a), then a must equal b.

The standard associative property always fails, but some multiple-operation versions succeed. Also a distributive law works for some combinations of operations. These are discussed in section 6 below.

No operations have a two-sided identity element, although some have a left identity, which means that there exists an a such that Z (a, b) = b for all b. Some others have the corresponding right identity. FOC guarantees that when such a one-sided identity exists, it is unique. Examples:

193∇second input
01234
first
input
040123
123401
201234
334012
412340
151∇second input
01234
first
input
030241
141302
202413
313024
424130
left identity = 2right identity = 1

Only two operations are idempotent in that Z (a, a) = a:

46∇second input
01234
first
input
0 04321
121043
243210
310432
432104
21∇second input
01234
first
input
0 02413
141302
230241
324130
413024


§ 4. One operation can be systematically altered into other. If X (a, b) = W (a, b) for all a and b, the identity shorthand XW is often used.

§ 4a. Three self-inverse transformations:

Examples, where the immobile elements are highlighted:

100∇second input
01234
first
input
020314
114203
203142
342031
431420
110∇second input
01234
first
input
021043
104321
232104
310432
443210
167∇second input
01234
first
input
031420
142031
203142
314203
420314
213∇second input
01234
first
input
041302
130241
224130
313024
402413
100∇ 110∇ ≡ 100∇T 167∇ ≡ 100∇V 213∇ ≡ 100∇H

The elements unmoved in transposition lie on the principal diagonal.

Successive superscripts are evaluated in the natural fashion: ZHTV ≡ ((ZH)T)V.

Two notable relations are Z (b, a) = ZT (a, b) and ZTHZVT.

The vertical and horizontal reversing operations suggest establishing a unary reversing operation, superscripted with I (for inverse) to avoid confusion with an operation introduced in the next section:

a 0 1 2 3 4
aI = 4 − a 4 3 2 1 0

Thus Z (a, b) = ZV (aI, b) = ZH (a, bI) = ZHV (aI, bI) = ZVH (aI, bI).

§ 4b. Two cyclical transformations:

Examples:

62∇second input
01234
first
input
012043
104312
231204
320431
443120
107∇second input
01234
first
input
020431
143120
212043
304312
431204
161∇second input
01234
first
input
031204
120431
243120
312043
404312
62∇ 107∇ ≡ 62∇R+3 161∇ ≡ 62∇C+4

These four statements are equivalent:

Row and column rotations are not independent:

There is not an transformation to in general exchange two rows, or two colums, as this could disturb SOC.

§ 4c. Elements of the table can be pairwise swapped, as denoted by a superscript S and two numbers from { 0, 1, 2, 3, 4 }. Only the output values, not the input values, are changed. The highlighted squares of this example show the effect of swapping:

1∇second input
01234
first
input
001234
134012
212340
340123
423401
43∇second input
01234
first
input
004231
131042
242310
310423
423104
1∇ ≡ 43∇S1,4 43∇ ≡ 1∇S1,4

The swap being pairwise, ZSm,nZSn,m. If m = n, nothing happens.

Canonization (or canonicalization) is the process of performing a sequence of pairwise swaps ultimately producing an operation where Z(0, a) = a; this condition is equivalent to saying that 0 is a left identity of Z. Such a canonical form helps to reveal the "shape" of the operation. Anywhere between zero and four swaps will be necessary. Example:

159∇second input
01234
first
input
0 31042
142310
210423
323104
404231
7∇second input
01234
first
input
0 01342
142013
213420
320134
434201
3∇second input
01234
first
input
0 01243
143012
212430
330124
424301
1∇second input
01234
first
input
0 01234
134012
212340
340123
423401
159∇ 7∇ ≡ 159∇S0,3 3∇ ≡ 7∇S3,2 1∇ ≡ 3∇S4,3

For the dozen-scores:

All of the dozen-scores are canonizable to only two operations, namely 0∇ or 1∇. However, canonization becomes very helpful in managing the complexity that arises in generalizations, as when the set has more than five members or the operations have more than two inputs.

If Z reduces to 0∇ and Y reduces to 1∇, then Z and Y taken together form a Graeco-Latin square. Each cell of the table contains a different ordered pair. Example:

60∇, 104∇ second input
01234
first
input
0 1, 22, 00, 43, 14, 3
10, 13, 34, 21, 02, 4
24, 01, 42, 10, 33, 2
32, 30, 23, 04, 41, 1
43, 44, 11, 32, 20, 0


§ 5. The dozen-scores can be partitioned into six subsets (quadragintas) of 40 operations each, as shown in the tables below.

quadraginta A
0∇192∇180∇129∇66∇
110∇59∇47∇239∇173∇
167∇101∇89∇26∇218∇
213∇150∇138∇72∇21∇
181∇128∇67∇1∇193∇
238∇172∇111∇58∇46∇
20∇212∇151∇139∇73∇
100∇88∇27∇219∇166∇
quadraginta B
2∇144∇228∇141∇71∇
108∇54∇35∇191∇221∇
215∇105∇77∇38∇170∇
165∇198∇126∇84∇17∇
229∇140∇70∇3∇145∇
190∇220∇109∇55∇34∇
16∇164∇199∇127∇85∇
104∇76∇39∇171∇214∇
quadraginta C
5∇194∇132∇177∇78∇
158∇57∇42∇227∇125∇
119∇149∇93∇14∇230∇
209∇102∇186∇60∇33∇
133∇176∇79∇4∇195∇
226∇124∇159∇56∇43∇
32∇208∇103∇187∇61∇
148∇92∇15∇231∇118∇
quadraginta D
6∇96∇216∇189∇83∇
156∇50∇23∇143∇233∇
210∇153∇65∇36∇122∇
117∇203∇174∇86∇29∇
217∇188∇82∇7∇97∇
142∇232∇157∇51∇22∇
28∇116∇202∇175∇87∇
152∇64∇37∇123∇211∇
quadraginta E
9∇146∇120∇225∇90∇
206∇53∇30∇179∇137∇
114∇197∇81∇12∇182∇
161∇107∇234∇62∇45∇
121∇224∇91∇8∇147∇
178∇136∇207∇52∇31∇
44∇160∇106∇235∇63∇
196∇80∇13∇183∇115∇
quadraginta F
11∇98∇168∇237∇95∇
204∇48∇18∇131∇185∇
162∇201∇69∇24∇134∇
113∇155∇222∇74∇41∇
169∇236∇94∇10∇99∇
130∇184∇205∇49∇19∇
40∇112∇154∇223∇75∇
200∇68∇25∇135∇163∇

The following formulas show more specifically how the dozen-scores within a column or row of a quadraginta table are connected, by giving as examples some relations within the first column and the first row of quadraginta B:

2∇ ≡ 16∇T229∇V190∇H
108∇ ≡ 104∇T190∇V229∇H
215∇ ≡ 229∇T104∇V 16∇H
165∇ ≡ 190∇T 16∇V104∇H
229∇ ≡ 215∇T 2∇V108∇H
190∇ ≡ 165∇T108∇V 2∇H
16∇ ≡ 2∇T165∇V215∇H
104∇ ≡ 108∇T215∇V165∇H

2∇ ≡ 144∇C+1 ≡ 228∇C+2 ≡ 141∇C+3 ≡ 71∇C+4

The operations in quadraginta A exhibit linearity in the following sense: for each operation there exist i, j and k such that Z(a, b) = i × a + j × b + k. With 128∇ for instance, i = 3, j = 1, and k = 2:

128∇second input
01234
first
input
023401
101234
234012
312340
440123

For a linear operation Z, the coëfficients are easily found:

With linear operations, four relations can never occur, because they would be connected with a violation of FOC or SOC:

In the next section are more examples of how quadraginta A is distinguished from the others.


§ 6. Combining operations.

§ 6a. There are 48,000 combinations (out of 2404 possibilities) of operations that satisfy this four-operation generalization of the associative law, here written in both prefix and infix notations:

Z (a, Y (b, c)) = X (W (a, b), c)
a Z (b Y c) = (a W b) X c

Necessary conditions are that operations Z and X must come from the same quadraginta, and operations Y and W must come from quadraginta A. Never does the particular case ZYXW succeed.

§ 6b. There are 576,000 combinations (of 2404) of operations that satisfy this next version of associativity:

Z (Y (a, b), c) = X (W (a, b), c)
(a Y b) Z c = (a W b) X c

A necessary condition is that Z and X must come from the same quadraginta. Always successful is ZYXW.

§ 6c. There are 160 combinations (of 2402) of operations, all from quadraginta A, that satisfy this distributive law:

Z (Y (a, b), c) = Y (Z (a, c), Z (b, c))
(a Y b) Z c = (a Z c) Y (b Z c)

Only 21∇ and 46∇, the idempotent operations, fulfill the constraint YZ.

§ 6d. A general approach to composite operations is lengthy enough to need its own page.




§ 7. Thus far, great attention has been paid to a collection of 240 operations over the set S5 = { 0, 1, 2, 3, 4 }. Why not the more general Sn = { 0, 1, 2 … n − 1 }? There is an important result about binary operations over Sn that are first- and second-order cancellative:

(Pertinent citations are found at OEIS, in the context of the n queens on a toroidal chess board problem.) Thus S2, S3 and S4 are excluded. The triviality of S1 = { 0 } leaves S5 to be the simplest case with any substance, and that is why it was selected for detailed examination in this report. Still, a brief mention of the larger sets is in order.

For each of S7 and S11, there are two substantively different configurations. Examples, in canonical form, appear below preceded by 1∇ for comparison:

1∇second input
01234
first
input
001234
134012
212340
340123
423401
1∇(a, b) = 1∇(a + 1, b + 2)

U1second input
0123456
first
input
00123456
15601234
23456012
31234560
46012345
54560123
62345601
U2 second input
0123456
first
input
00123456
14560123
21234560
35601234
42345601
56012345
63456012
U1(a, b) = U1(a + 1, b + 2) U2(a, b) = U2(a + 1, b + 3)

U3second input
012345678910
first
input
0012345678910
1910012345678
2789100123456
3567891001234
4345678910012
5123456789100
6100123456789
7891001234567
8678910012345
9456789100123
10234567891001
U4second input
012345678910
first
input
0012345678910
1891001234567
2567891001234
3234567891001
4100123456789
5789100123456
6456789100123
7123456789100
8910012345678
9678910012345
10345678910012
U3(a, b) = U3(a + 1, b + 2) U4(a, b) = U4(a + 1, b + 3)

All the other FOC and SOC operations over S7 and S11 can be found by making the obvious adaptations to the following transformations that were defined for S5:

When n ≤ 11, each operation over Sn can, through canonization, be transformed into a linear function (section 5). However, this property no longer applies when n ≥ 13, the point at which the operations become far more complicated. The following is an operation over S13 that, although it is in canonical form, is conspicuously non-linear:

U5second input
0 1 2 3 4 5 6 7 8 9 101112
first
input
00123456789101112
19101112012345678
25678910111201234
31201234567891011
42345678910111201
57891011120123456
61011120123456789
74567891011120123
81234567891011120
98910111201234567
101112012345678910
113456789101112012
126789101112012345
U5(a, b) = U5(a + m, b + n) cannot be satisfied


§ 8. The three-operand case can also be glimpsed. The following definitions are practically inevitable, and assume modulo-n arithmetic when the operation is over Sn:

FOC is satisfied when:

SOC is satisfied when:

Third-order cancellativity (TOC) is satisfied when:

Within the formulas there are more plus signs than minus signs, but this is not a problem because n itself can be positive or negative,.

Some existences: