7
$\begingroup$

Let $R$ be a finite ring with operations $(+,\cdot)$. Let $A \in R^{m\times n}$ and $b\in R^{m}$.

Questions:

  1. What is the complexity of counting the number of solutions to the system of equations $Ax = b$? Can it be done in polynomial time?
  2. More generally, let $R$ is a finite set and $(+,\cdot)$ be binary opeartions such that $(R,+)$ and $(R,\cdot)$ are (not necessarily commutative) semigroups. What is the complexity of counting the number of solutions to a system of linear equations $Ax=b$?

Note that it is well known that the answer to Question 1 is affirmative if the the ring $R$ is a finite field.

$\endgroup$
2
  • $\begingroup$ Perhaps Smith normal form can help in some cases. $\endgroup$ Sep 1, 2016 at 15:13
  • $\begingroup$ You might want to narrow this down by specifying what type of ring you are talking about. Are we guaranteed that the ring has a multiplicative identity? Commutative ring? Principle Ideal Domain? Division ring? Or do you want to know for the general case, where the ring need not be commutative? I suggest you take a look at math.stackexchange.com/q/414385/14578. Also consider the case of the ring of integers modulo $N$ where $N=pq$ is a product of two different prime numbers, chosen large enough that $N$ is hard to factor, to see one hard case. $\endgroup$
    – D.W.
    Sep 1, 2016 at 23:01

1 Answer 1

7
$\begingroup$

The answer to (1) is yes (regardless of the properties D.W. asked for in the comments), depending on how $R$ is given: First, note that since $R$ is finite, the abelian group $(R,+)$ is of the form $\mathbb{Z}_{p_1^{k_1}} \oplus \dotsb \oplus \mathbb{Z}_{p_\ell^{k_\ell}}$, where $\ell \leq \log_2|R|$. Now, if $R$ is only given to you by generators and relations, even finding this decomposition is as hard as factoring (but given a factoring oracle, it can then be done easily). But if $R$ is fixed for all time (not part of the input), then this can be done as a once-and-for-all off-line precomputation, or if $R$ is part of the input, this can be done in $O(|R|)$ steps (even when given generators and relations).

So depending on your assumptions, the preceding step is either hard or easy. But let's suppose it's done. Now we'll use two viewpoints on the elements of $R$ to reduce to linear algebra over abelian groups.

Viewpoint 1: We may consider elements of $R$ as "vectors" with $\ell$ integer coordinates, where we consider the $i$-th coordinate modulo $p_i^{k_i}$.

Viewpoint 2: This requires a little setup. Let $Hom(\mathbb{Z}_{p_j^{k_j}}, \mathbb{Z}_{p_i^{k_i}})$ denote the set of ring homomorphisms between these two rings. In particular, when $p_i \neq p_j$, this is zero; when $p_i = p_j$ if $k_i < k_j$ then this involves taking element of $\mathbb{Z}_{p_j^{k_j}}$ modulo $p_i^{k_i}$, and possibly multiplying it by an element of $\mathbb{Z}_{p_i^{k_i}}$ (which we may represent by an integer, treated modulo $p_i^{k_i}$); if $k_i > k_j$ it involves possibly multiplying by an element of $\mathbb{Z}_{p_j^{k_j}}$ (represented by an integer), and then applying the unique embedding of $\mathbb{Z}_{p_j^{k_j}}$ into $\mathbb{Z}_{p_i^{k_i}}$ (as the multiples of $p_i^{k_i-k_j}$, modulo $p_i^{k_i}$)

Now, consider the left multiplicative action of any $r \in R$ on $R$. Then we may associate to $r$ an $\ell \times \ell$ matrix, where the $(i,j)$ entry is an element of $Hom(\mathbb{Z}_{p_j^{k_j}}, \mathbb{Z}_{p_i^{k_i}})$, which can be represented by an integer, following the conventions above.

Now, replace each entry of $A$ by the associated $\ell \times \ell$ matrix as in viewpoint 2, replace each entry of $b$ by the associated vector as in viewpoint $1$, and replace each entry of $x$ with a vector of length $\ell$ (as in viewpoint 1).

Now the original problem has been reduced to linear algebra over abelian groups, which can be solved in polynomial time (see, e.g., Mikael Goldmann and Alexander Russell. The complexity of solving equations over finite groups. Inf. Comput., 178(1):253–262, 2002).

$\endgroup$
1
  • 1
    $\begingroup$ Beautiful. This shows that the problem is at most as hard as factoring. Can we prove it is at least as hard as factoring? Can we find a reduction from factoring, i.e., given $n$ can we find an explicit example of a problem instance where the solution to that problem instance reveals the factorization of $n$? $\endgroup$
    – D.W.
    Sep 2, 2016 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.