Harmonic Analysis On

Harmonic Analysis on Zn

Tomomi Haynes

Math 4495

Dr. Derado

December 14, 2005

Harmonic analysis is the branch of mathematics which studies the representation of functions or signals as the superposition of basic waves. It investigates and generalizes the notions of Fourier series and Fourier transforms. Also, the basic waves are called “harmonics”, hence the name “harmonic analysis.”

Since the name of the field is taken after the great French mathematician Jean Baptiste Joseph Fourier, one may think that the area of study was developed mainly by him. However, nothing is farther from the case. Fourier may be theprominent figure who is directly responsible for the development of Harmonic Analysis in the last two centuries, but he owes his achievements to the mathematicians before him. When describing his achievement in physics and astronomy, Newton once dedicated his achievement to Galileo and Kepler by noting, “If I have seen further [than certain other men] it is by standing upon the shoulders of giants.” This may well apply to the case of Fourier. There were indeed many contributions made by other mathematicians and scientists whose ideas helpedFourier to formulate his idea of decomposing a function into a sum of sinusoids or “waves.” InTrigonometric Delight (1998), Eli Maor eloquently describes the mathematical movement in the 17th and 18th centuries that influenced Fourier’s formulation of the theorem.

One of the movementsthat influenced Fourier’s theorem is the shiftin the treatment of trigonometry. Trigonometry had begun to assume its modern and analytic character with the great French mathematician,Francois Viete (1540-1603). With Viete, trigonometry underwent important changes, one of which is admitting infinite processes. In 1593, he discovered the famous infinite product

It was the first time an infinite process was explicitly written as a mathematical formula, and this was the beginning of modern analysis. In England, substantial contributions to trigonometry were also made in the first half of the seventeenth century. One of contributions which had an impact on Fourier’s theorem may be John Wallis’s (1616-1703) work on infinite series that is an immediate forerunner to Newton’s discoveries in the same field. Wallis,more than anyone else up to his time, realized the importance of analytic methods in mathematics: he was the first to treat conic sections as quadratic equations rather than geometric objects. His most famous formula is the infinite product

which together with Viete’s product are regarded as the most beautiful formulas in mathematics.

There was another reason for the rise of analytic trigonometry in the first half of the seventeenth century. Instead of applying trigonometry to heavens (spherical problems), mathematicians and scientists were interested in the mechanical world of daily life. The science of artillery was also developed during the century. Another branch of mechanics studied in the seventeenth and eighteenth centuries was oscillations. Due to the great sea voyages of the era, ever more accurate clocks of ever greater precision were heavily in demand. This led scientists to study the oscillations of pendulums and springs of various kinds. On another level, the increased skill and sophistication in building musical instruments motivated scientists to study the vibrations of sound-producing bodies such as strings, membranes, bells and air pipes. What is so significant about all these developments is that they all underscored the role of trigonometry in describing periodic phenomena which resulted in trigonometric functions---one of the essences of Fourier’s theorem.

It was not until Euler that trigonometry was fully incorporated with complex numbers for Fourier to later utilize it in his work. With Euler, the subject became truly analytic. Euler’s formula,

whichappeared in his great work, Analysin infinitorum (1748) expresses a deep relationship between trigonometric functions and the complex exponential function.

These developments moved trigonometry ever farther from its original connection with a triangle.

The outstanding problem in the second half of the eighteenth century was the vibrating string. Pythagoras, in the sixth century B.C., already discovered some of the laws governing the vibrations of a string. However, it was not until after the time of Newton and Leibniz that a full investigation of the problem was possible. This was due to the absence of partial differential equations. For the vibrating string the relevant equation is

where is the displacement from equilibrium of a point at a distancefrom one endpoint of the string at time, and is a constant that depends on the physical parameters of the string, which is its tension and linear density. This equation, known as the one-dimensional wave equation, excited the best mathematical minds of the time. Euler and D’Alembert expressed their solutions in terms of arbitrary functions representing two waves. On the other hand, Daniel Bernoulli found a solution involving an infinite series of trigonometric functions. These two types of solution to the same problem looked so different, the question arose whether they could be reconciled, and if not, to find out which was the more general. This question was answered by Fourier in his most important work, Theorie analytique de la chaleur (Analytic theory of heat, 1822). He showed that almost any function, when regarded as a periodic function over a given interval, can be represented by a trigonometric seriesof the form

where the coefficients and can be found from by computing certain integral.

We would like to see what he means by it by observing his study on heat propagation through Eli Maor’s account.

Fourier was particularly interested in the manner in which heat flows from a region of high temperature to one of lower temperature. The Law of cooling, previously discovered by Newton governed only the temporal rate of change of temperature, not its spatial rate of change. To deal with this problem, one must use the analytic tools of the continuum, in particular partial differential equations. Fourier showed that to solve such an equation, one must express the initial temperature distribution as a sum of infinitely many sine and cosine terms, which is now called Fourier series. This moment was the beginning of Harmonic Analysis.

The most remarkable advancement made in Harmonic Analysis in the last century is probably the invention of Cooley-Tukey fast Fourier transform algorithm known as FFT. It re-expresses the discrete Fourier transform (DFT) of an arbitrary composite size n = n1n2 in terms of smaller DFTs of sizes n1 and n2 recursively, in order to reduce the computation time to O(n log n) for highly-composite n (called smooth numbers).This algorithm, including its recursive application, was already known around 1805 to Carl Friedrich Gauss who used it to interpolate the trajectories of the asteroids Pallas and Juno, but unfortunetely, his work was not widely recognized. The effect of Cooley and Tukey’s algorithm was particularly significant in the area of signal processing, probably the best-known application of Fourier analysis. We would like to see some basic examples of signal processing at the end of the paper.

Applications of the use of Fourier transform areendless, for instance, Radon transform was advanced in the early 1900s by the mathematician from whom it takes its name. Fourier analysisare also found in x-ray crystallography, computerized tomography known as CT scanners, in the field of nuclear magnetic resonance, and in radioastronomy and modern Cosmology.

The next sectionof this paper explores theconnections between Fourier’s transform and the notions that are essential to the development of Fourier transform.

Harmonic Analysis onZp

ILet G= {e,}.

(1) Show that G is a commutative group.

(2) For which p G is a cyclic group.

(3) Find a relation to the modular arithmetic.

Before answering the questions above, we would like to revisit the notion of roots of unit and a concept of group introduced in abstract algebra; in particular, wewant to review the properties of group. The first reason to this is that is the set of roots of unity and the second reason is that the operation of is twofold. That is,has a complex multiplication as its binary operation; however, multiplying a complex number means adding exponents of which ultimately leads us to addition modulo p.

th Roots of Unity

n th roots of unity are the solutions to the equation. As the consequence of the fundamental theorem of algebra, we are guaranteed to have n different nth roots of unity.

(k = 0, 1, 2, 3, …, n-1)

Recall an important property of roots of unity: the sum of roots of unity is 0; that is,

B. The properties of group

is a group under addition modulo p. We will show that it is a group by showing that the following properties hold:

a)Closure

b)Associative laws

c)Identity

d)Inverse

(a) Closure:

Before proving that is closed in general term, let us look at the case with p= 3.Let and .

When,.

When,

When.

When .

So we can say that is closed under addition modulo 3. This also implies that any number in, we can find a number in that is congruent to that number. Notice also that is a cyclic group. That is, and, i.e., 1 and -1 are generators of. Because of this property, no matter what integer we use forto do the operation, all the results of the operation belong to. This confirms the fact that is closed under modulo arithmetic. Let us look at the examples to see what it means by a group being cyclic. By definition, when the operation is addition, is interpreted as when is positive. is interpreted as when is negative.

So basically, if a group is cyclic, any number in Z can be expressed in terms of elements insince we can always find a number in that is congruentto that number. In other words, all belong to one of class representatives,{0}, {1},{2},…,{p-1}.

For example, with our case p=3, every number in Z belongs to either

{…,-3p, -2p, -1p, 0, p, 2p, 3p,…},

{…,1-3p, 1-2p, 1-p, 1, 1+p, 1+2p, 1+3p,…}, or

{2-3p, 2-2p, 2-p, 2, 2+p, 2+2p, 2+3p,…}.

Therefore, is closed under modular arithmetic.

(b) Associative laws:

Associative laws hold under addition modulo p because of the fact that associative laws hold under addition..

Let . Then

This implies that

is the identity of , if for any k in , . So if is a group under addition modulo p, there is a unique element in such that for all k in. Since the operation involves addition, the identity of is 0 just as the identity of is 0 under addition.

For example, when p = 3.

since 0 and 3 are congruent.

since 4 and 1 are congruent.

, since 2 and 5 are congruent.

In general, = k for all.

(d) Inverse:

For each element k in, there is an element m in, called the inverse of k, such that . Let us find the inverse of each element inwhen p = 3 and derive the generalization from it.

. So -1 is the inverse of 1. The equivalent relation we are dealing with is addition modulo p, so we have to express -1 in terms of one of class representatives. We do so by applying modular arithmetic. . Since 2 is congruent to -1, we can replace -1 with 2 which is in. Applying addition modulo 3, we get, So 1 and 2 are inverse of each other just as 1 and -1 are.

0 + (-0) = 0 and. So we can say that 0 is the inverse of itself just as integerssuch as -3n, 3n are inverses of 0 for any.

So in general, we can say that k and p-k are inverse of each other because k + (p – k) = pmod p = 0.

Now we are ready to prove that G is a group. First, G is non-empty because. The binary operation for the set is the complex multiplication whichis ultimately the operation under addition modulo p.

Now, we need to show that:

(a) G is closed under complex multiplication.

(b) Associative laws hold;

(d) And inverse exists.

(a) Closure:

We are going to look at a few examples before proving the general case. Let us begin with the case when p=2, that is. Let k, =. Then. For Gto be a group, it must be closed under complex multiplication. What it means is that must be in G. So it ultimately means that. From our observation on, we claim that G is closed if exponents of each element in Gare closed under modular arithmetic.

Let us examine this claim with examples using p=2, and p=3.

When p=2,G=, for k=0, 1.

Let and, then .

If and .

If and, then .

If and , then .

is closed under complex multiplication because the operation is ultimately the addition modulo p.

When p=3,G=, for k = 0, 1, 2.

Let and. Then,.

If and, then.

So again, is closed under complex multiplication because the operation on exponents is modular arithmetic. Generalizing this, we can say that is closed under complex multiplication because for p ≥1 is a group under modular arithmetic.

So for any,.

(b) Associativity:

Let. We need to show that

that is, it is equivalent to showing that .

Therefore, the associative law holds for.

Let be the identity of. By definition of identity, is the identity of if for anyin for any. This implies that we simply need to find some, such that for any for the exponent of . From the preliminary observation made on, we know that k must be 0. So adding the inverse of, which is, to both sides, we obtain.

Thus,if . So 1 is the identity of, where k=0 is the identity of.

(d)Inverses:

By definition of inverse under multiplication, is the inverse of if *=. This means that we have to find some number which satisfy the modular arithmetic(k+k)modp=0. But this has been shown in the preliminary investigation showed that for any k, p-k is the inverse of k. So we know thatand for any are the inverse of each other, since

Let us look at some examples using p=3.

, for k=0,1,2.

The inverse of is itself since k = 0 and p-k = 3-0 = 3, k-(p-k) = 0 + 3 = 3, and , so = 1 = .

The inverse of is since k = 1 and p – k = 3 – 1 = 2 and.

So generally speaking, for any, if, then and are inverse of each other.

Finally, we are ready to answer the questions listed at the beginning of this section.

(1) Show that is a commutative group.

What needs to be shown here is that is Abelian. But this is obvious because the binary operation used for is the multiplication of complex numbers and multiplication is commutative. Under this operation, we need to apply modular arithmeticon exponents of but this operation is also commutative under addition modulo p. So we have,

(2) For which p is a cyclic group.

is a cyclic group if an element in generates every element in, that is,

=. This ultimately means that k must be a number that generates all elements of when multiplied by. Let us look at a few examples to see what we can conjecture about the relation between p and k.

When p=2, for k = 0, 1.

When k=0.

for any. So, k=0 fails to be a number for which is a generator of. The relation between 0 and 2 are not clear. So we proceed with more observation on.

When k=1.

. So k = 1 is a number where generates all elements of when raised to power where .

For example,

, , ,

,and so forth. So is a generator of. It looks like is the relation we need for generating all elements of, but what is the relation? We take a look at one more example since this example does not seem to be sufficient to conjecture any thing for the relation between k and p. So let us look at another example with p = 3. When p = 3, for k = 0, 1, and 2.

When k=0.

forany. So, k = 0 again fails to be the number for which is a generator of.

When k=1.

. So k = 1 is again a number where generates all elements of.

For example,,, ,

, , and so on.

So it appears that is the relation between k and p for which is a generator of

. What about, where?

,, ,

, and .

From these two examples, it appears that when and are relatively prime, generates every element of. So our conjecture is

is a generator of

Now we prove that the conjecture is true. Suppose that k and p are not relatively

prime. Then there exists a number other than 1 that is the greatest common divisor of and. This means that and for some. Then is a generator of, call it. Since is a generator of,. Notice that . So if we let should generate an element of other than itself since. Sowhich implies that by theorem. This is true only when. So cannot be a generator of.

Suppose that is not a generator of. Then there exists j in Z such that is not a generator of. Since k and p are relatively prime, there is no common factor other than 1. That means that generates all elements in since for all. This is a contradiction to our hypothesis that is not a generator of.

Thus is a generator of Q.E.D.

(3) Find a relation to the modular arithmetic.

We observed that the operation onis twofold. Multiplyingcomplex numbers means applying addition modulo p on the set. So if we describe the relation between and in terms of function, we can say that is a homomorphism. A homomorphism is a mapping that preserves the operation of the group that is used as a domain of the function: that is,:is called a homomorphismif for all. We need to show that this claim is valid. To do so, we first need to define the function and show that for all.

Define: Z by

We show that is a homomorphism.

Thus is a homomorphism of Z into. Now we want to see ifis an isomorphism. By definition, is an isomorphism if it is a bijection. So we first check to see whether is an injection then check to see if it is a surjection. The function is injective if. We prove this by proving the contrapositive statement of the original statement. That is if then

. Let and. Then,.

This means thatand .

So we proved thatif then.

To prove that is surjective, we need to show that if for any there exists afor which. Let, then there exists for whichand since all integers are congruent to one of the members of . Furthermore,for for the same reason. Thus is an isomorphism.

IILet Z={0,1,2,…,p-1}.

Let H be a set of all functions on into C.

Define

(4) Show that is an inner (dot) product.

To show that is an inner product, we need to show that the following axioms are satisfied for all and in, and.