Tag Archives: English

Want to Fight Climate Change? Don’t Waste Food

source: http://res.publicdomainfiles.com/pdf_view/152/13985772022293.jpg

A few days ago, my roommate and I were getting dinner at an Japanese restaurant. While we waited for food, we were having a brief discussion about the recent heat waves in Europe. Both of us felt very sad about these changes.

It was more upsetting to realize that the summers are going to be even hotter in the upcoming years. The climate of our planet is changing at an alarming rate. Earth is literally dying and nobody is doing anything meaningful about it.

Since then, I have talked with several other friends and realized that most of us feel the same way. We want to fight climate change, but our skillset and socio-economic condition are a very poor match to tackle this problem. For instance, most of us don’t own cars. We can’t help in preventing deforestation. We can’t donate any meaningful sum of money from our limited college student budgets.

So, what can we do? I thought about it for a while. I think I found a reasonable solution: we need to stop wasting food.

It should be noted that there are more efficient ways to fight climate change, but they are more demanding. For instance, turning off air conditioning for an hour every week is probably much more impactful, but most people will not be willing to participate in such a program. In contrast, reducing food waste is way easier.

Why This Matters?

You’ll be surprised to know the environmental impact of food waste.

Globally,  one third of the food produced is never eaten. [2] It contributes to 8 percent of total greenhouse gas emissions. If food waste were a country, it would come in third after the United States and China in terms of impact on global warming. [3]

An average american wastes upto 0.8 lbs (360g) of food per day or 290 lbs (131 kilograms) of food per year. [1] If you can prevent that, you might be able to save as much as $2275 per year. [2]

Limiting (even preventing) food waste is surprisingly easy. All you need to do is to eat everything you buy. For instance, take note of how much of each grocery item you use throughout the week. Do not buy more than that next time you do grocery shopping.

If you go to a restaurant, ask the waitress about serving portions. If you think there will be too much food, share with your friend. (This is especially true for buffet style restaurants and dining halls in residential dorms. I know of a sushi buffet in Boston that charges extra if customers leave their plates unfinished.)

Last but not least, never waste meat. Keep in mind that the meat on your plate comes from alive animals. Throwing away the meat is probably the most inconsiderate thing you can do to those poor animals that just died for you.

Hope you enjoy and finish your dinner next time!

References

  1. https://www.forbes.com/sites/christinatroitino/2018/04/23/americans-waste-about-a-pound-of-food-a-day-usda-study-finds/#497516b54ec3
  2. https://olioex.com/food-waste/food-waste-facts/
  3. https://www.washingtonpost.com/news/theworldpost/wp/2018/07/31/food-waste/?utm_term=.8f42041f3b2f

A Week of Poetry: Day 3

Sonnet 130

By William Shakespeare

My mistress’ eyes are nothing like the sun;
Coral is far more red than her lips’ red;
If snow be white, why then her breasts are dun;
If hairs be wires, black wires grow on her head.
I have seen roses damask’d, red and white,
But no such roses see I in her cheeks;
And in some perfumes is there more delight
Than in the breath that from my mistress reeks.
I love to hear her speak, yet well I know
That music hath a far more pleasing sound;
I grant I never saw a goddess go;
My mistress, when she walks, treads on the ground:
And yet, by heaven, I think my love as rare
As any she belied with false compare.

A Week of Poetry: Day 2

The Road Not Taken

By Robert Frost

Two roads diverged in a yellow wood,
And sorry I could not travel both
And be one traveler, long I stood
And looked down one as far as I could
To where it bent in the undergrowth;

Then took the other, as just as fair,
And having perhaps the better claim,
Because it was grassy and wanted wear;
Though as for that the passing there
Had worn them really about the same,

And both that morning equally lay
In leaves no step had trodden black.
Oh, I kept the first for another day!
Yet knowing how way leads on to way,
I doubted if I should ever come back.

I shall be telling this with a sigh
Somewhere ages and ages hence:
Two roads diverged in a wood, and I
I took the one less traveled by,
And that has made all the difference.

A Week of Poetry: Day 1

I love poetry. Did I ever tell you that? Not really.

I also enjoy world-building, philosophy, travelling to new places, but I never write about any of my experiences. I don’t write about myself much.

Twenty years later, when I’ll ask myself if I lived the life I dreamed for, I will need a definitive answer. The best way to do so would be to document all the interested things happen to me.

I’ll start with poetry. This week I’ll post some of my favorite poems. The first one would be Song of the Indian Maid by John Keats.

It’s a long poem like many of other Keats’s poems. The lines I like the most are the following:

To Sorrow
I bade good morrow,
And thought to leave her far away behind;
But cheerly, cheerly,
She loves me dearly;
She is so constant to me, and so kind:
I would deceive her
And so leave her,
But ah! she is so constant and so kind.

And also the following:

Young Stranger!
I’ve been a ranger
In search of pleasure throughout every clime;
Alas! ’tis not for me!
Bewitch’d I sure must be,
To lose in grieving all my maiden prime.

Come then, Sorrow,
Sweetest Sorrow!
Like an own babe I nurse thee on my breast:
I thought to leave thee,
And deceive thee,
But now of all the world I love thee best.

 

How Game of Thrones Should Have Ended

This is a very unusual post for this blog. I hope my regular readers will bear with me.

I love Game of Thrones. I have read the books and the companion novels. I have been following the series for years. I am familiar with most of the fan theories too. Tonight the series finale aired. I didn’t like how the show ended. It felt rushed and very baffling.

I understand that I don’t get to question the showrunners’ creative decisions about the show. However, as a fan I can disagree with them. This post is about how I feel the show should have ended. It was written in haste, so please forgive the typos and the repeating sentences.

Before I begin, please note that this article contains major spoilers. Read at your own risk.

The Long Night

In my honest opinion, the army of the living should have lost this fight. They should have retreated back to Iron Islands. However, this goes too far from the show’s ending, so I shall not pursue this thread. I shall try to modify the show’s version of the story so that it makes some sense.

The battle plan of the army of the living SUCKED. I won’t even try to justify it.

First of all, the cavalry charge was stupid. There are other articles on the internet suggesting better ways to use the Dothraki, so I’ll not get to it.  Secondly, if the army of the living wanted to defend the castle,  they should have also dug a wider, deeper trench around winterfell. The troops should be positioned behind the trench. In that way, the wights would not be able to cross the trench just by dropping some bodies. They would eventually fill in the trench, but it would require more time while they take damage. And when they do cross the trench, they would face fresh troops awaiting for them.

They should have manned the wall from the beginning, not when the wights are pursuing them.

In the show, the army of the living had catapults, but they got overrun only after throwing a couple of vollies. A more realistic solution would be to position the catapults inside the castle walls so that they may function for longer. Also, throwing jars full of wildfire, instead of rocks, might have been more effective since wights are susceptible to fire. (In fact, it was out of character for Tyrion not to suggest this strategy, after all, he had destroyed King Stanis’s fleet in the Blackwater Bay with wildfire.)

Nobody should have taken shelter in the Crypt. That’s where the Starks bury their dead. Someone should have spotted that!

Brianne Should have died in Jamie’s arms. Her character arc was complete.

Sansa should have died. She was useless throughout the entire story. Too bad, north needs a ruler.

In the show, the living were overwhelmed by Night King’s army. Night King was coming for Bran. At that point, out of desperation, Bran should have tried a new strategy. As we have seen in the Hodor story, warging in the past can affect the future. Inspired from this, he would try to go back thousands of years, when Night King was a human, and try to warg into him to stop the army of the dead at present. This would freeze the dead and white walkers for am moment, which is enough for Jon to rush and and stab the Night King. That would fulfil Jon’s role as the Azor Ahai.

Again, it should have been Jon who killed Night King. Otherwise, his resurrection has no importance, storywise.

As for Bran, altering past should have serious side-effects, as the previous Three Eyed Raven said,

The past is already written. The ink is dry.

He could get stuck in the past for good. Then, he could become Bran the Builder.

Rhaegal’s Death

The overpowered Scorpion plot had more holes than Swiss cheese. Someone calculated that the bolts needed to have an initial velocity of 2000m/s to make it happen. Also, the dragons are practically invulnerable in the air according to the books.

The show should have given Euron a dragon horn instead. These horns were used in Old Valeriya and are presumably capable of controlling dragons. Dany should have spotted Iron fleet from far above. Unknowing that Euron has a dragon horn, she would proceed to destroy the Iron fleet. When she was close enough, Euron would blow the horn and take control of both dragons. However, Dany should regain control of Drogon soon, because of special bond with him. Rhaegal would go berserk, attacking Dany’s ships and pursuing Drogon. Dany would have no choice but to kill Rhaegal with Drogon. That would be a devastating blow for both Dany and Drogon. She would mourn for Rhaegal and become more revengeful and destroy Euron’s fleet with remaining strength.

Destruction of King’s Landing

Jaime should accompany Dany, not to save Cersei, but to kill her. Suspecting Dany’s plan to burn everyone in King’s Landing, Tyrion would ask Jaime to secretly go to the Red Keep and convince Cersei to surrender. Jaime would do so, while Dany would attack the City’s defenses.

After meeting Jaime, Cersei would pretend to surrender. She would ring the bell and open the gates. When Dany’s troops get inside the walls, they would be greeted by common folk. Then the folk would suddenly attack Dany’s soldiers. It would become apparent that Cersei has hidden her soldiers among common folk and using them as a meat shield to slaughter Dany’s troops. There should also be archers in the buildings. Common folk would throw rocks at Dany and Drogon showing that she was undesirable. This would finally provoke Dany  and she would go on a rampage. She would also command Grey Worm to kill everyone who fought for Cersei.

On the other hand, seeing what Cersei had done, Jaime would finally choke Cersei, thus fulfilling Maggy the Frog’s prophecy.

The Ending

After witnessing the atrocities committed by Dany, Grey Worm and their army, Arya will finally kill Grey Worm and steal his face. Then she would get to Dany in the throne room and kill her. Seeing his mother dead, Drogon will burn Arya, melt the Iron Throne and fly away with Dany’s corpse.

Finally, Jon should become the king, with Tyrion becoming his hand. The post credit scene should show Night King is being reborn. (Implying that somehow the timeline has changed, which would provide the premise for HBO’s spin off.)

Prime Counting Function and Chebyshev Bounds

The distribution of primes plays a central role in number theory. The famous mathematician Gauss had conjectured that the number of primes between \(1\) and \(n\) is roughly \(n/\log n\). This estimation gets more and more accurate as \(n\to \infty\). We use \(\pi(n)\) to denote the number of primes between \(1\) and \(n\). So, mathematically, Gauss’s conjecture is equivalent to the claim

\[\lim_{n\to\infty}\frac{\pi(n)}{n/\log n}=1\]

This conjecture (currently known as the Prime Number Theorem) is notoriously difficult to prove. The first proof appeared almost a century after it was stated.

However, there are much simpler methods to bound \(\pi(n)\) above and below. Today I shall show such a bound that gives the correct order of magnitude for \(\pi(n)\) up to some constants. In particular, I shall prove that

\[(1+2\log 4)\frac{n}{\log n}\ge \pi(n)\ge \frac{\log 2}{2}\frac{n}{\log n}\]

for \(n\ge 12\). This proof technique is originally due to nineteenth century mathematician Pafnuty Chebyshev. He used a more complicated version of this technique to show that

\[1.1\frac{n}{\log n}\ge \pi(n)\ge 0.92\frac{n}{\log n}\]

for sufficiently large \(n\)s.

The Lower Bound

Suppose \(n\) is even, ie. \(n=2k\). Let us consider the prime factorization of \(\binom{2k}{k}\). All of its prime factors are between \(1\) and \(2k\). Therefore,

\[\binom{2k}{k}=p_1^{a_1}\cdots p_{\pi(2k)}^{a_{\pi(2k)}}\]

Claim: For every prime \(p_i\), \(p_i^{a_i}\leq 2k\)

Proof: We shall use this very simple identity \[\lfloor a+b\rfloor-\lfloor a\rfloor-\lfloor b\rfloor\leq1\]

It is well-known that the largest exponent of a prime dividing \(r!\) is

\[\left\lfloor\frac{r}{p_i}\right\rfloor+\left\lfloor\frac{r}{p_i^2}\right\rfloor+\cdots\]

Since \(\binom{2k}{k}=\frac{(2k)!}{(k!)^2}\), we have the following relationship

\begin{align}
a_i=&\left\lfloor\frac{2k}{p_i}\right\rfloor-2\left\lfloor\frac{k}{p_i}\right\rfloor+\left\lfloor\frac{2k}{p_i^2}\right\rfloor-2\left\lfloor\frac{k}{p_i^2}\right\rfloor+\cdots \\
&\leq 1+1+\cdots
\end{align}

Now there are as many \(1\)s as there are powers of \(p_i\leq 2k\). Hence, \(p_i^{a_i}\leq 2k\).

(Q.E.D)

So, we can conclude,

\[\binom{2k}{k}=p_1^{a_1}\cdots p_{\pi(2k)}^{a_{\pi(2k)}}\leq (2k)^{\pi(2k)}\]

It is easy to prove \(\binom{2k}{k}\ge 2^k\), hence

\[(2k)^{\pi(2k)}\ge 2^k\implies \pi(2k)\ge \frac{\log 2}{2}\cdot\frac{2k}{\log 2k}\]

The same bound can be derived for \(n=2k+1\) using \(\binom{2k+1}{k+1}\).  Therefore, the lower bound is

\[\boxed{\pi(n)\ge \frac{\log 2}{2}\cdot\frac{n}{\log n}}\]

The Upper Bound

Claim: For all \(n\ge 2\), \[\prod_{p\leq n\\ p\ \text{prime}}p\leq 4^n\]

Proof: We induct on \(n\). The base case trivially holds. \(n=2k-1\to 2k\) also holds because the product on the left hand side does not increment. So, we only need to prove \(n=2k\to 2k+1\)
\begin{align}
\prod_{p \leq 2k+1\\ p\ \text{prime}}p &= \prod_{p \leq k+1\\ p\ \text{prime}}p \cdot\prod_{k+2\leq p \leq 2k+1\\ p\ \text{prime}}p\\
&\leq 4^{k+1}\cdot \binom{2k+1}{k}\quad (1)
\end{align}
The first part of the product is \(\leq 4^{k+1}\) because of the inductive hypothesis. The second part is just the product of all the primes in between \(k+2\) and \(2k+1\). It’s easy to see that they all divide \(\binom{2k+1}{k}\), hence their product is \(\leq \binom{2k+1}{k}\).

It’s easy to show \(\binom{2k+1}{k}<4^k\). Substituting this bound back to (1) gives us

\[\prod_{p \leq 2k+1\\ p\ \text{prime}}p \leq 4^{k+1}\cdot 4^k=4^{2k+1}\quad (\text{Q.E.D.})\]

Now take a number \(2\leq m\leq n\). Consider the primes that are between \(m\) and \(n\). There are \(\pi(n)-\pi(m)\) of them, each of which is \(\ge m\). Consequently,

\[m^{\pi(n)-\pi(m)}\leq \prod_{m\leq p \leq n\\ p\ \text{prime}}p\leq \prod_{1\leq p \leq n\\ p\ \text{prime}}p\leq 4^n\]

Now take log of both sides

\[(\pi(n)-\pi(m))\log m\leq n\log 4\]

Rewrite this as

\[\pi(n)\leq \pi(m)+\frac{n\log 4}{\log m}\leq m+\frac{n\log 4}{\log m}\]

Set \(m=\frac{n}{\log n}\) and simplify the expression

\[\pi(n)\leq \frac{n}{\log n}\left(1+\frac{\log 4\cdot\log n}{\log(n/\log n)}\right)\]

Easy to show \(\frac{\log n}{\log(n/\log n)}\leq 2\) for \(n\ge 12\). (In fact you can show much tighter bound for sufficiently large \(n\).) Hence, the upper bound is

\[\boxed{\pi(n)\leq \left(1+2\log 4\right)\frac{n}{\log n}}\]

Lie Detectors and the Story of Halting Turing Machines

Is it possible to design a machine that detects lies? Sure, people have already built devices called polygraphs that monitor blood pressure, respiration, pulse etc. to determine if a person is giving false information. However, that is not same as “detecting lies” because polygraphs merely measure physical effects of telling lies. On the top of that, they are hella inaccurate. I am talking about REAL lie detectors, ie. machines that can instantly validate the statements themselves. Can we actually make such machines? (*insert new startup idea*)

Well, turns out if we ever could make such machines, they would become incredibly handy tools for scientists and mathematicians. That’s because they could babble all sorts of scientific and mathematical conjectures to such a machine, if it beeped, they would know those conjectures were false. Their conversation might go like this:

Crazy Physicist: Higgs Boson exists.
Machine: *Says Nothing*
Crazy Physicist: Ureka! I was right all along.

Computer Scientist: P=NP #changemymind
Machine: *beep*
Computer Scientist: OMG. P=/=NP. I just became a millionaire.

Clearly, you can see how these lie detectors would trivialize almost every known problem of science and mathematics. Then, a very legit question would be why nobody even tried to build such a machine. Indeed, humankind has spared far more effort after making junks like philosopher stones and elixir of life.

Turns out there is something fundamentally wrong about the design of the lie detectors. Before I get to the details, let me tell you a cool life hack. If you ever meet people that claim to be oracles, do this to them:

You: Will I offer you $10?

Whatever the oracle says, do the opposite.

This clearly shows the oracles cannot predict the future. The same thing is true for our lie detectors. Here is why:

Suppose you brought your friend Joe to show him the lie detector you bought. Now do the following:

You: I’m gonna hand Joe $10.

Whatever the lie detector says, do the opposite.

Therefore, just as above, our precious lie detectors cannot exist. However, they did have a purpose. They helped me to show you a proof technique called Cantor’s Diagonal Argument. It is a really nifty tool to prove many advanced statements in computability theory. Here is the general idea:

  • First you assume a machine with utterly unbelievable functions exists.
  • Then you come up for a statement or input for this machine using its own functions.
  • Finally, show that existence of such an input is contradictory to the existence of the machine itself.

As I’m running out of time, I’ll give you just one example of this technique. First proven by Alan Turing, it’s still one of the most famous proofs in computability theory.

Halting Turing Machine (HTM) is a special type of Turing machine that can instantly determine whether another Turing Machine halts on a specific input. In English, this means HTM is a cool app that can tell you whether one of the apps in your smartphone is gonna become unresponsive forever for a specific environment condition inside your smartphone. HTM would be a handy app, right? If HTM tells you an app is gonna be unresponsive beforehand, you’ll save time by not installing that crappy app. However, like all good things in computability theory, turns out HTM cannot exist either. This is because what if an evil developer created an app like this?

  • Give my app’s code and current environment condition of the smartphone to the HTM
  • Whatever the HTM says about my app, do the opposite inside the app.

Hence HTM is unable to predict what this evil dev’s app will do, and that’s why HTM cannot exist.

That’s it for today. I hope you enjoyed this blogpost. If you want to learn Computability Theory for real, I highly recommend Michael Sipser’s book.

A Special Case of Zsigmondy’s Theorem

Theorem (Zsigsmondy): 

  1. For two coprime positive integers \(a\) and \(b\) and for any positive integer \(n\), \(a^n-b^n\) has a prime divisor that does not divide \(a^k-b^k\) for all positive integers \(k< n\) with the following exceptions:
    • \(n = 2\) and \(a+b\) is a power of two.
    • \(n=6, a=2, b=1\).
  2. For two coprime positive integers \(a\) and \(b\) and for any positive integer \(n\), \(a^n+b^n\) has a prime divisor that does not divide \(a^k+b^k\) for all positive integers \(k< n\) with the following exception:
    • \(n=3, a=2, b=1\).

This theorem is very helpful in solving many olympiad number theory problems. However, its use is often frowned upon, as this theorem is quite hard to prove using only elementary mathematics. (I am aware of the proof using Cyclotomic Polynomials, but that’s not “elementary enough” in my opinion.)

In olympiad mathematics, one can get away in most of the cases by just using this theorem for a fixed pair of \(n\) and \(k\). This modification allows us to provide a very simple proof using LTE. Here I’ll restate this particular case, and then prove the first part. The second part can be proven analogously.

Theorem (Zsigsmondy Special Case): 

  1. For two coprime positive integers \(a\) and \(b\) and any two positive integers \(n\) and \(k\) with \(k<n\), \(a^n-b^n\) has a prime divisor that does not divide \(a^k-b^k\) with the following exception:
    • \(n = 2, k=1\) and \(a+b\) is a power of two.
  2. For two coprime positive integers \(a\) and \(b\) and any two positive integers \(n\) and \(k\) with \(k<n\), \(a^n+b^n\) has a prime divisor that does not divide \(a^k+b^k\) with the following exception:
    • \(n=3, k=1,a=2, b=1\).

Proof of 1:

Suppose \(a^n-b^n\) and \(a^k-b^k\) share same set of prime divisors. This implies \(a^n-b^n\) and \(a^{\gcd(n,k)}-b^{\gcd(n,k)}\) also share same set of prime divisors. Assuming \(A=a^{\gcd(n,k)}\) and \(B=b^{\gcd(n,k)}\), we could follow the rest of this argument and get to a contradiction. So, without loss of generality, we may assume \(k=1\).

Now we consider two cases:

Case 1: \(n\) is a power of \(2\).
If \(n=2\) and \(a+b\) is a power of two, we arrive at one of the listed exceptions. Now note that,
\(\begin{align*}&\gcd(a+b, a^2+b^2)\\
=&\gcd(a+b, (a+b)^2-a^2-b^2)\\
=&\gcd(a+b,2ab)\\
=&\gcd(a+b,2)\end{align*}\)
This implies both \(a+b\) and \(a^2+b^2\) can’t be powers of two unless \(a+b=2\implies a=b=1\). Hence at least one of them must have an odd prime divisor. Furthermore, this prime divisor does not divide \(a-b\) since \(\gcd(a-b, a^2+b^2)=\gcd(a-b,2)\) (following the previous steps). However, if \(n>2\), then \(a^2+b^2|a^n-b^n\), implying that odd prime will divide \(a^n-b^n\). This is a contradiction.

Case 2: \(n=2^md\) with \(d>1\) being odd.
Without loss of generality, we may assume \(n>1\) is odd, since \(a^d-b^d|a^n-b^n\) and it is sufficient to show that \(a^d-b^d\) has a prime divisor that does not divide \(a-b\).  From LTE, \(v_p(a-b)+v_p(n)=v_p(a^n-b^n)\) for each odd prime \(p|a-b\). Furthermore, \[\frac{a^n-b^n}{a-b}\equiv na^{n-1}\equiv 1\pmod 2\] implying \(v_2(a-b)=v_2(a^n-b^n)\). Therefore, we can conclude \[\frac{a^n-b^n}{a-b}=\prod_{p|\gcd(n,a-b)}p^{v_p(n)}\leq n\] which is impossible for \(n>1\). This raises another contradiction and we are done.

Guidelines to Open a Successful Math Club

[I run Mymensingh Parallel Math School (MPMS), a free-for-all math club whose members (including me) have consistently won many prizes  in Regional, National and International Mathematical Olympiads. Naturally, many math enthusiasts often ask me for tips on starting math clubs. So, 4 years ago, I wrote the following short note. I have decided to republish it here for future references.]

Unlike seeking for philosopher’s stone, starting a math club is very easy. You see, it requires only two things: a few classrooms and some members. Even a ‘teacher’ is not needed because the classes can find their way all by themselves! Although first a few month they need an instructor to teach them how to walk all-alone.

Through this tender age you have to be a bit careful. Try to drive the class in a relaxed mood so that everybody feels free to join in the discussion. It’s a very, very important thing for encouraging everyone to share his comments and ideas with others. In fact continuing this practice one day enables them to take the duster and the chalks in own hands. Moreover, we advise you to look for the true dedicated persons amongst the members. They will run it and never leave it. In this process MPMS has got its perfect structure.

May be the mostly asked questions are all about selecting class-topic. And yeah, this is too difficult to answer. Actually you can choose anything of your choice. There is neither any limitation nor any boundary. Math may appear boring sometimes. So why you don’t look at physics or literature then? In MPMS, physics, chemistry, economics, literature, biology-even philosophy take place frequently in the chaos. Also it is wise to discuss attractive topics like combinatorics at the early stage. Later you may go through harder things day by day depending on everybody’s capability to cope with it.

So…turn off your computer and come out to the field. See you at the BdMO National… 🙂