2
$\begingroup$

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)

$\endgroup$
7
  • 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$ Oct 16, 2014 at 7:48
  • $\begingroup$ corrected $p(x)$ to $p(x_1,x_2,\dots,x_n)$. $\endgroup$
    – Turbo
    Oct 16, 2014 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$ Oct 17, 2014 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$
    – Turbo
    Oct 17, 2014 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$
    – Turbo
    Oct 17, 2014 at 16:49

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\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$
    – Turbo
    Oct 18, 2014 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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