Construction of arbitrary functions with exponential-size $MODp \circ MODq$ circuits

Question

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.

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.