Finite Sum & Divisibility – 2

Standard

Earlier this year I discussed a finite analogue of the harmonic sum. Today I wish to discuss a simple fact about finite harmonic sums.

If p is a prime integer, the numerator of the fraction 1+\frac{1}{2}+\frac{1}{3}+\ldots + \frac{1}{p-1} is divisible by p.

We wish to treat the given finite sum modulo p, hence we can’t just add up fractions. We will have to consider each fraction as inverse of an integer modulo p. Observe that for 0<i<p, we have inverse of each element i in the multiplicative group \left(\mathbb{Z}/p\mathbb{Z}\right)^\times, i.e. there exist an i^{-1} such that i\cdot i^{-1}\equiv 1 \pmod p.

For example, for p=5, we have 1^{-1}=1, 2^{-1}=3, 3^{-1}=2 and 4^{-1}=4.

Hence we have
\displaystyle{i\cdot \frac{1}{i}\equiv 1 \pmod p ,\qquad (p-i)\cdot \frac{1}{p-i} \equiv 1 \pmod p }
for all 0<i<p.

Hence we have:
\displaystyle{i\left(\frac{1}{i}+\frac{1}{p-i}\right)\equiv i\cdot \frac{1}{i} - (p-i)\cdot \frac{1}{p-i} \equiv 0 \pmod p}

Thus we have:
\displaystyle{\frac{1}{i}+\frac{1}{p-i}\equiv 0 \pmod p}

The desired result follows by summation.

We can, in fact, prove that the above harmonic sum is divisible by p^2, see section 7.8 of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers for the proof.

Advertisements

Farey Dissection

Standard

The Farey sequence \mathcal{F}_n of order n is the ascending sequence of irreducible fractions between 0 and 1, whose denominators do not exceed n. This sequence was discovered by Charles Haros in 1806, but Augustin-Louis Cauchy named it after geologist John Farey.

Thus \frac{h}{k} belongs to \mathcal{F}_n if 0\leq h\leq k\leq n and \text{gcd}(h,k)=1, the numbers 0 and 1 are included in the forms \frac{0}{1} and \frac{1}{1}. For example,
\displaystyle{\mathcal{F}_5 = \frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1}}

Following are the  characteristic properties of Farey sequence (for proofs refer §3.3, §3.4 and §3.7 of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers):

  1. If \displaystyle{\frac{h}{k}} and \displaystyle{\frac{h'}{k'}} are two successive terms of \mathcal{F}_n, then kh'-hk'=1.
  2. If \displaystyle{\frac{h}{k}}\displaystyle{\frac{h''}{k''}} and \displaystyle{\frac{h'}{k'}} are three successive terms of \mathcal{F}_n, then \displaystyle{\frac{h''}{k''}=\frac{h+h'}{k+k'}}.
  3. If \displaystyle{\frac{h}{k}} and \displaystyle{\frac{h'}{k'}} are two successive terms of \mathcal{F}_n, then the mediant \displaystyle{\frac{h+h'}{k+k'}} of \displaystyle{\frac{h}{k}} and \displaystyle{\frac{h'}{k'}} falls in the interval \displaystyle{\left(\frac{h}{k},\frac{h'}{k'}\right)}.
  4. If n>1, then no two successive terms of \mathcal{F}_n have the same denominator.

The Stern-Brocot tree, which we saw earlier while understanding the working of clocks, is a data structure showing how the sequence is built up from 0 (=0/1) and 1 (=1/1) by taking successive mediants.

Now, consider a circle \mathcal{C} of unit circumference, and an arbitrary point O of the circumference as the representative of 0 (zero), and represent a real number x by the point P_x whose distance from O, measured round the circumference in the anti-clockwise direction, is x.

farey1

Plainly all integers are represented by the same point O, and numbers which differ by an integer have the same representative point.

Now we will divide the circumference of the circle \mathcal{C} in the following manner:

  1. We take the Farey sequence \mathcal{F}_n, and form all the mediants \displaystyle{\theta = \frac{h+h'}{k+k'}} of the successive pairs \displaystyle{\frac{h}{k}}\displaystyle{\frac{h'}{k'}}. The first and last mediants are \displaystyle{\frac{1}{n+1}} and \displaystyle{\frac{n}{n+1}}. The mediants naturally do not belong themselves to \mathcal{F}_n.
  2. We now represent each mediant \theta by the point P_\theta. The circle is thus divided up into arcs which we call Farey arcs, each bounded by two points P_\theta and containing  one Farey point, the representative of a term of \mathcal{F}_n. Thus \displaystyle{\left(\frac{n}{n+1},\frac{1}{n+1}\right)} is a Farey arc containing the one Farey point O.

The aggregate of Farey arcs is called Farey dissection of the circle. For example, the sequence of mediants for n=5, say \mathcal{M}_5 is
\displaystyle{\mathcal{M}_5 = \frac{1}{6},\frac{2}{9},\frac{2}{7},\frac{3}{8},\frac{3}{7},\frac{4}{7},\frac{5}{8},\frac{5}{7},\frac{7}{9},\frac{5}{6}}

And hence the Farey disscetion looks like:

farey2

Let n>1. If P_{h/k} is a Farey point, and\frac{h_1}{k_1}, \frac{h_2}{k_2} are the terms of \mathcal{F}_n which precede and follow \frac{h}{k}, then the Farey arc around P_{h/k} is composed of two parts, whose lengths are
\displaystyle{\frac{h}{k}-\frac{h+h_1}{k+k_1}=\frac{1}{k+k_1}, \qquad \frac{h+h_2}{k+k_2}-\frac{h}{k}=\frac{1}{k(k+k_2)}}
respectively. Now k+k_1<2n, since k_1 and k_2 are unequal (using the point (4.) stated above)and neither exceeds n; and k+k_1>n (using the point (3.) stated above). We thus obtain:

Theorem: In the Farey dissection of order n, there n>1, each part of the arc which contains the representative \displaystyle{\frac{h}{k}} has a length between \displaystyle{\frac{1}{k(2n-1)}} and \displaystyle{\frac{1}{k(n+1)}}.

For example, for \mathcal{F}_5 we have:

farey3

Using the above result, one can prove the following result about rational approximations (for more discussion, see §6.2 of  Niven-Zuckerman-Montgomery’s An Introduction to the Theory of Numbers):

Theorem: If x is a real number, and n a positive integer, then there is an irriducible fraction \displaystyle{\frac{h}{k}} such that 0<k\leq n and \displaystyle{\left| x-\frac{h}{k}\right| \leq \frac{1}{k(n+1)}}

One can construct a geometric proof of Kronceker’s theorem in one dimension using this concept of Farey dissection. See §23.2 of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers  for details.

Geometry & Arithmetic

Standard

A couple of weeks ago I discussed a geometric solution to an arithmetic problem. In this post, I will discuss an arithmetical solution to a geometry problem. Consider the following question:

Given a square whose sides are reflecting mirrors. A ray of light leaves a point inside the square and is reflected repeatedly in the mirrors. What is the nature of its paths?

It may happen that the ray passes through a corner of the square. In that case, we assume that it returns along its former path.

arth

In figure, the parallels to the axis are the lines, x = m + \frac{1}{2} and y = n + \frac{1}{2}, where m and n are integers. The thick square, of side 1, around the origin is the square of the problem and E\equiv(a,b) is the starting point. We construct all images of E in the mirrors, for direct or repeated reflection. One can observe that they are of four types, the coordinates of the images of the different types being

  1. (a+2n, b+2m)
  2. (a+2n, -b+2m+1)
  3. (-a+2n+1, b+2m)
  4. (-a+2n+1, -b+2m+1)

where m and n are arbitrary integers. Further, if the velocity at E has direction cosines, \lambda, \mu, then the corresponding images of the velocity have direction cosines

  1. (\lambda, \mu)
  2. (\lambda, -\mu)
  3. (-\lambda, \mu)
  4. (-\lambda, -\mu)

where we suppose (on the grounds of symmetry) that \mu is positive. If we think of the plane as divided into squares of unit side, then interior of a typical square being

\displaystyle{n -\frac{1}{2} < x < n+\frac{1}{2}, \qquad m-\frac{1}{2}<y<m+\frac{1}{2}}

then each squares contains just one image of every point in the original sqaure, given by n=m=0 (shown by the bold points in the figure). And if the image in any of the above squares of any point in the original sqaure is of type (1.), (2.), (3.) or (4.), then the image in any of the above squares of any other point in the original square is of the same type.

We can now imagine E moving with the ray (shown by dotted lines in the figure). When the point E meets the mirror, it coincides with an image and the image of E which momentarily coincides with E continues the motion of E, in its original direction, in one of the squares adjacent to the fundamental square (the thick square). We follow the motion of the image, in this square, until it in its turn it meets a side of the square. Clearly, the original path of E will be continued indefinitely in the same line L (dotted line in the figure), by a series of different images.

The segment of L in any square (for a given n and m) is the image of a straight portion of the path of E in the original square. There is one-to-one correspondence between the segments of L, in different squares, and the portions of the path of E between successive reflections, each segment of L being an image of the corresponding portion of the path of E.

The path of E in the original square will be periodic if E returns to its original position moving in the same direction; and this will happen if and only if L passes through an image of type (1.) of the original E. The coordinates of an arbitrary point of L are x=a+\lambda t, \quad y = b+\mu tf.

Hence the path will be periodic if and only if \lambda t = 2n, \quad \mu t = 2m, for some t and integral n,m, i.e. if  \frac{\lambda}{\mu} is rational.

When \frac{\lambda}{\mu} is irrational, then the path of E approaches arbitrarily near to every point (c,d) of the sqaure. This follows directly from Kronecker’s Theorem in one dimension (see § 23.3 of G H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers.):

[Kronecker’s Theorem in one dimension] If \theta is irrational, \alpha is arbitrary, and N and \epsilon are positive, then there are integers p and q such that p>N and |p\theta - q-\alpha|<\epsilon.

Here, we have \theta = \frac{\lambda}{\mu} and \alpha = (b-d)\frac{\lambda}{2\mu} - \frac{1}{2}(a-c), with large enough integers p=m and q=n. Hence we can conclude that

[König-Szücs Theorem]Given a square whose sides are reflecting mirrors. A ray of light leaves a point inside the square and is reflected repeatedly in the mirrors. Either the path is closed and periodic or it is dense in the square, passing arbitrarily near to every point of the square. A necessary and sufficient condition for the periodicity is that the angle between a side of the square and the initial direction of the ray should have a rational tangent.

Another way of stating the above Kronecker’s theorem is

[Kronecker’s Theorem in one dimension] If \theta is irrational, then the set of points n\theta - \lfloor n\theta\rfloor is dense in the interval (0,1).

Then with some knowledge of Fourier series, we can try to answer a more general question

Given an irrational number \theta, what can be said about the distribution of the fractional parts of the sequence of numbers n\theta, for n=1,2,3,\ldots?

The answer to this question is called Weyl’s Equidistribution Theorem (see §4.2 of  Elias M. Stein & Rami Shakarchi’s Fourier Analysis: An Introduction)

[Weyl’s Equidistribution Theorem] If \theta is irrational, then the sequence of fractional parts \{n\theta - \lfloor n\theta\rfloor\}_{n=1}^{\infty} is equidistributed in [0,1).

I really enjoyed reading about this unexpected link between geometry and arithmetic (and Fourier analysis). Most of the material has been taken/copied from Hardy’s book. The solution to the geometry problem reminds me of the solution to the Cross Diagonal Cover  Problem.

Understanding Geometry – 4

Standard

Aleksej Ivanovič Markuševič’s book, “Remarkable Curves” discusses the properties of ellipses, parabolas, hyperbolas, lemniscates, cycloids, brachistochrone, spirals and catenaries.  Among these “lemniscates” are the ones that I encountered only once before starting undergraduate education (all other curves appeared frequently in physics textbooks) and that too just to calculate the area enclosed by this curve. So I will discuss the properties of lemniscates in this post.

Let’s begin with the well-known curve, ellipse. An ellipse is the locus of points whose sum of distances from two fixed points (called foci) is constant. My favourite fact about ellipses is that we can’t find a general formula for the perimeter of an ellipse, and this little fact leads to the magical world of elliptic integrals. This, in turn, leads to the mysterious elliptic functions, which were discovered as inverse functions of elliptic integrals. Further, these functions are needed in the parameterization of certain curves, now called elliptic curves. For more details about this story, read the paper by Adrian Rice and Ezra Brown, “Why Ellipses are not Elliptic curves“.

Lemniscate is defined as the locus of points whose product of distances from two fixed points F_1 and F_2 (called foci) is constant. Lemniscate means, “with hanging ribbons” in Latin.  If the length of the segment \overline{F_1F_2} is c then for the midpoint of this line segment will lie on the curve if the product constant is c^2/4. In this case we get a figure-eight lying on its side.

Lemniskate_bernoulli2.svg

Lemniscate of Bernoulli; By Kmhkmh (Own work) [CC BY 4.0], via Wikimedia Commons

The attempt to calculate the perimeter of the above curve leads to elliptic integral, hence can’t derive a general formula for its perimeter. Just like an ellipse!

If we equate the value of the constant product not to c^2/4 but to another value, the lemniscate will change its shape. When the constant is less than c^2/4, the lemniscate consists of two ovals, one of which contains inside it the point F_1, and the other the point F_2.

oval

Cassini oval (x^2+y^2)^2−2c^2(x^2−y^2)=a^4−c^4; Source: https://www.encyclopediaofmath.org/legacyimages/common_img/c020700b.gif

When the product constant is greater than c^2/4 but less than c^2/2, the lemniscate has the form of a biscuit. If the constant is close to c^2/4, the “waist” of the biscuit is very narrow and the shape of the curve is very close to the figure-eight shape.

biscuit

Cassini oval (x^2+y^2)^2−2c^2(x^2−y^2)=a^4−c^4; Source: https://www.encyclopediaofmath.org/legacyimages/common_img/c020700b.gif

If the constant differs little from c^2/2, the waist is hardly noticeable, and if the constant is equal or greater than c^2/2 the waist disappears completely, and the lemniscate takes the form of an oval.

oval.gif

Cassini oval (x^2+y^2)^2−2c^2(x^2−y^2)=a^4−c^4; Source: https://www.encyclopediaofmath.org/legacyimages/common_img/c020700a.gif

We can further generalize this whole argument to get lemniscate with an arbitrary number of foci, called polynomial lemniscate.

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. 

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.