Small integral representation as $x^2-2y^2$ in Pell's equation

Let $k$ be a "representable" positive integer, in the sense that $k=|x^2-2y^2|$ for some integers $x,y$. Does it necessarily follow that $k$ can also be represented with small parameters, i.e. $k=|u^2-2v^2|$ with $|u|\leq\sqrt{k},|v|\leq\sqrt{k}$ ?

My (mostly useless) thoughts : if $N$ is very big and $a_N,b_N$ are the unique integers such that $a_N+b_N\sqrt{2}=(\sqrt{2}-1)^N(x+y\sqrt{2})$, then $|a_N+b_N\sqrt{2}|$ can be arbitrarily small, but unfortunately that doesn't make the individual $a_N$ and $b_N$ small.

Also, we know that $k$ is representable iff all the prime divisors of $k$ are such that $2$ is a quadratic residue to them, but that doesn't seem to help either.

• just realized the possible significance of your absolute value signs. If you are willing to have, with $k >0,$ the representation $u^2 - 2 v^2 = -k,$ then you actually do achieve the bounds you wanted, $$u \leq \sqrt k, \; \; v \leq \sqrt k.$$ Diagram and summary edited into answer. – Will Jagy Apr 5 '15 at 22:11
• Not by the way, $-k$ is represented if and only if $k$ is represented. – Will Jagy Apr 5 '15 at 22:14

Appendix 1: all pairs $(u,v)$ in the tree depicted satisfy $u \geq 2v.$ As a result, $$k = u^2 - 2 v^2 \geq 4 v^2 - 2v^2 = 2 v^2,$$ so $$2 v^2 \leq k$$ and $$\color{blue}{ v \leq \sqrt {\frac{k}{2}}}.$$

Appendix 2: we may demand $$v \leq \frac{u}{2}.$$ Therefore $$2 v^2 \leq \frac{u^2}{2},$$ $$-2 v^2 \geq - \frac{u^2}{2},$$ $$k = u^2 -2 v^2 \geq u^2 - \frac{u^2}{2} = \frac{u^2}{2},$$ $$u^2 \leq 2 k,$$ $$\color{blue}{ u \leq \sqrt {2k}}.$$

preliminary: I already think you are roughly correct. The Conway topograph method deals most directly with $u+v$ when both are positive. The largest variables come from $$u = 2n + 1, \; \; v = n, \; \; u^2 - 2 v^2 = 2 n^2 + 4 n + 1$$ Note that this "branch" of the tree illustrates both inequalities well, $u \leq \sqrt {2k}$ and $v \leq \sqrt {\frac{k}{2}}.$

I have answered several questions with these diagrams, also the book describing the method is at CONWAY. The point is that any (positive) number represented occurs in the first tree on the positive side of the river:

Just noticed the absolute values in the original question. If you are willing to represent $-k$ instead of $k,$ you get the bounds you wanted. This happens in an upside-down tree below the river where we have $u^2 - 2 v^2 = -k$ for positive $k,$ and with $u,v > 0$ and $v \geq u.$ Similar arguments to the above give your desired bounds, $$u \leq \sqrt k, \; \; \; v \leq \sqrt k.$$

• @EwanDelanoy, that is the real story, how we decide on size of a pair $(u,v).$ I just got one case which gives an explicit bound on $v.$ Typing... – Will Jagy Apr 5 '15 at 18:14
• "we may demand $v\leq \frac{u}{2}$" in appendix 2? How so ? – Ewan Delanoy Apr 5 '15 at 18:30
• @EwanDelanoy, every (primitively) represented positive number is represented in the tree depicted; any two $(u,v)$ pairs in the tree, depicted as a (green) column vector, have $u \geq 2 v,$ and add up to a new pair one number out which still satisfies $u \geq 2v,$ as $(3,1) + (5,2) = (8,3).$ – Will Jagy Apr 5 '15 at 18:37
• @EwanDelanoy, I suspect you can make an argument with no diagrams, given positive $(u,v)$ with positive $k$ and the ratio $v/u$ not big enough, repeatedly use the mappng $$(u,v) \mapsto (3u-4v, -2u+3v)$$ – Will Jagy Apr 5 '15 at 18:40
• The question has now become, can $|u|\leq \sqrt{2k}$ be strengthened to $|u|\leq \sqrt{k}$ ? – Ewan Delanoy Apr 5 '15 at 18:44