9
$\begingroup$

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

  • 0
    can you please say which interpretation of the limit is correct.2012-12-10
  • 0
    @BullwinkleJ.Moose, that's not "obvious". Why would someone write lim if they meant lim inf.2012-12-11
  • 0
    @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.2012-12-11
  • 0
    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.2012-12-11

2 Answers 2

8

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

  • 0
    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.2012-12-10
  • 0
    but isn't that also provable for all polynomials without the Thue-Siegel-Roth theorem? like here http://math.stackexchange.com/questions/253457/polynomial-values-take-on-arbitrarily-large-prime-factors2012-12-10
  • 0
    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.2012-12-10
  • 0
    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: http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=3012136 , this result was known to Pólya by a paper from *1918* (in German): http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=GDZPPN002364034&IDDOC=167172012-12-10
  • 0
    @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.2012-12-10
  • 0
    @Ofir, where is it stated that we need to show $p(f(x_n))$ bounded implies $x_n$ finite?2012-12-11
  • 0
    @sunflower, you seemed to be confused by some very basic logic. I suggest you think about the problem a little more off the website and you will work out what is going on.2012-12-11
  • 0
    @Bullwinkle J. Moose - Thank you for the edit, I prefer this more elementary solution. Regarding the bounty - I will award it when the 7-day period ends (but I expect it to go to you).2012-12-11
  • 0
    @BullwinkleJ.Moose, It was Ofir that said "but it doesn't imply that if p(f(xn)) is bounded then xn is finite" I'm asking why that needs proved - is this what his "lim" means? No definition of lim I've seen has this in it. Please don't just tell me I'm confused again, that doesn't help me not be confused.2012-12-11
  • 0
    First of all, I did mean $\lim$, but $\liminf = \infty$ implies $\lim = \infty$. Some definitions: If a limit of a sequence $x_n$ is infinity, it means that for any lower bound $C$, there's a point $N$ such that if $n>N$, $x_n$ passes $C$. So one way to prove my question is to assume that the limit isn't infinity and reach contradiction. If the limit isn't infinity, there's some specific bound $C$ such that for any point $N$, there is some $n>N$ such that $x_n < c$. This is the same as saying that for infinitely many $n$, $x_n$ is bounded from above by $C$. And that's what Bullwinkle did.2012-12-11
  • 0
    [cont.] He assumed $p(n^2+1)$ is bounded from above by $C$ for infinitely many $n$'s, and reached a contradiction. What you showed is that there's some subsequence $p((x_{n})^{2}+1)$ that tends to infinity, but that's not enough. That is what I meant in my first comment to this answer - your method is good enough to show that $p((x_{n})^{2}+1)$ goes to infinity for some $x_n$, but it isn't strong enough to show that if $p((x_{n})^{2}+1)$ is bounded, then $x_n$ is finite, which is equivalent to what Bullwinkle did.2012-12-11
  • 0
    [cont.] He assumed $\{p(s^2+1) | s \in S \}$ is bounded from above and that $S$ is infinite and reached contradiction, hence: $\{ p((x_{n})^{2}) \}$ is bounded from above implies $\{ x_n \}$ is finite. This is just another formulation of my problem, and I wrote it like this to compare it to your statement which is written in a similar vain ($\exists x_n: \lim p((x_{n})^{2}+1) = \infty$). If this is still unclear, I can elaborate more.2012-12-11
2

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