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

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

<blockquote>
  <p>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?</p>
</blockquote>

CC BY-SA 3.0
2017-08-04T11:35:00.203Z
@EmilJeřábek first sentence follows from here https://rjlipton.wordpress.com/2014/12/21/modulating-the-permanent/ right?
Turbo
CC BY-SA 3.0
2017-08-04T11:40:40.827Z
@EmilJeřábek done including.
Turbo
CC BY-SA 3.0
2017-08-09T05:23:15.557Z
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...
Joshua Grochow
CC BY-SA 3.0
2017-08-09T05:32:14.547Z
Interesting I did not know that but 2. still remains
Turbo
CC BY-SA 3.0
2017-08-09T15:27:49.050Z
Have you tried working through the paper yourself and seeing if you could get it to work? Did you encounter some obstacle in doing so? (Also, the my previous comment about unitary integer matrices is an easy exercise: start by considering the first row of $U$.)
Joshua Grochow
CC BY-SA 3.0
2017-08-09T16:13:20.000Z
@JoshuaGrochow I tried working through the paper. It uses some constructions which are valid only for finite fields. So this looks like either an open problem or something trivial and no utility.
Turbo
CC BY-SA 3.0
2017-08-09T16:51:43.097Z
@777 Maybe I'm missing something, but doesn't Valiant already do this in his classic paper? Braverman, Kulkarni and Roy show $\oplus L$ bound for computing Permanent modulo 2^k (for fixed $k$) and seem to say that they are improving on the P upper bound originally due to Valiant. See http://www.cs.toronto.edu/~mbraverm/Papers/PlanarDet.pdf
Nikhil
CC BY-SA 3.0
2017-08-09T16:54:23.843Z
@Nikhil sorry that sounds mod 2^k right?
Turbo
CC BY-SA 3.0
2017-08-09T17:00:34.533Z
@777 Theorem 3 in https://pdfs.semanticscholar.org/9c18/8b3291a7e83d667764be3377a99e15b4d988.pdf seems to suggest that permanent mod $2^k$ can be computed in $n^{4k-3}$ bit operations
Nikhil
CC BY-SA 3.0
2017-08-09T17:05:24.507Z
@777 oops, my bad. didn't realise you were asking about char 3. Now it makes sense!
Nikhil
CC BY-SA 3.0
2017-08-09T19:46:41.520Z
@777: Very good; this is useful information to include in the statement of the question (e.g. "If one considers the construction on p. blah of Kogan, I couldn't see how to get it to work in the setting mod $3^t$ instead of $\mathbb{F}_{3^t}$"). That way people don't duplicate your work, and they know more specifically where to look and what obstacles really need to be overcome.
Joshua Grochow
<ds.algorithms><counting-complexity><matrices><permanent><finite-fields>
On permanent mod $3^t$ computation
Turbo
# On permanent mod $3^t$ computation

(Asked by: username_0 on 2017-08-04)

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?

**Tags:** ds.algorithms, counting-complexity, matrices, permanent, finite-fields
> **Comments:**
> **username_0**: @EmilJeřábek first sentence follows from here https://rjlipton.wordpress.com/2014/12/21/modulating-the-permanent/ right?  
> **username_0**: @EmilJeřábek done including.  
> **username_1**: 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...  
> **username_0**: Interesting I did not know that but 2. still remains  
> **username_1**: Have you tried working through the paper yourself and seeing if you could get it to work? Did you encounter some obstacle in doing so? (Also, the my previous comment about unitary integer matrices is an easy exercise: start by considering the first row of $U$.)  
> **username_0**: @JoshuaGrochow I tried working through the paper. It uses some constructions which are valid only for finite fields. So this looks like either an open problem or something trivial and no utility.  
> **username_2**: @777 Maybe I'm missing something, but doesn't Valiant already do this in his classic paper? Braverman, Kulkarni and Roy show $\oplus L$ bound for computing Permanent modulo 2^k (for fixed $k$) and seem to say that they are improving on the P upper bound originally due to Valiant. See http://www.cs.toronto.edu/~mbraverm/Papers/PlanarDet.pdf  
> **username_0**: @Nikhil sorry that sounds mod 2^k right?  
> **username_2**: @777 Theorem 3 in https://pdfs.semanticscholar.org/9c18/8b3291a7e83d667764be3377a99e15b4d988.pdf seems to suggest that permanent mod $2^k$ can be computed in $n^{4k-3}$ bit operations  
> **username_2**: @777 oops, my bad. didn't realise you were asking about char 3. Now it makes sense!  
> **username_1**: @777: Very good; this is useful information to include in the statement of the question (e.g. "If one considers the construction on p. blah of Kogan, I couldn't see how to get it to work in the setting mod $3^t$ instead of $\mathbb{F}_{3^t}$"). That way people don't duplicate your work, and they know more specifically where to look and what obstacles really need to be overcome.  

---

## 0 answers

