Combinatorics of associativity
Dave L. Renfro
http://groups.google.com/group/sci.math/msg/e883dc17de2ddb14
> In general, there are a certain number of ways that a binary
> operation can be applied n times (google "catalan number"),
> and it can be proved from ordinary associativity that all of
> the different ways give rise to the same output (when the
> inputs aren't changed). This can be proved by induction,
> and I can post a proof and a number of related references
> if you'd like. (I thought I'd already posted an essay on
> this topic, but apparently not. However, I have the write-up
> in a LaTeX document, which I can re-write as a usenet post
> if anyone is interested.)
I thought I'd remedy this situation by posting some information
and references about generalized associativity and various
types of non-associativity.
Recall the associative law for a binary operation, multiplication
for instance:
a(bc) = (ab)c
It is commonly asserted, but rarely proved, that this suffices
for any type of associative rearrangement. That is, no "higher
order" associative laws are needed for more complicated
expressions. For example, ordinary associativity is enough
for us to obtain the following equalities:
[(ab)c]d = (ab)(cd) = [a(bc)]d = a[(bc)d] = a[b(cd)]
NOTE 1: The number of "binary bracketing patterns" for an
ordered sequence of n >= 2 objects is:
(1/n)*C(2n-2, n-1) = (2n-2)! / [n!(n-1)!]
= 2^(n-1) * [1*3*5* ... *(2n-3)] / n!
= Product(k=1 to n-1) of (4k-2) / (k+1),
where C(i,j) is the usual combinations symbol
(i.e. the number of j-element subsets from a
set containing i elements).
This is also equal to the number of distinct
triangulations of an (n+1)-gon by non-intersecting
diagonals. Derivations of this enumeration can be
found in Conway/Guy [4] (pp. 96-106), Etherington
[6], Forder [7], Hall [10] (pp. 25-26), Jacobson [12]
(p. 19), Knuth [14] (p. 531), Szekeres/Vaughan [16],
Tamari [17], and Wedderburn [19] (see p. 121). The
discussions in Becker [3], Conway/Guy [4], Gardner [8],
and Tamari [17] mention a number of related issues and
they are good places to begin if this is something
you'd like to delve deeper into.
NOTE 2: Related to this are the totally non-commutative operations
discussed in Machale [15]. These are binary operations #
on a set X such that a, b in X and a#b = b#a implies a=b.
Machale shows that the number of totally non-commutative
operations on a finite set with n >= 2 elements is
{ (n-1) ^ [(n/2)(n-1)] } * n ^ [(n/2)(n+1)]
= { n * (n^2 - n)^[(n-1)/2] } ^ n
Assume that we have an associative binary operation, whose outputs
we'll call products and which we'll denote by juxtapositions. For
each integer n >= 3, let S_n be the assertion that all possible
ways of grouping an ordered sequence of n elements give rise to
the same product. We will use strong induction (i.e. complete
induction) to prove that S_n holds for each n >= 3.
----------------------------
PROOF OF GENERALIZED ASSOCIATIVITY
The validity of S_3 follows from our assumption that binary
operation is associative. Now assume that S_k holds for each
3 <= k < n. To complete the proof, we need to show that S_n
holds. Let
x = ( a_1 ... a_i )( a_{i+1} ... a_n )
and
y = ( a_1 ... a_j )( a_{j+1} ... a_n )
be the final multiplications for two ways of computing the product
a_1 ... a_n. Without loss of generality, assume that 1 <= i < j < n.
Then, by our induction hypothesis, we can rewrite ( a_{i+1} ... a_n )
and ( a_1 ... a_j ) to give
x = ( a_1 ... a_i ) [ ( a_{i+1} ... a_j )( a_{j+1} ... a_n ) ]
and
y = ( a_1 ... a_i ) [ ( a_{i+1} ... a_j )( a_{j+1} ... a_n ) ].
Note that our induction hypothesis implies that the products
( a_1 ... a_i ), ( a_{i+1} ... a_j ), and ( a_{j+1} ... a_n )
are independent of grouping, and hence are well-defined without
having to specify any specific binary bracketing pattern for them.
Since x = y follows from the associative property for our
operation, the proof is now complete.
----------------------------
NOTE 3: This proof is adapted from an argument in Ames [1]
(p. 22). The proof given by Ames seemed to be the most
straightforward of the proofs that I looked at. Some
general remarks and text references to various proofs of
this result are given in Wardlaw [18]. However, Wardlaw
doesn't include the other references I've given.
NOTE 4: One can classify the non-associativity of a non-associative
operation according to the least number of terms in which
a generalized associativity relation shows up. Every
non-associative operation has a non-associativity rank > 3.
Since
a - [b - (c-d)] = [a - (b-c)] - d,
subtraction has a non-associativity rank of 4, and similarly
for division. It can be shown (see Irwin [11]) that for the
operations of subtraction and division, 2^(n-2) is the
maximum number of distinct values obtainable from various
associations of a sequence of n numbers. On the other hand,
exponentiation has no finite non-associativity rank. A proof
of this is given in Lord [13] (see example 3).
NOTE 5: More extreme forms of non-associativity can be classified
by looking for cases in which non-associativity relations
are possible even when the same element is used throughout.
For example, the operation a#b = (a+b)/2 is non-associative,
and yet a#(a#a) = (a#a)#a is true for all real numbers a.
On the other hand, note that a^(a^a) is not equal to
(a^a)^a in general, and so exponentiation has a "strong
non-associative rank" (my term) > 3. This stronger notion
of non-associativity is discussed in Baylis [2]. Baylis'
paper gives no references and it does not discuss to what
extent exponentiation is strongly non-associative. However,
the identity
(a^a) ^ (a^a) = [a ^ (a^a)] ^ a
shows that exponentiation has a strong non-associative rank
of 4. Some results concerning the strong non-associative rank
of exponentiation for specific numerical values of a can be
found in Gobel/Nederpelt [9].
NOTE 6: The number of interpretations that a^n takes on when
"multiplication" is non-commutative and non-associative
is
[ 2 * (2n-3)! ] / [ n! * (n-2)! ]
(for a proof, see Etherington [5]), and the number of
interpretations that a^n takes on when "multiplication"
is commutative and non-associative is is discussed in
Becker [3], Etherington [5], and Wedderburn [19].
Binary operations such that every interpretation of
a^n is the same for each element a are called "power
associative". An example of a non-associative binary
operation that is power associative is multiplication
for the octonions.
[1] Dennis B. Ames, INTRODUCTION TO ABSTRACT ALGEBRA, International
Textbook Company, 1969, xii + 368 pages.
[MR 39 #1249; Zbl 213.28902]
[2] John Baylis, "Generalizing associativity", International Journal
of Mathematical Education in Science and Technology 27 (1996),
460-464.
[3] H. W. Becker, "Genetic algebra -- Discussion of Monthly
Problem #4277", American Mathematical Monthly 56 (1949),
697-699.
[4] John Horton Conway and Richard Kenneth Guy, THE BOOK OF NUMBERS,
Springer-Verlag, 1996, x + 310 pages.
[MR 98g:00004; Zbl 866.00001]
[5] Ivor Malcolm Haddon Etherington, "Non-associative powers and
a functional equation", The Mathematical Gazette 21 #242
(February 1937), 36-39. [See also the postcript in Math.
Gazette 21 #243 (May 1937), p. 153.]
[Zbl 15.34102; JFM 63.0876.02]
[6] Ivor Malcolm Haddon Etherington, "Some problems of non-associative
combinations I", Edinburgh Mathematical Notes 32 (1941), 1-6.
[MR 4,68g; Zbl 60.02505]
[7] Henry George Forder, "Some problems in combinatorics", Mathematical
Gazette 45 #353 (October 1961), 199-201. [Zbl 98.24503]
[8] Martin Gardner, "Mathematical Games - Catalan numbers: an integer
sequence that materializes in unexpected places", Scientific
American 234 #6 (June 1976), 120-125 & 132.
[9] Fvrits Gobel and Rob P. Nederpelt, "The number of numerical
outcomes of iterated powers", American Mathematical
Monthly 78 (1971), 1097-1103. [MR 45 #6643; Zbl 233.05005]
[10] Marshall Hall, COMBINATORIAL THEORY, Ginn-Blaisdell, 1967,
x + 310 pages. [A 1986 2'nd edition exists (MR 87j:05001;
Zbl 588.05001), but I have not had a chance to examine
it in order to update the page reference for the proof of
generalized associativity.] [MR 37 #80; Zbl 196.02401]
[11] Frank Irwin, "Solution to Monthly Problem #2688",
American Mathematical Monthly 33 (1926), 105.
[12] Nathan Jacobson, LECTURES IN ABSTRACT ALGEBRA, Volume 1,
Van Nostrand Reinhold, 1951, xii + 217 pages.
[MR 12,794c; Zbl 326.00001]
[13] Nick J. Lord, "Non-associative operations", Mathematics
Magazine 60 (1987), 174-177.
[14] Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, VOL. I:
FUNDAMENTAL ALGORITHMS, 2'nd edition, Addison-Wesley,
1981, xxii + 634 pages. [A 1997 3'rd edition exists
(Zbl 895.65001), but I have not had a chance to examine
it in order to update the page reference for the proof of
generalized associativity.] [MR 51 #14624; Zbl 895.68055]
[15] Des Machale, "Totally non-commutative systems", The Mathematical
Gazette 82 #494 (July 1998), 283-286.
[16] George Szekeres and Herbert E. Vaughan, "Solutions to Monthly
Problem #3954", American Mathematical Monthly 48 (1941),
564-569.
[17] Dov Tamari, "The algebra of bracketings and their enumeration",
Nieuw Archief voor Wiskunde (3) 10 (1962), 131-146.
[MR 26 #3749; Zbl 109.24502]
[18] William P. Wardlaw, "A generalized general associative law",
Mathematics Magazine 74 (2001), 230-233. [Zbl 1002.20045]
[19] Joseph Henry Maclagan Wedderburn, "The functional equation"
g(x^2) = 2*alpha*x + [g(x)]^2", Annals of Mathematics (2)
24 (1922), 121-140. [JFM 49.0244.02]
Dave L. Renfro
Dave L. Renfro
> I thought I'd already posted an essay on this topic,
> but apparently not. However, I have the write-up [...]
I found my earlier post. It was made on January 27, 2002
in the sci.math thread "Generalisation of associativity
to >3 elements?" and is in The Math Forum's sci.math
archive, but not google's sci.math archive:
http://mathforum.org/kb/thread.jspa?messageID=361822
I thought this might be the case when I was originally
looking for it, but my searches at The Math Forum didn't
uncover it yesterday. (It's harder to search at The Math
Form, because there are no phrase searches. You can search
"by relevance", but even this doesn't always work well for
phrases. However, at google you can search using multiple
phrases and/or multiple terms, while simultaneously
omitting selected terms.)
In any event, the essay on associativity that I posted
today is much more complete than the version I posted
on January 27, 2002.
Dave L. Renfro