The interpolation problem for \(k\)-sparse polynomials and character sums (Q1814140)

The central theme of the paper is zero-testing and interpolation of k- sparse multivariate polynomials over fields of characteristic zero and over finite fields. The results are described in the more general framework of k-sparse sums of characters of abelian monoids. Let \(A\) be an abelian monoid and \(K\) a field. Let \(X\) be a subset of the set of all characters \(\Hom(A,(K,*))\), \(k\) a positive integer. Denote by \(X_ k\) the set \[ X_ k:=\{f:A\mapsto K\mid\exists f_ 1,\ldots,f_ k\in K,\quad \chi_ 1,\ldots,\chi_ k\in X,\quad f=\sum_{\kappa=1}^ k f_ \kappa\chi_ \kappa\}. \] The problem of interest is, for any \(f\) in \(X_ k\), to construct procedures to determine its support \(\text{supp}(f)=\{\chi\in X\mid f_ \chi\neq0\}\) and its coefficients from as few as possible evaluations of \(f\). The first step to solve this interpolation problem is to construct zero-test sets for \(X_ k\). These can be seen as tools to compute for any \(f\) its support and its coefficients. This holds for the particularly simple minimal zero-test sets one has for cyclic monoids. In general, there does not seem to exist a universally applicable interpolation algorithm. The authors discuss what is possible in this case.