Some ternary quasigroups over small sets.
Version of Wednesday 12 July 2017; originally published in 2010. Dave Barber's other topics. This is page one, with sections 1 through 4. Page two contains sections 5 through 10. Page three contains sections 11 and 12. Page four contains sections 13 through 16. |
Contents:
§1 Introduction. A ternary quasigroup (TQG for short) consists of two things: a set; and a cancellative operation that consumes three inputs and generates one output, all four of them elements of the set. How cancellativity is extended to ternary operations will be explained after some fundamentals are established.
§1A. The TQG's set need not be large to provide interesting results: a cardinality (C) of four is quite enough. Elements will be called a, b, c, et cetera — these constants are not assumed to have any properties except that no two of them are equal. Variables representing these constants have names such as p, q and r, sometimes subscripted.
Generic operations have names like O, N and M. In contrast, the method of denoting a particular ternary operation is to write two numbers separated by a colon. The first indicates the cardinality, and the second a particular operation; an example is 4:41250. Numerical names are attached to operations in an unsurprising lexicographical manner; details are supplied later.
The usual notation for invoking a ternary operation is O (a, b, c); but the condensed form Oabc, written when no confusion ensues, helps stem a profusion of parentheses in complicated expressions. Syntacticians will observe that if each operation and operand is represented by a single distinct character, this condensed prefix notation is unambiguous when applied to nested operation invocations. Examples:
OabNcde =
O (a, b, Ncde) = O (a, b, N (c, d, e)) |
ONabcdMefg =
O (Nabc, d, Mefg) = O (N (a, b, c), d, M (e, f, g)) |
ONabcdMeLfghi =
O (Nabc, d, MeLfghi) = O (N (a, b, c), d, M (e, Lfgh, i)) = O (N (a, b, c), d, M (e, L (f, g, h), i)) |
Occasionally mentioned in this report are binary quasigroups (BQGs for short). Examples of names for their generic operations are F and G; the notation for particular operations uses two colons, such as 4::25.
The not-equal sign ≠ will appear in several places throughout this report. It will always mean "strictly not equal" rather than "not necessarily equal".
§1B. A ternary operation O is cancellative if it meets this criterion:
In other words:
The gist is that changing exactly one input assuredly changes the output. This restriction is an adaptation of the feature that distinguishes quasigroups from other magmata.
Noteworthy is that the Latin square can be extended to three dimensions creating a Latin cube, which is precisely what the body of each operation's Cayley table turns out to be (but see a caution). The number of possible operations grows quickly (faster than the cube of a factorial) as C increases; see Potapov and Krotov. The numbers in the table below come from OEIS A098679:
C | number of operations |
---|---|
1 | 1 |
2 | 2 |
3 | 24 |
4 | 55,296 |
5 | 2,781,803,520 |
6 | 994,393,803,303,936,000 |
It is feasible to list all the operations for C ≤ 3, but only a selection for C = 4. Complication grows quickly as C increases, and for many kinds of investigation:
Dimitrova and Mihajloska also examine the C = 4 case, in the context of cryptography.
§1C. The notions here can easily be extended to operations that take four or more inputs. However, this report concentrates on three-input operations because three are enough to convey all the important ideas, and to permit tractable examples. Operations with four or more inputs would add complication but not substance.
In the other direction, two-input operations are insufficient because not all three-input operations can be decomposed into two successive invocations of two-input operations (example). This lack of decomposability is a primary motivation for producing this report; otherwise the ternary operations could simply be studied in terms of their binary components, and binary operations are already covered extensively in the algebraic literature.
Another reason that binary operations do not suffice is that the notion of identity element is far simpler with two inputs than with three or more.
The operations studied here are unrelated to the ternary operator of many computer programming languages. Another ternary operator is the scalar triple product of vector analysis, but it too does not relate to TQGs because while the inputs to this operation are vectors, the output is a scalar which is a different data type. For a ternary operation where the output data type is the same as that of the inputs, see the 4-dimensional cross product, although it is not cancellative.
§2 Some standard laws. Binary operations are often commutative, associative, distributive, medial, or idempotent. These notions can be generalized to ternary operations as follows.
§2A. Commutativity, or c'ty for short. The gist of this property is that the output of an operation is independent of the sequence of its inputs. In by comparison the addition of real numbers, 7 + 9 = 9 + 7. With three inputs instead of two, several possibilities arise:
Under a permutation of variable names, the cyclicity criterion can be written O (r, p, q) = O (q, r, p). This means that O (p, q, r) also equals O (q, r, p). In other words, one direction of cyclical c'ty logically implies the other. Otherwise, it would have been necessary to distinguish the following:
§2B. Associativity (a'ty). Under this property, the value of the output is independent of the grouping of inputs. With real numbers, an example is (7 + 8) + 9 = 7 + (8 + 9). The obvious extension to ternary operations yields these:
When C ≤ 4, an operation that has sinisterior a'ty also has exterior and dexterior; similarly, dexterior a'ty entails exterior and sinisterior. An example of full a'ty is 4:1632, while 4:17842 has exterior only.
With a fully associative operation, one can reasonably introduce the notion of a ternary semigroup. Note that some authors term a fully associative semigroup a group, despite the possibility in this ternary case that no single value serves as an identity. The fully associative operations, some tabulated here, constitute a relatively small subset of all operations when C ≥ 3.
With seven inputs there are twelve possible associations, and the number grows quickly with more than seven.
§2C. Power-associativity (pa'ty). This, perhaps the weakest form of a'ty, is like ordinary a'ty except that all five inputs are equal:
At one extreme is the a'ty of section 2B, where all the inputs can be different; at the other extreme is pa'ty, where all the inputs must be equal. Between those are adaptations of alternative associativity which, in the ternary case, would use more than one but fewer than five different inputs. Expressions such as the following might appear in their definitions:
§2D. Distributivity (d'ty). This traditionally employs two operations; with real numbers the typical example is of the form 7 × (8 + 9) = 7 × 8 + 7 × 9. For ternary operations, three kinds of d'ty immediately follow:
Sometimes each of two operations is distributive over the other. (Such mutual d'ty is reminiscent of the and and or operations of boolean algebra.) When K = 4:17019 and L = 4:43700, K is distributive over L thus:
Unlike most mathematical functions, many of the operations of ternary quasigroups are distributive over themselves; that is to say, O = N in the formulas above. Here are some different combinations of self-d'ty:
A distributivity that combines a ternary operation with a binary operation F could also be defined:
Such "3&2" treatment can be applied to many two-operation laws. A great deal can be said about the ways in which ternary and binary operations interact, but a full discussion is outside the scope of this report. Still, a variety of possible 3&2s will be cited later as a motivation for research in broader generalization of n-ary operations.
§2E. Mediality (m'ty) is defined using nine variables, and comes in only one ternary version:
The rearrangement of variables is suggestive of what happens when a matrix is transposed.
§2F. Idempotence (i'ce) is unsurprising:
§3 Some negations of standard laws. The following laws substitute non-equality for equality in some way.
§3A. Ex-commutativity (xc'ty). As with commutativity, several possibilities arise:
Cyclical xc'ty comes in two directions:
Even when both cyclical xc'ty laws are satisfied, O (r, p, q) might not equal O (q, r, p).
Conjecture: If C ≥ 3, no operation can exhibit both sinisterior c'ty and sinisterior xc'ty, and many operations will exhibit neither. Similar statements would apply to many of the other identities.
The following alternate definitions of cyclical xc'ty might be proposed, but it is hard to find operations to satisfy them:
§3B. Ex-associativity (xa'ty). As with associativity, several possibilities arise:
§3C. Ex-power-associativity (xpa'ty):
§3D. Ex-distributivity (xd'ty):
§3E. Ex-mediality (x'ty):
§3F. Ex-idempotence (xi'ce):
There is a stronger version of xi'ce:
§4 Some nonstandard laws. Creative algebraists can devise plenty more of these laws, and will frequently find be able to find operations that satisfy them — recall that when C = 4, there are over fifty thousand operations to choose from. Here are a few possibilities.
§4A. Cis-associativity (ca'ty). This is similar to a'ty, but now two operations are involved. O can be cis-associative over N in three ways:
For instance, 4:41121 is fully cis-associative over 4:220, but 4:220 exhibits only exterior ca'ty over 4:41121. Full ca'ty prevails when all any two conditions are satisfied, as the third condition will be consequential.
Here are some 3&2 cis-associations using binary F:
Cis-associativity can be, but rarely is, defined for two binary operations: G (Fpq, r) = G (p, Fqr).
§4B. Trans-associativity (ta'ty). This is like ca'ty, except with a swap of operations on one side of the equation:
When for instance K = 4:303 and L = 4:39155, the following are satisfied:
§4C. Re-associativity (ra'ty). Ta'ty suggests three additional laws whose cis-associative counterparts would be trivial:
In the 3&2 case, the distinction between ta'ty and ra'ty evaporates, with six plausible laws to choose from:
This gives a glimpse into how, for large n, the management of n-ary operations can start to become an exercise in combinatorics.
§4D. Cis-distributivity (cd'ty). This is like d'ty, except that on one side of the equation the two operations are swapped:
One says that O is cis-distributive over N. For example, 4:22191 is fully cis-distributive over 4:489, but 4:489 exhibits only interior and dexterior cd'ty over 4:22191.
Conventional d'ty (section 2D) might be termed trans-distributivity for contrast.
§4E. Cis-mediality (cm'ty) is a two-operation version of mediality:
Meanwhile, 4:58 and 4:16544 are exchangeable: either O = 4:58 and N = 4:16544, or O = 4:16544 and N = 4:58.
Twos 3&2 cm'ties are:
§4F. Trans-mediality (tm'ty) swaps the operations of cm'ty:
The combination O = 4:116 and N = 4:7920 exhibits both cm'ty and tm'ty, as does the singleton O = N = 4:1349.
A 3&2 tm'ty is:
To recapitulate, here is a listing of the laws presented in sections 2, 3, and 4:
table of laws | |||||||
---|---|---|---|---|---|---|---|
c'ty | §2A commutativity | xc'ty | §3A ex-commutativity | ca'ty | §4A cis-associativity | ||
a'ty | §2B associativity | xa'ty | §3B ex-associativity | ta'ty | §4B trans-associativity | ||
pa'ty | §2C power-associativity | xpa'ty | §3C ex-power-associativity | ra'ty | §4C re-associativity | ||
d'ty | §2D distributivity | xd'ty | §3D ex-distributivity | cd'ty | §4D cis-distributivity | ||
m'ty | §2E mediality | xm'ty | §3E ex-mediality | cm'ty | §4E cis-mediality | ||
i'ce | §2F idempotence | xi'ce | §3F ex-idempotence | tm'ty | §4F trans-mediality |
The method of transforming the laws of section 2 into those of section 3 (by changing equalities to non-equalities) can be applied to the laws of section 4 to produce ex-cis-associativity (xca-ty) and so forth.
This is page one, with sections 1 through 4.
Page two contains sections 5 through 10. Page three contains sections 11 and 12. Page four contains sections 13 through 16. |