On zero-testing and interpolation of sparse character sums (preliminary version)

Andreas Dress ^{∗} Fakultät für Mathematik Universität Bielefeld

Johannes Grabmeier IBM Deutschland GmbH Wissenschaftliches Zentrum Heidelberg

Abstract

Motivated by an amazing result of D. Y. Grigoriev and M. Karpinski, the interpolation problem for k-sparse multivariate polynomials has received some attention in recent years. In this note we want to show that essentially all of the results obtained so far hold more generally for k-sparse sums of characters of abelian monoids, thereby providing a useful unified approach to this active field of research. As it turns out the basic ingredients of this approach are the construction of distinction sets for characters and zero–test sets for k-sparse character sums.

Contents

0 Introduction 2

1 Character Sums of Cyclic Groups 4 2 Character Sets which Allow Reduction to Cyclic Groups 7

∗Part of this work was prepared during a visit at the Scientific Center Heidelberg, IBM Germany which is gratefully acknowledged.

3 General Case 12

0 Introduction

The basic ideas of the paper [GK87] were the starting point for the papers [BT88], [CDGK88] and [GKS88], where the question of zero-testing and interpolation of k-sparse multivariate polynomials over fields of characteristic 0 and over finite fields were studied. In this note we want to provide a unified approach to this active field of research, based on the observation that the fundamental ideas in these papers are valid in the more general context of k-sparse sums of characters of abelian monoids.

Let A be an abelian monoid with neutral element 1_{A} and let K be a field. According to the well known Artin-Dedekind Lemma the set Hom(A, (K, ∗)) of all characters, i.e. monoid homomorphisms with 1_{A} ↦ 1_{K} from A into the multiplicative monoid (K, ∗) of K is a linearly independent subset of the K-space of all maps from A into K. For any subset X ⊆ Hom(A, (K, ∗)) of characters and every positive integer k define the set X_{k} of k-sums of characters by

X_{k} := {f : A → K | ∃ f_{1}, …, f_{k} ∈ K, χ_{1}, …, χ_{k} ∈ X, f = ∑_{κ=1}^{k} f_{κ}χ_{κ}}.

For given X and k we are interested in procedures by which for any such f = ∑_{χ} f_{χ}χ in X_{k} its support

supp(f) := {χ ∈ X | f_{χ} ≠ 0}

and its coefficients f_{χ} can be determined from as few as possible evaluations of f. A first step to solve this interpolation problem is, of course, the study of (small) subsets T of A which allow to distinguish any non-trivial k-sum of characters from X from the zero map, that is, subsets T ⊆ A such that for any f ∈ X_{k} \ {0} there exists some a ∈ T with f(a) ≠ 0. We will refer to such subsets as zero-test sets for X_{k}. Obviously, any such zero-test set for X_{k} must contain at least k elements unless #X < k, compare the proof of Lemma 1.1. However, as we will see later on, only in the most simple case of cyclic groups zero-test sets of this cardinality can be guaranteed.

The relation between zero-test sets and subsets of A which may be suitable for interpolation, that is, which allow to distinguish any two different k-sums of characters, is simple and obvious.

Lemma 0.1 A subset T ⊆ A has the property that the associated restriction map K^{A} → K^{T} : f ↦ f|_{T} is injective on X_{k} ⊆ K^{A} if and only if T is a zero-test set for X_{2k}.

Hence, in principle, for any zero-test set T for X_{2k} it should be possible to compute for any map f = ∑_{χ∈X} f_{χ}χ in X_{k} its support and its coefficients from its restriction f|_{T}. Again, this holds indeed for the particularly simple minimal zero-test sets one has in cyclic groups. In general there does not seem to exist a universally applicable interpolation algorithm which for any field K, any monoid A, any set X ⊆ Hom(A, (K, ∗)) of K-valued characters of A, and any zero-test set T ⊆ A for X_{2k} allows to reconstruct the support and the coefficients of f for any f ∈ X_{k} systematically from its restriction to T, except, of course, the trivial, but surely not efficient algorithm, which for all possible choices of χ_{1}, ..., χ_{k} ∈ X and f_{1}, ..., f_{k} ∈ K compares f(a) with ∑_{κ=1}^{k} f_{κ}χ_{κ}(a) for all a ∈ T. Therefore it appears to be worthwhile to discuss in some detail what can be done in this direction.

The examples we have in mind are in particular the cases where A equals U^{n} for some submonoid U of the monoid (K, ∗) and X is a subset of all maps

χ^{α} = χ^{(α_{1},···,α_{n})} : U^{n} → K

where

χ^{α}((x_{1}, …, x_{n})) := x_{1}^{α_{1}} · . . . · x_{n}^{α_{n}}

for α_{1}, ..., α_{n} ∈ IN_{0} := {0, 1, ...} and x_{1}, ..., x_{n} ∈ U.

In the case of K := Q (or any other infinite field) and U := K the characters from X := {χ^{α}, α ∈ IN_{0}^{n}} correspond to the monomials in n indeterminates as k-sum characters correspond to k-sparse polynomials. In case U is finite it has turned out to be particular interesting to study the above problems for such monomial characters of type χ^{α} whose local degrees α_{1}, ..., α_{n}, are bounded by a natural number q, that is we choose

X = X(q, n) := {χ^{α} | α ∈ q^{n}},

where q is defined to be q := {0, …, q − 1}.

The overall outline of our note is as follows: In the first section we will assume A to be a cyclic group. In this almost trivial case minimal zero-test sets and optimal interpolation procedures can be constructed quite easily in a rather natural and a straightforward manner. Once this is established we will show in the second section that for surprisingly many other choices of A and X our problem can be reduced to the cyclic case.

In various cases this can be done simply by exhibiting a cyclic submonoid, (i.e. a submonoid wich is a cyclic group) A′ of A which distinguishes the charachters in the given set X (i.e. with χ|_{A′} ≠ ψ|_{A′} for any two different characters χ and ψ in X).

In other cases where this simple procedure cannot be applied a more subtle approach can be used instead which consists in the construction of a whole family of cyclic submonoids such that for any k characters from X there exists at least one member in this family which distinguishes these k characters. It is remarkable that all but one of the cases studied in [BT88],

[CDGK88] and [GKS88] fall in either one of these two categories. In section 3 we will discuss methods which apply to ‘properly’ non-cyclic

cases. A method based on a simple idea, developed in [CDGK88], by which zero-test sets for a product of monoids can be constructed from zero-test sets of the factors, is presented. In addition a quite general and efficient interpolation algorithm is given, of course needing more evaluations than in the cyclic case, but not needing to find roots of a polynomial as it is necessary in the case of cyclic groups. Instead, it presupposes the knowledge of a finite super set Y of supp(f), say of cardinality q, in which case it needs one inversion of a q × q-matrix and many inversions of k × k-matrices.

Finally, in the last section, we will use all these results to discuss in some detail how for a given submonoid U of the multiplicative monoid (K, ∗) and for variable n, q, k ∈ IN the minimal cardinality of zero-test sets in U^{n} for k-sums of characters from the set X = X(q, n) varies with n, q and k. As it will turn out there seems to exist some kind of ‘phase transition’ depending on the size first of all of q, but also of n and k, relative to the cardinality of U. This will help to clarify in particular the relation between the results presented in [BT88], [CDGK88] and [GKS88].

1 Character Sums of Cyclic Groups

In this section we assume A to be a cyclic group, generated by some a ∈ A, and we assume X to consist of all K-valued characters of A:

X = Hom(A, (K, ∗)).

Without loss of generality we may assume A to be infinite in which case evaluation at a defines a bijection

X → K, χ ↦ χ(a)

whose inverse is given by

K → X, c ↦ (χ_{c} : A → K, a^{i} ↦ c^{i}).

The basis observation on which everything in the next two sections is based, is the following Vandermonde Lemma:

Lemma 1.1 Let A be a cyclic group generated by an element a ∈ A. Then for X = Hom(A, (K, ∗)) and each natural number k ≤ #A the set

{1, a, a^{2}, …, a^{k−1}}

is a minimal zero-test set for X_{k}.

Proof. Let f = ∑_{κ=1}^{k} f_{κ}χ_{κ} ∈ X_{k} be a k-sum of characters. We have

f(a^{i}) = ∑_{κ=1}^{k} f_{κ}χ_{κ}(a^{i}) = ∑_{κ=1}^{k} f_{κ}χ_{κ}(a)^{i}

for all i ∈ IN_{0}. Thus we obtain the following matrix equation

(χ_{κ}(a)^{i})_{0≤i<k,1≤κ≤k} · (f_{κ})_{1≤κ≤k} = (f(a^{i}))_{0≤i<k}.

The k-square matrix (χ_{κ}(a)^{i})_{0≤i<k,1≤κ≤k} is a non-singular Vandermonde matrix since the χ_{κ}(a) are pairwise different.

Note that our proof shows as well how to compute the coefficients of any f ∈ X_{k} from the values f(1), f(a), f(a^{2}), …, f(a^{k−1}) once its support is known.

To find the support of f from its values on the zero-test set {1, a, a^{2}, …, a^{2k−1}} for X_{2k} we can use the following result, rather special cases of which occur in [BT88] and [CDGK88] and decoding of BCH-codes, see [LN83].

Theorem 1 Let A be a cyclic group generated by an element a ∈ A and let f be a sum of atmost k characters from X = Hom(A, (K, ∗)). Then the following holds: i) The rank of the matrix M_{k} := (f(a^{i+j}))_{0≤i,j<k} coincides with the cardinality of supp(f).

ii) If k̃ := #supp(f) (≤ k) and if

( e_{1} ; e_{2} ; ⋮ ; ek̃ ) := Mk̃^{−1} · ( −f(ak̃) ; −f(a^{k̃+1}) ; ⋮ ; −f(a^{2k̃−1}) )

then the equation

Xk̃ + e_{1}X^{k̃−1} + … + e_{k̃−1}X + ek̃ = 0  (1)

has k̃ different solutions c_{1}, …, ck̃ in K. Furthermore one has

supp(f) = {χ_{c_{κ}} | 1 ≤ κ ≤ k̃}.

Proof. Let f = ∑_{κ∈I} f_{κ}χ_{κ}, where I is any finite superset of the indices of the support of f. We denote by e_{i}(I) the i-th elementary symmetric polynomial in #I indeterminates, evaluated at (χ_{α}(a))_{α∈I}. Now substituting χ_{α}(a), α ∈ I, for X in the polynomial

p := ∏_{β∈I}(X − χ_{β}(a)) = ∑_{j=0}^{#I}(−1)^{#I−j}e_{#I−j}(I) · X^{j} ∈ K[X]  (2)

yields the generalized Newton identities [MS72], p. 244

0 = ∑_{j=0}^{#I}(−1)^{#I−j}e_{#I−j}(I)χ_{α}(a)^{j}, α ∈ I.

Fixing an i ∈ IN_{0}, multiplying the equation corresponding to α by f_{α}χ_{α}(a)^{i} and summing over all α ∈ I results in the following system of equations

0 = ∑_{j=0}^{#I}(−1)^{#I−j}e_{#I−j}(I)f(a^{i+j}), i ∈ IN.

As e_{0}(I) = 1 the equations for 0 ≤ i < #I are equivalent to the matrix equation

(f(a^{i+j})_{0≤i,j<#I} · ((−1)^{#I−j} e_{#I−j} (I))_{0≤j<#I} = −(f(a^{i+#I}))_{0≤i<#I}. (3)

The matrix (f(a^{i+j}))_{0≤i,j<#I} equals (χ_{α}(a^{i}))D_{I}(χ_{α}(a^{i}))^{t}, where the #I-square matrix D_{I} is the diagonal matrix diag((f_{α})_{α∈I}), see [LN83], 9.48, 9.49. As #{χ_{α}(a) | α ∈ supp(f)} = k̃, the cardinality of supp(f) equals the rank of the k-square matrix f(a^{i+j}))_{0≤i,j<k} and this proves i). Furthermore Mk̃ = (f(a^{i+j}))_{0≤i,j<k̃} is non-singular and from equation (3) we see that e_{k̃−j} = (−1)^{#I−j} e_{#I−j} (I) holds for all 1 ≤ j ≤ k̃ and for I = supp(f). Therefore the polynomial in equation (1) coincides with p and ii) is proved.

If an efficient algorithm for finding the roots of a polynomial over K which is known to have all its roots in K, then it is easy to derive an efficient algorithm to interpolate any f ∈ X_{k} from its values on {1, a, …, a^{2k−1}} from Theorem 1

2 Character Sets which Allow Reduction to Cyclic Groups

Given an abelian monoid A and a set X ⊆ Hom(A, (K, ∗)) of K-valued characters of A, we say that X allows reduction to one cyclic group if there exists an element a ∈ A which distinguishes all characters in X, i.e. χ(a) ≠ ξ(a) for χ ≠ ξ. It follows immediately from the Artin-Dedekind Lemma that in this case a k-sum f of characters from X is trivial if and only if the restriction of f to the cyclic group generated by a is trivial. Hence the results of section 1 can be applied. In particular {1, a, …, a^{k−1}} is a zero-test for X_{k} and the sums f of characters in X_{k} can be identified from the values of f on {1, a, …, a^{2k−1}}.

Important examples of character sets which allow cyclic reduction are the following ones:

1. If the submonoid U of (K, ∗) contains a submonoid which is a free abelian submonoid of rank n, generated, say, by {u_{1}, u_{2}, …, u_{n}}, (in particular, this is the case if U contains Q), then the set of all monomial charcters {χ^{α} | α ∈ ZZ^{n}} of U^{n} allows reduction to a cyclic group: indeed, any two different monomial characters of U^{n} differ necessarily on a := (u_{1}, …, u_{n}). This implies in particular many of the results presented in [GK87] and [BT88], where u_{i} is chosen to be the i-th prime.

2. Similarly, if U ≤ (K, ∗) contains at least one element, say u, of infinite order or of order at least q^{n} for some q ∈ IN then all monomial characters in X := X(q, n) = {χ^{α} | α ∈ q^{n}} differ on a := (u, u^{q}, …, u^{q^{n−1}}) in view of the uniqueness of q-adic expansion, and this is used in [CDGK88].

In particular, since any infinite submonoid of (K, ∗) either contains an element of infinite order or cyclic submonoids of arbitary large order (cf. Artin) we get the following essentialy trivial, though surprisingly general theorem.

Theorem 2 If U is an infinite submonoid of the multiplicative monoid (K, ∗) of a field K and if for natural numbers n and q

X := X(q, n) = {χ^{α} | α ∈ q^{n}}

denotes the set of all monomial characters of U^{n} local degree between 0 and q − 1, then for any k ∈ IN there exists a zero-test set of the form {1, a, …, a^{k−1}} for X^{k} in U^{n} and, in addition, one can identify the support of any map f ∈ X_{k} from its values on a corresponding zero-test set for X_{2k}.

To apply the results from section 1 even in cases which do not simply allow reduction to a cyclic group we use the following definition: for givien A and X ⊆ Hom(X, (K, ∗)), as above we define a subset D ⊆ A to be a k-cover for X if for any subset Y ⊆ X of cardinality at most k there exists some a ∈ D with χ(a) ≠ ψ(a) for all χ, ξ ∈ Y with χ ≠ ξ. Obviously, Lemma 1.1 implies :

Lemma 2.1 If D is a k-cover of an abelian monoid A and for a character set X ⊆ Hom(X, (K, ∗))), then D^{[k]} := {a^{i} | a ∈ D, 1 ≤ i < k} is a zero-test set for X_{k}.

In particular, we have the following

Corollary 2.2 If X = Hom(A, (K, ∗)) and if D ⊆ A generates A, then D^{[2]} = D ∪ {1_{A}} is a zero-test set for X_{2}.

To construct k-covers in more general situations we may adopt an idea from [GKS88]: for X ⊆ Hom(A, (K, ∗)) and a natural number k we define the collection of h-distinction sets:

D(X, h) := {D ⊆ A| ∀χ, ξ ∈ X, χ ≠ ξ, #{d ∈ D | χ(d) = ξ(d)} < h}.

Hence a member D of D(X, h) has the property that for every pair of distinct characters there are at most h − 1 elements in D where the two characters are equal. Of course we are not interested in sets D of cardinality smaller than h, which are trivially in D(X, h), but in those which are large enough to have subsets being in D(X, 1) as well.

Lemma 2.3 Every h-distinction set D having more than (h−1)·\binom{k}{2} elements is a k-cover of X.

Proof. Let Y be a subset of X, having at most k elements. The set ∪_{χ,ξ∈Y,χ≠ξ}\{d ∈ D | χ(d) = ξ(d)\} has atmost (h − 1) · \binom{#Y}{2} ≤ (h − 1) · \binom{k}{2} elements, therefore there exists an element a in D such that χ(a) ≠ ξ(a) for all distinct χ, ξ ∈ Y.

In [GKS88] D. Grigoriev, M. Karpinski and M. Singer have shown that the following observation — tranformed here into our more general context — has striking consequences.

Lemma 2.4 (cf. [GKS88]) . Let A denote an abelian monoid and assume K to be field, containing a primitive root of unity ω of order e. Assume that for some positive integer n we have characters χ_{1}, …, χ_{n} : A → K, elements a_{1}, …, a_{n} ∈ A, and integers ϵ_{μ,ν} ∈ ZZ for all 1 ≤ μ, ν ≤ n such that

χ_{μ}(a_{ν}) = ω^{ϵ_{μ,ν}}.

Assume furthermore that det(ϵ_{μ,ν}) ≠ 0 and that c := (c_{ν,ρ})_{1≤ν≤n,1≤ρ≤r} is an n × r-matrix for some r ≥ n such that every n × n-submatrix of c has a non-vanishing determinant. Then if

q := ⌈\frac{e}{n · max_{μ,ρ}(| ∑_{1≤ν≤n} ϵ_{μ,ν}c_{ν,ρ})|)}⌉

and

X := {χ^{α} : A → R | α ∈ q^{n}},

where χ^{α} denotes ∏_{1≤ν≤n} χ_{ν}^{α_{ν}}, is a set of q^{n} different characters, then the set

D := {d_{ρ} := ∏_{1≤ν≤n} a_{ν}^{c_{ν,ρ}} | 1 ≤ ρ ≤ r}

is in D(X, n).

Proof. For every pair of different characters χ^{α} and χ^{β} from X and for all 1 ≤ ρ ≤ r we have

χ^{α}(d_{ρ}) = ω^{∑_{μ=1}^{n}(∑_{ν=1}^{n} ϵ_{μ,ν}c_{ν,ρ})α_{μ}}

which equals χ^{β}(d_{ρ}) if and only if

∑_{μ=1}^{n}(∑_{ν=1}^{n} ϵ_{μ,ν}c_{ν,ρ})(α_{μ} − β_{μ}) ≡ 0 modulo e.

Furthermore we have

| ∑_{μ=1}^{n}(∑_{ν=1}^{n} ϵ_{μ,ν}c_{ν,ρ})(α_{μ} − β_{μ})| ≤ n · max_{μ,ρ}(| ∑_{1≤ν≤n} ϵ_{μ,ν}c_{ν,ρ}|)(q − 1) < e.

Altogether two different characters χ^{α}, χ^{β} ∈ X coincide at an element d_{ρ} ∈ D if and only if

∑_{μ=1}^{n}(∑_{ν=1}^{n} ϵ_{μ,ν}c_{ν,ρ})(α_{μ} − β_{μ}) = 0.

If there were more than n − 1 elements from D where χ^{α} and χ^{β} coincide then the non-singularity of the corresponding n × n-submatrix of c together with that of det(ϵ_{μ,ν}) would imply α − β = (0, …, 0).

In order to apply this lemma we first of all have to construct an integral matrix c satisfying the requirements from the lemma and having not too large entries. To do this we present the following lemma from [GKS88], which uses Cauchy’s determinants in a rather elegant way:

Lemma 2.5 For every two positive integers r and n there exists an integral n × r-matrix c = (c_{ν,ρ})_{1≤ν≤n,1≤ρ≤r}, the absolute value of each entry bounded by n + r − 1, such that no subdeterminant of c vanishes. Furthermore, all entries in the first row are pairwise different.

Proof. Choose a prime number p with n + r ≤ p < 2(n + r). Then for 1 ≤ ν ≤ n and 1 ≤ ρ ≤ r none of the numbers ν + ρ − 1 considered in GF (p) equals 0. Therefore we can consider the matrix

(\frac{1}{ν + ρ − 1})_{1≤ν,ρ<r} ∈ GF (p)^{n×r}.

By Lemma 2.6 below no subdeterminant of this matrix vanishes. Choose integers c_{ν,ρ} with −\frac{p−1}{2} ≤ c_{ν,ρ} ≤ \frac{p−1}{2} such that \frac{1}{ν+ρ−1} = c_{ν,ρ} in GF (p) , then the same is true for the matrix c = (c_{ν,ρ}).

Lemma 2.6 (Cauchy) . For every natural number n the following identity in rational functions in commuting indeterminates (x_{1}, …, x_{n}), (y_{1}, …, y_{n}) holds:

det(\frac{1}{x_{i} + y_{j}} )_{1≤i≤n,1≤j≤n} = \frac{∏_{1≤i<j≤n}(x_{j} − x_{i}) ∏_{1≤i<j≤n}(y_{j} − y_{i})}{n ∏_{1≤i,j≤n}(x_{i} + y_{j})}.

Proof. The polynomial

∏_{1≤i,j≤n}(x_{i} + y_{j}) det(\frac{1}{x_{i} + y_{j}} )_{1≤i≤n,1≤j≤n}

is not the zero-polynomial, because the coefficient of

x_{1}^{n−1}x_{2}^{n−2} … x_{n−1}y_{1}^{n−1}y_{2}^{n−2} … y_{n−1}

is 1. Considered as polynomial in the y’s it is alternating. Each coefficient of the monomials in the y’s is itself an alternating polynomial in the x’s. As the Vandermonde is the alternating non-zero polynomial having smallest degree, namely \binom{n}{2}, it is a scalar multiple of the Vandermonde determinant involving the indeterminates (y_{1}, …, y_{n}) and the coefficient has to be a Vandermonde determinant involving (x_{1}, …, x_{n}).

The last lemmata together imply the next result.

Theorem 3 If U is a finite (and therefore cyclic!) subgroup order e of the multiplicative group of a field K, if A = U^{n} is the n-fold direct product of U, then for every positive integer k and q satisfying

n · (q − 1) · (n + (n − 1) · \binom{k}{2}) < e

there exists a zero-test set of order at most k · ((n − 1) · \binom{k}{2} + 1) for the sums of characters from X(q, n)_{k} = {χ^{α} | α ∈ q^{n}}_{k}.

Proof. W.l.o.g. assume n ≥ 2. Put r := (n − 1) · \binom{k}{2} + 1 and choose c = (c_{ν,ρ})_{1≤ν≤n,1≤ρ≤r} according to Lemma 2.5. Choose a generator ω for U. Note that χ_{μ}(a_{ν}) = ω^{δ_{μ,ν}} for

a_{ν} := (1, …, 1, ω, 1, …, 1),

ω at the position ν, and the projections χ_{μ} = χ^{(δ_{μ,0},...,δ_{μ,n−1})} to the μ-th component holds for all 1 ≤ μ, ν ≤ n. An application of Lemma 2.4 guarantees the set

D := {d_{ρ} := ∏_{1≤ν≤n} a_{ν}^{c_{ν,ρ}} | 1 ≤ ρ ≤ r}

to be in D(X(q̃, n), n) for q̃ := ⌈\frac{e}{n·max_{μ,ρ}(| ∑_{1≤ν≤n} ϵ_{μ,ν}c_{ν,ρ})|)}⌉ and therefore in D(X(q, n), n) in view of

q < \frac{e}{n · (n + (n − 1) · \binom{k}{2})} + 1 = \frac{e}{n · (n + r − 1)} + 1 ≤
≤ \frac{e}{n · max_{μ,ρ}(|c_{μ,ρ}|)} + 1 ≤ q̃ + 1,

that is q ≤ q̃. In view of 0 ≠ |c_{0,ρ}−c_{0,ρ′}| ≤ 2·(n+r−1) = 2·(n+(n−1)·\binom{k}{2}) < e and therefore d_{ρ} ≠ d_{ρ′} for 1 ≤ ρ < ρ′ ≤ r the set D has r elements. Hence (n − 1) · \binom{k}{2} ≤ r = #D and we may apply the Lemmata 2.3 and 2.1 to conclude that

{(ω^{κ·c_{0,ρ}}, ω^{κ·c_{1,ρ}}, …, ω^{κ·c_{n−1,ρ}}) | 1 ≤ ρ ≤ r, 1 ≤ κ < k}

is a zero-test set for X(q, n)_{k} of size at most k · r = k · ((n − 1) · \binom{k}{2} + 1)

The main result of the paper [GKS88] is the case where K is the finite field GF (s) for a some s with s ≥ qk^{2}n^{2} and U := GF (s) \ {0} in Theorem 3.

3 General Case

If no reduction to a cyclic group is possible, all we can do is to give a method for a recursive construction of zero-test sets for direct products of abelian monoids from those of the factors.

Lemma 3.1 (cf. [CDGK88]) . If A and B are abelian monoids, if for given X ⊆ Hom(A, (K, ∗)) and Y ⊆ Hom(B, (K, ∗)) we have zero-test sets A_{1} = {1_{A}}, A_{2}, …, A_{k} ⊆ A and B_{1} = {1_{B}}, B_{2}, …, B_{k} ⊆ B for X_{1}, X_{2}, …, X_{k} and Y_{1}, Y_{2}, …, Y_{k}, respectively, then — identifying Hom(A × B, (K, ∗)) with Hom(A, (K, ∗)) × Hom(B, (K, ∗)), as usual — the set

⋃_{i·j≤k} A_{i} × B_{j} ⊆ A × B

is a zero-test set for (X × Y)_{k}.

Proof. Note that any f ∈ (X × Y)_{k} can be written uniquely in the form

f = ∑_{η∈Y} f_{η} · η

for some f_{η} ∈ X_{i(η)} (η ∈ Y) and ∑_{η∈Y} i(η) ≤ k. Obviously the cardinality j of the Y -support supp_{Y} (f) := {η ∈ Y | f_{η} ≠ 0} of f is bounded by k and in case f ≠ 0 there must exist some η_{0} ∈ supp_{Y} (f) with i(η_{0}) ≤ \frac{k}{j}. Choose a ∈ A_{i(η_{0})} with f_{η_{0}}(a) ≠ 0. Consequently, f(a, −) is a non-zero j-sum of characters from Y for which we can find an element b ∈ B_{j} with f(a, b) ≠ 0.

This lemma generalizes immediately to the situation of more than two factors.

Lemma 3.2 If A^{(1)}, …, A^{(n)} are abelian monoids, if for given X^{(ν)} ⊆ Hom(A^{(ν)}, R) we have zero-test sets A_{1}^{(ν)} = {1_{A^{(ν)}}}, A_{2}^{(ν)}, …, A_{k}^{(ν)} ⊆ A^{(ν)} for X_{1}^{(ν)}, X_{2}^{(ν)}, …, X_{k}^{(ν)}, respectively for ν = 1, …, n, then the set

⋃_{i_{1}·...·i_{n}≤k} A_{i_{1}}^{(1)} × … × A_{i_{n}}^{(n)} ⊆ A^{(1)} × … × A^{(n)}

is a zero-test set for k-sums from X^{(1)} × … × X^{(n)} ⊆ Hom(A^{(1)}, R) × … × Hom(A^{(n)}, R) = Hom(A^{(1)} × … × A^{(n)}, R).

Corollary 3.3 Let A be a finitely generated abelian group isomorphic to ∏_{1≤ν≤n} C_{q_{ν}} where C_{q_{ν}} is a cyclic group of order q_{ν}, q_{ν} a prime power or ∞, generated by a_{ν}. Then

⋃_{{k_{1}·...·kn≤k \atop kν ≤min(k,qν)}} T_{k_{1}}^{(1)} × … × T_{k_{n}}^{(n)},

where T_{k_{ν}}^{(ν)} := {1, a_{ν}, a_{ν}^{2}, …, a_{ν}^{k_{ν}−1}} is a zero-test set for all sums of characters from X_{k} = {χ^{α} | α ∈ ∏_{1≤ν≤n} q_{ν}} (∞ := ZZ).

Theorem 4 (cf. [CDGK88]) . Let U be a finite submonoid of order q of the multiplicative group of a field K for a natural number q, let X be the set of characters X(n, q) for U^{n} and T be any zerotest set for X_{k}. If U contains 0, then for every subset S ⊆ {1, ..., n} such that #S ≤ ⌊log_{2}k⌋ the set T contains an element a^{S} = (a_{1}^{S}, …, a_{n}^{S}) with S = {i : a_{i}^{S} = 0}. Hence T has at least ∑_{i=0}^{⌊log_{2} k⌋} \binom{n}{i} elements.

Proof. For every subset S ⊆ {1, ..., n} such that #S ≤ ⌊log_{2}k⌋ define a sum of characters by

f_{S} := ∏_{i∈S}(χ_{i}^{q−1} − 1) · ∏_{i∉S} χ_{i},

where χ_{i} is the projection to the i-th component. These functions have the following properties:

1. p_{S} is in X_{k}.

2. p_{S}(a) ≠ 0 if and only if {i : a_{i} = 0} = S.

The first property follows from 2^{#S} ≤ 2^{⌊log_{2}k⌋} ≤ k, the second from the fact that the zeros of χ_{i}^{q−1} − 1 are exactly the elements of U \ {0}. Hence, to distinguish such a polynomial and the zero-polynomial, there has to be an element a^{S} as claimed in the set A.

In case q = 2 we may combine Corollary 2.2 and the results before to obtain a minimal zero-test set.

Theorem 5 (cf. [CDGK88]) . Let U be the submonoid {0, 1} of a field K, let X be the set of characters X(n, 2) for U^{n}. Then

\{a^{S} ∈ U^{n} | S ⊆ \{1, ..., n\}, a_{i}^{S} = \{ \begin{matrix}1, & if i ∈ S; \\ 0, & if i ≠ S. \end{matrix}

is a minimal zero-test set of X_{k} of cardinality ∑_{i=0}^{⌊log_{2} k⌋} \binom{n}{i} .

Proof. It suffices to show that this set really is a zero-test set, but this follows from Lemma 3.1 using A_{2}^{(ν)} := {0, 1} for all 1 ≤ ν ≤ n.

As we have observed already in the introductions there does not seem to exist a universally applicable algorithm which would allow to interpolate k-sums of characters from some character set X from their restrictions to zero-test sets for X_{2k}. Hence to construct interpolation algorithms one has to consider more specific situations. One such situation is described in the following:

Theorem 6 . Assume that for some field K, some monoid A, some finite set X ⊆ Hom(A, (K, ∗)) of K-valued characters of A of cardinality q, and some subset D ⊆ A of the same cardinality q with det(χ(a))_{χ∈X,a∈D} ≠ 0, the inverse of the q × q-matrix (χ(a))_{χ∈X,a∈D} is given and that in addition for any two natural numbers k and n a zero-test set T_{n,k} ⊆ A^{n} of cardinality t(n, k) for X^{n} is specified. Then for any k, n ∈ IN one can compute supp(f) as well as the coefficients of f for any f ∈ (X^{n})_{k} from altogether at most n · (k^{2} = q) · t(n − 1, k) evaluations of f by an algorithm which needs at most 2n matrix inversions, each matrix having at most k rows ans colums, and otherwise only matrix multiplications and methods to find for r ≤ k and r ≤ l ≤ max(k^{2}, q) the first r linearly indepentent columns in an r × l matrix of rank r. Moreover, the 2n matrix inversions can be performed on n parallel processors so that the first n inversions, then the next \frac{n}{2}, \frac{n}{4}, … inversions can be done in parallel, leading to altogether to log_{2}(n) basic computational rounds.

Proof. We define set partitions P^{l} := (P_{1}^{l}, …, P_{⌈ \frac{n}{2^{l}} ⌉}^{l}) of n for 0 ≤ l ≤ ⌈log_{2} n⌉ by

P_{ν}^{l} := {ν · 2^{l}, ν · 2^{l} + 1, …, (ν + 1) · 2^{l} − 1},

of course stopping at n − 1 in the last part. Next the sets (supp_{P_{ν}^{l}})_{0≤ν<⌈ \frac{n}{2^{l}} ⌉} are determined inductively. In case l = 0 we use n-times Lemma ?? for T := P_{ν}^{0} = {ν} and the supersets Ŷ^{{ν}}, always setting A^{T} to be ∏_{ν∉T} A^{(ν)} and making the usual identifications. For the induction step we use at most ⌈\frac{n}{2^{l+1}} ⌉-times Lemma ?? for T := P_{ν}^{(l+1)} and the supersets Ŷ^{P_{ν}^{l+1}} := supp_{P_{2ν}^{l}}(f) × supp_{P_{2ν+1}^{l}i}(f). This is justified as more generally suppose that for disjoint subsets T_{0} and T_{1} of n the corresponding supports supp_{Y^{T_{0}}}(f) and supp_{Y^{T_{1}}}(f) are known, then it is clear that we can use Y^{T_{0}∪T_{1}} ⊇ Ŷ^{T_{0}∪T_{1}} := supp_{Y^{T_{0}}}(f) × supp_{Y^{T_{1}}}(f) as a finite superset of supp_{Y^{T_{0}∪T_{1}}}(f). Finally we arrive at supp(f). An application of lemma ?? for T := n gives the coefficients of f.

Note that we only required elements d^{T} and zero-test sets Z^{T} for the at most 2n + 1 sets occuring in the set partitions. The calculations to recover f require at most 2n + 1 applications of Lemma ??, i.e. in step 0 we have to invert (in parallel) n Vandermonde matrices, having as many rows and columns as the cardinality of the given supersets of supp_{{ν}}(f). In the next ⌈log_{2} n⌉ steps at each stage l at most ⌈\frac{n}{2^{l}} ⌉ Vandermonde matrices of size k^{2} × k^{2} have to be inverted. A further inversion of a k × k Vandermonde matrix gives the coefficients. Note further that the number of evaluation points can be reduced if one allows adaptive algorithms.

A similar result holds for the more general case of products ∏_{1≤ν≤n} and character sets X_{1}, …, X_{n} as long as for every 1 ≤ ν ≤ n a zero-test set for a (∏_{μ≠ν} X_{μ})_{k} is known.

References

[BT88] Ben-Or, M., Tiwari, P. A Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation, Proc. STOC ACM, (1988).

[CDGK88] Clausen, M., Dress, A., Grabmeier, J., Karpinski, M. On zerotesting and interpolation of k-sparse multivariate polynomials over finite fields, Theor. Comp. Sc., to appear, 1989

[GK87] Grigoriev, D.Y., Karpinski, M. The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents is in NC, Proc. 28^{th} IEEE FOCS (1987), Los Angeles, Oct. 12–14, 1987.

[GKS88] Grigoriev, D.Y., Karpinski, M., Singer, M.F. Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields, preprint, 1988.

[KR88] Karp, R.M., Ramachandran, V. L. A Survey of Parallel Algorithms for Shared-Memory Machines, Preprint, 1988, to appear in the Handbook of Theoretical Computer Science, North-Holland [LN83] Lidl, H., Niederreiter, H. Finite Fields,Encyclopedia of Mathe-

matics and its Applications, Vol.10, Cambridge University Press 1983.

[MS72] MacWilliams, F.J., Sloane, N.J.A. The Theory of Error Correcting Codes,North Holland (1972).

[M86] Mulmuley, K. A Fast Parallel Algorithm to Compute the Rank of a Matrix over an Arbitrary Field, Proc. STOC ACM (1986), 338–339.