<p><span class="math-container">$\def\M#1{\mathrm{MOD}_{#1}}\def\F#1{\mathbb F_{#1}}$</span>I don’t know of a reference, but here is one way how to prove the result. I’ll do it in three stages, each using one new idea: (1) multilinear expansion, (2) <span class="math-container">$q$</span>th root of unity, (3) extension field and Galois invariance:</p>
<ol>
<li><p>For <span class="math-container">$q=2$</span>, the following construction works. Let <span class="math-container">$f$</span> be any Boolean function. Considered as a function <span class="math-container">$\{1,-1\}^n\to\{0,1\}$</span>, <span class="math-container">$f$</span> has a multilinear extension <span class="math-container">$\F p^n\to\F p$</span>, which can be written as a sum of <span class="math-container">$\le2^n$</span> monomials. Then, considered as a function <span class="math-container">$\{0,1\}^n\to\{0,1\}$</span>, each monomial is a <span class="math-container">$\M2$</span> gate, and the outer sum is computed by a <span class="math-container">$\M p$</span> gate.</p>
</li>
<li><p>More generally, if <span class="math-container">$p\equiv1\pmod q$</span>, let <span class="math-container">$\xi$</span> be a primitive <span class="math-container">$q$</span>th root of unity in <span class="math-container">$\F p$</span>. Then any Boolean function considered as <span class="math-container">$\{1,\xi\}^n\to\{0,1\}$</span> has a multilinear extension <span class="math-container">$\F p^n\to\F p$</span>. Shifting the domain back to <span class="math-container">$\{0,1\}^n$</span>, each of the <span class="math-container">$\le2^n$</span> monomials computes a function <span class="math-container">$\{0,1\}^n\to\F p$</span> defined by <span class="math-container">$\xi^{\sum_{i\in I}x_i\bmod q}$</span> for some <span class="math-container">$I\subseteq[n]$</span>, which can be written as a sum (in <span class="math-container">$\F p$</span>) of <span class="math-container">$\M q$</span> gates, and again, the outer sum is a <span class="math-container">$\M p$</span> gate.</p>
<p>(I’m allowing here the inputs of the <span class="math-container">$\M q$</span> gates to be both variables and constants; equivalently, I’m using modular gates computing the predicates <span class="math-container">$|\{i\in I:x_i=1\}|\equiv k\pmod q$</span> for any <span class="math-container">$k&lt;q$</span>. I’m not sure whether it’s possible to circumvent this.)</p>
</li>
<li><p>In the general case, let <span class="math-container">$F=\F p(\xi)$</span> be an extension field of <span class="math-container">$\F p$</span> generated by a primitive <span class="math-container">$q$</span>th root of unity. By the same argument as above, any Boolean function <span class="math-container">$f\colon\{0,1\}^n\to\{0,1\}$</span> can be computed by an <span class="math-container">$F$</span>-linear combination of functions <span class="math-container">$\{g_j(\vec x):j&lt;m\}$</span>, <span class="math-container">$m\le q2^n$</span>, where each <span class="math-container">$g_j$</span> is computed by a single <span class="math-container">$\M q$</span> gate. Equivalently, <span class="math-container">$f$</span> is defined by an <span class="math-container">$\F p$</span>-linear combination</p>
<p><span class="math-container">$$f(\vec x)=\sum_{i&lt;d}\xi^i\sum_{j&lt;m}a_{i,j}g_j(\vec x),$$</span></p>
<p>where <span class="math-container">$d=[F:\F p]&lt;q$</span> and <span class="math-container">$a_{i,j}\in\F p$</span>. However, we are only interested in values of this function on <span class="math-container">$\{0,1\}^n$</span>, in which case also <span class="math-container">$g_j(\vec x),f(\vec x)\in\{0,1\}\subseteq\F p$</span>. It follows that for these inputs, the sum of terms involving <span class="math-container">$\xi^i$</span> with <span class="math-container">$i\ne0$</span> must vanish, and we have just</p>
<p><span class="math-container">$$f(\vec x)=\sum_{j&lt;m}a_{0,j}g_j(\vec x).$$</span></p>
<p>This can now be computed by a <span class="math-container">$\M p$</span> gate.</p>
</li>
</ol>

CC BY-SA 4.0
2021-11-26T10:50:42.997Z
2021-11-27T11:48:17.810Z
2021-11-27T11:48:17.810Z
Emil Jeřábek
<p>It is mentioned in multiple papers [1], [2] that <span class="math-container">$MODp \circ MODq$</span> circuits for two distinct primes <span class="math-container">$p, q$</span> can compute arbitrary functions in exponential size. However, [1] provides no citation for this fact, and [2] refers to [3], which, from what I can tell, neither makes this claim nor provides the proof or construction. I do not doubt that it is true; however, does anyone know either the construction itself, or a proper reference to the construction?</p>
<p>[1] <em>Thérien, Denis</em>, <a href="http://dx.doi.org/10.1007/BF01263425" rel="noreferrer"><strong>Circuits constructed with MOD(_ q) gates cannot compute “and” in sublinear size</strong></a>, Comput. Complexity 4, No. 4, 383-388 (1994). <a href="https://zbmath.org/?q=an:0829.68048" rel="noreferrer">ZBL0829.68048</a>.</p>
<p>[2] <em>Hansen, Kristoffer Arnsfelt; Koucký, Michal</em>, <a href="http://dx.doi.org/10.1007/s00037-010-0287-z" rel="noreferrer"><strong>A new characterization of (\text{ACC}^{0}) and probabilistic (\text{CC}^{0})</strong></a>, Comput. Complexity 19, No. 2, 211-234 (2010). <a href="https://zbmath.org/?q=an:1213.68262" rel="noreferrer">ZBL1213.68262</a>.</p>
<p>[3] <em>Barrington, David A. Mix; Straubing, Howard; Thérien, Denis</em>, <a href="http://dx.doi.org/10.1016/0890-5401(90)90007-5" rel="noreferrer"><strong>Non-uniform automata over groups</strong></a>, Inf. Comput. 89, No. 2, 109-132 (1990). <a href="https://zbmath.org/?q=an:0727.68070" rel="noreferrer">ZBL0727.68070</a>.</p>

<reference-request><circuit-complexity><proofs><universal-computation>
Construction of arbitrary functions with exponential-size $MODp \circ MODq$ circuits
Jake
# Construction of arbitrary functions with exponential-size $MODp \circ MODq$ circuits

(Asked by: username_0 on 2021-11-26)

It is mentioned in multiple papers [1], [2] that $MODp \circ MODq$ circuits for two distinct primes $p, q$ can compute arbitrary functions in exponential size. However, [1] provides no citation for this fact, and [2] refers to [3], which, from what I can tell, neither makes this claim nor provides the proof or construction. I do not doubt that it is true; however, does anyone know either the construction itself, or a proper reference to the construction?

[1] *Thérien, Denis*, [**Circuits constructed with MOD(\_ q) gates cannot compute “and” in sublinear size**](http://dx.doi.org/10.1007/BF01263425), Comput. Complexity 4, No. 4, 383-388 (1994). [ZBL0829.68048](https://zbmath.org/?q=an:0829.68048).

[2] *Hansen, Kristoffer Arnsfelt; Koucký, Michal*, [**A new characterization of (\text{ACC}^{0}) and probabilistic (\text{CC}^{0})**](http://dx.doi.org/10.1007/s00037-010-0287-z), Comput. Complexity 19, No. 2, 211-234 (2010). [ZBL1213.68262](https://zbmath.org/?q=an:1213.68262).

[3] *Barrington, David A. Mix; Straubing, Howard; Thérien, Denis*, [**Non-uniform automata over groups**](http://dx.doi.org/10.1016/0890-5401(90)90007-5), Inf. Comput. 89, No. 2, 109-132 (1990). [ZBL0727.68070](https://zbmath.org/?q=an:0727.68070).

**Tags:** reference-request, circuit-complexity, proofs, universal-computation

---

## 1 answers

### Answer by username_1 on 2021-11-26. Score: 9 | Accepted answer

$\def\M#1{\mathrm{MOD}\_{#1}}\def\F#1{\mathbb F\_{#1}}$I don’t know of a reference, but here is one way how to prove the result. I’ll do it in three stages, each using one new idea: (1) multilinear expansion, (2) $q$th root of unity, (3) extension field and Galois invariance:

1. For $q=2$, the following construction works. Let $f$ be any Boolean function. Considered as a function $\{1,-1\}^n\to\{0,1\}$, $f$ has a multilinear extension $\F p^n\to\F p$, which can be written as a sum of $\le2^n$ monomials. Then, considered as a function $\{0,1\}^n\to\{0,1\}$, each monomial is a $\M2$ gate, and the outer sum is computed by a $\M p$ gate.
2. More generally, if $p\equiv1\pmod q$, let $\xi$ be a primitive $q$th root of unity in $\F p$. Then any Boolean function considered as $\{1,\xi\}^n\to\{0,1\}$ has a multilinear extension $\F p^n\to\F p$. Shifting the domain back to $\{0,1\}^n$, each of the $\le2^n$ monomials computes a function $\{0,1\}^n\to\F p$ defined by $\xi^{\sum\_{i\in I}x\_i\bmod q}$ for some $I\subseteq[n]$, which can be written as a sum (in $\F p$) of $\M q$ gates, and again, the outer sum is a $\M p$ gate.

   (I’m allowing here the inputs of the $\M q$ gates to be both variables and constants; equivalently, I’m using modular gates computing the predicates $|\{i\in I:x\_i=1\}|\equiv k\pmod q$ for any $k. I’m not sure whether it’s possible to circumvent this.)
3. In the general case, let $F=\F p(\xi)$ be an extension field of $\F p$ generated by a primitive $q$th root of unity. By the same argument as above, any Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ can be computed by an $F$-linear combination of functions $\{g\_j(\vec x):j, $m\le q2^n$, where each $g\_j$ is computed by a single $\M q$ gate. Equivalently, $f$ is defined by an $\F p$-linear combination

   $$f(\vec x)=\sum\_{i

   where $d=[F:\F p] and $a\_{i,j}\in\F p$. However, we are only interested in values of this function on $\{0,1\}^n$, in which case also $g\_j(\vec x),f(\vec x)\in\{0,1\}\subseteq\F p$. It follows that for these inputs, the sum of terms involving $\xi^i$ with $i\ne0$ must vanish, and we have just

   $$f(\vec x)=\sum\_{j

   This can now be computed by a $\M p$ gate.


---

