A Look at Residues
Vector 8:2, page 137
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 137
One of the joys of APL is the ease with which it is possible to generate residues, for example the quadratic residues R of 13 are given by:
In this article we will be concerned with cubic and higher order residues, especially as quadratic residues have peculiar properties not possessed by other residues.
Cubic Residues¶
Consider the sequence:
⎕←R←P|(⍳¯1+P←13)*3
1 8 1 12 8 8 5 5 1 12 5 12
⎕←A←(R⍳R)=⍳⍴R 1)
1 1 0 1 0 0 1 0 0 0 0 0
⎕←X←¯1↑A/⍳⍴A
7
For any prime P of the form 1+3K, P = 7 13 19 31 … we arrive at a number X = 3 7 10 17 … which it turns out has not before been seen by science! What properties does it have? It is related to W defined by:
An alternative definitions of X is:
We have:
We get the value unity for any of the primes P = 7 13 19 31 … . If V is the vector \((x, y, z)\) then 2) becomes the equation:
This result has been published [1].
A natural question is how many binomial coefficients, that is members of Pascal’s Triangle, are residues. Binomial coefficients are given by ⍳K, +\⍳K, +\+\⍳K, etc. Continuing our APL:
Which we see has the same values as V except in a different order. This is true for any of the primes 7 13 19 31 … . Now consider the following:
B←P|+\⍳P ⍝ binomial coefficients.
C←2
U1←+/B∊R
U2←+/B∊P|R×C
U3←+/B∊P|R×C*2
(U1,U2,U3)+(P+2)÷3
8 11 7
Which again is the same as V to within permutations, and is for any C which is a cubic non-residue. e.g. for C←4 we get 8 7 11.
This is also true for all P = 7 13 19 …
Higher Order Residues¶
We can now press on to look at quartics:
R←13|(⍳¯1+P←13)*4
B←P|+\⍳P
C←2
U1←+/B∊R
U2←+/B∊P|R×C
U3←+/B∊P|R×C*2
U4←+/B∊P|R×C*3
U1,U2,U3,U4
4 4 2 1
Then we find:
In this case C is arbitrary except that it needs to be a quadratic non-residue. This is true for any p of the form 1 + 4K. There are many proofs of the fact that primes of the form 1 + 4K can be expressed as the sum of two squares \(p = x^2 + y^2\) but these do not generally specify values for \(x\) and \(y\).
This result generalises to primes of the form 1 + nK for any n > 2. Define a vector U length N where
Suppose that N is odd then
C is to a large extent arbitrary and can be any "primitive root" of P. Thus U×(?N-1)⌽U is constant. That is we have generated points round a circle such that when we rotate the circle, multiply coinciding points and add, we always get the same answer irrespective of the amount of the rotation.
For example if P = 31, N = 5, C = 3 we find U = 6 8 2 5 8.
If N is even then we have:
Instead of the above binomial coefficients given by B it apparently makes sense to look at further binomial coefficients, or more generally any polynomial and then use the same formula 5).
C F Gauss found formulae similar to 3) and 4). "Notions before notations" is a motto of his. However at that time APL had not yet been born. These investigations were prompted by the author from notation that is formula 1) which produces a Boolean string prompting the question where is the maximum unit value. We have a proof of 6) and 7) which are apparently original results.
This subject has connections with orthogonal experimental designs which are concerned with constructing orthogonal vectors of the same dimension, whose elements come from the same set of numbers. The vectors given by K⌽U are quasi-orthogonal; that is the angle between any two of them is non-zero but is the same.
Reference¶
[1] S Wynne, Minimising a Form, Problem 90.6, The Mathematical Intelligencer, Summer 1990.