# Upper bound on answer for Pell equation

A user on MSE, @martin , asked https://math.stackexchange.com/questions/1611411/pell-equations-upper-bound about an upper bound for $x$ in $x^2 - p y^2 = 1,$ when $p$ is prime. I checked, it appears reasonable to guess that $$x < p^{\sqrt p}$$ when $p > 2.$ I had the computer solve by Lagrange's method, no continued fractions, no decimal accuracy required, no memory required, but the method is still elementary. I had the machine print out whenever $\log_p(\log_p(x))$ increased. It was necessary to take $p > 2$ because $x=3$ gives an overly large logarithm. Meanwhile, if all we do is print whenever $x$ itself increases, there are several composite numbers below $100$ that get included, after that they give way to primes $p \equiv 1 \pmod 4.$ I put in a fair amount of effort but was unable to draw any firm conclusions.

So, the questions would be, (I) what is unconditionally proved about the size of $x,$ (II) what is proved under conjectures that people mostly believe true, (III) what are the most optimistic things conjectured?

p
5        log_p(x)     1.365212388971971   log_p(log_p(x)) 0.1934277864616169   X 9
13       log_p(x)     2.524585016802303   log_p(log_p(x)) 0.3610506760085375   X 649
61        log_p(x)    5.17947382679923   log_p(log_p(x))  0.4000860954668999   X 1766319049
109      log_p(x)     6.969012778576543   log_p(log_p(x)) 0.4138413148682316   X 158070671986249
421      log_p(x)    12.79922341582056   log_p(log_p(x))  0.4218996203501611   X 3879474045914926879468217167061449
1621     log_p(x)    23.61505725662223   log_p(log_p(x))  0.4278136548619654   X 6298101812493732343034974500091457815529942308667051412857352310169665125001
.....................
44450701  log_p(x) 2641.408511213517     log_p(log_p(x))  0.4474228404332914   X  is rather large...


Why not, here is how it begins if we print every time $x$ increases and make no requirement about loglog, allowing $n$ composite in $x^2 - n y^2$ with $2 \leq n \leq 500$

2  log_p(x) 1.584962500721156   log_p(log_p(x))   0.6644487074538893   X 3
5  log_p(x) 1.365212388971971   log_p(log_p(x))   0.1934277864616169   X 9
10  log_p(x) 1.278753600952829   log_p(log_p(x))  0.1067868696893203   X 19
13  log_p(x) 2.524585016802303   log_p(log_p(x))  0.3610506760085375   X 649
29  log_p(x) 2.729264122987999   log_p(log_p(x))  0.298171610554983   X 9801
46  log_p(x) 2.637925539730376   log_p(log_p(x))  0.2533517055829028   X 24335
53  log_p(x) 2.79606031271967   log_p(log_p(x))   0.258976271165875   X 66249
61  log_p(x) 5.17947382679923   log_p(log_p(x))   0.4000860954668999   X 1766319049
109  log_p(x) 6.969012778576543   log_p(log_p(x)) 0.4138413148682316   X 158070671986249
181  log_p(x) 8.146702019142648   log_p(log_p(x)) 0.4035037766708247   X 2469645423824185801
277  log_p(x) 8.271023203635528   log_p(log_p(x)) 0.3756670785256742   X 159150073798980475849
397  log_p(x) 8.05129073299257   log_p(log_p(x))  0.3485719633766078   X 838721786045180184649
409  log_p(x) 8.576275777667302   log_p(log_p(x)) 0.3573497754649824   X 25052977273092427986049
421  log_p(x) 12.79922341582056   log_p(log_p(x)) 0.4218996203501611   X 3879474045914926879468217167061449

• I'm sure you would have done, but if you re-ask a question I have asked previously, I wonder if I could ask you to keep me (or the original asker) updated re any response you get, as of course, I am interested. – martin Jan 28 '16 at 13:36
• @martin you are right, sorry. This question now refers to your MSE question rather than one of my answers, and mentions you by username. I also put a comment at your MSE question linking back to here. – Will Jagy Jan 28 '16 at 18:18
• many thanks - we have some nice answers now, so it was a good thing you asked here! – martin Jan 28 '16 at 19:19

Let $d$ be a positive fundamental discriminant, $\epsilon_d$ denote the fundamental unit, $h(d)$ the class number, and $\chi_d$ the primitive character associated to the discriminant $d$. The class number formula gives $$\log \epsilon_d = \sqrt{d} L(1,\chi_d)/h(d) \le \sqrt{d} L(1,\chi_d),$$ since the class number $h(d) \ge 1$. Now it is known that $L(1,\chi_d) \le C \log d$ for a constant $C$. This upper bound is completely effective. The best known constant $C$ is (for large enough $d$) $$\frac{1}{4} \Big(2-\frac{2}{\sqrt{e}} \Big).$$ If we knew something about how small primes split in ${\Bbb Q}(\sqrt{d})$ then this could be improved by taking those Euler factors into account (for example, we can use this if $d$ is even which would happen for primes $p\equiv 3\pmod 4$ in the question). This is a result of P.J. Stephens and uses the Burgess bound for character sums (together with an argument from multiplicative number theory along the lines of Vinogradov's $1/\sqrt{e}$ argument for the least quadratic non-residue). For a discussion of Stephens's result and extensions, see Granville and Soundararajan.
This would be enough to give your conjecture of $p^{C\sqrt{p}}$ (one needs a little care to go from the fundamental unit to the solution to Pell's equation -- i.e. one might need to take a small power of the fundamental unit). Also see this paper of Hua which explicitly states a bound along the lines you want, tracing it back to Schur. Finally, Louboutin has looked at explicit upper bounds for $L(1,\chi)$ (see Theorem 5.1 there).
The above results are unconditional. On GRH one can do a bit better, since $L(1,\chi_d)$ may then be bounded by $C\log \log d$, and then one would get a better bound of $(\log p)^{C\sqrt{p}}$ in your problem (see Theorem 1.5 of this paper for an explicit GRH bound), and I think that can probably happen (although this is not clear since we don't know that the class number can get down to $1$). Jacobson, Lukes and Williams report on extensive calculations on regulators, and at the end of the paper state the belief that the fundamental unit can get as large as $\exp(c \sqrt{d}\log \log d)$; however, as also noted there, unconditionally we only know that the fundamental unit (or the solution in Pell's equation) sometimes gets as large as $\exp(c(\log d)^4)$ -- so there is a very large gap in our understanding. (See also my answer to the related MO question Upper bound for class number of a real quadratic field .)
Let $u_0=x_0+y_0\sqrt{p}$ be the smallest solution with $x_0,y_0>0$. (I assume you're talking about an upper bound for the smallest solution, since obviously there are solutions that are arbitrarily large.) Also let $h_p$ denote the class number of the ring of integers of $\mathbb Q(\sqrt p)$. Then Siegel's theorem says that $$\lim_{p\to\infty} \frac{\log\bigl(h_p\log|u_0|\bigr)}{\log\sqrt p} = 1.$$ So at least approximately, we have $$|x_0| < |u_0| \approx \exp(\sqrt p/h_p) = p^{{\sqrt p}/{(h_p\log p)}} \le p^{\sqrt p/\log p}.$$ So this is a little better than your conjecture, but it's probably hard to see experimentally that $1/\log p$ in the exponent. And of course, the upper bound gets better as the class number increases, but conjecturally $h_p=1$ infinitely often, so in general one can't do better. Siegel's theorem is ineffective, but it may be that the upper bound you want is effective and the ineffectivity is in the lower bound.
• You only get from this a bound of $\exp(p^{1/2+\epsilon})$. Please see argument in my answer below. – Lucia Jan 27 '16 at 23:28
• @Lucia I stated Siegel's theorem precisely and then prefaced the rest of the post with "at least approximately." The poster is looking at experimental data, so rather than guessing a bound of $p^{\sqrt p}$, he'd be better off first trying to estimate the growth rate of the upper bound for $\log|x_0|$, which would hide some of the lower order phenomena. Then, as you say, one should be able to guess $\gg\ll p^{1/2\pm\epsilon}$. Following Siegel blindly and pretending lower order terms don't exist gives what I wrote; I made no claim it was accurate. Thanks for being more precise. – Joe Silverman Jan 28 '16 at 2:50