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

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.

$$\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.