general.hpp File Reference

Plans in general regarding quasi-groups. More...

Go to the source code of this file.

Detailed Description

Plans in general regarding quasi-groups.

Connections to other modules
  • The conversions between quasigroups and latin squares work as well for the translation between groupoids and "composition tables".
  • So perhaps we should generalisations (simply appropriately named) for this most general level.
Associativity resp. group test
  • A quasigroup Q is a group iff Q is associative.
  • A groupoid V with a rightneutral element is associative iff the composition of two rows of V (as a transformation of V) is again a row of V.
  • So we can test the quasigroup Q for the associativity/groupness by first checking whether we have a rightneutral element, and then checking the stability of the rows under composition.
  • The crucial part is the stability property:
    1. We assume Q is standardised, of order n.
    2. Consider two rows R_i, R_j of Q, where we want to check whether R_i * R_j = R_p for some p.
    3. First we evaluate p' := (R_i * R_j)(1) in constant time.
    4. Now there is a unique p with R_p(1) = p' (which can be found in constant time, given the obvious preparations).
    5. It remains to check whether R_i * R_j = R_p holds --- the whole algorithm will run faster than the trivial method (n^3 steps) iff this can be done faster (amortised) than by running through all the n arguments.
    6. Likely we should do the equivalent test R_i * R_j * R_p^(-1) = id (or R_p^(-1) * R_i * R_j = id).
    7. Say we check R_p^(-1) * R_i * R_j; each permutation is just available as a constant time function, with R_p^(-1) precomputed.
    8. Actually for each p there must be q with R_q = R_p^(-1); so better than to store the R_p^{-1} we first find these q, which might show that we don't have a group, or otherwise saves some storage. And we can use the same trick again, first find the right row q, and then just check whether R_q actually is the inverse of R_p.
    9. So we have to check for C := R_q * R_i * R_j whether we have C = id.
    10. One idea is as follows:
      1. We have precomputed the supports (changed places) S_i for all rows R_i. Now if |S_q| + |S_i| + |S_j| >= n, then we run simple through x = 1, ..., n, and check whether the composition C gives x back (it's hard to see how to do better here).
      2. Otherwise, using an array a[t], t in {1,...,n} of natural numbers >= 0, initialised to 0, we first run through x in S_j, set a[x] to the current round r (one round for each pair (i,j)), and check whether the composition C applied to x yields x.
      3. If yes, we run through y from S_i, if a[y] = r, then ignore y, otherwise set a[y] to r, and plug in y to the composition S_q * S_i, checking whether y is the result.
      4. If yes, then finally we check whether for all z in S_q we have a[z] = r (otherwise we return false).
      Unfortunately, this is always worse than the trivial method, since no left- or right-translation of an unital quasigroup except of the identity has any fixpoint, and thus the support is always the whole set!
    11. So the problem is, how to check for fixpoint-free permutations P1, P2, P3 (as elements of the symmetric group of order n) in less than n steps whether P1 * P2 * P3 = id (or not), where for each possible Pi we can spent less than quadratic preparation efforts (but only considered on its own).
    12. Hard to see that anything could be done.
  • If we have an interesting algorithm, it should be implemented and tested for run time, using, say, random latin squares, and comparing it with the trivial test.
    1. First groups should be tested.
    2. When checking a quasigroup then we only check unital quasigroups (otherwise they are immediately rejected).
    3. It doesn't make sense to consider a random isotopic image of a group, since if such an image is unital then it's itself a group (and it shouldn't make a difference how the rows and columns are ordered, since groups are the worst-case anyway).
    4. Thus left is the task of creating random unital quasigroups.
    5. See "Random generation of quasigroups and unital quasigroups" in Lisp/Groupoids/Quasigroups/plans/Enumeration.hpp.
  • We obtain in this way also a test for checking whether a groupoid V is a group: First check whether V is a quasigroup, and then apply the above.

Definition in file general.hpp.