This set is due Monday, September 13.

- Prove Lamé’s theorem (Exercise 1.3.23 from the textbook).
- Solve exercises 15–17 from Section 1.2 of the textbook.
- Solve exercise 1.4.37 from the textbook.
- In lecture I mentioned that in more general contexts than working with integers, one needs to be careful about whether there is unique factorization or not. Here I want to flesh this idea out a little bit. There is much to say on this topic, and we won’t even scratch the surface here. We may revisit this topic through the term.Recall that a
*unit*in a (commutative) ring with identity is an which is invertible, i.e., there is some such that . We say that is*irreducible*iff is not a unit but, whenever with , then either or is a unit.*Unique factorization*holds in iff any non-unit can be written as a finite product of irreducibles in an*essentially*unique way. The “essentially” means here that if admits the factorizations and with each irreducible, then , and there is a permutation such that for each there is a unit with , and .- Let denote the set of complex numbers of the form where are integers (and ). Check that this is a subring of .
- We say that for if there is a such that . So, if are integers and in the usual sense, then in this new sense. Check that if are integers and in the new sense, then in the usual sense, so this new notion of “divides” generalizes the usual one.
- Define by . This is an example of an
*Euclidean norm*. Check that for all , . Conclude that whenever , then . - Check that is a unit iff , and find all the units in .
- Let . Show that if is prime in then is irreducible in . The converse does not hold; for example, show that if for some prime in with , then is irreducible in .
- Show that is irreducible, and for some unit , so is no longer irreducible.
- One can show that unique factorization into irreducibles holds in . Explain how this is compatible with .

- I mentioned in lecture three kinds of functions that one can associate to a sequence, namely:
- Their usual generating function: We associate to the sequence the function

- Their exponential generating function: We associate to the function

- Their Dirichlet series: We associate to the function

For many applications, we do not need to worry about issues of convergence, and can manipulate these functions at a purely formal level. This is an interesting topic in itself. If you want to read some about the general theory of generating functions, I suggest to begin with one of the following:

- Ivan Niven.
*Formal Power Series*. The American Mathematical Monthly,**76 (8)**, (Oct., 1969), 871 – 889. - J. H. van Lint, R. M. Wilson.
**A Course in Combinatorics**, Cambridge University Press (1993). This nice book has a chapter on formal power series. - Herbert Wilf.
**generatingfunctionology**, A K Peters (2005), third edition. The second edition can be downloaded for free from the author site, at http://www.math.upenn.edu/wilf/DownldGF.html and it is a nice reference to have.

(Dirichlet series are usually treated in complex analysis books, or in number theory books, especially if the book deals with Dirichlet’s proof that for any with there are infinitely many primes of the form .)

Here are some examples of how these functions may be used:

- This example is directly from
*generatingfunctionology*. We want to analyze the sequence that satisfies the initial condition

and the recurrence relation (for )We use the generating function to find an explicit formula for as a function of . To do this, multiply both sides of the recurrence relation by , and add over all values of . Recall that

the generating function for the sequence ! Check that we obtain

Verify that this means that

Conclude that

and therefore for all .

- Recall that the Fibonacci sequence is given by

and (for )We use the exponential generating function to find a formula for . For this, show that

and

and, therefore,

Solve this differential equation (you may want to look in an ODE book if you do not recall how to do this). Use that

the exponential generating function for the sequence , to conclude that

- Suppose that

andShow that the product is given by

where

for all , the sum ranging over all (positive) divisors of .

Recall that

is the Dirichlet series of the sequence Show that is the Dirichlet series of the sequence , where is the number of divisors of . Show that is the Dirichlet series of the Möbius function, given by , if there is some such that , and if for distinct primes .

- Their usual generating function: We associate to the sequence the function

*Typeset using LaTeX2WP. Here is a printable version of this post.*

Hey Dr. Caicedo,

For the third exercise you listed, did you mean exercise 1.4.37, on p. 33? I can’t find a 37 in section 1.5.

Thanks, I’m looking forward to getting started on these,

Nick

Hehe. Yes, 1.4.37. Sorry.

Dr. Caicedo,

On question 4, second bullet, can you tell me which one is the “usual” sense and which is the “new” sense? I’ve used the alpha = beta times gamma one before, so that’s my “usual”, but for this problem is it the new one?

Hi Amy,

I meant this: , as we commonly use it, means that are integers, and there is an integer such that .

In this exercise, we defined to mean that are “Gaussian integers”, i.e., members of , and there is a with .

Since every integer is in , if , we have two potentially conflicting notions of , depending on whether we think of the definition of in terms of integers (the “usual” one), or of the definition in term of Gaussian integers (the “new” one).

Thank you so much, I was on the wrong track!