# 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}$

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

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

# Recursion and Periodicity

Standard

One of the simplest recursive formula that I can think of is the one which generates the Fibonacci sequence, $F_{n+1} = F_n +F_{n-1}, n\geq 1$ with $F_0 = F_1=1$. So, I will illustrate a following general concept about recursions using Fibonacci sequence.

A sequence generated by a recursive formula is periodic modulo k, for any positive integer k greater than 1.

I find this fact very interesting because it means that a sequence which is strictly increasing when made bounded using the modulo operation (since it will allow only limited numbers as the output of recursion relation), will lead to a periodic cycle.

Following are the first 25 terms of the Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025.

And here are few examples modulo k, for k=2,3,4,5,6,7,8

As you can see, the sequence repeats as soon as 1,0 appears. And from here actually one can see why there should be a periodicity.

For the sequence to repeat, what we need is a repetition of two consecutive values (i.e. the number of terms involved in the recursive formula) in the sequence of successive pairs. And for mod k, the choices are limited, namely k^2.  Now, all we have to ensure is that “1,0” should repeat. But since consecutive pairs can’ repeat (as per recursive formula) the repetition of “1,0” must occur within the first k^2.

For rigorous proofs and its relation to number theory, see: http://math.stanford.edu/~brianrl/notes/fibonacci.pdf

# Under 40

Standard

The age of 40 is considered special in mathematics because it’s an ad-hoc criterion for deciding whether a mathematician is young or old. This idea has been well established by the under-40 rule for Fields Medal, based on Fields‘ desire that:

while it was in recognition of work already done, it was at the same time intended to be an encouragement for further achievement on the part of the recipients and a stimulus to renewed effort on the part of others

Though it must be noted that this criterion doesn’t claim that after 40 mathematicians are not productive (example: Yitang Zhang).  So I wanted to write a bit about the under 40 leading number theorists which I am aware of (in order of decreasing age):

• Sophie Morel: The area of mathematics in which Morel has already made contributions is called the Langlands program, initiated by Robert Langlands. Langlands brought together two fields, number theory and representation theory. Morel has made significant advances in building that bridge. “It’s an extremely exciting area of mathematics,” Gross says, “and it requires a vast background of knowledge because you have to know both subjects plus algebraic geometry.” [source]
• Melanie Wood: Profiled at age 17 as “The Girl Who Loved Math” by Discover magazine, Wood has a prodigious list of successes. The main focus of her research is in number theory and algebraic geometry, but it also involves work in probability, additive combinatorics, random groups, and algebraic topology.  [source1, source2]
• James Maynard:  James is primarily interested in classical number theory, in particular, the distribution of prime numbers. His research focuses on using tools from analytic number theory, particularly sieve methods, to study primes.  He has established the sensational result that the gap between two consecutive primes is no more than 600 infinitely often. [source1, source2]
• Peter Scholze: Scholze began doing research in the field of arithmetic geometry, which uses geometric tools to understand whole-number solutions to polynomial equations that involve only numbers, variables and exponents. Scholze’s key innovation — a class of fractal structures he calls perfectoid spaces — is only a few years old, but it already has far-reaching ramifications in the field of arithmetic geometry, where number theory and geometry come together. Scholze’s work has a prescient quality, Weinstein said. “He can see the developments before they even begin.” [source]

# Prime Consequences

Standard

Most of us are aware of the following consequence of Fundamental Theorem of Arithmetic:

There are infinitely many prime numbers.

The classic proof by Euclid is easy to follow. But I wanted to share the following two analytic equivalents (infinite series and infinite products) of the above purely arithmetical statement:

• $\displaystyle{\sum_{p}\frac{1}{p}}$   diverges.

For proof, refer to this discussion: https://math.stackexchange.com/q/361308/214604

• $\displaystyle{\sum_{n=1}^\infty \frac{1}{n^{s}} = \prod_p\left(1-\frac{1}{p^s}\right)^{-1}}$, where $s$ is any complex number with $\text{Re}(s)>1$.

The outline of proof,   when $s$ is a real number, has been discussed here: http://mathworld.wolfram.com/EulerProduct.html

# Numbers and Logic

Standard

I am a big fan of number theory. I find the answer to Hilbert’s Tenth Problem fascinating. I was introduced to this problem, a couple of years ago, via the documentary titled : “Julia Robinson and Hilbert’s Tenth Problem“, here is the trailer:

You can read more about it here. Also for the sake of completeness, let me state Hilbert’s Tenth Problem:

Does there exist an algorithm to determine whether a given Diophantine equation has a solution in rational integers?

In 1970, Yuri Matiyasevich completed the solution of this problem by using the concept of Turing Machine. This short video provides a nice overview about Turing Machines in general

The answer to Hilbert’s Tenth Problem problem is

No such algorithm exists.

This interplay of number theory and logic is really interesting, isn’t it? But I can’t discuss solution of Hilbert’s Tenth Problem here, since I have never read it. But there is nice overview at Wikipedia.

I will rather discuss a puzzle from Boris A. Kordemsky’s book which illustrates the idea of this interplay.

Ask a friend to pick a number from 1 through 1000. After asking him/her ten questions that can be answered yes or no, you tell him/her the number. What kind of question?

The key to the solution is that 2 to the tenth power is 1024 (that is, over 1000). With each question you knock out half the remaining numbers, and after ten questions only the thought number is left.

I welcome you to think of a number and write the corresponding yes/no questions as a comment below.

# Happy Birthday Ramanujam

Standard

Today is 128th birthday of Srinivasa Ramanujam Iyengar.

[Please note that Britishers gave wrong English spelling for his name, they called him “Ramanujan”,  but it should be “Ramanujam” which means  “The younger brother of Lord Rama”]

John Littlewood said (as recalled by G. H. Hardy (1921), in “Obituary Notices: Srinivasa Ramanujan”, Proceedings of the London Mathematical Society 19, p. lvii) :

Every positive integer is one of Ramanujan’s personal friends.

So, let’s talk about numbers on his birthday.

128 is 7th power of 2 and leads to 4th Mersenne Prime ($2^7 - 1=127$ is a prime)

128 is the largest number which is not the sum of distinct squares. [https://oeis.org/A001422]

and here is my present for him:

RAMANUJAM’S MAGIC SQUARE

When I was in High School, I learned making such “Special Date Magic Squares” form P.K. Srinivasan’s (1924-2005) book regarding Ramanujam’s work. [see: https://nrich.maths.org/1380 ]

Magic sum of this square is 69. Thus all rows, columns and diagonals add up to the same total of 69 and today’s date has been placed in first row.

69 is a value of $n$ where $n^2$ and $n^3$ together contain each digit once. Since, $69^2=4761$ and $69^3 = 328509$

Ramanujam also studied “Partition Function”, this function gives the number of ways of writing the integer n as a sum of positive integers, where the order of addends is not considered significant. Observe that, in the magic square above we created 10 distinct 4-partitions of 69. (though 2376 distinct 4-partitions of 69 are possible!!)

Also, the total sum of numbers in our magic square is $69\cdot 4 = 276 = 1^5 + 2^5 + 3^5$

Once more, Happy Birthday Ramanujam!