zbMATH — the first resource for mathematics

Complete mappings and Carlitz rank. (English) Zbl 1408.11115
Summary: The well-known Chowla and Zassenhaus conjecture, proven by S. D. Cohen in [Can. Math. Bull. 33, No. 2, 230–243 (1990; Zbl 0722.11060)], states that for any \(d\geq 2\) and any prime \(p>(d^2-3d+4)^2\) there is no complete mapping polynomial in \(\mathbb {F}_p[x]\) of degree \(d\). For arbitrary finite fields \(\mathbb {F}_q\), we give a similar result in terms of the Carlitz rank of a permutation polynomial rather than its degree. We prove that if \(n<\lfloor q/2\rfloor \), then there is no complete mapping in \(\mathbb {F}_q[x]\) of Carlitz rank \(n^*\) of small linearity. We also determine how far permutation polynomials \(f\) of Carlitz rank \(n<\lfloor q/2\rfloor \) are from being complete, by studying value sets of \(f+x\). We provide examples of complete mappings if \(n=\lfloor q/2\rfloor \), which shows that the above bound cannot be improved in general.

11T06 Polynomials over finite fields
Full Text: DOI
[1] Aksoy, E; Çeşmelioğlu, A; Meidl, W; Topuzoğlu, A, On the Carlitz rank of a permutation polynomial, Finite Fields Appl., 15, 428-440, (2009) · Zbl 1232.11124
[2] Carlitz, L, Permutations in a finite field, Proc. Am. Math. Soc., 4, 538, (1953) · Zbl 0052.03704
[3] Chowla, S; Zassenhaus, H, Some conjectures concerning finite fields, Nor. Vidensk. Selsk. Forh. (Trondheim), 41, 34-35, (1968) · Zbl 0186.09203
[4] Çeşmelioğlu, A; Meidl, W; Topuzoğlu, A, On the cycle structure of permutation polynomials, Finite Fields Appl., 14, 593-614, (2008) · Zbl 1153.11057
[5] Çeşmelioğlu, A; Meidl, W; Topuzoğlu, A, Permutations with prescribed properties, J. Comput. Appl. Math., 259B, 536-545, (2014) · Zbl 1314.05003
[6] Cohen, SD, Proof of a conjecture of chowla and Zassenhaus on permutation polynomials, Can. Math. Bull., 33, 230-234, (1990) · Zbl 0722.11060
[7] Gomez-Perez D., Ostafe A., Topuzoğlu A.: On the Carlitz rank of permutations of \({\mathbb{F}}_q\) and pseudorandom sequences. J. Complex. 30, 279-289 (2014). · Zbl 1332.11103
[8] Guangkui, X; Cao, X, Complete permutation polynomials over finite fields of odd characteristic, Finite Fields Appl., 31, 228-240, (2015) · Zbl 1320.11121
[9] Işık L.: On complete mappings and value sets of polynomials over finite fields. PhD Thesis. Sabancı University (2015). · Zbl 0495.12018
[10] Laywine C.F., Mullen G.: Discrete Mathematics Using Latin Squares. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1998). · Zbl 0957.05002
[11] Lidl R., Niederreiter H.: Finite Fields, vol. 20, 2nd edn. Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (1997). · Zbl 0866.11069
[12] Mann, HB, The construction of orthogonal Latin squares, Ann. Math. Stat., 13, 418-423, (1942) · Zbl 0060.02706
[13] Muratovic-Ribic, A; Pasalic, E, A note on complete mapping polynomials over finite fields and their applications in cryptography, Finite Fields Appl., 25, 306-315, (2014) · Zbl 1302.11096
[14] Niederreiter, H; Robinson, KH, Complete mappings of finite fields, J. Aust. Math. Soc. A, 33, 197-212, (1982) · Zbl 0495.12018
[15] Niederreiter H., Winterhof A.: Cyclotomic \(\cal{R}\)-orthomorphisms of finite fields. Discret. Math. 295, 161-171 (2005). · Zbl 1078.11068
[16] Pausinger F., Topuzoğlu A.: Permutations of finite fields and uniform distribution modulo 1. In: Niederrreiter H., Ostafe A., Panario D., Winterhof A. (eds.) Algebraic Curves and Finite Fields, vol. 16, pp. 145-160. Radon Series on Applied and Computational Mathematics. De Gruyter, Berlin (2014). · Zbl 1368.11073
[17] Schulz R.-H.: On check digit systems using anti-symmetric mappings. In: Numbers Information and Complexity (Bielefeld, 1998), pp. 295-310. Kluwer Academic, Boston, MA (2000). · Zbl 0967.94030
[18] Shaheen, R; Winterhof, A, Permutations of finite fields for check digit systems, Des. Codes Cryptogr., 57, 361-371, (2010) · Zbl 1248.11100
[19] Stănică, P; Gangopadhyay, S; Chaturvedi, A; Gangopadhyay, AK; Maitra, S, Investigations on bent and negabent functions via the nega-Hadamard transform, IEEE Trans. Inf. Theory, 58, 4064-4072, (2012) · Zbl 1365.94684
[20] Topuzoğlu, A, Carlitz rank of permutations of finite fields: a survey, J. Symb. Comput., 64, 53-66, (2014) · Zbl 1332.11106
[21] Tu, Z; Zeng, X; Hu, L, Several classes of complete permutation polynomials, Finite Fields Appl., 25, 182-193, (2014) · Zbl 1284.05012
[22] Winterhof, A, Generalizations of complete mappings of finite fields and some applications, J. Symb. Comput., 64, 42-52, (2014) · Zbl 1332.11107
[23] Wu, G; Li, N; Helleseth, T; Zhang, Y, Some classes of monomial complete permutation polynomials over finite fields of characteristic two, Finite Fields Appl., 28, 148-165, (2014) · Zbl 1314.11073
[24] Zha, Z; Hu, L; Cao, X, Constructing permutations and complete permutations over finite fields via subfield-valued polynomials, Finite Fields Appl., 31, 162-177, (2015) · Zbl 1320.11123
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.