Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $p(n)$ be the greatest prime divisor of $n$. Chowla proved here that $p(n^2+1) > C \ln \ln n $ for some $C$ and all $n > 1$.

At the beginning of the paper, he mentions briefly that the weaker result $\lim_{n \to \infty} p(n^2+1) = \infty$ can be proved by means of the Thue-Siegel theorem (note: it was written before Roth considerably improved the theorem).

  1. Can someone elaborate on this? I was able to reduce the problem to showing that the negative Pell equation $x^2-Dy^2 = -1$ (where $D$ is positive and squarefree) has a finite number of solutions such that $p(y)$ is bounded by some $C$.

  2. Can someone provide examples of applications of Thue-Siegel in Diophantine equations? In the Wikipedia article it is mentioned that "Thue realised that an exponent less than d would have applications to the solution of Diophantine equations", but I am not sure I am realising it...

share|cite|improve this question
can you please say which interpretation of the limit is correct. – user51427 Dec 10 '12 at 15:46
@BullwinkleJ.Moose, that's not "obvious". Why would someone write lim if they meant lim inf. – user51427 Dec 11 '12 at 6:15
@BullwinkleJ.Moose "The fact that n2+1 (for some n) has arbitrarily large prime factors is completely trivial" that's exactly what I've been saying from before you posted your answer. – user51427 Dec 11 '12 at 14:49
why don't you change \lim to \liminf? I tried to suggest this edit but it wasn't enough changed letters (???) so the software rejected it. – user51427 Dec 11 '12 at 14:55
up vote 8 down vote accepted

Suppose that the prime factors of $n^2+1$ are all bounded by $N$ for infinitely many $n$. Then infinitely many integers $n^2 + 1$ can be written in the form $D y^3$ for one of finitely many $D$. Explicitly, the set of $D$ can be taken to be the finitely many integers whose prime divisors are all less than $N$, and whose exponents are at most $2$. For example, if $N=3$, then $D \in \{1,2,4,3,6,12,9,18,36\}$. Letting $x = n$, it follows that for at least one of those $D$, there are infinitely many solutions to the equation $$x^2 - D y^3 = -1.$$ From your original post, I'm guessing you actually know this argument, except you converted $n^2 + 1$ to $D y^2$ rather than $D y^3$ (of course, one can also use $D y^k$ for any fixed $k$, at the cost of increasing the number of possible $D$).

It turns out, however, that the equation $x^2 - D y^3 = -1$ only has finitely many solutions, and that this is a well known consequence of Siegel's theorem (1929), which says that any curve of genus at least one has only finitely many integral points. Siegel's proof does indeed use the Thue-Siegel method, although the proof is quite complicated. It is quite possible that this is the argument that Chowla had in mind - is is certainly consistent, since Chowla's paper is from 1934 > 1929.

There are some more direct applications of Thue-Siegel to diophantine equations, in particular, to the so called Thue equations, which look like $F(x,y) = k$ for some irreducible homogeneous polynomial $F$ of degree at least three. A typical example would be: $$x^n - D y^n = -1,$$ for $n \ge 3$. Here the point is that the rational approximations $x/y$ to $\sqrt[n]{D}$ are of the order $1/y^n$, which contradict Thue's bounds as long as $n \ge 3$. Equations of this kind are what are being referred to in the wikipedia article.

Edit Glancing at that paper of Chowla in your comment, one can see the more elementary approach. Let $K$ denote the field $\mathbf{Q}(i)$, and let $\mathcal{O} = \mathbf{Z}[i]$ denote the ring of integers of $K$. Assume, as above, that there exists an infinite set $\Sigma$ of integers such that $n^2+1$ has prime factors less than $N$. For $n \in \Sigma$, write $A = n+i$ and $B = n-i$; they have small factors in $\mathcal{O}$ (which is a PID, although the argument can be made to work more generally using the class number). As above, one may write $A =(a + bi)(x + i y)^3$ where $a + bi$ comes from a finite list of elements of $\mathcal{O}$ (explicitly, the elements whose prime factorization in $\mathcal{O}$ only contains primes dividing $N$ with exponent at most $2$). Since $\Sigma$ is infinite, there are thus infinitely many solutions for some fixed $a + b i$, or equivalently, infinitely many solutions to the equations (taking the conjugate): $$n + i = (a + b i)(x + i y)^3, \qquad n - i = (a - b i)(x - i y)^3,$$ Take the difference of these equations and divide by $2i$. We end up with infinitely many solutions to the equation: $$b x^3 + 3 a x^2 y - 3 b x y^2 - a y^3 = 1.$$ This is now homogeneous, so one can apply Thue's theorem, rather than Siegel's Theorem. (Explicitly, the fractions $x/y$ are producing rational approximations to the root of $b t^3 + 3 a t^2 - 3 b t - a = 0$ which contradict the Thue bounds.)

share|cite|improve this answer
I'm confused about the first part of your post, doesn't this just prove that $n^2+1$ has arbitrarily large prime factors, not that for any bound $M$ you can pick and $N$ such that for all $n > N$ the largest prime factor of $n^2+1$ is $> M$? I'm assuming that's the meaning of the limit since the first meaning can be proved without Thue-Siegel-Roth as linked in my answer. – user51427 Dec 10 '12 at 0:59
but isn't that also provable for all polynomials without the Thue-Siegel-Roth theorem? like here… – user51427 Dec 10 '12 at 15:09
sunflower - Bullwinkle understood the statement correctly. Regarding your link - it is true that for any polynomial $f$ there's ${x_n}$ such that $p(f(x_n)) \to \infty$, but it doesn't imply that if $p(f(x_n))$ is bounded then ${x_n}$ is finite. – Ofir Dec 10 '12 at 18:04
Bullwinkle J. Moose - First of all, thank you! After trying to read some articles in foreign lagnuages and failing, finally I see an answer I understand (it was very readable, and also your guess was correct). I also think that your method generalizes to polynomials of the form $x^k+a$ and their translations. BUT, according to this paper by Keates:… , this result was known to Pólya by a paper from 1918 (in German):… – Ofir Dec 10 '12 at 18:27
@Bullwinkle J. Moose - Another thing that bugs me about Siegel's Theorem is that it's so strong it didn't need the additional information about $p(y)$ being bounded. – Ofir Dec 10 '12 at 19:15

Suppose $p(n^2+1)$ was bounded by $X$, then no matter how large $n$ is $n^2+1$ factors into a product of powers of primes below $X$. In particular we have the factorization $n^2 + 1 = A^4 B^2 C$ where $B$ and $C$ are square free. There are $2^{|X|}$ possible values $C$ can take and $2^{|X|}$ $B$ can take. Some fixed $B^2C$ (with $C>1$) must occur for infinitely many $n$, in which case we have $$\frac{1}{A^4} = \left(B \sqrt{C}-\frac{n}{A^2}\right)\left(B \sqrt{C}+\frac{n}{A^2}\right)$$ infinitely many approximations of order 4 quality contradicting Thue-Siegel ($n$ may not be coprime to $A^2$, but by pigeonhole you can find some subsequence of $n$s for which they are all coprime to the same factor of $A^2$).

Edit Sorry this must be wrong since we can prove the same result by completely elementary methods. I'm not sure what the $\lim$ about $p$ means in this case.

Edit2: we need to show that the largest prime factor of n^2+1 is bounded below by an increasing function just proving that n^2+1 has arbitrarily large prime factors isn't enough it needs to be shown that it will always have large prime factors for n large

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.