Category Archives: Problem Solving

Richert Theorem

Standard

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.

Advertisements

Riemann zeta function

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):

pjimage

The Pleasures of Pi, E and Other Interesting Numbers by Y E O Adrian [Copyright © 2006 by World Scientific Publishing Co. Pte. Ltd.]

FLT for rational functions

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}.

Rational input, integer output

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}

 

Discrete Derivative

Standard

I came across the following interesting question in the book “Math Girls” by Hiroshi Yuki :

Develop a definition for the differential operator \Delta in discrete space,corresponding to the definition of the differential operator D in the continuous space.

We know that derivative of a function f at point x is the rate at which f changes at the point x . Geometrically, derivative at a point x is the slope of the tangent to the function f at x where a tangent is the limit of the secant lines as shown below :

Capture5

But this happens only in the continuous world where x “glides smoothly” from one point to another. But this is not the case in a discrete world. In the discrete world there is nothing like “being close to each other”. Hence we cannot use the earlier definition of bringing h arbitrarily close to x. In a discrete world we cannot talk about getting “close” to something but instead we can talk about being “next” to each other.

Capture6

We can talk about the change in x as it moves from x to x+1 while f changes from f(x) to f(x+1). We do not need limits here, so the definition of “difference operator” (analogous to differential operator ) will be :

\Delta f(x) = \frac{ f(x+1) - f(x) }{(x+1) - x} = f(x+1) - f(x)

Hence to find derivative of a function, say g(x) = x^2 , it is easy to verify that Dg(x) = 2x but \Delta g(x) = 2x + 1 (using definitions mentioned above)

Now, when will we be able to get the same derivative in both discrete and continuous worlds? I read a little about this question in math girls and a little more in “An introduction to the calculus of finite differences” by C.H.Richardson.

Calculus of differences is the study of the relations that exist between the values assumed by the function whenever the independent variable takes on a series of values in arithmetic progression.

Let us write f(x) as f_x instead from now onwards. So f(x+1) - f(x) = \Delta f(x) = f_{x+1} - f_x. Using above definition we can prove the following for functions U_x and V_x :

1) \Delta^{k+1} U_x = \Delta^{k} U_{x+1} - \Delta^{k} U_x

2) \Delta (U_x + V_x) = \Delta U_x + \Delta V_x (or) \Delta^k (U_x + V_x) =\Delta^k U_x + \Delta^k V_x

3) \Delta^k (cU_x) = c \Delta^k U_x

Theorem. \Delta^n x^n = n!

Proof. \Delta x^n = (x+1)^n - x^n = n\cdot x^{n-1} + \text{terms of degree lower than} (n - 1). Each repetition of the process of differencing reduces the degree by one and also adds one factor to the succession n(n - 1) (n - 2) \cdots. Repeating the process n times we have \Delta^k x^n = n!.

Corollary 1. \Delta^n ax^n = a\cdot n!

Corollary 2. \Delta^{n+1} x^n = 0

Corollary 3. If U_x is a polynomial of degree n i.e. U_x= a_0+ a_1 x + a_3 x + \ldots + a_n x^n , then \Delta^n U_x = a_n\cdot n!.

We call the continued products U_x^{|n|} = U_x\cdot U_{x+1}\cdot U_{x+2} \cdots U_{x+(n-1)} and U_x^{(n)} = U_x \cdot U_{x-1}\cdot U_{x-2}\cdots U_{x-(n-1)} as factorial expressions.

If U_x is the function ax+b for some real numbers a and b, then the factorial forms we get by replacing U_x by ax+b is (ax+b)^{|n|} = (ax+b)\cdot(a(x+1)+b)\cdot (a(x+2)+b)\cdots (a(x+n-1)+b) and (ax+b)^{(n)} =(ax+b)\cdot (a(x-1)+b)\cdot (a(x-2)+b)\cdots (a(x-(n-1))+b).

We define (ax+b)^{|0|} and (ax+b)^{(0)} as 1.

Using the above definition of factorial we can show the following :

(i) \Delta (ax+b)^{(n)} = a\cdot n \cdot (ax+b)^{(n-1)}

(ii) \displaystyle{\Delta \frac{1}{(ax+b)^{|n|}} = \frac{-an}{(ax+b)^{|n+1|}}}

When we consider the special case of a=1 and b=0, the factorial representations are called raising and falling factorials :

x^{|n|} = x \cdot (x+1)\cdot (x+2)\cdots (x+n-1) – rising factorial

x^{(n)} =x\cdot (x-1) \cdot (x-2) \cdots (x-n+1) – falling factorial.

Substituting a=1 and b=0 in (i) and (ii) above , we get that

\Delta x^{(n)} = n\cdot x^{(n-1)} , \Delta^n x^{(n)} = n! and \displaystyle{\Delta \frac{1}{x^{|n|}} = - \frac{n}{x^{|n+1|}}}.

Summary:

Capture7

source: Richardson, C. H. An introduction to the calculus of finite differences. pp. 10.

Due to the fact that x^{(n)} plays in the calculus of finite differences a role similar to that played by x^n in the infinitesimal calculus, for many purposes in finite differences it is advisable to express a given polynomial in a series of factorials. A method of accomplishing this is contained in Newton’s Theorem.

Capture8

source: Richardson, C. H. An introduction to the calculus of finite differences. pp. 10.

Since these differences and U_x are identities, they are true for all values of x, and consequently must hold for x = 0. Setting x = 0 in the given function and the differences, we have the required values for all a_i and theorem is proved.

Enclosing closed curves in squares

Standard

Let’s look at the following innocent looking question:

Is it possible to circumscribe a square about every closed curve?

The answer is YES! I found an unexpected and interesting proof in the book “Intuitive Combinatorial Topology ” by V.G. Boltyanskii and V.A. Efremovich . Let’s now look at the outline of proof for our claim:

1. Let any closed curve K be given. Draw any line l and the line l’ such that line l’ is parallel to l as shown in the fig 1.

capture11

2. Move the lines l and l’ closer to K till they just touch the curve K as shown in fig 2. Let the new lines be line m and line m’. Call these lines as the support lines of curve K with respect to line l.

capture21

3. Draw a line l* perpendicular to l and the line (l*)’ parallel to l* . Draw support lines with respect to line l* to the curve K as shown in the fig 3. Let the rectangle formed be ABCD .

capture31.png

4. The rectangle corresponding to a line will become square when AB and AD are equal . Let the length of line parallel to l (which is AB)  be h_1(\mathbf{l}) and line perpendicular to l (which is AD) be h_2(\mathbf{l}). For a given line n, define a real valued function f(\mathbf{n}) = h_1(\mathbf{n})-h_2(\mathbf{n}) on the set of lines lying outside the curve .  Now rotate the line l in an anti-clockwise direction till l coincides with l’. The rectangle corresponding to l* will also be ABCD (same as that with respect to l). When l coincides with l’, we can say that  AB = h_2(\mathbf{l^*}) and AD = h_1(\mathbf{l^*}).

capture41

5. We can see that when the line is lf(\mathbf{l}) = h_1(\mathbf{l})-h_2(\mathbf{l}). When we rotate l in an anti-clockwise direction the value of the function f changes continuously i.e. f is a continuous function (I do not know how to “prove” this is a continuous function but it’s intuitively clear to me; if you can have a proof please mention it in the comments). When l coincides with l’ the value of f(\mathbf{l^*}) = h_1(\mathbf{l^*})-h_2(\mathbf{l^*}). Since h_1(\mathbf{l^*}) = h_2(\mathbf{l}) and h_2(\mathbf{l^*}) = h_1(\mathbf{l}). Hence f(\mathbf{l^*}) = -(h_1(\mathbf{l}) - h_2(\mathbf{l})). So f is a continuous function which changes sign when line is moved from l to l’. Since f is a continuous function, using the generalization of intermediate value theorem we can show that there exists a line p between l and l* such that f(p) = 0 i.e. AB = AD.  So the rectangle corresponding to line p will be a square.

Hence every curve K can be circumscribed by a square.

Rooms and reflections

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.