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

CC BY-SA 4.0
2023-06-15T12:41:18.043Z
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
CC BY-SA 4.0
2023-06-15T23:19:04.773Z
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.
Heda Chen
CC BY-SA 4.0
2023-06-16T01:03:59.610Z
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
CC BY-SA 4.0
2023-06-16T07:20:04.530Z
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.
Heda Chen
<cc.complexity-theory><polynomials>
The $O(n^{1/r})$ upper bound of polynomial degree of OR over composite moduli
Heda Chen
# The $O(n^{1/r})$ upper bound of polynomial degree of OR over composite moduli

(Asked by: username_0 on 2023-06-13)

$\newcommand{\OR}{{\sf OR}}
\newcommand{\MOD}{{\sf MOD}}
$In the paper [*Representing Boolean functions as polynomials modulo composite numbers*](https://www.researchgate.net/publication/226408651_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](https://i.sstatic.net/319MP.png)](https://i.sstatic.net/319MP.png)

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?

**Tags:** cc.complexity-theory, polynomials
> **Comments:**
> **username_1**: Just to make sure I understand: is your issue with the square-free case? Or the generalization to all $m$, not necessarily square-free?  
> **username_0**: 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.  
> **username_1**: 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?  
> **username_0**: 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.  

---

## 0 answers

