Deciding Associativity for Partial Multiplication Tables of Order 3
Paul W. Bunting, Jan Van Leeuwen, Dov Tamari · Mathematics of Computation · 1978
The associativity problem for the class of finite multiplication tables is known to be undecidable, even for quite narrow infinite subclasses of tables. We present cri- teria which can be used to decide associativity in many cases, although any effective method based on such criteria must eventually fail on a table of some size (as other- wise decidability for the general class would follow). By means of an extensive com- puter search we have been able to use the criteria successfully to solve the associativity problem for all tables of order up to 3. We find 24,733 associative tables and 237,411 nonassociative tables, and present some further statistics about how deep we had to search to establish the nonassociativity of a table. We also prove that there are tables of order 3 for which no one-mountain theorem holds (which was known previously only for order 6 examples). Our methods make use of efficient data-representations and techniques of heuristic and adaptive programming.