Groups

[Keiji]

So I am currently studying groups at university, and an interesting thought occurred to me:

Let Σ be an alphabet of n ≥ 2 symbols.
Let L be the (infinite) set of all strings S over Σ such that S does not contain the substring <a,a> for any a ∈ Σ. For example, "abcabc" and "abcba" would be in L, but "abcca" would not because it contains two consecutive 'c's.

Then L is a non-commutative infinite group under an operation I call "concatenation with elimination", which I shall arbitrarily denote ⊗. This operation is performed by first concatenating the two operands, then removing any pair of consecutive identical symbols until there are no more such pairs. So for example, "abc"⊗"cbd" = ad, because the working goes: "abccbd" -> "abbd" -> "ad".

The four axioms are satisfied thus:

• Closure: If A and B are in L, then A⊗B is clearly in L because A⊗B has no such disallowed substrings by definition of ⊗.
• Associativity: Not sure how to prove this one at the moment, but my thinking is as follows: consider (A⊗B)⊗C versus A⊗(B⊗C), then consider the removed pairs in A⊗B versus the removed pairs in B⊗C - in cases where these sets of pairs do not "overlap" then it clearly must be associative; in cases where they do overlap, taking the substring from B which forms the overlap and reversing it produces a substring of the result which replaces the cancelled symbols, so again it is associative.
• Identity: this is the empty string Λ, clearly A⊗Λ = A = Λ⊗A
• Inverse: this is the reversed string A^-1: a copy of A with the order of symbols reversed, and by definition of ⊗ then A⊗A^-1 = Λ = A^-1⊗A

Has anyone else thought of this, or found any interesting properties, or perhaps a proof for associativity (I'm thinking that one would be inductive)?

[wendy]

Associativity can not be proved. That's why it's an axiom. Axioms just have to be taken as is.

On the other hand, if you can demonstrate the axioms in a set (eg reflections), then group theory holds.

[Keiji]

That's not what I meant, I meant there would need to be a proof of the associativity of this supposed group, to prove that it is indeed a group.

[quickfur]

I've considered an equivalent of such a structure before. I'm pretty sure it's a group; each individual letter is its own inverse, so by extension all strings have inverses. Does it associate? String concatenation is associative by definition, and since the idempotent letters do not change the order of letters in the string, given A*B*C it doesn't matter whether you concatenate A and B first or B and C first; any mutually-eliminating letters between A and B and B and C will eventually come into contact and eliminate themselves, and will always converge to the same final result.

There is a very interesting way to visualize this group as a graph. Let your alphabet have N letters. Draw a node in the center. Attach N copies of a full (N-1)-ary tree of infinite height to this node. Notice that every node in this graph has order N, and is completely isomorphic to every other node. Select any node as your "root" (it can be any node, since they are all equivalent). Since every node has N edges, consistently assign a letter to each edge such that every node is surrounded by edges of every letter exactly once. Now take any string in your group, and interpret it letter-by-letter as a path from the root node, with the letter indicating which edge you should traverse next. Notice how any adjacent duplicate letters eliminate themselves, since traversing the same edge twice returns you to the original node. Your group, therefore, is the set of all possible paths from the root node. Every node can be uniquely labelled by the string that takes you from the root to that node.

Now, given two root nodes, paths relative to one root node can be translated to paths relative to the other root node by simply prepending the path from the second root to the first (with duplicate letters eliminated from the result, of course). This gives you a way to translate node labels relative to a different root. Since the graph is a tree, there is a unique path from every node to every other node. The reverse of a path is simply the inverse string (reverse all the letters).

[Keiji]

That's really cool!

I noticed something else about this while I was getting to sleep last night: (ℤ,+) is a subgroup of (L₂,⊗). This is explained roughly as follows:

Let Σ be {a, b}.
Now consider all the strings in L with even length. Other than Λ, they clearly fall into two categories: those that begin with a, and those that begin with b.
Now consider setting 0 = Λ and 1 = ab. The additive inverse of 1 is -1, and the inverse of ab is ba. So we'll identify those two elements, too.
Now, 1+1 = 2, and ab⊗ab = abab. And so on for higher numbers/lengths. So we can say that a positive number n is the string in L with length 2n starting with a.
Similarly, we can say that a negative number n is the string in L with length 2n starting with b.

In fact thinking about it, the cyclic subgroup of "ab" in L₂ is exactly this subgroup.

Represented in your infinite tree form, it would simply be an infinite number of vertices all connected in a "line", with the "root" node being zero, and every second node being an integer.

[quickfur]

Hmm. So if we use the full group over two letters, that means we have "strange integers" between the normal integers where a positive number added to a negative number can sometimes be a bigger positive number? That's bizarrely cool.

[Keiji]

Yeah, I'd noticed that too, but I didn't mention it because there's no real purpose for it that I can think of and it just becomes obscure.

[quickfur]

I like things, esp. in math, that apparently have no purpose, because sometimes they lead to interesting structures. For example, I've been trying to figure out if there's a way to define fractional paths in your group by taking the limit of infinite paths, but I haven't been able to find anything workable yet. If achieved, it will be a new kind of number system with very different, yet consistent, properties from the one we're familiar with.

[Keiji]

Hmm, well, I'm not sure quite what you're trying to get at, but I'd be more interested to know if there was a relationship between L_n (n > 2) and other groups or sets, especially ℚ, ℤ^m or ℚ^m.

[quickfur]

IOW, I'm investigating whether it is possible to construct a group G', which contains your group G as a subgroup, and which interpolates between its elements in a similar way that the set of real numbers interpolates between the integers.

[Mrrl]

If we take strings of the even length of L_n, we get free group F_n-1: let ab=B, ba=B^-1, ac=C, bc=B^-1C, and so on - then every string of even length of a,b,c,... may be rewritten in B,C,... . We can get L_n from F_n-1 by adding to the latter element "a" with properties a²=1, aS=S^*a, where ^* is automorphism of F_n-1: B^*=B^-1, C^*=C^-1, (BC)^*=B^-1C^-1 and so on.

[Mrrl]

So, we may take infinite tree with 2n-2 edges in each node, enumerate them as B, B', C, C',..., H, H' (so that way C from some node followed by C' returns us to the same node). In every node we can be in one of two orientations: look frowqard and backward (when we turn around, directions B and B', C and C' and so on are being switched). If we name "turn around" operation as "a", "step in direction B and turn around" as "b", "step in direction C and turn around" as "c", we'll get the group L_n.
For example, L₂ is the group of "movements" of Z: element "a" is a(x)=-x and "b" is b(x)=1-x. L₃ may be morphed to the group of translations and central symmetries of Z² ((x,y)->(x+p,y+q) and (x,y)->(p-x,q-x)) if you add the identity "bac=cab" to it (that is "ab" and "ac" are commutating). L₃ itself is the group of translations and symmetries of infinite 4-tree or of the hyperbolic tiling {4,infinity}: you may take a(z)=-z, b(z)=2(z-1)/(z-2), c(z)=2(z*i+1)/(z-2i) as functions on complex plane