The Discrete Analog of the Malgrange-Ehrenpreis Theorem

Doron ZEILBERGER^{1}

In fond memory of Leon Ehrenpreis

Abstract One of the landmarks of the modern theory of partial differential equations is the Malgrange-Ehrenpreis theorem that states that every non-zero linear partial differential operator with constant coefficients has a Green function (alias fundamental solution). In this short note I state the discrete analog, and give two proofs. The first one is Ehrenpreis- style, using duality, and the second one is constructive, using formal Laurent series.

Key Words Formal Laurent Series • systems of constant-coefficient partial differential equations • fundamental solution

Mathematics Subject Classification (2010): 35E05 (Primary), 39A06 (Secondary)

One of the landmarks of the modern theory of partial differential equations is the Malgrange-Ehrenpreis[E1][E2][M] theorem (see [Wi]) that states that every non-zero linear partial differential operator with constant coefficients has a Green’s function (alias fundamental solution). Recently Wagner[W] gave an elegant constructive proof.

In this short note I will state the discrete analog, and give two proofs. The first one is Ehrenpreisstyle, using duality, and the second one is constructive, using formal Laurent series.

Let Z be the set of integers, and n a positive integer. Consider functions f(m_{1}, …, m_{n}) from Z^{n} to the complex numbers (or any field). A linear partial difference operator with constant coefficients P is anything of the form

Pf(m_{1}, …, m_{n}) := ∑_{α∈A} c_{α}f(m_{1} + α_{1}, …, m_{n} + α_{n}) ,

where A is a finite subset of Z^{n} and α = (α_{1}, …, α_{n}), and the c_{α} are constants.

For example, the discrete Laplace operator in two dimensions:

f(m_{1}, m_{2}) → f(m_{1}, m_{2}) − \frac{1}{4}(f(m_{1} + 1, m_{2}) + f(m_{1} − 1, m_{2}) + f(m_{1}, m_{2} + 1) + f(m_{1}, m_{2} − 1)) .

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg/ . First version: July 21, 2011. This version: Sept. 7, 2011. I’d like to thank an anonymous referee, and Hershel Farkas, for insightful comments. Accompanied by Maple package LEON available from http://www.math.rutgers.edu/~zeilberg/tokhniot/LEON . Supported in part by the USA National Science Foundation.

The symbol of the operator P is the Laurent polynomial

P (z_{1}, …, z_{n}) = ∑_{α∈A} c_{α}z_{1}^{α_{1}} ⋯ z_{n}^{α_{n}} .

The discrete delta function is defined in the obvious way

δ(m_{1}, …, m_{n}) = \{ \begin{matrix}1, & if (m_{1}, …, m_{n}) = (0, 0, …, 0); \\ 0, & otherwise. \end{matrix}

Note that the beauty of the discrete world is that the delta function is a genuine function, not a “generalized” one, and one does not need the intimidating edifice of Schwartzian distributions.

We are now ready to state the

Discrete Malgrange-Ehrenpreis Theorem: Let P be any non-zero linear partial difference operator with constant coefficients. There exists a function f(m_{1}, …, m_{n}) defined on Z^{n} such that

Pf(m_{1}, …, m_{n}) = δ(m_{1}, …, m_{n}) .

First Proof (Ehrenpreis-style) Consider the infinite-dimensional vector space, C[z_{1}, …, z_{n}, z_{1}^{−1}, …, z_{n}^{−1}], of all Laurent polynomials in z_{1}, …, z_{n}. Every function f on Z^{n} uniquely defines a linear functional T_{f} defined on monomials by

T_{f} [ z_{1}^{m_{1}} ⋯ z_{n}^{m_{n}} ] := f(m_{1}, …, m_{n}) ,

and extended by linearity. Conversely, any linear functional gives rise to a function on Z^{n}. Let P (z_{1}, …, z_{n}) be the symbol of the operator P. We are looking for a linear functional T such that for every monomial z_{1}^{m_{1}} ⋯ z_{n}^{m_{n}}

T [ P (z_{1}, …, z_{n})z_{1}^{m_{1}} ⋯ z_{n}^{m_{n}} ] = T_{δ}(z_{1}^{m_{1}} ⋯ z_{n}^{m_{n}}) .

By linearity, for any Laurent polynomial a(z_{1}, …, z_{n})

T [ P (z_{1}, …, z_{n})a(z_{1}, …, z_{n}) ] = T_{δ}(a(z_{1}, …, z_{n})) .

So T is defined on the (vector) subspace P (z_{1}, …, z_{n})C[z_{1}, …, z_{n}, z_{1}^{−1}, …, z_{n}^{−1}] of C[z_{1}, …, z_{n}, z_{1}^{−1}, …, z_{n}^{−1}]. By elementary linear algebra, every linear functional on the former can be extended (in many ways!) to the latter. QED.

Before embarking on the second proof we have to recall the notion of formal power series, and more generally, formal Laurent series.

A formal power series in one variable z is any creature of the form

∑_{i=0}^{∞} a_{i}z^{i} .

More generally, a positive formal Laurent series is any creature of the form

∑_{i=m}^{∞} a_{i}z^{i} ,

where m is a (possibly negative) integer. On the other hand a negative formal Laurent series is any creature of the form

∑_{i=−∞}^{m} a_{i}z^{i} ,

where m is a (possibly positive) integer.

A bilateral formal Laurent series goes both ways

∑_{i=−∞}^{∞} a_{i}z^{i} .

Note that the class of bilateral formal Laurent series is an abelian additive group, but one can’t multiply there. On the other hand one can legally multiply two positive formal Laurent series by each other, and two negative formal Laurent series by each other, but don’t mix them! Of course it is always legal to multiply any Laurent polynomial by any bilateral formal power series. But watch out for zero-divisors, e.g.

(1 − z) ∑_{i=−∞}^{∞} z^{i} = 0 .

Any Laurent polynomial p(z) = a_{i}z^{i} + … a_{j}z^{j} of low-degree i and (high-)degree j in z (so a_{i} ≠ 0, a_{j} ≠ 0) has two natural multiplicative inverses. One in the ring of positive Laurent polynomials, and the other in the ring of negative Laurent polynomials. Simply write p(z) = z^{i}a_{i}p_{0}(z) and get 1/p(z) = z^{−i}(1/a_{i})p_{0}(z)^{−1}, and writing p_{0}(z) = 1 + q_{0}(z), we form

p_{0}(z)^{−1} = (1 + q_{0}(z))^{−1} = ∑_{i=0}^{∞}(−1)^{i}q_{0}(z)^{i} ,

and this makes perfect sense and converges in the ring of formal power series. Analogously one can form a multiplicative inverse in powers in z^{−1}.

It follows that every rational function P (z)/Q(z) in one variable, z, has two natural inverses, one pointing positively, one negatively.

What about a rational function of several variables, P (z_{1}, …, z_{n})/Q(z_{1}, …, z_{n})? Here we can form 2^{n}n! natural inverses. There are n! ways to order the variables, and for each of these one can decide whether to do the positive-pointing inverse or the negative-pointing one. At each stage we get a one-sided formal Laurent series whose coefficients are rational functions of the remaining variables, and one just keeps going.

Second Proof (Constructive): To every discrete function f(m_{1}, …, m_{n}) associate the bilateral formal Laurent series

∑_{(m_{1},...,m_{n})∈Z^{n}} f(m_{1}, …, m_{n})z_{1}^{m_{1}} ⋯ z_{n}^{m_{n}} .

We need to “solve” the equation

P (z_{1}^{−1}, …, z_{n}^{−1}) ( ∑_{(m_{1},...,m_{n})∈Z^{n}} f(m_{1}, …, m_{n})z_{1}^{m_{1}} ⋯ z_{n}^{m_{n}} ) = 1 .

So “explicitly”

∑_{(m_{1},...,m_{n})∈Z^{n}} f(m_{1}, …, m_{n})z_{1}^{m_{1}} ⋯ z_{n}^{m_{n}} = 1/P (z_{1}^{−1}, …, z_{n}^{−1}) ,

and we just described how to do it in 2^{n}n! ways.

The Maple package LEON

This article is accompanied by a Maple package LEON. One of its numerous procedures is FS, that implements the above constructive proof. LEON can also compute polynomial bases to solutions of linear partial difference equations with constant coefficients, compute Hilbert Series for spaces of solutions of systems of linear differential equations, as well as find “multiplicity varieties” ( in the style of Ehrenpreis ) when they are zero-dimensional.

Leon Ehrenpreis (1930-2010): a truly FUNDAMENTAL Mathematician (a Videotaped lecture)

I strongly urge readers to watch my lecture, available in six parts from YouTube, and in two parts from Vimeo, see:

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/leon.html .

That page contains links to both versions, as well as numerous input and output files for the Maple package LEON.

References

[E1] Leon Ehrenpreis, Solution of some problems of division. I. Division by a polynomial of derivation, Amer. J. Math. 76(1954), 883-903.

[E2] Leon Ehrenpreis, Solution of some problems of division. II. Division by a punctual distribution, Amer. J. Math. 77(1955), 286-292.

[M] Bernard Malgrange, Existence et approximation des solutions des équations aux dérivées partielles et des équations de convolution, Ann. Inst. Fourier, Grenoble 6(1955-1956): 271-355.

[W] Peter Wagner, A new constructive proof of the Malgrange-Ehrenpreis theorem, Amer. Math. Monthly 116(2009), 457-462.

[Wi] Wikipedia,the free Encyclopedia, Malgrange-Ehrenpreis Theorem, Retrieved 16:10, July 21, 2011,