Proceedings of the Steklov Institute of Mathematics, Vol. 218, 1997, pp. 332–339. Translated from Trudy Matematicheskogo Instituta imeni V. A. Steklova, Vol. 218, 1997, pp. 335–342. Original Russian Text Copyright \begin{matrix}c \\ ◯ \end{matrix} 1997 by Nechaev. English Translation Copyright \begin{matrix}c \\ ◯ \end{matrix} by ���� �����/Interperiodica Publishing (Russia).

Distribution of Signs in a Sequence of Rectangular Matrices over a Finite Field

V. I. Nechaev

Received February, 1997

This article deals with the problem of distribution of the collections s of fixed signs on a given segment of a row or a column in a sequence of rectangular matrices which satisfy the linear recurrence equation over a finite field and the number of coincidence of these collections.

The problem of the number of the collections s (< n) of signs on a full period of a maximal linear recurrent sequence of order n was considered by Laksov [8] and Zierler [10] and the problem of number of occurences of a fixed sign on a part of the period of a maximal linear recurrent sequence was studied by Lidl and Niderreiter [3] and [9]. The problem of the occurence of a fixed collection of signs as successive values of a maximal linear recurrent sequence was considered by N. M. Korobov. In this article we use the approach to the study of linear recurrent sequences which was described, for the first time, in the articles [4–7].

Notation and terms. Assume that p is a prime number, ℕ is the set of positive integers, ℤ is the set of integers, ℂ is the set of complex numbers; n, s, q, X ∈ ℕ, 𝔽 = 𝔽_{q} = GF(q) is a finite field of q elements, p | q; V_{n} is an n-dimensional vector space over the field 𝔽; α • β is the inner product of the vectors α and β in the space V_{n}; V_{n}^{∗} is the set of nonzero vectors of the space V_{n}; M • is a linear operator on the space V_{n} for any square matrix M of order n over the field 𝔽_{q}, as well as on the space V_{n,k} of rectangular n × k matrices; E_{n} is the identity n × n matrix; □_{n,k} is zero matrix on the space V_{n,k}, □_{n,1} = θ^{(n)} is the null-vector of the space V_{n,1} = V_{n}; a_{1}, …, a_{n} ∈ 𝔽, a_{n} ≠ 0, f = λ^{n} − a_{1}λ^{n−1} − a_{2}λ^{n−2} − ⋯ − a_{n} is the characteristic polynomial of a linear recurrence equation of the form

δ_{x+n} = a_{1}δ_{x+n−1} + a_{2}δ_{x+n−2} + ⋯ + a_{n}δ_{x}, x ∈ ℤ,  δ_{0}, δ_{1}, …, δ_{n−1} ∈ 𝔽.  (1)

By the symbol δ = {δ_{x}}_{x=−∞}^{+∞} = {δ_{x}}_{x} we denote any solution of equation (1). The nonzero solution δ = {δ_{x}}_{x=−∞}^{+∞} over the field 𝔽 of equation (1) is called a maximal linear recurrent sequence if its primitive period, i.e., the least natural period, is equal to q^{n}−1; ord f is the order of the polynomial over the field 𝔽, i.e., the least positive integer t such that x^{t} − 1 is divisible by the polynomial f; the polynomial f over the field 𝔽 = 𝔽_{q} is said to be primitive if ord f = q^{deg f} − 1; ρ^{(j)} = {ρ_{x}^{(j)}}_{x=0}^{∞} for every j = 0, 1, …, n − 1 is the solution of equation (1) with the initial values

ρ_{x}^{(j)} = \{ \begin{matrix}1 & for x = j \\ 0 & for x ≠ j, \end{matrix} 0 ≤ x ≤ n − 1;

β_{x} and Δ_{x} are n-dimensional vectors, for all integers x, defined by the conditions

β_{x} = ∥ ρ_{x}^{(0)} ; ρ_{x}^{(1)} ; ⋮ ; ρ_{x}^{(n−2)} ; ρ_{x}^{(n−1)} ∥ , Δ_{x} = ∥ δ_{x} ; δ_{x+1} ; ⋮ ; δ_{x+n−2} ; δ_{x+n−1} ∥ .

Assume, furthermore, that

A = ∥ \begin{matrix}0 & 1 & … & 0 & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & … & 1 & 0 \\ 0 & 0 & … & 0 & 1 \\ a_{n} & a_{n−1} & … & a_{2} & a_{1} \end{matrix} ∥

is a matrix of equation (1), B = A^{T} is the transposite of the matrix A. Thus, B = [β_{1}, β_{2}, …, β_{n}], i.e., the vectors β_{1}, β_{2}, …, β_{n} are columns of the matrix B; b_{1}, b_{2}, …, b_{s} ∈ 𝔽; m, m_{1}, m_{2}, …, m_{s} ∈ ℤ.

Next suppose that χ is a character of the additive group of the field 𝔽 and χ_{0} is the principal character of the same group, e_{t}(x) = exp(2πix/t).

It is important to note for what follows that the set of solutions of equation (1) forms an ndimensional vector space over the field 𝔽 of ordinary operators on sequences, the primitive period of any solution of equation (1) divides the order of the characteristic polynomial of this equaltion and is equal to it if the characteristic polynomial is a primitive polynomial over the field 𝔽 [9]. The polynomial f is primitive over the field 𝔽 if and only if ord f = q^{n} − 1. The primitive polynomial over the field 𝔽 is irreducible over the same field. The order of the characteristic polynomial f of the square matrix C over a finite field is equal to the order of this matrix (ord f = ord C).

Lemma 1. δ_{x+y} = β_{x} • Δ_{y} holds for all integers x, y.

Proof. Indeed, the relation

δ_{x+y} = δ_{y}ρ_{x}^{(0)} + δ_{y+1}ρ_{x}^{(1)} + ⋯ + δ_{y+n−1}ρ_{x}^{(n−1)}  (2)

is valid for x = 0, 1, …, n − 1 for every fixed y, and therefore the solutions δ_{x+y} and β_{x} • Δ_{y} of equation (1) are equal for n successive values of the variable x.

Lemma 2. The solutions {δ_{x+h}}_{x}, …, {δ_{x+g}}_{x} of equation (1) are linearly independent over the field 𝔽 if and only if the vectors β_{h}, …, β_{g} of the space V_{n} are linearly independent over the field 𝔽.

Proof. It follows from Lemma 1.

Lemma 3. For all integers x we have

(1) A^{x} • Δ_{0} = Δ_{x},

(2) B^{x} • β_{0} = β_{x}.

Proof. (1) follows from the easily verifiable relation A • Δ_{x} = Δ_{x+1}.

(2) Setting δ_{y} = ρ_{y}^{(j)}, where 0 ≤ j ≤ n − 1, in relation (2), we obtain

ρ_{x+y}^{(j)} = ρ_{y}^{(j)} × ρ_{x}^{(0)} + ρ_{y+1}^{(j)} × ρ_{x}^{(1)} + ⋯ + ρ_{y+n−1}^{(j)} × ρ_{x}^{(n−1)}.

334 NECHAEV

It follows that

ρ_{x+y}^{(j)} = ρ_{1}^{(0)} × ρ_{y}^{(j)} + ρ_{1}^{(1)} × ρ_{y+1}^{(j)} + ⋯ + ρ_{1}^{(n−1)} × ρ_{y+n−1}^{(j)}

for all y ∈ ℤ. Thus B • β_{y} = β_{y+1}.

Lemma 4. The vectors β_{1}, β_{2}, …, β_{n} are linearly independent over the field 𝔽. Proof. Indeed,

∥ β_{1} β_{2} … β_{n} ∥ = ∥ \begin{matrix}0 & 0 & … & 0 & a_{n} \\ 1 & 0 & … & 0 & a_{n−1} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & … & 0 & a_{2} \\ 0 & 0 & … & 1 & a_{1} \end{matrix} ∥ .

Lemma 5. Let γ be a nonzero vector of the space V_{n}. Then

(B^{x} • γ) • Δ_{y} = γ • Δ_{x+y}  (3)

for every integer x, y.

Proof. Since the vectors β_{1}, β_{2}, …, β_{n} are linearly independent, it follows that the relation γ = c_{1}β_{1} + c_{2}β_{2} + ⋯ + c_{n}β_{n} holds true for certain c_{1}, c_{2}, …, c_{n}. Identity (3) can be direcly verified.

Lemma 6. Let γ ∈ V_{n}, χ ≠ χ_{0}. Then

(1) ∑_{a∈𝔽}χ(a × c) = \{ \begin{matrix}q & for c = 0 \\ 0 & for c ≠ 0; \end{matrix}

(2) ∑_{α∈V_{n}} χ(α • γ) = \{ \begin{matrix}q^{n} & for γ = θ \\ 0 & for γ ≠ θ. \end{matrix}

Proof. (1) Indeed, if c ∈ 𝔽 and c ≠ 0, then a × c together with a runs through all elements of the field 𝔽.

(2) If c_{1}, c_{2}, …, c_{n} ∈ 𝔽, then

∑_{a_{1},...,a_{n}∈𝔽}χ(a_{1} × c_{1} + ⋯ + a_{n} × c_{n}) = ∑_{a_{1}∈𝔽}χ(a_{1} × c_{1}) ⋯ ∑_{a_{n}∈𝔽}χ(a_{n} × c_{n}).

This proves the second assertion.

Lemma 7. Let f be a primitive polynomial over the field 𝔽 of degree n, t = ord f, a ∈ ℤ, γ ∈ V_{n}, γ_{x} = B^{x} • γ,

σ_{a,t}(δ, y) = ∑_{x=1}^{t} χ(γ • Δ_{x}) × e_{t}(a × x).

Then

σ_{a,t}(δ, y) = \{ \begin{matrix}q^{n/2} & for 1 ≤ a < t \\ 1 & for a = 0. \end{matrix}

Proof. Since t is the period of any solution of equation (1), we have

∑_{x=1}^{t} χ(γ • Δ_{x}) × e_{t}(a × x) = ∑_{x=1}^{t} χ(γ • Δ_{x+y}) × e_{t}(a(x + y))

DISTRIBUTION OF SIGNS IN A SEQUENCE OF RECTANGULAR MATRICES 335

for any integer y. Next note that γ • Δ_{x+y} = γ_{x} • Δ_{y}. Therefore

|σ_{a,t}(δ, γ)| = |∑_{x=1}^{t} χ(γ • Δ_{x+y}) × e_{t}(a × x)| = |∑_{x=1}^{t} χ(γ_{x} • Δ_{y}) × e_{t}(a × x)|.

Consequently,

t|σ_{a,t}(δ, γ)|^{2} = ∑_{y=1}^{t} ∑_{x=1}^{t} ∑_{z=1}^{t} χ((γ_{x} − γ_{z}) • Δ_{y}) × e_{t}(a × (x − z))

= ∑_{u=1}^{t} ∑_{z=1}^{t} e_{t}(a × u) ∑_{y=1}^{t} χ((γ_{u+z} − γ_{z}) • Δ_{y})

= ∑_{z=1}^{t} 1 × ∑_{y=1}^{t} χ(0) + ∑_{u=1}^{t−1} ∑_{z=1}^{t} e_{t}(a × u) × ∑_{α∈V^{∗}} χ((γ_{u+z} − γ_{z}) • α)

= t^{2} − t × ∑_{u=1}^{t−1} e_{t}(a × u) = \{ \begin{matrix}t & for a = 0 \\ t^{2} + t & for 1 ≤ a < t. \end{matrix}

Lemma 8. For any positive integer t > 12 and X we have

|∑_{u=1}^{t−1} ∑_{z=1}^{X} e_{t}(−a × z)| < t ln t − \frac{t}{2}.

Proof. [1, Ch. 3, Question 11c]. See also [3, Lemma 8.10].

Lemma 9. Let f be a primitive polynomial over the field 𝔽 of degree n, γ ∈ V_{n}, γ ≠ θ,

σ(X) = ∑_{x=1}^{X} χ(γ • Δ_{x}).

If 1 ≤ X ≤ t, then

|σ(X)| < q^{n/2} ln t.

Proof. We have

∑_{z=1}^{X} ∑_{x=1}^{t} ∑_{a=1}^{t} χ(γ • Δ_{x}) × e_{t}(a(x − z)) = ∑_{z=1}^{t} ∑_{x=1}^{t} χ(γ • Δ_{x}) × e_{t}(a(x − z))

and therefore

t ∑_{x=1}^{X} χ(γ • Δ_{x}) = X ∑_{x=1}^{t} χ(γ • Δ_{x}) + ∑_{a=1}^{t−1} ∑_{x=1}^{t} χ(γ • Δ_{x})e_{t}(a × x) × ∑_{z=1}^{X} e_{t}(−a × z),

t|σ(X)| ≤ X + q^{n/2}|∑_{a=1}^{t−1} ∑_{z=1}^{X} e_{t}(−a × z)| < X + q^{n/2}(t ln t − t).

This easily yields |σ(X)| < q^{n/2} ln t.

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS  Vol. 218  1997

Theorem 1. Let X ≤ t, 1 ≤ s < n, t > 12, 1 ≤ m < t. Suppose that δ^{(1)} = {δ_{x}^{(1)}}_{x}, …, δ^{(s)} =

{δ_{x}^{(s)}}_{x} are solutions of equation (1) which are linearly independent over the field 𝔽, T_{1X} = T_{1X}(b_{1}, …, b_{s}; δ^{(1)}, …, δ^{(s)}) and T_{2X} = T_{1X}(b_{1}, …, b_{s}; m; δ^{(1)}, …, δ^{(s)}) are the numbers of solutions in integers of the system of equations of the forms

δ_{x}^{(1)} = b_{1}, …, δ_{x}^{(s)} = b_{s}, 1 ≤ x ≤ X,

and

δ_{x}^{(1)} = δ_{x+m}^{(1)} + b_{1}, …, δ_{x}^{(s)} = δ_{x+m}^{(s)} + b_{s}, 1 ≤ x ≤ X,

respectively. Then

(1) T_{1X} = T_{1X}(b_{1}, …, b_{s}; δ^{(1)}, …, δ^{(s)}) = \frac{X}{q^{s}} + εq^{n/2} ln t, where ε ∈ ℂ and |ε| < 1;

(2) T_{2X} = T_{1X}(b_{1}, …, b_{s}; m; δ^{(1)}, …, δ^{(s)}) = \frac{X}{q^{s}} + εq^{n/2} ln t, where ε ∈ ℂ and |ε| < 1.

Proof. Each of two nonzero solutions of equation (1) is a shift of the other solution. Therefore there exist nonnegative integers m_{1}, …, m_{s} such that

δ_{x}^{(1)} = δ_{x+m_{1}}, , …, δ_{x}^{(s)} = δ_{x+m_{s}}

for all x ∈ ℤ. By virtue of Lemma 5, we have

T_{1X} = \frac{1}{q^{s}} ∑_{x=1}^{X} ∑_{c_{1},...,c_{s}∈𝔽}χ(c_{1}(δ_{x+m_{1}} − b_{1}) + ⋯ + c_{s}(δ_{x+m_{s}} − b_{s})),

and therefore

T_{1X} = \frac{1}{q^{s}} ∑_{c_{1},...,c_{s}∈𝔽}χ(−c_{1}b_{1} − ⋯ − c_{s}b_{s}) ∑_{x=1}^{X} χ(γ_{x}),

where γ_{x} = c_{1}δ_{x+m_{1}} + ⋯ + c_{s}δ_{x+m_{s}}. Using Lemma 1, we obtain

γ_{x} = Δ_{x} • (c_{1} × β_{m_{1}} + ⋯ + c_{s} × β_{m_{s}}).

By virtue of Lemma 2, the vectors β_{m_{1}}, β_{m_{2}}, …, β_{m_{s}} are linearly independent over the field 𝔽. Therefore

T_{1X} = \frac{X}{q^{s}} + \frac{1}{q^{s}}\begin{matrix}∑ & ∗ \\ c_{1},...,c_{s}∈𝔽 \end{matrix}χ(−c_{1}b_{1} − ⋯ − c_{s}b_{s}) ∑_{x=1}^{X} χ(γ_{x}),

where ^{∑∗} is the sum over all collections c_{1}, c_{2}, …, c_{s} of elements of the field 𝔽. From this and from Lemma 8 we get the first assertion of the theorem.

Next we have

T_{2X} = \frac{1}{q^{s}} ∑_{x=1}^{X} ∑_{c_{1},...,c_{s}∈𝔽}χ(c_{1}(δ_{x+m_{1}} − δ_{x+m_{1}+m} − b_{1}) + ⋯ + c_{s}(δ_{x+m_{s}} − δ_{x+m_{s}+m} − b_{s})).

By virtue of Lemmas 1 and 3, for every i, 1 ≤ i ≤ s, we have

δ_{x+m_{i}} − δ_{x+m_{i}+m} = Δ_{x} • (B^{m_{i}} • (β_{0} − β_{m})).

It follows from the hypothesis of the theorem that β_{0} − β_{m} ≠ θ, and since the primitive period of the sequence {β_{x}}_{x=−∞}^{+∞} is equal to t = q^{n} − 1, the relation β_{0} − β_{m} = β_{m^{∗}} holds true for a certain positive integer m^{∗}, 0 ≤ m^{∗} < t. Therefore

T_{2X} = \frac{1}{q^{s}} ∑_{c_{1},...,c_{s}∈𝔽}χ(−c_{1}b_{1} − ⋯ − c_{s}b_{s}) ∑_{x=1}^{X} χ(Δ_{0} • γ_{c_{1},...,c_{s}}),

where

γ_{c_{1},...,c_{s}} = c_{1}β_{m^{∗}+m_{1}} + ⋯ + c_{s}β_{m^{∗}+m_{s}} = B^{m^{∗}} • (c_{1}β_{m_{1}} + ⋯ + c_{s}β_{m_{s}}).

And since the vectors β_{m_{1}}, …, β_{m_{s}} are linearly independent over the field 𝔽 by virtue of Lemma 2, we have γ_{c_{1},...,c_{s}} = θ if and only if c_{1} = ⋯ = c_{s} = 0. Consequently,

T_{2X} = \frac{X}{q^{s}} + \frac{1}{q^{s}}\begin{matrix}∑ & ∗ \\ c_{1},...,c_{s}∈𝔽 \end{matrix}χ(−c_{1}b_{1} − ⋯ − c_{s}b_{s}) ∑_{x=1}^{X} χ(Δ_{0} • γ_{c_{1},...,c_{s}}),

where the summation in the sum ^{∑∗} is carried out over all nonzero collections of elemnts of the field 𝔽. This and Lemma 8 yield the second assertion of the theorem.

We are considering a sequence of rectangular n × k matrices which satisfies the recurrence equation of the form

C • D_{n,k}^{(x)} = D_{n,k}^{(x+1)},  x ∈ ℤ,  (4)

where C is a square n × n matrix and D_{n,k}^{(0)} is a rectangular n × k matrix. In the sequel we shall use the following notation:

C = ∥ \begin{matrix}c_{1,1} & … & c_{1,n} \\ ⋮ & ... & ⋮ \\ c_{n,1} & … & c_{n,n} \end{matrix} ∥ ,  C^{x} = ∥ \begin{matrix}c_{1,1}^{(x)} & … & c_{1,n}^{(x)} \\ ⋮ & ... & ⋮ \\ c_{n,1}^{(x)} & … & c_{n,n}^{(x)} \end{matrix} ∥ ,  D_{n,k}^{(0)} = ∥ \begin{matrix}d_{1,1} & … & d_{1,k} \\ ⋮ & ... & ⋮ \\ d_{n,1} & … & d_{n,k} \end{matrix} ∥ ,

D_{n,k}^{(x)} = ∥ \begin{matrix}d_{1,1}^{(x)} & … & d_{1,k}^{(x)} \\ ⋮ & ... & ⋮ \\ d_{n,1}^{(x)} & … & d_{n,k}^{(x)} \end{matrix} ∥ ,  Δ_{x}^{(j)} = ∥ d_{1,j}^{(x)} ; ⋮ ; d_{n,j}^{(x)} ∥ ,  Ψ_{x}^{(i)} = ∥ c_{i,1}^{(x)} … c_{i,n}^{(x)} ∥ ,

f is the characteristic polynomial of the matrix C.

Theorem 2. Let f = λ^{n} − a_{1}λ^{n−1} − ⋯ − a_{n−1}λ − a_{n}, ord f = q^{n} − 1, rang D_{n,k}^{(0)} = k. Then

(1) for any pair of integers (i, j), 1 ≤ i ≤ n, 1 ≤ j ≤ k, the sequence {d_{i,j}^{(x)}}_{x} is a nonzero solution of equation (1);

(2) for every j, 1 ≤ j ≤ k, the solutions of equation (1) of the form

{d_{1,j}^{(x)}}_{x}, …, {d_{n,j}^{(x)}}_{x}  (5)

are linearly independent over the field 𝔽;

(3) for every i, 1 ≤ i ≤ n, the solutions of equation (1) of the form

{d_{i,1}^{(x)}}_{x}, …, {d_{i,k}^{(x)}}_{x}  (6)

are linearly independent over the field 𝔽.

Proof. We have

C^{n} − a_{1}C^{n−1} − a_{2}C^{n−2} − ⋯ − a_{n−1}C − a_{n}E_{n} = □_{n,n},

and therefore

(C^{n} − a_{1}C^{n−1} − ⋯ − a_{n−1}C − a_{n}E_{n}) • D_{n,k}^{(x)}D_{n,k}^{(x+n)} − a_{1}D_{n,k}^{(x+n−1)} − ⋯ − a_{n}D_{n,k}^{(x)} = □_{n,k}.

Consequently, for any pair of positive integers (i, j), 1 ≤ i ≤ n, 1 ≤ j ≤ k, we have

d_{i,j}^{(n+x)} − a_{1}d_{i,j}^{(n−1+x)} − ⋯ − a_{n}d_{i,j}^{(x)} = 0.

Thus, the sequence {d_{i,j}^{(x)}}_{x} is a solution of equation (1). The primitive period of sequence (7) is equal

to 1 if it is zero and to t otherwise. It immediately follows from relation (4) that C • Δ_{x}^{(j)} = Δ_{x+1}^{(j)}.

Therefore C^{x} • Δ_{0}^{(j)} = Δ_{x}^{(j)}. Note that for any nonzero vector α of the space V_{n} we have

C^{x} • α = C^{y} • α

if and only if x ≡ y (mod t). It follows that the vectors of the series Δ_{0}^{(j)}, Δ_{1}^{(j)}, …, Δ_{t−1}^{(j)}, and all columns of the matrix M_{j} of the form

M_{j} = ∥ \begin{matrix}d_{1,j}^{(0)} & d_{1,j}^{(1)} & … & d_{1,j}^{(t−1)} \\ ⋮ & ⋮ & ... & ⋮ \\ d_{n,j}^{(0)} & d_{n,j}^{(1)} & … & d_{n,j}^{(t−1)} \end{matrix} ∥

are different. And since their number is equal to the number of nonzero vectors of the space V_{n}, the rows of the matrix M_{j} are linearly independent over the field 𝔽. Consequently, the solutions of (5)

are also linearly independent over the field 𝔽. In particular, the solutions {c_{1,j}^{(x)}}_{x}, {c_{2,j}^{(x)}}_{x}, …, {c_{n,j}^{(x)}}_{x}

are linearly independent over the field 𝔽. It is easy to deduce from the relation Ψ_{x}^{(i)} ∗ C = Ψ_{x+1}^{(i)} that the solutions

{c_{1,j}^{(x)}}_{x}, {c_{2,j}^{(x)}}_{x}, …, {c_{n,j}^{(x)}}_{x}  (7)

are also linearly independent over the field 𝔽. It remains to prove that the solutions of (6) are linearly independent over the field 𝔽. If this is not the fact, then there exist elements u_{1}, u − 2, …, u_{k}, not all of which are zero, such that

u_{1}d_{i,1}^{(x)} + u_{2}d_{i,2}^{(x)} + ⋯ + u_{k}d_{i,k}^{(x)} = 0

for all x ∈ ℤ. Noting that C^{x} • D_{n,k}^{(0)} = D_{n,k}^{(x)}, we obtain

c_{i,1}^{(x)}d_{1,j} + ⋯ + c_{i,n}^{(x)}d_{n,j} = d_{i,j}^{(x)}

for all x ∈ ℤ. Therefore, for every integer x, we have

u_{1}(c_{i,1}^{(x)}d_{1,1} + ⋯ + c_{i,n}^{(x)}d_{n,1}) + u_{2}(c_{i,1}^{(x)}d_{1,2} + ⋯ + c_{i,n}^{(x)}d_{n,2}) + ⋯ + u_{k}(c_{i,1}^{(x)}d_{1,k} + ⋯ + c_{i,n}^{(x)}d_{n,k})

= c_{i,1}^{(x)}(u_{1}d_{1,1} + u_{2}d_{1,2} + ⋯ + u_{k}d_{1,k}) + ⋯ + c_{i,n}^{(x)}(u_{1}d_{n,1} + u_{2}d_{n,2} + ⋯ + u_{k}d_{n,k}) = 0.

Since the solutions of (7) are linearly independent over the field 𝔽, we obtain

u_{1}d_{1,1} + u_{2}d_{1,2} + ⋯ + u_{k}d_{1,k} = 0,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
u_{1}d_{n,1} + u_{2}d_{n,2} + ⋯ + u_{k}d_{n,k} = 0,

and this is impossible.

ACKNOWLEDGMENTS

This work was supported by the Russian Foundation for Fundamental Research (project no. 96-01-00767).

REFERENCES

1. Vinogradov, I. M., Osnovy teorii chisel (Foundations of Number Theory), 9th ed., Moscow: Nauka, 1981.

2. Korobov, N. M., Distribution of Nonresidues and Primitive Roots in Recurrent Series, Dokl. Akad. Nauk SSSR, 1953, vol. 88, no. 4, pp. 603–606.

3. Lidl, R. and Niderreider, H., Finite Fields, Encycl. Math. Appl., 1983, vol. 20, Massachusets: Eddison Wesley.

4. Nechaev, V. I., Group of Nonsingular Matrices over a Finite Field and Recurrent Sequences, Dokl. Akad. Nauk SSSR, 1963, vol. 152, no. 2, pp. 275–277.

5. Nechaev, V. I., An Unimprovable Estimate of Trigonometric Sums for Recurrent Functions with Nonconstant Coefficients, Dokl. Akad. Nauk SSSR, 1964, vol. 154, no. 3, pp. 520–522.

6. Nechaev, V. I., Trigonometric Sums for Recurrent Sequences, Dokl. Akad. Nauk SSSR, 1972, vol. 206, no. 4, pp. 811–814.

7. Nechaev, V. I., Trigonometric Sums for Elements of a Finite Field, Mat. Zametki, 1972, vol. 11, no. 5, pp. 597–607.

8. Laksov, D., Linear Recurring Sequences over Finite Fields, Math. Scand., 1965, vol. 16, pp. 181–196.

9. Lidl, R. and Niderreiter, H., Introduction to Finite Fields and Their Applications, Cambridge (London), 1985.

10. Zierler, N., Linear Recurring Sequences, J. Soc. Indust. Appl. Math., 1959, vol. 7, pp. 31–48.

Translated by I. Aleksandrova