507 – Homework 1

This set is due Monday, September 13.

  1. Prove Lamé’s theorem (Exercise 1.3.23 from the textbook).
  2. Solve exercises 15–17 from Section 1.2 of the textbook.
  3. Solve exercise 1.4.37 from the textbook.
  4. 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 {R} with identity {1} is an {x\in R} which is invertible, i.e., there is some {y\in R} such that {xy=1}. We say that {x} is irreducible iff {x} is not a unit but, whenever {x=yz} with {y,z\in R}, then either {y} or {z} is a unit. Unique factorization holds in {R} iff any non-unit {x} can be written as a finite product of irreducibles in an essentially unique way. The “essentially” means here that if {x} admits the factorizations {p_1\dots p_n} and {q_1\dots q_k} with each {p_i,q_j} irreducible, then {n=k}, and there is a permutation {\pi:\{1,\dots,n\}\rightarrow\{1,\dots,n\}} such that for each {i} there is a unit {u_i} with {p_i=u_i q_{\pi(i)}}, and {u_1\dots u_n=1}.
    • Let {{\mathbb Z}[i]} denote the set of complex numbers of the form {a+bi} where {a,b} are integers (and {i=\sqrt{-1}}). Check that this is a subring of {{\mathbb C}}.
    • We say that {\alpha|\beta} for {\alpha,\beta\in{\mathbb Z}[i]} if there is a {\gamma\in{\mathbb Z}[i]} such that {\beta=\alpha\gamma}. So, if {n,m} are integers and {n|m} in the usual sense, then {n|m} in this new sense. Check that if {n,m} are integers and {n|m} in the new sense, then {n|m} in the usual sense, so this new notion of “divides” generalizes the usual one.
    • Define {N:{\mathbb Z}[i]\rightarrow {\mathbb Z}} by {N(a+bi)=a^2+b^2}. This is an example of an Euclidean norm. Check that for all {\alpha,\beta\in{\mathbb Z}[i]}, {N(\alpha\beta)=N(\alpha)N(\beta)}. Conclude that whenever {\alpha|\beta}, then {N(\alpha)|N(\beta)}.
    • Check that {\alpha\in{\mathbb Z}[i]} is a unit iff {N(\alpha)=1}, and find all the units in {{\mathbb Z}[i]}.
    • Let {\alpha\in{\mathbb Z}[i]}. Show that if {N(\alpha)} is prime in {{\mathbb N}} then {\alpha} is irreducible in {{\mathbb Z}[i]}. The converse does not hold; for example, show that if {N(\alpha)=p^2} for some {p} prime in {{\mathbb N}} with {p\equiv 3\pmod 4}, then {\alpha} is irreducible in {{\mathbb Z}[i]}.
    • Show that {1-i} is irreducible, and {2=u(1-i)^2} for some unit {u}, so {2} is no longer irreducible.
    • One can show that unique factorization into irreducibles holds in {{\mathbb Z}[i]}. Explain how this is compatible with {(2+i)(2-i)=5=(1+2i)(1-2i)}.
  5. 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 {a_0,a_1,\dots} the function
      \displaystyle G(x)=\sum_{n=0}^\infty a_n x^n.
    • Their exponential generating function: We associate to {a_0,a_1,\dots} the function
      \displaystyle E(x)=\sum_{n=0}^\infty \frac{a_n}{n!}x^n.
    • Their Dirichlet series: We associate to {a_1,a_2,\dots} the function
      \displaystyle D(s)=\sum_{n=1}^\infty\frac{a_n}{n^s}.

    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:

    1. Ivan Niven. Formal Power Series. The American Mathematical Monthly, 76 (8), (Oct., 1969), 871 – 889.
    2. 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.
    3. 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/{\sim}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 {a,b\in{\mathbb Z}^+} with {(a,b)=1} there are infinitely many primes of the form {ak+b}.)

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

    1. This example is directly from generatingfunctionology. We want to analyze the sequence {a_0,a_1,\dots} that satisfies the initial condition
      \displaystyle a_0=0 and the recurrence relation (for {n\ge0})

      \displaystyle a_{n+1}=2a_n+1.

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

      \displaystyle \sum_{n=0}^\infty t^n=\frac1{1-t},

      the generating function for the sequence {1,1,1,\dots}! Check that we obtain

      \displaystyle \frac{G(x)}x=2G(x)+\sum_{n=0}^\infty x^n=2G(x)+\frac1{1-x}.

      Verify that this means that

      \displaystyle G(x)=\frac x{(1-x)(1-2x)}=x\bigl[\frac 2{1-2x}-\frac1{1-x}\bigr].

      Conclude that

      \displaystyle G(x)=\sum_{n=0}^\infty(2^n-1)x^n,

      and therefore {a_n=2^n-1} for all {n}.

    2. Recall that the Fibonacci sequence is given by
      \displaystyle f_0=0,\quad f_1=1, and (for {n\ge0})

      \displaystyle f_{n+2}=f_{n+1}+f_n.

      We use the exponential generating function {E(x)} to find a formula for {f_n}. For this, show that

      \displaystyle E'(x)=\sum_{n=0}^\infty f_{n+1}\frac {x^n}{n!}

      and

      \displaystyle E''(x)=\sum_{n=0}^\infty f_{n+2}\frac {x^n}{n!}

      and, therefore,

      \displaystyle E(x)+E'(x)=E''(x).

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

      \displaystyle e^t= \sum_{n=0}^\infty \frac{t^n}{n!},

      the exponential generating function for the sequence {1,1,1,\dots}, to conclude that

      \displaystyle f_n=\frac1{\sqrt5}\left(\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n\right).

    3. Suppose that
      \displaystyle D_1(s)=\sum_{n=1}^\infty \frac{a_n}{n^s} and

      \displaystyle D_2(s)=\sum_{n=1}^\infty \frac{b_n}{n^s}.

      Show that the product {D_3=D_1D_2} is given by

      \displaystyle D_3(s)=\sum_{n=1}^\infty\frac{c_n}{n^s},

      where

      \displaystyle c_n=\sum_{k|n}a_kb_{n/k}

      for all {n}, the sum ranging over all (positive) divisors {k} of {n}.

      Recall that

      \displaystyle \zeta(s)=\sum_{n=1}^\infty\frac1{n^s}

      is the Dirichlet series of the sequence {1,1,\dots} Show that {\zeta^2(s)} is the Dirichlet series of the sequence {d(1),d(2),\dots}, where {d(n)} is the number of divisors of {n}. Show that {\displaystyle\frac1{\zeta(s)}} is the Dirichlet series of the Möbius {\mu} function, given by {\mu(1)=1}, {\mu(n)=0} if there is some {p>1} such that {p^2|n}, and {\mu(n)=(-1)^t} if {n=p_1\dots p_t} for distinct primes {p_i}.

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

Advertisement

This entry was posted on Thursday, September 2nd, 2010 at 1:13 pm and is filed under 507: Advanced number theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

5 Responses to 507 – Homework 1

  1. Nick Davidson says:
    September 2, 2010 at 4:45 pm

    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

    Reply
  2. Amy Griffin says:
    September 9, 2010 at 2:13 pm

    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?

    Reply
    • andrescaicedo says:
      September 9, 2010 at 2:39 pm

      Hi Amy,

      I meant this: a|b, as we commonly use it, means that a,b are integers, and there is an integer c such that ac=b.

      In this exercise, we defined \alpha|\beta to mean that \alpha,\beta are “Gaussian integers”, i.e., members of {\mathbb Z}[i], and there is a \gamma\in{\mathbb Z}[i] with \alpha\gamma=\beta.

      Since every integer is in {\mathbb Z}[i], if a,b\in{\mathbb Z}, we have two potentially conflicting notions of a|b, 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).

      Reply
  3. Amy Griffin says:
    September 9, 2010 at 4:04 pm

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

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: