lelbaba's blog

Ideas of Group Theory in CP
By lelbaba, history, 3 years ago, In English

Hi everyone. I have been getting into abstract algebra out of interest and recommendation. When I read about permutations and their cyclic decomposition from group theory perspective, I have been trying to find other objects or common problems that often come up in competitive programming and can be viewed through the lens of group theory in a different perspective. So far I have only found burnside's lemma for counting problems. I am also looking for problems that may be simplified through isomorphism or other concepts that are fundamental in group theory. The ones I did find seem to be way out of my league :(

  • Vote: I like it
  • +34
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
3 years ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

I would recommend looking at elementary number theory from a group theoretic perspective. Algebraic number theory deals with some very natural generalizations using an abstract algebraic perspective, so I would recommend looking into that too.

→ Reply
»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Knowing the language of group theory is essential to understanding how many data structures work and how they relate to each other.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    wut

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +22 Vote: I do not like it

      Perhaps they are referring to the fact that you can use segment trees for cases where elements of the array form a monoid and updates are monoid actions, and Fenwick tree can be used for cases where elements of the array form a group and updates are group actions (modified implementations can allow us to drop the requirement of identity in each case, leading to the requirements for segment tree being (semigroup, semigroup actions) and (inverse semigroup, inverse semigroup actions) respectively). For me, this helps in doing a sanity check while proving my solution.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        I mean, sure, the basic notions of various algebraic structures and properties is certainly helpful in that context but my perception of the OP question was that they were interested in some actual group theory concepts or results(like Burnside's lemma) applicable in CP.

        And since I've already started writing this comment, two examples come to my mind:
        1. Problems like "two strings are called equivalent if we can make them the same by performing some operations like insert '121' anywhere or delete '21' substring, do something about it". You say that these rules are actually presentation of a group and that simplifies the problem. Example
        2. Schreier–Sims algorithm, which was discussed (in Russian) here.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +31 Vote: I do not like it

          That reminds me of this recent SWERC problem that used the idea of presentation of a group, and is very similar to point 1 in your comment.

          As far as group theoretic ideas in CP are concerned, there's the idea of Pontryagin duality, which leads to a generalization of FFT to locally compact abelian groups using characters (I have set a relatively straightforward problem using this as a starting idea as well). There's also the idea of generators for structures that are not necessarily groups which is used in this problem (it might look like number theory but it is quite natural to look at it as a monoid). And the idea of transpositions generating permutations is quite natural in problems that involve swaps and stuff, so I would say knowing a bit of group theory is useful there as well.

          Apart from that, I've seen a lot of group theory being used in number theory problems (more technical stuff like Sylow groups and stuff) in math olympiads, but not really in competitive programming.

          → Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

You can try this

→ Reply