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)

  • 1
    $\begingroup$ 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? $\endgroup$ – Pietro Majer Oct 16 '14 at 7:48
  • $\begingroup$ corrected $p(x)$ to $p(x_1,x_2,\dots,x_n)$. $\endgroup$ – 1.. Oct 16 '14 at 11:57
  • $\begingroup$ 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$. $\endgroup$ – Felipe Voloch Oct 17 '14 at 10:49
  • $\begingroup$ @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$. $\endgroup$ – 1.. Oct 17 '14 at 16:45
  • $\begingroup$ The problem I am most interested is $S=\{0,1\}$ since that is the simplest case, we can take the polynomials to be multilinear. $\endgroup$ – 1.. 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$.

| cite | improve this answer | |
  • $\begingroup$ Thank you for the answer. I think I understand the mistake in framing my question. Let me post my thoughts as a different question. I will link it here. $\endgroup$ – 1.. Oct 18 '14 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.