19
$\begingroup$

I'm interested in the complexity of solving linear equations modulo k, for arbitrary k (and with a special interest in prime powers), specifically:

Problem. For a given system of $m$ linear equations in $n$ unknowns modulo $k$, do there exist any solutions?

In the abstract to their paper Structure and importance of logspace-MOD classes on the classes ModkL, Buntrock, Damm, Hertrampf, and Meinel claim that they "demonstrate their significance by proving that all standard problems of linear algebra over the finite rings $\mathbb Z/k\mathbb Z$ are complete for these classes". On closer inspection, the story is more complicated. For instance, Buntrock et al. show (by a proof-sketch in an earlier and freely accessible draft found by Kaveh, thanks!) that solving systems of linear equations is instead in the complementary class coModkL, for k prime. This class is not known to be equal to ModkL for k composite, but never mind that — what I'm concerned about is the fact that they don't make any remarks about whether solving systems of linear equations mod k is even contained in coModkL for k composite!

Question: Is solving systems of linear equations modulo k contained in coModkL for all positive k?

If you can solve systems of equations modulo a higher power q of a prime p, you can solve them modulo p as well; so solving systems of equations modulo q is coModpL-hard. If you could show that this problem is in ModqL, you would end up showing ModkL = coModkL for all k. That's likely to be difficult to prove. But is it in coModkL?

$\endgroup$
  • $\begingroup$ citeseerx link for the draft of the paper. ps: a more robust way of dealing with $\mod_k$ is using $\mod_k^A$ where $A \subseteq [k-1]$ is the set of accepted reminders $\mod k$. There is also a related question in proof complexity, cf. "The Proof Complexity of Linear Algebra" by Soltys and Cook, APAL 2004. $\endgroup$ – Kaveh Nov 11 '11 at 17:32
  • 2
    $\begingroup$ what about just k=4 and parity-L? $\endgroup$ – domotorp Nov 18 '11 at 20:48
9
$\begingroup$

I'm happy to say that I think we can answer this question in the affirmative: that is, deciding whether a linear congruence is feasible modulo k is coModkL-complete.

We can actually reduce this problem to the special case of prime powers. One may show that:

Normal Form. The class coModkL consists of langauges L of the form L = Lp1 ∩ Lp2 ∩ ... ∩ Lpr , where Lpj ∈ coModpL and where pj ranges over the prime factors of k.

By the Remainder Theorem, any solution to a system of equations modulo each of the prime powers $p_{\!j}^{e_j}$ dividing k gives rise to a solution to the same system, mod k. So if solving systems of linear equations over $p_{\!j}^{t_j}$ is contained in coModpL, it follows that solving systems of equations mod k is contained in coModkL.

There's a standard algorithm, described by McKenzie and Cook for reducing linear congruences modulo a prime power to constructing a spanning set for its nullspace (namely, for Ax = y over a given ring, construct a basis for the nullspace of [ A | y ] and see if any solutions exist with a final coefficient of −1); and subsequently for reducing the construction of nullspaces modulo prime powers to constructing nullspaces modulo primes, and matrix multiplication modulo prime powers. Both of the latter tasks are problems which are feasible for coModkL, provided that you can construct the matrices involved.

It turns out that the matrices involved in the reduction of McKenzie and Cook can themselves be computed by matrix multiplication, and (crucially) division by a constant factor. Fortunately, for prime powers, the coefficients of the matrices involved can be computed on the work-tape using an oracle for coModpL-machines; and the division by a constant can be performed in NC1, which is again feasible in coModpL. So it turns out that the whole problem is ultimately doable in coModkL.

For complete details, see [arxiv:1202.3949].

$\endgroup$
  • $\begingroup$ I would like to know, is it $k$ constant in your question/answer? I am interested in the case where the size of $k$ is not unbounded. $\endgroup$ – Juan Bermejo Vega Jul 26 '14 at 15:17
  • 1
    $\begingroup$ @Juan: Yes, $k$ is a constant, albeit any constant. $\endgroup$ – Niel de Beaudrap Jul 26 '14 at 22:20

Your Answer

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

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