## Tag: Mathematics

### The Proof From The Book

Abstruse Goose comic strip is simply awesome. Here is the Riemann Hypothesis, postulated in 1859,  which is also one of the seven millennium prize problems:

Some numbers have the special property that they cannot be expressed as the product of two smaller numbers, e.g., 2, 3, 5, 7, etc. Such numbers are called prime numbers, and they play an important role, both in pure mathematics and its applications. The distribution of such prime numbers among all natural numbers does not follow any regular pattern, however the German mathematician G.F.B. Riemann (1826 – 1866) observed that the frequency of prime numbers is very closely related to the behavior of an elaborate function

ζ(s) = 1 + 1/2s + 1/3s + 1/4s + …

called the Riemann Zeta function. The Riemann hypothesis asserts that all interesting solutions of the equation

ζ(s) = 0

lie on a certain vertical straight line. This has been checked for the first 1,500,000,000 solutions. A proof that it is true for every interesting solution would shed light on many of the mysteries surrounding the distribution of prime numbers. [Clay Mathematics Institute]

### P = NP?

P is not equal to NP, isn’t that simple enough? So what’s all the fuss about; well ask mathematicians and computer scientists who have been working to find the answer but have been unsuccessful.

Many of you who have been following science news and blogs must have heard the buzz about solution to P vs NP problem recently. For past couple of weeks, I have been taking off from blogging and basically the net itself (not to much success), so I missed the news until my friend Vishwesha told me about it couple of days back and told me how it has been making buzz in the blogosphere. Not just the bloggers but famous mathematicians jumped into it and provided critical review and analyis to the solution and finally it was concluded that there are many flaws in the solution. Vishwesha wrote quite a bit about the public review of the proof in his blog.

Here I will just to try to write about what P vs NP problem is, why it is so critical and alo provide various links for further reading. P vs NP is one of the seven unsolved problems in Mathematics for which Clay Mathematics Institute offers million dollars for providing the solution. Till now only one of the problems, Poincaré conjecture, has been resolved for which Russian mathematician Dr. Grigoriy Perelman was awarded the million dollar prize, but interestingly he refused to accept the reward and went into recluse in Russia. P vs NP problem was first formulated by Stephen Cook in 1971 and official formulation can be found here. In layman terms, P Vs NP problem asks the question whether a “hard” problem, whose solution can be easily verified, can it also be solved easily by a computer algorithm? Got confused? Ok, let’s try to understand more clearly.

P= NP?

P stands for polynomial time and here it refers to set of problems whose solution can be determined by computer algorithm in polynomial time proportional to number of elements N. These problems are said to be solved easily. For a problem with N elements in it, algorithm execution time is polynomial : N, N2, N3 and so on. Higher the order of power slower is the execution.

NP here stands for ” Non-deterministic Polynomial” and consists of set of those problems for which solutions are very hard to obtain, but once solutions are given, its easily verifiable in polynomial time. In terms of algorithm execution time, the solution finding times for NP problems are exponential where a number is raised to the Nth power, like, say, 2N. Time taken to solve is huge and practically impossible to solve.For example, it’s very hard to find prime factors of a very large number but once the solution is available, it can be verified simply by multiplying the factors which can be done in polynomial time. Many of the real life problems come under NP category, such as scheduling optimization problem (stochastic algorithms are used to solve such problems in real-life). Clay Institute provides another example to understand the NP type problem:

Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker’s list also appears on the list from the Dean’s office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. [Clay Institute]

So P= NP? question means that for a hard problem whose solution can be verified in Polynomial time, can it also be solved in Polynomial time. In other words, is the apparent ‘hard’ problem really hard or not? Till now, no one has been to prove or disprove this problem, while majority of mathematicians believe that P is not equal to NP, implying that for a hard problem whose solutions can be verified easily, finding solution is impossible even by the best algorithm.

Recently Vinay Deolalikar from HP claimed that he has solved the problem and claimed P is not equal to NP. His manuscript can be found here. He sent out his results and proof to mathematicians and what followed was a collaborative public reviewing of the proof from famous mathematicians to students to bloggers. Mathematicians found many gaping holes in the proof.

Some might ask, how does it help knowing that we cannot solve a very hard problem. Well, Dr Sipser from MIT rightly explains the importance of knowing the proof of whether P=NP or not:

He says that the P-versus-NP problem is important for deepening our understanding of computational complexity. “The P-versus-NP problem has become broadly recognized in the mathematical community as a mathematical question that is fundamental and important and beautiful.” [MIT]

You can also follow this link to get a detailed list of related articles and links and ofcourse Wikipedia. You an also follow Georgia Tech proffesor, R J Lipton’s blog which provides indepth analysis and discussion. He also gives three reasons as to why we need proof for this problem:

Does A Proof Of P${\neq}$NP Matter?

Yes it does. Here are my three foremost reasons to think that such a proof could be very important.

${\bullet}$ A Proof Would Tell Why: Even those who are sure that P${\neq}$NP would like to know why this is so. This is exactly Atiyah’s point. A proof would give us insight into why there can be no efficient search for SAT.

${\bullet}$ A Proof Could Give Us New Methods: Perhaps the best reason is the hope that a proof that P${\neq}$NP would have to use new tools in the proof. These tools would hopefully shed light on computation in general. They could yield insights into the fundamental nature of computation. This is the best reason, in my opinion, for wanting a proof.

${\bullet}$ A Proof Helps With Goals of Security: Modern cryptography uses the term provable security. In many cases this means only that they have proved that breaking their system implies that some hardness assumption, such as on factoring, is wrong. Even a proof that P${\neq}$NP would not rule out that such assumptions are false: recall that factoring is not known to be NP-complete. I think, however, that a proof of at least P${\neq}$NP would be of some comfort to cryptographers. Their special hardness assumptions might still be unproved, but a proof would move us closer to perhaps one day really having provable security. [R J Lipton blog]

### 17 is The Random Number

Well, the reason I asked you guys to post some random number between 1-20 was to see how many of you choose 17 as your random number. It has been observed by many people that when asked to choose a random number between 1-20, people tend to choose 17 more often than any other number. There are many theories which try to explain this but none of them are conclusive. Human minds like to follow patterns, preferences and thereby we are less likely to be good random number generators. When faced with a question of choosing a random number, we tend to look for those numbers which appear to be less common , such as prime numbers. That can probably explain why we pick prime numbers more often as compared to other numbers. So between 1-20, there are 8 of them- 2,3,5,7,11,13,17,19. Probably 2 and 5 can be ruled out being too common among all of them. 3,7 and 13 have cultural references. That leaves 11, 17 and 19. Of these three, why we prefer to pick 17 is a mystery.  Maybe because 17 is neither too far away nor too near from the upper limit 20. If you have any other theories, please post it. By the way, if asked to choose a random number between 1-100, most people choose 37 as the random number, making it the most commonly chosen random two-digit number.

In short humans are poor random number generators!

Picture credit: Flickr user sarahbaker

### Think of Any Number Between 1-20

Well, I don’t have much time to write a long post today, maybe in the evening, but for the time being just think of any number between 1-20 and if possible post it in the comment section without looking at what others posted. I could have created a poll to do so but was too lazy to do.

Picture credit: Flickr user stewf | Used under Creative Commons License

### Love Is Not Enough: Mathematics Of Love

Life is beautiful, but it’s love that gives meaning to life. Everyone is craving for that perfect everlasting love. People find their love, commit to each other for life with the belief that it’s going to last for ever and their love is sufficient to cruise them into this perfect everlasting relationship for life. And why not, the relationship is based on Love so it should be enough, you think so, right. Then, why so many breakups, so many divorces (especially in US and Europe). Is Love Enough to sustain a relationship? Is their a recipe for a perfect stable relationship. You can get into philosophy of love and life and keep it discussing it for ever or you can formulate this unique emotion/sentiment based real life situation as a mathematical problem and try to find a solution by solving few equations. Well, José-Manuel Rey has done the latter to understand the dynamics of love and stability of relationship and that too in a very beautiful way. The paper is available free to download here.

Here is the Abstract of the paper:

Background: Marital dissolution is ubiquitous in western societies. It poses major scientific and sociological problems both in theoretical and therapeutic terms. Scholars and therapists agree on the existence of a sort of second law of thermodynamics for sentimental relationships. Effort is required to sustain them. Love is not enough.
Methodology/Principal Findings: Building on a simple version of the second law we use optimal control theory as a novel approach to model sentimental dynamics. Our analysis is consistent with sociological data. We show that, when both partners have similar emotional attributes, there is an optimal effort policy yielding a durable happy union. This policy is prey to structural destabilization resulting from a combination of two factors: there is an effort gap because the optimal policy always entails discomfort and there is a tendency to lower effort to non-sustaining levels due to the instability of the dynamics.
Conclusions/Significance: These mathematical facts implied by the model unveil an underlying mechanism that may explain couple disruption in real scenarios. Within this framework the apparent paradox that a union consistently planned to last forever will probably break up is explained as a mechanistic consequence of the second law.

There are two important variables in this model. First one is the ‘feeling variable’ x (t) which represents the state of relationship or the common sentiments towards each other. When people fall in love, they have a very strong feeling towards each other. At the beginning of relationship, this common feeling towards each other is assumed in this model to be very large, x(0). According to Second law of thermodynamics for sentimental relationships, there is tendency for the initial feeling for one another to fade away. This kind of inertia must be counteracted by conscious practices. So applying this second law, it can be assumed that x(t) will decrease in a relationship with the passage of time and x(0) > x(t) at all the times. There is a critical value of x, x(min), at which relationship will fall apart.

Coming to second variable, its the effort variable, c(t), which is the amount of effort required in day to day activities, which can be a small gesture or a big sacrifice, in order to counter the fading sentiment. This effort variable, reinforces the relationship on day to day basis. But this effort comes at a cost to the individual and there is a maximum amount of effort a person can apply before it starts taking toll on the person and it becomes too much for the person to handle the energy associated with the efforts. In terms of the equation this second law of relationship can be written as

In this state equation, c(t) effort variable, is the control variable, while x(t) the feeling variable is the controlled variable. Here a is the effort efficiency factor, meaning how effective is your effort. If there is no effort in replenishing your relationship, then relationship continually degrades and ultimately breakups.

Speaking in simple words, when you make efforts, you make sacrifices to make your partner happy, and that makes you happy in return. But if the efforts required are too high for the emotional comfort level of the individual, these extra efforts can start bringing stress in the person as well as in the relationship. So there is a maximum effort level ,c(*), beyond which extra effort doesn’t help in rebuilding the relationship, also can be called as maximum tolerable effort level.

What you see in this plot is that a sentimental equilibrium solution is possible shown as point E, given that the feeling variable x>x(min) which ofcourse is required and easy to understand. The second requirement for this equilibrium is that the effort level c> c(*), i.e. c-c(*) >0, meaning you need more efforts than what is perceived as comfortable or tolerable effort level by the individuals. In other words, individuals in relationship have to be ready to make that extra effort to go beyond their tolerable effort level and fill that “effort gap” to make relationship stable. Failure to do so can lead to demise of the relationship.

So summarizing, when in relationship you start with a mutual emotional feeling of well being for each other at say x(0). With time it starts fading away, but you make efforts to replenish the relationship by making that extra effort and keep your relationship status at pint A in the above plot. Ideally , you have to reach to point E which is the equilibrium, so you need continuously increasing efforts. But suppose, you relaxed for a while in making those efforts, so you fall down a bit due to these ‘effort inattentions’ as shown in the plot. But as sincere couples you realize and get back to work it out again quickly, so you are back in track to point E, but now you have to put in more efforts. If you keep being inattentive to these efforts, you can completely lose your track and the feeling will keep on fading and you can ultimately hit x(min), the point where the feeling is totally gone, and ultimately can lead to breakups or divorce.

Sadly, this study, while beautiful mathematically, doesn’t give a rosy picture of stability of love and feelings in a relationship. Love is not sufficient, you need to nurture it, every moment, everyday and still there can be factors and perturbations in life, which can throw your relationship offtrack. But its not bleak altogether, atleast there is hope, if you can find someone who is willing to work together making these efforts continuously, Life can Be Beautiful.

PS: Will this model be applicable for relationships in India, where not just the two individuals play a role in relationship, rather the whole family and friend circle is involved which can be a stabilizing factor sometimes, but can also be a destabilizing factor.

Reference: Rey J-M (2010) A Mathematical Model of Sentimental Dynamics Accounting for Marital Dissolution. PLoS ONE 5(3): e9881. doi:10.1371/ journal.pone.0009881

Photo Credit: Kevinspear.com

### Happy Pi Day

It’s March 14th today, 3/14, mathematicians celebrate this day as Pi day to mark the importance of constant (3.14) in mathematics and science. Today is also Einstein’s birthday!! Geeks celebrate this day eating pies and discussing the importance of number pi. Till now pi’s value has been determined to 2.7 trillion digits after decimal. There are people who have memorized pi’s values to hundreds and thousands of digits after decimal. Current world record is held by Lu Chao who memorized and recited the value of pi to 67,890 digits, pretty impressive!! As we all know pi is an irrational number and any string of number will be present in number pi somewhere. Try this pi search engine to find where your date of birth or any string of number lies in pi.

Some more pi trivia:

1. Symbol of pi first used in 1706 by William Jones, but was popular after it was adopted by the Swiss mathematician Leonhard Euler in 1737.
2. Historical evidence suggest that Pi was known and approximated by Greeks and Indian mathematicians around 1900 BC.
3. Professor Hans-Henrik Stolum, an earth scientist at Cambridge University has calculated the ratio between teh actual length of rivers from source to mouth and their direct length. Although the ratio varies from river to river, the average value is slightly greater than 3, that is to say that the actual length is roughly three times greater than the direct distance. In fact the ratio is approximately 3.14, which is close to the value of the number pi… The ratio of pi is most commonly found for rivers flowing across very gently sloping planes, such as those found in Brazil or the Siberian tundra.
4. Pi truncated to 50 decimal places 3.14159 26535 89793 23846 26433 83279 50288 41971 69399 37510
5. MIT usually sends out its acceptance letter to students on pi day.

So how will you celebrate the pi day? I might use this as an excuse to eat some more strawberry pies from nearby Servatii bakery !!

December 7, 2019