Polynomials – How to Find an Integer Coefficient Polynomial from Values at Few Points

algorithmscomputer-algebrapolynomials

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 3×3 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?

Best Answer

You can certainly do better than brute force by considering modular constraints. If the solution is $p(x) = \sum_i a_i x^i$ then $p(x) - \sum_{j=0}^{n-1} a_j x^j$ is divisible by $x^n$ and $$\frac{p(x) - \sum_{j=0}^{n-1} a_j x^j}{x^n} = a_n \pmod x$$

Solving for $a_0$ in each of the given bases and using the Chinese remainder theorem gives an equivalence class for $a_0$; for each possible value of $a_0$ you can expand similarly for $a_1$; and traversing this tree in order of increasing cost of the coefficients gives a directed search. This works in principle for any cost function which increases when any coefficient increases in absolute value.

This Python code implements the idea and finds two polynomials with sum of absolute values of 29:

$$-2x^3 + 4x^4 + 3x^5 + 11x^6 + x^7 + 5x^8 + 3x^{10} \\ -2x^3 + 4x^4 + 3x^5 - 4x^6 + 9x^7 + 4x^8 + 3x^{10}$$

and one polynomial with maximum absolute value of 7:

$$-2x^3 + 4x^4 + 3x^5 - 4x^6 - 6x^7 - 3x^8 + 7x^9 + 2x^{10}$$

in a small fraction of a second.

Some follow-up questions in comments brought me to the realisation that if we're trying to interpolate $\{ (x_i, y_i) \}$ with the $x_i$ coprime, there is at most one polynomial with coefficients in the range $[-\lfloor \tfrac{(\operatorname{lcm} x_i) - 1}2 \rfloor, \lfloor \tfrac{\operatorname{lcm} x_i}2 \rfloor]$, because the tree collapses to a chain. This gives the following algorithm for finding such a polynomial, if it exists:

M := lcm(x_i)
while any y_i is non-zero:
    find a_0 by Chinese remainder theorem
    if a_0 > floor(M / 2):
        a_0 -= M

    output a_0
    update y_i := (y_i - a_0) / x_i

In the long term, the initial values of the $y_i$ are reduced to negligibility by the repeated division by $x_i$, so eventually each $y_i$ will be reduced to a range which is bounded by $\frac{x_i}{x_i - 1} M$. This means that for a given set of $x_i$ it's possible to compute a finite directed graph to see whether existence is guaranteed.

In the particular case that the $x_i$ are $\{3, 5\}$ there are three cycles, all of them loops: $(0,0) \to (0,0)$ is the terminating loop which indicates that a solution exists, but there are also loops $(2, 1) \to (2, 1)$ and $(-2, -1) \to (-2, -1)$.

Related Question