# Deligne-Simpson problem in the symmetric group

Question. Let $C_1,\dots,C_k$ be conjugacy classes in the symmetric group $S_n$. (More explicitly, each $C_i$ is given by a partition of $n$; $C_i$ consists of permutations whose cycles have the length prescribed by the partition.) Give a necessary and sufficient condition on $C_i$ that would ensure that there are permutations $\sigma_i\in C_i$ with $$\prod\sigma_i=1.$$

Variant. Same question, but now $\sigma_i$'s are required to be irreducible in the sense that they have no common invariant proper subsets $S\subset\lbrace 1,\dots,n\rbrace$.

I am not certain how hard this question is, and I would appreciate any comments or observations. (I was unable to find references, but perhaps I wasn't looking for the right things.)

This question is inspired by Jonah Sinick's question via the simple

Geometric interpretation. Consider the Riemann sphere with $k$-punctures $X=\mathbb{CP}^1-\lbrace x_1,\dots,x_k\rbrace$. Its fundamental group $\pi_1(X)$ is generated by loops $\gamma_i$ ($i=1,\dots,k$) subject to the relation $$\prod\gamma_i=1.$$ Thus, homomorphisms $\pi_1(X)\to S_n$ describe degree $n$ covers of $X$, and the problem can be stated as follows: Determine whether there exists a cover of $X$ with prescribed ramification over each $x_i$. The variant requires in addition the cover to be irreducible.

Background. The Deligne-Simpson Problem refers to the following question:

Fix conjugacy classes $C_1,\dots,C_k\in\mathrm{GL}(n,\mathbb{C})$ (given explicitly by $k$ Jordan forms). What is the necessary and sufficient condition for existence of matrices $A_i\in C_i$ with $$\prod A_i=1$$ (variant: require that $A_i$'s have no common proper invariant subspaces)?

There are quite a few papers on the subject; my favorite is Simpson's paper, which has references to other relevant papers. The problem has a very non-trivial solution (even stating the answer is not easy): first there is a certain descent procedure (Katz's middle convolution algorithm) and then the answer is constructed directly (as far as I understand, there are two answers: Crawley-Boevey's argument with parabolic bundles, and Simpson's construction using non-abelian Hodge theory).

The same geometric interpretation shows that the usual Deligne-Simpson problem is about finding local systems (variant: irreducible local systems) on $X$ with prescribed local monodromy.

So: any remarks on what happens if we go from $\mathrm{GL}(n)$ to $S_n$?

-
Does looking at permutation matrices over $\mathbb{F}_2$ give you anything from the D-S result? –  Steve Huntsman Jan 23 '10 at 18:08
@Steve Huntsman: That's an interesting idea. I do not think you get much immediately... and, at any rate, some methods in the usual DS problem rely on characteristic 0. But it's definitely worth thinking about. –  t3suji Jan 23 '10 at 18:21
It might be worth looking at permutation matrices over $\mathbb{C}$ then, but probably not. –  Steve Huntsman Jan 23 '10 at 22:29

This question is a more than 100 years old problem and it is called in the litearture "Hurwitz exitence problem". This is an open problem. Though many partial cases are solved. For example you can check the following article

On the existence of branched coverings between surfaces with prescribed branch data, I Ekaterina Pervova, Carlo Petronio

http://arxiv.org/abs/math/0508434

Of course, you can give an obvious formal answer, (in the first case that is not irreducible) that the cover exists if and only if the product of the elements in the group algebra of $S_n$ corresponding to the permutation that you chose contains $1$ in their decomposition. But this is just a reformulation of the problem.

Here is a different example of a recent article on Hurwitz existence problem, it contains in partcular a lot of references on the research in this topic.

Solution of the Hurwitz problem for Laurent polynomials

http://arxiv.org/abs/math/0611776

Also notice that there is a whole branch of math nowadays where people try to compute the actual number of ramified covers, and not only to answer the quesiton wheather a cover exists or not. Here is a typical example

Gromov-Witten theory, Hurwitz theory, and completed cycles Authors: Andrei Okounkov, Rahul Pandharipande http://arxiv.org/abs/math/0204305

-
Can you express the irreducibility condition in the variant in the group algebra? The outer automorphism on S_6 shows irreducibility is not an intrinsic property, but is that just isolated? –  Douglas Zare Jan 23 '10 at 18:32
Douglas, you are right what I said does not deal with the irreducible case. I don't know how to formulate this in the irreducible case. –  Dmitri Jan 23 '10 at 18:47
Thanks a lot for the answer, and particularly for the reference. Let me look it up. –  t3suji Jan 23 '10 at 19:07

(wanted to make this a comment but couldn't figure how)

As Dmitri says, you can express the number of ramified covers using the group algebra of S_n, not just whether it's nonzero; once you do this, an inclusion/exclusion argument based on splitting up the conjugacy classes into smaller partitions lets you figure out the number of these that are irreducible. this is an in-principle answer that's of course totally useless in practice

-