10.12.2008

In [DG 89], the authors show that many results concerning the problem of efficient interpolation of k-sparse multivariate polynomials can be formulated and proved in the general setting of k-sparse sums of characters of abelian monoids. In this note we describe another conceptual framework for the interpolation problem. In this framework, we consider R-algebras of functions A₁,...,A_n on integral domain R, together with R-linear operators D_i: A_i → A_i. We then consider functions f from Rⁿ to R that can be expressed as the sum of k terms, each term being an R-multiple of an n-fold product f₁(x₁)⋅...⋅f_n(x_n) where each f_i is an eigenfunction for D_i. We show how these functions can be thought of as k-sums of characters on an associated abelian monoid. This allows one to use the results of [DG 89] to solve interpolation problems for k-sparse sums of functions which, at first glance, do not seem to be characters.