A topic I wanted to discuss for long time

Standard

If you are an average maths undergraduate student (like me), you might have ended up in a situation of choosing between “just completing the degree by somehow passing the courses without caring about the grades” and “repeating a course/taking fewer courses so as to pass all courses with nice grades only”. Following is a nice discussion from Reddit:

Mathematics Today…

Standard

When we talk about doing mathematics, what comes to  our mind is Blackboard-chalk, notebook-pen and books. No doubt that these are and will remain one one of the most important instruments leading to elegant mathematical discoveries.  But, the evolution of technology we use has also affected the way we do, learn and share mathematics. In ancient time, mathematics was shared in form of books and letters. Then in 17th Century people started publishing academic journals periodically, which has today become one the most profitable business (like pharmaceuticals).  In 1960s computer algebra systems were invented (called MATHLAB). Then in 1970s books were digitized and today we have dedicated ebook readers.  Another major challenge  of publishing mathematical knowledge was to be able to typeset weird symbols, and this problem was fully solved using computers in 1978 by Donald Knuth. (to know more about this transition read this discussion).

Now it’s 21st century and the shape of sharing mathematical knowledge has changed significantly in past decade.  To begin with, in 2003 Poincaré conjecture’s solution was not published in any journal but was rather posted on arXiv. Today we have people on social networking sites like Facebook, Twitter, Google+, Tumblr, Weblogs...  who let you know the results just as they are being cooked up. For example, Live-tweet of Babai’s first Graph Isomorphism talk, in this talk one of the most interesting theorem of 2015 was proved. Many big shots announce their big results directly on their Weblogs, for example Terence Tao announced his proof of Erdős Discrepancy Problem on his blog. Today we can have interactive textbooks (like this), articles (like this) and assignments (like this) with advent of MathJax, SageMath

So far I have been concerned about “print” mathematics, but with advent of cheap internet, whole new methods of mathematical ideas sharing have come into picture. Today almost every reputed research organization maintain video lecture archives (IAS, CIRM,  IHÉSIHPInstitut Fourier, MatScience). Apart from mainstream mathematics, popularization of mathematics has become much more interesting today. We have lots of interesting mathematics popularization channels on YouTube like ViHartNumberphile, Mathologer, 3Blue1Brown, The Global Math Project,… and SoundCloud like BBC Radio 4: More or Less, ACMEScience ,… For a big-list of online mathematics videos see this and for big-list of mathematics podcasts see this.

Before this internet era, there were similar mathematics popularization attempts. Like my favourite: “Donald Duck in Mathmagic Land” (1959) [updated the link on 28 Dec’18]

135th Carnival of Mathematics

Standard

Welcome to the carnival…

Before we begin, let’s know our number-friend of this month. 135 is the smallest three-digit number that is the sum of its first digit and the square of its second digit and the cube of its third digit: $\displaystyle{135 = 1 + 3^2 + 5^3}$.

Now, get hold of pen and paper, the carnival begins…

Cross-Number Puzzle – Numbrcise.com

This is a “medium” brainteaser to help you warm up. To play, you must fill in all the blank squares in the grid with numbers ranging from 1 to 9 in order to find a synchronized solution to a series of horizontal and vertical equations – all at once.

Three dimensional tessellation of crosses – circlesandtriangles (Dan)

Day after tomorrow is 118th birthday of Maurits Cornelis Escher and will be celebrated as first “Tessellation Day” [details]. And in this article, Dan investigates the three dimensional analogue of Greek Cross tessellation using animations. He elegantly explains the mathematics involved behind tessellation by reducing  the 3D problem to a 2D one.

Snell and Escher – Joshua Bowman

When we study the concept of refraction, one of the central law is “Snell’s Law”. Motivated by Johann Bernoulli’s (a mathematician) clever application of Snell’s Law to solve brachistochrone problem,  Joshua introduces reader to hyperbolic geometry via works of Maurits Cornelis Escher  (an artist) using Snell’s Law! I have many times discussed hyperbolic geometry with young  minds, but this introduction is really illuminating.

5 Mistakes to Avoid when Drawing a Soccer Ball – David Swart

At some point of time, you must have tried your hand at drawing various objects around you. Moreover, soccer is claimed to be most played sports in the world. But still many of us can’t draw a soccer ball properly! In this lovely article, David helps us to mathematically identify and correct these mistakes…

Boolean Algebra – mathsbyagirl

If you try to take a stroll through “mathematical logic”, you will encounter the statements that contradict themselves and yet might be true.  Such statements are called paradoxes. In this article, Austin gives a sketch of the Banach-Tarski theorem and paradox.  It is intended for mathematicians of intermediate skills though the first few paragraphs are accessible to more people.

Programming is a piece of cake  – Paula Rowinska

This is an article discussing the importance of computing in the modern maths, especially the applied areas. There’s a common misconception that mathematicians work only on very pure and useless for the society problems – Paula explains that it’s a myth.

Many of us would have appeared for exams in May, and hence this article by a gifted mathematician becomes oddly relevant! In this article Prof. Terence does a serious analysis of grading system using techniques from Probability and Statistics. In case you happen to be a person associated with academia, this is worth reading.

Float like butterfly and Sting like a Mathematician!  – Nira Chamberlain

Muhammed Ali has been regarded as the most influential sportsman of the century. A week ago, he died aged 74. This is intriguing story about how a heavyweight boxing champion influenced Dr. Nira to become a mathematician.

Interview with a mathematician: Maria Chudnovsky  – Anthony Bonato

Graph Theory is one of those branches of Mathematics which consist of simple to state but difficult to solve problems. In case you are not familiar with it, just spend some time on this “Math for seven-year-olds” kit. Prof. Anthony interviewed Maria Chudnovsky, a leading mathematician specializing in graph theory. Maria is famous for proving the “Strong Perfect Graph theorem”, which was open for forty years. Maria is engaging and gives great advice to young mathematicians. She also talks about her upbringing, including facts you can’t find on her wiki page or other interviews.

Prime After Prime  – Brian Hayes

There’s lots about the prime numbers that seems random; you can even play a good game of dice with them. But in March Robert J. Lemke Oliver and Kannan Soundararajan discovered some remarkable biases or correlations between pairs of consecutive primes. Brain explores this discovery in computer code and “very illuminating” pictures.

This article builds upon Brian Hayes‘ article about the distribution of primes, which we just discussed.  Motivated by the argument that “Primes aren’t random, but sometimes it can be useful to treat them as if they were.”, John writes about the connection between statistics and number theory. Mathematically mature audience will surely enjoy reading this.

Maximal density subsquare-free arrangements – Peter Karpov

I will end this Carnival with an open problem. In this article, Peter discusses some computational results for the “no subsquares problem”. The statement of problem is as follows

What is the largest number of points that can be placed on a N × N grid so that no four of them form a square?

Get your hands dirty and try to find an efficient algorithm to calculate answer for N>16!

But, before we say good bye to this edition of monthly roundup, let me remind you to visit the previous edition which was hosted by Kartik at Comfortably Numbered. Join us next time for the 136th edition, hosted by Manan at Math Misery. You can find all the other Carnivals, and submit articles for future carnivals at: http://aperiodical.com/carnival-of-mathematics/

Numbers and Logic

Standard

I am a big fan of number theory. I find the answer to Hilbert’s Tenth Problem fascinating. I was introduced to this problem, a couple of years ago, via the documentary titled : “Julia Robinson and Hilbert’s Tenth Problem“, here is the trailer:

You can read more about it here. Also for the sake of completeness, let me state Hilbert’s Tenth Problem:

Does there exist an algorithm to determine whether a given Diophantine equation has a solution in rational integers?

In 1970, Yuri Matiyasevich completed the solution of this problem by using the concept of Turing Machine. This short video provides a nice overview about Turing Machines in general

The answer to Hilbert’s Tenth Problem problem is

No such algorithm exists.

This interplay of number theory and logic is really interesting, isn’t it? But I can’t discuss solution of Hilbert’s Tenth Problem here, since I have never read it. But there is nice overview at Wikipedia.

I will rather discuss a puzzle from Boris A. Kordemsky’s book which illustrates the idea of this interplay.

Ask a friend to pick a number from 1 through 1000. After asking him/her ten questions that can be answered yes or no, you tell him/her the number. What kind of question?

The key to the solution is that 2 to the tenth power is 1024 (that is, over 1000). With each question you knock out half the remaining numbers, and after ten questions only the thought number is left.

I welcome you to think of a number and write the corresponding yes/no questions as a comment below.

Call for Submissions

Standard

I will be hosting 135th Carnival of Mathematics on 15 June 2016.

The Carnival of Mathematics is a monthly blogging round up hosted by a different blog each month. The Aperiodical is responsible for organising a host each month.

The Carnival of Mathematics accepts any mathematics-related blog posts: explanations of serious mathematics, puzzles, writing about mathematics education, mathematical anecdotes, refutations of bad mathematics, applications, reviews, etc. Sufficiently mathematized portions of other disciplines are also acceptable.

Last date for submission is 10 June 2016

Revision 1: Why I love Mathematics?

Standard

Unlike Mathematics itself, which is forever, philosophy of mathematics keeps on changing. Philosophy of mathematics includes basic definitions and ideologies. About one and a half years ago I wrote about “Why I love Mathematics?” and in these one and a half years my ideologies changed.

Now, for me love means

a feeling of awesomeness for something/ someone.

I believe that this definition captures the general idea. Now let me update the answer to the question.

Mathematics is not a human being, so it can’t accept or reject me. I like logical, concrete and unambiguous statements which are provided by mathematics. Hence I study it.

Unfortunately, contrary to what I believed earlier, mathematics doesn’t have its own language.

The language of mathematics is the language being spoken by the citizens of the “world center(s) of mathematics” of that time.

Let me illustrate my point:

• The ancient mathematics was communicated in Greek, Arabic and Sanskrit (symbolic languages of Babylonians and Mayans are yet to be fully deciphered).
• The medieval mathematics (14th century to 18th Century) was communicated in Italic languages like Latin, Italian, French etc. A good supporter of this argument is the fact that Carl Friedrich Gauss being German wrote his most celebrated book, Disquisitiones Arithmeticae, in Latin.
• The before-my-birth mathematics (18th Century to 20th Century) was communicated in Germanic languages like English and German, since then Cambridge (UK) and Göttingen were the “world centers of mathematics”. A good supporter of this argument is the fact that Paul Erdős being Hungarian wrote his first paper in German (though, he and his friends also published in Hungarian). Interestingly, Russian was the language of many beautiful olympiad problem books until disintegration of USSR.
• The after-my-birth mathematics (21st Century onwards) is communicated in English (Germanic Language) and French (Italic Language) since today’s world centers of mathematics are USA and France. German lost its position as scientific language because of Adolf Hitler‘s dictatorship.

I am not claiming that today mathematics doesn’t exist in any languages other than English or French, but these are the languages in which we today consider publishing our work.  For example, there are more than 550 million people speaking Spanish so it is obvious that their mathematics textbooks are written in their languages (some spanish books). Even in  India, though we have more than 260 million people speaking Hindi and high school mathematics textbooks in Hindi (see: KhanAcademy in Hindi), but still at college level English is only official mode of instruction so that the students have access to the latest discoveries.

Cross Diagonal Cover – V

Standard

This has been an exciting week! Prof. Sukanta Pati proved an interesting theorem that enables us to get decomposition of $2m-1\times n$ grids into simpler grids, hence simplifying counting to large extent (note that $m=n$ is also allowed). It enables us to surpass the difficulty posed by “more than two crosses in one square”, thus supporting the idea of colouring (i.e. not giving importance to two crosses in a square).

Given $\dpi{300}\inline m\times n$ grid which has consisting of $\dpi{300}\inline m$ rows and $\dpi{300}\inline n$ columns such that the terminating corner square lie in $\dpi{300}\inline m^{th}$ row. Let the number of covered squares in $\dpi{300}\inline m\times n$ grid be $\dpi{300}\inline C(m,n)$ . Then for  $\dpi{300}\inline 2m-1\times n$ grid we have $\dpi{300}\inline C(2m-1, n)= 2C(m,n)-\beta(m,n)$  where $\dpi{300}\inline \beta(m,n)$ is the number of covered squares in $\dpi{300}\inline m^{th}$ row of $\dpi{300}\inline m\times n$ grid.

Instead of giving its proof, I will give an  example when $m=5, n=10$.

I omitted the repetitions of crosses (x) since the number of x in each square doesn’t matter. Note that if we reflect 5×10 about the middle of 5th row we will get 9×10.

Here, $C(5,10) = 25$ and $C(9,10) = 2\times 25 - 5 = 45$. Using this example you can easily prove the generalized statement by exploiting the bilateral symmetry of grid and x about ythe dotted line.

Though  I suspected that least common multiple of $m-1, n-1$ determine the number of steps my algorithm evaluates, Pritam Laskar  found the exact formula.

Given a $m\times n$ grid, the Cross Diagonal Cover algorithm terminates after  $lcm(m-1, n-1) + 1$  steps.

For proof, follow the arguments of grant93jr in his/her comment (he/she mistakenly called their lcm to be their gcd).

Using the SageMath Program, about which I wrote in previous post, I am pretty sure that $\gcd(m,n)$ always divides the number of filled squares. So, now the question is

Why the greatest common divisor of m and n always divides the number of filled squares?

Cross Diagonal Cover – IV

Standard

While discussing this problem with Dr. Shailesh Shirali, he commented that there has to be a way to phrase the problem in terms of a ray of light being reflected off the walls of the rectangle, bouncing around, proceeding from one corner to some other corner.

The problem in re-stating my problem in “light reflection” form was that reflections must be from center of squares and this is not the way light “actually” reflects from surfaces. But, I clubbed that idea with “graph theory” (directed graphs), which actually answers the first question I asked in my previous post:

Why no filled square has more than 2 crosses?

As per my “Cross diagonal cover algorithm” we can’t retrace a path and each square has just two diagonals. Hence, if we replace all the squares by their centers then each center is of degree two (i.e. can allow intersection of at most two distinct paths). Hence proving that no filled square can have more than 2 crosses. For example:

Now moving to the bigger question of counting the total number of filled squares, there hasn’t been much progress yet (even on arriving at a concrete conjecture). But, Prof. Amritanshu Prasad wrote a SageMath  program for my algorithm which enables us to find number of the filled squares for individual cases without actually drawing them! For Example: for m=101 , n=102 grid, there will be 5151 = (101 * 102 )/ 2 filled squares. Pretty cool 🙂

SageMath is is an open source implementation of mathematics and scientific software based on Python 2.  Unfortunately, since the SageMath program is essentially a Python script I am not allowed to embed  it in my WordPress.com blog. But, motivated by my discussions with Ms. Marina Ibrishimova, I tweaked Prof. Prasad’s original source-code and added comments (initialized by #) to make it self explanatory.

Here is the SageMath (or Python) code to count the number of filled squares for $2 \leq m\leq n\leq 10$

#-----START OF PYTHON FUNCTION FOR CROSS DIAGONAL COVER ALGORITHM-----

def cover(m,n):
#a function to count the number of squares covered in a grid with m rows
#and n columns
xinc = 1
#we will use this variable to increment (or decrement) the value of
#x-coordinate (row position) by 1 unit after each step
yinc = 1
#we will use this variable to increment (or decrement) the value of
#y-coordinate (column position) by 1 unit after each step
pos = [1, 1]
#we are assuming our grid to have at least 2 rows and 2 columns
#and will initialize counting from (1,1) position.
visited = [[0, 0], [1, 1]]
#since we start from (1,1) position, we implicitly assume to have
#counted (0,0) position.
while pos != [m-1, 0] and pos != [0, n-1] and pos != [m - 1, n - 1]:
#whenever we reach any corner the algorithm terminates, so need to include
#position of other three corners apart from starting corner in condition.
if pos[0] in [0, m-1]:
#evaluates to true if x-coordinate of current position is a
#member of the collection [0,m-1]
xinc = - xinc
#if x-coordinate is either 0 or m-1 then we will switch diagonal
#by switching the sign of xinc
if pos[1] in [0, n-1]:
#evaluates to true if y-coordinate of current position is a member
#of the collection [0,n-1]
yinc = -yinc
#if y-coordinate is either 0 or n-1 then we will switch diagonal
#by switching the sign of yinc
pos[0] += xinc
#update the x-coordinate of new position as x(new) = x(old) + xinc,
# where xinc = 1 or -1.
pos[1] += yinc
#update the y-coordinate of new position as y(new) = y(old) + yinc,
# where yinc = 1 or -1.
if not (pos in visited):
#if this new state is not there in visited positions list
visited.append([pos[0], pos[1]])
#then add this new position to the list of visited positions.
return visited

#---------------END OF FUNCTION---------------

#we will write a small code to be able to use above function to find number of
#filled squares for all grids where m,n lie between 1 and 11 (both excluded).

for i in range (2, 11):
#The range() function provides an easy way to construct a list of integers.
#The range() function only does numbers from the first to the last,
#not including the last.
for j in range(i, 11):
print i, j, len(cover(i, j))
# len(indata) counts the bytes of data in indata here it
#counts the number of elements is visited list.


To run the above code, please copy-paste it in SageMathCell and click evaluate button. You will get the list displaying m, n and the number of filled squares in each of the grid (with 1<m,n<11).

In case you want to understand above Python function, here is an illustration when m=3 and n=4:

Note that though (1,1) position is encountered twice but it is added to “visited squares” list only once.

So far I haven’t been able to derive a useful interpretation even after getting access to lot of data. I hope to formulate a conjecture soon…

Cross Diagonal Cover – I

Standard

While doodling in my college classes, I designed an algorithm which I called Cross Diagonal Cover Algorithm:

I have a $m\times n$ rectangle divided into unit squares. I start by placing a x (cross) in leftmost corner. Every time I visit a square in diagonal direction I place a  x in the squares till I reach any boundary of rectangle, from where I switch to adjacent diagonal.

Illustrating the algorithm… Follow the arrow numbers to fill the grid.

Please note that it doesn’t matter that how many x (cross) are there in each square. The number of x (cross) in each square just signify number of times I visited that square while executing the algorithm.

Then I asked myself the following question:

Can I cover whole grid with at least one x in each unit square?

The answer to my above question is NO! The proof is pretty easy.

If $m=n$ then it’s trivial that I can’t cover the whole grid with x since I will  be tracing the main diagonal again and again.

Moreover, the key observation here is that I will be stuck in loop (which can’t cover whole grid) whenever I reach another corner of the grid since it supports only one diagonal. Since I want to cover whole grid I must visit all the corners but they are dead ends!

Quod Erat Demonstrandum.

Any references about this idea from literature would be appreciated. I am working on a better question on “Cross Diagonal Cover Algorithm”, which I will discuss in next post.

History of Math Week at Pune

Standard

On board it is written : "Mathematics! We are doing it because we love doing it. (Lawn of Mathematics Department, Pune University)

Last week (unofficial) History of Math Week was celebrated in Pune. Lectures about work of Galois, Abel, Newton and Bhaskaracharya were delivered at various institutes in Pune. So to attend lectures I visited Indian Institute of Science Education and Research (IISER), Pune and Mathematic Department of Pune University.
Though I don’t have much interest in History of Math (like who discovered which theorem or method or zero). But, its a good experience to see the theorem from point of view of a person who first published it.

Moreover the bird which I pointed out in my earlier post (Kya Mangta Hai) keep returning to that tree for berries.