Thursday, May 29, 2008

Circle on many lattice points

Are there radii, possibly irrational, for which there exist an arbitrarily large number of lattice points at that radius from the origin? In other words, for any fixed D, is there a limit to the number of solutions to the Diophantine Pythagorean equation a2+b2=D? If there is no limit, what is the order of growth of the number of solutions with respect to D? How many co-circular pixels can I plot on a typical display?


Anonymous said...

A circle centered at any lattice point with radius sqrt(D), where D is the product of k different primes congruent to 1 mod 4, will have 2^{k+1} lattice points on it.

This is closely related to Erdos' construction for a set of n points with many unit distances: scale a sqrt(n) x sqrt(n) grid by a factor of 1/sqrt(D) where D is less than n and the product of as many 1-mod-4 primes as possible.

Ken said...

Cool! Who'd have thought there's a relationship between circles and prime numbers.