Rational functions and polynomials evaluated on a set of points

Question

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)

Answer 1

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