Algebraic Hoop Construction

Moved from AlgebraicHoop due to its size.

Seems to have died too... has no more progress been made? I'm still looking for that abcd != adcb hoop, to no avail. I can't seem to reduce the condition to a constructive form, either. -- td

Two elements are abcd and adcb, and others are constructed as other letter sequences. I still think abcd = adcb, unless someone provides a complete counter example. Why? Because I think (no proof for that, though) that this is true for Hoops which have 3 elements, called {1, 2, 3}. Now, somewhere it basically says that all hoops are constructed as product of size 3 hoops, call that {1, 2, 3}^n. As abcd = adcb for size 3 hoops, this holds for every 'coordinate' of the bigger hoop, therefore holding for the bigger hoop as well. That was the Houben conjecture, and the abcd != adcb hoop is a counter-example to it. I'd like to see an explicit construction of it, too, as it is too big for me to work with personally, but I don't doubt it exists.

I think the "death" here stems from the fact that 81-hoops are a bit big to work with. Before listing the 81 elements, it helps to play with the algebra to avoid listing the same element twice. Getting the non-Houben 81-hoop then requires spotting the equation to use instead of abcd = adcb. However, that doesn't by itself make the structure easy to understand. It should be reasonably apparent that simply doing without abcd = adcb (where a,b,c,d are distinct) does give an (infinite, apparently) example of a non-Houben hoop.

I thought the conjecture was that all _finite_ hoops had abcd = adcb. -- td [It was, but first ideas are not always right (as with programming...).]

Sure. Maybe we could get a hint as to what the defining relationship is for the finite non-Houben hoop? I'd like to see it but don't quite have the motivation to work it out for myself...

[First list the 81 elements, then it's fairly easy to see what rule will ensure that trying to form an 82nd element (using 8 letters or more) won't work.]

Can anyone give me an example of a hoop larger than 3? I'm at the denial stage. I can't construct a 9 hoop that satisfies the third, let alone the fourth rule. I can construct a 7 that satisfies the third rule, but breaks the fourth. Tell me now if the next one is like 81 long and I'll stop flogging this technique :) -- RichardHenderson

Aha! I got it. Here's a 9 hoop.

9 hoop:

a b c d e f g h i ----------------- a: a c b g i h d f e b: c b a i h g f e d c: b a c h g i e d f d: g i h d f e a c b e: i h g f e d c b a f: h g i e d f b a c g: d f e a c b g i h h: f e d c b a i h g i: e d f b a c h g i

Rather groovy (hoopy?) -- RichardHenderson

Arg, you beat me to it. Well, I'm going to leave my table here for a bit.

It's a good table, I used a constructive rather than algebraic technique. I'd like to see how you do it properly.

I probably did about the same thing as you. This is the free hoop with three generators, you can get it by assuming ab <> c (in your case, the third generator is d) and working out what all the products should be. I like to use trees, they make manipulations easier:

      _             ____            _______            ___
    _/ \_         _/    \_        _/       \_        _/   \_    a
  _/ \ / \_     _/ \_   / \_     / \_     _/ \_     / \  _/ \  
 / \ c b / \   / \ / \_ c / \_   b / \_  / \ / \_   b c / \ a
 a b     a c   a b b / \  b / \    a / \ b c c / \      b c
                     a c    a c      a c       a c
 (abc)(acb) = a

I think the free hoop with four generators is infinite but haven't been able to prove that. -- JoshuaGrosse

[I don't quite follow the tree diagram - can you briefly explain it? -- Each node is a multiplication. It's very easy to turn the hoop axioms into geometrical operations.]

A little more detail is needed to allow the diagrams to be verified.

Ok, I didn't want to go into too much detail about this, because it is simply a notation I found convenient, it being a heck of a lot easier to see how you are operating on elements when you don't have to try and match brackets. Something of the form ((ab)c)(de) would be written

_ _/ \_ _/ \ / \ / \ c d e a b

The hoop axioms correspond to the following geometric operations, where X and its kin are not just leafs but possibly branches. These are applied in simple form above. As said, it's a lot easier than the algebraic form - at least until you go to type it in wiki. :) But then I'm not the one who found the irreducible 81-hoop.

  _        _      _               _           _
 / \ <--> / \    / \_  <--> Y    / \_ <-->  _/ \_
 X Y      Y X    X / \           X / \     / \ / \ 
                   X Y             Y Z     Y X X Z

How did you get the second diagram from the first in the original list? Rule 3, sliding the right side of the tree over the two branches of the left side.

You're correct, but it's less easy than you might think to spot what rule is being used.

Were the changes to the tree diagrams above intended? They didn't display properly on my computer, so I reset them. Happy with the 81-hoop info?

Thanks for that. I didn't do anything deliberate to the trees - it may be my browser, so let's see if this edit upsets them. Actually, there is something that seems wrong to me in what you said about the 81-hoop. You stated that there are 24 elements of the form abcdb, but I got that abcdb = (ab)(cd)(ad), and there are only 12 products of that form. Either the counts are wrong or I made a mistake; the derivation is kind of long but I'll post it on request.

Since it's easily shown that ab cd ad = cdabda identically, you made a slip.

I did, thanks. Then what you've said is sufficient to fix the structure of the 81-hoop down to whether the defining relationship is abcdbcd=acdbcdb, abcdbcd=cdbabda, or abcdbcd=bdcadca. I'm sure two of those will be shown to result in smaller or larger hoops with only a little more effort, and then writing out an entire multiplication table would be trivial though exceedingly tedious. Thanks, I'm very happy with that.

Be logical - the relation needed prevents an expression of length 8 being added by making it equal to an expression already listed.

(The relation needed is quite easy to find, especially if one plays with the algebra, but if you prefer not to, just ask.)

I'll look at that. I used an intuitive technique. In the mean-time, this notation makes the arithmetic explicitly dimensional. It is a hoop of identical hoops. Reminds me of Hilbert space-filling curves. -- RichardHenderson

11 12 13 21 22 23 31 32 33 ---------------------------- 11: 11 13 12 31 33 32 21 23 22 12: 13 12 11 33 32 31 23 22 21 13: 12 11 13 32 31 33 22 21 23

21: 31 33 32 21 23 22 11 13 12 22: 33 32 31 23 22 21 13 12 11 23: 32 31 33 22 21 23 12 11 13

31: 21 23 22 11 13 12 31 33 32 32: 23 22 21 13 12 11 33 32 31 33: 22 21 23 12 11 13 32 31 33

It also reminds me of magic squares. Each element can only appear once in any row or column. to satisfy rule 3.

That's a pretty notation, it makes it plain how the 9-hoop is the cartesian product of two 3-hoops. You can build larger hoops the same way, and these are precisely the hoops corresponding to the groups C3^n. Unfortunately, not all hoops are generated this way. That's why I was looking at free hoops instead.

Can you explain a little further? I have difficulty imagining a hoop which isn't stuck with this dimensional form. I tried using a freer derivation but kept running into shared edge problems. This appears in the matrix of values as repeats in a row and column. I remember playing with 3-D spacefilling curves and they could turn inside out producing left-handed and right-handed mirror forms. I suspect you have more exotic hoops in mind. Are you suggesting hoops which aren't a power of 3 or different geometries from the permutations of the above?

The 4-generated Houben hoop is C3^3 (generators 111,112,121,211), but it only takes a little experimentation to convince yourself a 4-generated hoop may have more elements than that, and so have a different structure. Someone above said the simplest example has 81 elements, although I haven't constructed that explicitly, and would be interested if you bothered.

I will believe it when I see it. Symmetry, self-inverse and self-identity seem to kill most possibilities. Rule 4 is tricky, but is automatically satisfied by subhoops (local hoops), and orthogonal basis superhoops like the '9' above. If we assume any three points must be a hoop, then there are only two possible answers for the '9', and they are both orthogonal or else they break rule 4. So any non-orthogonal solution must involve 3 points that are not a local hoop, but still satisfy rule 4. That seems unlikely to work for all combinations of the 3. I remember where I've done this sort of thing before, in flexagon theory :). If anyone comes up with a non-orthogonal basis version of any degree I'd be interested. All orthogonal base versions are equivalent by simple relabelling. And I am now in denial over the 'exceptions' :). -- RichardHenderson I'm not sure what you mean by basis, but it sounds like you are trying to build hoops as cartesian products of C3-copies, which gives you only Houben hoops by definition. That doesn't mean other hoops don't exist, though, just that you can't build them in terms of a basis. Try playing around with four generators and see if you can get anything with more than 27 elements. I might work on that this evening.

I made a quick program to generate these by applying a few simple rules, but the program was far too slow... had to search all the time and wasn't too intelligent about it. So I never did finish having it make a 4-generated hoop. I basically applied some simple rules:

 x*x = x
 x*y = z -> x*z = y & y*z = x
 x*y = z & x*a = b -> b*z = x*(a*y)

If, after application of these rules, there are still spaces, fill one in with a new element, and try again.

If anyone wants to try again with this stuff (using some good search-space limits this time), be my guest. -- TaralDragon

[Why not first modify the program to look for other handy rules? A rule needn't be provable to be useful!]

Okay I got it. There are a number of interesting regularities, but the fundamental 'rules' of a good hoop are simple. Each triplet of elements is a 'hooplet' which obeys rule 3, and also an identity function due to rule 4. The pattern is:

a b c a a c b b c b a c b a c .

Each and every triplet must obey this pattern or break rule 3 and/or 4. The only other rule is that triplets cannot share 'edges'. For example, triplets abc and dbc cannot both exist. This locks the number of hooplets per hoop to 12.

Some notation. I use the letters abcdefghi.

To construct any matrix. First recognize the identity hooplets: abc,def,ghi. They will all have the standard hooplet pattern as above. This is constant for all solutions (IMO :)).

The whole matrix must transpose about the identity products (from g*h = h*g).

Given these three primary hooplets (and every hoop must have them, though possibly under different labels), we can look at the secondary hooplets. Secondary hooplets have edges outside the three primaries. It is easy to see that each element of a triplet must come from a different primary. Otherwise one primary and the secondary would share an edge, and that is a no-no. In the product matrix, this shows up as a repeated element (and thus also a missing element) in a row or column.

Consider the first element a. We have products with b,c. We need the rest d,e,f,g,h,i. This must choose one element from the second primary, and one element from the third. We must do the same thing for b and c too. All of these hooplets must not share an edge.

Okay, the possible choices available to abc are the product of elements in the other two primaries = def X ghi.

dg dh di eg eh ei fg fh fi

The procedure is to pick one possibility per element of abc. Each pick must be a different edge. So adg aeh afi is okay, but adg aeh afg isn't, as it has a shared edge ag. Having picked three for a, we need to pick three for b; these must not mutually interfere, and must pick from the six remaining choices. Finally, c must use the remaining three. If you draw parallel diagonals on the 3x3 matrix above and wrap on diagonals, you get the three sets of mutually separate edges.

So: dg eh fi, dh ei fg, di eg fh . Or going the other way: dg ei fh, dh eg fi, di eh fg .

Okay we're nearly there. a can pick from any of the three. b can pick from two, and c is implied. This works in any sequence giving(drum-roll) 18 possible 9-hoops of 12 hooplets. These arrange into 2 alternatives. -- RH

That's very odd, that you should insist that ab=c but not ad=e or some such. Up to isomorphism, there's only one 9-hoop, as you yourself pointed out when you said they are all equivalent through row-and-col swapping.

RH didn't say that. His original statement meant that the matrix is symmetrical about its main diagonal. What's now being considered is letter swapping (relabelling).

Well yes, I think they are all isomorphic under transformation via row-col swaps, but not under simple relabelling. The row-col thing doesn't convince me yet. I need to generate the 18 variations and see.

The elements you're labelling c,e,f,g,h,i are necessarily the products ab,bd,ad,abd,bad,bda in some order. If you relabel them in that form then you necessarily get the table I quoted above. The rest is just a matter of choosing which symbol to associate with which product, you see? But you're right that that isn't the same as row-col swapping, MeaCulpa.

I need to convince myself that the two basic alternatives (after eliminating relabelling) are the same one. Geometrically, they appear to differ but that may be my poor 3-D spatial manipulation. Juggling 20 triangles is tricky :). I like to see it and understand it.

Oh, and here's the (partial) matrices of 9-hoop twins. (non-Houben?) for your viewing pleasure (this is fixed up from before):

a b c d e f g h i a b c d e f g h i ----------------- ----------------- a: g i h d f e a: i g h e f d b: i h g f e d b: h i g f d e c: h g i e d f c: g h i d e f d: a c b d: c b a e: c b a e: a c b f: b a c f: b a c g: g: h: h: i: i:

abc-def-ghi abc-def-igh adg-aei-afh adi-aeg-afh bdi-beh-bfg bdh-bei-bfg cdh-ceg-cfi cdg-ceh-cfi

-- RichardHenderson

The first table, when completed, becomes your original 9-hoop example. The second is obtained from it by relabelling d as e and e as d, so both are the unique 9-hoop, which is a Houben hoop.

I'm curious to see how many forms there are. It looks like 2 or 3. Interestingly, one need only specify two hooplets (of 12) to generate the entire set, if those hooplets do not share a corner. -- RichardHenderson

Eh? You used 'non-Abelian' (originally - objection below now adopted), which I took to mean 'non-Houben', ie., not corresponding to a group in the manner Houben suggested. BTW, Even two hooplets which share a corner work, since they must generate the unique (Abelian or Houben) 9-hoop.

Abelian usually means that a*b = b*a, so isn't really appropriate for hoops. I've been calling a hoop Houben if the operation a**b = o*(a*b) for some fixed element o is associative, so that the set forms a group under that operation. Some group theory shows that a Houben hoop is necessarily a Cartesian product of C3s. But a hoop is Houben iff abcd = adcb for all elements a,b,c,d.

[The symbol ** is clumsy; a high-visibility symbol is needed, so how about #?]

I get 2 hoops. Corresponding to two sequence orders abc vs acb, forwards versus backwards. This makes no difference when you've only got 3, but when you've got 6, it gives a left-handed versus right-handed geometry, exactly as you'd expect in a 3-D system = abc X def X ghi OR abc X def X ihg. This is looking more like flexagons the more I look at it. I suspect this is equivalent to a hexaflexagon. This would clarify the number of hooplets required to uniquely define the hoop. Usually, but not always, two hooplets define the hoop. -- RichardHenderson

As there's only one 9-hoop, it's easy to have sufficient to define it; for larger hoops, two hooplets are usually insufficient.

From JG: I can't say I understand what you are doing. The way you restrict products makes no sense to me - ab is always denoted by c, ad can be denoted by g or i but never h. What is it we have three or six of, disjoint hooplets? Maybe all this has something to do with the way you are mapping these to space, but it doesn't look inherent to the algebraic structure. The two twin hoops you list above are isomorphic through the interchange of g and i.

It's d and e to swap (see earlier note). You can swap either pair and get the same effect, since none of the symbols have any meaning apart from each other.

[Not quite. The f column contains g and i, but is the same in both tables; the h column changes corresponding to swapping d and e, and the missed entries are i, h, and g (in that order) in both tables.]

Yes that is true. I'm not using full commutation as my distinction (sorry I didn't realize till you pointed it out). I'm thinking geometrically, in which case there are two separate dimensional spaces. You convert left-handed to right-handed in 3-D space simply by swapping two of the dimensions. This system has a similar quality. A hexaflexagon (a paper flexing toy) has a similar state-space. I might mess with this idea a bit more. Good luck with the 27-hoop(s?) :). Loads of no-shared-edge paths. -- RichardHenderson

[Pondering hexaflexagons... don't see any commutative principle.]

The 27-hoop is unique, and it is the Houben hoop with four generators. Each element can be written using from 1 to 4 letters, without repetition. As with all Houben hoops we have to identify wxyz = wzyx = xzyw and (wx)(yz) = (wy)(xz) = (wz)(yx), where w,x,y,z represent the generators in some order. [Note that wxyz=wzyx implies all these identities.] It would be interesting to find out what the corresponding relations defining the non-Houben 81-hoop are.

You can also write the 27-hoop as the cross product of three C3s, just as you wrote the 9-hoop as the cross product of two C3s. Your elements would be 111, 112, 113, and so forth, with multiplication component-wise as before. Figuring out what geometric object you want to think of this in terms of is up to you. :)

The Houben 81-hoop's elements can be written using up to 5 letters, without repetition. The 81 elements can be listed as a(5), ab(10), abc(30), abcd(20), ab cd(5), abcde(10), ab cd e(1). These are archetypes - the number in parentheses gives the total number of distinct elements obtained by permuting the five letters a, b, c, d, e.

Similarly, the Houben 243-hoop's elements can be listed using up to 6 letters, without repetition, as a(6), ab(15), abc(60), abcd(60), ab cd(15), abcde(60), ab cd e(6), abcdef(15), abcd ef(6).

It would seem that such a list "without repetition" is possible for every Houben hoop, but I don't have a proof of that.

The non-Houben 81-hoop's elements can be written using up to 7 letters chosen from 4, so there are various repeated letters. The 81 elements can be listed as a(4), ab(6), abc(12), ab cd(3), abcd(12), abcdb(24), abcdbc(12), and abcdbcd(8). These are archetypes - the number in the parentheses gives the total number of distinct elements obtained by permuting the letters a, b, c, and d. These numbers total 81, of course.

Of course, once one has one finite non-Houben hoop, further ones can be produced by forming products. I have limited information on any other finite non-Houben hoops which can't be expressed as a product.

Terminology: suppose one considers all the elements obtained by forming expressions involving one or elements drawn from some fixed list, where no element in the list equals some expression formed exclusively from other elements in the list. The resulting hoop is called the free hoop generated by the elements in the list. The set of elements in the original list is sometimes called a basis for the generated hoop.

The free hoop generated by the basis containing a, b, c, and d appears to be infinite (as previously stated). This free hoop is non-Houben. One can modify this process to generate a finite non-Houben hoop.

The original page was getting too big for some browsers.

The whole thing needs to be refactored out of ThreadMode anyways, but I don't have time to try right now.

It's like a journey of discovery :).

CategoryMath