# Dirichlet Characters, Gauss Sums, and Inverse Z Transform

Authors: Jing Gao; Huaning Liu
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

A generalized Möbius transform is presented. It is based on Dirichlet characters. A general algorithm is developed to compute the inverseZ transform on the unit circle, and an error estimate is given for the truncated series representation.


---

## Body

## 1. Introduction

We consider a causal, linear, time-invariant system with an infinite impulse response{cj}j=1∞. The system is assumed to be stable and the Z transform X(z)=∑j=1∞cjz-j is convergent for |z|>r, where r<1. The frequency response of the system is obtained by evaluating the Z transform on the unit circle.The arithmetic Fourier transform (AFT) offers a convenient method, based on the construction of weighted averages, to calculate the Fourier coefficients of a periodic function. It was discovered by Bruns [1] at the beginning of the last century. Similar algorithms were studied by Wintner [2] and Sadasiv [3] for the calculation of the Fourier coefficients of even periodic functions. This method was extended in [4] to calculate the Fourier coefficients of both the even and odd components of a periodic function. The Bruns approach was incorporated in [5] resulting in a more computationally balanced algorithm. In [6, 7], Knockaert presented the theory of the generalized Möbius transform and gave a general formulation.In [8], Schiff et al. applied Wintner's algorithm for the computation of the inverse Z-transform of an infinite causal sequence. Hsu et al. [9] applied two special Möbius inversion formulae to the inverse Z-transform.The transform pairs play a central part in the arithmetic Fourier transform and inverseZ-transform. In this paper, based on Dirichlet characters, we presented a generalized Möbius transform of which all the transform pairs used in the mentioned papers are the special cases. A general algorithm was developed in Section 2 to compute the inverse Z transform on the unit circle. The algorithm computes each term cj of the infinite impulse response from sampled values of the Z transform taken at a countable set of points on the unit circle. An error estimate is given in Section 3 for the truncated series representation. A numerical example is given in Section 4. Number theory and Dirichlet characters [10] play an important role in the paper.


## 2. The Algorithm

According to the Möbius inversion formula for finite series [4], if n is a positive integer and f(n), g(n) are two number-theoretic functions, then(2.1)g(n)=∑k=1[N/n]f(kn)ifff(n)=∑m=1[N/n]μ(m)g(mn),
where [y] denotes the integer part of real number y and μ(n) is the Möbius function:(2.2)μ(n)={1ifn=1,(-1)rifnincludesrdistinctprimefactors,0,otherwise.
Knockaert [6] extended the Möbius inversion formula and proved the following proposition.Proposition 2.1.
Letf1,f2,… be a sequence of real numbers and α(n),β(n) two arithmetical functions. For the transform pair
(2.3)sn=∑k=1∞α(k)fkn,fn=∑k=1∞β(k)skn
to be valid for all sequences fn, it is necessary and sufficient that
(2.4)∑kl=mα(k)β(l)=∑k∣mα(k)β(mk)=δ1m={1,m=1,0,m≠1.LetG be the group of reduced residue classes modulo q. Corresponding to each character f of G, we define an arithmetical function χ=χf as follows:(2.5)χ(n)=f(n̂)if(n,q)=1,χ(n)=0if(n,q)>1,
where n̂={x:x≡n(modq)} and (a,b) denotes the greatest common divisor of a and b.The functionχ is called a Dirichlet character modulo q. The principal character χ1 is that which has the properties(2.6)χ1(n)={1if(n,q)=1,0if(n,q)>1.Ifq≥1, the Euler’s totient ϕ(q) is defined to be the number of positive integers not exceeding q that are relatively prime to q. There are ϕ(q) distinct Dirichlet characters modulo q, each of which is completely multiplicative and periodic with period q. That is, we have(2.7)χ(mn)=χ(m)χ(n)∀m,n,(2.8)χ(n+q)=χ(n)∀n.
Conversely, if χ is completely multiplicative and periodic with period q, and if χ(n)=0 if (n,q)>1, then χ is one of the Dirichlet characters modulo q.Letf(n) be an arithmetical function. Series of the form ∑n=1∞f(n)/nsare called Dirichlet series with coefficients f(n). If f(n)=χ(n), then the series are called Dirichlet L-functions. For any Dirichlet character χmodq, the sum(2.9)G(n,χ)=∑m=1qχ(m)e2πimn/q
is called the Gauss sums associated with χ. If χ=χ1, then the Gauss sums reduce to Ramanujan's sum(2.10)G(n,χ1)=∑m=1q(m,q)=1e2πimn/q=cq(n).
See [10].Letχ be a Dirichlet character modulo q. We have(2.11)∑k|mχ(k)μ(mk)χ(mk)=χ(m)∑k∣mμ(mk)=δ1m.
In this way, we have defined a generalized Möbius transform pair.Lemma 2.2.
Letχ be a Dirichlet character modulo q; then transform pair
(2.12)sn=∑k=1∞χ(k)fkn,fn=∑k=1∞μ(k)χ(k)skn
is valid for all q.Remarks 1.
The transform pairs play a central part in the arithmetic Fourier transform and inverseZ-transform. It is not hard to show that all the transform pairs used in the mentioned papers are the special cases of our generalized Möbius transform. In fact,(a)
letq=1 in Lemma 2.2; we have
(2.13)sn=∑k=1[N/n]fkn,fn=∑k=1[N/n]μ(k)skn,
which is Theorem  3 in [4] and Lemma  1 in [8];(b)
letq=2α and χ=χ1 in Lemma 2.2, where α≥1 is a positive integer; we have
(2.14)sn=∑k=1,3,5,…[N/n]fkn,fn=∑k=1,3,5,…[N/n]μ(k)skn,
which is Case  1 of Lemma  1 in [9];(c)
letq=2α, α≥2, and
(2.15)χ2(k)={(-1)(k-1)/2if(k,q)=1,0if(k,q)>1
in Lemma 2.2, then χ2 is one of the Dirichlet characters modulo q since χ2(k) is completely multiplicative and periodic with period q. We have
(2.16)sn=∑k=1,3,5,…[N/n]fkn(-1)(k-1)/2,fn=∑k=1,3,5,…[N/n]μ(k)skn(-1)(k-1)/2,
which is Case  2 of Lemma  1 in [9];(d)
letχ=χ1 in Lemma 2.2; we have
(2.17)sn=∑(k,q)=1fkn,fn=∑(k,q)=1μ(k)skn,
which is transform pair I of Theorem  4 in [7];(e)
letq=4,pα or 2pα, and χ3(k)=(k/q) in Lemma 2.2, where p is an odd prime, α≥1, and (k/q) is the Legendre's symbol defined as follows:(2.18)(kq)={1if(k,q)=1andnisaquadraticresiduemod⁡q,-1if(k,q)=1andnisnotaquadraticresiduemod⁡q,0if(k,q)>1.
From [10], we know that q admits a primitive root and (k/q)=(-1)ind(k). We have
(2.19)sn=∑(k,q)=1(-1)ind(k)fkn,fn=∑(k,q)=1μ(k)(-1)ind(k)skn,
which is transform pair II of Theorem  4 in [7].
From these facts, we claim that Lemma2.2 is actually an important extension on the Möbius inversion formula. In practice, we can choose the best possible transform pair.We do not discuss the convergence of the transform pair since in practice it is used only on a truncated series. Next we establish our main theorem.Theorem 2.3.
LetX(z)=∑j=1∞cjz-j be convergent for |z|>r, where r<1. For any fixed q≥1 and Dirichlet character χ modulo q, the coefficients are given by
(2.20)cn=1qn∑k=1∞μ(k)χ(k)k∑r=1qG(r,χ)∑l=1knX(e(2πi/kn)(l+r/q)).Proof.
On|z|=1, let us write X(θ)=X(eiθ)=∑j=1∞cje-ijθ.
Define(2.21)sn=1q∑r=1qG(r,χ)[1n∑l=1nX(e(2πi/n)(l+r/q))].
Note that for a positive integerk(2.22)1n∑m=1ne2πikm/n={1ifndividesk,0ifndoesnotdividek,
we have
(2.23)sn=1q∑r=1qG(r,χ)[1n∑l=1nX(e(2πi/n)(l+r/q))]=1q∑r=1qG(r,χ)[1n∑l=1n∑j=1∞cje-2πij(l+r/q)/n]=1q∑r=1qG(r,χ)[1n∑j=1∞cj∑l=1ne-2πijl/ne-2πijr/nq]=1q∑r=1qG(r,χ)∑l=1∞clne-2πilr/q.
Let l=qk+s; then
(2.24)sn=1q∑r=1qG(r,χ)∑k=0∞∑s=1qcn(qk+s)e-2πisr/q=1q∑k=0∞∑s=1qcn(qk+s)∑m=1qχ(m)∑r=1qe2πir(m-s)/q.
Note that 1≤m,s≤q,  so q∣(m-s) if and only if m=s; therefore,
(2.25)sn=∑k=0∞∑s=1qχ(s)cn(qk+s)=∑t=1∞χ(t)cnt.
By Lemma 2.2, we have
(2.26)cn=∑k=1∞μ(k)χ(k)snk=1qn∑k=1∞μ(k)χ(k)k∑r=1qG(r,χ)∑l=1knX(e(2πi/kn)(l+r/q)).
This completes the proof of Theorem 2.3.Remarks 2.
Letq=1 in Theorem 2.3; we have
(2.27)cn=∑k=1∞μ(k)kn∑l=1knX(e(2πi/kn)(l+1)),
which is the theorem in [8].
Letq=2 in Theorem 2.3 or q=4 and χ=χ1 in Theorem 2.3; we easily have
(2.28)cn=∑k=1,3,5,…∞μ(k)2kn[∑l=1knX(e(2πi/kn)(l+1))-∑l=1knX(e(2πi/kn)(l+1/2))].
Letq=4 and χ=χ2 in Theorem 2.3; we have
(2.29)cn=∑k=1,3,5,…∞μ(k)(-1)(k-1)/2i2kn[∑l=1knX(e(2πi/kn)(l+1/4))-∑l=1knX(e(2πi/kn)(l+3/4))].In practice, a large number of coefficientscn may be calculated. We suppose that a truncation is employed. Next we estimate the error due to the truncation of the series.


## 3. Error Estimate

In order to estimate the error due to truncation of the series representation of the coefficientscn, we require the following lemma.Lemma 3.1.
Iff is a function of period 2π, with f′∈Lip1([0,2π]), then
(3.1)|∫02πf(θ)dθ-1n∑m=1nf(θ+2πmn)|≤Cn2,
uniformly in θ, where C is the Lipschitz constant.Proof.
This is Lemma  3 of [8].TakingX(z) as in Theorem 2.3, we maintain the following theorem.Theorem 3.2.
The truncation error satisfies(3.2)|cn-1qn∑k=1Nμ(k)χ(k)k∑r=1qG(r,χ)∑l=1knX(e(2πi/kn)(l+r/q))|≤Cϕ(q)n2N,
where C is the Lipschitz constant.Proof.
Note that we have(3.3)0=c0=12π∫02πX(eiφ)dφ.
Moreover,X′∈Lip1([0,2π]) by the analyticity of X. By Theorem 2.3 and Lemma 3.1, we have
(3.4)|cn-1qn∑k=1Nμ(k)χ(k)k∑r=1qG(r,χ)∑l=1knX(e(2πi/kn)(l+r/q))|=|1qn∑k=N+1∞μ(k)χ(k)k∑r=1qG(r,χ)∑l=1knX(e(2πi/kn)(l+r/q))|≤|1q∑k=N+1∞μ(k)χ(k)∑r=1qG(r,χ)Cn2k2|≤Cϕ(q)n2∑k=N+1∞1k2≤Cϕ(q)n2N.
This completes the proof of Theorem3.2.


## 4. An Example

Consider the function(4.1)X(z)=e1/z+1z-1/2-1,|z|>12.
The few first coefficients are c1=2, c2=1, and c3=5/12. Employing formulae (2.27), (2.28), and (2.29), we obtain the results given in Tables 1, 2, and 3. The results show that formulae (2.28) and (2.29) is quite more accurate than formula (2.27). Choosing carefully the modulo q and the Dirichlet character, we will greatly improve the algorithm.Table 1
Calculation of theZ-transform coefficients of the function: X(z)=e1/z+1/(z-1/2)-1,q=1.
kc1c2c313.718281828+0.000000720i1.209747301+0.000000338i0.453772595+0.000000199i22.508534526+0.000000381i1.034722511+0.000000208i0.420637706+0.000000128i32.054761931+0.000000182i1.001587622+0.000000138i0.416721106+0.000000087i42.054761931+0.000000182i1.001587622+0.000000138i0.416721106+0.000000087i51.981912218+0.000000089i0.999632365+0.000000100i0.416660127+0.000000062i62.015047107+0.000000160i1.000120712+0.000000131i0.416667696+0.000000082i71.999100704+0.000000103i0.999998692+0.000000105i0.416666804+0.000000065i81.999100704+0.000000103i0.999998692+0.000000105i0.416666804+0.000000065i91.999100704+0.000000103i0.999998692+0.000000105i0.416666804+0.000000065i102.001055961+0.000000140i1.000000538+0.000000123i0.416666743+0.000000077iTable 2
Calculation of theZ-transform coefficients of the function: X(z)=e1/z+1/(z-1/2)-1,q=2,q=4,orχ=χ1.
kc1c2c312.508534526+0.000000785i1.034722484+0.000000226i0.420637664+0.000000130i32.087896862+0.000000654i1.002075958+0.000000213i0.416728633+0.000000129i52.017002434+0.000000624i1.000122546+0.000000212i0.416667589+0.000000126i72.001178059+0.000000618i1.000000467+0.000000209i0.416666630+0.000000121i92.001178059+0.000000618i1.000000467+0.000000209i0.416666630+0.000000121i112.000201462+0.000000617i0.999999985+0.000000205i0.416666627+0.000000117i131.999957311+0.000000615i0.999999950+0.000000200i0.416666625+0.000000113i152.000018355+0.000000618i0.999999956+0.000000204i0.416666626+0.000000117i172.000003089+0.000000614i0.999999953+0.000000200i0.416666625+0.000000114i191.999999268+0.000000610i0.999999951+0.000000196i0.416666624+0.000000111iTable 3
Calculation of theZ-transform coefficients of the function: X(z)=e1/z+1/(z-1/2)-1,q=4,andχ=χ2.
kc1c2c311.641470945+0.000000164i0.969199603+0.000000195i0.412817735+0.000000128i32.054288680+0.000000292i1.001830856+0.000000204i0.416726726+0.000000119i51.983516336+0.000000263i0.999877456+0.000000214i0.416665686+0.000000128i71.999338790+0.000000262i0.999999531+0.000000205i0.416666645+0.000000122i91.999338790+0.000000262i0.999999531+0.000000205i0.416666645+0.000000122i112.000315379+0.000000252i1.000000013+0.000000200i0.416666650+0.000000120i132.000071234+0.000000261i0.999999978+0.000000204i0.416666646+0.000000122i152.000010194+0.000000270i0.999999971+0.000000207i0.416666642+0.000000123i171.999994930+0.000000277i0.999999967+0.000000209i0.416666639+0.000000124i191.999998750+0.000000271i0.999999971+0.000000208i0.416666642+0.000000123i


## 5. Conclusion

A general algorithm offers a general way to compute the inverseZ transform. It is based on generalized Möbius transform, Dirichlet characters, and Gauss sums. The algorithm computes each term cj of the infinite impulse response from sampled values of the Z transform taken at a countable set of points on the unit circle. An error estimate and a numerical example are given for the truncated series representation. Choosing carefully the modulo q and the Dirichlet character we will greatly improve the algorithm. But this is not exhaustive. Dirichlet characters and Gauss sums play an important role in number theory, and there are so many methods and results associated with them. Any development on the Dirichlet character and Gauss sums may be applied to the inverse Z transform.



---

*Source: 821949-2012-03-18.xml*