$\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}$): The proof from BBR94

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?

  • $\begingroup$ Just to make sure I understand: is your issue with the square-free case? Or the generalization to all $m$, not necessarily square-free? $\endgroup$
    – Jake
    Jun 15, 2023 at 12:41
  • $\begingroup$ 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. $\endgroup$
    – Heda Chen
    Jun 15, 2023 at 23:19
  • 2
    $\begingroup$ 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? $\endgroup$
    – Jake
    Jun 16, 2023 at 1:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – Heda Chen
    Jun 16, 2023 at 7:20


Your Answer

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

Browse other questions tagged or ask your own question.