Upper bound on answer for Pell equation

Question

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

Answer 1

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

Answer 2

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.