It is one of the first things we learn in algebra that x²+2xy+y²=(x+y)² and x²-2xy+y²=(x-y)², and so the quadratic forms in the title are certainly squares for integer x and y when N=2.

The question is: for what values of N can we find non-zero integers such that both forms are squares?

The history of such forms is discussed in Chapter 16 of volume 2 of Dickson's History. It is stated that Adrain and Genocchi had shown that the problem is not soluble for N=1.

Assume x²+Nxy+y²=a² and x²-Nxy+y²=b², and let x/y=z and b/y=d in the second equation.

Thus

d2  =  z2 - N z + 1

which passes through z = 0, d = 1.

The line d = 1 + m z meets this quadratic at z = 0 and z = ( 2 m + N ) / (1- m²). Setting m = p / q, we derive the parameterisation of the second quadratic form as x = q ( N q + 2 p ) and y = q² - p².

Substituting into   a²  =  x² + N x y + y², we get

a2  =  p4 - 2 N p3 q  +  ( 2 - N2 ) p2 q2  +  6 N p q3  +  ( 2 N2 + 1 ) q4

This quartic has an obvious rational solution, and so we can find a birational transformation to an elliptic curve. We find the curves to be

EN :  w2  =  v3 + 2 ( N2 + 4 ) v2  +  ( N2 - 4 )2 v

which can be written

EN :  w2  =   v ( v + ( N + 2)2 ) ( v + ( N - 2)2 )

with the transformation

p q   =  N v + w + N ( N2 - 4 ) 2 ( v - N2 + 4 )

As an example, if N = 7, the curve E₇ is w² = v³ + 106v² + 2025v. This contains the point v = -135/4, w = 945/8, which gives p/q = -5/4. Setting p = -5, q = 4 leads to x = 72, y = -9. Since the forms are homogeneous we can divide out common factors, and the symmetry of the problem allows us to ignore minus signs. We have x = 8, y = 1 with 8² + 7*8*1 + 1² = 11² and
8² - 7*8*1 +1² = 3².

The curves E_N have clearly 3 finite points of order 2, when v = 0,
v = - ( N + 2)², v = -( N - 2)².  Points of order 4 also occur when v=±(N²-4), so that the torsion points form a subgroup isomorphic to Z2 ×Z4 or Z2 ×Z8. Computations suggest the former but I can't prove this. None of these 8 points lead to a non-zero solution.

Thus we need to find curves with rank > 0. Use of the Birch and Swinnerton-Dyer conjecture produced estimates of the rank for 1 £ N £ 999. The distribution of ranks is given in the following table (the 1-99 results exclude N=2).
 

For those values with positive rank, we have found points on most of the curves and hence values of x and y solving the initial problem. The solutions can be found in this file.

Recently (Feb/Mar 2004) I attacked some unsolved curves with a new faster computer and a mixture of my codes and John Cremona's ratpoint code. This has allowed me to reduce the number of unsolved values to 19.

The values of N where we don't have a point on the curve are given in the following table. If anyone can find a point on one of these curves, please let me know. Randall Rathbun has been very successful in computing the large height solutions. Thanks to him, there only 2 values of N left unresolved as of 5 January 2006. Both curves seem to lack isogenous curves with points of lower height so it will be difficult to find these solutions, though not imposssible.
 
 

As of 27 November 2006, all N in [1,999] have now been solved. The final N=809 solution was produced through the combined efforts of Tom Fisher, Mark Watkins and Randall Rathbun.

I might get round to extending this range, but not soon!!

As a development of the above discussion, we next considered the similar problem of finding integers x and y with  x²  - y²  + N x y = a²   and   x²  - y²  - N x y = b² . We can parameterise the second form  as  x = p²  + q²  and y = q ( 2 p - N q ). Substituting into the first form we get a quartic with an obvious rational solution, so equivalence to the elliptic curves

FN :  w2  =  v3 + 2 ( N2 - 4) v2  +  ( N2 + 4 )2 v

Use of the Birch and Swinnerton-Dyer conjecture for the range of 1 to 999 for N produces much larger height estimates for F_N than for the curves E_N. In fact, there are seven values which give estimates of over 1000, with the largest being an estimate of 3604 for N = 953. It is difficult to know if these are true estimates or are affected by large values from the unknown Tate-Safarevic group component of the Birch-Swinnerton-Dyer estimate. There are so many values of N with large height estimates that we have not attempted to find points on these curves.

As an example of the sizes even for small N, N=13 gives a height estimate of  11, and a point with v=4039110916/107184609 and w=1425398791591970/1109682256977.

This leads to p=6136418609 , q=1141873782, and so

x=38959509078900478405 and y=2936353492258767336.