<p>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 <em>subgroup-restricted determinant</em> had been considered.</p>

<p>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 <em>normal</em> if (i) $G_1$ is simple, (ii) for each $1 \leq i &lt; k$, $G_i$ is a maximal normal subgroup of $G_{i+1}$. We may then define, for an $n \times n$ matrix $A$:</p>

<blockquote>
  <p>Given $K \subseteq S_n$, let $Sum_{K}(A) = \sum_{\sigma \in K} a_{1,\sigma(1)} \ldots a_{n,\sigma(n)}$;</p>
  
  <p>Let $SgrDet_{\Sigma}(A) = Sum_{G_k}(A) - \sum_{i = 1}^{k-1} [G_i : G_k] SgrDet_{\Sigma_i}(A)$.</p>
</blockquote>

<p>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$.</p>

<p>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:</p>

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

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

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

CC BY-SA 3.0
2014-04-26T20:19:51.890Z
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?
Joshua Grochow
CC BY-SA 3.0
2014-04-27T12:42:26.550Z
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.
NisaiVloot
CC BY-SA 3.0
2014-04-27T14:27:41.530Z
Re: immanants, there are other interesting cases. The immanant for any character corresponding to partition of constant width can be computed in P: http://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).
Joshua Grochow
CC BY-SA 3.0
2014-04-27T14:29:00.940Z
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. http://en.wikipedia.org/wiki/Subgroup_series#Normal_series.2C_subnormal_series). Also, can you help motivate your definition? Why  require $G_1$ to be simple but not each $G_i / G_{i-1}$?
Joshua Grochow
CC BY-SA 3.0
2014-04-27T15:33:12.190Z
These references about the immanants are welcome; I was wrong then, there should be a non-trivial complexity dichotomy lying there. Also, I need to see if I can exhibit some interesting polynomial case in praise of my definition; the simplest way might be to consider some (exponential-size) abelian subgroup of $S_n$, but it's not clear how to construct one. Finally, I've added a qualifier 'maximal' to address your last question.
NisaiVloot
CC BY-SA 3.0
2014-04-27T15:36:11.420Z
For a large abelian subgroup of $S_n$, just consider the largest cyclic subgroup: if I recall correctly, this has order around $exp(\sqrt{n})$.
Joshua Grochow
CC BY-SA 3.0
2014-04-28T08:44:27.743Z
I do not know how related this is, but another, more recent, link regarding the complexity of immanants: http://arxiv.org/abs/1309.2156.
Bruno
CC BY-SA 4.0
2021-05-02T03:24:37.133Z
Larger abelian subgroup of $S_n$: that generated by the adjacent transpositions of the form $(2i,2i+1)$ is isomorphic to $C_2^n$.
Joshua Grochow
<permutations><gr.group-theory><arithmetic-circuits>
Generalizations of the determinant/permanent problem?
NisaiVloot
# Generalizations of the determinant/permanent problem?

(Asked by: username_0 on 2014-04-26)

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).

**Tags:** permutations, gr.group-theory, arithmetic-circuits
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_1**: Re: immanants, there are other interesting cases. The immanant for any character corresponding to partition of constant width can be computed in P: http://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).  
> **username_1**: 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. http://en.wikipedia.org/wiki/Subgroup_series#Normal_series.2C_subnormal_series). Also, can you help motivate your definition? Why  require $G_1$ to be simple but not each $G_i / G_{i-1}$?  
> **username_0**: These references about the immanants are welcome; I was wrong then, there should be a non-trivial complexity dichotomy lying there. Also, I need to see if I can exhibit some interesting polynomial case in praise of my definition; the simplest way might be to consider some (exponential-size) abelian subgroup of $S_n$, but it's not clear how to construct one. Finally, I've added a qualifier 'maximal' to address your last question.  
> **username_1**: For a large abelian subgroup of $S_n$, just consider the largest cyclic subgroup: if I recall correctly, this has order around $exp(\sqrt{n})$.  
> **username_2**: I do not know how related this is, but another, more recent, link regarding the complexity of immanants: http://arxiv.org/abs/1309.2156.  
> **username_1**: Larger abelian subgroup of $S_n$: that generated by the adjacent transpositions of the form $(2i,2i+1)$ is isomorphic to $C_2^n$.  

---

## 0 answers

