Seeing is believing

Algebra Level 5

Note: We use the convention that 1 1 is the identity/neutral element of some group, and abbreviate some binary operation * between elements x , y G x, y \in G , G G a group, as ( x , y ) = x y = x y *(x, y) = x*y = xy .

Consider the dihedral group. A geometric or visual interpretation deals with polygons, which are 2 dimensional. One example of a dihedral group is to consider all vertices of a triangle under the binary operation of moving a step forward, and each vertex has some orientation (which we will denote by the presence or absence of τ \tau ). Label the vertices 1 , σ , σ 2 1, \sigma, \sigma^2 . 1 1 means you didn't move forward at all (stayed at the same point), σ \sigma means you moved a step forward, and σ 2 \sigma^2 means you moved two steps forward. But, if you multiply each vertex by τ \tau , it's almost like adding a negative sign to σ \sigma ; τ σ \tau \sigma means we first move from 1 1 to σ \sigma , then change the direction of σ \sigma in such a way that if we then try to do σ \sigma again, meaning σ ( τ σ ) \sigma (\tau \sigma ) , we end up back where we started, namely at 1 1 , except with orientation τ \tau . In other words, τ σ = σ 1 τ \tau \sigma = \sigma^{-1} \tau . It is then apparent that there are 6 6 unique elements in this dihedral group: 1 , σ , σ 2 , τ , τ σ , τ σ 2 1, \sigma, \sigma^2, \tau, \tau \sigma, \tau \sigma^2 .

Now consider the dihedral-like group which consists of the vertices of a dodecagon, 1 , σ , σ 2 , . . . , σ 11 1, \sigma, \sigma^2, ..., \sigma^{11} , and each vertex has some orientation, which is described by the presence or absence of any or all of 2018 2018 distinct elements, denoted τ 1 , τ 2 , . . . , τ 2018 \tau_1, \tau_2, ... , \tau_{2018} which under the operation of "moves forward", for each i N : 1 i < 2018 i \in \mathbb{N} : 1 \leqslant i < 2018 , each τ i \tau_i , behaves just like τ \tau from the previously mentioned dihedral group, and for 1 i < j 2018 1 \leqslant i < j \leqslant 2018 , i , j N i,j \in \mathbb{N} , τ i τ j = τ j τ i \tau_i \tau_j = \tau_j \tau_i . How many distinct elements are in this dihedral-like group? If the answer can be represented in the form 3 2 a 3 \cdot 2^a , find a a .

Bonus : To be fully rigorous, you should ignore the geometric intuition (for a minute--use it to give you an idea how to solve the problem but do not rely on it and be rigorous algebraically) and try to formulate the problem more precisely, only thinking algebraically, i.e. using bracket notation. You could define dihedral-like group as G = set of generators relations between generators G = \left \langle \text{set of generators} | \text{ relations between generators} \right \rangle , which is very precise. Also, without geometric intuition, if we define the finite group G G' as having order n n as having elements 1 , σ , σ 2 , σ 3 , . . . , σ n 1 1, \sigma, \sigma^2, \sigma^3, ..., \sigma^{n-1} , how do you know that 1 , σ , σ 2 , . . . , σ n 1 1, \sigma, \sigma^2, ..., \sigma^{n-1} are all distinct? Also, how do we know that the dihedral-like group I discussed is actually a group in the first place? You should prove that.


The answer is 2020.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Jc 506881
Feb 4, 2018

Picture each vertex σ i \sigma^i , i = 0 , , 11 i = 0, \dots, 11 of the dodecagon as having a panel of 2018 light switches next to it, each of which can be in either the on or off position. An element of the dihedral-like group, call it G G , is a pair ( σ i , P ) (\sigma^i, P) where P P is a 2018 bit binary number, the j j -th bit indicating with a 1 or 0 whether the light switch in the j j -th position on the panel is on or off. Roughly speaking, the actions of the rotation σ \sigma and the reflections τ i \tau_i are: σ ( σ i , P ) = ( σ i + 1 , P ) \sigma (\sigma^i, P) = (\sigma^{i+1}, P) and τ j ( σ i , P ) = ( σ i , δ j P ) \tau_j(\sigma^i, P) = (\sigma^i, \delta_j P) , where δ j P \delta_j P is just P P with the j j -th bit toggled. That is, σ \sigma moves you to the next vertex with the same light switch configuration and the τ j \tau_j 's toggle the light switches. It's not hard to see that there are 12 2 2018 12 \cdot 2^{2018} such elements in G G .

Regarding the bonus, I'd like to say that I disagree with the notion that one should ignore their geometric intuition in order to be rigorous. I think being rigorous and utilizing one's geometric intuition are separate things. It's certainly possible to use geometric intuition in a non-rigorous way, for instance by trying to generalize a result from an overly simplified example picture, but it has been my experience that it's just as easy to fall into that trap pushing symbols around as it is thinking geometrically. Being careful is being careful, regardless of what types of ideas you're thinking about. Also, applying geometric intuition in a rigorous way can lead to interesting results, especially in the context finitely presented groups. Approaching finitely presented groups on a purely formal/symbolic level often leads nowhere. For instance, determining whether a group generated from a given presentation is abelian, or simple, or trivial, or isomorphic to another presentation, etc... are all provably undecidable problems. However, if you look at Coxeter groups, or fundamental groups, or word-hyperbolic groups, each of which can be examined through a geometric lens, you are able to get some results.

Well the only reason why I said ignore it is because if you don't use geometry, it's not immediately obvious that the 1 , σ , σ 2 , . . . , σ 11 1, \sigma, \sigma^2, ..., \sigma^{11} are distinct, which needs to be proven if one wants to be extremely rigorous. I have edited the bonus to be clearer about this--my only point is, when you solve the problem you should be rigorous and not just rely on geometry/intuition, that's all, because intuition sometimes fails. Good solution though.

Hobart Pao - 3 years, 4 months ago

1 pending report

Vote up reports you agree with

×

Problem Loading...

Note Loading...

Set Loading...