Application of Gauss sums to calculate the exact values of the number of appearances of elements on cycles of linear recurrences | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2017. № 36. DOI: 10.17223/20710410/36/3

Using Gauss sums, we solve the problem of obtaining the formulas for the exact values N(z,u) of appearances of z among the elements u(0), u(1), ..., u(T - 1) of a linear recurrence sequence (LRS) u generated by an irreducible polynomial of a degree m over a field P = GF(q) in the case, when the period of u is equal to T = (q^m - 1)/d, where d| (p^j + 1) for some natural number j and p = char P, that is, p is a semiprimitive number modulo d. Such a sequence u is obtained from a LRS of the maximal period q^m - 1 by regular sampling with step d. The results of the article generalize the formulas for N(z,u) which are well-known in the case of prime q or z = 0. In fact, we give some formulas for N(z, u) in the following cases: 1) d = 2; 2) d > 2 and z = 0; 3) d > 2, z = 0, and d = d₁ or d₁ = 1, where d1 = ((q^m - 1)/(q - 1), d); 4) d > 2, z = 0, d1 =2, and d/2 is odd or (p^h + 1)/(d/2) is even, where l₁ is the least positive integer such that (d/2) | (pp¹ + 1). Thus, as a corollary, we have a complete solution of the problem in the situation when d is a prime number.