# The minimal degree of solutions to polynomial equations used for the construction of refinable functions.

1 Introduction

Nowadays, subdivision schemes and wavelet analysis are widely used in many areas of applied mathematics and engineering, cf. [1, 2, 3, T, 15, 18]. The construction of wavelets relies on an underlying refinable function that generates a multiresolution analysis. Pundamental refinable functions, i.e., continuous refinable functions that interpolate the integer grid, are desirable because they provide favorable sampling formulas, cf. [4, 5, 10, 11] and Section 2. Smoothness, small support, and reproduction of polynomials are further important characteristics of good refinable functions because these properties transform into well-localized wavelets with high approximation orders. However, small support and high order of polynomial reproduction are competitive properties that must be balanced.

Constructions of fundamental refinable functions are often based on a simple start function that is used as the input of a polynomial equation. Its solution induces a new refinable function with hopefully better properties. A polynomial solution's total and maximum degree provide upper bounds on the size of the refinable function's support. Therefore, solutions with minimal total and minimal maximum degree are sought.

This polynomial approach reflects convolutions of refinable functions and has been extensively studied in the univariate setting, cf. [6]. In fact, univariate solutions with minimal degree have been identified as the Bezout polynomials, cf. [6].

Studying such polynomial equations in the multivariate setting is more complicated due to the much more complex algebraic structure of the ring of multivariate polynomials. Multivariate polynomial equations have probably first been applied to construct multivariate refinable functions in [9], see also [8, 13]. However, specifying the minimal total and minimal maximum degree is an open problem in the multivariate setting since 1997. The present paper is dedicated to solving this problem completely.

The outline is as follows: We recall refinable functions in Section 2. Section 3 is dedicated to introducing the polynomial equation under consideration and recalling univariate results from [6]. We determine the minimal total and minimal maximum degrees of a solution in Section 4. Conclusions are given in Section 5.

2 Refinable Functions

The standard approach for the construction of wavelets is based on a refinable function [psi], i.e., a solution of the refinement equation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] is a finitely supported sequence and M is a square integer matrix whose eigenvalues are bigger than one in modulus. For the further discussion, let us mention that, for a function f [member] L1 (Rd), its Fourier transform 7 used in this paper is defined to be [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. In order to choose p, one starts with a finitely supported sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] satisfying [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] 1. The symbol of the sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] is the trigonometric polynomial

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

The infinite product [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] then converges uniformly on compact sets, such that [psi] constitutes a compactly supported distributional solution of the refinement equation (1), normalized by 7(0) = 1, cf. [6]. One seeks well localized refinable functions and the smaller the size of the mask [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] the smaller the support of [psi], cf. [6]. To specify [psi]'s further properties by means of its symbol a, let F denote a complete set of representatives of ([M.sup.-T][Z.sup.d])/[Z.sup.d] with 0 [member of] [GAMMA]. It turns out that the cardinality of [GAMMA] is m := [absolute value of det(M)].

Recall that the total degree of a multivariate polynomial is the maximum over the sum of the exponents of the variables in any monomial term. The maximum degree of a multivariate polynomial, on the other hand, is the maximum over the maximum of the exponents of the variables in any monomial term.

We say that a satisfies the sum rules of order s if a has a zero of order s at [gamma], for all [gamma] [member of] [GAMMA]\{0}. Let sr(a) denote the maximal sum rule order of a. It is well known that [psi] reproduces polynomials of order sr(a), i.e., for any polynomial q on [R.sup.d] of total degree less than sr(a), there is a sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

If [psi] is used to construct orthonormal or biorthogonal wavelets, then the induced wavelets have sr(a) vanishing moments, which lead to a high approximation order of the system, cf. [14]. Therefore, we are interested in the construction of refinable functions with high sum rule order.

A refinable function is called fundamental if it is continuous and its integer shifts interpolate the integer grid, i.e., [psi](k) = [[delta].sub.k,0], for k [member of] [Z.sup.d]. This property is desirable because it leads to the following simple sampling formula: if a function f can be expressed as a linear combination of the integer shifts of [psi], then its coefficients are given by the sampling [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], i.e,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

A necessary condition is that [psi]'s symbol a is interpolatory, i.e.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2)

and this is also sufficient under reasonable additional assumption, cf. [16]. In summary, one seeks to construct interpolatory symbols a with high sum rule order and small mask size.

3 Interpolatory Symbols From Polynomial Equations

Given an interpolatory symbol a with sum rule order K, we aim to construct interpolatory symbol with increased sum rule order. Let [GAMMA] = [{[Y.sub.i]}.sup.m-1.sub.i=0] be again a complete set of representatives of ([M.sup.-T] [Z.sup.d])/[Z.sup.d] with [[gamma].sub.0] = 0 and denote [x.sub.i] := a([xi] + [Y.sub.i]) for i = 0,..., m - 1. We then seek, for fixed N [member of] N\{0}, a polynomial P such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (3)

is interpolatory in the sense of (2). Due to the factor [x.sup.N.sub.0], the new symbol [A.sub.N] satisfies the sum rules of order KN. To obtain a small support of the induced refinable function, we seek a polynomial P that has minimal degree. Let us formally state how much the support increases from a to [A.sub.N]:

Lemma 3.1. Let Q be a polynomial in m-1 variables with either total or maximum degree r. Let a be a symbol whose mask [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] satisfies 0 [member of] supp([a.sub.k]) [subset] C, where C is a convex and compact set. By applying [x.sub.i] = a(* + [y.sub.i]), for i = 0,...,m - 1, the support of the mask of the symbol Q([x.sub.1],..., [X.sub.m-1]) is contained in rC.

We omit the proof of Lemma 3.1 since it is straightforward.

Remark 3.2. To construct biorthogonal wavelets from an interpolatory refinable function [psi] with symbol a, one needs a second symbol b such that [bar.a([xi])b([xi])] is interpolatory. Equation (3) provides such a dual symbol by b (xi) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

For [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], the term a ([xi]+[gamma]) only depends on the equivalence class [gamma] + [Z.sup.d], but not on the choice of representatives. Hence, for i,j = 0,... ,m - 1, there is k(i,j) [member] {0,... ,m - 1} such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Recall that a is interpolatory and, hence, [x.sub.o] = 1 - [[SIGMA].sup.m-1.sub.i=1][x.sub.i]. We then seek a polynomial P that satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Since F is an additive group, we have [gamma] + [GAMMA] = [GAMMA], for any [gamma] [member] [GAMMA]. If we require P to be symmetric, then (4) reads as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (5)

where [[??].sup.i] means that [x.sub.i] is left out. For the remainder of the present paper, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

Equation (5) has already been considered in [6], for m = 2,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (6)

The Bezout polynomial

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (7)

is the unique solution to (6) with minimal degree, cf. [6]:

Theorem 3.3. The polynomial P is a solution to (6) iff

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (8)

where R is an arbitrary odd polynomial.

Provided that m = 2, the minimal degree of a solution to (5) is N - 1. Different methods for solving (5) for m > 2 have been derived in [8, 9, 13]. These approaches lead to polynomials P that have total degree (m - 1)(N - 1). So far, it was still an open question if this is the minimal total degree.

4 The Minimal Degree of Polynomial Solutions

Due to Lemma 3.1, we seek solutions with minimal total and minimal maximum degree. It seems possible, however, that these two types of degree could lead to different solutions of minimal degree:

Definition 4.1. For fixed N and m, we call a solution of (5) optimal if its maximum and total degrees are minimal, and its number of monomial terms is minimal among all solutions.

We shall identify, the minimal maximum and the minimal total degree. We also aim to specify optimal solutions. To get an idea about the minimal degree and the variation between different solutions, we first consider the underlying homogeneous equation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (9)

If P solves (5), then P + Q obviously solves (.5), too.

Example 4.2. For all k, g, r [member] N with r [less than or equal to] min {N + l, N + k}, the polynomial

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

is a solution of the homogeneous equation (9).

We omit the proof of Example 4.2 and rather discuss its consequences: Since the polynomial Q1,0,0 contains monomials [x.sup.N.sub.i], i = 1,..., m-l, there is no chance that coefficients of such monomials are uniquely determined in a solution to (5). But there is a chance that the coefficients of monomials [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], are uniquely determined. In fact, it turn out in the following section that the latter statement holds.

4.1 Minimal Degree and Optimal Solutions

The minimal degree of a solution to (5) in the univariate case m = 2 is N - 1. This is derived from Theorem 3.3 by choosing R [equivalent to] 0. The choice m > 2 leads to a multivariate polynomial equation. They are much harder due to the more complicated algebraic structure. While univariate polynomials are decomposable into linear factors, multivariate polynomials can generally not be written as a product of linear factors, and the zeros are never discrete. Thus, it is not obvious how to extend Theorem 3.3 to the multivariate setting, and it is rather surprising that there is an extension. The algebraic structure of a solution to (5) with m > 2 cannot directly be derived from following the lines in [6]. The required key idea is to evaluate a univariate polynomial at [x.sub.1] + ... + [X.sub.m-l]:

Theorem 4.3. Let the symmetric polynomial P be a solution of (5); then there are polynomials [R.sub.1], ..., [R.sub.m-1] such that P([X.sub.1], ..., [X.sub.m-1]) equals

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (11)

We shall make use of the following lemma:

Lemma 4.4. For a positive integer N and x [member] R satisfying [absolute valve of x] < 1, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (12)

The above lemma has been used in [6] to prove the univariate (m = 2) version of Theorem 4.3. The series is splitted at j = N - 1, and coefficients of univariate polynomials are then compared. We shall split the sum in a different way and replace x with [x.sub.1] + ... + [X.sub.m-l]:

Proof. We first split the series (12) at j = (m-1)(N-1) rather than at j = N-l:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

The key idea, which allows us to make rise of Equation (13) in the multivariate setting, is to replace the univariate variable x with the sum of variables [[sigma].sub.1] = [x.sub.1] + xxx + [x.sub.m-1]. We then obtain, for [[absolute value of [[sigma].sub.1]] < 1,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

We can now compare the coefficients on the right- and left-hand side. Each monomial with respect to the variables [x.sub.1],..., [x.sub.m-1] in the term

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

is at least for one i [member of] {1,..., m - 1} divisible by [x.sup.N.sub.i]. The monomial terms of P, which are not divisible by any of the monomials [x.sup.N.sub.1], ..., [x.sup.N.sub.m-1], must coincide with those in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Let R be

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Since P is a symmetric polynomial, R must also be a symmetric polynomial. Finally, each monomial in R is at least for one i [member of] {1,..., m - 1} divisible by [x.sup.N.sub.i]. Therefore, there are polynomials [R.sup.1], ..., [R.sub.m-1] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

which concludes the proof.

The following corollary is the main theoretical result of the present paper:

Corollary 4.5. For fixed N and m, the maximum degree of any solution P of (5) is at least N - 1, and its total degree is at least (m - 1)(N - 1). Moreover, there exists a unique optimal solution in the sense of Definition 3.1.

Proof. The monomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] in (11) occurs only in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

It is obvious that its coefficient is nonzero. Thus, any solution to (5) has maximum degree at least N - 1 and total degree at least (m - 1)(N - 1).

For given N and m, Lemma 3.6 in [9] provides a solution [??] of (5) whose maximum degree is N - 1, and its total degree is (m - 1)(N - 1). According to Theorem 4.3, the coefficients occuring with each monomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] are uniquely determined.

Remark 4.6. According to Corollary 4.5, the solutions to (5), which are derived in [8, 9, 13], have minimal total degree, and [9] provides the unique optimal solution.

In fact, the coefficient of the monomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (11) can easily be computed as follows: Applying [K.sub.j] := {([k.sub.1],..., [k.sub.m-l]) [member of] [N.sup.m-1]: [[SIGMA].sup.m-1.sub.i-1 [k.sub.i] = j]} yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and the monomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] then has the coefficient

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

which simplifies to (m(N-1))! / (N-1)!.sup.m].

To verify that the solutions to (5) with minimal total degree are generally not unique, for m > 2, we define the elementary symmetric polynomials:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

By using the Bezout polynomial [P.sub.N] in (7), we have the following example:

Example 4.7. For N = 3 and m = 3, the solution

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

from [8] is minimal with respect to the total degree. The solution

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

from [9, 13] is optimal, and we clearly have [A.sub.1] [??] [B.sub.1]. For N = 2 and m = 4, [8] yields that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

is a solution with minimal total degree. The optimal solution in [9, 13] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

which shows [A.sub.2] [??] [B.sub.2].

Remark 4.8. We have restricted our focus to the symmetric equation (5) only for notational conveniences. Essentially following the lines in Section 4.1 for the nonsymmetric equation (4) yields that any solution of (4), through not necessarily symmetric, has maximum degree at least N - 1 and total degree at least (m - 1)(N - 1).

5 Conclusions

We have analyzed a multivariate polynomial equation that is used to construct refinable functions providing favorable sampling formulas. A polynomial solution's total and maximum degrees provide upper bounds on the size of the refinable function's support. We were able to specify the minimal total and the minimal maximum degree of a solution. Moreover, we have verifed that the Lemma 3.6 in [9] provides the unique solution that satisfies both: it has a minimal total and a minimal maximum degree.

Methods and results in [11, 12] suggest that there are constructions of refinable functions that outperform the known solutions to polynomial equations. These methods provide scaling functions with similar properties but smaller support. Our result reveals intrinsic limitations of the polynomial construction method. It, hence, supports alternative approaches such as those in [11, 12] when constructing refinable functions.

References

[1] A. S. Cavaretta, W. Dahmen, and C. A. Micchelli. Stationary subdivision. Mem. Amer. Math. Soc., 93, 1 186, 1991.

[2] C. K. Chui, W. He, and J. Stockler. Compactly supported tight and sibling frames with maximum vanishing moments. Appl. Comput. Harmon. Anal., 13, 224-262, 2002.

[3] C. K. Chui and C. Li. A general framework of multivariate wavelets with duals. Appl. Comput. Harmon. Anal., 1, 368-390, 1994.

[4] S. Dahlke, K. Grochenig, and P. Maass. A new approach to interpolating scaling functions. Appl. Anal., 72, 485-500, 1999.

[5] S. Dahlke and P. Maass. Interpolating refinable functions and wavelets for general scaling matrices. Numer. Funct. Anal. Optim., 18(5&6), 521-539, 1997.

[6] I. Daubechies. Ten Lectures on Wavelets, volume 9. SIAM, Philadelphia, 1992. CBMS-NSF Regional Conf. Ser. in Appl. Math. 61.

[7] I. Daubechies, B. Han, A. Ron, and Z. Shen. Framelets: MRA-based constructions of wavelet frames. Appl. Comput. Hawnon. Anal., 14(1), 1-46, 2003.

[8] J. Derado. Multivariate refinable interpolating functions. Appl. Cornput. Harmon. Anal., 7, 165-183, 1999.

[9] B. Han. On dual wavelet tight frames. Appl. Comput. Harmon. Anal., 4(4), 380-413, October 1997.

[10] B. Han and R. Q. Jia. Optimal interpolatory subdivision schemes in multidimensional spaces. SIAM Y. Numer. Anal., 36(1), 105-124, 1998.

[11] B. Han and R. Q. Jia. Quincunx fundamental refinable functions and quincunx biorthogonal wavelets. Math. Comp., 71(237), 165-196, 2002.

[12] B. Han and S. D. Riemenschneider. Interpolatory biorthogonal wavelets and CBC algorithm. In International Conference on Wavelet Analysis and Its Applications, AMS/IP Studies in Advanced Mathematics, volume 25, pages 119-138, 2002.

[13] H. Ji, S. D. Riemenschneider, and Z. Shen. Multivariate compactly supported fundamental refinable functions, duals and biorthogonal wavelets. Stud. Appl. Math., 102, 173-204, 1999.

[14] R. Q. Jia. Approximation properties of multivariate wavelets. Math. Comp., 67, 647-665, 1998.

[15] R. Q. Jia and C. A. Micchelli. Using the refinement equation for the construction of pre-wavelets II: powers of two. In P. J. Laurent, A. Le M6haut6, and L. L. Schumaker, editors, Papers from the International Conference on Curves and Surfaces, pages 209-246, 1991.

[16] W. Law-ton, S. L. Lee, and Z. Shen. Stability and orthonormality of multivariate refinable functions. SIAM d. Math. Anal., 28(4), 999-1014, 1997.

[17] S. D. Riemenschneider and Z. Shen. Multidimensional interpolatory subdivision schemes. SIAM d. Numer. Anal., 34, 2357-2381, 1997.

[18] I. W. Selesnick and A. F. Abdelnour. Symmetric wavelet tight frames with two generators. AppL Comput. Harmon. Anal., 17'(2)i 211 225, 2004.

M. Ehler

University of Maryland, Department of Mathematics

Norbert Wiener Center for Harmonic Analysis and Applications

College Park. MD 20742

ehlermar@math.umd.edu