Category Archives: Problem Solving

Dec28

Richert Theorem

Posted on December 28, 2018 by math

In 1852, Chebyshev proved the Bertrand’s postulate:

For any integer $n>1$ , there always exists at least one prime number $p$ with $n < p < 2n$ .

You can find Erdős’ elementary proof here. In this post I would like to discuss an application of this fantastic result, discovered by Hans-Egon Richert in 1948:

Every integer $n\geq 7$ can be expressed as a sum of distinct primes.

There are several proofs available in literature, but we will follow the short proof given by Richert himself (english translation has been taken from here and here):

Consider the set of prime integers $\{p_1, p_2,p_3,\ldots\}$ where $p_1=2, p_2=3, p_3=5,\ldots$ . By Bertrand’s postulate we know that $\boxed{p_i < p_{i+1} < 2p_i }$ .

Next, we observe that, any integer between 7 and 19 can be written as a sum of distinct first 5 prime integers $\{2,3,5,7,11\}$ :

7 = 5+2; 8 = 5+3; 9 = 7+2; 10 = 5+3+2; 11 = 11; 12 = 7+5; 13 = 11+2; 14 = 7+5+2; 15 = 7+5+3; 16 = 11+5; 17 = 7+5+3+2; 18 = 11+7; 19 = 11+5+3

Hence we fix $a=7-1=6$ , $b=19-a=13$ , and $k=5$ to conclude that $\boxed{b \geq p_{k+1}}$ .

Let, $S_i = \{a+1,a+2,\ldots, a+p_{i+1}\}=\{7,8,\ldots, 6+p_{i+1}\}$ . Then by the above observation we know that the elements of $S_k = S_5 = \{7,8,\ldots, 19\}$ are the sum of distinct first $k=5$ prime integers.
Moreover, if the elements of $S_i$ can be written as the sum of distinct first $i$ prime integers, then the elements of $S_{i+1}$ can also be written as the sum of distinct first $i+1$ prime integers since

$S_{i+1}\subset S_i \cup \{m + p_{i+1}: m\in S_{i}\}$

as a consequence of $2p_{i+1} \geq p_{i+2}$ .

Hence inductively the result follows by considering $\bigcup_{i\ge k} S_i$ , which contains all integers greater than $a=6$ , and contains only elements which are distinct sums of primes.

Exercise: Use Bertrand’s postulate to generalize the statement proved earlier: If $n>1$ and $k$ are natural numbers , then the sum

$\displaystyle{\frac{1}{n}+ \frac{1}{n+1} + \ldots + \frac{1}{n+k}}$

cannot be an integer.

[HINT: Look at the comment by Dan in the earlier post.]

References:
[0] Turner, C. (2015) A theorem of Richert. Math.SE profile: https://math.stackexchange.com/users/37268/sharkos

[1] Richert, H. E. (1950). Über Zerfällungen in ungleiche Primzahlen. (German). Mathematische Zeitschrift 52, pp. 342-343. https://doi.org/10.1007/BF02230699

[2] Sierpiński,W. (1988). Elementary theory of numbers. North-Holland Mathematical Library 31, pp. 137-153.

Dec20

Riemann zeta function

Posted on December 20, 2018 by math

Standard

About 2.5 years ago I had promised Joseph Nebus that I will write about the interplay between Bernoulli numbers and Riemann zeta function. In this post I will discuss a problem about finite harmonic sums which will illustrate the interplay.

Consider the Problem 1.37 from The Math Problems Notebook:

Let $\{a_1, a_2, \ldots, a_n\}$ be a set of natural numbers such that $\text{gcd}(a_i,a_j)=1$ , and $a_i$ are not prime numbers. Show that $\displaystyle{\frac{1}{a_1}+\frac{1}{a_2}+ \ldots + \frac{1}{a_n} < 2}$

Since each $a_i$ is a composite number, we have $a_i = p_i q_i s_i$ for some, not necessarily distinct, primes $p_i$ and $q_i$ . Next, $\text{gcd}(a_i,a_j)=1$ implies that $p_i,q_i \neq p_j, q_j$ . Therefore we have:

$\displaystyle{\sum_{i=1}^n \frac{1}{a_i} \leq \sum_{i=1}^n \frac{1}{p_i q_i} \leq \sum_{i=1}^n \frac{1}{(\text{min}(p_i,q_i))^2} < \sum_{k=1}^\infty \frac{1}{k^2}}$

Though it’s easy to show that $\sum_{k=1}^\infty \frac{1}{k^2} < \infty$ , we desire to find the exact value of this sum. This is where it’s convinient to recognize that $\boxed{\sum_{k=1}^\infty \frac{1}{k^2} = \zeta(2)}$ . Since we know what are Bernoulli numbers, we can use the following formula for Riemann zeta-function:

$\displaystyle{\zeta(2n) = (-1)^{n+1}\frac{B_{2n}(2\pi)^{2n}}{2(2n)!}}$

There are many ways of proving this formula, but none of them is elementary.

Recall that $B_2 = 1/6$ , so for $n=1$ we have $\zeta(2) = \pi^2/6\approx 1.6 < 2$ . Hence completing the proof

$\displaystyle{\sum_{i=1}^n \frac{1}{a_i} <\zeta(2) < 2}$

Remark: One can directly caculate the value of $\sum_{k=1}^\infty \frac{1}{k^2}$ as done by Euler while solving the Basel problem (though at that time the notion of convergence itself was not well defined):

Jul29

FLT for rational functions

Posted on July 29, 2018 by math

Standard

Following is the problem 2.16 in The Math Problems Notebook:

Prove that if $n>2$ , then we do not have any nontrivial solutions of the equation $F^n + G^n = H^n$ where $F,G,H$ are rational functions. Solutions of the form $F = aJ, G=bJ, H=cJ$ where $J$ is a rational function and $a,b,c$ are complex numbers satisfying $a^n + b^n = c^n$ , are called trivial.

This problem is analogous to the Fermat’s Last Theorem (FLT) which states that for $n> 2$ , $x^n + y^n = z^n$ has no nontrivial integer solutions.

The solution of this problem involves proof by contradiction:

Since any rational solution yields a complex polynomial solution, by clearing the denominators, it is sufficient to assume that $(f,g,h)$ is a polynomial solution such that $r=\max(\deg(f),\deg(g),\deg(h))$ is minimal among all polynomial solutions, where $r>0$ .

Assume also that $f,g,h$ are relatively prime. Hence we have $f^n+g^n = h^n$ , i.e. $f^n-h^n = g^n$ . Now using the simple factorization identity involving the roots of unity, we get:

$\displaystyle{\prod_{\ell = 0}^{n-1}\left(f-\zeta^\ell h\right) = g^n}$

where $\zeta = e^{\frac{2\pi i}{n}}$ with $i = \sqrt{-1}$ .

Since $\gcd(f,g) = \gcd(f,h) = 1$ , we have $\gcd(f-\zeta^\ell h, f-\zeta^k h)=1$ for $\ell\neq k$ . Since the ring of complex polynomials has unique facotrization property, we must have $g = g_1\cdots g_{n-1}$ , where $g_j$ are polynomials satisfying $\boxed{g_\ell^n = f-\zeta^\ell h}$ .

Now consider the factors $f-h, f-\zeta h, f-\zeta^2 h$ . Note that, since $n>2$ , these elements belong to the 2-dimensional vector space generated by $f,h$ over $\mathbb{C}$ . Hence these three elements are linearly dependent, i.e. there exists a vanishing linear combination with complex coefficients (not all zero) in these three elements. Thus there exist $a_\ell\in\mathbb{C}$ so that $a_0g_0^n + a_1g_1^n = a_2g_2^n$ . We then set $h_\ell = \sqrt[n]{a_\ell}g_\ell$ , and observe that $\boxed{h_0^n+h_1^n = h_2^n}$ .

Moreover, the polynomials $\gcd(h_\ell,h_k)=1$ for $\ell \neq k$ and $\max_{\ell}(h_\ell) = \max_{\ell} (g_\ell) < r$ since $g_\ell^n \mid f^n-h^n$ . Thus contradicting the minimality of $r$ , i.e. the minimal (degree) solution $f,g,h$ didn’t exist. Hence no solution exists.

The above argument fails for proving the non-existence of integer solutions since two coprime integers don’t form a 2-dimensional vector space over $\mathbb{C}$ .

Jun15

Rational input, integer output

Posted on June 15, 2018 by math

Standard

Consider the following polynomial equation [source: Berkeley Problems in Mathematics, problem 6.13.10]:

$f(t) = 3t^3 + 10t^2 - 3t$

Let’s try to figure out the rational values of $t$ for which $f(t)$ is an integer. Clearly, if $t\in\mathbb{Z}$ then $f(t)$ is an integer. So let’s consider the case when $t=m/n$ where $\gcd(m,n)=1$ and $m\neq \pm 1$ . Substituting this value of $t$ we get:

$\displaystyle{f\left(\frac{m}{n}\right) = \frac{3m^3}{n^3} + \frac{10m^2}{n^2} - \frac{3m}{n}= \frac{m(3m^2+10mn-3n^2)}{n^3}=k \in \mathbb{Z}}$

Since, $n^3\mid (3m^2+10mn-3n^2)$ we conclude that $n\mid 3$ . Also it’s clear that $m\mid k$ . Hence, $n=\pm 3$ and we just need to find the possible values of $m$ .

For $n=3$ we get:

$\displaystyle{f\left(\frac{m}{3}\right) = \frac{m(m^2+10m-9)}{9}=k \in \mathbb{Z}}$

Hence we have $9\mid (m^2+10m)$ . Since $\gcd(m,n)=\gcd(m,3)=1$ , we have $9\mid (m+10)$ , that is, $m\equiv 8\pmod 9$ .

Similarly, for $m=-3$ we get $n\equiv 1 \pmod 9$ . Hence we conclude that the non-integer values of $t$ which lead to integer output are:

$\displaystyle{t = 3\ell+ \frac{8}{3}, -3\ell-\frac{1}{3}}$ for all $\ell\in\mathbb{Z}$

May18

Rooms and reflections

Posted on May 18, 2018 by math

Standard

Consider the following entry from my notebook (16-Feb-2014):

The Art Gallery Problem: An art gallery has the shape of a simple n-gon. Find the minimum number of watchmen needed to survey the building, no matter how complicated its shape. [Source: problem 25, chapter 2, Problem Solving Strategies, Arthur Engel]

Hint: Use triangulation and colouring. Not an easy problem, and in fact there is a book dedicated to the theme of this problem: Art Gallery Theorems and Algorithms by Joseph O’Rourke (see chapter one for detailed solution). No reflection involved.

Then we have a bit harder problem when we allow reflection (28-Feb-2017, Numberphile – Prof. Howard Masur):

The Illumination Problem: Can any room (need not be a polygon) with mirrored walls be always illuminated by a single point light source, allowing for the repeated reflection of light off the mirrored walls?

The answer is NO. Next obvious question is “What kind of dark regions are possible?”. This question has been answered for rational polygons.

This reminds me of the much simpler theorem from my notebook (13-Jan-2014):

The Carpets Theorem: Suppose that the floor of a room is completely covered by a collection of non-overlapping carpets. If we move one of the carpets, then the overlapping area is equal to the uncovered area of the floor. [Source: §2.6, Mathematical Olympiad Treasures, Titu Andreescu & Bogdan Enescu]

Why I mentioned this theorem? The animation of Numberphile video reminded me of carpets covering the floor.

And following is the problem which motivated me write this blog post (17-May-2018, PBS Infinite Series – Tai-Danae):

Secure Polygon Problem: Consider a n-gon with mirrored walls, with two points: a source point S and a target point T. If it is possible to place a third point B in the polygon such that any ray from the source S passes through this point B before hitting the target T, then the polygon is said to be secure. Is square a secure polygon?

The answer is YES. Moreover, the solution is amazing. Reminding me of the cross diagonal cover problem.

Apr27

New Proofs on YouTube

Posted on April 27, 2018 by math

Standard

Earlier, YouTube maths channels focused mainly on giving nice expositions of non-trivial math ideas. But recently, two brand new theorems were presented on YouTube instead of being published in a journal.

Proofs of the fact that $\sqrt{2}$ , $\sqrt{3}$ , $\sqrt{5}$ and $\sqrt{6}$ are irrational numbers – Burkard Polster (13 April 2018)

This is an extension of the idea discussed in this paper by Steven J. Miller and David Montague.

A new proof of the Wallis formula for π – Sridhar Ramesh and Grant Sanderson (20 Apr 2018):

This is an extension of Donald Knuth‘s idea documented here by Adrian Petrescu.

It’s nice to see how the publishing in maths is evolving to be accessible to everyone.

Apr19

Probability Musing

Posted on April 19, 2018 by math

Standard

Please let me know if you know the solution to the following problem:

What is the probability of me waking up at 10am?

What additional information should be supplied so as to determine the probability? What do you exactly mean by the probability of this event? Which kind of conditional probability will make sense?

Consider the following comment by Timothy Gowers regarding the model for calculating the probability of an event involving a pair of dice:

Rolling a pair of dice (pp. 6), Mathematics: A very short introduction © Timothy Gowers, 2002 [Source]

I find probability very confusing, for example, this old post.

Apr7

Conway’s Prime Producing Machine

Posted on April 7, 2018 by math

Standard

Primes are not randomly arranged (since their position is predetermined) but we can’t find an equation which directly gives us nth prime number. However, we can ask for a function (which surely can’t be a polynomial) which will give only the prime numbers as output. For example, the following one is used for MRDP theorem:

Source: Andrew Granville (http://www.dms.umontreal.ca/~andrew/PDF/PrimesLecture2014.pdf)

But it’s useless to use this to find bigger primes because the computations are much more difficult than the primality tests.

Conway’s PRIMEGAME takes whole numbers as inputs and outputs $2^k$ if and only if $k$ is prime.

PRIMEGAME is based on a Turing-complete esoteric programming language called FRACTRAN, invented by John Conway. A FRACTRAN program is an ordered list of positive fractions together with an initial positive integer input n. The program is run by updating the integer $n$ as follows:

for the first fraction $f$ in the list for which $nf$ is an integer, replace $n$ by $nf$ ;
repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.

PRIMEGAME is an algorithm devised to generate primes using a sequence of 14 rational numbers:

$\displaystyle{\left( \frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{2}, \frac{1}{7}, \frac{55}{1} \right)}$

Starting with 2, one finds the first number in the machine that multiplied by 2 gives an integer; then for that integer we find the first number in the machine that generates another integer. Except for the initial 2, each number output have an integer for a binary logarithm is a prime number, which is to say that powers of 2 with composite exponents don’t show up.

If you have some knowledge of computability and unsolvability theory, you can try to understand the working of this Turing machine. There is a nice exposition on OeisWiki to begin with.

Following is an online program by Prof. Andrew Granville illustrating the working of PRIMEGAME:

Source: http://www.dms.umontreal.ca/~andrew/conwaymachine.html

Motivation for this post came from Andrew Granville’s Math Mornings at Yale.

Mar23

Generalization of Pythagoras equation

Posted on March 23, 2018 by math

Standard

About 3 years ago I discussed following two Diophantine equations of degree 2:

A special case of negative Pell’s equation (determining solvability conditions for a special degree 2 equations in 2 variables)
A slight modification of Pythagorean equation (finding explicit solutions for a particular degree 2 equations in 3 variables, using method used for finding Pythagorean triplets)

In this post, we will see a slight generalization of the result involving Pythagorean triplets. Unlike Pythagoras equation, $x^2+y^2-z^2=0$ , we will work with a little bit more general equation, namely: $ax^2+by^2+cz^2=0$ , where $a,b,c\in \mathbb{Z}$ . For proofs, one can refer to section 5.5 of Niven-Zuckerman-Montgomery’s An introduction to the theory of numbers.

Theorem: Let $a,b,c\in \mathbb{Z}$ be non-zero integers such that the product is square free. Then $ax^2+by^2+cz^2=0$ have a non-trivial solution in integers if and only if $a,b,c$ do not have same sign, and that $-bc, -ac, -ab$ are quadratic residues modulo $a,b,c$ respectively.

In fact, this result helps us determine the existence of a non-trivial solution of any degree 2 homogeneous equation in three variables, $f(X,Y,Z)=\alpha_1 X^2 +\alpha_2Y^2+\alpha_3Z^2+\alpha_4XY+\alpha_5YZ+\alpha_6ZX$ due to the following lemma:

Lemma: There exists a sequence of changes of variables (linear transformations) so that $f(X,Y,Z)$ can be written as an equation of the form $g(x,y,z)=ax^2+by^2+cz^2$ with $\gcd(a,b,c)=1$ .

Now let’s consider the example. Let $f(x,y,z)=3x^2+5y^2+7z^2+9xy+11yz+13zx$ , and we want to determine whether this $f(x,y,z)=0$ has a non-trivial solution. Firstly, we will do change of variables:

$\displaystyle{f(x,y,z)=3\left(x+\frac{3}{2}y +\frac{13}{6}z\right)^2 - \frac{7}{4}y^2 - \frac{85}{12}z^2 - \frac{17}{2}yz = g(x',y',z')}$

where $x' = x+\frac{3}{2}y +\frac{13}{6}z$ , $y'=y$ and $z'=z$ . Thus

$\displaystyle{12g(x',y',z')=36x'^2 - 21 y'^2 - 85z'^2 - 102y'z' = 36x'^2 - 21\left(y'+\frac{17}{7}z'\right)^2+\frac{272}{7}z'^2=h(x'',y'',z'')}$

where $x'' = x'$ , $y'' = y'+\frac{17}{7}z'$ and $z''=z'$ . Thus

$\displaystyle{7h(x''',y'',z'') = 252x''^2 - 147y''^2+272z''^2=7(6x'')^2-3(7y'')^2 + 17(4z'')^2 = F(X,Y,Z)}$

where $X=6x''$ , $Y=7y''$ and $Z=4z''$ . Now we apply the theorem to $7X^2-3Y^2+17Z^2=0$ . Since all the coefficients are prime numbers, we can use quadratic reciprocity to conclude that the given equation has non-trivial solution (only non trivial thing to note that $-7\times 17$ is quadratic residue mod -3, is same as $-7\times 17$ is quadratic residue mod 3).

Feb3

A sequence I didn’t like

Posted on February 3, 2018 by math

Standard

Following is a problem I encountered many times in my high school olympiads, but was never able to solve it. Hence didn’t like it.

What is the 100th term in the sequence $1,2,2,3,3,3,4,4,4,4,5,\ldots$ ?

Following is a quick solution:

Source: http://www.careerbless.com/qna/discuss.php?questionid=1489

In this post, I will discuss the solution given in The Green Book of Mathematical Problems (problem 14).

Determine a function $f(n)$ such that the $n^{th}$ term of the sequence $1,2,2,3,3,3,4,4,4,4,5,\ldots$ is given by $\lfloor f(n)\rfloor$ .

Let’s denote the $n^{th}$ number of the sequence by $a_n$ , i.e. $a_n=\lfloor f(n)\rfloor$ . The integer $m$ first occurs in the sequence when each of the integers from 1 to $m-1$ have already appeared 1 to $m-1$ times, respectively. Hence, if $a_n=m$ then
$n = [1 + 2 + 3 + \ldots + (m-1)]+1 +\ell = \frac{m(m-1)}{2} + 1 + \ell$
for $\ell = 0,1,2,\ldots, m-1$ .

Hence we have:
$\displaystyle{0\leq n - \frac{m(m-1)}{2} - 1 \leq m-1}$

$\displaystyle{\Rightarrow \frac{m^2-m+2}{2}\leq n \leq \frac{m^2+m}{2}}$

$\displaystyle{\Rightarrow m^2-m+2\leq 2n \leq m^2+m}$

$\displaystyle{\Rightarrow \left(m-\frac{1}{2}\right)^2+\frac{7}{4}\leq 2n \leq \left(m+\frac{1}{2}\right)^2-\frac{1}{4}}$

$\displaystyle{\Rightarrow (2m-1)^2+7\leq 8n \leq (2m+1)^2 - 1}$

$\displaystyle{\Rightarrow (2m-1)^2 \leq 8n - 7 \leq (2m+1)^2 - 8}$

$\displaystyle{\Rightarrow (2m-1)^2 \leq 8n - 7 < (2m+1)^2}$

$\displaystyle{\Rightarrow 2m-1 \leq \sqrt{8n-7}<2m+1}$

$\displaystyle{\Rightarrow m \leq \frac{1+\sqrt{8n-7}}{2} < m+1}$

$\displaystyle{\Rightarrow m=\left\lfloor \frac{1+\sqrt{8n-7}}{2} \right\rfloor}$

Hence we have $a_n = \left\lfloor \frac{1+\sqrt{8n-7}}{2} \right\rfloor$ . Thus, we have

$\displaystyle{\boxed{f(n) =\frac{1+\sqrt{8n-7}}{2}}}$

Now compared to the earlier solution obtained by observing the pattern, one might ask “Is there is a better formula?”. For that, you might also look at the discussion at Math.SE.

Gaurish4Math

For the love of Mathematics

Category Archives: Problem Solving

Richert Theorem

Riemann zeta function

FLT for rational functions

Rational input, integer output

Rooms and reflections

New Proofs on YouTube

Probability Musing

Conway’s Prime Producing Machine

Generalization of Pythagoras equation

A sequence I didn’t like