Example: How can you guess a polynomial $p$ if you know that $p(2) = 11$? It is simple: just write 11 in binary format: 1011 and it gives the coefficients: $p(x) = x^3+x+1$. Well, of course, this polynomial is not unique, because $2x^k$ and $x^{k+1}$ give the same value at $p=2$, so for example $2x^2+x+1$, $4x+x+1$ also satisfy the condition, but their coefficients have greater absolute values!

Question 1: Assume we want to find $q(x)$ with integer coefficients, given its values at some set of primes $q(p_i)=y_i$ such that $q(x)$ has the least possible coefficients. How should we do it? Any suggestion/algorithm/software are welcome. (Least coefficients means: the least maximum of modulii of coefficients).

Question 2: Can one help to guess the polynomial $p$ such that $p(3) = 221157$, $p(5) = 31511625$ with the smallest possible integer coefficients? (Least maximum of modulii of coefficients). Does it exist?

(The degree of the polynomial seems to be 10 or 11. It seems divisible by $x^3$, and I have run a brute force search bounding absolute values of the coefficients by 3, but no polynomial satisfying these conditions is found, so I will increase the bound on the coefficients and will run this search again, but the execution time grows too quickly as the bound increases and it might be that brute force is not a good choice).

Question 3: Do conditions like $q(p_i)=y_i$ imply some bounds on coefficients? E.g., can we estimate that the coefficients are higher than some bound?

Example: How can you guess a polynomial $p$ if you know that $p(2) = 11$? It is simple: just write 11 in binary format: 1011 and it gives the coefficients: $p(x) = x^3+x+1$. Well, of course, this polynomial is not unique, because $2x^k$ and $x^{k+1}$ give the same value at $p=2$, so for example $2x^2+x+1$, $4x+x+1$ also satisfy the condition, but their coefficients have greater absolute values!

Question 1: Assume we want to find $q(x)$ with integer coefficients, given its values at some set of primes $q(p_i)=y_i$ such that $q(x)$ has the least possible coefficients. How should we do it? Any suggestion/algorithm/software are welcome. (Least coefficients means: the least maximum of modulii of coefficients).

Question 2: Can one help to guess the polynomial $p$ such that $p(3) = 221157$, $p(5) = 31511625$ with the smallest possible integer coefficients? (Least maximum of modulii of coefficients). Does it exist?

(That example comes from the question MO404817 on count of 3x3 anticommuting matrices $AB+BA=0$ over $F_p$.)

(The degree of the polynomial seems to be 10 or 11. It seems divisible by $x^3$, and I have run a brute force search bounding absolute values of the coefficients by 3, but no polynomial satisfying these conditions is found, so I will increase the bound on the coefficients and will run this search again, but the execution time grows too quickly as the bound increases and it might be that brute force is not a good choice).

Question 3: Do conditions like $q(p_i)=y_i$ imply some bounds on coefficients? E.g., can we estimate that the coefficients are higher than some bound?

Example: How to guess a polynomial $p$ if you know that $p(2) = 11$? It is simple: just write 11 in binary format: 1011 and it gives the coefficients: $p(x) = x^3+x+1$. Well, of course, this polynomial is not unique, because $2x^k$ and $x^{k+1}$ give the same value at $p=2$, so for example $2x^2+x+1$, $4x+x+1$ also satisfy the condition, but their coefficients have greater absolute values!

Question 1: Assume we want to find $q(x)$ with integer coefficients, given its values at some set of primes $q(p_i)=y_i$ such that $q(x)$ has the least possible coefficients. How should we do it? Any suggestion/algorithm/software are welcome. (Least coefficients means: the least maximum of modulii of coefficients).

Question 2: Can one help to guess the polynomial $p$ such that $p(3) = 221157$, $p(5) = 31511625$ with the smallest possible integer coefficients? (Least maximum of modulii of coefficients). Does it exist?

(The degree of the polynomial seems to be 10 or 11, it seems divisible by $x^3$, I have run a brute force search bounding absolute values of the coefficients by 3, but no polynomial satisfying these conditions is found, so I will increase the bound on the coefficients and will run this search again, but the execution time grows too quickly as the bound increases and it might be that brute force is not a good choice).

Question 3: Do conditions like $q(p_i)=y_i$ imply some bounds on coefficients? E.g., can we estimate that the coefficients are higher than some bound?

Example: How can you guess a polynomial $p$ if you know that $p(2) = 11$? It is simple: just write 11 in binary format: 1011 and it gives the coefficients: $p(x) = x^3+x+1$. Well, of course, this polynomial is not unique, because $2x^k$ and $x^{k+1}$ give the same value at $p=2$, so for example $2x^2+x+1$, $4x+x+1$ also satisfy the condition, but their coefficients have greater absolute values!

Question 1: Assume we want to find $q(x)$ with integer coefficients, given its values at some set of primes $q(p_i)=y_i$ such that $q(x)$ has the least possible coefficients. How should we do it? Any suggestion/algorithm/software are welcome. (Least coefficients means: the least maximum of modulii of coefficients).

Question 2: Can one help to guess the polynomial $p$ such that $p(3) = 221157$, $p(5) = 31511625$ with the smallest possible integer coefficients? (Least maximum of modulii of coefficients). Does it exist?

(The degree of the polynomial seems to be 10 or 11. It seems divisible by $x^3$, and I have run a brute force search bounding absolute values of the coefficients by 3, but no polynomial satisfying these conditions is found, so I will increase the bound on the coefficients and will run this search again, but the execution time grows too quickly as the bound increases and it might be that brute force is not a good choice).

Question 3: Do conditions like $q(p_i)=y_i$ imply some bounds on coefficients? E.g., can we estimate that the coefficients are higher than some bound?