X2+Y2

When the curve meets a lattice point (x,y) in this picture, it means that there x^2+y^2=n has an integer value. I put the prime n in red. Notice that the red line marked 3 has no dots, while the 5 line has. This pattern is the same for all primes one less and one more than a multiple of 4.
sumofsquares
The primes p\equiv 1 \bmod 4: (all crossing lattice points)
1mod4primes
The primes p\equiv 3 \bmod 4: (none cross lattice points)
3mod4primes

In these next pics, all possible values of x^2+y^2=n are shown, x and y integers \ges 0, up to a certain n.

Why there should be vertical gaps is explained by modular arithmetic and residues.

“Of two numbers possessing no common divisor one is called the quadratic residue of the other when it is congruent to a square number with respect to the other as modulus; if there is no such square number it is called a quadratic nonresidue. For example, 12 is a quadratic residue of 13, since 12\equiv8^2 \mod 13; -1 is a quadratic nonresidue of 3, since there exists no square number x^2 such that x^2\equiv -1 \mod 3.” (Dörrie)

I don’t know if there’s a name for the equivalent thing with sums of squares; for now I’ll call it the biquadratic residue.

Since x^2 \bmod 4 is always 0 or 1, +++ x^2+y^2\not\equiv 3 \pmod 4. (i.e. 3 is a biquadratic nonresidue of 4.)
Since x^2 \bmod 8 is 0, 1 or 4, +++ x^2+y^2\not\equiv 3, 6 \text{ or }7 \pmod 8.
Since x^2 \bmod 16 is 0, 1, 4 or 9, +++ x^2+y^2\not\equiv 3, 6,7,11,12,14 \text{ or }15 \pmod{16}.

840 = 2^3\cdot 3\cdot 5\cdot7 numbers to a row, i.e. the top line of the image shows, for the numbers n=1 to 839, a black dot where there are values of x and y such that x^2+y^2=n. Up to n=588000. (700 rows)

x2 plus y2 - lines of 840 up to 588000

Rows of 1000=2^3\cdot 5^3, up to 700,000.
x2 plus y2 - lines of 1000 up to 700000

Rows of 1024=2^{10}, up to 716,800.
x2 plus y2 - lines of 1024 up to 716800

In these next pics, only the top-leftmost part is shown.

Rows of 2310 =2\cdot 3\cdot 5\cdot 7\cdot 11, up to 1,617,000.
x2 plus y2 - lines of 2310 up to 1617000 - left half of pic

Rows of 4,620=2\cdot 2\cdot 3\cdot 5\cdot 7\cdot 11, up to 3,234,000.
x2 plus y2 - lines of 4620 up to 3234000 - left quarter of pic

Rows of 304200=2^6\cdot 3^3 \cdot 5^2\cdot 7x2y2 gaps mod 304200

Rows of 3,346,200=2^6\cdot 3^3\cdot 5^2\cdot 7\cdot 11 (i.e. only about the leftmost 1/3000th of the row shown)x2y2 gaps mod 3346200 v2

Detail of the upper-left corner of previous picture. The top row pixels are black if there are values of x and y such that x^2+y^2=0,1,2,3,\dots; the 2nd row represents 3346200,3346201,3346202,\dots etc.
Picture 11


In the following picture, the pixels of the nth row show whether 0 up to n are biquadratic residues of n or not. i.e. the white pixels show the “gaps” (biquadratic nonresidues) where no x^2+y^2 (mod n) can ever land.
All the preceding pictures use one modulus (row length) for the entire image; in these ones, each row is a different modulus.
Gaps, approx. 0 up to 700
modgaps starting at 0 to 700
Gaps, approx. 500 to 1200.
modgaps starting at 500 to 1200
Gaps, approx. 10001700.
modgaps starting at 1000 to 1700
Gaps, approx. 15002200
modgaps starting at 1500
The next pictures summarize the last ones, and plot the number of (biquadratic nonresidue) gaps (y-axis) for each modulus (x-axis). The labelled points are those moduli that have a larger number of gaps than any smaller modulus.
Number of gaps, moduli 01000
gaps 0-1000
Number of gaps, moduli 02000
gaps 0-2000
Some more x^2+y^2 pictures, with rows the length of some of those “record” moduli.
Rows of 720 = 2^4\cdot 3^2 \cdot 5
x2y2 gaps mod 720
Rows of 1152 = 2^7\cdot 3^2. (the right edge past x=1020 is cut off)
x2y2 gaps mod 1152
Rows of 1440 = 2^5\cdot 3^2\cdot 5. (Left 2/3 of the rows shown)
x2y2 gaps mod 1440


List of gaps, to \mod 100
Gaps mod 4=2.2 : 3 (i.e. there are no integer values of x and y such that x^2+y^2\equiv 3\mod 4.)
Gaps mod 8=2.2.2 : 3, 6, 7
Gaps mod 9=3.3 : 3, 6
Gaps mod 12=2.2.3 : 3, 7, 11
Gaps mod 16=2.2.2.2 : 3, 6, 7, 11, 12, 14, 15
Gaps mod 18=2.3.3 : 3, 6, 12, 15
Gaps mod 20=2.2.5 : 3, 7, 11, 15, 19
Gaps mod 24=2.2.2.3 : 3, 6, 7, 11, 14, 15, 19, 22, 23
Gaps mod 27=3.3.3 : 3, 6, 12, 15, 21, 24
Gaps mod 28=2.2.7 : 3, 7, 11, 15, 19, 23, 27
Gaps mod 32=2.2.2.2.2 : 3, 6, 7, 11, 12, 14, 15, 19, 22, 23, 24, 27, 28, 30, 31
Gaps mod 36=2.2.3.3 : 3, 6, 7, 11, 12, 15, 19, 21, 23, 24, 27, 30, 31, 33, 35
Gaps mod 40=2.2.2.5 : 3, 6, 7, 11, 14, 15, 19, 22, 23, 27, 30, 31, 35, 38, 39
Gaps mod 44=2.2.11 : 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43
Gaps mod 45=3.3.5 : 3, 6, 12, 15, 21, 24, 30, 33, 39, 42
Gaps mod 48=2.2.2.2.3 : 3, 6, 7, 11, 12, 14, 15, 19, 22, 23, 27, 28, 30, 31, 35, 38, 39, 43, 44, 46, 47
Gaps mod 49=7.7 : 7, 14, 21, 28, 35, 42
Gaps mod 52=2.2.13 : 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51
Gaps mod 54=2.3.3.3 : 3, 6, 12, 15, 21, 24, 30, 33, 39, 42, 48, 51
Gaps mod 56=2.2.2.7 : 3, 6, 7, 11, 14, 15, 19, 22, 23, 27, 30, 31, 35, 38, 39, 43, 46, 47, 51, 54, 55
Gaps mod 60=2.2.3.5 : 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59
Gaps mod 63=3.3.7 : 3, 6, 12, 15, 21, 24, 30, 33, 39, 42, 48, 51, 57, 60
Gaps mod 64=2.2.2.2.2.2 : 3, 6, 7, 11, 12, 14, 15, 19, 22, 23, 24, 27, 28, 30, 31, 35, 38, 39, 43, 44, 46, 47, 48, 51, 54, 55, 56, 59, 60, 62, 63
Gaps mod 68=2.2.17 : 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67
Gaps mod 72=2.2.2.3.3 : 3, 6, 7, 11, 12, 14, 15, 19, 21, 22, 23, 24, 27, 30, 31, 33, 35, 38, 39, 42, 43, 46, 47, 48, 51, 54, 55, 57, 59, 60, 62, 63, 66, 67, 69, 70, 71
Gaps mod 76=2.2.19 : 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75
Gaps mod 80=2.2.2.2.5 : 3, 6, 7, 11, 12, 14, 15, 19, 22, 23, 27, 28, 30, 31, 35, 38, 39, 43, 44, 46, 47, 51, 54, 55, 59, 60, 62, 63, 67, 70, 71, 75, 76, 78, 79
Gaps mod 81=3.3.3.3 : 3, 6, 12, 15, 21, 24, 27, 30, 33, 39, 42, 48, 51, 54, 57, 60, 66, 69, 75, 78
Gaps mod 84=2.2.3.7 : 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83
Gaps mod 88=2.2.2.11 : 3, 6, 7, 11, 14, 15, 19, 22, 23, 27, 30, 31, 35, 38, 39, 43, 46, 47, 51, 54, 55, 59, 62, 63, 67, 70, 71, 75, 78, 79, 83, 86, 87
Gaps mod 90=2.3.3.5 : 3, 6, 12, 15, 21, 24, 30, 33, 39, 42, 48, 51, 57, 60, 66, 69, 75, 78, 84, 87
Gaps mod 92=2.2.23 : 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83, 87, 91
Gaps mod 96=2.2.2.2.2.3 : 3, 6, 7, 11, 12, 14, 15, 19, 22, 23, 24, 27, 28, 30, 31, 35, 38, 39, 43, 44, 46, 47, 51, 54, 55, 56, 59, 60, 62, 63, 67, 70, 71, 75, 76, 78, 79, 83, 86, 87, 88, 91, 92, 94, 95
Gaps mod 98=2.7.7 : 7, 14, 21, 28, 35, 42, 56, 63, 70, 77, 84, 91
Gaps mod 99=3.3.11 : 3, 6, 12, 15, 21, 24, 30, 33, 39, 42, 48, 51, 57, 60, 66, 69, 75, 78, 84, 87, 93, 96
Gaps mod 100=2.2.5.5 : 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83, 87, 91, 95, 99


“Record” gaps.
4 (2.2) has 1 gap. (i.e. 3 : there are no integer values of x and y such that x^2+y^2\equiv 3\mod 4.)
8 (2.2.2) has 3 gaps.
16 (2.2.2.2) has 7 gaps.
24 (2.2.2.3) has 9 gaps.
32 (2.2.2.2.2) has 15 gaps.
48 (2.2.2.2.3) has 21 gaps.
64 (2.2.2.2.2.2) has 31 gaps.
72 (2.2.2.3.3) has 37 gaps.
96 (2.2.2.2.2.3) has 45 gaps.
112 (2.2.2.2.7) has 49 gaps.
128 (2.2.2.2.2.2.2) has 63 gaps.
144 (2.2.2.2.3.3) has 81 gaps.
192 (2.2.2.2.2.2.3) has 93 gaps.
216 (2.2.2.3.3.3) has 111 gaps.
256 (2.2.2.2.2.2.2.2) has 127 gaps.
288 (2.2.2.2.2.3.3) has 169 gaps.
360 (2.2.2.3.3.5) has 185 gaps.
384 (2.2.2.2.2.2.2.3) has 189 gaps.
416 (2.2.2.2.2.13) has 195 gaps.
432 (2.2.2.2.3.3.3) has 243 gaps.
504 (2.2.2.3.3.7) has 259 gaps.
576 (2.2.2.2.2.2.3.3) has 345 gaps.
720 (2.2.2.2.3.3.5) has 405 gaps.
792 (2.2.2.3.3.11) has 407 gaps.
864 (2.2.2.2.2.3.3.3) has 507 gaps.
1008 (2.2.2.2.3.3.7) has 567 gaps.
1152 (2.2.2.2.2.2.2.3.3) has 697 gaps.
\vdots
1872 (2.2.2.2.3.3.13) has 1053 gaps.
2016 (2.2.2.2.2.3.3.7) has 1183 gaps.
2160 (2.2.2.2.3.3.3.5) has 1215 gaps.

Leave a Reply

Your email address will not be published.