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.

  • $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Apr 5, 2015 at 22:11
  • $\begingroup$ Not by the way, $-k$ is represented if and only if $k$ is represented. $\endgroup$
    – Will Jagy
    Apr 5, 2015 at 22:14

1 Answer 1


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:

enter image description here enter image description here

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

enter image description here

  • $\begingroup$ @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... $\endgroup$
    – Will Jagy
    Apr 5, 2015 at 18:14
  • $\begingroup$ "we may demand $v\leq \frac{u}{2}$" in appendix 2? How so ? $\endgroup$ Apr 5, 2015 at 18:30
  • $\begingroup$ @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).$ $\endgroup$
    – Will Jagy
    Apr 5, 2015 at 18:37
  • $\begingroup$ @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) $$ $\endgroup$
    – Will Jagy
    Apr 5, 2015 at 18:40
  • $\begingroup$ The question has now become, can $|u|\leq \sqrt{2k}$ be strengthened to $|u|\leq \sqrt{k}$ ? $\endgroup$ Apr 5, 2015 at 18:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .