Proceedings of the Steklov Institute of Mathematics, Vol. 218, 1997, pp. 261–281. Translated from Trudy Matematicheskogo Instituta imeni V. A. Steklova, Vol. 218, 1997, pp. 266–286. Original Russian Text Copyright \begin{matrix}c \\ ◯ \end{matrix} 1997 by Mit’kin. English Translation Copyright \begin{matrix}c \\ ◯ \end{matrix} by ���� �����/Interperiodica Publishing (Russia).

On the Lower Bound of the Number of Variables for the Solvability of the Hilbert–Kamke System in 3-Adic Integers

D. A. Mit’kin

Received February, 1997

Let s, n be two natural numbers and let p be a prime number. Denote by s(n, p) the minimal natural number such that for s ≥ s(n, p) and for any integers A_{1}, …, A_{n} the system of equations

∑_{i=1}^{s} \binom{x_{i}}{j} = A_{j}, j = 1, …, n,

is solvable in integer p-adic numbers x_{1}, …, x_{s}.

Arkhipov [1] established for the first time the greatest lower and least upper bounds of s(n, 2). Also he showed that the minimal number of variables that are necessary when realizing the corresponding arithmetical conditions for the positivity of a special series of the Hilbert–Kamke problem is defined by the value of s(n, 2). Later, the exact value was also found for s(n, 2) (see [2, 3]). We note that in the mentioned estimates of the value s(n, 2), a considerable role was played by possibilities of application of induction and special integral polynomials, which take relatively few values modulo the power of a prime number. Arkhipov and Karatsuba [4] succeeded in application of analogous arguments to the Artin problem on the representation of zero by a form in local fields. They proved that for any prime p, there exists an infinite sequence of forms with integer coefficients and with the number of variables increasing as the exponential function of the degree of the form such that they do not nontrivially represent 0 in the field of p-adic numbers.

The exact estimate of s(n, 3) is important for the special series of the Hilbert–Kamke problem in prime numbers (see [5, 6]). The author suppose that by analogy with the formula for s(n, 2), the value of s(n, 3) is recursively defined: s(n, 3) = q(n), where

q(0) = 0,  q(n) = \{ \begin{matrix}2(3^{n/2} − 1) + 3q([\frac{n}{3}]) & if n is even \\ 3^{(n+1)/2} − 2 + 3q([\frac{n}{3}]) & if n is odd. \end{matrix}  (1)

As in the case of s(n, 2), the proof of both estimates s(n, 3) ≤ q(n) and s(n, 3) ≥ q(n) is expected to be complicated technically in the general case. In the present paper, we prove the inequality s(n, 3) ≥ q(n) for those n for which all positive numbers of the series

n, [\frac{n}{3}], [\frac{n}{3^{2}} ], …  (2)

are simultaneously odd or are simultaneously not divisible by 3. In the proof, we use specific integral polynomials of the even degree l which assume only two values 0 and 1 modulo 3^{l/2}. The restrictions on n are caused by the found possibilities of application of induction.

Introduce the following notation: [a] is the integral part of a; {a} is the fractional part of a; ν_{p}(a) is the largest exponent of a prime p, which divides an integer a; p^{k} ∥ a denotes p^{k} | a or p^{k+1} ∤ a;

Δ_{h}^{(0)}f(x) = f(x),  Δ_{h}f(x) = f(x + h) − f(x),  Δ_{h}^{(j+1)}f(x) = Δ_{h}(Δ_{h}^{(j)}f(x)), j = 0, 1, …;

\binom{x}{0} = 1, \binom{x}{k} = \frac{x(x − 1) ⋯ (x − k + 1)}{k!}, k = 1, 2, ….

Lemma 1. Let l ≥ 2 be an odd number and let ζ be a primitive cubic root of 1. The polynomial

f_{l}(x) = ∑_{j=1}^{l} a_{j}\binom{x}{j}, where a_{j} = −\frac{1}{3} ∑_{k=1}^{2}(ζ^{k} − 1)^{j},

is integral and satisfies the congruence

f_{l}(x) ≡ \{ \begin{matrix}0 (mod 3^{l/2}) & for an integer x if x ≡ 0 (mod 3) \\ 1 (mod 3^{l/2}) & if x ≢ 0 (mod 3). \end{matrix}

The coefficients of f_{l}(x) satisfy the conditions

3^{(l−2)/2} ∥ a_{l}, a_{j} ≡ 0 (mod 3^{(l−2)/2−[(l−j)/2]}), j = 1, …, l.

The proof see in [2, Lemma 7].

Lemma 2. Let n, l, j be natural numbers, j ≤ l ≤ n, and let α(n, j) be defined by one of the formulas

[\frac{n − j + 1}{2}] + 1  or  [\frac{n − j + 1}{3}] + 1 + ν_{3}(\frac{n!}{(j − 1)!}).  (3)

Then the inequality

α(n, j) + [\frac{l − 1}{2}] − [\frac{l − j}{2} ] ≥ [\frac{l + 1}{2}]

holds true.

Proof. If α(n, j) = [(n−j +1)/2]+1, then the inequality is obvious. Consider the second case. In the series 1, 2, …, n, there are [n/3] integers which are divisible by 3, and there are [(j − 1)/3] numbers with the same property in the series 1, 2, …, j − 1. Therefore,

ν_{3}(\frac{n!}{(j − 1)!}) = [\frac{n}{3}] − [\frac{j − 1}{3}] + ν_{3}(\frac{[n/3]!}{[(j − 1)/3]!}) ≥ [\frac{n}{3}] − [\frac{j − 1}{3}].

Now it is sufficient to show that

[\frac{n − j + 1}{3}] + [\frac{n}{3}] − [\frac{j − 1}{3}] − [\frac{l − j}{2} ] ≥ 0

for j ≤ l ≤ n. Since the left-hand side does not increase with increasing l and

[\frac{n}{3}] − [\frac{j − 1}{3}] ≥ [\frac{n − j + 1}{3}],

it is sufficient to establish the validity of the inequality 2[(n − j + 1)/3] ≥ [(n − j)/2]. Representing n−j in the form n−j = 6k +r, k, r ∈ ℤ, where k ≥ 0, 0 ≤ r ≤ 5, we transform the latter inequality into the form k + 2[(r + 1)/3] ≥ [r/2], where it can easily be verified. The lemma is proved.

Lemma 3. Let h be a real number, and let f(x) be a polynomial of degree n with real coefficients. Then the relation

Δ_{hy}f(x) = ∑_{k=1}^{n} Δ_{h}^{k}f(x)\binom{y}{k}

holds true.

The proof see in [6, Chap. 1].

Lemma 4. Let l ≥ 2 be an even number, let ζ be a primitive cubic root of 1, and let

a_{j} = −\frac{1}{3} ∑_{k=1}^{2}(ζ^{k} − 1)^{j}, j = 1, 2, ….

The following equality holds for the polynomial

f_{l}(x) = ∑_{j=1}^{l} a_{j}\binom{x}{j} :

Δ_{3}f_{l}(x) = 3^{l/2}φ_{l}(x), where φ_{l}(x) = c_{l,1}\binom{x}{l − 1} + c_{l,2}\binom{x}{l − 2}

is an integral polynomial, c_{l,2} = −3^{−l/2}a_{l+1}, and c_{l,1} = 3−l/2 + 1a_{l} ≢ 0 (mod 3).

Proof. By Lemma 3, we have

Δ_{3}f_{l}(x) = ∑_{k=1}^{3} Δ_{1}^{(k)}f_{l}(x)\binom{3}{k} = ∑_{k=1}^{3} \binom{3}{k} ∑_{j=k}^{l} a_{j}\binom{x}{j − k} = ∑_{m=0}^{l−1} \binom{x}{m} ∑_{\begin{matrix}1≤k≤3 \\ k+m≤l \end{matrix}} \binom{3}{k}a_{m+k}

= 3a_{l}\binom{x}{l − 1} + (3a_{l} + 3a_{l−1})\binom{x}{l − 2} = 3a_{l}\binom{x}{l − 1} − a_{l+1}\binom{x}{l − 2}

since

3a_{l−1} + 3a_{l} + a_{l+1} = −\frac{1}{3} ∑_{k=1}^{2}(ζ^{k} − 1)^{l−1}(3 + 3(ζ − 1) + (ζ − 1)^{2}) = 0.

Now, the assertion of the lemma follows from the relations of Lemma 1 for the coefficients a_{l} and a_{l+1} for even l, i.e.,

3^{(l−2)/2} ∥ a_{l}, a_{l+1} ≡ 0 (mod 3^{l/2}).

Lemma 5. Let n, h be two natural numbers, n ≥ 3, u = [n/3], h ≤ u, α(n, j) be defined for a natural j ≤ n by one of formulas (3), and let

β(l) = min_{j=1,...,l}(α(n, j) + [\frac{l − 1}{2}] − [\frac{l − j}{2} ]).

Then, for l = 3h, 3h − 1, 3h − 2 the inequality β(l) − [(l + 1)/2] ≥ α(u, h) holds in all cases, except for the case α(n, j) = [(n − j + 1)/2] + 1, n = 3u, h = u, l = 3u.

Proof. First assume that α(n, j) = [(n − j + 1)/2] + 1. Then it is sufficient to show that

[\frac{n − j + 1}{2}] − [\frac{l − j}{2} ] ≥ [\frac{u − h + 1}{2}] + 1.

The left-hand side of this inequality is greater than or equal to [(n − l + 1)/2]; this is greater or equal to [3(u − h)/2] + 1, except for the case n = 3u and l = 3h where [(n − l + 1)2] ≥ [3(u − h)/2]. It is easy to see that [3(u − h)/2] ≥ [(u − h + 1)/2] for h < u. The case h = u is obvious.

Consider now the case of the second definition of α(n, j). It is sufficient to show that for any j = 1, 2, …, 3h, the inequality

α(n, j) − 1 − [\frac{3h − j}{2} ] ≥ α(u, h)

holds. Since α(n, j) does not decrease when n increases, we can restrict ourselves by the proof of the last inequality with α(3u, j) instead of α(n, j), i.e., it is sufficient to establish that the following inequality holds for 1 ≤ j ≤ 3h:

[\frac{3u − j + 1}{3}] + ν_{3}(\frac{(3u)!}{(j − 1)!}) − [\frac{3h − j}{2} ] ≥ [\frac{u − h + 1}{3}] + 1 + ν_{3}(\frac{u!}{(h − 1)!}).

Here, by virtue of the relations

ν_{3}(\frac{(3u)!}{(j − 1)!}) = u − [\frac{j − 1}{3}] + ν_{3}(\frac{u!}{[(j − 1)/3]!}), [\frac{j − 1}{3}] ≤ h − 1,

it is sufficient to restrict ourselves by the proof of the inequality

[\frac{3u − j + 1}{3}] + u − [\frac{j − 1}{3}] − [\frac{3h − j}{2} ] ≥ [\frac{u − h + 1}{3}] + 1.

However, we note that it is necessary to verify this inequality only for j = 3h, 3h − 1, 3h − 2 since its left-hand side does not increase when j increases by 3. For the indicated j, the left-hand side of the last inequality is equal to 2(u − h) + 1, and obviously, 2(u − h) + 1 ≥ [(u − h + 1)/3] + 1. The lemma is proved.

Lemma 6. For integers g_{k,l}, which are defined by the equality

g_{k,l} = Δ_{3}^{(k−1)}\binom{0}{l − 1}

for natural k and l, the following relations are satisfied:

(1) g_{k,l} = 0 if l > 3k − 2,

(2) g_{k,l} = 1 if l = 3k − 2,

(3) ν_{3}(g_{k,l}) ≥ min_{r≤[(l−k)/2]}(k − 1 − r + ν_{3}(\frac{(k − 1)!}{r!(k − 1 − r)!})) if l < 3k − 2.

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS  Vol. 218  1997

Proof. By Lemma 3, we have

g_{k,l} = ∑_{1≤i_{1},...,i_{k−1}≤3} Δ_{1}^{(i_{1}+···+i_{k−1})}\binom{0}{l − 1}\binom{3}{i_{1}} ⋯ \binom{3}{i_{k−1}}

= ∑_{\begin{matrix}1≤i_{1},...,i_{k−1}≤3 \\ i_{1}+···+i_{k−1}=l−1 \end{matrix}} \binom{3}{i_{1}} ⋯ \binom{3}{i_{k−1}} = ∑_{r=0}^{k−1} \binom{k − 1}{r}3^{k−1−r} ∑_{\begin{matrix}1≤i_{1},...,i_{k−1−r}≤2 \\ i_{1}+···+i_{k−1−r}=l−1−3r \end{matrix}} 1

= ∑_{r=0,1,...,k−1} \binom{k − 1}{r}\binom{k − 1 − r}{l − k − 2r}3^{k−1−r}.

The interval of summation with respect to r is not empty if l + 1 − 2k ≤ (l − k)/2, i.e., in the case l ≤ 3k − 2; moreover, for l = 3k − 2, the variable r of summation assumes only one value r = k − 1, and g_{k,l} = 1. For l < 3k − 2 we have ν_{3}(g_{k,l}) ≥ 1; a more exact lower estimate of ν_{3}(g_{k,l}) can obviously be written as in item (3) of the lemma.

Lemma 7. Let k, l, u, and h be natural numbers, h ≤ u, l ≤ 3h, g_{k,l} = Δ_{3}^{(k−1)}\binom{0}{l−1}, and let α(n, j) be defined by one of formulas (3) for natural j and n, where j ≤ n. Then the following inequalities hold:

ν_{3}(g_{k,l}) ≥ α(u, h) if k > u

and

ν_{3}(g_{k,l}) + α(u, k) ≥ α(u, h) if h < k ≤ u.

Proof. First let α(n, j) = [(n − j + 1)/2] + 1. Since, by Lemma 6,

ν_{3}(g_{k,l}) ≥ k − 1 − [\frac{l − k}{2} ],

in order to prove the first inequality of the lemma, it is sufficient to verify that for k > 0 the inequality

k − 1 − [\frac{l − k}{2} ] ≥ [\frac{u − h + 1}{2}] + 1

holds true. In turn, it is sufficient for this that

u − [\frac{3h − u − 1}{2}] ≥ [\frac{u − h + 1}{2}] + 1;

this can easily be verified. To prove the second inequality, it is sufficient to verify that

k − 1 − [\frac{l − k}{2} ] + [\frac{u − k + 1}{2}] ≥ [\frac{u − h + 1}{2}]

for h < k ≤ u and l ≤ 3h. In fact, here the left-hand side is greater than or equal to

k − 1 − [\frac{3h − k}{2} ] + [\frac{u − k + 1}{2}] ≥ k − 1 + [\frac{u − 3h + 1}{2}] ≥ [\frac{u − h + 1}{2}].

Consider now the case where α(n, j) is defined by the second formula. Apply the lower estimate of ν_{3}(g_{k,l}) from item (3) of Lemma 6. In both inequalities of the lemma, it is sufficient to use the value

G(k, l, r) = k − 1 − r + ν_{3}(\frac{(k − 1)!}{r!(k − 1 − r)!})

for an arbitrary integer r with the condition 0 ≤ r ≤ [(l − k)/2] instead of ν_{3}(g_{k,l}). Since

ν_{3}(m!) = [\frac{m}{3}] + [\frac{m}{3^{2}} ] + ⋯ ≤ [\frac{m − 1}{2}]

for a natural m, we have

m − ν_{3}(m!) ≥ m − [\frac{m − 1}{2}] = [\frac{m}{2}] + 1,

this implies that

G(k, l, r) ≥ [\frac{k − 1 − r}{2} ] + 1 + ν_{3}(\frac{(k − 1)!}{r!}).

Let k > u. Then it is sufficient to show that

[\frac{k − 1 − r}{2} ] + ν_{3}(\frac{(k − 1)!}{r!}) ≥ [\frac{u − h + 1}{3}] + ν_{3}(\frac{u!}{(h − 1)!}).

This inequality holds since

k − 1 ≥ u, r ≤ [\frac{3h − u − 1}{2}] ≤ [\frac{2h − 1}{2}] = h − 1,

and then k − 1 − r ≥ u − h + 1, while (k − 1)!/r! is divisible by u!/(h − 1)!.

In the case h < k ≤ u, it is sufficient to show that

[\frac{k − 1 − r}{2} ] + ν_{3}(\frac{(k − 1)!}{r!}) + [\frac{u − k + 1}{3}] + ν_{3}(\frac{u!}{(k − 1)!}) ≥ [\frac{u − h + 1}{3}] + ν_{3}(\frac{u!}{(h − 1)!}).

Since r ≤ [(3h − k)/2] ≤ h − 1, it is sufficient to verify the inequality

[\frac{k − 1 − r}{2} ] + [\frac{u − k + 1}{3}] ≥ [\frac{u − h + 1}{3}].

The last inequality is obviously true if k ≥ h + 2, or if k = h + 1, r < h − 1. In the case k = h + 1, r = h − 1, we return to the initial formula for G(k, l, r). It is sufficient to verify the inequality

1 + ν_{3}(h) + [\frac{u − h}{3}] + ν_{3}(\frac{u!}{h!}) ≥ [\frac{u − h + 1}{3}] + ν_{3}(\frac{u!}{(h − 1)!}),

this is easily verified. The lemma is proved.

Lemma 8. Let l, u, h, and k be natural numbers, g_{u,l} = Δ_{3}^{(u−1)}\binom{0}{l−1}, and let α(n, j) be defined by the formula [(n − j + 1)/2] + 1 for natural j and n, where j ≤ n. Then the following inequalities hold:

(1) ν_{3}(g_{u,l−2}) ≥ α(u, h) if l ≤ 3h, h ≤ u − 1,

(2) ν_{3}(g_{u,l}) ≥ α(u, h) if l ≤ 3h, h ≤ u − 2,

(3) ν_{3}(g_{k,l} + 1 ≥ α(u, h) if l ≤ 3h, h ≤ u − 2, k ≥ u − 1.

Proof. By Lemma 6, for ν_{3}(g_{u,l−2}), we have

ν_{3}(g_{u,l−2}) ≥ u − 1 − [\frac{l − 2 − u}{2}] ≥ u − 1 − [\frac{3h − 2 − u}{2}] = u − h − [\frac{h − u}{2}]

for l ≤ 3h; this implies the inequality

ν_{3}(g_{u,l−2}) ≥ [\frac{u − h + 1}{2}] + 1 if h ≤ u − 1.

Similarly,

ν_{3}(g_{u,l}) ≥ u − 1 − [\frac{l − u}{2}] ≥ u − 1 − [\frac{3h − u}{2}] = u − 1 − h − [\frac{h − u}{2}]

for l ≤ 3h; this implies that

ν_{3}(g_{u,l}) ≥ [\frac{u − h + 1}{2}] + 1 if h ≤ u − 2.

Finally, for l ≤ 3h and k ≥ u − 1, we obtain

ν_{3}(g_{k,l}) ≥ k − 1 − [\frac{l − k}{2} ] ≥ u − 2 − [\frac{3h − u + 1}{2}] = u − 2 − h − [\frac{h − u + 1}{2}];

this is not less than [(u − h + 1)/2] if h ≤ u − 2. The lemma is proved.

Lemma 9. Let ζ be a primitive cubic root of 1. The following formulas hold for the numbers a_{j}, j = 1, 2, …, defined by the equality

a_{j} = −\frac{1}{3} ∑_{k=1}^{2}(ζ^{k} − 1)^{j} :

a_{j+2} = −3(a_{j+1} + a_{j}),  (4)
a_{j} = 3^{[(j−1)/2]}μ_{j},  (5)

where μ_{1} = 1, μ_{2} = −1, μ_{3} = 0, μ_{4} = 1, μ_{5} = −1, μ_{6} = 2, and μ_{6m+r} = (−1)^{m}μ_{r} for r = 1, …, 6, m = 1, 2, ….

Proof. Since ζ^{2} + ζ + 1 = 0, relation (4) follows from the equality 3 + 3(ζ^{k} − 1) + (ζ^{k} − 1)^{2} = 0, k = 1, 2. By induction on j, we obtain relation (5).

Theorem. Let s and n be natural numbers, with n belonging to one of the types of numbers (A) or (B) depending on the fact that all integers of series (2) are simultaneously odd or are simultaneously not divisible by 3. Let α(n, j) be defined by the formula

[\frac{n − j + 1}{3}] + 1 + ν_{3}(\frac{n!}{(j − 1)!})

for j = 1, …, n, if n is of type (A), and by the formula

[\frac{n − j + 1}{2}] + 1

if n of type (B). Let further the integer δ assume not more than two values modulo 3,

δ_{j} = \{ \begin{matrix}δ & if j = n and n is an odd number of type (B) \\ 3δ & if j = n − 1 and n is an even number of type (B) \\ 0 & in other cases. \end{matrix}

Then there exist integers A_{1}, …, A_{n} such that the condition s ≥ q(n) is necessary for the solvability of the system of congruences of degree n

∑_{i=1}^{s} \binom{x_{i}}{j} ≡ A_{j} + δ_{j} (mod 3^{α(n,j)}),  j = 1, …, n,  (6)

in integers x_{1}, …, x_{s} independently of δ, where the function q(n) is recursively defined as in (1).

Proof. We apply the induction on n. For n = 1, we have q(1) = 1 and α(1, 1) = 1. Without loss of generality, we assume that δ can take the values which are congruent only to 0 or 1 modulo 3. It is sufficient to choose A_{1} = 1 since A_{1} + δ ≡ 0 (mod 3), and hence, the condition s ≥ 1 is necessary.

The number n = 2 is of type (B), and α(2, 1) = 1, α(2, 2) = 2, and q(2) = 4. It is sufficient to restrict ourselves by the consideration of the system of congruences

∑_{i=1}^{s} x_{i}^{2} ≡ 2A_{2} + A_{1} (mod 3),

∑_{i=1}^{s}((x_{i} − 1)^{2} − 1) ≡ 2A_{2} − A_{1} (mod 3)

instead of system (6). Here, we choose A_{1} = 0, A_{2} = 2. If k_{r} is the number of x_{i} with the condition x_{i} ≡ r (mod 3), r = 0, 1, 2, then it follows from the last congruences that k_{1} + k_{2} ≡ 1 (mod 3), −k_{1} ≡ 1 (mod 3); this implies k_{1} ≡ k_{2} ≡ 2 (mod 3) and s ≥ k_{1} + k_{2} ≥ 4 = q(2). Thus, the assertion of the theorem is proved for n = 1, 2.

Let n ≥ 3 and let the assertion of the theorem be true for the system of congruences of degree < n. We prove the assertion for n. Let A_{1}, …, A_{n} be certain integers and let δ, s, x_{1}, …, x_{s} be integers which satisfy congruences (6) under the conditions of the theorem. Then the equalities

∑_{i=1}^{s} \binom{x_{i}}{j} = A_{j} + δ_{j} + 3^{α(n,j)}M_{j},  j = 1, …, n,  (7)

hold for certain integers M_{1}, …, M_{n}. Let f_{l}(x), l = 1, 2, …, be polynomials defined in Lemma 1. We set

F_{l}(x) = \{ \begin{matrix}f_{l}(x) & if l is even \\ Δ_{1}f_{l+1}(x) − f_{l+1}(1) & if l is odd. \end{matrix}

We express the polynomials F_{l}(x) in terms of the basic integer-valued polynomials \binom{x}{j}:

F_{l}(x) = ∑_{j=1}^{l} a_{l,j}\binom{x}{j}, a_{l,j} ∈ ℤ.

Multiplying the jth equality in (7) by a_{l,j} and summing the obtained equalities over j varying from 1 to l for each l = 1, …, n, we obtain the system of equalities

∑_{i=1}^{s} F_{l}(x_{i}) = B_{l} + Ω_{l} + 3^{β(l)}C_{l},  l = 1, …, n,  (8)

where

B_{l} = ∑_{j=1}^{l} a_{l,j}A_{j},  Ω_{l} = ∑_{j=1}^{l} a_{l,j}δ_{j},  3^{β(l)}C_{l} = ∑_{j=1}^{l} 3^{α(n,j)}a_{l,j}M_{j},

and β(l) is the exponent of the highest degree of 3 which divides all the numbers 3^{α(n,j)}a_{l,j} for j = 1, …, l. By the definition of the polynomials F_{l}(x), we have

a_{l,j} = \{ \begin{matrix}a_{j} & if l ≡ 0 (mod 2) \\ a_{j+1} & if l ≡ 1 (mod 2). \end{matrix}  (9)

for j = 1, …, l. Hence, by Lemma 1,

a_{l,j} ≡ 0 (mod 3^{[(l−1)/2]−[(l−j)/2]}),  3^{[(l−1)/2]} ∥ a_{l,l},  (10)

and

β(l) ≥ min_{j=1,...,l}(α(n, j) + [\frac{l − 1}{2}] − [\frac{l − j}{2} ]).

Let us impose the first conditions on the choice of the numbers A_{1}, …, A_{n}, assuming that

B_{l} = \{ \begin{matrix}λ_{1} + 3^{[(l+1)/2]}t_{l} & for an odd l \\ λ_{2} + 3^{[(l+1)/2]}t_{l} & for an even l. \end{matrix}

By induction, with the help of relations (9) and (10), it is easy to verify that 3-integers A_{1}, …, A_{n} are uniquely determined from the equations

∑_{j=1}^{l} a_{l,j}A_{j} = B_{l}, l = 1, …, n,

by any integers λ_{1}, λ_{2}, and t_{1}, …, t_{n}. The fact that the numbers A_{1}, …, A_{n} occur to be 3-integers, but not integers, is not essential for congruences. Choose λ_{1}, λ_{2}. To this end, we pass to congruences modulo 3^{[(l+1)/2]} in equalities (8) for l = n, n − 1. By Lemma 2, β(l) ≥ [(l + 1)/2], and therefore, we obtain the congruences

∑_{i=1}^{s} F_{l}(x_{i}) ≡ B_{l} + ∑_{j=n−1}^{l} a_{l,j}δ_{j} (mod 3^{[(l+1)/2]}),  l = n, n − 1.  (11)

The polynomials F_{l}(x) defined in terms of f_{l}(x) have the following properties for integral x by virtue of Lemma 1:

F_{l}(x) ≡ \{ \begin{matrix}0 (mod 3^{l/2}) & if x ≡ 0 (mod 3) \\ 1 (mod 3^{l/2}) & if x ≢ 0 (mod 3) \end{matrix}  for even l,

F_{l}(x) ≡ \{ \begin{matrix}0 (mod 3^{(l+1)/2}) & if x ≡ 0 (mod 3) \\ −1 (mod 3^{(l+1)/2}) & if x ≡ 1 (mod 3) \\ −2 (mod 3^{(l+1)/2}) & if x ≡ 2 (mod 3) \end{matrix}  for odd l.

Denote by s_{0}, s_{1}, and s_{2} the numbers of x_{i} which are congruent to 0, 1, and 2 modulo 3, respectively. Then relation (11) implies the congruences

s_{1} + s_{2} ≡ λ_{2} + a_{n,n−1}3δ (mod 3^{n/2}),
−s_{1} − 2s_{2} ≡ λ_{1} + a_{n,n−1}3δ (mod 3^{n/2})

for even n (having only type (B)), and the congruences

s_{1} + s_{2} ≡ λ_{2} (mod 3^{(n−1)/2}),
−s_{1} − 2s_{2} ≡ λ_{1} + a_{n,n}δ_{n} (mod 3^{(n+1)/2})

for odd n. We choose

λ_{2} = 2(q([\frac{n}{3}]) − 1), λ_{1} = \{ \begin{matrix}−3(q([\frac{n}{3}]) − 1) & for even n \\ −3(q([\frac{n}{3}]) − 1) − 3^{(n−1)/2}χ & for odd n, \end{matrix}

where χ will be chosen later.

By Lemma 1, a_{j} ≡ 0 (mod 3^{[(j−1)/2]}), and therefore, we can define μ_{j} ∈ ℤ by the equality a_{j} = 3^{[(j−1)/2]}μ_{j}. By the definition of the polynomial F_{n}(x), we have a_{n,n−1} = a_{n−1}, a_{n−1,n−1} = a_{n}, and a_{n} ≡ a_{n−1} ≡ 0 (mod 3^{n/2−1}) for even n. For odd n, we have a_{n,n} = a_{n+1} ≡ 0 (mod 3^{(n−1)/2}). Hence the congruences

s_{1} ≡ s_{2} ≡ q([\frac{n}{3}]) − 1 (mod 3^{[n/2]})

hold for even n and for odd n. Represent s_{1}, s_{2} in the form

s_{r} = q([\frac{n}{3}]) − 1 + 3^{[n/2]}d_{r}, d_{r} ∈ ℤ, r = 1, 2.

ON THE LOWER BOUND OF THE NUMBER OF VARIABLES 271

In the case of odd n, we have the additional congruence

d_{1} + 2d_{2} ≡ χ − μ_{n+1}δ_{n} (mod 3).

Since δ_{n} can assume not more than two values modulo 3, χ can be chosen so that

d_{1} + 2d_{2} ≢ 0 (mod 3).  (12)

Further, we transform equalities (8) into the form which is convenient for the choice of the numbers t_{1}, …, t_{n}. Rewrite equalities (8) into three progressions r + 3x_{i,r}, (r = 0, 1, 2), dividing the summation with respect to the numbers x_{i}:

∑_{r=0}^{2} ∑_{i=1}^{s_{r}} F_{l}(r + 3x_{i,r}) = B_{l} + Ω_{l} + 3^{β(l)}C_{l}, l = 1, …, n.

Using the finite-difference operator we rewrite this system of equalities

∑_{r=0}^{2} ∑_{i=1}^{s_{r}} Δ_{3x_{i,r}}F_{l}(r) = B_{l} + Ω_{l} − ∑_{r=0}^{2} F_{l}(r) + 3^{β(l)}C_{l}, l = 1, …, n.

Replacing Δ_{3x}F_{l}(r) here by the expression

∑_{k=1}^{l} Δ_{3}^{(k)}F_{l}(r)\binom{x}{k},

which is equal to it by Lemma 3, we obtain the equalities

∑_{r=0}^{2} ∑_{k=1}^{l} Δ_{3}^{(k)}F_{l}(r) ∑_{i=1}^{s_{r}} \binom{x_{i,r}}{k} = B_{l} + Ω_{l} − ∑_{r=0}^{2} F_{l}(r) + 3^{β(l)}C_{l},  l = 1, …, n.  (13)

It follows from the definition of the polynomials F_{l}(x) and from Lemma 4 that

Δ_{3}F_{l}(x) = 3^{[(l+1)/2]}ψ_{l}(x),

where

ψ_{l}(x) = c_{l,1}\binom{x}{l − 1} + c_{l,2}\binom{x}{l − 2}, c_{l,1}, c_{l,2} ∈ ℤ, c_{l,1} ≢ 0 (mod 3).

Denoting

X_{k,r} = ∑_{i=1}^{s_{r}} \binom{x_{i,r}}{k},

we rewrite now relations (13) in the form

∑_{r=0}^{2} ∑_{k=1}^{l} Δ_{3}^{(k−1)}ψ_{l}(r)X_{k,r} = 3^{−[(l+1)/2]}(B_{l} + Ω_{l} − ∑_{r=0}^{2} F_{l}(r) + 3^{β(l)}C_{l}),  l = 1, …, n. (14)
PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS  Vol. 218  1997

Let us simplify the right-hand side of (14). Using the notation introduced above a_{j} = 3^{[(j−1)/2]}μ_{j}, where μ_{j} ∈ ℤ, we write Ω_{l} in the form Ω_{l} = 3^{[n/2]}ω_{l}, where

ω_{l} = \{ \begin{matrix}μ_{n−1}δ & for even n and l = n \\ μ_{n}δ & for even n and l = n − 1 \\ μ_{n+1}δ_{n} & for odd n. \end{matrix}

Suppose that l is even. Then F_{l}(x) = f_{l}(x), and hence, by Lemma 1,

F_{l}(0) = 0, F_{l}(1) = a_{1} = −\frac{1}{3} ∑_{k=1}^{2}(ζ^{k} − 1) = 1,

F_{l}(2) = a_{2} + 2a_{1}, a_{2} = −\frac{1}{3} ∑_{k=1}^{2}(ζ^{k} − 1)^{2} = 1.

Whence, using the expressions for B_{l}, s_{1}, and s_{2}, we obtain

3^{−[(l+1)/2]}(B_{l} + Ω_{l} − ∑_{r=0}^{2} F_{l}(r)) = t_{l} − 3^{−[n/2]−[(l+1)/2]}(d_{1} + d_{2} − ω_{l})

for even l. If l is odd, then F_{l}(x) = Δ_{1}f_{l+1}(x) − f_{l+1}(1), and hence, by Lemma 1, F_{l}(0) = 0, F_{l}(1) = f_{l+1}(2) − 2f_{l+1}(1) = −1, F_{l}(2) = f_{l+1}(3) − 2f_{l+1}(2) − f_{l+1}(1) = f_{l+1}(3) − 2. Since

a_{3} = −\frac{1}{3} ∑_{j=1}^{2}(ζ^{j} − 1)^{3} = 0,

we have f_{l+1}(3) = 3a_{2} + 3a_{1} = 0, and therefore, F_{l}(2) = −2. Whence we have

3^{−[(l+1)/2]}(B_{l} + Ω_{l} − ∑_{r=0}^{2} F_{l}(r)) = t_{l} + 3^{[n/2]−[(l+1)/2]}(d_{1} + 2d_{2} − 2χ\{\frac{n}{2}\} + ω_{l})

for odd l.

Let us introduce some new notation. Set

g_{k,l} = Δ_{3}^{(k−1)}\binom{0}{l − 1}.

Then, by Lemma 3, we have

Δ_{3}^{(k−1)}\binom{r}{l − 1} = Δ_{3}^{(k−1)}\binom{0}{l − 1} + Δ_{r} ∘ Δ_{3}^{(k−1)}\binom{0}{l − 1}

= g_{k,l} + \binom{r}{1}g_{k,l−1} + \binom{r}{2}g_{k,l−2} = ∑_{γ=0}^{2} \binom{r}{γ}g_{k,l−γ}

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS  Vol. 218  1997

for r = 0, 1, 2. Setting

Y_{k,γ} = ∑_{γ=0}^{2} \binom{r}{γ}X_{k,r},

D_{l,k,γ} = c_{l,1}g_{k,l−γ} + c_{l,2}g_{k,l−γ−1},  (15)

K_{l}(d_{1}, d_{2}) = \{ \begin{matrix}−3^{[n/2]−[(l+1)/2]}(d_{1} + d_{2} − ω_{l}) & if l ≡ 0 (mod 2) \\ 3^{[n/2]−[(l+1)/2]}(d_{1} + 2d_{2} − 2χ\{\frac{n}{2}\} + ω_{l}) & if l ≡ 1 (mod 2), \end{matrix}

and restricting ourselves by only 3u inequalities, where u = [n/3], in (14), we obtain the system

∑_{γ=0}^{2} ∑_{k=1}^{l} D_{l,k,γ}Y_{k,γ} = t_{l} + K_{l}(d_{1}, d_{2}) + 3^{β(l)−[(l+1)/2]}C_{l},  l = 1, …, 3u.  (16)

We shall consider this system as a linear one with respect to the variables Y_{k,γ}, k = 1, …, u, γ = 0, 1, 2. Write the left-hand sides of equations (16) for l = 3h, 3h − 1, 3h − 2 modulo 3. By relation (15) and Lemma 6, these are of the form

c_{3h,1}Y_{h,2} + c_{3h,2}Y_{h,1},  c_{3h−1,1}Y_{h,1} + c_{3h−1,2}Y_{h,0},  c_{3h−2,1}Y_{h,0} + c_{3h−2,2}Y_{h−1,2},

where c_{l,1} ≢ 0 (mod 3). Hence the matrix of coefficients has the triangular form modulo 3 with respect to the variables Y_{k,γ}, k = 1, …, u, γ = 0, 1, 2, and we can solve this system with respect to the chosen variables in 3-integer numbers. This solution has the following form:

Y_{k,γ} = T_{k,γ} + L_{k,γ} + Q_{k,γ}, k = 1, …, u, γ = 0, 1, 2,

where T_{k,γ} are defined by the system

∑_{γ=0}^{2} ∑_{k=1}^{u} D_{l,k,γ}T_{k,γ} = t_{l}, l = 1, …, 3u,

L_{k,γ} = L_{k,γ}(d_{1}, d_{2}) are defined by the system

∑_{γ=0}^{2} ∑_{k=1}^{u} D_{l,k,γ}L_{k,γ} = K_{l}(d_{1}, d_{2}),  l = 1, …, 3u,  (17)

and Q_{k,γ} are defined by the system

∑_{γ=0}^{2} ∑_{k=1}^{u} D_{l,k,γ}Q_{k,γ} = 3^{β(l)−[(l+1)/2]}C_{l} − ∑_{γ=0}^{2} ∑_{u<k≤l} D_{l,k,γ}Y_{k,γ}, l = 1, …, 3u.

By Lemma 5, relation (15), and by the first inequality of Lemma 7, the numbers Q_{k,γ} satisfy the congruences

∑_{γ=0}^{2} ∑_{k=1}^{u} D_{l,k,γ}Q_{k,γ} ≡ 0 (mod 3^{α(u,h)}), l = 3h, 3h − 1, 3h − 2,

for each h = 1, …, u. The values α(u, h) do not decrease when h decreases, and therefore, it follows from the presented system of congruences that the congruence

Q_{k,γ} ≡ 0 (mod 3^{α(u,u)})

holds for all Q_{k,γ}, and then, by induction, we obtain with the help of the second inequality of Lemma 7 that

Q_{k,γ} ≡ 0 (mod 3^{α(u,h)})

for k ≤ h. Thus,

Q_{k,γ} ≡ 0 (mod 3^{α(u,k)}),  k = 1, …, u, γ = 0, 1, 2.  (18)

Since the choice of the numbers t_{1}, …, t_{n} is at our disposal, the numbers T_{k,γ} can also be chosen in an arbitrary way for now. We obtain from (18) the congruences

Y_{k,γ} ≡ T_{k,γ} + L_{k,γ}(d_{1}, d_{2}) (mod 3^{α(u,k)}),  k = 1, …, u, γ = 0, 1, 2,  (19)

where the numbers T_{k,γ} can be chosen as arbitrary integers.

1. Let n be an odd number of type (A). In this case, δ_{n} = 0 and ω_{l} = 0, and hence, the functions L_{k,γ}(d_{1}, d_{2}) are fixed. Then we can complete the step of induction without of additional information on the functions L_{k,γ}(d_{1}, d_{2}). We have from relations (19) and the definition of T_{k,γ} that

X_{k,r} = ∑_{i=1}^{s_{r}} \binom{x_{i,r}}{k} ≡ T_{k}^{(r)} + L_{k}^{(r)}(d_{1}, d_{2}) (mod 3^{α(u,k)}),  k = 1, …, u, r = 0, 1, 2,  (20)

where T_{k}^{(r)} can be chosen as arbitrary integers, and L_{k}^{(r)}(d_{1}, d_{2}) and L_{k,γ}(d_{1}, d_{2}) are fixed. It follows from the definition of the type that the number u = [n/3] ≥ 1 belongs to the same type as the number n. Therefore, by the inductive assumption for u, we choose the numbers T_{k}^{(2)} in such a way that s_{2} ≥ q(u) is necessary for the solvability of the system of congruences

∑_{i=1}^{s_{2}} \binom{x_{i,2}}{k} ≡ T_{k}^{(2)} + L_{k}^{(2)}(1, 0) (mod 3^{α(u,k)}), k = 1, …, u.

We choose the numbers T_{k}^{(1)} in such a way that s_{1} ≥ q(u) is necessary for the solvability of the system of congruences

∑_{i=1}^{s_{1}} \binom{x_{i,1}}{k} ≡ T_{k}^{(1)} + L_{k}^{(1)}(0, 2) (mod 3^{α(u,k)}), k = 1, …, u.

Finally, we choose the numbers T_{k}^{(0)} in such a way that s_{0} ≥ q(u) is necessary for the solvability of the system of congruences

∑_{i=1}^{s_{0}} \binom{x_{i,0}}{k} ≡ T_{k}^{(0)} + L_{k}^{(0)}(2, 1) (mod 3^{α(u,k)}), k = 1, …, u.

Let us return to system (20) with the chosen T_{k}^{(r)}. Since δ_{n} = 0 and d_{1} + 2d_{2} ≡ 1 (mod 3), there are the following possibilities in view of relation (12): (d_{1}, d_{2}) is equal to (1, 0), (0, 2), (2, 1), or d_{1} + d_{2} ≥ 4. In the case d_{1} + d_{2} ≥ 4, it follows that

s = s_{0} + s_{1} + s + 2 = 2(q(u) − 1) + 3^{[n/2]}(d_{1} + d_{2}) ≥ q(n).

The conditions of the choice of T_{k}^{(2)} imply that (d_{1}, d_{2}) ≠ (1, 0), and those of the choice of T_{k}^{(1)} imply that (d_{1}, d_{2}) ≠ (0, 2). Then (d_{1}, d_{2}) = (2, 1), and it follows from the choice of T_{k}^{(0)} that s_{0} ≥ q(u). As a result, we have

s ≥ 3q(u) − 2 + 3 × 3^{[n/2]} = q(n).

Let n be of type (B). For such n α(n, j) was defined as

[\frac{n − j + 1}{2}] + 1.

The following two cases are possible: n = 3u + 2 or n = 3u + 1, with u belonging to type (B). 2. Let n = 3u + 2. Then n and u are of the same parity. In the case of even n, we have

[\frac{n}{2}] − [\frac{l + 1}{2}] ≥ [\frac{3u}{2}] + 1 − [\frac{3h + 1}{2}] ≥ [\frac{u − h + 1}{2}] + 1 = α(u, h),

K_{l} ≡ 0 (mod 3^{α(u,h)}),

for l = 3h, 3h − 1, 3h − 2, h = 1, …, u, and hence, the congruences as those for Q_{k,γ} hold for the numbers L_{k,γ}:

L_{k,γ} ≡ 0 (mod 3^{α(u,k)}), k = 1, …, u, r = 0, 1, 2,

this implies Y_{k,γ} ≡ T_{k,γ} (mod 3^{α(u,k)}), k = 1, …, u, r = 0, 1, 2, where the numbers T_{k,γ} can be chosen as arbitrary integers. By the definition of Y_{k,γ}, we obtain the congruences

X_{k,r} = ∑_{i=1}^{s_{r}} \binom{x_{i,r}}{k} ≡ T_{k}^{(r)} (mod 3^{α(u,k)}), k = 1, …, u, r = 0, 1, 2,

where T_{k}^{(r)} can be chosen as arbitrary integers. On the basis of the inductior assumption, for each r = 0, 1, 2, we choose the numbers T_{k}^{(r)} in such a way that s_{r} ≥ q(u) is necessary for the solvability of the system of congruences

∑_{i=1}^{s_{r}} \binom{x_{i,r}}{k} ≡ T_{k}^{(r)} (mod 3^{α(u,k)}), k = 1, …, u.

As a result of this choice we have d_{1} ≥ 1, d_{2} ≥ 1, and

s = s_{0} + s_{1} + s_{2} = s_{0} + 2(q(u) − 1) + 3^{n/2}(d_{1} + d_{2}) ≥ q(n).

3. The inequality

[\frac{n}{2}] − [\frac{l + 1}{2}] ≥ [\frac{u − h + 1}{2}] + 1 = α(u, h)

276 MIT’KIN

holds for odd n = 3u + 2, in all the cases where l = 3h, 3h − 1, 3h − 2 (h = 1, …, u), except for the case where l = 3h and h = u. Hence K_{l}(d_{1}, d_{2}) ≡ 0 (mod 3^{α(u,h)}) for l = 3h, 3h − 1, 3h − 2, h = 1, …, u, except for l = 3h and h = u where

K_{l}(d_{1}, d_{2}) ≡ d_{1} + 2d_{2} − χ (mod 3).

According to system (17), we have the following system of congruences for the numbers L_{k,γ}:

∑_{γ=0}^{2} ∑_{k=1}^{u} D_{3u,k,γ}L_{k,γ} ≡ d_{1} + 2d_{2} − χ (mod 3),

∑_{γ=0}^{2} ∑_{k=1}^{u} D_{l,k,γ}L_{k,γ} ≡ 0 (mod 3^{α(u,[(l+2)/3])}), l = 1, …, 3u − 1,

by virtue of equality (15), where c_{l,1} ≢ 0 (mod 3), Lemma 7, and the first item of Lemma 8, this implies analogously to the congruences for the numbers Q_{k,γ} the congruences L_{k,γ} ≡ 0 (mod 3^{α(u,k)}) for all k = 1, …, u, r = 0, 1, 2, except for the number L_{u,2}, for which by the congruence (c_{3u,1})^{2} ≡ 1 (mod 3), we obtain the congruence

L_{u,2} ≡ c_{3u,1}(d_{1} + 2d_{2} − χ) (mod 3).

By the definition of the numbers Y_{k,γ} and L_{k,γ}, we obtain from this that

X_{u,r} = ∑_{i=1}^{s_{r}} \binom{x_{i,r}}{u} ≡ T_{u}^{(r)} + c_{3u,1}(d_{1} + 2d_{2} − χ) (mod 3), r = 0, 1, 2,

X_{k,r} = ∑_{i=1}^{s_{r}} \binom{x_{i,r}}{k} ≡ T_{k}^{(r)} (mod 3^{α(u,k)}), k = 1, …, u − 1, r = 0, 1, 2,

where T_{k}^{(r)}, k = 1, …, u, r = 0, 1, 2, can be chosen as arbitrary integers. Since, by relation (12), d_{1} +2d_{2} can assume not more than two values modulo 3, we have that by the inductive assumption, the numbers T_{k}^{(r)} can be chosen so that the inequalities s_{r} ≥ q(u), r = 0, 1, 2, hold. Then, however, d_{1} ≥ 1 and d_{2} ≥ 1. According to relation (12), (d_{1}, d_{2}) can assume the values (0, 1), (1, 0), (0, 2), (2, 0), or d_{1} + d_{2} ≥ 3. Hence, d_{1} + d_{2} ≥ 3 and

s = s_{0} + 2(q(u) − 1) + 3^{[n/2]}(d_{1} + d_{2}) ≥ q(n).

4. Let now n = 3u + 1. First, we consider the case of even n. Then u is odd and the inequality

[\frac{n}{2}] − [\frac{l + 1}{2}] ≥ [\frac{u − h + 1}{2}] + 1 = α(u, h)

holds in all the cases where l = 3h, 3h − 1, 3h − 2, (h = 1, …, u), except for the case l = 3h, h = u. Therefore, K_{l}(d_{1}, d_{2}) ≡ 0 (mod 3^{α(u,h)}) for l = 3h, 3h − 1, 3h − 2, h = 1, …, u, except for the case l = 3h, h = u where

K_{l}(d_{1}, d_{2}) ≡ d_{1} + 2d_{2} + μ_{n}δ (mod 3).
PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS  Vol. 218  1997

According to system (17), we have the following system of congruences for the numbers L_{k,γ}:

∑_{γ=0}^{2} ∑_{k=1}^{u} D_{3u,k,γ}L_{k,γ} ≡ d_{1} + 2d_{2} + μ_{n}δ (mod 3),

∑_{γ=0}^{2} ∑_{k=1}^{u} D_{l,k,γ}L_{k,γ} ≡ 0 (mod 3^{α(u,[(l+2)/3])}), l = 1, …, 3u − 1,

by virtue of equality (15), where c_{l,1} ≢ 0 (mod 3), Lemma 7, and the first item of Lemma 8, this implies analogously to the congruences of the numbers Q_{k,γ} the congruences L_{k,γ} ≡ 0 (mod 3^{α(u,k)}) for all k = 1, …, u, r = 0, 1, 2, except for the number L_{u,2} for which, by the congruence (c_{3u,1})^{2} ≡ 1 (mod 3), we obtain the congruence

L_{u,2} ≡ c_{3u,1}(d_{1} + 2d_{2} + μ_{n}δ) (mod 3).

Since δ can assume not more than two values modulo 3, we can represent μ_{n}δ in the form μ_{n}δ = η+ρ, where ρ is fixed and η can assume only the values 0 and 1 modulo 3. By the definitions of the numbers Y_{k,γ} and L_{k,γ}, we obtain from this that

\begin{matrix}X_{u,r} = ∑_{i=1}^{s_{r}} \binom{x_{i,r}}{u} ≡ T_{u}^{(r)} + V (d_{1} + 2d_{2} + η) (mod 3),  r = 0, 1, 2, \\ X_{k,r} = ∑_{i=1}^{s_{r}} \binom{x_{i,r}}{k} ≡ T_{k}^{(r)} (mod 3^{α(u,k)}),  k = 1, …, u − 1, r = 0, 1, 2, \end{matrix}  (21)

where V (m) = c_{3u,1}m and the numbers T_{k}^{(r)} (k = 1, …, u, r = 0, 1, 2) can be chosen as arbitrary

integers. By the inductive assumption for u, we choose the number T_{k}^{(2)} so that s_{2} ≥ q(u) is necessary for the solvability of the system of congruences

∑_{i=1}^{s_{2}} \binom{x_{i,2}}{u} ≡ T_{u}^{(2)} + σ_{2} (mod 3),

∑_{i=1}^{s_{2}} \binom{x_{i,2}}{k} ≡ T_{k}^{(2)} (mod 3^{α(u,k)}), k = 1, …, u − 1,

independently of the fact that σ_{2} = V (1) or σ_{2} = V (−1). We choose the numbers T_{k}^{(1)} so that s_{1} ≥ q(u) is necessary for the solvability of the system of congruences

∑_{i=1}^{s_{1}} \binom{x_{i,1}}{u} ≡ T_{u}^{(1)} + σ_{1} (mod 3),

∑_{i=1}^{s_{1}} \binom{x_{i,1}}{k} ≡ T_{k}^{(1)} (mod 3^{α(u,k)}), k = 1, …, u − 1,

independently of the fact that σ_{1} = V (0) or σ_{1} = V (−1). Finally, we choose the numbers T_{k}^{(0)} so that s_{0} ≥ q(u) is necessary for the solvability of the system of congruences

∑_{i=1}^{s_{0}} \binom{x_{i,0}}{u} ≡ T_{u}^{(0)} + σ_{0} (mod 3),

∑_{i=1}^{s_{0}} \binom{x_{i,0}}{k} ≡ T_{k}^{(0)} (mod 3^{α(u,k)}), k = 1, …, u − 1,

independently on the fact that σ_{0} = V (0) or σ_{0} = V (1).

Let us return to system (21) with the chosen T_{k}^{(r)}. If d_{1} + d_{2} ≥ 3, then

s = s_{0} + 2(q(u) − 1) + 3^{[n/2]}(d_{1} + d_{2}) ≥ q(n).

Therefore, it is sufficient to restrict ourselves by the consideration of the cases with d_{1} + d_{2} ≤ 2. Let η = 0. If d_{1} + 2d_{2} ≡ −1 (mod 3), then (d_{1}, d_{2}) is equal to (2, 0) or (0, 1). Then however, by the choice of the numbers T_{k}^{(2)} and T_{k}^{(1)}, the numbers s_{2} and s_{1} should be not less than q(u); in turn, this implies that d_{2} ≥ 1 and d_{1} ≥ 1. Hence, d_{1} + 2d_{2} ≡ 0 (mod 3) or d_{1} + 2d_{2} ≡ 1 (mod 3). In both cases, by the choice of the numbers T_{k}^{(0)}, we have the inequality s_{0} ≥ q(u). If d_{1} + 2d_{2} ≡ 0 (mod 3), then (d_{1}, d_{2}) is equal to (0, 0) or (1, 1). However, the choice of the numbers T_{k}^{(1)} implies that d_{1} ≥ 1, and thus, (d_{1}, d_{2}) can only be equal to (1, 1). If d_{1} + 2d_{1} ≡ 1 (mod 3), then (d_{1}, d_{2}) is equal to (1, 0) or (0, 2). It follows, however, from the choice of the numbers T_{k}^{(2)} that d_{2} ≥ 1 and (d_{1}, d_{2}) can only be equal to (0, 2). In both cases d_{1} + d_{2} = 2 and

s = s_{0} + 2(q(u) − 1) + 3^{[n/2]}(d_{1} + d_{2}) ≥ q(n).

Let η = 1. If d_{1} + 2d_{2} ≡ 1 (mod 3), then (d_{1}, d_{2}) is equal to (1, 0) or (0, 2), and d_{1} + 2d_{2} + η ≡ −1 (mod 3). By the choice of the numbers T_{k}^{(2)} and T_{k}^{(1)}, the numbers s_{2} and s_{1} in system (21) should be not less than q(u); in turn, this implies that d_{2} ≥1 and d_{1} ≥1. Hence d_{1} +2d_{2} ≡0 (mod 3) or d_{1} + 2d_{2} ≡ −1 (mod 3) and respectively, d_{1} + 2d_{2} + η ≡ 1 (mod 3) or d_{1} + 2d_{2} + η ≡ 0 (mod 3). In both cases, by the choice of the numbers T_{k}^{(0)}, we have the inequality s_{0} ≥ q(u). In the case d_{1} + 2d_{2} + η ≡ 1 (mod 3), only the value (1, 1) is possible for (d_{1}, d_{2}) since, by the choice of the numbers T_{k}^{(2)} it follows that d_{2} ≥ 1. Analogously, in the case d_{1} + 2d_{2} + η ≡ 0 (mod 3), only the value (2, 0) is possible for (d_{1}, d_{2}) since, by the choice of the numbers T_{k}^{(1)}, it follows that d_{1} ≥ 1. In both cases, the equality d_{1} + d_{2} = 2 holds, and hence,

s = s_{0} + 2(q(u) − 1) + 3^{[n/2]}(d_{1} + d_{2}) ≥ q(n).

5. It remains to consider the induction step for odd n = 3u + 1. Then u is even, and the inequality

[\frac{n}{2}] − [\frac{l + 1}{2}] ≥ [\frac{u − h + 1}{2}] + 1 = α(u, h)

holds for l = 3h, 3h − 1, 3h − 2, h = 1, …, u, except for the cases where l = 3h with h = u and h = u − 1, and l = 3h − 1 with h = u. Hence the congruence

K_{l}(d_{1}, d_{2}) ≡ 0 (mod 3^{α(u,h)})

holds for l = 3h, 3h − 1, 3h − 2 (h = 1, …, u), except for the indicated cases where the following equalities hold:

K_{3u}(d_{1}, d_{2}) = −(d_{1} + d_{2}),  K_{3u−1}(d_{1}, d_{2}) = d_{1} + 2d_{2} − χ,  K_{3u−3}(d_{1}, d_{2}) = 3(d_{1} + 2d_{2} − χ),

According to system (17), we have from this the following system of congruences for the numbers L_{k,γ}:

∑_{γ=0}^{2} ∑_{k=1}^{u} D_{3u,k,γ}L_{k,γ} ≡ −(d_{1} + d_{2}) (mod 3),

∑_{γ=0}^{2} ∑_{k=1}^{u} D_{3u−1,k,γ}L_{k,γ} ≡ d_{1} + 2d_{2} − χ (mod 3),

∑_{γ=0}^{2} ∑_{k=1}^{u} D_{3u−2,k,γ}L_{k,γ} ≡ 0 (mod 3),

∑_{γ=0}^{2} ∑_{k=1}^{u} D_{3u−3,k,γ}L_{k,γ} ≡ 3(d_{1} + 2d_{2} − χ) (mod 3^{2}),

∑_{γ=0}^{2} ∑_{k=1}^{u} D_{l,k,γ}L_{k,γ} ≡ 0 (mod 3^{α(u,[(l+2)/3])}), l = 1, …, 3u − 4,

Using representation (15), where g_{k,l} = Δ_{3}^{(k−1)}\binom{0}{l−1}, and the bounds of ν_{3}(g_{k,l}) from Lemmas 6 and 8, we reduce this system to the form

c_{3u,1}L_{u,2} + c_{3u,2}L_{u,1} ≡ −(d_{1} + d_{2}) (mod 3),
c_{3u−1,1}L_{u,1} + c_{3u−1,2}L_{u,0} ≡ d_{1} + 2d_{2} − χ (mod 3),
c_{3u−2,1}L_{u,0} + c_{3u−2,2}L_{u−1,2} ≡ 0 (mod 3),

\begin{matrix}c_{3u−3,1}g_{u,3u−4}L_{u,1} + (c_{3u−3,1}g_{u,3u−3} + c_{3u−3,2}g_{u,3u−4})L_{u,0} \\ + (c_{3u−3,1} + c_{3u−3,2}g_{u−1,3u−6})L_{u−1,2} + c_{3u−3,2}L_{u−1,1} ≡ 3(d_{1} + 2d_{2} − χ) (mod 3^{2}), \end{matrix}

\begin{matrix}c_{3u−4,1}g_{u,3u−4}L_{u,0} + c_{3u−4,1}g_{u−1,3u−6}L_{u−1,2} + (c_{3u−4,1} + c_{3u−4,2}g_{u−1,3u−6})L_{u−1,1} \\ + c_{3u−4,2}L_{u−1,0} ≡ 0 (mod 3^{2}), \end{matrix}

c_{3u−5,1}g_{u−1,3u−6}L_{u−1,1} + (c_{3u−5,1} + c_{3u−5,2}g_{u−1,3u−6})L_{u−1,0} + c_{3u−5,2}L_{u−2,2} ≡ 0 (mod 3^{2}),

∑_{γ=0} ∑_{k=1}^{u−2} D_{l,k,γ}L_{k,γ} ≡ 0 (mod 3^{α(u,[(l+2)/3])}), l = 1, …, 3u − 6,

where L_{u−2,2} = 0 if u = 2. Considering the obtained system modulo 3, we have with the help of Lemma 6 and the condition c_{l,1} ≢ 0 (mod 3) that

L_{u,0} ≡ 0 (mod 3), L_{k,r} ≡ 0 (mod 3),  k = 1, …, u − 1, r = 0, 1, 2.  (22)

Moreover, the congruences

L_{k,r} ≡ 0 (mod 3^{α(u,k)}),  k = 1, …, u − 2, r = 0, 1, 2,  (23)

follow from the congruences of the system which correspond to l = 1, …, 3u − 6. Substituting congruences (22) and (23) into the system, we arrive at the congruences

c_{3u,1}L_{u,2} + c_{3u,2}L_{u,1} ≡ −(d_{1} + d_{2}) (mod 3),  c_{3u−1,1}L_{u,1} ≡ d_{1} + 2d_{2} − χ (mod 3), (24)
L_{u−1,0} ≡ L_{u−1,1} ≡ 0 (mod 3^{2}),  L_{u−1,2} ≡ 3(d_{1} + 2d_{2} − χ) − g_{u,3u−4}L_{u,1} (mod 3^{2}). (25)

Now we shall need explicit expressions for the numbers c_{3u,1}, c_{3u,2}, and c_{3u−1,1}. According to the definition of the numbers c_{l,1} and c_{l,2}, Lemma 3, and the notation of Lemma 9,

c_{l,1} = μ_{l},  c_{l,2} = −μ_{l+1},  c_{l+1,1} = c_{l,1},  c_{l+1,2} = c_{l,2}

for even l. Since u is even, we obtain from this and Lemma 9

c_{3u−1,1} = c_{3u,1} = (−1)^{[u/2]} × 2, c_{3u,2} = (−1)^{[u/2]},

then we express L_{u,1} and L_{u,2} from congruences (24) as follows:

L_{u,1} ≡ −(−1)^{[u/2]}(d_{1} + 2d_{2} − χ) (mod 3), L_{u,2} ≡ (−1)^{[u/2]}(−d_{2} + χ) (mod 3).

We rewrite the congruence in relations (25) for L_{u−1,2} in the form

L_{u−1,2} ≡ 3λ(d_{1} + 2d_{2} − χ) (mod 3^{2}),  (26)

where λ is a certain integer.

By the definition of the numbers Y_{k,γ} and L_{k,γ}, we obtain the following congruences from congruences (23)–(26):

X_{u,2} ≡ T_{u}^{(2)} − d_{2} (mod 3),  X_{u,1} ≡ T_{u}^{(1)} − d_{1} (mod 3),  X_{u,0} ≡ T_{u}^{(0)} + d_{1} + d_{2} (mod 3),
X_{u−1,r} ≡ T_{u−1}^{(r)} + 3λ(d_{1} + 2d_{2} − χ) (mod 3^{2}), r = 0, 1, 2,
X_{k,r} ≡ T_{k}^{(r)} (mod 3^{α(u,k)}), k = 1, …, u − 2, r = 0, 1, 2,

where we denote

X_{k,r} = ∑_{i=1}^{s_{r}} \binom{x_{i,r}}{k}.

Since n is an odd number of type (B), according to congruence (12), η = λ(d_{1} + 2d_{2} − χ) can have not more than two values modulo 3. By the induction assumption, for an even u of type (B), we choose the numbers T_{k}^{(r)} for each r = 0, 1, 2 so that s_{r} ≥ q(u) is necessary for the solvability of the system of congruences

∑_{i=1}^{s_{r}} \binom{x_{i,r}}{u} ≡ T_{u}^{(r)} (mod 3),  ∑_{i=1}^{s_{r}} \binom{x_{i,r}}{u − 1} ≡ T_{u−1}^{(r)} + 3η (mod 3^{2}),

∑_{i=1}^{s_{r}} \binom{x_{i,r}}{k} ≡ T_{k}^{(r)} (mod 3^{α(u,k)}), k = 1, …, u − 2,

independently of η. It is easy to see that the conditions d_{2} ≥ 1 and d_{1} ≥ 1 are necessary for the

chosen numbers T_{k}^{(r)}. But since, by relation (12), d_{1} + 2d_{2} is congruent to 1 or −1 modulo 3, we have d_{1} + d_{2} ≥ 3, and therefore,

s = s_{0} + 2(q(u) − 1) + 3^{[n/2]}(d_{1} + d_{2}) ≥ q(n).

By the induction principle, the assertion of the theorem is valid for all natural numbers of types (A) and (B).

Corollary. Suppose that s and n are two natural numbers and n belongs to one of two types (A) or (B) depending on the fact that all positive numbers of series (2) are simultaneously odd or are not simultaneously divisible by 3. Then there exist integers A_{1}, …, A_{n} such that the condition s ≥ q(n), where the function q(n) is defined recursively in relations (1), is necessary for the solvability of the system of equations of degree n

∑_{i=1}^{s} \binom{x_{j}}{j} ≡ A_{j}, j = 1, …, n,

in integer 3-adic numbers x_{1}, …, x_{s}.

ACKNOWLEDGMENTS

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

REFERENCES

1. Arkhipov, G. I., On the Hilbert–Kamke Problem, Izv. Akad. Nauk SSSR, Ser. Mat., 1984, vol. 48, no. 1, pp. 3–52.

2. Mit’kin, D. A., An Estimate of the Number of Summands in the Hilbert–Kamke Problem, Mat. Sb., 1986, vol. 129 (171), no. 4, pp. 549–577.

3. Mit’kin, D. A., An Estimate of the Number of Summands in the Hilbert–Kamke Problem, II, Mat. Sb., 1987, vol. 132 (174), no. 3, pp. 345–351.

4. Arkhipov, G. I. and Karatsuba, A. A., On a Local Representation of Zero by a Form, Izv. Akad. Nauk SSSR, Ser. Mat., 1981, vol. 45, no. 5, pp. 948–961.

5. Chubarikov, V. N., On a Simultaneous Representation of Natural Numbers by Sums of Powers of Prime Numbers, Dokl. Akad. Nauk SSSR, 1986, vol. 286, no. 4, pp. 828–831.

6. Mit’kin, D. A., On the Number of Summands in the Hilbert–Kamke Problem in Prime Numbers, Diskr. Mat., 1992, vol. 4, no. 4, pp. 149–158.

Translated by S. Vakhromeev