Gap in degree of representations of candidate boolean functions

Question

Let $x_1,x_2,\dots x_n$ be literals.

Let $P(x_1,x_2,\dots,x_n)$ be one of the following Boolean function:

$0)$ Equality function - $Eq_k^n(x)=1\iff x_1+\dots+x_n= k$

$1)$ Threshold function - $Th_k^n(x)=1\iff x_1+\dots+x_n\ge k$

$2)$ Majority function - $Maj_n(x)=1\iff x_1+\dots+x_n\ge \lceil\frac{n}{2}\rceil$

$3)$ Modular-$s$ function - $MOD_k(s)=s\iff x_1+\dots+x_n\equiv 0\mod k$

If a function 'represents' $P(x_1,x_2,\dots,x_n)$, that means the function and $P(x_1,x_2,\dots,x_n)$ agree on $x_i\in\{0,1\}$.

If a function is rational then its degree is the sum of degrees of numerator and denominator.

What is known about the smallest degree of a:

$A)$ polynomial $p(x_1,x_2,\dots,x_n)\in\mathbb R[x_1,x_2,\dots,x_n]$

$B)$ rational function $r(x_1,x_2,\dots,x_n)\in\mathbb R(x_1,x_2,\dots,x_n)$

that represents $P(x_1,x_2,\dots,x_n)$ in each case of $0,1,2$ and $3$?

In which case the gap is the largest? It seems intuitively that $2,3$ should be the most complex with possibly the largest gap for $3$.

Note that both the polynomial and the numerator and denominator of the rational function can be multilinear since $x_i^t=x_i$ on $\{0,1\}$.

Answer 1

For symmetric functions (as those you suggest), one may make use of the Minsky-Papert symmetrization technique to get an easy $(n+1)/2$ lower bound for all nonconstant functions.

The idea behind the symmetrization technique is to replace a polynomial $p(x)$ of degree at most $d$ by the symmetric polynomial $\sum_{\sigma \in S_n} p(\sigma(x))$. Then we may find a univariate polynomial $P$ also of degree at most $d$ such that $P(\sum_i x_i) = \sum_{\sigma \in S_n} p(\sigma(x))$.

Suppose that $f$ is a symmetric non-constant Boolean function. With abuse of notation, write also $f(k) = f(x)$, where $k = \sum_i x_i$. Let $p$ and $q$ be polynomials such that $p(x)/q(x) = f(x)$ for all $x$ (in particular $q(x)\neq 0$ for all $x$). Then $p(x)=f(x)q(x)$, and hence $\sum_{\sigma \in S_n} p(\sigma(x)) = \sum_{\sigma \in S_n} f(\sigma(x)) q(\sigma(x)) = f(x) \sum_{\sigma \in S_n} q(\sigma(x))$ for all $x$. We may thus find univariate polynomials $P$ and $Q$ such that $P(k) = f(k) Q(k)$ for all $k$. Thus $P(k)/Q(k)=f(k)$. Now we can observe:

• The polynomial $P(k)$ must be 0 exactly when $f(k)=0$. This means $\mathrm{deg(p)} \geq \#\{k \mid f(k)=0\}$.

• The polynomial $P(k)-Q(k)$ must be 0 exactly when $f(k)=1$ (since q is by assumption never 0). This means $\max(\mathrm{deg}(p),\mathrm{deg(q)}) \geq \#\{k \mid f(k)=1\}$.

It follows that the degree of $p(x)/q(x)$ must always be at least $(n+1)/2$.

For representation by polynomials even better bounds have been proved by von zur Gathen and Roche as well as Cohen and Shpilka. Namely any nonconstant symmetric function must have degree $n$ minus lower order terms.

In any case, the conclusion is, that for symmetric Boolean functions, the largest separation you may hope for is a factor 2.