<p>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.</p>

<p>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))$.</p>

<p>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:</p>

<ul>
<li><p>The polynomial $P(k)$ must be 0 exactly when $f(k)=0$. This means $\mathrm{deg(p)} \geq \#\{k \mid f(k)=0\}$.</p></li>
<li><p>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\}$.</p></li>
</ul>

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

<p>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.</p>

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

CC BY-SA 3.0
2014-10-18T22:38:01.670Z
So it is sufficient to consider univariate forms for minimal degrees of both polynomials and rational functions due to Minsky-Papert?
Turbo
CC BY-SA 3.0
2014-10-18T23:23:29.600Z
Do you know of an example where the factor scales like $n^a$ for $a\in(0,1)$?
Turbo
CC BY-SA 3.0
2014-10-19T00:10:50.693Z
Also could you link the works of von zur Gathen and Roche as well as Cohen and Shpilka?
Turbo
CC BY-SA 3.0
2014-10-19T10:16:55.530Z
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.
Turbo
CC BY-SA 3.0
2014-10-19T13:32:00.120Z
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$.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-10-19T17:45:35.567Z
Thank you for the answers. On Q2 I am looking for any example (even asymmetric ones).
Turbo
CC BY-SA 3.0
2014-10-18T19:43:20.383Z
2014-10-19T13:35:05.353Z
2014-10-19T13:35:05.353Z
Kristoffer Arnsfelt Hansen
<p>Let $x_1,x_2,\dots x_n$ be literals.</p>

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

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

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

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

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

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

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

<p>What is known about the smallest degree of a:</p>

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

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

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

<p>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$.</p>

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

CC BY-SA 3.0
2016-02-02T13:49:45.827Z
I am trying to dig out the definition of the term `"candidate boolean function"`, http://cstheory.stackexchange.com/questions/33706/what-is-candidate-boolean-function, can you help with that?
hhh
<boolean-functions>
Gap in degree of representations of candidate boolean functions
Turbo
# Gap in degree of representations of candidate boolean functions

(Asked by: username_0 on 2014-10-18)

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

**Tags:** boolean-functions

> **Comments:**
> **username_1**: I am trying to dig out the definition of the term `"candidate boolean function"`, http://cstheory.stackexchange.com/questions/33706/what-is-candidate-boolean-function, can you help with that?  

---

## 1 answers

### Answer by username_2 on 2014-10-18. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: So it is sufficient to consider univariate forms for minimal degrees of both polynomials and rational functions due to Minsky-Papert?  
> **username_0**: Do you know of an example where the factor scales like $n^a$ for $a\in(0,1)$?  
> **username_0**: Also could you link the works of von zur Gathen and Roche as well as Cohen and Shpilka?  
> **username_0**: 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.  
> **username_2**: 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$.  
> **username_0**: Thank you for the answers. On Q2 I am looking for any example (even asymmetric ones).  

---

