Discovering Math

November 8, 2009

Proving the Cauchy-Schwarz Inequality

The inequality states:

$a_1b_1+a_2b_2 +.. a_nb_n <= \sqrt (a_1^2+ ..+a_n^2)\sqrt(b_1^2+..+b_n^2)$ .

This is very easily proved by squaring both sides, and cancelling the common terms.

One gets the following on doing this:

$2\sum_{i\neq j}a_ib_ia_jb_j <= \sum_{i\neq j}a_i^2b_j^2$ .

For every pair of indices i & j, we can take the two same terms from the RHS and put them onto the LHS, creating a sequence of sum of squares whose generic term is:

$a_i^2b_j^2+a_j^2b_i^2-2a_ia_jb_ib_j = (a_ib_j-a_jb_i)^2$ .

The sum of squares of the above form for every i,j is clearly positive.

Hence the inequality is true.

October 19, 2009

(a,b) =d –> (ka,kb) = kd

If $(a,b) = d$ , then for some $x_1, y_1, ax_1+by_1=d$ .

Now to evaluate $(ka,kb)$ , we know that for some $x_2, y_2, kax_2+kay_2 = d^{'}$ .

Thus, we have $k|d^{'}$ .

Thus, we have $kd^{''} = d^{'}$ . This implies that $mkd^{''} = ka$ , for some m. Thus, we have $d^{''} | a and d^{''} |b$ . Therefore, since the GCD has to be the maximal divisor, $d^{''} = d$ , otherwise, a new maximal divisor could be created either for (a,b) or (ka,kb).

October 17, 2009

Math Overflow

Great to see a site that’s modelled on www.stackoverflow.com.

I’ve posted my first question here: http://mathoverflow.net/questions/840/the-core-question-of-topology

October 11, 2009

Topology Review

Definitions

Simplex: Given $k+1$ points in general position, the smallest convex set containing these points is known as the k-Simplex, i.e. points on the simplex are represented as $\sum_{i=0}^{n} \lambda_i v_i$ with $\sum \lambda_i = 1$ .

i.e. the 0-simplex is a point, the 1-simplex is a line, the 2-simplex is a triangle, and the 3-simplex is a tetrahedron.

General Position: $v_0..v_k$ are in general position if the vectors $v_1-v_0,v_2-v_0..v_k-v_0$ are linearly independent.

Thus, a rectangle (4 points) can’t be a simplex as the four points are not in general position.

Face: Simplex B is a face of Simplex A if the vertices of B form a subset of the vertices of A.

Simplicial Complex: A finite collection of simplices, such that any two simplices intersect in a common face, and all the faces of the simplices are contained in the simplical complex.

Triangulation: A triangulation of a topological space X consists of a homeomorphism $h:|K|-> X$ , where |K| is the simplicial complex K with the subspace topology.

Next to do:

1. Figure out exactly what Topology does! I have a good idea of the basics of point-set topology, but a very vague sense of what these tools can actually be used for.

2. Understand the exact differences between functions and spaces.

3. Examine barycentric coordinates & subdivision.

4. Basic triangulation theorems.

October 2, 2009

Proving the Mobius Inversion Formula

So for the last few days I’ve been trying to prove the Mobius Inversion formula:

If $f(n)= \sum_{d|n} g(d)$ , then

$g(n)= \sum_{d|n} \mu(d)f(n/d)$ .

The best way to get an intuitive understanding of this formula is to write out a few equations in long form.

For example, I worked out the values of $g(n)$ for various n.

The values for $g(1),g(p),g(p_1p_2)$ can easily be worked out.

It’s literally amazing to see how the signs in the worked out equations match up to exactly what one would get on applying the Mobius Function!

I thought the Mobius function seemed pretty useless, so it was exhilarating to see the connection between solving these equations and the Mobius Function.

For quite some time, I approached the proof in terms of trying to generalize my solution of the equations for $g(1),g(p)$ etc. However, that didn’t work.

However, yesterday, I started playing around with the formula itself to see what happens. As a first step, I started working with $\sum_{d|n} \mu(d)f(n/d)$ .

I rewrote this as $\sum_{ab=n} \mu(a) \sum_{m|b} g(m)$ . Say we define the identity function i(n) = 1, then we have the following equation

$\sum_{abd=n} \mu(a) g(b) i (d)$ .

This thus is equivalent to

$\sum_{ab|n} \mu(a)g(b)$ .

Now, say we keep b constant. Then, essentially, this boils down to

$g(b) \sum_{a|(n/b)} \mu(a)$ .

This sums to 0!

The only term left in the equation is g(n).

Thus we have the answer.

September 23, 2009

Man & Lion

A few months ago, I got hold of Bela Bollobas’ Art of Mathematics and was working through the ‘Man & Lion’ problem. This can be stated very simply: A lion and a man in a closed circular arena have equal maximum speeds. What tactics should the lion employ to be sure of his meal?

This is a surprisingly involved and deep problem that brings out some beautiful mathematics.

I was browsing through ArXiv the other day, and came across the following paper: http://arxiv.org/abs/0909.2524.

Lots of interesting sub-problems to work through here. Fascinating stuff!

September 3, 2009

Arbitrage Theorem – I

Say we have a set of mutually exclusive bets, $x_1,x_2,.. x_i$ that provide $r_1, r_2, .. r_i$ in returns.

Assume that we have $1 to wager. So

$\sum x_i =-1$

Assume that the occurence of an event is signified by an indicator variable. So if Event i happens, $e_i = 1$ , else $e_i = 0$ .

Therefore

$\sum e_i =1 with e_i \in \{{0,1}\}$ .

Now, essentially, the problem is to find the maximum value that is obtained by the following function:

$\sum -e_ix_ir_i$ .

Given that only one of the $e_i$ ’s is =1, this implies that $x_i = 1/r_i$ (finessing a fine point over a negative sign).

Thus, if we have $\sum 1/r_i =1$ , then there is no arbitrage.

Of course, all this is trivially true. I need to figure out a more interesting problem to think about here.

I think there’s a connection with information theory/compression in here somewhere. That could be one angle to consider.

Discovering Math

Proving the Cauchy-Schwarz Inequality

(a,b) =d –> (ka,kb) = kd

Math Overflow

Topology Review

Proving the Mobius Inversion Formula

Man & Lion

Arbitrage Theorem – I

Recent Posts

Categories

Archives

Follow “Discovering Math”