# On permanent mod $3^t$ computation

By $'$ I mean transpose. I gather the info here from rjlipton.wordpress.com/2014/12/21/modulating-the-permanent. We know that if $U\in\Bbb F_{3^t}^{n\times n}$ satisfies $UU'=I_n$ in $\Bbb F_{3^t}$ then we can compute $Perm(U)$ in $\Bbb F_{3^t}$ in $O(n^4)$ time.

This gives an $O(n^4)$ time algorithm for $Perm(U)\bmod 3$ for $U\in\Bbb Z^{n\times n}$ satisfying $UU'=I_n$ in $\Bbb Z$?

Can it be modified to give an $O(n^{O(t)})$ time algorithm for $Perm(U)\bmod 3^t$ for $U\in\Bbb Z^{n\times n}$ satisfying $UU'=I_n\bmod 3^r$ in $\Bbb Z$ where $r\in\Bbb N$ is fixed?

• @EmilJeřábek first sentence follows from here rjlipton.wordpress.com/2014/12/21/modulating-the-permanent right? Commented Aug 4, 2017 at 11:35
• @EmilJeřábek done including. Commented Aug 4, 2017 at 11:40
• The only matrices $U \in \mathbb{Z}^{n \times n}$ satisfying $UU^T=I$ are signed permutation matrices, for which it is trivial to compute the permanent... Commented Aug 9, 2017 at 5:23
• Interesting I did not know that but 2. still remains Commented Aug 9, 2017 at 5:32
• @777 oops, my bad. didn't realise you were asking about char 3. Now it makes sense! Commented Aug 9, 2017 at 17:05