Saturday, July 21, 2012

Quadratic residue gaps

In an earlier post I went through the equations covering spacing of quadratic residues:

If integer solutions for x2 - Dy2 = F exist, it must be true that:

2ky = z - Fz-1 mod D-k2

(z-ky)2 = k2y2 + F mod D-k2

Where x = z-ky or x = -(z-ky), and z is any residue for which the modular inverse exists. Here there is the additional requirement that 2kyz + F = -1 or 1 mod 8, or 0 mod 4, if D-k2 is a square.

Now I'll consider the related subject of gaps between quadratic residues. And I'll start with k=1:

2y = z - Fz-1 mod D-1

(z-k)2 = y2 + F mod D-1

The possibility of a gap is determined by the value of F, but these equations must exist! Where for x and y to have integer solutions, we have that F must be a quadratic residue modulo D, from x2 - Dy2 = F.

To get perspective on the number theory mechanism and how the gaps are different from the spacing consider the quadratic residues of 19:

1, 4, 5, 6, 7, 9, 11, 16, 17

And notice that 4 is one away from 5, but 2 away from 6, while 7 is two away from 9, with a gap of 2.

For the control equations with k=1 we'd need D=20 with F=2, which is: x2 - 20y2 = 2

And there are no integer solutions for x and y, and notice that 20 doesn't have 2 as a quadratic residue.

The quadratic residues for 20 are: 1, 4, 5, 9, 16

But let k = 2, then D=23, and still with F = 2, the control equations are:

4y = z - 2z-1 mod 19

(z-2y)2 = 4y2 + 2 mod 19

And now consider the quadratic residues of 23, which are:

1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18

And 2 is there as needed to allow the gap of 2 with 19, but notice it doesn't mean there actually is such a gap! We know there is one because we looked but the equations are actually simply allowing a spacing of 2, where we could see two examples with the quadratic residues of 19.

Looking over the quadratic residues for 19, I'm more interested now in what is not allowed as a spacing, and it looks like only 17, for obvious reasons, which is boring but not surprising with quadratic residues of primes.

And by observation I see that 5 is the widest gap between the quadratic residues of 19, and at this point I'm not sure why, so it's something to ponder. But things should be much more interesting with composites, where there should be potential for bigger gaps, as there are fewer quadratic residues.

For instance for 16 the quadratic residues are: 1, 4, 9

So spacings appear to be 3, 5 and 8, but gaps are only 3 and 5.

Looking at the control equations, starting with k=1, so I'd have x2 - 17y2 = F, then:

2y = z - Fz-1 mod 16

(z-y)2 = k2y2 + F mod 16

And it's easy to see how a lot of possibles are blocked which is that the modular inverse won't exist for any even z's. But what does that have to do with F? Not much I guess.

Looking at quadratic residues of 17 they are:

1, 2, 4, 8, 9, 13, 15, 16

And 3 and 5 don't even make the list, so F = 3 or 5 mod 16 isn't allowed. So F may not even be able to equal a spacing that you can see from the actual quadratic residues. Interesting.

Oh, forgot the additional requirement: 2kyz + F = -1 or 1 mod 8, or 0 mod 4, if D-k2 is a square.

These things can get convoluted and you have to keep up with all the rules! Maybe should have looked at 21 or 32 instead. Maybe later.

So not much progress here. But putting up things to ponder.

At this point I'm not sure how you find the gaps then! Spacing doesn't tell you that a gap exists as explained above, so it's an open problem on which I might ponder for a while. Cool!

James Harris