<p>What is known about the separation of minimal degrees of polynomials and that of rational functions that represent boolean functions? What is a good reference for the topic?</p>

CC BY-SA 3.0
2014-10-14T01:48:05.867Z
Can you give an example of a rational function representing a Boolean function?
Yuval Filmus
CC BY-SA 3.0
2014-10-14T04:23:58.447Z
@YuvalFilmus I am thinking along the same lines as representation in this question http://cstheory.stackexchange.com/questions/27042/representing-boolean-function-by-a-polynomial where $p(x)$ is replaced by $p(x)/q(x)$.
Turbo
CC BY-SA 3.0
2014-10-14T13:23:17.443Z
I'm not sure there are any non-trivial examples, but before thinking about it, I was interested whether you knew about any.
Yuval Filmus
CC BY-SA 3.0
2014-10-14T16:09:23.683Z
Exactly how is the representation defined? Specifically, do you demand that $q(x)\ne0$ for all $x\in\{0,1\}^n$, or is it sufficient if the rational function has an appropriate limit at these points?
Emil Jeřábek
CC BY-SA 3.0
2014-10-14T18:00:15.473Z
(A case in point: $(x^3+y^3)/(x^2+y^2)$ uniquely extends to a total real-analytic function that defines $x\lor y$ on $\{0,1\}^2$, and the two polynomials have no common divisor, nevertheless they both vanish at $(0,0)$.)
Emil Jeřábek
CC BY-SA 3.0
2014-10-14T18:40:04.730Z
Actually, if this *is* allowed, it gives a nontrivial example for the question: the function $x_1\lor\dots\lor x_n$ requires polynomials of degree $n$, but can be expressed by the degree 3 rational function $(x_1^3+\dots+x_n^3)/(x_1^2+\dots+x_n^2)$.
Emil Jeřábek
CC BY-SA 3.0
2014-10-15T00:10:41.930Z
What is the polynomial for the OR function? (I guess you can recursively use the polynomial for $x_1 \vee x_2$)
Turbo
CC BY-SA 3.0
2014-10-15T09:23:27.850Z
$1-(1-x_1)\cdots(1-x_n)$.
Emil Jeřábek
CC BY-SA 3.0
2014-10-17T16:40:20.663Z
@EmilJeřábek missed the question. the rational function needs to have exact valuation at given points (should not be a limit).
Turbo
<boolean-functions>
Representing boolean function by a rational function
Turbo
# Representing boolean function by a rational function

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

What is known about the separation of minimal degrees of polynomials and that of rational functions that represent boolean functions? What is a good reference for the topic?

**Tags:** boolean-functions
> **Comments:**
> **username_1**: Can you give an example of a rational function representing a Boolean function?  
> **username_0**: @YuvalFilmus I am thinking along the same lines as representation in this question http://cstheory.stackexchange.com/questions/27042/representing-boolean-function-by-a-polynomial where $p(x)$ is replaced by $p(x)/q(x)$.  
> **username_1**: I'm not sure there are any non-trivial examples, but before thinking about it, I was interested whether you knew about any.  
> **username_2**: Exactly how is the representation defined? Specifically, do you demand that $q(x)\ne0$ for all $x\in\{0,1\}^n$, or is it sufficient if the rational function has an appropriate limit at these points?  
> **username_2**: (A case in point: $(x^3+y^3)/(x^2+y^2)$ uniquely extends to a total real-analytic function that defines $x\lor y$ on $\{0,1\}^2$, and the two polynomials have no common divisor, nevertheless they both vanish at $(0,0)$.)  
> **username_2**: Actually, if this *is* allowed, it gives a nontrivial example for the question: the function $x_1\lor\dots\lor x_n$ requires polynomials of degree $n$, but can be expressed by the degree 3 rational function $(x_1^3+\dots+x_n^3)/(x_1^2+\dots+x_n^2)$.  
> **username_0**: What is the polynomial for the OR function? (I guess you can recursively use the polynomial for $x_1 \vee x_2$)  
> **username_2**: $1-(1-x_1)\cdots(1-x_n)$.  
> **username_0**: @EmilJeřábek missed the question. the rational function needs to have exact valuation at given points (should not be a limit).  

---

## 0 answers

