Arithmetic & Geometry

Standard

After a month of the unexpected break from mathematics, I will resume the regular weekly blog posts. It’s a kind of relaunch of this blog, and I  will begin with the discussion of an arithmetic problem with a geometric solution.  This is problem 103 from  The USSR Olympiad Problem Book:

Prove that
\displaystyle{t_1+t_2+\ldots + t_n = \left\lfloor\frac{n}{1}\right\rfloor + \left\lfloor\frac{n}{2}\right\rfloor + \left\lfloor\frac{n}{3}\right\rfloor + \ldots + \left\lfloor\frac{n}{n}\right\rfloor}
where t_k is the number of divisors of the natural number k.

One can solve this problem by using the principle of mathematical induction or using the fact that the number of integers of the sequence 1,2,3,\ldots , n which are divisible by any chosen integer k is equal to \left\lfloor \frac{n}{k}\right\rfloor. The second approach of counting suggests an elegant geometric solution.

Consider the equilateral hyperbola \displaystyle{y = \frac{k}{x}} , (of which we shall take only the branches in the first quadrant):
ss
We note all the points in the first quadrant which have integer coordinates as the intersection point of the dotted lines. Now, if an integer x is a divisor of the integer k, then the point (x,y) is a point on the graph of the hyperbola xy=k. Conversely, if the hyperbola xy=k contains an integer point, then the x-coordinate is a divisor of k. Hence the number of integers t_k is  equal to the number of the integer points lying on the hyperbola xy=k. The number t_k is thus equal to the number of absciassas of integer points lying on the hyperbola xy=k. Now, we make use of the fact that the hyperbola xy=n lies “farther out” in the quadrant than do xy=1, xy=2, xy=3, \ldots, xy=n-1. The following implication hold:

The sum t_1+t_2\ldots + t_n is equal to the number of integer points lying under or on the hyperbola xy=n. Each such point will lie on a hyperbola xy=k, where k\leq n. The number of integer points with abscissa k located under the hyperbola is equal to the integer part of the length of the segment \overline{AB} [in figure above k=3]. That is \left\lfloor\frac{n}{k}\right\rfloor, since \displaystyle{|\overline{AB}|=\frac{n}{k}}, i.e. ordinate of point A on hyperbola xy=n for abscissa k. Thus, we obtain

\displaystyle{t_1+t_2+\ldots + t_n = \left\lfloor\frac{n}{1}\right\rfloor + \left\lfloor\frac{n}{2}\right\rfloor + \left\lfloor\frac{n}{3}\right\rfloor + \ldots + \left\lfloor\frac{n}{n}\right\rfloor}

Caution: Excess of anything is harmful, even mathematics. 

Advertisements

Triangles and Rectangles

Standard

Consider the following question by Bill Sands (asked in 1995):

Are there right triangles with integer sides and area, associated with rectangles having the same perimeter and area?

Try to test your intuition. The solution to this problem is NOT so simple. The solution was published by Richard K. Guy in 1995: http://www.jstor.org/stable/2974502 

If you have a simpler solution, please write it in a comment below. Even I don’t understand much of the solution.

Building Mathematics

Standard

Let’s talk about the work of a mathematician. When I was young (before highschool), I used to believe that anyone capable of using mathematics is a mathematician. The reason behind this was that being a mathematician was not a job for people like Brahmagupta, Aryabhatta, Fermat, Ramanujan (the names I knew when I was young). So by that definition, even a shopkeeper was a mathematician. And hence I had no interest in becoming a mathematician.

Then, during highschool, I came to know about the mathematics olympiad and was fascinated by the “easy to state but difficult to solve” problems from geometry, combinatorics, arithmetic and algebra (thanks to AMTIVipul Naik and Sai Krishna Deep) . I practiced many problems in hope to appear for the exam once in my life. But that day never came (due to bad education system of my state) and I switched to physics, just because there was lot of hype about how interesting our nature is (thanks to Walter Lewin). 

In senior school I realised that I can’t do physics, I simply don’t like the thought process behind physics (thanks to Feynman). And luckily, around the same time, came to know what mathematicians do (thanks to Uncle Paul). Mathematicians “create new maths”. They may contribute according to their capabilities, but no contribution is negligible. There are two kinds of mathematicians, one who define new objects (I call them problem creators) and others who simplify the existing theories by adding details (I call them problem solvers). You may wonder that while solving a problem one may create bigger maths problems, and vice versa, but I am talking about the general ideologies. What I am trying to express, is similar to what people want to say by telling that logic is a small branch of mathematics (whereas I love maths just for its logical arguments).

A few months before I had to join college (in 2014), I decided to become a mathematician. Hence I joined a research institute (clearly not the best one in my country, but my concern was just to be able to learn as much maths as possible).  Now I am learning lots of advanced (still old) maths (thanks to Sagar SrivastavaJyotiraditya Singh and my teachers) and trying to make a place for myself, to be able to call myself a mathematician some day.

I find all this very funny. When I was young, I used to think that anyone could become a mathematician and there was nothing special about it. But now I everyday have to prove myself to others so that they give me a chance to become a mathematician. Clearly, I am not a genius like all the people I named above (or even close to them) but I still want to create some new maths either in form of a solution to a problem or foundations of new theory and call myself a mathematician. I don’t want it to end up like my maths olympiad dream.

Polynomials and Commutativity

Standard

In high school, I came to know about the statement of the fundamental theorem of algebra:

Every polynomial of degree n with integer coefficients have exactly n complex roots (with appropriate multiplicity).

In high school, a polynomial = a polynomial in one variable. Then last year I learned 3 different proofs of the following statement of the fundamental theorem of algebra [involving, topology, complex analysis and Galois theory]:

Every non-zero, single-variable, degree n polynomial with complex coefficients has, counted with multiplicity, exactly n complex roots.

A more general statement about the number of roots of a polynomial in one variable is the Factor Theorem:

Let R be a commutative ring with identity and let p(x)\in R[x] be a polynomial with coefficients in R. The element a\in R is a root of p(x) if and only if (x-a) divides p(x).

A corollary of above theorem is that:

A polynomial f of degree n over a field F has at most n roots in F.

(In case you know undergraduate level algebra, recall that R[x] is a Principal Ideal Domain if and only if R is a field.)

The key fact that many times go unnoticed regarding the number of roots of a given polynomial (in one variable) is that the coefficients/solutions belong to a commutative ring (and \mathbb{C} is a field hence a commutative ring). The key step in the proof of all above theorems is the fact that the division algorithm holds only in some special commutative rings (like fields). I would like to illustrate my point with the following fact:

The equation X^2 + X + 1 has only 2 complex roots, namely \omega = \frac{-1+i\sqrt{3}}{2} and \omega^2 = \frac{-1-i\sqrt{3}}{2}. But if we want solutions over 2×2 matrices (non-commutative set) then we have at least  3 solutions (consider 1 as 2×2 identity matrix and 0 as the 2×2 zero matrix.)

\displaystyle{A=\begin{bmatrix} 0 & -1 \\1 & -1 \end{bmatrix}, B=\begin{bmatrix} \omega & 0 \\0 & \omega^2 \end{bmatrix}, C=\begin{bmatrix} \omega^2 & 0 \\0 & \omega \end{bmatrix}}

if we allow complex entries. This phenominona can also be illusttrated using a non-commutative number system, like quaternions. For more details refer to this Math.SE discussion.

Four Examples

Standard

Following are the four examples of sequences (along with their properties) which can be helpful to gain a better understanding of theorems about sequences (real analysis):

  • \langle n\rangle_{n=1}^{\infty} : unbounded, strictly increasing, diverging
  • \langle \frac{1}{n}\rangle_{n=1}^{\infty} : bounded, strictly decreasing, converging
  • \langle \frac{n}{1+n}\rangle_{n=1}^{\infty} : bounded, strictly increasing, converging
  • \langle (-1)^{n+1}\rangle_{n=1}^{\infty} : bounded, not converging (oscillating)

I was really amazed to found that x_n=\frac{n}{n+1} is a strictly increasing sequence, and in general, the function f(x)=\frac{x}{1+x} defined for all positive real numbers is an increasing function bounded by 1:

 

Thre graph of x/(1+x) for x>0. Plotted using SageMath 7.5.1

The graph of x/(1+x) for x>0, plotted using SageMath 7.5.1

 

Also, just a passing remark, since \log(x)< x+1 for all x>0, and as seen in prime number theorem we get an unbounded increasing function \frac{x}{\log(x)} for x>1

dort

The plot of x/log(x) for x>2. The dashed line is y=x for the comparison of growth rate. Plotted using SageMath 7.5.1

 

Magic Cubes

Standard

Last week I attended a talk (by a student) about Magic Squares. I learned a bunch of cool facts about them (like how to devise an algorithm to construct them). Towards the end of the talk, one student from the audience suggested the possibility of Magic Cubes. I got very excited about this idea since it pointed towards the stereotypical mathematical ideology of generalizing the examples in order to see the deeper connections.

I myself don’t know much about Magic Cubes (or even Magic Squares) but would like to quote W. W. Rouse Ball & H. S. M. Coxeter from pp. 217 the book “Mathematical Recreations and Essays” (11th Ed.) :

A Magic Cube of the n^{th} order consists of the consecutive numbers from 1 to n^3, arranged in the form of a cube, so that the sum of the numbers in every row, every column, every file, and in each of the four diagonals (or “diameters “), is the same-namely, \frac{1}{2}(n^3 + 1). This sum occurs in 3n^2 + 4 ways. I do not know of any rule for constructing magic cubes of singly-even order. But such cubes of any odd or doubly-even order can be constructed by a natural extension of the methods already used for squares.

I would like to read about these magic hyper-cubes in future. And if you know something interesting about them, let me know in the comments below.

Counting Cycles

Standard

During one of my reading projects in 2015, I read about the Enigma cipher machine. While reading about it, I came to know that the number of possible keys of this machine is 7, 156, 755, 732, 750, 624, 000. One can see the counting procedure at pp. 22 of this document. But the counting procedure was not found to be satisfactory by most members of the audience (during my presentation). My failure to convince the audience that the counting procedure was correct, lead to my distrust in the counting arguments in general. Many times, I still, find the counting procedures controversial.

So, in an attempt to regain the trust, I will present two counting procedures for counting the number of cycles of length r when n objects (colours/beads/numbers) are given.

Procedure A: Using multiplication principle
Step 1: Choose r objects from the n choices.
Step 2: Arrange the selected r objects in a cyclic order.

  1. Since the Step 1 and Step 2 are independent of each other but should be performed together, we will multiply the results (i.e. use the multiplication principle). From Step 1 we will get \binom{n}{r} and from Step 2, we will get (r-1)! as per the circular permutation formula. Hence we get:

\displaystyle{\# r-\text{cycles from } n \text{ objects} =\binom{n}{r}\times(r-1)! = \frac{n!}{r (n-r)!}}

Procedure B: Using division principle
Step 1: Permute r of the n objects.
Step 2: Realise the mistake that you counted the permutations r extra times because these circular permutations of objects are equivalent since the circle can be rotated.

Since in Step 2 we want to correct the overcounting mistake of Step 1 performed for different objects simultaneously, we will divide the result of Step 1 by the result of Step 2. From Step 1 we will get ^n P_r and from Step 2 we will get r. Hence we get:

\displaystyle{\# r-\text{cycles from } n \text{ objects} =\frac{^n P_r}{r} = \frac{n!}{r (n-r)!}}

I am still not happy with the Procedure B, so if you have a better way of stating it please let me know.