UNREASONABLE EFFECTIVENESS OF NUMBER THEORY 9

where g is a primitive root of the prime p (g is a primitive root of p if its

powers,

gn,

generate all the p - 1 different nonzero integers modulo p). The

sequence rn is then periodic with period p - 1. It is not difficult to show that

the Discrete Fourier Transform Rk of (5) has constant magnitude except for

IR01 which is p times smaller than I Rk I for k #0 (mod p - 1).

Figure 3 shows a scatter diagram of a microwave reflection phase grating

based on p = 7 and g = 3. Note the attenuated zeroeth diffraction order

between the six strong "lobes" corresponding to k = ±1, ±2, ±3.

Figure 3. Scattering of electromagnetic waves from a reflection phase-grating

based on powers of a primitive root g of a prime p. (Here p = 7 and g = 3.)

Note strong reflections in the six non-specular directions and the weak

specular reflection in the center between them.

The success of phase gratings based on primitive roots raises the

following mathematical question: The least positive residues of gn modulo p

generate a permutation of the integers 1 to p - 1. The |(p - 1) primitive

roots of p generate j( p - 1) different permutations, which is typically a small