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, Comput. Complexity 4, No. 4, 383-388 (1994). ZBL0829.68048.

[2] Hansen, Kristoffer Arnsfelt; Koucký, Michal, A new characterization of (\text{ACC}^{0}) and probabilistic (\text{CC}^{0}), Comput. Complexity 19, No. 2, 211-234 (2010). ZBL1213.68262.

[3] Barrington, David A. Mix; Straubing, Howard; Thérien, Denis, Non-uniform automata over groups, Inf. Comput. 89, No. 2, 109-132 (1990). ZBL0727.68070.


1 Answer 1


$\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<q$. 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\}$, $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<d}\xi^i\sum_{j<m}a_{i,j}g_j(\vec x),$$

    where $d=[F:\F p]<q$ 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<m}a_{0,j}g_j(\vec x).$$

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


Your Answer

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

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