Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?

Question

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 Mod_kL, 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 coMod_kL, for k prime. This class is not known to be equal to Mod_kL 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 coMod_kL for k composite!

Question: Is solving systems of linear equations modulo k contained in coMod_kL 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 coMod_pL-hard. If you could show that this problem is in Mod_qL, you would end up showing Mod_kL = coMod_kL for all k. That's likely to be difficult to prove. But is it in coMod_kL?

Answer 1

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 coMod_kL-complete.

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

Normal Form. The class coMod_kL consists of langauges L of the form L = L_p1 ∩ L_p2 ∩ ... ∩ L_pr , where L_pj ∈ coMod_pj L and where p_j 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 coMod_pj L, it follows that solving systems of equations mod k is contained in coMod_kL.

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 coMod_kL, 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 coMod_pL-machines; and the division by a constant can be performed in NC¹, which is again feasible in coMod_pL. So it turns out that the whole problem is ultimately doable in coMod_kL.

For complete details, see [arxiv:1202.3949].