Thursday, September 10, 2020

When are both x^2+3y and y^2+3x both squares, and a more general question

 In my last post (see here) I asked two math questions. In this post I discuss one of them. (I will discuss the other one later, probably Monday Sept 14.)

For which positive naturals x,y are x^2+3y and y^2+3x both squares?

I found this in a math contest book and could not solve it, so I posted it to see what my readers would come up with. They came up with two solutions, which you can either read in the comments on that post OR read my write up here.)

The problem raises two more general questions

1) I had grad student Daniel Smolyak write a program that showed that if  1\le x,y \le 1000 then the only solutions were (1,1) and (11,16) and (16,11).  (See write up for why the program did not have to look like anything close to all possibly (x,y).)  

Is there some way to prove that if the only solutions for 1\le x,y\le N (some N) are the three given above, then there are no other solutions?

2) Is the following problem solvable: Given p,q in Z[x,y] determine if the number of a,b such that both p(a,b) and q(a,b) are squares is finite or infinite.  AND if finite then determine how many, or a bound on how many.

Can replace squares with other sets, but lets keep it simple for now. 


  1. Replies
    1. Surely you are correct, or were correct, as I have fixed it.


  2. I'm not an expert, but I think that the general question (2) is "a little bit" harder than the one in the last post because it falls in the "neighbourhood" of the Hilbert's 10th problem.

    We know that:
    - deciding if a polynomial equation in 11 variables has integer solutions is undecidable
    - deciding if a polynomial equation in 1 variable has integer solutions is decidable

    But I think that everything in between is unknown (even for the 2 variables case).

    And deciding whether p in Z[x1,x2] has integer solutions (p(x1,x2)=0) can be reduced to your problem:

    p' = 1 - p * p
    q' = p'

    p'(x1,x2), q'(x1,x2) are both squares iif p(x1,x2)=0

  3. I would be curious if the program would give incorrect results if take up to larger values to check due to precision errors.

    1. Lots of languages have libraries to do arbitrary precision (integer) math, or have it build in.

      I also made a program searching for solutions, going all the way up to 100,000,000, using arbitrary big integers to avoid any precision errors:

  4. New Optimization Era: