Recursions associated to trapezoid, symmetric and rotation symmetric functions over Galois fields
Francis N. Castro Robin Chapman Luis A. Medina L. Brehsner Sepúlveda

Recursions and trapezoid, symmetric and rotation symmetric functions]Recursions associated to trapezoid, symmetric and rotation symmetric functions over Galois fields


Department of Mathematics, University of Puerto Rico, San Juan, PR 00931
franciscastr@gmail.com


Department of Mathematics, University of Exeter, Exeter, EX4 4QF, UK
r.j.chapman@exeter.ac.uk


Department of Mathematics, University of Puerto Rico, San Juan, PR 00931
luis.medina17@upr.edu



Department of Mathematics, University of Puerto Rico, San Juan, PR 00931
leonid.sepulveda1@upr.edu



Rotation symmetric Boolean functions are invariant under circular translation of indices.  These functions have very rich cryptographic properties and have been used in different cryptosystems.
Recently, Thomas Cusick proved that exponential sums of rotation symmetric Boolean functions satisfy homogeneous linear recurrences with integer coefficients.  In this work, a generalization of this 
result is proved over any Galois field.  That is, exponential sums over Galois fields of rotation symmetric polynomials satisfy linear recurrences with integer coefficients.
 In the particular case of 𝔽_2, an elementary method is used to obtain explicit recurrences for exponential sums of some of these functions.  The concept of trapezoid Boolean function is also introduced and it is showed that the linear recurrences that exponential sums of trapezoid Boolean functions satisfy are the same as the ones satisfied by exponential sums of 
the corresponding rotations symmetric Boolean functions.  Finally, it is proved that exponential sums of trapezoid and symmetric polynomials also satisfy linear recurrences with integer coefficients over any 
Galois field 𝔽_q.  Moreover, the Discrete Fourier Transform matrix and some Complex Hadamard matrices appear as examples in some of our explicit formulas of these recurrences.



[2010]05E05, 11T23, 11B50





[
    L. Brehsner Sepúlveda
    December 30, 2023
=========================



§ INTRODUCTION

A Boolean function is a function from the vector space 𝔽_2^n to  𝔽_2.  Boolean functions are part of a beautiful branch of combinatorics with applications to many scientific areas.  
Some particular examples are the areas of theory of error-correcting codes and cryptography.   Efficient cryptographic implementations of Boolean functions with many variables is a challenging problem due to memory 
restrictions of current technology. Because of this, symmetric Boolean functions are good candidates for efficient implementations. However, symmetry is a too special property and may imply that these 
implementations are vulnerable to attacks.

In <cit.>, Pieprzyk and Qu introduced rotation symmetric Boolean functions. A rotation symmetric Boolean function in n variables is a function which is invariant under the action of the cyclic group C_n on the set 𝔽_2^n.   For example, let X_i∈𝔽_2 for 1≤ i≤ n.  Define, for 1≤ k ≤ n, the shift function

    E_n^k(X_i) = 
     X_i+k    if i+k≤ n, 
    
     X_i+k-n    if i+k>n.

Extend this definition to 𝔽_2^n by defining

    E_n^k(X_1,X_2,⋯, X_n) = (E_n^k(X_1),E_n^k(X_2),⋯, E_n^k(X_n)).

The shift function E_n^k can also be extended to monomials via

    E_n^k(X_i_1X_i_2⋯ X_i_t) = E_n^k(X_i_1)E_n^k(X_i_2),⋯ E_n^k(X_i_t).

A Boolean function F( X) in n variables is a rotation symmetric Boolean function if and only if for any (X_1⋯, X_n)∈𝔽_2^n, 

    F(E_n^k(X_1⋯, X_n))=F(X_1⋯, X_n)

for every 1≤ k≤ n.
Pieprzyk and Qu showed that these functions are useful in the design of fast hashing algorithms with strong cryptographic properties.  This work sparked interest in these functions and today their study is an active area of research <cit.>.

Every Boolean function in n variables can be identified with a multi-variable Boolean polynomial.  This polynomial is known as the algebraic normal form (ANF for short) of the Boolean function.  The 
degree of a Boolean function F( X) is the degree of its ANF.  The ANF of a rotation symmetric Boolean function is very well-structured.  For example, suppose we have a rotation symmetric Boolean function in 5 variables.  Suppose that X_1X_2X_3 is part of the ANF of the function.  Then, the terms

    E_5^1(X_1X_2X_3)   =   X_2X_3X_4
    
    E_5^2(X_1X_2X_3)   =   X_3X_4X_5
     
    E_5^3(X_1X_2X_3)   =   X_4X_5X_1
    
    E_5^4(X_1X_2X_3)   =   X_5X_1X_2

are also part of its ANF.  Similarly, suppose that X_1X_3 is also a term of the ANF.  Then, 

    X_2X_4, X_3X_5, X_4X_1, X_5X_2

are also part of the ANF.  An example of a rotation symmetric Boolean function with this property is given by

    R( X)    =   X_1X_2X_3+X_2X_3X_4+X_3X_4X_5+X_4X_5X_1+ X_5X_1X_2+
          X_1X_3+X_2X_4+ X_3X_5+ X_4X_1+ X_5X_2.

Therefore, once a monomial X_i_1⋯ X_i_t is part of the ANF of a rotation symmetric Boolean function, so is E_n^k(X_i_1⋯ X_i_t) for all 1≤ k ≤ n.  This implies that the 
information encoded in the ANF of a rotation symmetric Boolean function can be obtained with minimal information.  Define the set

    RSet_n(X_i_1⋯ X_i_t)={E_n^k(X_i_1⋯ X_i_t) |  1≤ k ≤ n}.

For example,

    RSet_5(X_1X_2X_3)={X_2X_3X_4, X_3X_4X_5, X_4X_5X_1, X_5X_1X_2, X_1X_2X_3}.

Select as a representative for the set RSet_n(X_i_1⋯ X_i_t) the first element in the lexicographic order.  For example, the representative for 

    {X_2X_3X_4, X_3X_4X_5, X_4X_5X_1, X_5X_1X_2, X_1X_2X_3}

is X_1X_2X_3.  Observe that if the rotation symmetric Boolean function is not constant, then X_1 always appears in the lexicographically first element of RSet_n(X_i_1⋯ X_i_t).
The short algebraic normal form (or SANF) of a rotation symmetric Boolean function is a function of the form

    a_0 +a_1 X_1+∑ a_1,jX_1X_j+⋯+a_1,2,⋯,n X_1X_2⋯ X_n,

where a_0,a_1, a_1,j,⋯, a_1,2,⋯,n∈𝔽_2 and the existence of the term X_1X_i_2⋯ X_i_t implies the existence of every term in 
    RSet_n(X_1X_i_2⋯ X_i_t)

in the ANF.  For example, the SANF of the rotation symmetric Boolean function (<ref>) is given by

    X_1X_3+X_1X_2X_3.



Let 1<j_1<⋯< j_s be integers.  A rotation symmetric Boolean function of the form 

    R_j_1,⋯, j_s(n)=X_1X_j_1⋯ X_j_s+X_2X_j_1+1⋯ X_j_s+1+⋯+X_nX_j_1-1⋯ X_j_s-1,

where the indices are taken modulo n and the complete system of residues is {1,2,⋯, n}, is called a monomial rotation symmetric Boolean function.  For example, the rotation symmetric 
Boolean function (<ref>) is given by

    R( X) = R_2,3(5) + R_3(5).

Sometimes the notation (1,j_1,⋯, j_s)_n is used to represent the monomial rotation Boolean function (<ref>), see <cit.>.

In some applications related to cryptography it is important for Boolean functions to be balanced.  A balanced Boolean function is one for which the number of zeros and the number 
of ones are equal in its truth table.  Balancedness of Boolean functions can be studied from the point of view of exponential sums.  The exponential sum of an n-variable Boolean function F( X) is defined as

    S(F)=∑_ x∈𝔽_2^n (-1)^F( x).

Observe that a Boolean function F( X) is balanced if and only if S(F)=0.  This gives importance to the study of exponential sums.  This point of view is also a very active area of research. For 
some examples, please refer to <cit.>.

Let F( X) be a Boolean function.  List the elements of 𝔽_2^ n in lexicographic order and label them as x_0=(0,0,⋯, 0), x_1=(0,0,⋯, 1) and so on.  The vector (F( x_0),F( x_1),⋯, F( x_2^n-1)) is called the truth table or F.  The Hamming weight of F, denoted by wt(F), is the number of 1's in the truth table of F.  Observe that a Boolean function in n variables is balanced if and only if its Hamming weight is 2^n-1.  The Hamming weight of a Boolean function F and its exponential sums are related by the equation

    wt(F)=2^n-S(F)/2.


The study of weights of rotations symmetric Boolean functions has received some attention lately <cit.>.  In particular, it has been observed that weights of cubic  rotation symmetric Boolean functions are linear recursive with constant coefficients <cit.>.  Recently, Cusick <cit.> showed that weights of any rotation symmetric 
Boolean function satisfy linear recurrences with integer coefficients.  Since the exponential sum and the weight function of a Boolean function are related by (<ref>), then it is also true 
that exponential sums of rotation symmetric Boolean functions satisfy linear recurrences with integer coefficients.

One of the most important results in this work is a generalization of Cusick's Theorem over any Galois field.  To be specific, let q=p^r with p prime and r≥1. Exponential sums over 𝔽_q 
of monomial rotation symmetric polynomials (and linear combinations of them) satisfy homogeneous linear recurrences with integer coefficients.  Remarkably, this can be proved by elementary means.  
Another important result included in this work is that exponential sums over 𝔽_q of elementary symmetric polynomials and linear combinations of them also satisfy linear recurrences with integer 
coefficients.  Surprisingly, the Discrete Fourier Transform matrix, some Complex Hadamard matrices and the quadratic Gauss sum mod p appear in the study of the recurrences considered in this work.

This article is divided as follows. The next section is an introduction of the elementary method used to obtain the recurrences.  This introduction is done over 𝔽_2 in order to solidify the 
intuition.  The reader interested in the generalization is invited to skip this section, however, the reader is encouraged to read the definition of trapezoid functions, as they are used through 
out the article. In section <ref> linear recurrences with integer coefficients are obtained for exponential sums trapezoid functions over Galois fields.  Moreover, it is in this section where 
it is proved that exponential sums over 𝔽_q of monomial rotation symmetric polynomials and linear combinations of them satisfy linear recurrences with integer coefficients.  The same technique 
is used in the section <ref> to prove that exponential sums over 𝔽_q of elementary symmetric polynomials and linear combinations of them also satisfy linear recurrences with 
integer coefficients.  Finally, in the last section, some conjectures about the initial conditions of some of the sequences considered in this work are presented.









§ LINEAR RECURRENCES OVER 𝔽_2


As mentioned in the introduction, Cusick <cit.> recently showed that exponential sums of rotation symmetric Boolean functions satisfy homogeneous linear recurrences with integer coefficients.  
This fact was suggested by some previous works on the subject. For example, in <cit.>, Cusick and Stnic provided a linear recursion for the sequence of
weights for the monomial rotation function (1,2,3)_n.  This recursion, however, was not homogeneous, but it could be transformed into a homogeneous one, see <cit.>.
Later, Cusick and Johns <cit.> provided recursions for  weights of cubic rotation symmetric Boolean functions.

In this section we use elementary machinery to provide explicit homogeneous linear recurrences with integer coefficients for exponential sums of some rotation symmetric Boolean functions.  The idea is to
show that exponential sums of rotation symmetric Boolean functions satisfy the same linear recurrences of exponential sums of trapezoid Boolean functions (see definition below).  We prove this fact
using elementary machinery and, at this early stage, without the use linear algebra.  In the next section we show that exponential sums of rotation symmetric functions over any Galois field satisfy 
linear recurrences.  The reader interested in this generalization may skip this section, but not before reading the definition of trapezoid functions.

Define the trapezoid Boolean function in n variables of degree k as

    τ_n,k = ∑ _j=1^n-k+1 X_jX_j+1⋯ X_j+k-1.

For example,

    τ_7,3   =    X_1 X_2 X_3+X_2 X_3 X_4+X_3 X_4 X_5+X_4 X_5 X_6+X_5 X_6 X_7
    τ_6,4   =    X_1 X_2 X_3 X_4+X_2 X_3 X_4 X_5+X_3 X_4 X_5 X_6.

The name trapezoid comes from counting the number of times each variable appears in the function τ_n,k.  For example, consider τ_7,3.  Observe that X_1 appears 1 time in τ_7,3, X_2 
appears 2 times, X_3, X_4 and X_5 appears 3 times each, X_6 appears twice, and X_7 appears once.  Plotting the these values and connecting the dots produces the shape of an isosceles trapezoid. 
Figure <ref> is a graphical representation of this.  The Boolean variable X_i is represented by i in the x-axis. The y-axis corresponds to the number of times the variable appears in τ_7,3.



The opposite is also true, that is, for every isosceles trapezoid that can be constructed by steps of length at most 1, one can construct a trapezoid Boolean function.

It turns out that sequences of exponential sums of trapezoid Boolean functions of fixed degree satisfy homogeneous linear recurrences with integer coefficients.  These linear recurrences are the same 
satisfied by sequences of exponential sums of (1,2,⋯,k)-rotation symmetric Boolean functions.  Remarkably, this fact can be proved by elementary means by “playing" a simple game of turning 
ON and OFF some of the variables.   Given a Boolean variable X_i, we say that it is turned OFF if X_i assumes the value 0 and turned ON if the variable assumes the value 1.
In other words, each Boolean variable represents a “switch" with two options: 0 (OFF) and 1 (ON).

We start the discussion with the recurrence for exponential sums of trapezoid Boolean functions.



 The sequence {S(τ_n,k)}_n=k^∞ satisfies a homogeneous linear recurrence with integer coefficients whose characteristic polynomial is given by 
 
    p_k(X)=X^k -2 (X^k-2+X^k-3+⋯+X+1).



For the sake of simplicity, we present, in detail, the proof for the cases k=3 and k=4.  The general case becomes clear after that.  Moreover, the complete proof of a generalization of this theorem over any Galois field is presented in section <ref>.
 
Start with the case k=3.  Observe that by turning X_n OFF and ON we get the identity
 
    S(τ_n,3) = S(τ_n-1,3)+S(τ_n-1,3+X_n-2X_n-1).

Consider now S(τ_n-1,3+X_n-2X_n-1).  Turn X_n-1 OFF and ON to get

    S(τ_n-1,3+X_n-2X_n-1)=S(τ_n-2,3)+S(τ_n-2,3+X_n-2+X_n-3X_n-2).

Finally, turn X_n-2 OFF and ON to get

    S(τ_n-2,3+X_n-2+X_n-3X_n-2)=S(τ_n-3,3)-S(τ_n-3,3+X_n-3+X_n-4X_n-3).

The last equation is equivalent (after relabeling) to 

    S(τ_n,3)=S(τ_n+1,3+X_n+1+X_nX_n+1)+S(τ_n,3+X_n+X_n-1X_n).


Observe that equations (<ref>) and (<ref>) can be combined to obtain

    S(τ_n,3)=S(τ_n-1,3)+S(τ_n-2,3)+ S(τ_n-2,3+X_n-2+X_n-3X_n-2).

Let a_n,3 =S(τ_n,3+X_n+X_n-1X_n).  Note that (<ref>) implies that S(τ_n,3)=a_n+1,3+a_n,3.  Therefore, (<ref>) can be re-written as

    (a_n+1,3+a_n,3) = (a_n,3+a_n-1,3)+(a_n-1,3+a_n-2,3)+a_n-2,3,

which is equivalent to 

    a_n+1,3 = 2a_n-1,3+2a_n-2,3.

This implies that {a_n,3} satisfies the linear recurrence whose characteristic polynomial is given by p_3(X).  Since S(τ_n,3)=a_n+1,3+a_n,3, then {S(τ_n,3)} also satisfies such recurrence and the result holds for k=3.

Consider now the case when k=4.  As it was done in the case when k=3,  turning OFF and ON several variables leads to 

    S(τ_n,4)   =   S(τ_n-1,4)+S(τ_n-2,4)+S(τ_n-3,4)
          +S(τ_n-3,4+X_n-3+X_n-4X_n-3+X_n-5X_n-4X_n-3)

and

    S(τ_n,4)   =    S(τ_n+1,4+X_n+1+X_nX_n+1+X_n-1X_nX_n+1)
          +S(τ_n,4+X_n+X_n-1X_n+X_n-2X_n-1X_n).

Now let a_n,4=S(τ_n,4+X_n+X_n-1X_n+X_n-2X_n-1X_n) and observe that (<ref>) can be re-written as

    (a_n+1,4+a_n,4)=(a_n,4+a_n-1,4)+(a_n-1,4+a_n-2,4)+(a_n-2,4+a_n-3,4)+a_n-3,4,

which is equivalent to

    a_n+1,4 = 2a_n-1,4+2a_n-2,4+2a_n-3,4.

Therefore, {a_n,4} satisfies the linear recurrence whose characteristic polynomial is given by p_4(X).  Since S(τ_n,4)=a_n+1,4+a_n,4, then {S(τ_n,4)} also satisfies such 
recurrence and the result also holds for k=4.  

In general, S(τ_n,k) can be expressed as

    S(τ_n,k)   =∑_i=1^k-1 S(τ_n-i,k)+S(τ_n-k+1,k+∑_j=0^k-2∏_i=0^j X_n-k+1-i)

and as

    S(τ_n,k)   =S(τ_n+1,k+∑_j=0^k-2∏_i=0^j X_n+1-i)+S(τ_n,k+∑_j=0^k-2∏_i=0^j X_n-i).

Combine these equations and proceed as before to obtain the result.  This concludes the proof.


It turns out that the sequence of exponential sums of (1,2,⋯,k)-rotation symmetric Boolean functions, that is, of R_2,3,⋯, k(n), also satisfies the linear recurrence whose characteristic 
polynomial is given p_k(X). This is a well-known result for the case when k=3 (<cit.>), but, to the knowledge of the authors, the closed formula for the general case is new. 




Before proving that {S(R_2,3,⋯, k(n))} satisfies the linear recurrence with characteristic polynomial p_k(X), we show an auxiliary result which can be proved using the same arguments as in the 
proof of Theorem <ref>.



 Let τ_n,k be the trapezoid Boolean function of degree k in n variables.  Suppose that F( X) is a Boolean polynomial in the first j variables with j<k.  Then, the sequences
 
    {S(τ_n,k+F( X))}
 and 
    {S(τ_n,k+F( X)+X_n+X_nX_n-1+X_nX_n-1X_n-2+⋯+X_nX_n-1⋯ X_n-k+2)}
 satisfies the linear recurrence whose characteristic polynomial 
 is given by p_k(X).



 The proof of this result follows the same argument of the proof of Theorem <ref>.   


Theorem <ref> and Lemma <ref> is all that is needed to show that the sequence of exponential sums of (1,2,⋯,k)-rotation symmetric Boolean functions satisfies the linear
recurrence with characteristic polynomial p_k(X).


 The sequence {S(R_2,3,⋯, k(n))} satisfies the homogeneous linear recurrence whose characteristic polynomial is given by p_k(X). 



 This result can also be proved by turning OFF and ON several variables.  As before, we provide the proof for the case when k=4.  The general case follows the same argument.
 
 To start the argument, turn OFF and ON the variable X_n to get
 
    S(R_2,3,4(n)) = S(τ_n-1,4)+S(τ_n-1,4+X_1X_2X_3+X_1X_2X_n-1+X_1X_n-2X_n-1).

Consider the second term of the right hand side of this equation.  Turn X_n-1 OFF and ON to get

    S(τ_n-1,4   +X_1X_2X_3+X_1X_2X_n-1+X_1X_n-2X_n-1)
       =S(τ_n-2,4+X_1X_2X_3)
          +S(τ_n-2,4+X_1X_2+X_1X_2X_3+X_1X_n-2+X_n-3X_n-2+X_n-4X_n-3X_n-2).

Again, consider the second term of the right hand side of equation (<ref>). Turn X_n-2 OFF and ON to get

    S(τ_n-2,4   +X_1X_2+X_1X_2X_3+X_1X_n-2+X_n-3X_n-2+X_n-4X_n-3X_n-2)
       =S(τ_n-3,4+X_1X_2+X_1X_2X_3)
          +S(τ_n-3,4+X_1+X_1X_2+X_1X_2X_3+X_n-3+X_n-4X_n-3+X_n-5X_n-4X_n-3).

Equations (<ref>), (<ref>) and (<ref>) lead to the equation
 
    S(R_2,3,4(n))    = S(τ_n-1,4)+S(τ_n-2,4+X_1X_2X_3)+S(τ_n-3,4+X_1X_2+X_1X_2X_3)
          +S(τ_n-3,4+X_1+X_1X_2+X_1X_2X_3+X_n-3+X_n-4X_n-3+X_n-5X_n-4X_n-3).

Theorem <ref> and Lemma <ref> imply that {S(τ_n-1,4)},  {S(τ_n-2,4+X_1X_2X_3)}, {S(τ_n-3,4+X_1X_2+X_1X_2X_3)} and

    {S(τ_n-3,4+X_1+X_1X_2+X_1X_2X_3+X_n-3+X_n-4X_n-3+X_n-5X_n-4X_n-3)}

satisfy the linear recurrence whose characteristic polynomial p_4(X).  Since {S(R_2,3,4(n))} is a linear combination of them, then the result holds when k=4.

In general, S(R_2,3,⋯, k(n)) can be expressed as

    S(R_2,3,⋯, k(n))   =S(τ_n-1,k)+∑_m=0^k-3 S(τ_n-2-m,k+∑_j=0^m ∏_i=1^k-1-j X_i)
          +S(τ_n-k+1,k+∑_j=1^k-1(∏_i=1^j X_i+ ∏_i=0^j-1 X_n-k+1-i))

Invoke Theorem <ref> and Lemma <ref> to get the result.  This concludes the proof.


The same technique can be applied to find linear recurrences of exponential sums other rotations.  Recall that 

    R_j_1,⋯, j_s(n)=X_1X_j_1⋯ X_j_s+X_2X_j_1+1⋯ X_j_s+1+⋯+X_nX_j_1-1⋯ X_j_s-1,

where the indices are taken modulo n and the complete system of residues is {1,2,⋯, n}. 




We define the equivalent of the trapezoid Boolean function for R_j_1,⋯, j_s(n) as

    T_j_1,⋯,j_s(n)=X_1X_j_1⋯ X_j_s+X_2X_j_1+1⋯ X_j_s+1+⋯+X_n+1-j_sX_j_1+n-j_s⋯ X_j_s-1+n-j_sX_n.

For instance, under this notation one has

    τ_n,k=T_2,3,⋯, k(n).

It turns out that for k≥ 4, the sequences {S(R_2,3,⋯,k-2,k(n))} and {S(R_2,3,⋯,k-2,k+1(n))} both satisfy the linear recurrence whose characteristic polynomial is

    q_k(X)=X^k+1-2X^k-1-2X^k-2-⋯-2X^3-4.

As just mentioned, this can be proved by playing a game of turning ON and OFF some variables.  However, the process becomes somewhat tedious at a very early stage.

For example, recall that Theorem <ref> is an auxiliary result that was used to show that {S(R_2,3,⋯, k(n))} satisfies the linear recurrence with characteristic polynomial  p_k(X).  Let us show the equivalent of Theorem <ref> for {S(R_2,4(n))}.  The idea is to show the reader how tedious the process can get.  Recall that the equivalent of the trapezoid Boolean function for this problem is 

    T_2,4(n)=X_1X_2X_4+X_2X_3X_5+⋯+X_n-3X_n-2X_n.

Start with the equation

    S(T_2,4(n)+X_n-1X_n)   =   S(T_2,4(n+1)+X_n-1X_n+X_n+1+X_nX_n+1)+
           S(T_2,4(n)+X_n-2X_n-1+X_n+X_n-1X_n),

which is a consequence of turning OFF and ON the variable X_n+1. On the other hand, by turning X_n OFF and ON one gets

    S(T_2,4(n)+X_n-1X_n)   =   S(T_2,4(n-1)+ S(T_2,4(n-1)+X_n-1+X_n-2X_n-3).

This gave us two equations for S(T_2,4(n)+X_n-1X_n).

Consider now the right hand side of (<ref>).  Turn X_n-1 OFF and ON to get 

    S(T_2,4(n-1)+X_n-1+X_n-2X_n-3)   =    S(T_2,4(n-2)+X_n-2X_n-3)-
          S(T_2,4(n-2)+X_n-4X_n-3+X_n-3X_n-2)

Now turn X_n-2 OFF and ON to get the equation

    S(T_2,4(n-2)+X_n-4X_n-3+X_n-3X_n-2)   =   S(T_2,4(n-3)+X_n-4X_n-3)+
          S(T_2,4(n-3)+X_n-5X_n-4+X_n-3+X_n-4X_n-3).

Combine equations (<ref>), (<ref>), (<ref>), and (<ref>) to get

    S(T_2,4(n)   =   S(T_2,4(n+1)+X_nX_n+1)-S(T_2,4(n-1)+X_n-2X_n-1)+S(T_2,4(n-2)+X_n-3X_n-2)
          +S(T_2,4(n-2)+X_n-4X_n-3+X_n-2+X_n-3X_n-2).


Now let a_n=S(T_2,4(n)+X_n-2X_n-1+X_n+X_n-1X_n).  Observe that equation (<ref>) can be re-written as

    S(T_2,4(n)+X_n-1X_n)=a_n+1+a_n.

This and equation (<ref>)  imply

    S(T_2,4(n))   =   (a_n+2+a_n+1)-(a_n+a_n-1)+(a_n-1+a_n-2)+a_n-2
       =   a_n+2+a_n+1-a_n+2a_n-2.

On the other hand, by switching OFF and ON several variables one obtains

    S(T_2,4(n))   =    S(T_2,4(n-1))+S(T_2,4(n-2)+X_n-3X_n-2)+S(T_2,4(n-3)+X_n-4X_n-3)
          + S(T_2,4(n-3)+X_n-5X_n-4+X_n-3+X_n-4X_n-3).

Writing this last equation in terms of a_n one gets

    (a_n+2+a_n+1-a_n+2a_n-2)   =   (a_n+1+a_n-a_n-1+2a_n-3)
          +(a_n-1+a_n-2)+(a_n-2+a_n-3)+a_n-3,

which simplifies to

    a_n+2=2a_n+4a_n-3.

The characteristic polynomial for this recurrence is q_3(X).

Other examples on which this elementary method can be used to find explicit formulas for linear recurrences include the sequence

    {S(R_2,3,⋯,k(n)+R_2,3,⋯,k-1(n))},

which satisfies the linear recurrence with characteristic polynomial 

    x^k-2x^k-1+2,

the sequence

    {S(R_2,3,⋯, k-1,k(n)+R_2,3,⋯,k-2,k(n))},

which satisfies the linear recurrence with characteristic polynomial 

    x^k-2x^k-1+2x-2,

and the sequence 

    {S(R_2, 3,⋯, k-2,k(n)+ R_2, 3, ⋯, k-1(n)+R_2, 3, ⋯,k(n))},

which satisfies the linear recurrence with characteristic polynomial 

    x^k-2(x^k-2+x^k-3+⋯+x^2+1).

However, the process is somewhat tedious to be done by hand.  Automatization seems to be the way to go.  The reader is invited to read Cusick's work <cit.>, which
includes a Mathematica code that calculates a linear recurrences for the weights of a given rotation.







§ LINEAR RECURRENCES OVER 𝔽_Q



In this section we show that exponential sums of rotation functions over Galois fields satisfy linear recurrence.  This is a generalization of Cusick's result.

Consider the Galois field 𝔽_q = {0,α_1,⋯,α_q-1} where q=p^r with p prime and r≥ 1.  Recall that the exponential sum 
of a function F:𝔽_q^n →𝔽_q is given by

    S_𝔽_q(F)=∑_ x∈𝔽^n_q e^2π i/pTr_𝔽_q/𝔽_p(F( x)),

where Tr_𝔽_q/𝔽_p represents the field trace function from 𝔽_q to 𝔽_p.
The same technique used for exponential sums of Boolean functions can be used in general.  However, instead of having two options for the “switch", we now have q of them.  Let X be a variable which takes values on 𝔽_q.  As before, we say that the variable X can be turned OFF or ON, however, this time the term “turn OFF" means that X assumes the value 0, while the term “turn ON" means that X assumes all values in 𝔽_q that are different from zero.  Think of this situation as a light switch on which you have the option to turn  OFF the light and the option to turn it ON to one of q-1 colors.


We consider first sequences exponential sums of trapezoid functions.  As in the case over 𝔽_2, they satisfy linear recurrences with integer coefficients over any Galois field 
𝔽_q.   We start with the following lemma, which is interesting in its own right.



Let k, n and j be integers with k>2, 1≤ j<k and n≥ k.   Then,

    S_𝔽_q(T_2,3,⋯,k(n)+∑_s=1^jβ_s∏_l=0^k-s-1X_n-l)=S_𝔽_q(T_2,3,⋯,k(n)+∑_s=1^j∏_l=0^k-s-1X_n-l)

for any choice of β_s∈𝔽_q^×.



The proof is by induction on n.  Suppose first that n=k.  Observe that

    T_2,3,⋯,k(k)+∑_s=1^jβ_s∏_l=0^k-s-1X_k-l   =    X_1X_2⋯ X_k+β_j X_j+1X_j+2⋯ X_k+β_j-1 X_jX_j+1⋯ X_k
          +⋯+ β_2 X_3 X_4⋯ X_k+  β_1 X_2 X_3⋯ X_k.

Consider the right hand side of (<ref>).  If 1≤ j≤ k-2, then make the changes of variables

    X_t    =    Y_t,     for j+2≤ t ≤ k 
    
     X_j+1   =   β_j^-1Y_j+1
    
     X_t   =   β_t-1^-1β_t Y_t,     for 2≤ t ≤ j
     
     X_1   =   β_1 Y_1.

On the other hand, if j=k-1, then make the change of variables

    X_k   =   β_k-1^-1Y_k
    
     X_t   =   β_t-1^-1β_t Y_t,     for 2≤ t ≤ k-1
     
     X_1   =   β_1 Y_1.

This transforms (<ref>) into 

    Y_1Y_2⋯ Y_k +∑_s=1^j∏_l=0^k-s-1Y_k-l.

Therefore, 

    S_𝔽_q(T_2,3,⋯,k(k)+∑_s=1^jβ_s∏_l=0^k-s-1X_k-l)=S_𝔽_q(T_2,3,⋯,k(k)+∑_s=1^j∏_l=0^k-s-1X_k-l).

This concludes the base case.  

Suppose now that for some n≥ k we have 

    S_𝔽_q(T_2,3,⋯,k(n)+∑_s=1^jβ_s∏_l=0^k-s-1X_n-l)=S_𝔽_q(T_2,3,⋯,k(n)+∑_s=1^j∏_l=0^k-s-1X_n-l).

Consider 

    S_𝔽_q(T_2,3,⋯,k(n+1)+∑_s=1^jβ_s∏_l=0^k-s-1X_n+1-l).

Suppose first that 1≤ j ≤ k-2.  Letting X_n+1 run over every element of the field leads to 

    S_𝔽_q(T_2,3,⋯,k(n+1)+∑_s=1^jβ_s∏_l=0^k-s-1X_n+1-l)   =    S_𝔽_q(T_2,3,⋯,k(n))
          +∑_α∈𝔽_q^×  S_𝔽_q(T_2,3,⋯,k(n)+∑_s=1^j+1γ_s(α)∏_l=0^k-s-1X_n-l),

where γ_1(α)=α and γ_s(α) = αβ_s-1.  By induction

    S_𝔽_q(T_2,3,⋯,k(n)+∑_s=1^j+1γ_s(α)∏_l=0^k-s-1X_n-l)=S_𝔽_q(T_2,3,⋯,k(n)+∑_s=1^j+1∏_l=0^k-s-1X_n-l).

Therefore,

    S_𝔽_q(T_2,3,⋯,k(n+1)+∑_s=1^jβ_s∏_l=0^k-s-1X_n+1-l)   =    S_𝔽_q(T_2,3,⋯,k(n))
          +∑_α∈𝔽_q^×  S_𝔽_q(T_2,3,⋯,k(n)+∑_s=1^j+1∏_l=0^k-s-1X_n-l).

However, (<ref>) does not depend on the choice of the β_t's. It follows that

    S_𝔽_q(T_2,3,⋯,k(n+1)+∑_s=1^jβ_s∏_l=0^k-s-1X_n+1-l)   =    S_𝔽_q(T_2,3,⋯,k(n+1)+∑_s=1^j∏_l=0^k-s-1X_n+1-l)

is true for 1≤ j≤ k-2.

Consider now the case j=k-1.  Again,  letting X_n+1 run over every element of the field leads to 

    S_𝔽_q(T_2,3,⋯,k(n+1)   +∑_s=1^k-1β_s∏_l=0^k-s-1X_n+1-l)= S_𝔽_q(T_2,3,⋯,k(n))
       +∑_α∈𝔽_q^× e^2π i/pTr_𝔽_q/𝔽_p(αβ_k-1) S_𝔽_q(T_2,3,⋯,k(n)+∑_s=1^k-1γ_s(α)∏_l=0^k-s-1X_n-l),

where γ_1(α)=α and γ_s(α) = αβ_s-1.  However, by induction

    S_𝔽_q(T_2,3,⋯,k(n)+∑_s=1^k-1γ_s(α)∏_l=0^k-s-1X_n-l)=S_𝔽_q(T_2,3,⋯,k(n)+∑_s=1^j+1∏_l=0^k-s-1X_n-l).

Since

    ∑_α∈𝔽_q^×e^2π i/pTr_𝔽_q/𝔽_p(αβ_k-1)=-1,

then it follows that

    S_𝔽_q(T_2,3,⋯,k(n+1)+∑_s=1^k-1β_s∏_l=0^k-s-1X_n+1-l)   =    S_𝔽_q(T_2,3,⋯,k(n))
          -∑_α∈𝔽_q^×  S_𝔽_q(T_2,3,⋯,k(n)+∑_s=1^k-1∏_l=0^k-s-1X_n-l).

Since (<ref>) does not depend on the choice of the β_t's, then it follows that

    S_𝔽_q(T_2,3,⋯,k(n+1)+∑_s=1^k-1β_s∏_l=0^k-s-1X_n+1-l)   =    S_𝔽_q(T_2,3,⋯,k(n+1)+∑_s=1^k-1∏_l=0^k-s-1X_n+1-l)

is true.  This completes the induction and the proof.


Next is the recurrence for exponential sums of trapezoid functions over any Galois field.



Let k≥ 2 be an integer and q=p^r with p prime. The sequence {S_𝔽_q(T_2,3,⋯,k(n))}_n=k^∞ satisfies a homogeneous linear recurrence with integer coefficients whose characteristic polynomial is given by 
 
    Q_T,k,𝔽_q(X)=X^k-q ∑ _l=0^k-2 (q-1)^l X^k-2-l.

 In particular, when q=2 we recover Theorem <ref>.



We present the proof for k>2.  The case k=2 can be proved using similar techniques.
 Start by turning X_n OFF and ON, that is, by letting X_n assume all its possible values.  This produces the identity
 
    S_𝔽_q(T_2,3,⋯,k(n))=S_𝔽_q(T_2,3,⋯,k(n-1))+ ∑_β∈𝔽_q^×S_𝔽_q(T_2,3,⋯,k(n-1)+β∏_j=1^k-1 X_n-j)

However, Lemma <ref> implies

    S_𝔽_q(T_2,3,⋯,k(n-1)+β∏_j=1^k-1 X_n-j)=S_𝔽_q(T_2,3,⋯,k(n-1)+ ∏_j=1^k-1 X_n-j)

for every β∈𝔽_q^×.  Therefore, (<ref>) reduces to 
 
    S_𝔽_q(T_2,3,⋯,k(n))=S_𝔽_q(T_2,3,⋯,k(n-1))+ (q-1)S_𝔽_q(T_2,3,⋯,k(n-1)+ ∏_j=1^k-1 X_n-j)

Consider now S_𝔽_q(T_2,3,⋯,k(n-1)+ ∏_j=1^k-1 X_n-j). Let X_n-1 assume all its possible values and use the same argument as before to get

    S_𝔽_q(T_2,3,⋯,k(n-1)+ ∏_j=1^k-1 X_n-j)   =    S_𝔽_p(T_2,3,⋯,k(n-2))
          + (q-1) S_𝔽_q(T_2,3,⋯,k(n-2)+∏_j=1^k-2 X_n-1-j+∏_j=1^k-1 X_n-1-j)

Thus, (<ref>) reduces to

    S_𝔽_q(T_2,3,⋯,k(n))   =   S_𝔽_q(T_2,3,⋯,k(n-1))+(q-1)S_𝔽_q(T_2,3,⋯,k(n-2))
          + (q-1)^2 S_𝔽_q(T_2,3,⋯,k(n-2)+∏_j=1^k-2 X_n-1-j+∏_j=1^k-1 X_n-1-j).

Continue in this manner to get the following equation

    S_𝔽_q(T_2,3,⋯,k(n))   =   ∑_l=1^k-1(q-1)^l-1S_𝔽_qT_2,3,⋯,k(n-l))
          +(q-1)^k-1 S_𝔽_q(T_2,3,⋯,k(n-k+1)+∑_j=0^k-2∏_l=0^j X_n-k+1-l).


On the other hand, let X_n+1 assume all its possible values and use Lemma <ref> to get the equation

    S_𝔽_q(T_2,3,⋯,k(n+1)+∑_j=0^k-2∏_i=0^j X_n+1-l)   =    S_𝔽_q(T_2,3,⋯,k(n))
          +e^2π i/pTr_𝔽_q/𝔽_p(1)S_𝔽_q(T_2,3,⋯,k(n)+∑_j=0^k-2∏_i=0^j X_n-l)
          +e^2π i/pTr_𝔽_q/𝔽_p(2)S_𝔽_q(T_2,3,⋯,k(n)+∑_j=0^k-2∏_i=0^j X_n-l)
          +e^2π i/pTr_𝔽_q/𝔽_p(3)S_𝔽_q(T_2,3,⋯,k(n)+∑_j=0^k-2∏_i=0^j X_n-l)
          ⋮
          +e^2π i/pTr_𝔽_q/𝔽_p(α_p-1)S_𝔽_q(T_2,3,⋯,k(n)+∑_j=0^k-2∏_i=0^j X_n-l).

Use the well-known formula

    ∑_β∈𝔽_q^× e^2π i/pTr_𝔽_q/𝔽_p(β)=-1.
  
to reduce (<ref>) to 

    S_𝔽_q(T_2,3,⋯,k(n+1)+∑_j=0^k-2∏_i=0^j X_n+1-l)   =    S_𝔽_q(T_2,3,⋯,k(n))
       =    - S_𝔽_q(T_2,3,⋯,k(n)+∑_j=0^k-2∏_i=0^j X_n-l).

This last equation is equivalent to 

    S_𝔽_q(T_2,3,⋯,k(n))   =    S_𝔽_q(T_2,3,⋯,k(n+1)+∑_j=0^k-2∏_i=0^j X_n+1-l)
           +S_𝔽_q(T_2,3,⋯,k(n)+∑_j=0^k-2∏_i=0^j X_n-l).


Let a_n = S_𝔽_q(T_2,3,⋯,k(n)+∑_j=0^k-2∏_i=0^j X_n-l). Then,

    S_𝔽_q(T_2,3,⋯,k(n))=a_n+1+a_n

and equation (<ref>) is now

    (a_n+1+a_n)   =   ∑_l=1^k-1(q-1)^l-1(a_n+1-l+a_n-l)+(q-1)^k-1 a_n-k+1.

The last equation reduces to

    a_n+1=∑_l=0^k-2 q(q-1)^la_n-1-l

This concludes the proof.


The polynomial Q_T,k,𝔽_q(X) is quite interesting. In particular, it seems to be irreducible for k > 2 and every q=p^r with p prime.  The irreducibility of Q_T,k,𝔽_q(X) when (k,r)=1 
is a consequence of Eisenstein-Dumas criterion.


Let f(x)=a_n x^n+a_n-1x^n-1+⋯+a_1 x+a_0 ∈ℤ[x] be a polynomial. Let p be a prime. Denote the p-adic valuation of an integer m by ν_p(m) (with ν_p(0)=+∞).  Suppose that

 
  * ν_p(a_n)=0,
 
  * ν_p(a_n-i)/i>ν_p(a_0)/n for 1≤ i ≤ n-1, and
 
  * (ν_p(a_0),n)=1.

Then, f(x) is irreducible over ℚ.



 Let q=p^r with p prime.  Suppose that (k,r)=1.  Then, the polynomial
 
    Q_T,k,𝔽_q(X)=X^k-q ∑ _l=0^k-2 (q-1)^l X^k-2-l

is irreducible over ℚ.



 This is a direct consequence of Eisenstein-Dumas criterion.


Exponential sums over 𝔽_q of rotation functions also satisfy homogeneous linear recurrences.  However, in general, these linear recurrences have higher order than the 
homogeneous linear recurrences satisfied by exponential sums of trapezoid functions.  In other words, the identity observed over 𝔽_2 between the linear recurrences of exponential sums of trapezoid Boolean functions and rotation symmetric Boolean functions is lost over 𝔽_q.
For example, if we consider the monomial rotation 

    R_2(n)=X_1X_2+X_2X_3+⋯+X_n-1X_n+X_nX_1,

then we have the following result.  This is the first result that relies on linear algebra.


 Suppose that p>2 is prime.  Then, {S_𝔽_p(R_2(n)} satisfy the homogeneous linear recurrence with characteristic polynomial 
 
    Q_R,2,𝔽_p(X)=X^4-p^2.




Turn X_n and X_n-1 OFF and ON, that is, let them assume all values in 𝔽_p, and use the identity

    S_𝔽_p(T_2(n)+β X_n) = S_𝔽_p(T_2(n)+ X_n),  for β∈𝔽_p^×

to get the equation 

    S_𝔽_p(R_2(n))   =    S_𝔽_p(T_2(n-2))+(p-1)S_𝔽_p(T_2(n-2)+X_n-2)
          +∑_α∈𝔽_p^×∑_β∈𝔽_pe^2π i/pαβS_𝔽_p(T_2(n-2)+α X_1+β X_n-2),

Let 

    a_0(n)   =   S_𝔽_p(T_2(n))
    
     a_1(n)   =   S_𝔽_p(T_2(n)+X_n)
    
     b_α,β(n)   =   S_𝔽_p(T_2(n)+α X_1+β X_n)   for α∈𝔽_p^×, β∈𝔽_p.

Then,

    S_𝔽_p(R_2(n))   =    a_0(n-2)+(p-1)a_1(n-2)+∑_α∈𝔽_p^×∑_β∈𝔽_pe^2π i/pαβb_α,β(n-2).

Observe that

    a_0(n)   =    a_0(n-1)+(p-1)a_1(n-1)
    
     a_1(n)   =    a_0(n-1)-a_1(n-1)
    
     b_α,β(n)   =   ∑_γ∈𝔽_p e^2π i/p(βγ) b_α,γ(n-1),

which can be written in matrix form as

    (
     [       a_0(n);       a_1(n);     b_1,0(n);     b_1,1(n);            ⋮; b_p-1,p-1(n) ])=A(p)(
     [       a_0(n-1);       a_1(n-1);     b_1,0(n-1);     b_1,1(n-1);              ⋮; b_p-1,p-1(n-1) ])

where

    A(p)   =(
    [   A_0(p)        O        O        ⋯        O;        O   A_1(p)        O        ⋯        O;        O        O   A_2(p)        ⋯        O;        ⋮        ⋮        ⋮        ⋱        ⋮;        O        O        O        ⋯ A_p-1(p);          ]),

and

    A_0(p)=(
    [   1 p-1;   1  -1;     ])     and     A_j(p) = (
    [                 1                 1                 1                 ⋯                 1;                 1        e^2  π i/p        e^4  π i/p                 ⋯     e^2(p-1)π i/p;                 1       e^4   π i/p         e^8 π i/p                 ⋯  e^2× 2(p-1)π i/p;                 ⋮                 ⋮                 ⋮                 ⋱                 ⋮;                 1    e^2(p-1) π i/p    e^4(p-1) π i/p                 ⋯ e^2× (p-1)^2π i/p;                   ]),

for 1≤ j ≤ p-1.
It is clear that the first block A_0(p) satisfies X^2-p.  All other blocks A_j(p)'s, for 1≤ j ≤ p-1, are √(p)· W_p, where W_p is the p× p square Discrete Fourier 
Transform matrix.
Observe that

    A_j(p)^2 = (
    [ p 0 ⋯ 0 0; 0 0 ⋯ 0 p; 0 0 ⋯ p 0; ⋮ ⋮   ⋮ ⋮; 0 p ⋯ 0 0;   ]).

Therefore,

    A_j(p)^4 = (
    [ p^2   0   0   ⋯   0;   0 p^2   0   ⋯   0;   0   0 p^2   ⋯   0;   ⋮   ⋮   ⋮   ⋱   ⋮;   0   0   0   ⋯ p^2;     ]).

In other words, the big blocks A_j(p)'s satisfiy X^4-p^2.  Since X^2-p |  X^4-p^2, then we conclude that the matrix A(p) satisfies the polynomial
 
    Q_R,2,𝔽_p(X)=X^4-p^2.

This means that the sequences {a_0(n)}, {a_1(n)} and {b_α,β(n)}, for α∈𝔽_p^×,β∈𝔽_p, all satisfy the linear
recurrence with characteristic polynomial given by Q_R,2,𝔽_p(X).  Since {S_𝔽_p(R_2(n))} is a combination of these sequences, then it also satisfies such recurrence.
This concludes the proof.


We are now ready to prove one of the main results of this article.  That is, exponential sums of rotation polynomials satisfiy linear recurrences with integer coefficients.



 Let k≥ 2 be an integer and q=p^r with p prime and r≥ 1.  The sequence {S_𝔽_q(R_2,3,⋯,k(n))}_n≥ k satisfies a linear recurrence with integer coefficients.



 Let ζ_p=e^2π i/p. Consider the expression S_𝔽_q(R_2,3,⋯, k(n+k)).  Let X_n+k, X_n+k-1, ⋯, X_n assume all values in 𝔽_q and observe that S_𝔽_q(R_2,3,⋯, k(n+k))
 can be written as a linear combination of expressions of the form
 
    a_α;β(n)=S_𝔽_q(T_2,3,⋯, k(n)+∑ _j=1^k-1(α _j ∏ _l=1^j X_n+1-l+β _j ∏ _l=1^j X_l)),

 where α=(α_1,⋯,α_k) ∈𝔽_q^k-1 and β=(β_1,⋯,β_k) ∈𝔽_q^k-1.
 However, note that for each α,β∈𝔽_q^k-1, we have
 
    a_α;β(n) = ∑_γ,λ∈𝔽_q^k-1c_γ,λ· a_γ,λ(n-1),

where c_γ,λ∈ℤ[ζ_p] is a cyclotomic integer.  Let A_2,3,⋯, k(q) be the corresponding matrix for the linear equations in (<ref>) and
F(X) be any annihilating polynomial for A_2,3,⋯, k(q).   We can assume that F(X) has integer coefficients.  This is because the minimal polynomial of A_2,3,⋯,k(q) is monic, 
has algebraic integers coefficients and integrality is transitive.  Then each {a_α;β(n)}_n satisfies the linear recurrence with characteristic polynomial given
by F(X). Since {S_𝔽_q(R_2,3,⋯, k(n+k))} is a linear combination of these sequences, then {S_𝔽_q(R_2,3,⋯, k(n+k))} also satisfies such recurrence.
This concludes the proof.


We know that the identity between linear recurrences of exponential sums of trapezoid Boolean functions and rotation symmetric Boolean functions is lost over 𝔽_q.  However, 
the proof of Theorem <ref> suggests that a relation can be recovered.


Let q=p^r with p prime and r≥ 1.  Let μ_T,k,𝔽_q(X) and μ_R,k,𝔽_q(X) be the characteristic polynomials associated to the minimal homogeneous linear recurrences with integer coefficients 
satisfied by {S_𝔽_q(T_2,3,⋯, k(n))} and {S_𝔽_q(R_2,3,⋯, k(n))} (resp.).  Then,

    μ_T,k,𝔽_q(X) | μ_R,k,𝔽_q(X).

In particular, if (k,r)=1,  then Q_T,k,𝔽_q(X) | μ_R,k,𝔽_q(X)



 In the proof of Theorem <ref>.  Observe that {a_0;0(n)}={S_q(T_2,3,⋯,k(n))}, this implies (<ref>).  Now, if (k,r)=1,  
then Q_T,k,𝔽_q(X) is irreducible and therefore μ_T,k,𝔽_q(X)=Q_T,k,𝔽_q(X).  This concludes the proof.




Let {b(n)} be a sequence on an integral domain D.  A set of sequences 
    {{a_1(n)}, {a_2(n)},⋯, {a_s(n)}},
 where s is some natural number, is called a 
recursive generating set for {b(n)} if 

 
  * there is an integer l such that for every n, b(n) can be written as a linear combination of the form 
 
    b(n)=∑_j=1^s c_j· a_j(n-l),
  
 where c_j's are constants that belong to D, and
 
  * for each 1≤ j_0 ≤ s and every n, a_j_0(n) can be written as a linear combination of the form 
 
    a_j_0(n)=∑_j=1^s d_j· a_j(n-1),

 where d_j's are also constants that belong to D.

The sequences {a_j(n)}'s are called recursive generating sequences for {b(n)}.




It is a well-known result in the theory of recursive sequences that a sequence that has a recursive generating set satisfies a linear recurrence with constant coefficients.  In fact, this technique 
has been used in Theorems <ref> and <ref>.


Theorem <ref> generalizes to monomial rotation functions and linear combinations of them, that is, exponential sums over any Galois field of linear combinations of monomial rotation polynomials 
satisfy linear recurrences.  Of course, in general, we might need to turn OFF and ON more than k variables, even if the rotation is of degree k.  Also, even though the sequences 
(<ref>) always exist, their number might be too big to be handled by hand.  For example, consider the sequence of exponential sums {S_𝔽_3(R_2,3(n))}.  After some 
identifications, the authors needed 24 different recursive generating sequences (not claiming that this is optimal) of the form  (<ref>) and their corresponding 24× 24 matrix in order 
to find that {S_𝔽_3(R_2,3(n))} satisfy the linear recurrence whose characteristic polynomial is given by

    X^6-3 X^4-9 X^3+9 X+18   =   (X^3-3) (X^3-3 X-6)
       =   (X^3-3)Q_T,3,𝔽_3(X).

Also, in general, finding the minimal polynomial of a matrix is not an easy task, therefore explicit formulas like the ones in Theorem <ref> and Theorem <ref> are much harder to get.

In the next section, this technique is used to prove that exponential sums over Galois fields of elementary symmetric polynomials (and linear combinations of them) satisfy homogeneous linear
recurrences with integer coefficients.







§ LINEAR RECURRENCES OVER 𝔽_Q: SYMMETRIC POLYNOMIALS CASE



It is a well-established result that exponential sums of symmetric Boolean functions are linear recurrent.  This was first established by Cai, Green and Thierauf <cit.>.   In <cit.>, Castro and 
Medina use this result to show that a conjecture of Cusick, Li, Stnic <cit.> is true asymptotically.  In <cit.>, some of the results of <cit.> where 
extended to some perturbations of symmetric Boolean functions.  This recursivity was also used in <cit.> to study the periodicity mod p (p prime) of exponential sums of symmetric Boolean functions. 

In this section we show that exponential sums of some symmetric polynomials are linear recurrent over any Galois field.  Remarkably, the proof uses the same argument as in the proof of 
Theorem <ref>. We decided to include the proof for completeness of the writing.  However, the reader is welcome to skip the proof.

Let σ_n,k be the elementary symmetric polynomial in n variables of degree k. For example,

    σ_4,3 = X_1 X_2 X_3+X_1 X_4 X_3+X_2 X_4 X_3+X_1 X_2 X_4.

We have the following result.



 Let k≥ 2 be an integer and q=p^r with p prime and r≥ 1.  The sequence {S_𝔽_q(σ_n,k)} satisfies a linear recurrence with constant coefficients.



Consider the expression S_𝔽_q(σ_n+k,k).  Define

    a_β(n)=S_𝔽_q(σ_n,k+∑ _j=1^k-1β_j σ_n,k-j),

The set {a_β(n)}_β∈𝔽_q^k-1 is a recursive generating set for S_𝔽_q(σ_n+k,k).  Therefore, the sequence 
{S_𝔽_q(σ_n+k,k)}_n≥ 0 satisfies a linear recurrence with constant coefficients.  As in the proof of Theorem <ref>, it can be argued that a linear recurrence with 
integer coefficients is guaranteed to exist.  This concludes the proof.


This result can be generalized to any polynomial of the form 

    ∑ _j=0^k-1β_j σ_n,k-j,

with β_j ∈𝔽_q.  We present the result without proof, as it follows almost verbatim as the one from Theorem <ref>.



 Let k≥ 2 be an integer and q=p^r with p prime and r≥ 1.  The sequence 

    S_𝔽_q(∑ _j=0^k-1β_j σ_n,k-j)

satisfies a linear recurrence with constant coefficients, regardless of the choice of the β_j's.




 Consider the sequence {S_𝔽_3(σ_n,3)}.  Recall that in this case the generating sequences are given by 
 
    a_(s,t)(n)={S_𝔽_3(σ_n,3+sσ_n,2+tσ_n,1)},

 where s,t∈𝔽_3.  Establish the order
 
    (0,0), (1,0), (2,0), (0,1), (1,1), (2,1), (0,2),(1,2), (2,2).

 Then, 
 
    ( [ a_(0,0)(n); a_(1,0)(n);          ⋮; a_(2,2)(n) ]) = A ( [ a_(0,0)(n-1); a_(1,0)(n-1);            ⋮; a_(2,2)(n-1) ]),

where the matrix A is given by

    A=(
    [          1          1          1          0          0          0          0          0          0;          0          1          0          0          0          1          1          0          0;          0          0          1          0          1          0          1          0          0;          0          0          0          1  e^2 i π/3 e^-2 i π/3          0          0          0; e^-2 i π/3          0          0          0          1          0          0          0  e^2 i π/3;  e^2 i π/3          0          0          0          0          1          0 e^-2 i π/3          0;          0          0          0          0          0          0          1 e^-2 i π/3  e^2 i π/3;          0          0 e^-2 i π/3  e^2 i π/3          0          0          0          1          0;          0  e^2 i π/3          0 e^-2 i π/3          0          0          0          0          1;            ]).

The minimal polynomial of A is given by 

    μ_A(X)    =    X^9-9 X^8+36 X^7-81 X^6+108 X^5-81 X^4+81 X^2-81 X+27
       =   (X^3-3 X^2+3) (X^6-6 X^5+18 X^4-30 X^3+36 X^2-27 X+9).

Therefore, {S_𝔽_3(σ_n,3)} satisfies the linear recurrence with characteristic polynomial given by μ_A(X).




 §.§ Quadratic case


The case of the elementary symmetric polynomial of degree 2 is fascinating.  Observe that
 
    a_s(n) = S_𝔽_p(σ_n,2+s σ_n,1),

where s∈𝔽_p, are the generating sequences of {S_𝔽_p(σ_n,2)}.  Also,

    ( [   a_0(n);   a_1(n);        ⋮; a_p-1(n) ]) = M(p) ( [   a_0(n-1);   a_1(n-1);          ⋮; a_p-1(n-1) ]),

where the matrix M(p) is given by

    M(p)=([                 1                 1                 1                 1                 1                 ⋯                 1;     e^2(p-1)π i/p                 1         e^2 π i/p         e^4 π i/p         e^6 π i/p                 ⋯     e^2(p-2)π i/p;  e^2× 2(p-2)π i/p  e^2× 2(p-1)π i/p                 1        e^4  π i/p         e^8 π i/p                 ⋯  e^2× 2(p-3)π i/p;  e^2× 3(p-3)π i/p  e^2× 3(p-2)π i/p  e^2× 3(p-1)π i/p                 1        e^6  π i/p                 ⋯  e^2× 2(p-3)π i/p;  e^2× 4(p-4)π i/p  e^2× 4(p-3)π i/p  e^2× 4(p-2)π i/p  e^2× 4(p-2)π i/p                 1                 ⋯  e^2× 2(p-3)π i/p;                 ⋮                 ⋮                 ⋮                 ⋮                 ⋮                 ⋱                 ⋮;    e^2(p-1) π i/p e^2× 2(p-1) π i/p e^2× 3(p-1) π i/p e^2× 4(p-1) π i/p e^2× 5 (p-1)π i/p                 ⋯                 1;                   ]).

The matrix M(p) can be obtained from the p× p Fourier Discrete Transform Matrix by replacing its j-row r_j by RTC^j-1( r_j), where RTC is the rotate through carry
function

    RTC(a_1,a_2,a_3,⋯, a_n) = (a_n,a_1,a_2,⋯, a_n-1)

and RTC^m represents m iterations of RTC.


It is not hard to prove that M(p) is a Complex Hadamard Matrix.  In particular,

    M(p) M(p)^T = M(p)^T M(p) = (
    [ p 0 0 ⋯ 0; 0 p 0 ⋯ 0; 0 0 p ⋯ 0; ⋮ ⋮ ⋮ ⋱ ⋮; 0 0 0 ⋯ p;   ]).

This implies that M(p) is diagonalizable and that all its eigenvalues satisfy |λ|=√(p).  Moreover, its eigenvalues are related to the number-theoretical quadratic Gauss sum mod p.  
The quadratic Gauss sum mod p is defined by

    g(a;p)=∑_k=0^p-1e^2π i ak^2/p

It is well-established that

    g(a;p) = (a/p)g(1;p),

where (a/p) denotes the Legendre's symbol, and that

    g(1;p) = √(p)    p≡ 1  4 
    
     i√(p)    p≡ 3  4.





Let C(p) be the set of eigenvalues of M(p). Let ζ_p =e^2π i/p.  Then, λ∈ C(p) if and only if

    λ = -2p g(1;p)ζ^-s a^2.

In particular, |C(p)|=(p+1)/2.



Let p be an odd prime number and ζ=exp(2π i/p). The matrix
M(p) has (j,k)-entry ζ^j(k-j) where j and
k run from 0 to p-1 inclusive.  We compute the eigenvalues
of M(p) simply by writing down its eigenvectors.

Set s=1/2(p-1). Then 1≡-2s (mod p)
For 0≤ a≤ p-1, let v_a be the column vector with k-entry
ζ^s(k-a)^2 where 0≤ k≤ p-1. Then the v_a are the cyclic shifts of
v_0. The entry in row j of M(p)v_a is

    ∑_k=0^p-1ζ^j(k-j)+s(k-a)^2   =   ∑_k=0^p-1ζ^-2sjk+2sj^2+sk^2-2sak+sa^2
       =   ∑_k=0^p-1ζ^s(k-a-j)^2+sj^2-2saj
       =   g(s;p)ζ^s(j-a)^2-sa^2.

This is g(s,p)ζ^-sa^2 times the entry in row j of v_a.
Therefore each v_a is an eigenvector with eigenvalue

    g(s;p)ζ^-sa^2= sp g(1;p)ζ^-sa^2
    =-2p g(1;p)ζ^-sa^2.


As these eigenvalues are not all distinct, there remains the possibility
that some of these eigenvectors v_a are not linearly independent.
That can only happen with eigenvectors in the same eigenspace, so
for v_a and v_p-a where 0<a<p. But it is clear that none
of the v_a are multiples of any of the others; simply consider
the quotients of corresponding entries. So we have a dimension-two
eigenspace for each eigenvalue -2p g(1,p)ζ^-sa^2
for 1≤ a≤1/2(p-1). This completes the proof.



Note that if λ is defined as in (<ref>), then equation (<ref>) implies

    λ^p = (-i)^p-1/2√(p^p)

for every odd prime p.  Therefore, Theorem <ref> leads to

    M(p)^p =(
    [ (-i)^p-1/2√(p^p)                0                0                ⋯                0;                0 (-i)^p-1/2√(p^p)                0                ⋯                0;                0                0 (-i)^p-1/2√(p^p)                ⋯                0;                ⋮                ⋮                ⋮                ⋱                ⋮;                0                0                0                ⋯ (-i)^p-1/2√(p^p);                  ]),

and so

    M(p)^2p =(
    [ (-1/p)p^p         0         0         ⋯         0;         0 (-1/p)p^p         0         ⋯         0;         0         0 (-1/p)p^p         ⋯         0;         ⋮         ⋮         ⋮         ⋱         ⋮;         0         0         0         ⋯ (-1/p)p^p;           ]).

Thus,

    X^2p-(-1/p)p^p

is an annihilating polynomial for the matrix M(p), which in turns implies that {S_𝔽_p(σ_n,2)} satisfies the linear recurrence with characteristic polynomial (<ref>).






§ SOME OBSERVATIONS AND CONCLUDING REMARKS


We had shown that exponential sums over Galois fields of trapezoid polynomials and rotation polynomials satisfy linear recurrences with integer coefficients.  This means that they can be
calculated efficiently if we know a priori some initial values. We predict the initial conditions for two families of these type of polynomials.

Consider the trapezoid polynomial T_2,3,⋯,k(n). Recall that {S_𝔽_q(T_2,3,⋯,k(n))} satisfies the linear recurrence with integer coefficients with characteristic polynomial 
given by Q_T,k,𝔽_q(X), which is of degree k.  This implies that we need to know k initial values in order to calculate the whole sequence.  Of course, {S_𝔽_q(T_2,3,⋯,k(n))}
makes sense only for values of n≥ k, however, since it satisfies a linear recurrence with integer coefficients, it can be extended to values of n<k.  We conjecture the following.


 Let {t_k,q(n)} be defined by 
 
    t_k,q(j)    =    q^j,    for 0≤ j ≤ k-1
    
      t_k,q(n)    =    =q ∑ _l=0^k-2 (q-1)^l t_k,q(n-(l+2)),     for n≥ k.

Then, S_𝔽_q(T_2,3,⋯,k(n)) = t_k,q(n) for all values of n≥ k.

We were able to prove that this conjecture is true for k=2,3,4, but the general statement remains open.  We were also able to predict the initial conditions for {S(R_2,3,⋯, k(n))} (Boolean case). Recall that this sequence satisfies the linear recurrence whose characteristic polynomial is given by

    p_k(X)=X^k -2 (X^k-2+X^k-3+⋯+X+1).

Therefore, as in the case of trapezoid polynomial T_2,3,⋯,k(n), we need to know k initial values in order to calculate the whole sequence.


Let

    δ_o(j) =
     0     if j  is even
    
     1     if j  is odd.

Define {r_k(n)} by 
 
    r_k(0)   =    k
    
      r_k(j)   =    2^j-δ_o(j)· 2,    for 1≤ j≤ k-1
    
      r_k(n)   =    2∑_l=0^k-2 r_k(n-(l+2)),     for n≥ k.

Then, S(R_2,3,⋯,k(n)) = r_k(n) for all values of n≥ k.


The problem of finding suitable initial conditions for this type of sequences is a nice problem, but also an important one.  For example, if 
Conjecture <ref> is true, then 

    {S(R_2,3,⋯,15(n))}_n≥ 15   =    32766, 65504, 131036, 262036, 524096, 104813,2096268, 4192412⋯
    {S(R_2,3,⋯,30(n))}_n≥ 30   =   1073086444, 2146129256, 4292171136, 8584167576, 17167985776,
           34335272736, 68669148016, 137335500952,⋯
    {S(R_2,3,⋯,100(n))}_n≥ 100   =    1267650600228229401496703205376, 2535301200456458802993406410548,
          5070602400912917605986812821300, 10141204801825835211973625642388, 
          20282409603651670423947251284976, 40564819207303340847894502569720, 
          ⋯

On the other hand, we know that Conjecture <ref> is true for k=3, which means, for example, that

    {S_𝔽_9(T_2,3(n))}_n≥ 3   =    153, 1377, 7209, 23409, 164025, 729729, 3161673, 18377361,⋯
    {S_𝔽_7^3(T_2,3(n))}_n≥ 3   =    234955, 80589565, 13881523159, 55203852025, 14215001955427,
          1647320876934229, 11351488736356111, 2232536080171760209,⋯
    {S_𝔽_71^2(T_2,3(n))}_n≥ 3   =    50818321, 256175156161, 645881606118001, 2582501749259041, 
           9764439145967152081, 16422699840579863752321, 
          114835229977615135072561, 330868420079857977922668001,⋯.

Also, if Conjecture <ref> is true in general, then we have, for example, 

    {S_𝔽_5(T_2,3,4,5(n))}_n≥ 5   =    1845, 9225, 39725, 173025, 730725, 2988025, 13244125, 56108625,⋯
    {S_𝔽_11^2(T_2,3,⋯, 7(n))}_n≥ 7   =    18445769583241, 2231938119572161, 226346720724231481,
          22141818198352009201, 2044333948085969113321,
           170550498912524502711841, 11342127359186464124132761,⋯
    {S_𝔽_7919(T_2,3,⋯,8(n))}_n≥ 8   =    13665512318276822315545157633, 108217192048434155916802103295727, 
          734609211013142008709051078210604961,
          4848502223556916452901817857822360556623,
          30722822355930196223839440343843855453844801, 
          182535766024343164334384388453936618605681619887,⋯.


All these values where calculated almost instantaneously.  Another nice problem is to automatize the process presented in this work.





plain
1
sperber A. Adolphson and S. Sperber. 
p-adic Estimates for Exponential Sums and the of Chevalley-Warning.
Ann. Sci. Ec. Norm. Super., 4^e série,  20, 545–556, 1987.

ax J. Ax.
Zeros of polynomials over finite fields. 
Amer. J. Math., 86, 255–261, 1964.

BCP M. L. Bileschi, T.W. Cusick and D. Padgett.
Weights of Boolean cubic monomial rotation symmetric functions.
Cryptogr. Commun., 4, 105–130, 2012.

cai J. Cai, F. Green and T. Thierauf. 
On the correlation of symmetric functions.
Math. Systems Theory, 29, 245–258, 1996.

cm1 F. N. Castro and L. A. Medina. 
Linear Recurrences and Asymptotic Behavior of Exponential Sums of Symmetric Boolean Functions. 
Elec. J. Combinatorics, 18:#P8, 2011.

cm2 F. N. Castro and L. A. Medina. 
Asymptotic Behavior of Perturbations of Symmetric Functions.  
Annals of Combinatorics, 18:397–417, 2014.

cm3 F. N. Castro and L. A. Medina. 
Modular periodicity of exponential sums of symmetric Boolean functions.
Discrete Appl. Math. 217, 455–473, 2017.

cusick4 T. W. Cusick. 
Hamming weights of symmetric Boolean functions.
Discrete Appl. Math. 215, 14–19, 2016.

cusickArXiv T. W. Cusick.
Weight recursions for any rotation symmetric Boolean functions.
arXiv:1701.06648 [math.CO]

cusickjohns T. W. Cusick and B. Johns.
Recursion orders for weights of Boolean cubic rotation symmetric functions.
Discr. Appl. Math., 186, 1–6, 2015.

cusick2 T. W. Cusick, Y. Li, and  P. Stnic.
Balanced Symmetric Functions over GF(p).
IEEE Trans. on Information Theory 5, 1304-1307, 2008.

cusickstanica T.W. Cusick and P. Stnic.
Fast evaluation, weights and nonlinearity of rotation symmetric functions.
Discr. Math., 258, 289–301, 2002.

dalaimaitrasarkar D. K. Dalai, S. Maitra and S. Sarkar. 
Results on rotation symmetric Bent functions.
Second International Workshop on Boolean Functions: Cryptography and
Applications, BFCA'06, publications of the universities of Rouen and Havre, 137–156, 2006.

hell M. Hell, A. Maximov and S. Maitra. 
On efficient implementation of search strategy for rotation symmetric Boolean functions. 
Ninth International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2004, Black Sea Coast, Bulgaria,
2004.

fspectrum M. Kolountzakis, R. J. Lipton, E. Markakis, A. Metha and N. K. Vishnoi. 
On the Fourier Spectrum of Symmetric Boolean Functions.
Combinatorica, 29, 363–387, 2009.

maxhellmaitra A. Maximov, M. Hell and S. Maitra. 
Plateaued Rotation Symmetric Boolean Functions on Odd Number of Variables. 
First Workshop on Boolean Functions:Cryptography and Applications, BFCA'05, publications of the universities of Rouen and Havre, 83–104, 2005.

mm1 O. Moreno and C. J. Moreno.
Improvement of the Chevalley-Warning and the Ax-Katz theorems.
Amer. J. Math., 117, 241–244, 1995.

mm O. Moreno and C. J. Moreno.
The MacWilliams-Sloane Conjecture on the Tightness of the Carlitz-Uchiyama Bound and the Weights of Dual of BCH Codes.
IEEE Trans. Inform. Theory, 40,  1894–1907, 1994.

piequ J. Pieprzyk and C.X. Qu.
Fast hashing and rotation-symmetric functions.
J. Universal Comput. Sci., 5 (1), 20–31, 1999.

fdegree A. Shpilka and A. Tal.
On the Minimal Fourier Degree of Symmetric Boolean Functions.
Combinatorica, 88, 359–377, 2014.

stanicamaitra P. Stnic and S. Maitra. 
Rotation Symmetric Boolean Functions – Count and Cryptographic Properties. 
Discr. Appl. Math., 156, 1567–1580, 2008

stanicamaitraclark P. Stnic, S. Maitra and J. Clark. 
Results on Rotation Symmetric Bent and Correlation Immune Boolean Functions. 
Fast Software Encryption, FSE 2004, Lecture Notes in Computer Science, 3017, 161–177. SpringerVerlag, 2004.






