From: Boudewijn Moonen Subject: Re: Inverse calculation Date: Tue, 07 Sep 1999 11:39:30 +0200 Newsgroups: sci.math To: dlan@oce.nlGroetjes Keywords: inverting a discrete convolution Dave Langers wrote: > > A practical problem, at least for me: > > Given some function f(x), the function g(x) is calculated as follows: > g(x) = 4/pi * [ f(x) - f(3x)/3 + f(5x)/5 - f(7x)/7 + ... ] > > For example: > if f(x)=a^x then g(x)=4/pi*arctan(a^x) (00) > > Now the problem is: > Given g(x), how can f(x) be found? > > I don't believe there is a solution in general, so I will shrink it down > to: > Given g(x)=a^x, what is f(x)? > > Solutions anyone? > > As a background: this has something to do with optical transfer > functions in physics, Fourier theory in mathematics. > > Groetjes, > Dave Langers. > _______________________________ > / _\ \ > | \ | " I think that God, | > \_/_| in creating man, | > | somewhat overestimated | > / his ability. " / > | | > | (Oscar Wilde) | > | _________________________|___ > \_/____________________________/ A) There is, in fact, a solution for general g, not just for the special choice you made. The following considerations will be formal. Suppose you have some f and define g as g(x) := sum_{n >=1} b_n f(nx) (1) where b_1, b_2, ..., is any sequence of real or complex numbers and you want to express f in terms of g. Make the ansatz f(x) = sum_{m >=1} a_m g(mx) (2) Plugging (2) into (1) yields g(x) = sum_{m,n>=1} a_m b_n f(mnx) = sum_{n>=1} (sum_{d|n} a_d b_{n/d}) g(nx) =: sum_{n>=1} c_n g(nx) So we require c_1 = 1 , c_n = 0 for n >=2 . But these requirements can be easily met iff b_1 <> 0: put recursively a_1 := 1/b_1 (3a) a_n := - sum_{d|n, d<>n} a_d b_{n/d} (3b) and you are done. B) What is behind this shenanigan? Well, a standard method of elementary number theory. Consider a set M of any symbols D_n, n = 1, 2, ... behaving multiplicatively: D_m D_n = D_{mn} , (4) i.e. M is just the multiplicative monoid of the natural numbers. Let F be the vector space of formal linear combinations sum_m a_m D_m of elements in M with real or complex coefficients. Then F becomes a ring under termwise addition and multiplication defined by bilinearity using the multiplicative rule (4): (sum_m a_m D_m)(sum_n b_n D_n) := sum_{m,n} a_m b_n D_{mn} (5) = sum_n (sum_{d|n} a_d b_{n/d}) D_n The units in the ring are just the b = sum_n b_n D_n with b_1 <> 0, the inverse of b being a = sum_m a_m D_m with the a_m by the recursion (3a), (3b). This ring can also be viewed as the space S of sequences a = (a_1, a_2, ....) under termwise addition and the "convolution product" (a*b)_n := sum_{d|n} a_d b_{n/d} with unit (1, 0, 0, ...). The rings F resp. S are often called the space of "number theoretic functions". So if we put a := sum_m a_m D_m and b := sum_n b_n D_n, the solution to your original problem posed by (1), (2) is just given by inverting b in the ring F, i.e. by solving the equation a b = 1 in F, or just solving the convolution equation (a_1, a_2, ...)*(b_1, b_2, ..) = (1, 0, 0, ..) in S. C) How is this related to the somewhat condensed solution of David Petry? This goes under the heading of "Dirichlet generating functions" (see e.g. the classic of Hardy and Wright, Introduction to Number Theory). Note that in B) we could make any choice of multiplicative symbols D_m to encode the natural numbers multiplicatively. David chooses firstly D_m as the operator mapping f to D_m f given by (D_m f)(x) := f(mx) and then D_m := m^s, s anything you like; let us now take the more standard choice D_m := m^{-s}. So we encode any sequence (a_1, a_2, ...) by its "Dirichlet generating function" a := sum_{m>=1} a_m m^{-s} Then the convolution product of sequences just corresponds to the usual product of Dirichlet series. Now to your case b_n = 0, n even, b_n = (-1)^k for n = 2k+1. Then b becomes a famous Dirichlet L-series: b = sum_n b_n n^{-s} = 1 - 3/3^{-s} + 1/5^{-s} - ... = L(chi,s) with chi(n) = b_n a Dirichlet charakter. Therefore, it has an Euler product representation: L(chi,s) = product_{p prime, p>2} 1/(1 - chi(p) p^{-s}) Therefore, the equation a b = 1 is readily solved: a is just the multiplicative inverse of L(chi,s): a = L(chi,s)^{-1} = product_{p prime, p>2} (1 - chi(p) p^{-s}) (6) But now the "Moebius function" mu comes to the rescue. Recall it is defined as follows. Decompose any natural number uniquely into its prime factors: n = p_1^{e_1} ... p_r^{e_r} , e_r >= 1 . Then mu(1) := 1 mu(n) := (-1)^r if all e_r = 1 mu(n) := 0 else So mu(n) = 0 if n is not square-free, i.e. is divided by the square of a prime number. This yields 1-chi(p) p^{-s} = 1 + mu(p) chi(p) p^{-s} + mu(2p) chi(2p) p^{-2s} + ... and plugging this into (6) gives a = sum_{n odd} mu(n) chi(n) n^{-s} , hence the explicit formula for the a_n given by David. Groetjes, -- Boudewijn Moonen Institut fuer Photogrammetrie der Universitaet Bonn Nussallee 15 D-53115 Bonn GERMANY e-mail: Boudewijn.Moonen@ipb.uni-bonn.de Tel.: GERMANY +49-228-732910 Fax.: GERMANY +49-228-732712 ============================================================================== From: Boudewijn Moonen Subject: Re: Inverse calculation Date: Tue, 07 Sep 1999 13:16:47 +0200 Newsgroups: sci.math Boudewijn Moonen wrote: -------------->oo big snip > > Now to your case b_n = 0, n even, b_n = (-1)^k for n = 2k+1. Then b > becomes a famous Dirichlet L-series: > > b = sum_n b_n n^{-s} = 1 - 3/3^{-s} + 1/5^{-s} - ... > > = L(chi,s) > > with chi(n) = b_n a Dirichlet charakter. > Oops. I either should have written b = sum_n b_n n^{-s} = 1 - 3/3^{-s} + 5/5^{-s} - ... = L(chi,s-1) or b = sum_n b_n n^{-s} = 1 - 1/3^{-s+1} + 1/5^{-s+1} - ... = L(chi,s-1) But luckily, s could be anything, so just replace it with s+1 and consider b = sum_n b_n n^{-s} = 1 - 1/3^{-s} + 1/5^{-s} - ... = L(chi,s) which is what I wanted to write... -- Boudewijn Moonen Institut fuer Photogrammetrie der Universitaet Bonn Nussallee 15 D-53115 Bonn GERMANY e-mail: Boudewijn.Moonen@ipb.uni-bonn.de Tel.: GERMANY +49-228-732910 Fax.: GERMANY +49-228-732712