From solving "playful" "puzzle" to Dehn functions

   Introduction: A group can be represented via letters and the relations between these letters. While it might be easy to realize the element by our knowledge in the corresponding group structures, it requires much more steps to delve into the letters in the representation and the relations. Such "playful" and "time-consuming" operations on letters lead to the birth of a mathematical topic: Dehn functions, which was named after the German mathematician Max Dehn (1878 - 1952). 

1. What is the Dehn function? 

   Consider a group G and a representation G = <S|R> of G. An element of the free group generated by S represents the identity in G if it can be converted to the empty word (i.e. the identity element of the free group generated by S) by applying one of the following types of move: 
   - Type 1: Free reduction uss^(-1)v -> uv 
   - Type 2: Free expansion uv -> uss^(-1)v
   - Type 3: wuw' -> wvw', where uv^(-1) or vu^(-1) is a cyclic permutation of an element of R. 
   A question can be raised: given a representation corresponding to the identity element, what is the number of moves that we need to apply in order to convert this representation to the empty word? In other words, we want to measure the complexity of this algorithm. In computer science, when we take complexity into consideration, we should indicate the size of the data (set). In this particular case, the length of the word is perhaps one of the most direct and appropriate ways to measure the size. 
   This leads to the definition of the Dehn function f(n) (where n is a positive integer), which is defined as the largest number of moves of Type 3 that we need to apply in order to convert a word w satisfying |w| <= n to the empty word (it is obvious that w must represent the identity element). In fact, we also need to apply moves of Type 1 and Type 2, but these types of moves are not related to the relations, thus the Dehn function won't consider. This is similar to the enumeration of steps in certain sorting algorithms in computer science, where we only care about the number of comparisons or swaps in a type of algorithm. 
   You might wonder about the name "puzzle" of this manuscript. In fact, the algorithms mentioned in the Dehn function correspond to solving a type of puzzle. The equivalence between them will be discussed in another manuscript.  

2. Some examples
  2.1. How to apply the three types of move
   
   Consider the group G = <a, b, c| a^(-1)b^(-1)ab = c, ac = ca, bc = cb>. Here is a possible way to apply the three types of move mentioned in section 1 to convert a^(-2)b^(-1)ab^2ab^(-1) to the empty word: 
   - First, rewrite the word as a^(-1)(a^(-1)b^(-1)ab)bab^(-1)
   - Replace a^(-1)(a^(-1)b^(-1)ab)bab^(-1) -> a^(-1)cbab^(-1) (one move of Type 3)
   - Replace a^(-1)cbab^(-1) -> a^(-1)bcab^(-1) (one move of Type 3)
   - Replace a^(-1)bcab^(-1) -> a^(-1)bacb^(-1) (one move of Type 3)
   - Replace a^(-1)bacb^(-1) -> a^(-1)baa^(-1)b^(-1)abb^(-1) (one move of Type 3)
   - Applying moves of Type 1 four times to obtain the empty word
   In fact,  if we are lazy and smart, the second and the third move of Type 3 can be "merged" in our textbook. As c commutes with a and b, the letter c can be "move freely" to anywhere in the word. However, as indicated in the definition of the three types of move and the Dehn function, we are only allowed to use the relations indicated in the representation of the group. This means that any additional relation that can be inferred from the original representation/relation can't be used. Roughly speaking, we should "respect" the relations in the representation. Therefore, each move only consists of moving c one "cell" to the left or to the right and we can't "merge" different steps when considering the Dehn function. 

  2.2. The Dehn function of certain representations
   
   Example 1: Given a positive integer m. We consider the cyclic group of order m represented my <a | a^m = e>. If w is a word of length at most n, w can be converted to a word of the form a^(n_0), where n_0 is an integer (possibly negative) after a finite number of free reductions (i.e. moves of Type 1). It is obvious that |n_0| <= n and n_0 is divisible by m. If n_0 is positive, we can obtain the empty word after applying n_0/m moves of Type 3: 
                              a^(n_0) = a^m*a^(n_0 - m) -> e*a^(n_0 - m) = a^(n_0 - m) (first move)
                    a^(n_0 - m) = a^m*a^(n_0 - 2m) -> e*a^(n_0 - 2m) = a^(n_0 - 2m) (second move)
                                                                                                    ...
                                                                                            a^m -> e (the (n_0/m)-th move)
   Since |n_0| <= n, the number of moves doesn't exceed [n/m]. 
   Let n_0 be the largest multiple of m that is smaller than or equal to m. Since each move can only remove at most m letters from the word, converting the word a^(n_0) of length <= m to the empty word requires at least n_0/m = [n/m] moves. The Dehn function is exactly f(n) = [n/m]. 
   
   Example 2: In fact, the Dehn function of a finite representation of a finite group G is always bounded above by Cn, where C is a constant that does not depend on the length n. We will prove this by induction on n. We can choose a constant C such that the claim holds for all n <= |G|. If n > |G|, assume that the claim holds for all words of length smaller than n. Consider a word w = w(1)w(2)...w(n) of length n that represents the identity. The sequence 
                                          u(1) = w(1), u(2) = w(1)w(2), ..., u(|G| + 1) = w(1)w(2)...w(|G| + 1)
   consists of |G| + 1 words. Meanwhile, G has only |G| elements. By the pigeonhole principle, there exists two words in the sequence u(1), u(2), ..., u(|G| + 1) that represents the same element. Let these two words be u(i), u(j) (i < j). Since u(i), u(j) represents the same element, the word w(i + 1)w(i + 2)...w(j) represents the identity. We can divide our jobs into two separated stages: 
   - First stage: Convert w(i + 1)w(i + 2)...w(j) to the empty word => At most C times (j - i) moves of Type 3 are needed (By our hypothesis)
   - Second stage: Convert u(i)w(j + 1)w(j + 2)...w(n) to the empty word => At most C times (n - j + i) moves of Type 3 are needed (Again by our hypothesis)
   Therefore, we need to apply at most Cn moves of Type 3. 


Nhận xét

Đăng nhận xét

Bài đăng phổ biến từ blog này

Trước khi đi du học ngành toán tại Đức

Hình ảnh
Bài viết này tổng hợp những câu chuyện mang tính cá nhân về quá trình tôi chuẩn bị cho chuyến du học tại Đại học Bonn (Đức), một ngôi trường khá danh tiếng về ngành toán. Tôi đã chia sẻ khá đầy đủ những kinh nghiệm hữu ích cho mọi người trong  quyển guideline này , do đó trong bài viết này tôi sẽ đề cập đến những khía cạnh khác, chẳng hạn như trải nghiệm của tôi với các giáo sư ở Đức, hướng nghiên cứu của bản thân, hay là cả những câu chuyện mang tính giải trí cực cao.  1. Trước khi có ý định đi Đức, tôi KHÔNG BIẾT GÌ về Đại học Bonn và những trường khác ở Đức      Hồi năm thứ 1 và năm thứ 2, tôi chỉ tập trung học chứ gần như không tìm hiểu về các nhà toán học cũng như nơi công tác của họ. Lúc đó tôi chỉ thấy các trường ở Mỹ hấp dẫn vì có khá nhiều hướng nghiên cứu, hơn nữa hầu hết các trường đều có các giáo sư làm về đại số  và tổ hợp , những lĩnh vực tôi yêu thích nhất vào lúc đó. Tôi cũng biết rằng  Giáo sư Phan Thành Nam là một trong những cựu si...
Đọc thêm

Some remarkable statistics about the major of (pure) mathematics at several universities in the world

Hình ảnh
1. The number of PhD/Graduate students at some US universities    Many US universities indicated all of their graduate students on their websites. For example, the following image shows the list of graduate students in mathematics at Harvard University.     Based on these lists, I just counted the number of graduate students at some universities and got the following result(s): MIT has 122 students, Cornell University has 80 students, Texas A&M University has 105 students, Stanford University has 65 students, Harvard University has 64 students, Yale University has 46 students, University of Utah has 90 students, The University of Chicago has 81 students, City University of New York has 76 students and University of California, Berkeley (UCB) has 175 students.  2. The number of PhD/Graduate students from several universities who later became speakers at International Congress of Mathematicians    Being invited at International Congress of Mathe...
Đọc thêm

Some interesting facts about Vietnamese

Here is a collection of interesting facts about the language of Vietnamese (tiếng Việt) that I just found out when talking to my friends, who are all Europeans, in Bonn (Germany).  1. In Vietnamese, grandson and nephew are called the same (cháu trai). Similarly, granddaughter and niece are also called the same (cháu gái).  2. In Vietnamese, you can use the same pronoun "em" to call your younger sibling, no matter whether it is your younger brother or your younger sister. Similarly, this pronoun can be used to call someone who is just a few years younger than you, no matter whether this person is a man or a woman.  3. However, when referring to your older sibling, you must use the pronoun "anh" to call your older brother and the pronoun "chị" to cold your older sister. Similarly, you can use the pronoun "anh" to call a boy who is just a few years older than you and the pronoun "chị" to call a girl who is just a few years older than you. ...
Đọc thêm