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.

  • 1
    $\begingroup$ 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? $\endgroup$ – Chris Wuthrich Oct 11 '16 at 11:12
  • $\begingroup$ @ChrisWuthrich Probably yours is equivalent, but in my case solution exists, while in yours it may not exist. $\endgroup$ – joro Oct 11 '16 at 11:50
  • 1
    $\begingroup$ Wouldn't the polynomial $g(x)=x$ always work? $\endgroup$ – Jan-Christoph Schlage-Puchta Oct 11 '16 at 12:09
  • $\begingroup$ @Jan-ChristophSchlage-Puchta Thank you, missed this case. Edited with deg(f)>1. $\endgroup$ – joro Oct 11 '16 at 12:23
  • 1
    $\begingroup$ mathoverflow.net/questions/52677/… $\endgroup$ – 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$.

  • $\begingroup$ Thanks, interesting. This appears to require factoring oracle, which is not efficient in general, right? $\endgroup$ – joro Oct 11 '16 at 12:26
  • $\begingroup$ 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. $\endgroup$ – Doris Oct 11 '16 at 12:57
  • $\begingroup$ Do you think this will work over the rationals too? Clearing denominators may help. $\endgroup$ – joro Oct 12 '16 at 13:39
  • $\begingroup$ @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. $\endgroup$ – Doris Oct 18 '16 at 17:22
  • $\begingroup$ Yes, I meant cancellations, since $\frac12=\frac24$ and in some sense the "factorizations" are different. $\endgroup$ – 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$.


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.