Monthly Archives: July 2015

Jul31

Kempner Series & MMC

Posted on July 31, 2015 by math

In Madhava Mathematics Competition 2015 (held in January 2015), we were asked to prove the convergence of Kempner Series (first time proved in 1914). Recently I discovered the paper by A. J. Kempner (http://www.jstor.org/stable/2972074), so in this blog post I will state and prove that problem.

The basic idea behind proof is to divide whole series into chunks (finding symmetry) and then construct a converging geometric series which will act as upper bound of Kempner Seires.

A detailed study of this cartoon has been done by Ben Orlin (http://bit.ly/1KD4shF)

Theorem (Kempner Series, 1914). Harmonic Series, $\sum_{k=1}^{\infty} \frac{1}{k} = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} +\ldots$ , converge, if the denominators do not include all natural numbers $1,2,3,\ldots$ , but only those numbers which do not contain any figure 9.

Proof: Given Series is:
$K = \frac{1}{1}+\ldots +\frac{1}{8}+\frac{1}{10}+\ldots +\frac{1}{18}+\frac{1}{20} + \ldots + \frac{1}{28}+\frac{1}{30}+\ldots +\frac{1}{38}+\frac{1}{40}+\ldots +\frac{1}{48}+\frac{1}{50} + \ldots + \frac{1}{58}+\frac{1}{60}+\ldots+\frac{1}{68}+\frac{1}{70}+\ldots +\frac{1}{78}+\frac{1}{80} + \ldots + \frac{1}{88}+\frac{1}{100}+\ldots$
Now we can rewrite above series as:
$S = a_1 + a_2 + \ldots + a_n + \ldots$
where $a_n$ is the sum of all terms in $K$ of denominator $d$ with $10^{n-1} \leq d < 10^{n}$ .
Observe that, each term of $K$ which forms part of $a_n$ , is less than or equal to $1/10^{n-1}$ .

Now count the number of terms of $K$ which are contained in $a_1$ , in $a_2$ , $\ldots$ , in $a_n$ . Clearly, $a_1$ , consists of 8 terms, and $a_1 < 8 \cdot 1 < 9$ . In $a_2$ there are, as is easily seen, less than $9^2$ terms of $K$ , and $a_2 < (9^2/10)$ . Altogether there are in $K$ less than $9^2 + 9$ terms with denominators under 100.

Assume now that we know the number of terms in $K$ which are contained in $a_n$ to be less than $9^n$ , for $n = 1, 2, 3, \ldots, n$ . Then, because each term of $K$ which is contained in $a_n$ is not greater than $1/10^{n-1}$ , we have $a_n < (9^n/10^{n-1})$ , and the total number of terms in $K$ with denominators under $10^n$ is less than $9^n + 9^{n-1} + 9^{n-2} + \ldots + 9^2 + 9$ .

Now, let’s go for induction. For $n = 1$ and $n = 2$ we have verified all this, and we will now show that if it is true for $n$ , then $a_{n+1} < (9^{n+1}/10^n)$ . $a_{n+1}$ contains all terms in $K$ of denominator $d$ , $10^n \leq d < 1^{n+1}$ . This interval for $d$ can be broken up into the nine intervals, $\alpha \cdot 10^n \leq d < (\alpha + 1)10^n$ , $\alpha = 1,2, \ldots, 9$ . The last interval does not contribute any term to $K$ , the eight remaining intervals contribute each the same number of terms to $K$ , and this is the same as the number of terms contributed by the whole interval $0 < d < 10^n$ , that is, by assumption, less than $9^n + 9^{n-1} + 9^{n-2} + \ldots + 9^2 + 9$ .

Therefore, $a_{n+1}$ contains less than $8(9^n + 9^{n-1} + 9^{n-2} +\ldots + 9^2 + 9) < 9^{n+1}$ terms of $K$ , and each of these terms is less than or equal to $1/10$ , we have $a_{n+1} < (9^{n+1}/10^n)$ .

Hence, $S = a_1 + a_2 + a_3 + \ldots < 9 + \frac{9}{10} + \ldots + \frac{9^{n+1}}{10^n}+ \ldots = 90$
Thus, $S$ converges, and since, $K=S$ , $K$ also converges.

——————————–
Note: There is nothing special about 9 here, the above method of proof holds unchanged if, instead of 9, any other figure $1, 2, \ldots, 8$ is excluded, but not for the figure $0$ .

Jul22

Diophantine Equation & Primes

Posted on July 22, 2015 by math

Standard

I stumbled upon following statement on some webpage (don’t have link):

There exist infinitely many integers $n$ such that $n^2 +1$ divides $n!$ .

I tried proving it, though not able to prove it but here are my insights:

Proof by contradiction (the way we show infinite primes) doesn’t work here.
I need to prove that $\frac{n!}{n^2+1} = k \in \mathbb{N}$ for infinitely many values of $n$ , so I should try to express $n^2+1$ in product form (since numerator is already in product form). After writing denominator in product form, find a condition satisfied by infinitely many values of $n$ , which generates infinitely many natural numbers as outcomes of $\frac{n!}{n^2+1}$ .

First idea that came to my mind, for factoring the denominator was in terms Gaussian Integers (numbers of form $a+ib$ where $a,b$ are integers and $i = \sqrt{-1}$ ), but I am not able to proceed in this direction further.

Second idea to generate factors of denominator was to analyze Diophantine equation (i.e. we are concerned with only integer solutions of given equation), of form: $x^2 + 1 = Dy^2$

Here is a theorem from Diophantine equation, which can help me generate factors:

Lemma: Let $p$ be a prime. The diophantine equation: $x^2 - py^2 = -1$ is solvable if and only if $p=2$ or $p\equiv 1 \pmod 4$

Proof: If the considered equation has a solution $(x,y)$ , then $p| x^2+1$ . Hence either $p=2$ or $p \equiv 1 \pmod 4$ .

For $p=2$ , $x=y=1$ is a solution.

We show that there is a solution for each prime $p=4t+1$ . Let us study the existence of an integral solution $(x_0,y_0)$ to the wee known diophantine equation: $x_0^2 - py_0^2 = 1$ .

Observe that $x_0$ is odd [otherwise, $y_0^2 \equiv py_0^2 \equiv 3 \pmod 4$ , but no square leaves a remainder 3 when divided by 4]. Thus in the relation:

$x_0^2 - 1 = (x_0-1)(x_0+1) = py_0^2$

factors $x_0+1$ and $x_0-1$ have greatest common divisor 2, and consequently one of them is a doubled square (to be denoted by $2x^2$ ) and the other one $2p$ times a square (to be denoted by $2py^2$ ).

The case $x_0+1 = 2x^2$ and $x_0-1 = 2py^2$ is impossible because it leads to a smaller solution of diophantine equation: $x^2-py^2=1$ . [method of infinite descent]

It follows that $x_0-1=2x^2$ , and $x_0+1 = 2py^2$ , therefore $x^2-py^2 = -1$

——

Now we return back to main statement.

——

Let $n^2+1 = pm^2$ , where $m \in \mathbb{N}$ and $p$ is a prime of form $p=2$ or $p \equiv1 \pmod 4$ .

Now let us consider another result:

Lemma: There are infinitely number of primes of the form $4n+1$ .

Proof : Suppose $n>1$ is an integer. Let $p$ be the smallest prime divisor of $N$ .

We define $N=(n!)^2 +1$ .

Since $N$ is odd, $p$ cannot be equal to $2$ . It is clear that $p$ is bigger than $n$ (otherwise $p \mid 1$ ).

We know that $p$ has the form $4k+1$ or $4k+3$ . Since $p\mid N$ we have:

$(n!)^2 \equiv -1 \pmod p \$

$\Rightarrow (n!)^{p-1} \equiv (-1)^{ \frac{p-1}{2} } \pmod p$ .

Using Fermat’s little Theorem we get $(-1)^{ \frac{p-1}{2} } \equiv 1 \pmod p$ .

If $p$ was of the form $4k+3$ then $\frac{p-1}{2} =2k+1$ is odd and therefore we obtain $-1 \equiv 1 \pmod p$ or $p \mid 2$ which is a contradiction since $p$ is odd.

Hence, $p$ is of the form $4k+1$ , now we can repeat the procedure replacing $n$ with $p$ and produce an infinite sequence of primes of the form $4k+1$ .

——

From above lemma, we can say that, $n^2+1 = pm^2$ for infinitely many values of $p$

I have expressed denominator in product form, what remains to prove is that the expression $\frac{n!}{pm^2}$ simplifies to give a natural number as answer.

Now this appears to me as a dead end.

If you discover/know the proof of starting statement please give its outline in comments.

But, the motive of this post is to show the beautiful flowers I observed while searching for a path which leads to given statement.

Jul15

Lecture in Dilli

Posted on July 15, 2015 by math

Standard

Sign post for Kashmere Gate campus

Today I presented my one week work at Ambedkar University, Delhi. The title of the talk was: Enigma Cryptanalysis – Beginnings. It was my first talk outside my school/institute. It was cool experience, a boy (looking uncle) wearing pajamas, old fashion spectacles and from a small city of Haryana, speaking in front of well reputed professor and students from reputed colleges.

Tiny entry to big world

It was tiring to keep on standing and speaking for one and a half hours and then to travel by Haryana Roadways, but at the end I can say “IT WAS FUN”!

Jul6

Mathematical Almora

Posted on July 6, 2015 by math

Standard

Centre of Excellence in Mathematical Sciences, Almora

For last two weeks I was in Almora (SSJ Campus of Kumaon University), attending Undergraduate Summer Workshop. There were lectures and tutorials on Group Theory, Linear Algebra and Real Analysis. I was successful in meeting Prof. E. K. Narayanan and discussing one of my research problems. These two weeks were incredible.

50 students, most of them strangers to each other, came together to learn mathematics (though some participants denied this fact). We all had different backgrounds and interests which made my experience more colorful. During free time we visited local markets, Kasar Devi Mandir, Simtola Eco Park and Binsar Wildlife Sanctuary.

Langurs at Binsar (photo courtesy: Kamal Kishore)

I had lot of new experiences like taking bath in naula (harvested water springs in Kumaon), living in dormitory (with 12 others), going for evening walk on माल road (I don’t understand why they write it “mall” instead of “maal” in English).

Sunset at maal road , Almora

Unfortunately the life is too small to revisit Almora and meet all of my buddies again, but still I hope to meet all of them again at some point of my life.

Jul1

From centre of calmness

Posted on July 1, 2015 by math

Standard

Today morning.....

Almora is awesome place. Weather is beautiful. A lot of old math is being re-learnt. Words are not enough describe my experience. Group theory, linear algebra and real analysis is being discussed.

Kainchi (a holy place near Almora)

Will write a detailed review once I return to my home.

Gaurish4Math

For the love of Mathematics

Monthly Archives: July 2015

Kempner Series & MMC

Diophantine Equation & Primes

Lecture in Dilli

Mathematical Almora

From centre of calmness