Wolfram Alpha will provide integer solutions to arbitrary circle equations. I'm trying to understand how it's able to calculate them, but despite a fair bit of digging I haven't found any discussion of how to get either the number of, or which, integer solutions to a given circle. Plenty of discussion of lattice points inside a circle, related to the Gauss circle problem, and some discussion of circles centered on the origin, but nothing for the general case.

Wolfram Alpha can quickly determine there are $12$ integer solutions to the circle $x^2-10 (x+y)+y^2+50 = 50$ - how?

  • $\begingroup$ Someone should read through this paper, and figure out the exact ${\cal O}(\cdot)$ time complexity: Felipe Cucker Pascal Koiran and Steve Smale, A Polynomial Time Algorithm for Diophantine Equations in One Variable PDF file $\endgroup$ – user2468 Mar 25 '12 at 6:05
  • $\begingroup$ How did you get Wolfram alpha to provide integer solutions? $\endgroup$ – LarsH Oct 29 '13 at 16:22
  • $\begingroup$ @LarsH I just dropped in the equation and it provided them, see the link in my question. $\endgroup$ – dimo414 Oct 29 '13 at 17:42

As long as the coefficients of $x^2, \; y^2$ are $1$ and the coefficients of $x,y$ are even, this is quite easy. What you get by completing two squares is $$ (x-5)^2 + (y-5)^2 = 50. $$ Fine, so define new variables, $$ u = x-5, \; \; \; v = y - 5, $$ and count the (integer pair) solutions to $$ u^2 + v^2 = 50. $$ For each pair, return by $x = u + 5, \; \; y = v + 5.$ It is easy enough to plot these.

However, what if you had some very large target number $n$ and had to count the number of integer pair solutions to $$ u^2 + v^2 = n? $$ Well, if you can factor $n,$ you can make a complete list of all numbers that divide it, including $1$ and $n$ itself. Ignore the even divisors. Count the number of divisors that leave a remainder of 1 when divided by 4, call that count $C_1.$ Put another way, this is the count of $d > 0, \; \; d | n, \; \; d \equiv 1 \pmod 4.$ Next, count the number of divisors that leave a remainder of 3 when divided by 4, call that count $C_3.$ This is the count of $d > 0, \; \; d | n, \; \; d \equiv 3 \pmod 4.$ The number of integer lattice points on the circle is $$ 4 (C_1 - C_3).$$ For $n = 50,$ the divisors are $1,2,5,10,25,50.$ So $C_1 = 3$ and $C_3 = 0,$ and the number of integer points is $4 (3-0) = 4 \cdot 3 = 12.$

  • 2
    $\begingroup$ Why does this work? $\endgroup$ – user7530 Mar 25 '12 at 6:57
  • 2
    $\begingroup$ @user7530: See the answers to this question for more discussion. $\endgroup$ – Jyrki Lahtonen Mar 25 '12 at 7:36
  • 1
    $\begingroup$ @Jyrki, this description is Theorem 65 on page 80 of Introduction to the Theory of Numbers by Leonard Eugene Dickson, (1929). Proper representations are Theorems 61 and 62 on page 76. I probably have more recent books that give the "excess of divisors" method. Dickson does some other forms with class number one in exercises on pages 80-81. Rather cute, in a footnote he points to his own 1911 proof that there are no extra discriminants of class number one to $-1,500,000.$ $\endgroup$ – Will Jagy Mar 25 '12 at 20:40
  • $\begingroup$ @WillJagy, thanks for the reference. I really should get my hands on a copy of that book :-). I've seen, e.g. Carlitz refer to it on at least couple occasions. I recently spent some time on a cute but not deep problem. Found a reference from 70s, another from the late 50s. Then in a paper Carlitz says that the result is an exercise (!) in Dickson's book :-) $\endgroup$ – Jyrki Lahtonen Mar 25 '12 at 21:31
  • $\begingroup$ @Jyrki, I sent you an email with a place to buy the Dickson book. $\endgroup$ – Will Jagy Mar 26 '12 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.