Monthly Archives: April 2015

The Sieve — elementary combinatorial applications

One powerful tool in the theory of enumeration as well as in prime number theory is the inclusion-exclusion principle (sieve of Erathosthenes). This relates the cardinality of the union of certain sets to  the cardinalities of the intersections of some of them, these latter cardinalities often being easier to handle. However, the formula does have some handicaps, it contains terms alternating in sign, and in general it has too many of them!

A natural setting for the sieve is in the language of probability theory. Of course, this only means a division by the cardinality of the underlying set, but it has the advantage that independence of occurring events can be defined. Situations in which events are almost independent are extremely important in number theory and also arise in certain combinatorial applications. Number theorists have developed ingenious methods to estimate the formula when the events (usually divisibility by certain primes) are almost independent. We give here the combinatorial background of some of these methods. Their actual use, however, rests upon complicated number theoretic considerations which are here illustrated only by two problems.

It should be emphasized that the sieve formula has many applications in quite different situations.

A beautiful general theory of inclusion-exclusion, usually referred to as the theory of the Mobius function is due to L. Weisner, P. Hall and G. C. Rota.

Question 1: In a high school class of 30 pupils, 12 pupils like mathematics, 14 like physics and 18 chemistry, 5 pupils like both mathematics and physics, 7 both physics and chemistry, 4 pupils like mathematics and chemistry. There are 3 who like all three subjects. How many pupils do not like any of them?

Question 2: (a) The Sieve Formula: 

Let A_{1}, \ldots, A_{n} be arbitrary events of a probability space (\Omega, P). For each

I \subseteq \{ 1, \ldots , n\}, let

A_{I}= \prod_{i\in I}A_{i}, A_{\phi}=\Omega

and let \sigma_{k}=\sum_{|I|=k}P(A_{I}), \sigma_{0}=1

Then, P(A_{1}+\ldots + A_{n})=\sum_{j=1}^{n}(-1)^{j-1}\sigma_{j}

Question 2: (b) (Inclusion-Exclusion Formula)

Let A_{1}, \ldots, A_{n} \subseteq S, where S is a finite set, and let

A_{I}=\bigcap_{ j \in J}A_{j}, A_{\phi}=S. Then,

|S-(A_{1}\cup \ldots \cup A_{n})|=\sum_{J \subset \{ 1, \ldots n\}}(-1)^{|I|}|A_{I}|

Hints:

1) The number of pupils who like mathematics or physics is not 12+14. By how much is 26 too  large?

2) Determine the contribution of any atom of the Boolean Algebra generated by A_{1},, \ldots A_{n} on each side.

Solutions.

1) Let us subtract from 30 the number of pupils who like mathematics, physics, chemistry, respectively:

30-12-14-13.

This way, however, a student who likes both mathematics and physics is subtracted twice; so we have to add them back, and also for the other pairs of subjects:

30-12-14-13+5+7+4.

There is still trouble with those who like all three subjects. They were subtracted 3 times, but back 3 times, so we have to subtract them once more to get the result:

30-12-14-13+5+7+4-3=4/

2) (a) Let B=A_{1}A_{2}\ldots A_{k}\overline A_{k+1}\ldots \overline A_{n}

be any atom of the Boolean algebra generated by A_{1}, A_{2}, \ldots A_{n} (with an appropriate choice of indices, every atom has such a form.) Every event in the formula is the union of certain (disjoint) atoms; let us express each P(A_{I}) and P(A_{1}+A_{2}+\ldots +A_{n}) as the sum of the probabilities of the corresponding atoms. We show that the probability of any given atom cancels out.

The coefficient of P(B) on the left hand side is

1, if k \neq 0 and 0, if k=0

B occurs in A_{I} if I \subseteq \{ 1, \ldots k\}. so its coefficient on the right hand side is

\sum_{j=1}^{k}\left( \begin{array}{c}    k \\    j \end{array} \right) (-1)^{j}=1-(1-1)^{k}=1, k \neq 04, and latex 0 if k =0$.

Thus, P(B) has the same coefficient on both sides, which proves part a.

Solution (b):

Choose an element x of S by a uniform distribution. Then, A_{i} can be identified with the event that

x \in A_{I}, and we have

P(A_{i})=\frac{|A_{i}|}{|S|}

So, we have, by the above,

P(A_{1}+A_{2}+\ldots + A_{n})=\sum_{j=1}^{n}(-1)^{j-1}\sum_{|I|=j}\frac{|A_{I}|}{|S|}, where

\sum_{\phi \neq I \subseteq \{ 1, \ldots n\} }(-1)^{|I|-1}\frac{A_{I}}{|S|}, or equivalently

P(\overline{A_{1}}\ldots \overline{A_{n}})=1-P(A_{1}+\ldots + A_{n}), which in turn equals,

1- \sum_{\phi \neq I \subseteq \{ 1, \ldots , n\}}(-1)^{|I|-1}\frac{|A|}{|S|}

The assertion (b) follows on multiplying by |S|.

More later,

Nalin Pithwa

Mathematical Career — Do you love Math as vocation and would you like to make it your profession

Feature Column.

Jensen’s inequality and trigonometry

The problem of maximizing \cos{A}+\cos{B}+\cos{C} subject to  the constraints A \geq 0,

B \geq 0, C \geq 0 and A+B+C=\pi can be done if instead of the AM-GM inequality we use a stronger inequality, called Jensen’s inequality. It is stated as follows:

Theorem. 

Suppose h(x) is a twice differentiable, real-valued function on an interval [a,b] and that h^{''}(x)>0 for all a<x<b. Then, for every positive integer m and for all points x_{1}, x_{2}, \ldots x_{m} in [a,b], we have

h(\frac{x_{1}+x_{2}+\ldots+x_{m}}{m}) \leq \frac{h(x_{1})+h(x_{2})+h(x_{3})+\ldots+h(x_{m})}{m}

Moreover, equality holds if and only if x_{1}=x_{2}=\ldots=x_{m}. A similar result holds if

h^{''}(x)<0 for all a<x<b except that the inequality sign is reversed.

What this means is that the value of assumed by the function h at the arithmetic mean of a given set of points in the interval [a,b] cannot exceed the arithmetic mean of the values assumed by h at these points, More compactly, the value at a mean is at most the mean of values if h^{''} is positive in the open interval (a,b) and the value at a mean is at least the mean of values if h^{''} is negative on it. (Note that h^{''} is allowed to vanish at one or both the end-points of the interval [a,b].)

A special case of Jensen’s inequality is the AM-GM inequality.

Jensen’s inequality can also be used to give easier proofs of certain other trigonometric inequalities whose direct proofs are either difficult or clumsy. For example, applying Jensen’s inequality to the function h(x)=\sin{x} on the interval [0,\pi] one gets the following result. (IITJEE 1997)

If n is a positive integer and 0<A_{i}<\pi for i=1,2,\ldots, n, then

\sin{A_{1}}+\sin{A_{2}}+\ldots+\sin{A_{n}} \leq n \sin{(\frac{A_{1}+A_{2}+\ldots+A_{n}}{n})}.

More later,

Nalin Pithwa