<p>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 <em>k</em> is <strong>coMod</strong><sub><em>k</em></sub><strong>L</strong>-complete.</p>

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

<blockquote>
  <p><strong>Normal Form.</strong> The class <strong>coMod</strong><sub><em>k</em></sub><strong>L</strong> consists of langauges <em>L</em> of the form <em>L</em>&nbsp;=&nbsp;<em>L</em><sub><em>p</em><sub>1</sub></sub>&nbsp;&cap;&nbsp;<em>L</em><sub><em>p</em><sub>2</sub></sub>&nbsp;&cap;&nbsp;...&nbsp;&cap;&nbsp;<em>L<sub>p<sub>r</sub></sub></em>&nbsp;, where <em>L<sub>p<sub>j</sub></sub></em>&nbsp;&isin;&nbsp;<strong>coMod</strong><sub><em>p<sub>j&nbsp;</sub></em></sub><strong>L</strong> and where <em>p<sub>j</sub></em> ranges over the prime factors of <em>k</em>.</p>
</blockquote>

<p>By the Remainder Theorem, any solution to a system of equations modulo each of the prime powers $p_{\!j}^{e_j}$ dividing <em>k</em> gives rise to a solution to the same system, mod <em>k</em>.
So if solving systems of linear equations <em>over $p_{\!j}^{t_j}$</em> is contained in <strong>coMod</strong><sub><em>p<sub>j&nbsp;</sub></em></sub><strong>L</strong>, it follows that solving systems of equations mod <em>k</em> is contained in <strong>coMod</strong><sub>k</sub><strong>L</strong>.</p>

<p>There's a standard algorithm, described by <a href="http://dl.acm.org/citation.cfm?id=33386">McKenzie and Cook</a> for reducing linear congruences modulo a prime power to constructing a spanning set for its nullspace (namely, for <em>A</em><strong>x</strong>&nbsp;=&nbsp;<strong>y</strong> over a given ring, construct a basis for the nullspace of [&nbsp;<em>A</em>&nbsp;|&nbsp;<strong>y</strong>&nbsp;] and see if any solutions exist with a final coefficient of &minus;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 <strong>coMod</strong><sub><em>k</em></sub><strong>L</strong>, provided that you can construct the matrices involved.</p>

<p>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 <strong>coMod</strong><sub><em>p</em></sub><strong>L</strong>-machines; and the division by a constant can be performed in <strong>NC</strong><sup>1</sup>, which is again feasible in <strong>coMod</strong><sub><em>p</em></sub><strong>L</strong>. So it turns out that the whole problem is ultimately doable in <strong>coMod</strong><sub><em>k</em></sub><strong>L</strong>.</p>

<p>For complete details, see [<a href="http://arxiv.org/abs/1202.3949">arxiv:1202.3949</a>].</p>

CC BY-SA 3.0
2014-07-26T15:17:31.820Z
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.
Juan Bermejo Vega
CC BY-SA 3.0
2014-07-26T22:20:07.837Z
@Juan: Yes, $k$ is a constant, albeit any constant.
Niel de Beaudrap
CC BY-SA 3.0
2012-02-20T02:37:35.017Z
2012-02-20T02:37:35.017Z
Niel de Beaudrap
<p>I'm interested in the complexity of solving linear equations modulo <em>k</em>, for arbitrary <em>k</em> (and with a special interest in prime powers), specifically:</p>
<blockquote>
<p><strong>Problem.</strong> <em>For a given system of <span class="math-container">$m$</span> linear equations in <span class="math-container">$n$</span> unknowns modulo <span class="math-container">$k$</span>, do there exist any solutions?</em></p>
</blockquote>
<p>In the abstract to their paper <a href="https://doi.org/10.1007/BF01374526" rel="nofollow noreferrer">Structure and importance of logspace-MOD classes</a> on the classes <a href="https://web.archive.org/web/20120307125303/http://qwiki.stanford.edu/index.php/Complexity_Zoo:M#modkl" rel="nofollow noreferrer"><strong>Mod</strong><sub><em>k</em></sub><strong>L</strong></a>,  Buntrock, Damm, Hertrampf, and Meinel claim that they  &quot;<em>demonstrate their significance by proving that all standard problems of linear algebra over the finite rings <span class="math-container">$\mathbb Z/k\mathbb Z$</span> are complete for these classes</em>&quot;. On closer inspection, the story is more complicated. For instance, Buntrock <em>et al.</em> show (by a proof-sketch in an <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.5193" rel="nofollow noreferrer">earlier and freely accessible draft</a> found by Kaveh, thanks!) that solving systems of linear equations is instead in the complementary class <strong>coMod</strong><sub>k</sub><strong>L</strong>, for <em>k</em> prime. This class is not known to be equal to <strong>Mod</strong><sub>k</sub><strong>L</strong> for <em>k</em> 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 <em>k</em> is even <em>contained</em> in <strong>coMod</strong><sub>k</sub><strong>L</strong> for <em>k</em> composite!</p>
<blockquote>
<p><em><strong>Question:</strong> Is solving systems of linear equations modulo k contained in</em> <strong>coMod</strong><sub><em>k</em></sub><strong>L</strong> <em>for all positive k?</em></p>
</blockquote>
<p>If you can solve systems of equations modulo a higher power <em>q</em> of a prime <em>p</em>, you can solve them modulo <em>p</em> as well; so solving systems of equations modulo <em>q</em> is <strong>coMod</strong><sub><em>p</em></sub><strong>L</strong>-hard. If you could show that this problem is in <strong>Mod</strong><sub><em>q</em></sub><strong>L</strong>, you would end up showing <strong>Mod</strong><sub><em>k</em></sub><strong>L</strong> = <strong>coMod</strong><sub><em>k</em></sub><strong>L</strong> for all <em>k</em>. That's likely to be difficult to prove. But is it in  <strong>coMod</strong><sub><em>k</em></sub><strong>L</strong>?</p>

CC BY-SA 3.0
2011-11-11T17:32:04.773Z
[citeseerx link for the draft of the paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.5193&rep=rep1&type=pdf). 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](http://www.cas.mcmaster.ca/~soltys/papers/soltys_cook_apal.pdf)" by Soltys and Cook, APAL 2004.
Kaveh
CC BY-SA 3.0
2011-11-18T20:48:05.420Z
what about just k=4 and parity-L?
domotorp
<cc.complexity-theory><dc.parallel-comp><linear-algebra><nt.number-theory>
Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?
Niel de Beaudrap
# Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?

(Asked by: username_0 on 2011-11-11)

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](https://doi.org/10.1007/BF01374526) on the classes [**Mod***k***L**](https://web.archive.org/web/20120307125303/http://qwiki.stanford.edu/index.php/Complexity_Zoo:M#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](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.5193) found by username_1, thanks!) that solving systems of linear equations is instead in the complementary class **coMod**k**L**, for *k* prime. This class is not known to be equal to **Mod**k**L** 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**k**L** for *k* composite!

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

**Tags:** cc.complexity-theory, dc.parallel-comp, linear-algebra, nt.number-theory

> **Comments:**
> **username_1**: [citeseerx link for the draft of the paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.5193&rep=rep1&type=pdf). 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](http://www.cas.mcmaster.ca/~soltys/papers/soltys_cook_apal.pdf)" by Soltys and Cook, APAL 2004.  
> **username_2**: what about just k=4 and parity-L?  

---

## 1 answers

### Answer by username_0 on 2012-02-20. Score: 9 | Accepted answer

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***k***L**-complete.

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

> **Normal Form.** The class **coMod***k***L** consists of langauges *L* of the form *L* = *L**p*1 ∩ *L**p*2 ∩ ... ∩ *Lpr* , where *Lpj* ∈ **coMod***pj***L** 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 **coMod***pj***L**, it follows that solving systems of equations mod *k* is contained in **coMod**k**L**.

There's a standard algorithm, described by [McKenzie and Cook](http://dl.acm.org/citation.cfm?id=33386) for reducing linear congruences modulo a prime power to constructing a spanning set for its nullspace (namely, for *A***x** = **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***k***L**, 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***p***L**-machines; and the division by a constant can be performed in **NC**1, which is again feasible in **coMod***p***L**. So it turns out that the whole problem is ultimately doable in **coMod***k***L**.

For complete details, see [[arxiv:1202.3949](http://arxiv.org/abs/1202.3949)].

> **Comments:**
> **username_3**: 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.  
> **username_0**: @Juan: Yes, $k$ is a constant, albeit any constant.  

---

