{"id":210,"date":"2015-04-23T12:23:10","date_gmt":"2015-04-23T10:23:10","guid":{"rendered":"http:\/\/duch.mimuw.edu.pl\/~bojan\/podpunkt\/?page_id=210"},"modified":"2015-06-22T16:37:31","modified_gmt":"2015-06-22T14:37:31","slug":"group-case","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20142015-2\/alg\/4-factorisation-trees\/group-case","title":{"rendered":"Group case"},"content":{"rendered":"

Define a\u00a0nontrivial prefix\u00a0<\/em>of a word to be a prefix which is neither empty nor full. The following lemma shows that the Factorisation Tree Theorem<\/a> holds for groups.<\/p>\n

Lemma.\u00a0<\/b>If \"G\" is\u00a0a finite group, then every \"w \in G^+\" is the yield of some\u00a0\"G\"-factorisation tree of height at most 3 times the size of \"[w]\" where \"[w] \subseteq G\" is the set of types of nontrivial prefixes of \"w\".<\/p>\n

Proof.\u00a0<\/b>The lemma is proved by induction on the size of \"[w]\". \u00a0If this set is empty,\u00a0\u00a0then the word has one letter, and therefore has a \"G\"-factorisation tree consisting only of a leaf.<\/span><\/p>\n

Let us therefore focus on the induction step. Consider a word \"w\" with \"[w]\" nonempty, and let \u00a0\"g \in [w]\". Cut the\u00a0word \"w\" in all places where we find a nontrivial prefix of type \"g\". In other words, consider a factorisation <\/p>\n

  <\/span>   <\/span>\"\[w = w_1 w_2 \cdots w_n\]\"<\/p>\n

such that the only nontrivial prefixes of \"w\" with type \"g\" are <\/p>\n

  <\/span>   <\/span>\"\[w_1, \quad w_1w_2, \quad \ldots, \quad w_1 \cdots w_{n-1}\]\"<\/p>\n

By choice of the factorisation, \u00a0\"[w_1]\" is a subset of \"[w]\" that does not contain \"g\", and therefore the induction assumption can be applied to \"[w_1]\". For similar reasons, if \"i \ge 2\" then \u00a0\"g \cdot [w_i]\" is a subset of \"[w]\" that does not contain \"g\". Note that multiplying a subset \u00a0of a group by \"g\" on the left does not affect\u00a0its\u00a0cardinality, and therefore each \"[w_i]\" has smaller size than \"[w]\", and therefore the induction assumption can be applied as well. Summing up, to\u00a0every \"w_1,\ldots,w_n\" we can apply the induction assumption.<\/p>\n

If \"i \in \{2,\ldots,n-1\}\" then\u00a0the\u00a0type of \"w_i\" goes from \"g\" to \"g\", \u00a0and in a group there is only one such element, namely the identity. Therefore all words \"w_2,\ldots,w_{n-1}\" have type which is the group identity, and therefore an idempotent node can be used to group all of them into a single tree. To this tree, the words \"w_1\" and \"w_n\" can be added using a binary rule. This construction creates a tree whose height is 3 plus the maximal height of any tree for \"w_1,\ldots,w_n\", thus completing the proof of the\u00a0lemma. \"\Box\"<\/span><\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

Define a\u00a0nontrivial prefix\u00a0of a word to be a prefix which is neither empty nor full. The following lemma shows that the Factorisation Tree Theorem holds for groups. Lemma.\u00a0If is\u00a0a finite group, then every is the yield of some\u00a0-factorisation tree of height at most 3 times the size of where is the set of types of […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":208,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-210","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/210"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=210"}],"version-history":[{"count":3,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/210\/revisions"}],"predecessor-version":[{"id":466,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/210\/revisions\/466"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/208"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=210"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}