Math 6161 : Algebraic Combinatorics

This is the third set of homework problems Link to main web page for the course

I would like you all to show me your results. After you have finished these programs please email them to me and I will post the shortest solution.

Solutions to the homework problems

Exercise 1:
Given a value n for the number of variables and an deg for the degree, write a function to list the monomials of degree deg in the n variables.
(Hint: given a subset SS and a value n, write a function subset_to_monomial( SS, deg ) which converts a subset into a monomial, then write another function list_all_monomials( n, deg ) which makes a list of monomials by calling this function). Recall that in the last class I gave a formula to convert subsets to monomials. Here is the correct version of that formula. If $S = \{ a_1 < a_2 < \cdots < a_{n-1} \}$, $$x_1^{a_1-1} x_2^{a_2-a_1-1} \cdots x_{n-1}^{a_{n-1}-a_{n-2}-1} x_n^{n+d-1-a_{n-1}}$$ Here is the function list_all_monomials( n, deg ) that I provided in class.

sage: def list_all_monomials( n, deg ): ....: return [subset_to_monomial( SS, deg ) for SS in Subsets(n+deg-1, n-1)]

Exercise 2:
Given an element of the dihedral group (generated by two elements $x$ and $y$ with $x^n = y^2 = 1$ and $x y = y x^{-1}$) and a polynomial in 2 variables ${\mathbb C}[ a_1, a_2 ]$, write a function which acts on the polynomial according to the action: $x(a_1) = \zeta a_1$, $y(a_1) = a_2$ where $\zeta$ is an $n^{th}$ root of unity. That is, write a function dihed_action( groupelt, poly ) returns a polynomial where groupelt has acted on poly. (Hint: the way that you represent a group element can be using the built in DihedralGroup(n) or it can be that you think of your group is a list of pairs Dn = [ (a, b) for a in range(n) for b in range(2) ]. The bijection between these two sets is demonstrated in the following code.

sage: n = 4 # as an example take n=4 sage: (x,y) = DihedralGroup(n).gens() # this group is generated by two elements sage: D4 = [ (a, b) for a in range(n) for b in range(2) ] # this is a list of exponents sage: D4 [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)] sage: [ x^a*y^b for (a,b) in D4 ] [(), (1,4)(2,3), (1,2,3,4), (1,3), (1,3)(2,4), (1,2)(3,4), (1,4,3,2), (2,4)] sage: DihedralGroup(n).list() # not in the same order but the same elements [(), (2,4), (1,2)(3,4), (1,2,3,4), (1,3), (1,3)(2,4), (1,4,3,2), (1,4)(2,3)]

There are several ways of working with a root of unity in sage. Two are CyclotomicField(n).zeta() and exp(2*pi*I/n). You may need to experiment to see which works better.

The command subs is a method of polynomials that might be useful. For instance, poly.subs( a1 = a2, a2 = a1 ) should substitute a1 for a2 and vice versa.

Exercise 3:
Write a function dihed_char( deg, groupelt ) which returns the character of the dihedral action of the module spanned by all monomials of degree deg.

Exercise 4:
Write a function which given a degree deg, returns the decomposition of the result of dihed_char into irreducible characters.

Note: There may be a holdup here because in Exercise 3 it was ok to define your character function to work only with pairs (a, b) with a in range(n) and b in range(2). But here you want to take a scalar product with the characters of the DihedralGroup(n).irreducible_characters() and so suddenly you want your character to really work with elements of DihedralGroup(n) so that you can take a scalar product (scalar_product is a method built into the characters). The following are two functions which converts group element to a pair (a,b) and back.

def group_element_to_pair( g ): """ Converts a group element g of DihedralGroup(n) into a pair (a,b) with a in range(n) and b in range(2) EXAMPLES:: sage: [group_element_to_pair(g) for g in DihedralGroup(4)] [(0, 0), (3, 1), (2, 1), (1, 0), (1, 1), (2, 0), (3, 0), (0, 1)] """ G = g.parent() # this is the dihedral group (x,y) = G.gens() # these are the generators # the following construction is a 'dictionary' which maps group elements # to pairs over all possible group elements (not efficient, but it works) M = { x^a*y^b : (a,b) for a in range(G.order()/2) for b in range(2) } return M[g] def pair_to_group_element(p, n): """ Converts a pair p = (a,b) into a group element of the DihedralGroup(n) Given n, this function is the inverse of group_element_to_pair EXAMPLES:: sage: all(pair_to_group_element(group_element_to_pair( g ), 4)==g for g in DihedralGroup(4)) True sage: all(group_element_to_pair(pair_to_group_element((a,b),4))==(a,b) for a in range(4) for b in range(2)) True """ G = DihedralGroup(n) (x,y) = G.gens() return x^p[0]*y^p[1]

If you want to see how this works try the following commands

sage: pair_to_group_element((3,1), 5) (1,2)(3,5) sage: group_element_to_pair(_) # underline means the result of the last calculation (3, 1) sage: group_element_to_pair(DihedralGroup(5).list()[4]) (2, 1) sage: [group_element_to_pair(g) for g in DihedralGroup(5)] [(0, 0), (4, 1), (3, 1), (1, 0), (2, 1), (2, 0), (1, 1), (3, 0), (4, 0), (0, 1)]