cozilikethinking

4 out of 5 dentists recommend this WordPress.com site

Effective Altruism- May

I turned *way too old* earlier this month. Hence, on my birthday month, I would like to record the donation I made to Effective Altruism:

Screen Shot 2019-05-13 at 5.54.44 PM

I have also started reading on poverty in India. The first paper that I perused (very) partially is this.

It is a paper written by two Indian PhD students at Columbia University, who talk about the fact that there are basically two poverty lines used by the government of India. The latest one is in fact a harsher scale of poverty, and according to both such lines poverty in India has been steadily decreasing, especially in the 2004-2005 and the 2009-2010 period. The authors do not use the 5-year studies on poverty as a basis for their conclusions, but the annual expenditure survey done by the government of India. The basis for their choice is the following: people who spend more are probably earning more, and vice-versa. Hence, whether people are above or below the poverty line can be easily approximated by how much they’re spending.

I didn’t complete reading the paper for the following reasons: it seems motivated at the very outset to show that India is “shining”, it is more an instance of statistical jugglery than a commentary on the causes of poverty, and bases its conclusions on poverty lines that I don’t take to be credible. Every government is motivated to suppress data on poverty, or introduce measures of poverty that suggests that there are less poor people in their country than there really are. And I find the two poverty lines to not be a good measure for poverty in India.

I then found this book written up by people at the World Bank.

I will try to peruse relevant sections of this book and complete this article by (hopefully) this weekend

Putnam 1994, Question 1

Just want to record a solution to a relatively simple Putnam problem here. The problem is the following:

Show that a sequence a_1,a_2,a_2,\dots satisfies the condition 0<a_n\leq a_{2n}+a_{2n+1}. Prove that \sum a_i diverges.

I tried attacking it with the usual methods of showing that a sequence diverges, but nothing seemed to work. However, every good Olympiad worth its salt asks for some experimentation, which will then yield important observations/patterns. I did the same here.

Without loss of generality, let a_1=1. Then a_2+a_3\geq a_1=1. Hence, a_2+a_3\geq 1. Similary, a_4+a_5\geq a_2 and a_6+a_7\geq a_3. Therefore, a_4+a_5+a_6+a_7\geq a_2+a_3\geq 1. Continuing this pattern, we observe that for all n\in\Bbb{N}, a_{2^n}+\dots+a_{2^{n+1}-1}\geq 1. Hence \sum a_i, which can be thought of as \sum\limits_{n=1}^{\infty}(a_{2^n}+\dots+a_{2^{n+1}-1}), diverges.

Effective Altruism- April

Screen Shot 2019-04-16 at 9.23.23 AM

Recording my donation here for April. This was an eventful month, as I was part of a team that organized a massive fundraising event in State College. Minor glitches notwithstanding, it was an enriching experience.

This post will be updated soon with some views on child malnutrition in India.

A cute combinatorial identity

Just wanted to record a cute combinatorial argument. Prove that      \sum\limits_{i=0}^n {n\choose i} {i\choose m}= {n\choose m} 2^{n-m}

I read this formula in the article “Pascal functions” in “The American Mathematical Monthly”.

They prove it using the new machinery of Pascal functions that they develop in the article. I tried proving it using an algebraic argument, but couldn’t find the right formulation. I could finally prove it using a combinatorial argument, which I have explained below:

The left hand side counts the number of ways of first selecting i items from n items, and then selecting m items from those already-selected i items. Obviously, for i<m, this does not make sense. Hence, {i\choose m}=0 in those cases. For i\geq m, the above interpretation is valid.

We can interpret the right hand side as the number of ways of selecting m items from n items, and then going to each of the left-over items (there are n-m of them) and deciding if they had been pre-selected or not. Here pre-selection implies being selected amongst the i items, out of which the final m items have been chose.

Hence, the right hand side equals the left hand side.

Some solutions

I solved two math problems today. The solutions to both were uniquely disappointing.

The first problem was the first problem from IMO 1986:

Let d be a number that is not 2,5 or 13. Prove that out of the set \{2,5,13,d\}, we can select two different numbers a,b such that ab-1 is not a square.

A quick check would show that 2.5-1, 2.13-2 and 5.13-1 are all squares. This shows that of the two numbers that we select from \{2,5,13,d\}, one of them has to be d. We essentially need to prove that for d\neq 2,5,13, 2d-1, 5d-1 and 13d-1 are not all squares (a maximum of two of them might be. But all three cannot).

I tried figuring out some of the implications of all of them being squares, but couldn’t come up with anything concrete, as I didn’t write anything at all, and just tried to devise a strategy mentally. Ultimately, I came up with possibly the most mundane proof of all time.

Proof: Consider squares \mod 16 (I couldn’t come up with any contradiction up until \mod 8). The possible residues for squares \mod 16 are 0,1,4,9. Now my strategy was to plug in all possible residues \mod 16 in place of d, and checking that in every such instance, at least one of 2d-1, 5d-1 and 16d-1 gave a residue that was not 0,1,4,9\mod 16. This I could successfully verify. Hence proved.

The solution that I could find in the IMO compendium was much smarter, but involved some algebra that would obviously involve putting pen to paper.

The second question that I solved today was proving the Koszul formula, which states that

2g(\nabla_X Y,Z)=D_Xg(Y,Z)+D_Yg(X,Z)-D_Zg(X,Y)-g([Y,X],Z)-g([X,Z],Y)+g([Z,Y],X)

I’d seen proofs before in textbooks, that would involve writing down expansions, and then combining all of them in some clever way. The way that I came up with was pretty algorithmic, and perhaps even more elementary. It is simply the following: Take g(\nabla_X Y,Z). Use the torsion free condition to write it as g(\nabla_Y X,Z)+g([X,Y],Z). Now use the formula for connection acting on a tensor to write g(\nabla_Y X,Z) as D_Y g(X,Z)-g(X,\nabla_Y Z). Performing the two operations, we have D_Yg(X,Z)-g(X,\nabla_Y Z)+g([X,Y],Z). Performing this operation of first using the torsion free condition and then the formula for a connection on a tensor three times, we get the Koszul formula.

Effective Altruism – March

I’m recording the payment I made to Effective Altruism in the month of March, to keep my pledge of donating 10% of my lifetime income to it.

Screen Shot 2019-03-08 at 10.24.55 AM

I had said that I’ll soon write an article about causes that concern me/that I want to make monetary contributions to. Some articles that I read in the recent past are the wiki article on poverty in India, sexual injustice in rural India, and also Tolstoy’s views on charity and religion (which for sure have changed the world. For starters, Gandhi pretty much took all of his views and practices from Tolstoy, almost verbatim, which of course decided the course for Indian self-determination). However, I feel that I have not read enough to write anything original/meaningful. Hopefully this will change by next month.

Here’s a slightly badly written proof to a competitive math problem. I guess I could expand it slightly if readers find it unreadable.

The following is a question from the International Mathematics Competition, 1994.

Prove that in any set S of 2n-1 different irrational numbers, there exist n irrational numbers \{s_1\dots,s_n\} such that for any \{a_1,\dots,a_n\}\in \Bbb{Q} such that

(1)  a_i\geq 0,\forall i\in\{1,\dots,n\} and (2)  \sum\limits_k a_k>0
\sum\limits_{i=1}^n a_is_i is also irrational.

Proof: We will prove this by induction. This is obviously true for n=1. Now let us assume that this is also true for n. We shall now prove the case for n+1: that amongst any 2(n+1)-1 different irrational numbers, there exist n+1 numbers such that the given condition is satisfied. We will prove this by contradiction. Let us call this 2(n+1)-1 element set A_{n+1}.
Remove any two elements from A_{n+1}. We get 2n-1 elements. By the inductive hypothesis, there exist n elements \{s_1,\dots,s_n\} such that for any \{a_1,\dots,a_n\} non-negative rational numbers amongst which at least one is strictly positive, \sum\limits_{i=1}^n a_is_i is irrational. Let us call this set of elements S_n. Now one by one, add each element of A_{n+1}\setminus S_n, to S_n to form n+1 element sets. If each of these n+1 element sets can be put into some linear combination to give us a rational number, then we can subtract the right rational linear combination of A_{n+1}\setminus S_n (which by our assumption should also be rational) to give us S_n back, which should again be a rational number. But that is a contradiction. Hence, there has to exist an n+1 tuple of elements in A_{n+1} too such that no linear combination with non-negative rational coefficients, such that at least one coefficient is positive, can give us a rational number.

Effective Altruism

The reason that I’m writing this non-mathematical post here is that I want to help spread the word about this fantastic organization. I also heard about it in Vipul Naik’s blog.

I decided to start donating to Effective Altruism December last year. It is an organization that does research on the most effective ways to donate money, and then makes suggestions based on where one might want to donate. Typically, it asks its members to pledge 10% of their lifetime income to such causes.

I was initially introduced to Effective Altruism by some of my math heroes like Vipul Naik. Some causes that facilitated my joining this organization were that I now have a disposable income through a monthly stipend, not all of which I spend, and that I’ve gotten increasingly involved in fundraising at my university through various organizations, and find my involvement to be meaningful and fulfilling.

Below is the screenshot of my donation for this month. I shall soon update this blog with details of the specific organizations linked with EA that are doing amazing work, especially organizations that are fighting malaria/other preventable diseases in Africa and other parts of the world.

Screen Shot 2019-02-07 at 12.19.12 AM

Math Olympiads #1

I’ve been obsessed with Math Olympiads and other kinds of competitive math for a loong time now. Although I should be doing more serious mathematics now that can actually get me a job, I shall ignore good sense and start my series of posts on Math Olympiad problems!

The first problem that I want to write about is a relatively easy one from IMO (International Math Olympiad) 1974. I think it was a long-listed problem, and didn’t actually make it to the test. It asks to prove the fact that

\displaystyle 343|2^{147}-1

(that 343 divides 2^{147}-1)

The important thing in this problem is to figure out that 343=7^3 and 147=3.7^2. Hence, we’re being asked to prove that 7^3|2^{3.7^2}-1.

We have the following theorem for reference: If a and b are co-prime, then a^{\phi(b)}\equiv 1\pmod b, where \phi(b) is the number of natural numbers that are co-prime with b. Fermat’s Little Theorem is a special case of this.

Now on to the calculations and number crunching. We have fleshed out the main idea that we’ll use to attack the problem. We can see that \phi(7^3)=7^3-7^3/7=6.7^2. Hence, as 2 is co-prime with 7^3, 2^{6.7^2}-1\equiv 0\pmod {7^3}. We can factorize this as (2^{3.7^2}+1)(2^{3.7^2}-1)\equiv 0\pmod {7^3}. Now we have to prove that 7^3 does not have any factors in common with 2^{3.7^2}+1. As 2^3\equiv 1\pmod 7, 2^{3.7^2}\equiv 1\pmod 7 too. Hence, 2^{3.7^2}+1\equiv 2\pmod 7. This shows that 2^{3.7^2}+1 does not have any factors in common with 7^3, and leads us to conclude that 7^3|(2^{3.7^2}-1), or 343|2^{147}-1. Hence proved.

I realize that the formatting is pretty spotty. I shall try and re-edit this in the near future to make it more readable.

 

The Möbius strip

Almost every Math student (or even otherwise) has heard of the Möbius strip at least once in their career. I too have. Embarrassingly, I always had my doubts about it. And I can bet that a lot of people have the same problem.

A Möbius strip is almost always taught in the following “intuitive way”: take a long, thin strip of paper, and connect the opposite ends along the length in such a way that one end is oriented in the opposite direction as compared to the other end. You get something that looks like the picture below:

Paper mobius strip

And when you take an object, say a pen cap around the Möbius strip, you’re somehow supposed to believe that the pen cap returns to the same spot as before, but with the opposite orientation. But you (or at least I) would think “No!! The pen cap has not returned to the original starting point! It is at the other side of the piece of paper! Points at opposite sides of the paper can’t be the same point!”

As I grew older, I decided to exorcise my demons, and think about these seemingly fundamental concepts that I had accepted, but not really understood. And I have arrived upon the conclusion that the paper model is completely wrong, at least to convey the essence of the Möbius strip. A much much more convincing model is the following:

Mobius strip

Imagine a coin that is traveling from top to bottom. The coin is colored in the following way: the left side is red, and the right side is blue. After disappearing at the bottom, it re-emerges at the top, but now its left side is blue, and its right side is red. This picture is much much clearer to me than paper strips forming loops.

Thus ends my spiel for the day!