# Rational functions and polynomials evaluated on a set of points

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)

• Something is unclear to me: you are talking of evaluating a rational functions of $n$ variables $f(x_1,\dots,x_n)$ on points $x\in S$, a subset of the real line. What's $f(x)$ then? – Pietro Majer Oct 16 '14 at 7:48
• corrected $p(x)$ to $p(x_1,x_2,\dots,x_n)$. – T.... Oct 16 '14 at 11:57
• I don't understand the role of $p$ or $S$ and particularly the restrictions on $S$. If you are given $P_1,\ldots,P_m \in \mathbb{R}^n, y_1,\ldots,y_m \in \mathbb{R}$ and you seek a rational function $f$ with $f(P_i)=y_i$, this is a system of $m$ linear equations in the coefficients of the numerator and denominator of $f$ and you need more than $m$ variables to have a non-trivial solution. If $d$ is the degree of $f$, you need $2{\binom {n+d} {n}} > m$. – Felipe Voloch Oct 17 '14 at 10:49
• @FelipeVoloch for $S=\{0,\1\}$, the polynomials could be multilinear forms(linear in each variable). The number of variables is fixed to be $m=n$. – T.... Oct 17 '14 at 16:45
• The problem I am most interested is $S=\{0,1\}$ since that is the simplest case, we can take the polynomials to be multilinear. – T.... Oct 17 '14 at 16:49

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