$\newcommand{\OR}{{\sf OR}} \newcommand{\MOD}{{\sf MOD}} $In the paper Representing Boolean functions as polynomials modulo composite numbers, Barrington, Beigel and Rudich showed that $\delta_m(\OR_n) = O(n^{1/r})$ with a symmetric witness, where $r$ is the number of distinct prime divisors of moduli $m$. Recently I am reading this paper, and I have some problems understanding the proof in the case that $m$ is composite but not square-free.
Their proof idea is to compute $\OR_n$ by choosing proper $m' > n$ and computing $\MOD_{m'}$ as $\OR_n$. Here the $m'$ is chosen to have the same set of prime factors as $m$, say $m' = p_1^{d_1} \ldots p_r^{d_r}$, $m = p_1^{e_1} \ldots p_r^{e_r}$. Then by Chinese Remainder Theorem we have $\delta_m(\MOD_{m'}) = \max_i \delta_{p_i^{e_i}}(\MOD_{p_i^{d_i}})$. They first proved the bound on square-free $m$, then extended it to general case:
For square-free $m = p_1 p_2 \ldots p_r$, each prime factor $p_i$ of $m$ requires degree at most $p_i^{d_i}$ to compute $\MOD_{p_i^{d_i}}$, since $\binom{x}{0}, \binom{x}{1}, \ldots, \binom{x}{p_i^{d_i} - 1}$ form a basis of the vector space of symmetric functions with period $p_i^{d_i}$. Thus $\delta_m(\MOD_{m'}) \leq \max_i p_i^{d_i} = O(n^{1/r})$, where the last step is by carefully choosing $m'$ for sufficiently large $n$.
For general composite $m$, their original proof is shown below, where $s_i(\vec{x})$ is defined to be the sum of all monomials of degree $i$ over all input variables, and $s_i(j)$ is the value of $s_i(\vec{x})$ where $j$ variables in $\vec{x}$ are on (i.e., $\binom{j}{i}$):
Here my problem is: to apply the Chinese Remainder Theorem, all subcomponents should have the same number of input variables. (In the notation of $\MOD_p$, we don't have the number of inputs $n$ explicitly, which is often treated as an input variable to the degree function. This leads to some subtlety. To make it explicit, I will use the notation $\MOD_{p, n}$ to describe the polynomial computing $\MOD_p$ over $n$ input variables.)
In the square-free case, all subcomponents $\MOD_{p_i^{d_i}, n}$ are over prime moduli $p_i$, where we can use the basis $\binom{x}{0}, \binom{x}{1}, \ldots, \binom{x}{p_i^{d_i}-1}$ to compute $\MOD_{p_i^{d_i}, n}$ for all $n \in \mathbb{N}$. Here the proof strategy goes smoothly.
But in the general case, the proof strategy seems to fail on the subgoal of computing $\MOD_{p_i^{d_i}, n}$: the given function $g$ has the property $g(0) = 0, g(i) = 1$ for $1 \leq i < p^z$, so it can compute $\OR_{p^z-1}$ (more precisely, $\OR_k$ for $k < p^z$), which is equivalent to $\MOD_{p^z, k}$ for $k < p^z$; But it is not under control when the input is in $[p^z, p^{e+z-1})$. (specifically, $g(p^z) \not\equiv 0 \pmod{p^e}$ in several cases, e.g. $p=2, e=3, z=2$: $g(2^2) = \binom{4}{1} - \binom{4}{2} + \binom{4}{3} \equiv 2 \pmod{2^3}$.) That is to say, $g$ cannot compute $\MOD_{p^z, k}$ for $k \geq p^z$. Thus to reach our goal $\MOD_{p_i^{d_i}, n}$, we must have $p_i^{d_i} > n$, which implies $\delta(g) = p_i^{d_i} - 1 = \Omega(n)$. In this case, every subgoal has $\Omega(n)$ degree, and the combination result is also of degree $\Omega(n)$ by CRT.
The most important difference of the strategy's behavior is, we can choose $p_i^{d_i}$ freely in the square-free case, but in the general case it is lower-bounded by $n$ to behave as we desired.
What's wrong with my understanding?
