You are currently browsing the monthly archive for March 2008.

[Update: Firefox 3 Beta 5 is out – the last beta version! And it is supposedly the fastest browser out there. So, far it’s been using memory not more than 150 200 Mb!]

I have been wanting to respond to some of the comments I’ve received over the past week but haven’t had enough time to do so. I will certainly respond some time soon.

For now, I just wish to point out to folks who use Firefox 2 that Firefox 3 Beta 4 has been released. Well, it is only meant for developers and testers for now, but having installed and used it over the past several days, I can say it’s  a much better version of the Firefox browser. The biggest problem (I’ve had) with the current version of Firefox is it uses an enormous amount of memory mostly due to memory leaks. Keep it running for several days – I hardly log off – and the browser takes up as much as 700-800Mb of memory, sometimes even consuming a gigabyte, which is plain insane! Due to this, I had seriolusly considered switching to Flock or IE altogether. But, now I am very satisfied with the new beta version. It mostly uses around 150Mb of memory while never exceeding 200Mb 250Mb, which really shows that the Firefox team has had been working hard on the new version.

Go ahead and download/install the new beta version and test it yourself. I haven’t had any problems thus far. The only downside of using the beta version is your add-ons will not work, but that is hardly an issue, at least to me, for now.

Part 2:

After having understood the inclusion-exclusion principle by working out a few cases and examples in my earlier post, we are now ready to prove the general version of the principle.

As with many things in mathematics, there is a “normal” way of doing proofs and there is the “Polya/Szego” way of doing proofs. (Ok, ok, I admit it’s just a bias I have.) I will stick to the latter. Ok, let’s state the principle first and follow it up with its proof in a step-by-step fashion.

Inclusion-Exclusion Principle: Let there be a set of $N$ objects. Suppose out of these $N$ objects, there are $N_a$ objects of type $a$, $N_b$ objects of type $b, \ldots ,$ $N_k$ objects of type $k$ and $N_l$ objects of type $l$. Also, suppose $N_{ab}, N_{ac}, \ldots , N_{abc}, \ldots , N_{ab \ldots kl}$ denote the number of objects that are simultaneously of type $a$ AND $b,$ $a$ AND $c, \ldots , a, b$ AND $c, \ldots , a, b, c, k$ AND $l,$ respectively. Then, the number of objects that are NOT of type $a, b, c, \ldots , k, l$ is

$N - (N_a + N_b + \ldots + N_k + N_l)$

$+ (N_{ab} + N_{ac} + \ldots + N_{kl})$

$- (N_{abc} + \ldots ) + \ldots$

$\pm N_{abc \ldots kl}$.

Notation —

Let $U$ (finite or infinite) be the universe of discourse. Suppose $A \subset U$. Then, the characteristic function $1_A: U \to \{ 0, 1 \}$ of $A$ is defined as

$1_A (x) = 1$ if $x \in A$,

and $1_A(x) = 0$ otherwise, for all $x \in U$.

For example, suppose $U = \{ 1, 2, 3, 4, \ldots , 29, 30 \}$. Let $A = \{ 2, 4, 6, \ldots , 28, 30 \}$ (i.e. even integers.) Then, $1_A(2) = 1_A(26) = 1, 1_A(3) = 1_A(29) = 0$, and so on.

Note: $1_U (x) = 1$ and $1_{\emptyset}(x) = 0$ for all $x \in U$. Here, $\emptyset$ denotes the empty set. Due to this, we will use $1$ and $1_U$ interchangeably from now.

Lemma 1: $A \subset B$ iff $1_A(x) \le 1_B(x)$ for all $x \in U$.

Proof: We first prove the “only if”part. So, suppose $A \subset B$. Let $x \in U$. If $x \in A$, then $1_A(x) = 1$. But, we also have $x \in B$, in which case, $1_B(x) = 1$. If, on the other hand, $x \notin A$, then $1_A(x) = 0 \le 1_B(x)$. Hence, in either case, $1_A(x) \le 1_B(x)$ for all $x \in U$.

We now prove the “if” part. So, suppose $1_A(x) \le 1_B(x)$ for all $x \in U$. Let $x \in A$. Then, $1_A(x) = 1$, which forces $1_B(x) = 1$, which implies $x \in B$. Hence, $A \subset B$, and this completes our proof.

Note: If $U$ is finite, then $\displaystyle |A| = \sum_{x \in U}1_A(x)$.

Lemma 2: $1_{A^c}(x) = 1 - 1_A(x) ,$

$1_{A \cap B}(x) = 1_A(x) 1_B(x),$ and

$1_{A \cup B}(x) = 1 - (1 - 1_A(x))(1 - 1_B(x))$

for all $x \in U$. (Here, $A^c$ is the complement of $A$.)

Proof: The proof for each case is elementary.

Lemma 3: Suppose $U$ is finite. If $A, B, C, \ldots \subset U$, then the characteristic function of $A \cup B \cup C \cup \ldots$ is $1 - (1 - 1_A)(1 - 1_B)(1 - 1_C) \ldots$, i.e.

$1_{A \cup B \cup C \cup \ldots}(x) = 1 - (1 - 1_A(x))(1 - 1_B(x))(1 - 1_C(x)) \ldots$ for all $x \in U$.

Proof: Note the above is an extension of the third part of lemma $(2)$. A simple induction on the number of subsets of $U$ proves the result.

Proof of the inclusion-exclusion principle —

Now, suppose $A, B, C, \ldots, K, L$ are subsets of objects of type $a, b, c, \ldots, k, l$, respectively. Observe that the set of objects that are NOT of type $a, b, c, \ldots , k, l$ is simply the region outside of all the oval regions! (Look at the previous post to see what this means.) And this region is simply the subset $(A \cup B \cup B \cup \ldots \cup K \cup L)^c$. Using the first part of lemma $(2)$, we see that the characteristic function of this outside region is $1 - 1_{A \cup B \cup B \cup \ldots \cup K \cup L}$, which from lemma $(3)$ is the same as

$(1-1_A)(1-1_B)(1-1_C) \ldots (1-1_K)(1-1_L)$.

Expand the last expression to get

$1 - (1_A + 1_B + 1_C + \ldots)$

$+ (1_A1_B + 1_A1_C + \ldots)$

$- (1_A1_B1_C + \ldots) + \ldots$

$\pm 1_A1_B\ldots 1_L$.

Now, sum over all the elements of $U$ and use the second part of lemma $(2)$ to obtain the desired result. And this completes our proof.

Part 1:

A couple of weeks ago, my friend John (from UK) asked me if I could explain the Inclusion-Exclusion Principle to him. Wikipedia contains an article on the same topic but John felt that it wasn’t a very helpful introduction. So, as promised, here is the post on that topic, though I managed to finish it only after some delay. (Sorry, John!)

As the title of this post suggests, the inclusion-exclusion principle can simply be described as counting all the objects outside the oval regions! We will use Venn diagrams to explain what that means.

Note: $\lfloor x \rfloor$ denotes the greatest integer less than $x$.

Ok, let’s now “build” the principle step by step.

1. Suppose there are $N$ objects out of which there are exactly $N_a$ objects of type $a$. How many objects are NOT of type $a$? The answer is obvious: $N - N_a$. The Venn diagram below depicts the answer pictorially. The rounded rectangular region (with the orange border) is the set of all $N$ objects, and the oval region (with the blue border) is the set of all $N_a$ objects of type $a$. Then, the remaining white region that is outside the oval region denotes the set of all objects that are NOT of type $a$, and clearly, there are $N - N_a$ of ’em.

Indeed, let us take a simple example. Consider the set of first thirty natural numbers: $\{ 1, 2, \ldots , 30 \}$. So, $N = 30$. Now, out of these thirty integers, let $N_2$ be the number of integers divisible by $2$. Then, $N_2 = \lfloor 30/2 \rfloor = 15$. It is easy to see that the number of integers NOT divisible by $2$ equals $N - N_2 = 30 - 15 = 15$, which is what we would expect if we were to list all the integers not divisible by $2$. Indeed, those integers are $1, 3, 5, \ldots , 29$.

2. Now, suppose there are $N$ objects out of which there are exactly $N_a$ objects of type $a$ and $N_b$ objects of type $b$. Also, suppose there are exactly $N_{ab}$ objects that are of both type $a$ AND $b$. Then, how many objects are NOT of type $a$ OR $b$? The Venn diagram below illustrates this case.

Again, we are counting the number of objects outside the two oval regions. To answer the above question, we first need to determine the number of objects inside the two oval regions, and then subtract this number from the total, which is $N$. Now, one might be tempted to think that the number of objects inside the two oval regions is simply $N_a + N_b$. But this is only true if the two oval regions don’t intersect (i.e. they have no objects in common.) In the general case, however, the expression $N_a + N_b$ counts $N_{ab}$ twice! And so, we must subtract $N_{ab}$ from the expression to get $N_a + N_b - N_{ab}$ as the exact number of objects inside the two oval regions. We can now see that the number of objects outside the two oval regions equals $N - (N_a + N_b - N_{ab}) = N - (N_a + N_b) + N_{ab}$, and we are done.

Continuing with our example used earlier, let $N_3$ be the number of integers divisible by $3$. Also, let $N_6$ be the number of integers divisible by $2$ AND $3$ (i.e. we count multiples of $6$.) Now, note that $N_3 = \lfloor 30/3 \rfloor = 10$, and $N_6 = \lfloor 30/6 \rfloor = 5$.

Thus, using the formula derived above, the number of integers that are NOT divisible by $2$ OR $3$ equals $N - (N_2 + N_3) + N_6 = 30 - (15 + 10) + 5 = 10$. In fact, we can list these ten integers: $1, 5, 7, 11, 13, 17, 19, 23, 25$ and $29$; and this confirms our answer.

3. Now, suppose there are $N$ objects out of which there are exactly $N_a$ objects of type $a$, $N_b$ objects of type $b$ and $N_c$ objects of type $c$. Also, let $N_{ab}$ denote the number of objects of type $a$ AND $b$, $N_{bc}$ the number of objects of type $b$ AND $c$, $N_{ca}$ the number of objects of type $c$ AND $a$, and $N_{abc}$ the number of objects of type $a, b$ AND $c$. Then, how many objects are NOT of type $a, b$ OR $c$? This case is illustrated by the Venn diagram shown below.

Once again, let us ask, what is the number of objects inside the three oval regions. A possible answer is $N_a + N_b + N_c$. Now this will only be true if the three oval regions are pairwise disjoint. In the general case, however, we will have to take care of overcounting, just as we did in $(2)$ earlier. A brief thought will reveal that in the above expression, we have counted each of $N_{ab}, N_{bc}$ and $N_{ca}$ twice and $N_{abc}$ thrice! To take care of this overcounting, we subtract each of $N_{ab}, N_{bc}$ and $N_{ca}$ once from the expression, but in doing so, we also end up subtracting $N_{abc}$ thrice! We thus need to add $N_{abc}$ back into the expression to get $N_a + N_b + N_c - N_{ab} - N_{bc} - N_{ca} + N_{abc}$, and this expression yields the exact number of objects inside the three oval regions. Therefore, the number of objects outside the three oval regions equals $N - (N_a + N_b + N_c) + (N_{ab} + N_{bc} + N_{ca}) - N_{abc}$. And, we are done.

Again, continuing with our earlier example, let $N_5$ denote the number of integers divisible by $5$. Then, $N_5 = \lfloor 30/5 \rfloor = 6$. Also, let $N_{15}$ denote the number of integers divisible by $3$ AND $5$ (i.e. we are counting multiples of $15$); then, $N_{15} = \lfloor 30/15 \rfloor = 2$. Again, let $N_{10}$ denote the number of integers divisible by $2$ and $5$; then $N_{10} = \lfloor 30/10 \rfloor = 3$. And, finally, let $N_{30}$ denote the number of integers divisible by $2, 3$ and $5$; then $N_{30} = \lfloor 30/30 \rfloor = 1$.

So, the number of integers NOT divisible by $2, 3$ OR $5$ equals $N - (N_2 + N_3 + N_5) + (N_{6} + N_{15} + N_{10}) - N_{30}$

$= 30 - (15 + 10 + 6) + (5 + 2 + 3) - 1 = 8$. Indeed, those eight integers are $1, 7, 11, 13, 17, 19, 23$ and $29$.

It isn’t very hard to deduce the formula for the general case when we have a set of $N$ objects, out of which there are $N_a$ objects of type $a$, $N_b$ objects of type $b$, and so on. The proof of the general formula will follow in the next post, which may include a couple of problems/solutions involving this principle.

I attended the CURM Conference & MAA Intermountain Section Meeting yesterday at BYU, Provo, and had the chance to attend quite a few presentations that I found interesting. There were four presentations in particular that were of special interest to me, and though, right now, I don’t have enough material to blog on ’em, I think I will eventually find the required material to post some stuff here.

These four presentations were titled

1. Exploration of G-graphs of Non-Abelian Groups: Andrea L. DeWitt & Alys M. Rodriguez (Lamar University)

2. Re-invent the Wheel: can it be done?: Christa Bauer & Jillian Hamilton (Lamar University)

3. Proving Integer Sequence Identities with Paths on Graphs: Megan Craven (St. Peters College)

4. Restricted Rado Numbers: Katrina Luckenbach & Matthew Vieira (St. Peters College)

I simply love the sound of the guitar (of all types), and as any amateur guitar player, I have some guitar heroes myself – this has got nothing to do with the popular game Guitar Hero, which I think sucks!

Let me begin by posting several videos of Joe Satriani or “Satch” (as he is popularly known) playing Love Thing, Always with Me Always with You and Starry Night. By the way, Kirk Hammett (Metallica) and Steve Vai were both students of Satch, if you didn’t know.

Enjoy!🙂

Love Thing

Always with Me Always with You

Starry Night

[Update: Thanks to Andreas for pointing out that I may have been a little sloppy in stating the maximum modulus principle! The version below is an updated and correct one. Also, Andreas pointed out an excellent post on “amplification, arbitrage and the tensor power trick” (by Terry Tao) in which the “tricks” discussed are indeed very useful and far more powerful generalizations of the “method” of E. Landau discussed in this post. The Landau method mentioned here, it seems, is just one of the many examples of the “tensor power trick”.]

The maximum modulus principle states that if $f: U \to \mathbb{C}$ (where $U \subset \mathbb{C}$) is a holomorphic function, then $|f|$ attains its maximal value on any compact $K \subset U$ on the boundary $\partial K$ of $K$. (If $|f|$ attains its maximal value anywhere in the interior of $K$, then $f$ is a constant. However, we will not bother about this part of the theorem in this post.)

Problems and Theorems in Analysis II, by Polya and Szego, provides a short proof of the “inequality part” of the principle. The proof by E. Landau employs Cauchy’s integral formula, and the technique is very interesting and useful indeed. The proof is as follows.

From Cauchy’s integral formula, we have

$\displaystyle f(z) = \frac1{2\pi i} \oint_L \frac{f(\zeta)}{\zeta - z} d\zeta$,

for every $z$ in the interior of $D$.

Now, suppose $|f(\zeta)| \le M$ on $L$. Then,

$\displaystyle |f(z)| \le \frac{M}{2\pi} \int_L \left|\frac{d\zeta}{\zeta - z}\right| = KM$,

where the constant $K$ depends only on the curve $L$ and on the position of $z$, and is independent of the specific choices of $f(z)$. Now, this rough estimate can be significantly improved by applying the same argument to $(f(z))^n$, where $n \in \mathbb{N}$, to obtain

$|f(z)|^n \le K M^n$, or $|f(z)| \le K^{1/n} M$.

By allowing $n$ to go to infinity, we get $|f(z)| \le M$, which is what we set out to prove.

Polya/Szego mention that the proof shows that a rough estimate may sometimes be transformed into a sharper estimate by making appropriate use of the generality for which the original estimate is valid.

I will follow this up with, maybe, a couple of problems/solutions to demonstrate the effectiveness of this useful technique.

1. Notions of Set Theory

Artin introduces a concept that is referred to as the canonical factoring of a map (function). The basic idea is that any function $f$ can be factored into three functions $f_1, f_2$ and $f_3$ in a somewhat unique way:

$f = f_3 f_2 f_1$, where

$f_1$ is onto, $f_2$ is a bijection, and $f_3$ is an injection. The construction of these three functions is done in a canonical, or natural, way that doesn’t require the use of objects outside the domain and/or range of $f$.

Let $S$ be some non-empty set. If $f$ is a function from $S$ into a set $T$, then we write

$f: S \to T$.

Suppose $f: S \to T$ and $g: T \to U$. Then, we can form a composite function $g \circ f: S \to U$ defined by $(g \circ f)(s) = g(f(s))$ for all $s \in S$. The associative law holds trivially for composition of functions.

Further, if $S_0 \subset S$, then the set of all the images of elements of $S_0$, denoted by $f(S_0)$, is called the image of $S_0$. In general, $f(S) \subset T$. We call the function $f$ onto whenever $f(S) = T$.

Now, let us partition the set $S$ into equivalence classes such that $s_1, s_2 \in S$ are in the same equivalence class iff $f(s_1) = f(s_2)$. This partition is called the quotient set and is denoted by $S_f$.

To illustrate, suppose $S = \{ 1, 2, 3, 4\}$ and $T = \{ a, b, c, d\}$. Also, let $f: S \to T$ such that $f(1) = a, f(2) = b, f(3) = b$ and $f(4) = c$. Then, the quotient set, $S_f = \{ \{ 1\}, \{ 2, 3\}, \{ 4\}\}$.

We construct now a function $f_1: S \to S_f$ that maps each $s \in S$ to its equivalence class. It can be verified that $f_1$ is onto. So, taking the above example, we have $f_1(1) = \{ 1 \}$, $f_1(2) = \{ 2, 3\}$, $f_1(3) = \{ 2, 3\}$ and $f_1(4) = \{4\}$.

Next, we construct a function $f_2: S_f \to f(S)$ where each element (which is an equivalence class) of $S_f$ is mapped to a $t \in T$ where each $t$ is the image of the members of the equivalence class. Recall that $s_1, s_2 \in S$ are in the same equivalence class iff $f(s_1) = f(s_2)$. Therefore, $f_2$ is one-to-one and onto. Continuing with our above example, we have $f_2(\{ 1\}) = a$, $f_2(\{ 2, 3\}) = b$ and $f_2(\{ 4\}) = c$.

And, finally, we construct a trivial function $f_3: f(S) \to T$ where $f_3(t) = t$ for each $t \in f(S)$. Note that $f_3$ is not an identity because it maps a subset, $f(S)$, into a possibly larger set, $T$, i.e. $f_3$ is an identity iff $f$ is onto. In general, $f_3$ is one-to-one and into (i.e. an injection.)

Thus, if $f(s) = t$, we note that $f_3 f_2 f_1 (s) = t$ for every $s \in S$.

And, so,

$f = f_3 f_2 f_1$.

Once again, $f_1$ is onto, $f_2$ is a bijection, and $f_3$ is an injection.

It looks like it doesn’t make much sense to factor $f$ the way we did above, but we will explore more of this with respect to group homomorphisms in my next post.

Ok, I got a copy of Emil Artin‘s Geometric Algebra from the library a couple of days ago, and a careful reading of some of the parts from the first chapter has convinced me even more now that one should indeed learn mathematics from the masters themselves!

The subject employs concepts/theorems/results from set theory, vector spaces, group theory, field theory and so on, and centers around the foundations of affine geometry, the geometry of quadratic forms and the structure of the general linear group. The book also deals with symplectic and orthogonal geometry and also the structure of the symplectic and orthogonal groups.

I intend to blog on this subject for as long as I can, and this will be my first serious project for now. There are some neat things I learned in chapter I which basically deals with preliminary notions. The actual text begins from chapter II, which is titled Affine and Projective Geometry. But, chapter I has some cool techniques too, and I wish to share them in my subsequent posts.

This post is non-mathematical in nature, and yet, I felt I should write about a very important essay written by Kant, for the rational thought expressed in the essay is very close to my heart!

In 1784, Immanuel Kant wrote an essay titled, Answer to the Question: What is Enlightenment?

He answers that question in the first paragraph of his essay:

Enlightenment is man’s emergence from his self-imposed immaturity. Immaturity is the inability to use one’s understanding without guidance from another. This immaturity is self-imposed when its cause lies not in lack of understanding, but in lack of resolve and courage to use it without guidance from another. Sapere Aude! [dare to know] “Have courage to use your own understanding!”–that is the motto of enlightenment.

And, the part that I really like is contained in the second paragraph, and it reads,

If I have a book to serve as my understanding, a pastor to serve as my conscience, a physician to determine my diet for me, and so on, I need not exert myself at all. I need not think, if only I can pay: others will readily undertake the irksome work for me. The guardians who have so benevolently taken over the supervision of men have carefully seen to it that the far greatest part of them (including the entire fair sex) regard taking the step to maturity as very dangerous, not to mention difficult. Having first made their domestic livestock dumb, and having carefully made sure that these docile creatures will not take a single step without the go-cart to which they are harnessed, these guardians then show them the danger that threatens them, should they attempt to walk alone.

Yesterday, I wrote a post on the Mason-Stothers theorem and presented an elementary proof of the theorem given by Noah Snyder. As mentioned in that post, I will present now a problem proposed by Magkos Athanasios (Kozani, Greece) that can be solved almost “effortlessly” using the aforesaid theorem.

Problem: Let $f$ and $g$ be polynomials with complex coefficients and let $a \ne 0$ be a complex number. Prove that if

$(f(x))^3 = (g(x))^2 + a$

for all $x \in \mathbb{C}$, then the polynomials $f$ and $g$ are constants.

(Magkos Athanasios)

Solution: First, note that if $f$ is a constant, then this forces $g$ to be a constant, and vice-versa. Now, suppose $f$ and $g$ are not constants. We show that this leads to a contradiction.

Observe that if $f$ and $g$ have a common root, say, $\alpha$, then we have $(f(\alpha))^3 = (g(\alpha))^2 + a$, which implies $0 = 0 + a$, which implies $a = 0$, a contradiction. Therefore, we conclude $f, g$ and $a$ are relatively prime polynomials, and hence, $f^3, g^2$ and $a$ are also relatively prime. Now, let $\deg (f) = n$ and $\deg (g) = m$. Then, from the given equation, we conclude $n = 2k$ and $m = 3k$ for some $k \in \mathbb{N}$.

So,

$\max \{\deg(f^3), \deg(-g^2), \deg(a)\} = \max \{6k, 6k, 0\} = 6k$.

Also,

$N_0 (f^3 (-g^2) a) - 1$

$= N_0 (fg) - 1 \le \deg (f) + \deg(g) - 1 = 2k + 3k - 1 = 5k - 1$.

Now, applying the Mason-Stothers theorem, we get

$6k \le 5k - 1$, which implies $k \le -1$, a contradiction! And, we are done.

• 302,871 hits