Let $S$ be a collection of points on the real line.


Let $\{x\_i\}\_{i=1}^n$ take values in $S$. 


Consider a polynomial $p(x\_1,x\_2,\dots,x\_n)$ over $\mathbb R[x\_1,x\_2,\dots,x\_n]$ of degree $d$ which when evaluated on $S$ takes values in $S$.


Can one say anything about the degree of smallest rational function (sum of degrees of numerator and denominator) over $\mathbb R(x\_1,x\_2,\dots,x\_n)$ which when evaluated on $S$ takes identical values as that of $p(x\_1,x\_2,\dots,x\_n)$ at least for special subsets of $S$ such as:


$1)$ $\{0,1\}$? 


Note here $p$ and numerator and denominator of the rational function can be multiaffine.


What tools could be useful to study problems in case $1)$?


(Can the degree be $m^2$ for $p$ and $m$ for $f$? One possible candidate is here <https://mathoverflow.net/questions/184635/composition-of-multilinear-forms-on-a-set-of-points>)



Rational functions and polynomials evaluated on a set of points
The set $\{0,1\}^n$ has $m=2^n$ elements, let's order them $P\_1,\ldots,P\_m$. The space $V$ of polynomials in variables of degree at most one each variable (multilinear or multiaffine if you like) has dimension $m$ and for any choice of values $y\_1,\ldots,y\_m$, there is a unique $p \in V, p(P\_j)=y\_j,j=1,\ldots,m$. This $p$ has degree $n$ potentially, as it may include the term $x\_1\cdots x\_n$. Let's assume $n$ odd. A dimension count shows that for any choice of $y\_1,\ldots,y\_m$, there exists a quotient 
$$h= f/g, f,g \in V, \deg f, \deg g \le (n+1)/2, h(P\_j)=y\_j, j=1,\ldots,m$$
but if you put the more stringent condition that $\deg f, \deg g \le (n-1)/2$, then there will be choices of the $y\_j$ (even if restricted to be in $\{0,1\}$) for which you cannot find $h$, i.e., the degree $(n+1)/2$ is optimal. 


Edit: It's even worse, the existence part only guarantees $f,g$ with $f(P\_j)=y\_jg(P\_j)$ but we could still have $g(P\_j)=0$. I think for $p=x\_1\cdots x\_n$ we cannot find $h=f/g$ as above with $f,g \in V, \deg f, \deg g < n$. 


