We can think of modular arithmetic as amending operations on Z to “wrap around and stay in Zn.” Can we generalize this idea to arbitrary groups, or even general algebras?
(Note: I originally wrote this on Apple Notes, not in Word, so there is no math/equation formatting in this post. It seems cumbersome to go through manually and change it all now, but if it makes sense to change it at some point — e.g. if I have a script to do it — I will.)
Let G be a group, and let S be a subset of G. If S is closed under multiplication, identity, and inverse, then S is in fact a subgroup of G. But in the case that S is not closed, can we define operations just on S that are based on the operations of G? Can we then prove certain analogous properties of these operations (like e.g. that S is on its own with these operations a group, or that if S is closed then our construction just reduces to the original G-operations restricted to S?)
How would we define this? In fact, some of these sound like reasonable requirements for such a construction: for example, we would require the reducibility to original operations in the case of closure.
The notation we can use for this is “(original operation) wrap S.” So if the group operation is the standard multiplication, then the operation we define here will be multiplication wrap S. Then, modular arithmetic corresponds to arithmetic wrap Zn, where here Zn refers to the underlying set. In other words, mod n is the same as wrap Zn.
So how do we do this? Well, the “wrap around” basically means that we perform operations on G as usual, and then we “wrap around” the result to something in S. In other words, we should define an equivalence relation such that any element of G is equivalent to exactly one element in S, and that’s the one we “wrap around to.” For the case of Zn and Z, each element of Zn defines a subset of Z in this way (part of a partition.) I’m thinking something with cosets could work here — every two elements in the same class for Zn have a difference of a multiple of n. Similarly, we can say that every element of the equivalence class we construct should be related to each other by a certain factor. What about this: given an element a in G, we define b to be equivalent to c if and only if b = ca^k for some k? This is an equivalence relation (as can be easily seen), thus it defines a partition into equivalence classes. Thus, this is a construction of G wrap S where S is comprised of one element from each class. Actually, for such an S, is this well-defined? Is it possible that there are more than one possible a leading to a given S, and if so, do these different values of a lead to ultimately the same construction? We’d need to show that to verify that this yields a valid construction of G wrap S without a being given.
Also, our construction of G wrap S for any subset S should reduce to this if S is of this form. Is it true that for any subset S there would exist a corresponding a?
Let’s work on this. First, a few lemmas.
Lemma. Say that b and c are equivalent “by a” if b = ca^k for some k. Then, the equivalence relations for different a can’t be equal.
Proof. Assume there were two a and b such that for all c and d, c equals d by a if and only if c equals d by b. We show a contradiction.
In a first case, say that there don’t exist different c and d such that c is equal to d by a. Then, a must be e, the identity. For if a wasn’t e, then ca would be equal to c by a, but ca wouldn’t be the same as c, since otherwise the cancellation property would imply that a=e. But this logic works for b too, so a=e=b. Thus, this case is resolved.
Otherwise, there exist different c and d such that c is equal to d by a. Then, a can’t be equal to e, otherwise that would imply that the only possible elements equal by a are those that are the exact same. Similarly, b can’t be equal to e. So we have that ca is equal to c by a, hence ca is equal to c by b by hypothesis. Hence, ca=cb^k for some k, so a=b^k. But the logic is symmetric, so b=a^l for some l. Hence, a=a^kl, and kl-1 must be a multiple of the order of a. Similarly, kl-1 must be a multiple of the order of b. Hence, kl-1 must be a multiple of the LCM of the orders of a and b.
Actually, so what we’ve proven so far is: if the equivalence relations of by a and by b are the same, then kl-1 is a multiple of the orders of a and b. (In particular, if either a or b doesn’t have an order, then the equivalence relations of a and b can’t be the same.) I think I forgot about finite order (which is not true for example in Z, which is where I got my intuition) — can we show that a converse to this holds? Then, we can characterize all equivalence relations by a for all a in G.
So what we want to show is: the equivalence relations of by a and by b are equal if and only if both a and b have finite order and a=b^k and b=a^l for some k and l.
We’ve shown the equal implies the k/l; we want to show the converse. So say that a=b^k and b=a^l for some k and l; it is then obvious that being equal by a is the same as being equal by b, and vice versa. So actually, we can say that: by a is equal to by b if and only if a=b^k and b=a^l for some k and l. But then, a consequence of this condition is that kl-1 must be a multiple of the orders of a and b, and in particular a and b must have finite order.
It is very easy to construct different a and b for which this is true; indeed, just consider the group Z6 and a=2, b=4. Then, 2(2)=4 but 4(2)=8=2 (mod 6.) Both of these are different and satisfy the condition to have their equivalence relations be equal. As a quick check, they both have finite order: 2(3)=6=0, and 4(3)=12=0.
OK, so our result is:
Result. The relations by a and by b are equal if and only if a=b^k and b=a^l for some k and l. Furthermore, there exists a group G and different a and b that meet this condition; in fact, we can make G finite.
OK, so what we want to show is: if S is formed from two different a and b, then a and b must satisfy this condition. That would make G wrap S (without knowledge of a) well-defined.
So say there exist a and b such that S has one element from each of the equivalence classes of a, and similarly for b. In other words, no two elements of S are equal to each other by a, and no two elements of S are equal to each other by b. Furthermore, forming the set of all elements equal to something in S by a would produce all of G, and similarly for b. We can just show a=b^k; symmetry would then yield b=a^l, completing our desired.
We will get back to that. But first, we can ask: for any subset S, is it possible to find a corresponding a? If that’s true, then our construction is completely well-defined for any subset of a group.
But actually that’s not true: if G is finite, then the size of S is the number of equivalence classes. But must each equivalence class have the same size? If that’s the case, then for S to result from some a the size of S must divide the order of the group, and we can certainly find many G and S for which this isn’t the case.
Let’s show that the equivalence classes must have the same size under the relation of by a. Since G is finite, a must have finite order; hence, for some equivalence class containing b, it must contain ba^i for i less than n where n is the order of a. Furthermore, all these ba^i are distinct. In fact, if there is any element c in this equivalence class that is not of this form, then since c is equal to b by a we must have c = ba^k for some k, but that then reduces to c = ba^i for some i less than n, contradiction. Thus, the set of ba^i for i<n is the equivalence class, and each of these elements is distinct. Thus, we in fact have that the size of any equivalence class must be the order of a, hence in particular all these classes must have the same size. Hence, we can’t use this construction for any general subset S.
But this same argument (it’s not circular when we organize it properly, I’m doing stream of consciousness here while figuring things out) shows that if the relations for a and b are equal, then a and b must have the same order. (And again, we saw an example of this with 2 and 4 in Z6.) Conversely, if a and b have the same order and a=b^k, then it immediately follows that b=a^l, which we can see as follows. Letting the common order be n, if we can show existence of l and m such that kl = mn+1, then b = b^(mn+1) = b^kl = a^l, as desired. But if k and n are relatively prime, then this is immediate from Bezouts lemma. (Conversely, this won’t be possible if k and n aren’t relatively prime.) So we can say that: if a=b^k, a and b both have order n, and k and n are relatively prime, then b=a^l for some l. Thus, if a=b^k, a and b both have order n, and k and n are relatively prime, then the relations by a and by b are equal.
We also have that if the relations by a and by b are equal, then a=b^k for some k and a and b have the same order (call it n.) Can we show further that k and n must be relatively prime? Then, we’d have an alternative if and only if condition. For this case, we also have b = a^l. We also know that for any i less than n, b^i isn’t e, so li can’t be divisible by n. Or, actually, analogous logic: for any i less than n, ki can’t be divisible by n. Now assume for the sake of contradiction that k and n weren’t relatively prime, and that they had a common factor g>1. Then, if i=n/g, definitely greater than 0 and less than n, ki would dw divisible by n, contradiction. Thus, k and n must be relatively prime. So we have so far:
Result. The following are equivalent:
- The relations by a and by b are equal.
- There exist k and l such that a=b^k and b=a^l.
- There exists k such that a=b^k, a and b have the same order, call it n, and k and n are relatively prime.
Let’s try to answer our previous question: for an S that is generatable by different a and b, is the construction defined earlier well-defined depending on S and not a (or b)? In other words (equivalently), if S is formed from a and also formed from b, then are the relations by a and by b equal?
Clearly, if the relations by a and by b are equal, then any S formed from a can also be formed from b and vice versa (so the converse is clear.)
Well, actually, they must be! Say S is formed from a and also formed from b; then, by what we’ve shown so far, a and b must have the same order (which is the order of G divided by the order of S, which as discussed must be an integer.) Let this order be n. We only need to show that a=b^k for some k … actually, that is sufficient by symmetric logic, so we don’t even need to show that k and n are relatively prime. Hmm … can we reduce the if-and-only-if condition further, or have a different one that allows us to take better advantage of the information that a and b must have the same order?
We want to show an alternative condition equivalent to:
- There exists k such that a=b^k, a and b have the same order, call it n, and k and n are relatively prime.
Say a and b have the same order n. There must exist a number k less than n and relatively prime to it.
Or let’s take a different approach to showing well-definedness. Say that we’re forming S from a, so no two elements of S are related by a. We also know that S can be formed from b, so now two elements are related by b. If we can show that no two elements of G are related by a if and only if they are not related by b, then that will show the relations are in fact equal, as desired.
So we know we can construct G from S by forming the equivalence classes of each element in S. Now, say two elements in G aren’t related by a. Then, they must be in different equivalence classes, and in particular different equivalence classes of different elements of S. Say for the sake of contradiction that the two elements of G were related by b. Then, they would be in the same equivalence class, but they’d correspond to the same element of S, contradicting that S can be formed from b in the same way that it was formed from a.
Then, we can use symmetric logic, and we have our desired result!
While this last proof is great and I have the flow, I should probably rewrite it more rigorously for the sake of completeness.
OK, so for any subset S of G that takes a different element from each equivalence class of the relation by a for some a, we can define G wrap S.
What about general subsets? Is that possible? Can we develop a construction that reduces to this for an S of this form, and that also reduces to just the original operation if S is closed under the operation?
It remains to continue this.
