(The published version is available online.)

Let G be a finite abelian group, let ψ be a permutation of G, and let u₀ be an element of G. Define the sequence u₁, u₂, ... recursively by u_n+1 = ψ(u_n).  This sequence is purely periodic, say with least period t. For any 1≤N≤t  and any nontrivial character χ of G, we consider the problem of finding nontrivial upper upper bounds on the absolute value of the incomplete character sum ∑_0≤n<N χ(u_n).  This problem arises in various applications involving pseudorandom number generation.

Recently Niederreiter and Shparlinski gave such bounds in case  G = F_p  and  ψ(g) = cg^p-2+d.  We generalize their method to arbitrary G and ψ,  obtaining an upper bound for the incomplete character sum in terms of the values of the complete character sums ∑_g∈G χ(ψ^k(g)-g)  for k = 1, 2, ...

This complete character sum vanishes if ψ^k-id  permutes G;  if this occurs for each "small" integer k, then our bound on the incomplete character sum can be sharpened significantly. We conclude by giving two constructions of permutations ψ of F_q such that ψ^k-id  permutes F_q for each of the first several positive integers k.

Michael Zieve:  home page   publication list