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

Question

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.

Answer 1

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

Answer 2

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