Tag Archives: arithmetic

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}

 

Advertisements

Number Theory

Standard

I read the term “number theory” for the first time in 2010, in this book (for RMO preparation):

This term didn’t make any sense to me then. More confusing was the entry in footer “Number of Theory”. At that time I didn’t have much access to internet to clarify the term, hence never read this chapter. I still like the term “arithmetic” rather than “number theory” (though both mean the same).

Yesterday, following article in newspaper caught my attention:

The usage of this term makes sense here!

Sum of squares

Standard

In the past few posts, I have talked about representing integers as a sum of squares:

In this post, I would like to state Lagrange’s four-square theorem following section 6.4 of Niven-Zuckerman-Montgomery’s An introduction to the theory of number.

Firstly, by applying Hensel’s lemma to the result from the earlier post we get (Theorem 5.14):

Proposition: Let a,b,c be arbitrary integers. Then the congruence ax^2+by^2+cz^2\equiv 0\pmod{p} has a non-trivial solution modulo any prime p.

The theorem stated in the earlier post establishes that there is no need for any condition modulo primes p not dividing abc. The above proposition, application of Hensel’s lemma, just demonstrates it more explicitly by telling that the equation is solvable everywhere locally (i.e. modulo every prime).

Secondly, we need following result from Geometry of numbers (Theorem 6.21):

Minkowski’s Convex Body Theorem for general lattices: Let A be a non-singular n\times n matrix with real elements, and let \Lambda = A\mathbb{Z}^n=\{A\mathbf{s}\in \mathbb{R}^n: \mathbf{s}\in \mathbb{Z}^n\} be a lattice. If \mathcal{C} is a set in \mathbb{R}^n that is convex, symmetric about origin \mathbf{0}, and if \text{vol}(\mathcal{C})> 2^n |\det(A)|, then there exists a lattice point \mathbf{x}\in\Lambda such  that \mathbf{x}\neq 0 and \mathbf{x}\in \mathcal{C}.

Now we are ready to state the theorem (for the proof see Theorem 6.26):

Lagrange’s four-square theorem: Every positive integer n can be expressed as the sum of four squares, n=x_1^2+x_2^2+x_3^2+x_4^2, where x_i are non-negative integers.

Birch and Swinnerton-Dyer Conjecture

Standard

This is part of the 6 unsolved Millennium Problems. Following is a beautiful exposition of the statement and consequences of this conjecture:

Anybody with high-school level knowledge can benefit from this video.

Nim

Standard

Nim is a very old game with precise mathematical theory, and one player can always force a win.

The game is Nim is played as follows: Any number of matches/pebbles are arranged in heaps, the number of heaps and the number matches/pebbles in each heap, being arbitrary.  There are two players, A and B. The first player A takes any number of matches/pebbles from a heap, he/she may take only one or any number up to the whole of the heap, but he/she must touch one heap only. B then makes a move conditioned similarly, and the players continue to take alternate turns of picking matches/pebbles. The player who takes the last match/pebble wins the game.

We define a winning position as a position such that if one player P (A or B) can secure it by his/her move, leaving his/her opponent Q (B or A) to move next, then, whatever Q may do, P can play so as to win the game. Any other position we call a losing position.

Next, we express the number of matches in each heap in the binary scale and form a figure by writing down one under the other. Then we add up the columns. For example, consider the following position:

nim

Then, (1,3,5,7) position gives the following figure:

001
011
101
111

224

If the sum of each column is even (which is the case above), then the position is correct. An incorrect position is one which is not correct, thus (1,3,4) is incorrect.

Then we have the following result:

A position in Nim is a winning position if and only if it is correct.

For the proof/discussion/variations of rules, see § 9.8, of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers.

But designing an elaborate winning strategy, i.e. ensuring that you always stay in winning position, is not so easy (though we know it exists!). For example, watch this video by Matt Parker:

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.