Teaching Philosophy (1)

I think the most important aspect in university teaching is providing the right learning atmosphere. The class will basically takes care of itself if the atmosphere is right. i.e.　無為而治。

It is my goal to promote students’ interests in mathematics. To do this, I first ask myself the question: Why do I love mathematics? In short, I love mathematics because I appreciate its power, beauty, and applications. Thereofre, I shall try my best to make my students to appreciate the same three aspects. Nothing is more convincing than giving examples to illustrate these:

(1) For power, I ask my students to solve the following problem:Given a 8 by 8 checkerboard with the opposite corners removed. Can you tile it with 31 by dominos?

(2) For beauty, I ask them the following problem: Let Suppose is a point, which can move along the line , and be a moving point on the -axis. What is the minimum perimeter of the triangle ?

(3) For applications, I show them how Google’s page rank works. (when I was teaching linear algebra, for calculus classes, there are more examples…)

To be continued…

Answer to “Another HKAL Problem”.

Here is an intuitive answer given by Katherine Chiu (my high school math teacher):

Let It is clear that and are monotonically increasing, and have no points of inflection. Therefore, the two functions intersect at most twice. Therefore, and are the only solutions.

Here is my solution, using Mean Value Theorem (MVT):

Let , then by MVT, there exists such that:

, and

Suppose there is a real such that , we have:

, which means either or Now, since , we have Therefore, the only solutions are and

Another AL problem?

I am not sure whether the following is an actual AL problem, but it can definitely be solved using techniques learned in AL pure mathematics.

Find all real numbers such that

There are obvious solutions and Is that it?

While I can simply give my solution, I want the reader to play around this problem a little bit, and I hope some of you will either e-mail me the answer or post it as a comment. If no one does that, solution will be given tomorrow.

IMO 2008 Problem 3

Prove that there are infinitely many positive integers  such that  has a prime divisor greater than

Many of you probably knew the elementary solution already. If not, it is included in the appendix. 

I want to discuss about the problem and tell you some of the major theorems related to the problem. 

Conjecture: There are infinitely many such that is a prime number. 

Theorem (Iwaniec): There are infinitely many such that is either a prime or a product of two primes. 

Reference: 

H. Iwaniec, “Almost-primes represented by quadratic polynomials,” Inventiones Mathematicae, 47 (1978), 171-188. 

While this theorem is the closest thing to the conjecture, it doesn’t help with the IMO problem at all. The most it can say is that there are infinitely many such that the largest prime divisor of is at least  

Here are two theorems, that would “second-kill” the problem. 

Theorem (Deshouillers, Iwaniec) There exist infinitely many integers  such that the greatest prime factor of  is at least

Reference: 

Deshouillers, Iwaniec, “On the greatest prime factor of “. Annales de l’institut Fourier, 32 no. 4 (1982), p. 1-11

Knowing this, this IMO problem is a piece of cake. Hopefully, knowing this would help the contestants with the forth coming IMOs. 

Appendix: Here is a sketch of elementary proof of the problem. Using your favorite method, argue that we may take . (using Iwaniec’s theorem for example…though this is kind of over killing) Since , we may also assume Write .  Since divides  . This implies Hence we have , which implies We thus have . By choosing a sufficiently big ,  we have , and hence , which implies and we are done. 

Challenge: Imporve the bound in the theorem of Deshouillersand Iwaniec. (this is really a real challenge…)

Coming up: My teaching philosophy. 

 

Sum of Squares (2)

Recall the question, let be a prime, in how many ways can we write as a sum of two squares?

The answer is , i.e. if , then the pair works. However, the following pairs also work:

The reason is simple if one thinks in terms of Gaussian integers Recall that the Gaussian primes are precisely the following:

1) .

2) Rational primes of the form

3) such that , a rational prime.

Since has unique factorization, if , we must have , therefore must be a Gaussian prime, and hence the prime divisors of are precisely and its unit multiples, namely: Likewise for the conjugate , we also have . Therefore, this gives 8 different ways to write as a sum of two squares.

For the general question: For a given integer , how many ways can we write it as a sum of two squares. For this, let to denote the number of ways to write as a sum of squares. We have:

For the proof, one may try to use Gaussian integers. There is a more general method that deals with finding , which uses the theory of modular forms. I will discuss that later.

Coming up: IMO 2008 Problem 3.

Sum of Squares (1)

It is a well known theorem by Fermat that any prime of the form can be written as a sum of two squares. 

One question is, in how many ways can we write a prime of the form into sum of two squares? 

More generally, given an integer .  In how many ways can we write as a sum of two squares? 

Perhaps I will let the reader to think for a momenrt, I will discuss more of this tomorrow.

CGMO 2007 Problem 7 and Liouville’s theorem

Let such that

Let

Suppose Prove that

We first sketch a proof of the official solution:

Plugging into yields:

We have This gives

If , we have , which implies . Hence

Therefore, we have:

which is a contradiction and we are done.

Notice that if we replace by , then the above solution does not work.

—————————————————————————————

Here, I give a different proof, using the following theorem of Liouville:

Theorem (Liouville) Let be an algebraic number of degree . Let
such that
and that is irreducible over Then for all ,
we have:

where

Here , where are the roots of The proof of this theorem will be given later, let;s see how we can apply this theorem to this CGMO problem.

Proof: Let Let , then and is clearly irreducible. (i.e. is an algebraic number of degree ) Since We have Now, suppose then we have since is not rational (this is an easy application of the rational root theorem). Write Now since By Liouville, we have:

Now, since .

This gives:

Finally, we have
Therefore, This is a contradiction and
we are done.

—————————————————————————————

Appendix: Proof of Liouville’s theorem.

Proof: We have since the numerator of is a non-zero integer. Now we consider two cases:

(1) then , since

(2) , then We have Let , we have:

Hence, we have as claimed.

Leibniz’s identity and beyond (1)

We start with the following well-known identity:

Let’s give a proof of this identity:

Note that we may rewrite the series as:

Next, we switch the order of integration and summation: [For those of you who do not know why we can do that, you will learn it later]

This last integral equals: which finishes the proof.

Consider a similar sum:

To compute the sum, we may proceed similarly as before, which yields:

This last integral can be computed by completing squares and trigonometric substitutions. We get the sum S equals [The last few equalities would be excellent exercises for those students preparing for HKCEE.]

Hm…notice that mysterious number shows up again… one might wonder, does shows up ALL the time?  The answer is no, because we have the following:

[Note that this is the natural log, i.e. log base e.]

The nest question would be, why does show up, and why?

The problem turns out to be ultimately related to number theory via something called the Dirichlet’s L-function, and we shall talk about it more in a later post.

Exercise: Prove that

Generating Function and Tiling Problems

Consider the following classic: Suppose one deletes two opposite corners from a standard 8 by 8 checkerboard (or chessboard). Prove that it cannot be tiled by 31 two by one dominos.

One solution is to put the standard coloring on the board, and argue that the number of black squares and the number of white squares are different. Hence such tiling is not possible.

Here I give a different solution using generating function. To do this, we place the board on a coordinate system. Say the lower left corner is (0, 0), and the top right corner is (8, 8). From now on, we use the coordinate of the lower left corner to represent each square. i.e. the square at the top right corner is represented by (7, 7).

Now for each (a, b), we associate a monomial . Therefore, a horizontal domino is represented by the polynomial: , and a vertical domino is represented by the polynomial

Suppose a tiling using these dominos is possible, we must have the following identity:

for some polynomials and

i.e.

Since this is an identity, we may let . The left hand sides gives , while the right hand side gives . Therefore, such tiling is not possible and we are done.

Challenge: Suppose we have 21 three by one domino. (or tri-mino?) Which square in a 8 by 8 checkerboard must be removed in order for these tri-minos to tile the board?