PIMS - SFU Discrete Math Seminar: Haggai Liu

Abstract: Given a group G with a finite set of generators, S, it is natural to ask if the product of n generators from S evaluate to the identity. The enumerative version of this problem, known as the cogrowth problem, counts the number of such products and studies the associated counting sequence. Many cogrowth sequences are known. We focus on the free products of finite groups: Specifically, cyclic and dihedral groups. Such groups have the property that their cogrowth generating functions are algebraic functions, and thus, are solutions to implicit polynomial equations. Using algebraic elimination techniquesand free probability theory, we establish upper bounds on the degrees of the polynomial equations that they satisfy. This has implications for asymptotic enumeration, and makes it theoretically possible to determine the functions explicitly.