On the Carlitz rank of permutations of \(\mathbb F_q\) and pseudorandom sequences (Q2442861)

With \(f(x)\) a permutation polynomial acting on \(\mathbb{F}_q\), the main topic is the analysis of sequences \(\{ u_i \}_{i\geq 0}\) with \[ u_{i+1}=f(u_i).\tag{1} \] The main tool is a previously known result of the following type. Suppose \(f(x)\) is a permutation polynomial of \(\mathbb{F}_q\) with Carlitz rank \(k\). Then for at least \(q-k\) elements \(u\) in \(\mathbb{F}_q\), we have \[ f(u)=\frac{\alpha_{k+1}u+\beta_{k+1}}{\alpha_{k}u+\beta_{k}}, \] where the \(\alpha_i,\beta_i\) are constructed by linear recursions. Result 1: A lower bound for the Carlitz rank of a permutation polynomial \(f(x)\) of \(\mathbb{F}_q\) in terms of the number of nonzero coefficients of \(f(x)\). Result 2: Suppose \(f(x)\) is a permutation polynomial of a prime field \(\mathbb{F}_p\) with Carlitz rank at least 1 and degree at least 2. The authors analyse the pseudorandomness properties of a sequence \(\{u_i \}\) as in equation (1) by deriving an upper bound based on the Carlitz rank for the discrepancy of sequences of \(m-\)tuples with entries of the form \(u_i/p\). The tools employed are the Koksma-Szüsz inequality and the Bombieri-Weil bound for exponential sums involving rational functions. Result 3: A lower bound in terms of the Carlitz rank for the linear complexity profile of sequences of type \(\{u_n\}\) as in equation (1). All throughout the text, there are detailed discussions of particularly interesting cases of the new bounds derived and their relations to bounds already known.