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\}$.


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.

  • $\begingroup$ So it is sufficient to consider univariate forms for minimal degrees of both polynomials and rational functions due to Minsky-Papert? $\endgroup$
    – Turbo
    Commented Oct 18, 2014 at 22:38
  • $\begingroup$ Do you know of an example where the factor scales like $n^a$ for $a\in(0,1)$? $\endgroup$
    – Turbo
    Commented Oct 18, 2014 at 23:23
  • $\begingroup$ Also could you link the works of von zur Gathen and Roche as well as Cohen and Shpilka? $\endgroup$
    – Turbo
    Commented Oct 19, 2014 at 0:10
  • $\begingroup$ I think $\sum_{\sigma \in S_n} p(\sigma(x)) = f(x)\sum_{\sigma \in S_n} q(\sigma(x))$ should be $\sum_{\sigma \in S_n} p(\sigma(x)) = [\sum_{\sigma \in S_n}f(\sigma(x))][\sum_{\sigma \in S_n} q(\sigma(x))]$ since both LHS and RHS should be univariate. $\endgroup$
    – Turbo
    Commented Oct 19, 2014 at 10:16
  • $\begingroup$ Answers: Q1 - Unless I already answered this, I don't know what you are asking. Q2 - This answer is only for symmetric Boolean functions, and as noted the separation factor is at most 2. Q3 - I think you can just search for their names together with "symmetric". Q4 - No, $\sigma(x)$ is still $n$ variables, just permuted according to $\sigma$. $\endgroup$ Commented Oct 19, 2014 at 13:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.