11
$\begingroup$

A tantalizing open question in computational complexity is to understand the 'behavioral differences' between the determinant and the permanent. While the former is computable in polynomial time with Gauss pivot, the second is $\# P$-hard by Valiant's result. There have been attempts to generalize the notions of determinant/permanent, but I was wondering if the following notion of subgroup-restricted determinant had been considered.

Fix a series $\Sigma$ of subgroups $G_1 \leq G_2 \leq \ldots \leq G_k$ of $S_n$, and for an index $p \leq k$ let $\Sigma_p$ denote the truncated series $G_1 \leq G_2 \leq \ldots \leq G_p$. Say that $\Sigma$ is normal if (i) $G_1$ is simple, (ii) for each $1 \leq i < k$, $G_i$ is a maximal normal subgroup of $G_{i+1}$. We may then define, for an $n \times n$ matrix $A$:

Given $K \subseteq S_n$, let $Sum_{K}(A) = \sum_{\sigma \in K} a_{1,\sigma(1)} \ldots a_{n,\sigma(n)}$;

Let $SgrDet_{\Sigma}(A) = Sum_{G_k}(A) - \sum_{i = 1}^{k-1} [G_i : G_k] SgrDet_{\Sigma_i}(A)$.

Observe that when $G_{k}$ is isomorphic to $Z_n$, any maximal series $\Sigma$ corresponds to a prime factorization of $n = p_1^{i_1} \ldots p_k^{i_k}$, and then $SgrDet_{\Sigma}(I_n)$ corresponds to the 'signed divisor function' $\zeta'(n) = [i_1]_{-p_1} \ldots [i_k]_{-p_k}$ where by convention $[n]_q = \sum_{i = 0}^{n-1} q^i$.

Observe that we can recover the permanent and determinant with the series $(S_n)$ and $(A_n \lhd S_n)$, respectively. Note that the second series is normal (by the simplicity of $A_n$) while the first is not. This leads to the following questions, probably difficult:

(1) does the formula always have exponential algebraic complexity when the series is not normal?

(2) are there other examples of a normal series for which the formula has polynomial complexity?

(NOTE: I updated the definition of $SgrDet$ to have a better-behaved operator, but it's still unclear whether it is the 'right' definition).

$\endgroup$
  • 6
    $\begingroup$ Interesting Q! I don't think they're immediately related, but you might also be interested in immanents: defined like perm/det, but with any character of $S_n$ in place of $(\pm 1)^\sigma$. A few Qs: what do you mean $1 \unlhd S_n$ isn't a normal series? 1 is most definitely a normal subgp... FYI, if you require the series to end in $S_n$, then there essentially aren't other normal series: for $n \geq 5$, $A_n$ is the only normal subgroup of $S_n$, and $A_n$ is simple. Last, typically $\unlhd$ means "normal subgroup" by definition - did you mean to imply that each $G_i$ is normal in the next? $\endgroup$ – Joshua Grochow Apr 26 '14 at 20:19
  • $\begingroup$ Thanks, I have addressed your concerns by redefining 'normal series' and updating the notation. Regarding immanents, they seem an interesting generalization but I expect them to be $\# P$-hard to compute in all cases (except for det). Therefore, I was looking for a different generalization that would yield interesting polynomial cases. $\endgroup$ – NisaiVloot Apr 27 '14 at 12:42
  • 1
    $\begingroup$ Re: immanants, there are other interesting cases. The immanant for any character corresponding to partition of constant width can be computed in P: arxiv.org/abs/1110.1821. In the opposite direction, immanants corresponding to very wide partitions are #P-hard (see references from the introduction of the preceding). $\endgroup$ – Joshua Grochow Apr 27 '14 at 14:27
  • $\begingroup$ Thanks for clarifying. You are of course free to make definitions as you like, but it might help if you try to avoid using names that conflict with standard terminology: "Normal series" has a standard meaning (e.g. en.wikipedia.org/wiki/…). Also, can you help motivate your definition? Why require $G_1$ to be simple but not each $G_i / G_{i-1}$? $\endgroup$ – Joshua Grochow Apr 27 '14 at 14:29
  • 1
    $\begingroup$ I do not know how related this is, but another, more recent, link regarding the complexity of immanants: arxiv.org/abs/1309.2156. $\endgroup$ – Bruno Apr 28 '14 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.