Abstract
Fourier inversions of operations identify those with certain symmetries. A general method with invertible matrices over semirings sets up many different inversive schemes, such as disjunctive normal form, algebraic normal form and classical Fourier analysis. First, unary functions are inverted, and then, with tensor products, the same is done for operations of more than one argument. Classical Fourier analysis is applied to inverting operations on a set of k elements by replacing it by the set of \({k^{\rm th}}\) roots of unity. The Fourier transform of an operation preserving rotations of the roots has many coefficients that are zero, in fact, at most \({1/k}\) are non-zero. A related result holds for operations preserving reflections of the roots.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Burris S., Sankappanavar H.P.: A Course in Universal Algebra. Springer, New York (1981)
Dixon J.D., Mortimer B.: Permutation Groups. Springer, New York (1996)
Głazek, K.: A Guide to the Literature on Semirings and their Applications in Mathematics and Information Sciences. Kluwer Academic Publishers, Dordrecht (2002)
Halmos P.R.: Finite-dimensional Vector Spaces. Springer, New York (1974)
Kerkhoff, S., Pöschel, R., Schneider, F.M.: A short introduction to clones. In: Proceedings of the Workshop on Algebra, Coalgebra and Topology (WACT 2013). Electron. Notes Theor. Comput. Sci., vol. 303, pp. 107–120. Elsevier, Amsterdam (2014)
Knoebel, A.: Inversion formulas. Notices Amer. Math. Soc. 19, A-754 (1972)
Knoebel, A.: The Equational Classes Generated by Single Functionally Precomplete Algebras. Mem. Amer. Math. Soc., vol. 57 (1985)
Ledermann, W.: Introduction to the Theory of Finite Groups, 4th ed. Oliver and Boyd, Edinburgh (1961)
O’Donnell R.: Analysis of Boolean Functions. Cambridge University Press, New York (2014)
Pöschel, R., Rosenberg, I.: Compositions and clones of Boolean functions. In: Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp. 3–38. Cambridge University Press, New York (2010)
Strang G.: Introduction to Applied Mathematics. Wellesley-Cambridge Press, Wellesley (1986)
Zhegalkin I.I.: On the technique of calculating propositions in symbolic logic. Matematicheskii Sbornik 43, 9–28 (1927)
Zhuk D.: The lattice of all clones of self-dual functions in three-valued logic. J. Mult.-Valued Logic Soft Comput. 24, 251–316 (2015)
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by R. Poeschel.
Rights and permissions
About this article
Cite this article
Knoebel, A. Fourier analysis of operations that preserve permutations. Algebra Univers. 78, 533–544 (2017). https://doi.org/10.1007/s00012-017-0470-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00012-017-0470-z