# Finding polynomial $f$ given $\{f(x_i)\}$ for unknown $x_i$

Let $K=\mathbb{Z}$ or $K=\mathbb{Q}$. Let $f \in K[x],\deg(f)>1$ and $x_i,y_i \in K$.

Let $x_i$ be $n$ elements of $K$ randomly chosen, where $n > d = 2 \deg(f)$.

Given $\{a_i=f(x_i)\}$ ($x_i$ are unknown) and $d$, what are the best algorithms to find $f$ or another polynomial $g$, satisfying $a_i=g(y_i)$ for known $y_i$, possibly $x_i=y_i$?

One approach is to treat the coefficients of $f$ and $x_i$ as unknowns and try to find $K$ points on the variety, but this appears hard to me.

If $x_i$ are known, the problem is easy.

• I don't understand. $x_i$ are randomly chosen, but unknown ? -- One possible interpretation of your question is: Given $n$ and $a_i\in K$ for $i\leq n$. Can we find a polynomial $f$ of degree $<n/2$ such that $a$ is in the image of $f$? Is it that? – Chris Wuthrich Oct 11 '16 at 11:12
• @ChrisWuthrich Probably yours is equivalent, but in my case solution exists, while in yours it may not exist. – joro Oct 11 '16 at 11:50
• Wouldn't the polynomial $g(x)=x$ always work? – Jan-Christoph Schlage-Puchta Oct 11 '16 at 12:09
• @Jan-ChristophSchlage-Puchta Thank you, missed this case. Edited with deg(f)>1. – joro Oct 11 '16 at 12:23
• mathoverflow.net/questions/52677/… – Dror Speiser Oct 11 '16 at 13:42

This is half-baked, but note that if $f(x) = \sum_{i=0}^n f_i x^i$ then $$a_j - a_k = \sum_{i=1}^n f_i (x_j^i - x_k^i)$$ is a multiple of $d_{j,k} := (x_j - x_k)$. By factorizing $(a_j-a_k)$ you can get a list of possibilities for $d_{j,k}$, from there you may be able to do some combinatorics to find consistent values for $d_{j,k}$ (i.e. consistent with $d_{j,k} + d_{k,\ell} = d_{j,\ell}$) and from there you pretty much have $x_j$.

• Thanks, interesting. This appears to require factoring oracle, which is not efficient in general, right? – joro Oct 11 '16 at 12:26
• ECM will factor an integer in no time provided the second largest prime factor is not too large, which is true for most integers. I imagine the combinatorial step is the hard bit. – Doris Oct 11 '16 at 12:57
• Do you think this will work over the rationals too? Clearing denominators may help. – joro Oct 12 '16 at 13:39
• @joro Well you can factorize rational numbers into integers too, by factoring both the numerator and the denominator, and my comment that $a_j-a_k$ is a multiple of $d_{j,k}$ still holds, except now it is a rational multiple, which makes things harder, because there may have been cancellation. – Doris Oct 18 '16 at 17:22
• Yes, I meant cancellations, since $\frac12=\frac24$ and in some sense the "factorizations" are different. – joro Oct 18 '16 at 18:05

Here is a silly approach for the case when the degree of $f$ is $2$. (so $d=4$?)

For $f(x)= \alpha (x-\beta)^2 + \gamma$, if $a_1,a_2,a_3,a_4$ all lie inthe image of $f$, then $(a_1-\gamma)(a_2-\gamma)(a_3-\gamma)(a_4-\gamma)$ is a perfect square, so we have a rational point on the elliptic curve $y^2=(a_1-\gamma)(a_2-\gamma)(a_3-\gamma)(a_4-\gamma)$ (which already has two rational points at $\infty$).

Keep trying different 4-tuples until you find an elliptic curve with rank $0$, which should happen with high probability. Then the only rational points are torsion points, which are easy to find. Finally check each rational value of $x$ solving the elliptic equation to see if the ratios $(a_i-\gamma)/(a_j-\gamma)$ are all perfect squares. If they are, choose some $a_i-\gamma$ to be $\alpha$, set $x_i$ to be square roots, and $\beta=0$.