Lacunary polynomials, sparse interpolation and uniqueness in $F_q$

Question

I am currently studying lacunary polynomials in finite fields and trying to understand a basic concept.

When we do dense interpolation using a classical method like Lagrange interpolation or Newton's interpolation, we may expect a dense polynomial of degree $d \le n$ for a set of $n+1$ points i.e., a polynomial of the form:

$$f(x) = \sum_{k=0}^{d} a_k x^{k}, x_d \ne 0$$

In other words, we expect $n$ or less non-constant terms in $f(x)$. This is true of dense interpolation over finite fields such as $\mathbb{F}_q$.

A lacunary polynomial (also called sparse polynomial or fewnomial) is a polynomial where the number of its terms is considered fixed, while the degrees and coefficients of its terms may vary. For example we can write

$$f(x) = a_1 x^{d_1} + . . . + a_l x^{d_{l}}$$

for a lacunary polynomial with at most $l$ terms, with no control whatsoever on the actual value of the degrees $d_i$ and the coefficients $a_i$. (Sparse interpolation methods are given in the linked article and references within).

My understanding is that by using a sparse interpolation algorithm for lacunary polynomials, we can obtain an interpolation of $f(x)$ with fewer than $n$ non-constant terms. Then, by using Fermat's Little Theorem, we can reduce degree $d_i$ of terms with $d_i > q$. Therefore, $\forall i, d_i < q$.

Questions:

1. Is it true that if we built a blackbox for $n+1$ datapoints using Lagrange or Newton interpolation over in $\mathbb{F}_q$ with $n < q$ and then used that as a blackbox for sparse interpolation of a lacunary polynomial (as many of the sparse interpolation methods seem to require one), we would get a different sparse polynomial?
2. Does this mean that the sparse polynomials obtained are not unique in $\mathbb{F}_q$? How does this reconcile with the Theorem on Uniqueness of Interpolating Polynomial (See Theorem 4.1 in linked notes)?

Answer 1

My understanding is that by using a sparse interpolation algorithm for lacunary polynomials, we can obtain an interpolation of $f(x)$ with fewer than $n$ non-constant terms.

This is impossible; you cannot expect to do better than $n$ non-constant terms in general. This is because for $n + 1$ points the vector space of possible inputs is $(n+1)$-dimensional, so the vector space of interpolating polynomials must also be at least $(n+1)$-dimensional to be able to match it.

Edit: Ah, sorry, there's a mistake in this argument. Here I am assuming that the degrees are fixed ahead of time. This argument doesn't apply if the degrees are allowed to depend on the points.

Is it true that if we built a blackbox for $n+1$ datapoints using Lagrange or Newton interpolation over in $\mathbb{F}_q$ with $n < q$ and then used that as a blackbox for sparse interpolation of a lacunary polynomial (as many of the sparse interpolation methods seem to require one), we would get a different sparse polynomial?

I don't know what sparse interpolation method you have in mind, and I also don't know what you mean by "a different sparse polynomial" - different from what?

It is true, over any field including finite fields, that there is a unique interpolating polynomial of degree $\le n$ if we interpolate at $n + 1$ distinct points. If instead you consider sparse interpolating polynomials of degree $> n$ there is no reason to expect uniqueness, again over any field.

(At least, that was my original interpretation of your question. But I don't think the linked paper is doing this; it looks like the point is to write down an algorithm for interpolation which has the property that it finds a sparse representation when one exists, with a runtime depending on the size of such a sparse representation. But the degree is still $n$, I think.)