Fruits of procrastination

Month: August, 2013

My first attempt at solving the Lonely Runner Conjecture

Let us suppose there are k runners running at speeds 0<a_1<a_2<\dots<a_k around a field of circumference 1. Take any runner from the k runners- say r_i, who runs with speed a_i. Say we pair him up with another runner r_j who runs with speed a_j. Then for time 0\leq t\leq\frac{1}{2|a_i-a_j|}, the distance between them is |a_i-a_j|t, and for \frac{1}{2|a_i-a_j|}\leq t\leq \frac{1}{|a_i-a_j|}, the distance between them is 1-|a_i-a_j|t.

The Lonely Runner Conjecture can be stated in the following way: there exists a time t such that \min\left[\min\{|a_i-a_1|t_1,1-|a_i-a_1|t_1\},\min\{|a_i-a_2|t_2,1-|a_i-a_2|t_2\},\dots,\min\{|a_i-a_k|t_k,1-|a_i-a_k|t_k\}\right]\geq\frac{1}{k}.

Here t_1,t_2,t_3,\dots,t_k are the smallest positive values found after successively determining t_x-n\frac{1}{|a_i-a_x|}, where x\in\{1,2,3,\dots k\}\setminus\{i\}, and n\in\Bbb{Z}^+

Proofs of Sylow’s Theorems in Group Theory- Part 1

I will try to give a breakdown of the proof of Sylow’s theorems in group theory. These theorems can be tricky to understand, and especially retain even if you’ve understood the basic line of argument.

1. Sylow’s First Theorem- If for a prime number p, o(G)=p^km, and p\nmid m, then there is a subgroup H\leq G such that o(H)=p^k.

First we will try to understand what an orbit of a group is. Take a set S, and a group G. S does not necessarily have to be a subset of G. Orbit(S)=\{gs|s\in S, g\in G\}. Note that this is right multiplication.

Stabilizer(S)=\{g\in G|gs=s\}.

Now the Orbit-Stabilizer Theorem- $|Orbit||Stabilizer|=|Group|$. Something to remember from this is that there is nothing special about this theorem. It is just another way of saying $|Image||Kernel|=|Group|$, as derived from the First Isomorphism Theorem.

The stabilizer of a set S is a subgroup. Proof: Let as=s and bs=s. Then abs=as=s. Also, if as=s, then taking left inverse on both sides, a^{-1}s=s.

Now we move to a combinatorial argument: what power of p divides {p^km\choose p^k}? On expanding, we get \displaystyle{\frac{p^km(p^km-1)(p^km-2)\dots (p^km-p^k+1)}{1,2,3\dots p^k}}=m\displaystyle{\Pi}_{j=1}^{p^k-1}\frac{p^km-j}{p^k-j}. The highest power of p that can divide j is \leq k-1. Hence, the power of p that divides p^k-j is the same that which divides p^km-j. In fact, p does not have to be prime for this property to be true. More generally speaking, just to gain a feel for this kind of argument, provided j\leq p^k-1, the fraction of the form \frac{a-j}{b-j} not be divided by any power of p except for 1, as long as both a and b are divisible by powers of p greater than or equal to k. j is clearly the constraint here. Remember that p\nmid m is a necessary condition for this.

Now we prove {p^km\choose p^k}\equiv m  (mod p).

Now we will define the set S to contain all subsets of G with p^k elements. Clearly, |S|={p^km\choose p^k}, which as shown above is not divisible by p. Take every g\in G, and multiply it with every element of S. Note that very element of S is itself a set containing p^k elements of G. If S_i\in S, then gS_i\in S. Moreover, equivalence classes are formed when all elements of G are multiplied with all elements of S, and these equivalence classes partition S. The proof of this: let GS_i be the orbit of S_i. Then if S_k\in Orb(S_i), gS_i=S_k. Moreover, if S_l\in S=g'S_i, then g'g^{-1}S_k=S_l. This gives a feel for why these objects of S are all in the same class.

Let there be r such partitions of S. Then |S|=|S_1|+|S_2|+\dots+|S_r|, where S_1,S_2,etc are partitions of S. We know |S| is not divisible by p. Hence, there has to be at least one |S_k| which is not divisible by p. Let S_k\in [S_k], where [S_k] is an equivalence class partitioning S. Consider a mapping f:G\to S_k such that f(g)=gS_k. The image is [S_k], and the kernel is the stabilizer. By the orbit-stabilizer theorem, |G|=|Stabilizer||Orbit|. We know that the orbit is not divisible by p^k. Hence, the stabilizer has to be divisible by p^k. Also, the stabilizer is a subgroup.

The rest of the proof will be continued next time.

Today, I will discuss this research paper by Javed Ali, Professor of Topology and Analysis, BITS Pilani.

What exactly is a proximinal set? It is the set of elements X in which for any x\in X, you can find the nearest point(s) to it in X. More formally, for each x\in X, \exists y\in X such that d(x,y)=\inf \{d(x,K)\}.

This article says a Banach space is a complete vector space with a norm. One might find the difference between a complete metric space and a complete vector space to be minimal. However, the difference that is crucial here is that not every metric space is a vector space. For example, let (X,d) be a metric space, satisfying the relevant axioms. However, for x,y\in X, x+y not being defined is possible. However, if X is a vector space, then $x+y\in X$. Hence, every normed vector space is a metric space if one were to define \|x-y\|=d(x,y), but the converse is not necessarily true.

What is a convex set? This article says a convex set is one in which a line joining any two points in the set lies entirely inside the set. But how can a set containing points contain a line? Essentially, the the convex property implies that every point the line passes through is contained within the convex space. Convexity introduces a geometrical flavor to Banach spaces. It is difficult to imagine what such a line segment would be in the Banach space of matrices (with the norm \|\mathbf{A}-\mathbf{B}\|=\mathbf{A}-\mathbf{B}.

What is a uniformly convex set? This paper says that a uniform convex space is defined thus: \forall<\epsilon\leq 2\in\Bbb{R}, \exists \delta(\epsilon)>0 such that for \|x\|=\|y\|=1 and \|x-y\|\geq \epsilon, \frac{\|x+y\|}{2}\leq 1-\delta(\epsilon). Multiplying by -1 on both sides, we get 1- \frac{\|x+y\|}{2}\geq \delta(\epsilon). What does this actually mean? The first condition implies that x and y cannot lie in the same direction. Hence, \|x+y\|<2. As a result, we get \left\|\frac{x+y}{2}\right\|<1, or 1-\left\|\frac{x+y}{2}\right\|>0. As \delta(\epsilon)>0, and as 1-\left\|\frac{x+y}{2}\right\| is bounded, \delta(\epsilon) can be the lower bound of 1-\left\|\frac{x+y}{2}\right\|.

But what is uniform about this condition? It is the fact that \delta(\epsilon) does not change with the unit vector being considered, and depends only on \epsilon.

Now we go on to prove that every closed convex set of every uniformly convex Banach space is proximinal.

This is the second time I’m checking whether I can write a LATEX equation in wordpress.


o(HK)=\frac{o(H)o(K)}{o(H\cap K)}

Why I have nothing better to do than blog :(

After trying to follow blogs by various mathematicians, I have concluded that having a digital presence is pretty darned cool and useful in academia! Hence, in my pursuit of the forever-elusive elixir of “cool”, I have decided to record my progress in Algebraic Geometry through this blog. I’m no expert. But I feel trying to explain concepts to others promotes a higher degree of clarity than self-study, athough this is debatable and most definitely a grey area.

I really do hope Math enthusiasts find this blog to be a useful spot for better explanations of convoluted geometrical/algebraic concepts.

And reaffirm that beneath all the daunting machinery, Math is so simple and beautiful.