7
$\begingroup$

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?

  • 0
    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](http://lara.inist.fr/bitstream/handle/2332/690/RR1997-45.pdf;jsessionid=C217F2640B9B9606C52C13171D9C13C6?sequence=1)2012-03-25
  • 0
    How did you get Wolfram alpha to provide integer solutions?2013-10-29
  • 0
    @LarsH I just dropped in the equation and it provided them, see the link in my question.2013-10-29

1 Answers 1

3

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
    Why does this work?2012-03-25
  • 2
    @user7530: See [the answers to this question](http://math.stackexchange.com/q/17496/11619) for more discussion.2012-03-25
  • 1
    @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.$2012-03-25
  • 0
    @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 :-)2012-03-25
  • 0
    @Jyrki, I sent you an email with a place to buy the Dickson book.2012-03-26
  • 0
    @WillJagy - does your method work for arbitrary circle equations, like the one I posted? Perhaps I'm just terrible at algebra, but I can't seem to generate a $u$ and $v$ given the equation I posted, the best I can get is $(x-10)x+(y+10)y = 0$.2012-03-26
  • 0
    @dimo414: If you "complete the square" (en.wikipedia.org/wiki/Completing_the_square) with the equation you gave, you get $(x - 5)^2 + (y - 5)^2 = 50$. That's what Will is showing in the first equation he gives.2013-10-25