Equivalence classes of functions between finite groups
K. J. Horadam
RMIT University, Melbourne, VIC 3001, Australia
DOI: 10.1007/s10801-011-0310-8
Abstract
Two types of equivalence relation are used to classify functions between finite groups into classes which preserve combinatorial and algebraic properties important for a wide range of applications. However, it is very difficult to tell when functions equivalent under the coarser (“graph”) equivalence are inequivalent under the finer (“bundle”) equivalence. Here we relate graphs to transversals and splitting relative difference sets (RDSs) and introduce an intermediate relation, canonical equivalence, to aid in distinguishing the classes. We identify very precisely the conditions under which a graph equivalence determines a bundle equivalence, using transversals and extensions. We derive a new and easily computed algebraic measure of nonlinearity for a function f, calculated from the image of its coboundary
tial f. This measure is preserved by bundle equivalence but not by the coarser equivalences. It takes its minimum value if f is a homomorphism, and takes its maximum value if the graph of f contains a splitting RDS.
tial f. This measure is preserved by bundle equivalence but not by the coarser equivalences. It takes its minimum value if f is a homomorphism, and takes its maximum value if the graph of f contains a splitting RDS.
Pages: 477–496
Keywords: equivalent functions; graph of function; finite field polynomial; linear equivalence; relative difference set; nonlinear function; APN function
Full Text: PDF
References
1. Breveglieri, L., Cherubini, A., Macchetti, M.: On the generalized linear equivalence of functions over finite fields. In: Lee, P.J. (ed.) ASIACRYPT
2004. LNCS, vol. 3329, pp. 79-91. Springer, Berlin (2004)
2. Browning, K.A., Dillon, J.F., Kibler, R.E., McQuistan, M.T.: APN polynomials and related codes. J. Comb. Inf. Syst. Sci. 34, 135-159 (2009). Special Issue honoring the 75th birthday of Prof. D.K. Ray-Chaudhuri
3. Budaghyan, L., Carlet, C., Pott, A.: New classes of almost bent and almost perfect nonlinear polynomials. IEEE Trans. Inf. Theory 52, 1141-1152 (2006)
4. Carlet, C., Ding, C.: Highly nonlinear mappings. J. Complex. 20, 205-244 (2004)
5. Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Des. Codes Cryptogr. 15, 125-156 (1998)
6. Cavior, S.R.: Equivalence classes of functions over a finite field. Acta Arith. 10, 119-136 (1964)
7. Coulter, R.S., Matthews, R.W.: Planar functions and planes of Lenz-Barlotti Class II. Des. Codes Cryptogr. 10, 167-184 (1997)
8. Elliott, J.E.H., Butson, A.T.: Relative difference sets. Ill. J. Math. 10, 517-531 (1966)
9. Galati, J.C.: A group extensions approach to relative difference sets. J. Comb. Des. 12, 279-298 (2004)
10. Horadam, K.J.: Hadamard Matrices and Their Applications. Princeton University Press, Princeton (2007)
11. Horadam, K.J.: Relative difference sets, graphs and inequivalence of functions between groups. J.
2004. LNCS, vol. 3329, pp. 79-91. Springer, Berlin (2004)
2. Browning, K.A., Dillon, J.F., Kibler, R.E., McQuistan, M.T.: APN polynomials and related codes. J. Comb. Inf. Syst. Sci. 34, 135-159 (2009). Special Issue honoring the 75th birthday of Prof. D.K. Ray-Chaudhuri
3. Budaghyan, L., Carlet, C., Pott, A.: New classes of almost bent and almost perfect nonlinear polynomials. IEEE Trans. Inf. Theory 52, 1141-1152 (2006)
4. Carlet, C., Ding, C.: Highly nonlinear mappings. J. Complex. 20, 205-244 (2004)
5. Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Des. Codes Cryptogr. 15, 125-156 (1998)
6. Cavior, S.R.: Equivalence classes of functions over a finite field. Acta Arith. 10, 119-136 (1964)
7. Coulter, R.S., Matthews, R.W.: Planar functions and planes of Lenz-Barlotti Class II. Des. Codes Cryptogr. 10, 167-184 (1997)
8. Elliott, J.E.H., Butson, A.T.: Relative difference sets. Ill. J. Math. 10, 517-531 (1966)
9. Galati, J.C.: A group extensions approach to relative difference sets. J. Comb. Des. 12, 279-298 (2004)
10. Horadam, K.J.: Hadamard Matrices and Their Applications. Princeton University Press, Princeton (2007)
11. Horadam, K.J.: Relative difference sets, graphs and inequivalence of functions between groups. J.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition