# The $O(n^{1/r})$ upper bound of polynomial degree of OR over composite moduli

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

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

2. 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?

• Just to make sure I understand: is your issue with the square-free case? Or the generalization to all $m$, not necessarily square-free?
– Jake
Jun 15, 2023 at 12:41
• The square-free case is provably correct, my problem is in the generalization case, since it has a prime-power moduli (rather than prime). I will modify the description to make my problem clear, thanks. Jun 15, 2023 at 23:19
• Couldn't you just ignore the redundant factors by multiplying by a suitable constant? E.g. if you're looking for OR mod 12, couldn't you find OR mod 6 in the square-free case and then multiply the resulting polynomial by 2?
– Jake
Jun 16, 2023 at 1:03
• Your suggestion seems so simple, elegant and straightforward that I spent hours wondering why the authors of the paper didn't choose this method at that time lol... Now I'm still curious about the reason and decide to ask them by e-mail. Jun 16, 2023 at 7:20