International
Tables for Crystallography Volume B Reciprocal space Edited by U. Shmueli © International Union of Crystallography 2010 
International Tables for Crystallography (2010). Vol. B, ch. 1.3, pp. 8285

As was the case in the absence of symmetry, the two previous classes of algorithms can only factor the global transform into partial transforms on prime numbers of points, but cannot break the latter down any further. Rader's idea of using the action of the group of units to obtain further factorization of a pprimary transform has been used in `scalar' form by Auslander & Shenefelt (1987), Shenefelt (1988) and Auslander et al. (1988). It will be shown here that it can be adapted to the crystallographic case so as to take advantage also of the possible existence of nfold cyclic symmetry elements in a twodimensional transform (Bricogne & Tolimieri, 1990). This adaptation entails the use of certain rings of algebraic integers rather than ordinary integers, whose connection with the handling of cyclic symmetry will now be examined.
Let G be the group associated with a threefold axis of symmetry: with . In a standard trigonal basis, G has matrix representationin real space,in reciprocal space. Note thatand thatso that and are conjugate in the group of unimodular integer matrices. The group ring is commutative, and has the structure of the polynomial ring with the single relation corresponding to the minimal polynomial of . In the terminology of Section 1.3.3.2.4, the ring structure of is obtained from that of by carrying out polynomial addition and multiplication modulo , then replacing X by any generator of G. This type of construction forms the very basis of algebraic number theory [see Artin (1944, Section IIc) for an illustration of this viewpoint], and as just defined is isomorphic to the ring of algebraic integers of the form under the identification . Addition in this ring is defined componentwise, while multiplication is defined by
In the case of a fourfold axis, with , and is obtained from by carrying out polynomial arithmetic modulo . This identifies with the ring of Gaussian integers of the form , in which addition takes place componentwise while multiplication is defined by
In the case of a sixfold axis, with , and is isomorphic to under the mapping since .
Thus in all cases where is an irreducible quadratic polynomial with integer coefficients.
The actions of G on lattices in real and reciprocal space (Sections 1.3.4.2.2.4, 1.3.4.2.2.5) extend naturally to actions of on in which an element of acts viain real space, and viain reciprocal space. These two actions are related by conjugation, sinceand the following identity (which is fundamental in the sequel) holds:
Let us now consider the calculation of a twodimensional DFT with nfold cyclic symmetry for an odd prime . Denote by . Both the data and the results of the DFT are indexed by : hence the action of on these indices is in fact an action of , the latter being obtained from by carrying out all integer arithmetic in modulo p. The algebraic structure of combines the symmetrycarrying ring structure of with the finite field structure of used in Section 1.3.3.2.3.1, and holds the key to a symmetryadapted factorization of the DFT at hand.
The structure of depends on whether remains irreducible when considered as a polynomial over . Thus two cases arise:
These two cases require different developments.
References
Artin, E. (1944). Galois Theory. Notre Dame University Press.Auslander, L., Johnson, R. W. & Vulis, M. (1988). Evaluating finite Fourier transforms that respect group symmetries. Acta Cryst. A44, 467–478.
Auslander, L. & Shenefelt, M. (1987). Fourier transforms that respect crystallographic symmetries. IBM J. Res. Dev. 31, 213–223.
Bricogne, G. & Tolimieri, R. (1990). Twodimensional FFT algorithms on data admitting 90°rotational symmetry. In Signal Processing Theory, edited by L. Auslander, T. Kailath & S. Mitter, pp. 25–35. New York: SpringerVerlag.
Shenefelt, M. (1988). Group Invariant Finite Fourier Transforms. PhD thesis, Graduate Centre of the City University of New York.