The normal limit distribution of the number of false solutions of a system of nonlinear random equations in the field GF(2)
The theorem on a normal limit (n→∞) distribution of the number of false solutions of a beforehand consistent system of nonlinear random equations in the field GF(2) with independent coefficients is proved. In particular, we assume that each equation has coefficients that take values 0 and 1 with e...
Збережено в:
| Дата: | 2006 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут математики НАН України
2006
|
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/4447 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | The normal limit distribution of the number of false solutions of a system of nonlinear random equations in the field GF(2) / V.I. Masol, S.Y. Slobodyan // Theory of Stochastic Processes. — 2006. — Т. 12 (28), № 1-2. — С. 116–126. — Бібліогр.: 3 назв.— англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-4447 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-44472009-11-11T12:00:29Z The normal limit distribution of the number of false solutions of a system of nonlinear random equations in the field GF(2) Masol, V.I. Slobodyan, S.Y. The theorem on a normal limit (n→∞) distribution of the number of false solutions of a beforehand consistent system of nonlinear random equations in the field GF(2) with independent coefficients is proved. In particular, we assume that each equation has coefficients that take values 0 and 1 with equal probability; the system has a solution where the number of ones equals [ρn], ρ = const, 0 < ρ < 1. 2006 Article The normal limit distribution of the number of false solutions of a system of nonlinear random equations in the field GF(2) / V.I. Masol, S.Y. Slobodyan // Theory of Stochastic Processes. — 2006. — Т. 12 (28), № 1-2. — С. 116–126. — Бібліогр.: 3 назв.— англ. 0321-3900 http://dspace.nbuv.gov.ua/handle/123456789/4447 519.21 en Інститут математики НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
The theorem on a normal limit (n→∞) distribution of the number of false solutions
of a beforehand consistent system of nonlinear random equations in the field GF(2)
with independent coefficients is proved. In particular, we assume that each equation
has coefficients that take values 0 and 1 with equal probability; the system has a
solution where the number of ones equals [ρn], ρ = const, 0 < ρ < 1. |
| format |
Article |
| author |
Masol, V.I. Slobodyan, S.Y. |
| spellingShingle |
Masol, V.I. Slobodyan, S.Y. The normal limit distribution of the number of false solutions of a system of nonlinear random equations in the field GF(2) |
| author_facet |
Masol, V.I. Slobodyan, S.Y. |
| author_sort |
Masol, V.I. |
| title |
The normal limit distribution of the number of false solutions of a system of nonlinear random equations in the field GF(2) |
| title_short |
The normal limit distribution of the number of false solutions of a system of nonlinear random equations in the field GF(2) |
| title_full |
The normal limit distribution of the number of false solutions of a system of nonlinear random equations in the field GF(2) |
| title_fullStr |
The normal limit distribution of the number of false solutions of a system of nonlinear random equations in the field GF(2) |
| title_full_unstemmed |
The normal limit distribution of the number of false solutions of a system of nonlinear random equations in the field GF(2) |
| title_sort |
normal limit distribution of the number of false solutions of a system of nonlinear random equations in the field gf(2) |
| publisher |
Інститут математики НАН України |
| publishDate |
2006 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/4447 |
| citation_txt |
The normal limit distribution of the number of false solutions of a system of nonlinear random equations in the field GF(2) / V.I. Masol, S.Y. Slobodyan // Theory of Stochastic Processes. — 2006. — Т. 12 (28), № 1-2. — С. 116–126. — Бібліогр.: 3 назв.— англ. |
| work_keys_str_mv |
AT masolvi thenormallimitdistributionofthenumberoffalsesolutionsofasystemofnonlinearrandomequationsinthefieldgf2 AT slobodyansy thenormallimitdistributionofthenumberoffalsesolutionsofasystemofnonlinearrandomequationsinthefieldgf2 AT masolvi normallimitdistributionofthenumberoffalsesolutionsofasystemofnonlinearrandomequationsinthefieldgf2 AT slobodyansy normallimitdistributionofthenumberoffalsesolutionsofasystemofnonlinearrandomequationsinthefieldgf2 |
| first_indexed |
2025-07-02T07:41:25Z |
| last_indexed |
2025-07-02T07:41:25Z |
| _version_ |
1836520136651046912 |
| fulltext |
Theory of Stochastic Processes
Vol. 12 (28), no. 1–2, 2006, pp. 116–126
UDC 519.21
VOLODYMYR I. MASOL AND SVITLANA Y. SLOBODYAN
THE NORMAL LIMIT DISTRIBUTION OF THE
NUMBER OF FALSE SOLUTIONS OF A SYSTEM OF
NONLINEAR RANDOM EQUATIONS IN THE FIELD GF(2)
The theorem on a normal limit (n → ∞) distribution of the number of false solutions
of a beforehand consistent system of nonlinear random equations in the field GF(2)
with independent coefficients is proved. In particular, we assume that each equation
has coefficients that take values 0 and 1 with equal probability; the system has a
solution where the number of ones equals [ρn], ρ = const, 0 < ρ < 1.
Statement of the problem. Formulation of the theorem
Let us consider a system of equations over the field GF(2) consisting of two elements
(1)
gi(n)∑
k=1
∑
1≤j1<...<jk≤n
a
(i)
j1...jk
xj1 . . . xjk
= bi, i = 1, . . . , N,
that satisfies condition (A).
Condition (A):
1) Coefficients a
(i)
j1...jk
, 1 ≤ j1 < . . . < jk ≤ n, k = 1, . . . , gi(n), i = 1, . . . , N, are
independent random variables that take value 1 with probability P{a(i)
j1...jk
= 1} = pik
and value 0 with probability P{a(i)
j1...jk
= 0} = 1 − pik.
2) Elements bi, i = 1, . . . , N , are the result of the substitution of a fixed n-dimensional
vector x0, that has [ρn] /n−[ρn]/ components equal to one /zero/, ρ = const, 0 < ρ < 1
on the left-hand side of system (1) .
3) Function gi(n), i = 1, . . . , N, is nonrandom, gi(n) ∈ {2, . . . , n}, i = 1, . . . , N.
Denote by νn the number of false solutions of the system (1) , i.e. the number of
solutions of system (1) different from the vector x0.
Put m = n−N . We are interested in the conditions, under which the random variable
νn has a normal limit (n → ∞) distribution.
Theorem. Let, for an arbitrary i, i = 1, . . . , N, there exist a nonempty set
(2) Ti ⊆ {2, 3, . . . , ϕ(n)}, Ti �= ∅,
such that
(3) pit =
1
2
for t ∈ Ti,
2000 AMS Mathematics Subject Classification. Primary 60C05.
Key words and phrases. The nonlinear random equations in the GF(2), normal limit distribution,
number of false solutions.
116
THE NORMAL LIMIT DISTRIBUTION OF THE NUMBER OF FALSE SOLUTIONS 117
where the function ϕ(n) takes integer values,
(4) 2 ≤ ϕ(n) ≤ ε
n1−p
lnn
,
(5) p = const, 0 < p < 1,
(6) ε is a positive number, 0 < ε <
ρ
2
,
and
(7) m = [log2(
p
14
log2 n)].
Then
(8) λ → ∞, n → ∞,
where λ = Mνn, and the random variable νn−λ√
λ
has asymptotically (n → ∞) standard
normal distribution.
Auxiliary statements
Proposition 1. ([1]) Let X and Y be random variables that take non-negative integer
values, and λ = MX. If the distributions of the random variables are changed so that
(9) sup
1≤r≤7λ
∣∣M(X)r(M(Y )r)−1 − 1
∣∣ e2λ
√
λ
→ 0
and, for all r ≤ 7λ,
(10) M(Y )r ≤ Cλr
with some constant C, then
(11) max
1≤r≤2λ
|P {X ≥ t} − P {Y ≥ t}| → 0.
Proposition 2. ([2]) If condition (A) holds, then the expectation of the random variable
νn equals
(12) Mνn =
n−[ρ n]∑
i=0
Ci
n−[ρ n]
[ρ n]∑
j=0
Cj
[ρ n]
N∏
i=1
⎛
⎝1
2
+
1
2
gi(n)∏
t=1
(1 − 2pit)
Γt
⎞
⎠ ,
where Γt = Ct
i+[ρ n]−j + Ct
[ρ n] − 2Ct
[ρ n]−j , t = 1, ..., gi(n) , i + j ≥ 1.
Proposition 3. ([3]) If condition (A) holds, then, for integer r ≥ 1,
(13) M (νn)r = 2−r NS(n, r; Q),
where
(14)
S(n, r; Q) =
n−[ρ n]∑
s=0
∑
(n − [ρ n]) !
(
(n − [ρ n] − s) !
∏
i∈I
i!
)−1
×
[ρ n]∑
s′=0
s′+s≥1
∑ ′ ([ρ n])!
⎛
⎝([ρ n] − s′) !
∏
j∈J
j!
⎞
⎠
−1
Q,
118 VOLODYMYR I. MASOL AND SVITLANA Y. SLOBODYAN
(15) Q =
N∏
i=1
⎛
⎝1 +
r∑
ν=1
∑
1≤u1<...<uν≤r
gi(n)∏
t=1
(1 − 2pit)
Γ
{u1,...,uν}
t,r
⎞
⎠ ,
the sum
∑
(
∑ ′ ) is taken over all i ∈ I (j ∈ J), where I = { i{u1,...,uν} : 1 ≤ u1 <
... < uν ≤ r, ν = 1, ..., r } , J =
{
j{u1,...,uν} : 1 ≤ u1 < ... < uν ≤ r, ν = 1, ..., r
}
,
such that
(16)
∑
i∈I
i = s
⎛
⎝∑
j∈J
j = s′
⎞
⎠ ;
the numbers i (i ∈ I) , j (j ∈ J) satisfy the relations
(17)
∑
i∈I{u},j∈J{u}
(i + j) ≥ 1, u = 1, ..., r,
in equality (14),
(18)
r−2∑
l=0
∑
1≤μ1<...<μl≤r
(
i{u1,μ1,...,μl} + j{u1,μ1,...,μl} + i{u2,μ1,...,μl} + j{u2,μ1,...,μl}
) ≥ 1,
1 ≤ u1 < u2 ≤ r ;
for 1 ≤ u1 < ... < uν ≤ r, ν ∈ {1, ..., r} and t ∈ {1, ..., n}, the inequality
(19) Γ{u1,...,uν}
t, r ≥
∑
(i,j)∈T
(
Ct
i + Ct
j
)
holds true, where T = I{u1,...,uν} × J{u1,...,uν} ; and if
(20) [ρ n] − s′ ≥ t,
then
(21) Γ{u1,...,uν}
t, r ≥ Ct−1
[ρ n]−s′
∑
(i,j)∈T
(i + j) .
Here,
I{ur ,...,uν} =
{
i{σ1,...,σψ, μ1,...,μl} : A (ψ, l, r)
}
,
J{ur ,...,uν} =
{
j{σ1,...,σψ, μ1,...,μl} : A (ψ, l, r)
}
,
where A (ψ, l, r) is a notation for the following set of restrictions: 1 ≤ σ1 < ... < σψ ≤
r, σz ∈ {u1, ..., uν} , z = 1, ..., ψ, ψ = 1, ..., ν, ψ ≡ 1 (mod2) , 1 ≤ μ1 < ... < μl ≤
r, μ1, ..., μl /∈ {u1, ..., uν} , l = 0, ..., r − ν.
Remark 1. The explicit expression Γ{u1,...,uν}
t, r for 1 ≤ u1 < ... < uν ≤ r, ν ∈ {1, ..., r} ,
t = 1, 2, ..., gi (n) , i = 1, ..., N is given in [3].
Let W be a set of all nonempty subsets of the set Ω, the potency of which equals
|Ω| = k, 1 ≤ k < ∞. Let us define two subsets WΔ and Is of the set W :
WΔ ⊆ W, WΔ = {ω1, ..., ωΔ} , |WΔ| = Δ , Δ ≥ 1, ωi �= ωj
for i �= j, i, j ∈ {1, ...,Δ};
Is ⊆ W, Is = {m1, ..., ms} , |Is| = s, s ≥ 0, mi �= mj
for i �= j, i, j ∈ {1, ..., s} .
THE NORMAL LIMIT DISTRIBUTION OF THE NUMBER OF FALSE SOLUTIONS 119
Proposition 4. ([3]) Let
(22) |mi ∩ ωj| ≡ (mod2), i = 1, ..., s, j = 1, ..., Δ;
(23) Δ ∈ [2r−1, 2r − 1] , 1 ≤ r ≤ k.
Then
(24) s ≤ 2k−r − 1.
Proposition 5. ([3]) Let Ω = {1, ..., k} , 3 < k < ∞. If conditions (22),
(25) Δ = 2r − 1, s = 2k−r − 1, 1 ≤ r ≤ k − 2;
(26) |ωj | ≥ 3, j = 1, ...,Δ,
hold for the sets WΔ and Is, then there exists such a number α, α ∈ {1, ...,Δ} , that, for
some miν , miν ∈ Is, ν = 1, 2, 3,
(27) |ωα ∩ miν | = 2, ν = 1, 2, 3, |ωα ∩ (a ∪ b) | = 3,
where a �= b, a, b ∈ {miν : ν = 1, 2, 3} .
Remark 2. Condition (26) does not hold for r = k − 1 and s = 1. This fact follows from
the proof of Proposition 5 (see also [3, p.45]).
Proof of the theorem
Let us show that, under the conditions of the theorem, we can use Proposition 1.
Let the random variable Y in the mentioned proposition have the Poisson distribution
with parameter 2m, while the distribution of the random variable X coincides with the
distribution of the random variable νn.
Provided that condition (3) holds, Proposition 2 implies
(28) Mνn = 2m − 1
2N
.
Next, using relation (28), conditions (5) and (7), it is easy to show that (8) is valid and
inequality (10) is fulfilled with C ≥ 2 for all n, beginning from some n0, n ≥ n0.
Let us proceed to the verification of condition (9).To achieve this, we will use equal-
ity (13) written as
(29) M (νn)r =
1
2rN
2r−1∑
Δ=0
S(Δ) (n, r; Q),
where S(Δ) (n, r; Q) differs from S (n, r; Q) so that all i and j, i ∈ I, j ∈ J , participating
in the notation S (n, r; Q) given by (14) take only such values that there exist precisely
Δ various sets
(30)
ωα =
{
u
(α)
1 , ..., u
(α)
ξα
}
, 1 ≤ u
(α)
1 < ... < u
(α)
ξα
≤ r,
ξα ∈ {1, 2, ..., r} , α = 1, 2, ...,Δ,
for each of which a number t(α) ∈ {2, ..., ϕ (n)} can be found such that
(31) Γωα
t(α), r
= 0,
and, for the sets {ϑ1, ..., ϑγ} , 1 ≤ ϑ1 < ... < ϑγ ≤ r, γ = 1, ..., r, satisfying the relation
(32) {ϑ1, ..., ϑγ} �= ωα, α = 1, 2, ..., Δ,
120 VOLODYMYR I. MASOL AND SVITLANA Y. SLOBODYAN
the estimate
(33) Γ{ϑ1,...,ϑγ}
t, r ≥ 1
is valid for all t ∈ {2, ..., ϕ (n)} .
Let us show that
(34) sup
1≤r≤7λ
∣∣∣∣S(0) (n, r; Q)
2r NM (Y )r
− 1
∣∣∣∣ e2λ
√
λ
→ 0, n → ∞.
Firstly, we state that the equality Δ = 0 can really be achieved.
Indeed, if the inequality i ≥ ϕ (n) , j ≥ ϕ (n) , holds for all i, i ∈ I and (or) j, j ∈ J ,
then, by virtue of (19), estimation (33) holds true for all sets {ϑ1, ..., ϑγ} , 1 ≤ ϑ1 < ... <
ϑγ ≤ r, γ = 1, ..., r, and t ∈ {2, ..., ϕ (n)} ; and the inequality max (|I|ϕ (n) , |J |ϕ (n)) ≤
min (n − [ρn], [ρn]) holds for r ≤ 7λ.
Thus, the equality Δ = 0 can be really reached.
With Δ = 0, estimate (33) and condition (3) imply
(35) Q = 1.
Hence, by the polynomial theorem,
(36) S(0) (n, r; Q) = S(0) (n, r; 1) = 2r n − σ0,
where
(37) σ0 = 1 +
2r−1∑
q=1
S(0)
q (n, r; 1),
S
(0)
q (n, r; 1) differs from S (n, r; 1) so that the numbers i ∈ I and j ∈ J on the right-
hand side of (14) are changed so that there exist precisely q expressions of the type
Γ{u1,...,uν}
t, r , for each of which
(38) Γ{u1,...,uν}
t, r = 0,
where q = 1, 2, 3, ..., 2r − 1.
Let all expressions Γ{u1,...,uν}
t, r , 1 ≤ u1 < ... < uν ≤ r, ν ∈ {1, ..., r}, be numbered by
1, 2, 3, ..., 2r − 1. Then the sum S
(0)
q (n, r; 1) can be written as
(39) S(0)
q (n, r; 1) =
∑
1≤γ1<...<γq≤2r−1
S
(0)
〈γ1,...,γq〉 (n, r; 1),
q = 1, 2, 3, ..., 2r − 1, where S
(0)
〈γ1,...,γq〉 (n, r; 1) differs from S
(0)
q (n, r; 1) so that rela-
tion (38) holds only for those expressions Γ{u1,...,uν}
t, r to which the numbers γ1, γ2, ..., γq
correspond. Denote, by A (γ1, ..., γq) /B (γ1, ..., γq) /, the set of all those i ∈ I /j ∈ J/
that are used in estimate (19) for all γ1, γ2, ..., γq. By virtue of (38), the number of
elements in the set A (γ1, ..., γq) /B (γ1, ..., γq) / is not less than 2r−1:
(40) |A (γ1, ..., γq)| ≥ 2r−1,
(41) |B (γ1, ..., γq)| ≥ 2r−1.
THE NORMAL LIMIT DISTRIBUTION OF THE NUMBER OF FALSE SOLUTIONS 121
Now, the sum S
(0)
q (n, r; 1) can be given as
(42)
S(0)
q (n, r; 1) =
∑
1≤γ1<...<γq≤2r−1
n−[ρ n]∑
s=0
Cs
n−[ρ n]×
×
∑
s1+s2=s
Cs1
s
⎧⎪⎨
⎪⎩
∑
1
s1 !∏
i∈A(γ1,..., γq)
i !
⎫⎪⎬
⎪⎭
⎛
⎜⎝∑
2
s2 !∏
i∈I\A(γ1,..., γq)
i !
⎞
⎟⎠×
×
[ρ n]∑
s′=0
∑
s′
1+s′
2=s′
C
s′
1
s′
⎧⎪⎨
⎪⎩
∑
3
s′1!∏
j∈B(γ1,..., γq)
j !
⎫⎪⎬
⎪⎭
⎛
⎜⎝∑
4
s′2!∏
j∈J\B(γ1,..., γq)
j !
⎞
⎟⎠,
where
∑
1 is the sum over all i ∈ A (γ1, ..., γq) such that
∑
i = s1,
∑
2 is the sum over
all i ∈ I\A (γ1, ..., γq) such that
∑
i = s2,
∑
3 is the sum over all j ∈ B (γ1, ..., γq) such
that
∑
j = s′1, and
∑
4 is the sum over all j ∈ j\B (γ1, ..., γq) such that
∑
j = s′2.
Relations (37), (39) – (42), and the polynomial formula allow us to obtain the following
estimate for σ0:
(43) σ0 ≤ 22r−12(r−1)n
⎛
⎝∑
s1≥0
Cs1
n−[ρ n]
(
2r−1
)s1
⎞
⎠
⎛
⎝∑
s′
1≥0
C
s′
1
[ρ n]
(
2r−1
)s′
1
⎞
⎠ .
Since s1 ≤ 2rϕ (n) and s′1 ≤ 2rϕ (n), relation (43) can be rewritten in the following way:
(44) σ0 ≤ 22r−12(r−1)n2r 2r+1ϕ (n)
⎛
⎝2rϕ (n)∑
s1=0
Cs1
n−[ρ n]
⎞
⎠
⎛
⎝2rϕ (n)∑
s′
1=0
C
s′
1
[ρ n]
⎞
⎠ .
Next, we can use the fact that, under the conditions of the theorem for 1 ≤ r ≤ 7λ,
(45) 2r+1ϕ (n) ≤ min (n − [ρn], [ρn]) .
This allows us to proceed from (44) to the estimate
σ0 ≤ 22r−12(r−1) n2r 2r+1ϕ (n) (2rϕ (n))2 C
2rϕ (n)
n−[ρ n]C
2rϕ (n)
[ρ n] ,
from whence, with the help of the Stirling’s formula, we can obtain
(46) σ0 ≤ 22r−12(r−1) n 2rϕ (n)
2π
(
(n − [ρ n]) [ρ n] e2
ϕ2 (n)
)2rϕ (n)
.
Now it is easy to verify that
(47) sup
1≤r≤7λ
σ0
2r n
e2λ
√
λ
→ 0
as n → ∞.
Indeed, by virtue of (46), we can find
(48)
sup
1≤r≤7λ
σ0
2r n
e2λ
√
λ
≤ 1
4π
exp
{
27λ ln 2 + 7λ ln 2+
+ 27λϕ (n) ln
(
(n − [ρ n]) [ρ n] e2
ϕ2 (n)
)
+ lnϕ (n) + 2λ − 1
2
lnλ − n ln 2
}
.
122 VOLODYMYR I. MASOL AND SVITLANA Y. SLOBODYAN
Conditions (4), (7) and relation (28) allow us to conclude that
(49) 0 ≤ 27λϕ (n) ≤ ε
n1− p
2
lnn
.
In response to (48) and (49), we can apparently obtain (47).
From the relations (36), (47) and equality M (Y )r = 2r m, (34) follows.
By virtue of (29) and (34), in order to complete the checking of condition (9), it is
necessary to establish that, for 1 ≤ r ≤ 7λ,
(50)
1
2r N+r m
(
2r−1∑
Δ=1
S(Δ) (n, r; Q)
)
e2λ
√
λ
→ 0
as n → ∞.
Let us show that the restriction (R0)
(51) [ρ n] − ϕ (n) + 1 ≤ s′ ≤ [ρ n],
where s′ is the summation parameter introduced in (14), implies (50).
Let S
(Δ)
〈(R 0); γ1,...,γΔ〉 (n, r; 1) be defined in analogy to S
(0)
〈 γ1,...,γΔ〉 (n, r; 1) with the ad-
ditional condition (R0). Then, under condition (51), we have
(52)
2r−1∑
Δ=1
S(Δ) (n, r; Q) =
r∑
z=1
2z−1∑
Δ=2z−1
∑
1≤γ1<...<γΔ≤2r−1
S
(Δ)
〈(R 0); γ1,...,γΔ〉 (n, r; Q).
Each term on the right-hand side of (52) can be estimated as
(53) S
(Δ)
〈(R 0); γ1,...,γΔ〉 (n, r; Q) ≤ (Δ + 1)N
S
(Δ)
〈(R 0); γ1,...,γΔ〉 (n, r; 1) .
Denote, by M1 /M̃1/, the set of all i, i ∈ I /j, j ∈ J/, that do not belong to
Iωα /Jωα/, α = 1, ... ,Δ and put M2 = I\M1, M̃2 = J\M̃1.
Let z be the minimal integer number such that
(54) Δ ≤ 2z − 1, 1 ≤ z ≤ r.
Then by Proposition 4, the number of elements of the set M1 /M̃1/ does not exceed
(55) |M1| ≤ 2r−z − 1,
∣∣∣M̃1
∣∣∣ ≤ 2r−z − 1.
With the help of (55), we find the estimate
(56)
S
(Δ)
〈(R 0); γ1,...,γΔ〉 (n, r; 1) ≤
≤
n−[ρ n]∑
s=0
Cs
n−[ρ n]
(
2r−z − 1
)s s∑
s2=0
s2≤(2r−1)ϕ (n)
Cs2
s (2r − 1)s2×
× (2r−z − 1
)[ρ n]
[ρ n]∑
s′=[ρ n]−ϕ(n)+1
Cs′
[ρ n]
s′∑
s′
2=0
s′
2≤(2r−1)ϕ(n)
C
s′
2
s′ (2r − 1)s′
2 ,
where s2 =
∑
i∈M1
i, s′2 =
∑
j∈M̃2
j.
THE NORMAL LIMIT DISTRIBUTION OF THE NUMBER OF FALSE SOLUTIONS 123
Relations (52) – (54) and (56) provide the inequality
(57)
2r−1∑
Δ=1
S(Δ) (n, r; Q) ≤ 22r+r n−m
(
1 − 1
2r−1
)[ρ n]
(2r − 1)2(2
r−1)ϕ (n) ×
×
⎛
⎝(2r−1)ϕ (n)∑
s2=0
Cs2
n−[ρ n]
⎞
⎠
⎛
⎝(2r−1)ϕ (n)∑
s′
2=0
C
s′
2
[ρ n]
⎞
⎠ ϕ (n)∑
s′=0
Cs′
[ρ n].
Let us observe that
(58)
(2r−1)ϕ (n)∑
s2=0
Cs2
n−[ρ n] ≤
(
(n − [ρ n]) e
(2r − 1)ϕ (n)
)(2r−1)ϕ (n)√
(2r − 1)ϕ (n) ,
(59)
(2r−1)ϕ (n)∑
s′
2=0
C
s′
2
[ρ n] ≤
(
[ρ n] e
(2r − 1)ϕ (n)
)(2r−1)ϕ (n)√
(2r − 1)ϕ (n) ,
(60)
ϕ (n)∑
s′=0
Cs′
[ρ n] ≤
(
[ρ n] e
ϕ (n)
)ϕ (n)√
ϕ (n) .
Using (58) – (60), (7), and (29), we find that when the restriction (R0) holds for 1 ≤ r ≤
7λ and all n, beginning from some n1, n ≥ n1,
(61)
1
2r N+r m
(
2r−1∑
Δ=1
S(Δ) (n, r; Q)
)
e2λ
√
λ
≤ 227 λ−m
(
1 − 1
27 λ−1
)[ρ n]
×
×
(
(n − [ρ n]) [ρ n] e2
ϕ2 (n)
)(27 λ−1)ϕ (n)( [ρ n] e
ϕ (n)
)ϕ (n)
e2λ
√
λ
(
27λ − 1
)
(ϕ (n))3/2
.
With the help of relation (61) and conditions (4) and (7), it is easy to verify that (50)
follows from (51).
Let now
(62) 0 ≤ s′ ≤ [ρ n] − ϕ (n) .
Next, we will use the following lemma.
Lemma. If condition (62) and restriction (R∗),
(R∗): there exists i ∈ M2 and (or) j ∈ M̃2 such that
0 ≤ i ≤ ϕ (n) and (or) 0 ≤ j ≤ ϕ (n) ,
hold, then, for an arbitrary Δ, 1 ≤ Δ ≤ 2r − 1,
(63) 0 ≤ S(Δ) (n, r; Q) ≤ CΔ
2r−12
r n−m+r
(
1 − 1
2r
)[ρ n](
n e
ϕ (n)
)2(2r−1)ϕ(n)
ϕ (n) .
With the help of the lemma, we find that (62) and (R∗) imply the inequality
1
2r N+r m
(
2r−1∑
Δ=1
S(Δ) (n, r; Q)
)
e2λ
√
λ
≤ 1
2r N+r m
22r+r n−m
(
1 − 1
2r
)[ρ n]
×
×
(
n e
ϕ (n)
)2(2r−1)ϕ (n)√
ϕ (n)
e2λ
√
λ
.
124 VOLODYMYR I. MASOL AND SVITLANA Y. SLOBODYAN
Hence, for 1 ≤ r ≤ 7λ, we obtain
(64)
1
2r N+r m
(
2r−1∑
Δ=1
S(Δ) (n, r; Q)
)
e2λ
√
λ
≤ exp
{
27λ ln 2 − m ln 2−
− [ρ n]
27λ
+ 2
(
27λ − 1
)
ϕ (n) ln
n e
ϕ (n)
+
1
2
lnϕ (n) + 2λ − 1
2
lnλ
}
.
Using (4), (7), and estimate λ ≤ 2m, we find that
(65)
214λ+1ϕ (n)
[ρ n]
ln
n e
ϕ (n)
≤ 2
ε
ρ
(
1 +
1
lnn
ln
e
2
)
< 1
holds for 0 < ε < ρ
2 and n → ∞.
Relations (64) and (65) allow us, apparently, to conclude that (50) holds true under the
conditions of the lemma.
The validity of condition (9) follows from relations (29), (34), and (50). Hence, the
conditions of Proposition 1 hold. Using Proposition 1, we obtain
max
1≤r≤2λ
|P {νn ≥ t} − P {Y ≥ t}| →
n→∞ 0.
The statement of the theorem follows now from the last relation and the fact that the
random variable (Y − 2m) (2m/2)−1 has the standard normal distribution as m → ∞ .
Proof of the lemma. Indeed, for S(Δ) (n, r; Q), we have the obvious estimate
(66) S(Δ) (n, r; Q) ≤
∑
1≤γ1<...<γΔ≤2r−1
S
(Δ)
〈γ1,...,γΔ〉 (n, r; Q),
where S
(Δ)
〈γ1,...,γΔ〉 (n, r; Q) is determined in accordance to S(Δ) (n, r; Q) but with an
additional condition, namely that relation (38) holds true only for those expressions
Γ{u1,...,uν}
t, r , 1 ≤ u1 < ... < uν ≤ r, ν ∈ {1, ..., r}, to which the numbers γ1, γ2, ..., γΔ ∈
{1, 2, 3, ..., 2r − 1} correspond.
Let z be the minimal integer number for which the inequality Δ ≤ 2z − 1 is valid.
Then, providing that conditions (62), (3) and restrictions (R1),
(R1): there exists i ∈ M2 and (or) j ∈ M̃2 such that
1 ≤ i ≤ ϕ (n) and (or) 1 ≤ j ≤ ϕ (n) ,
hold and taking into account relation (21), it is easy to check that
(67) Q ≤ (2z − 1)N
.
With the help of (66) and (67), we find that (63) and (R1) prove the correctness of the
inequality
(68) S(Δ) (n, r; Q) ≤ (2z − 1)N
∑
1≤γ1<...<γΔ≤2r−1
S
(Δ)
〈(R 1); γ1,...,γΔ〉 (n, r; 1),
where S
(Δ)
〈(R 1); γ1,...,γΔ〉 (n, r; 1) differs from S
(Δ)
〈γ1,...,γΔ〉 (n, r; 1) by the additional condition
(R1). In turn, accordingly to (56), we obtain
(2z − 1)N
S
(Δ)
〈(R 1); γ1,...,γΔ〉 (n, r; 1) ≤ 2r n−m
(
1 − 1
2r
)N
(2r − 1)2(2
r−1)ϕ(n) ×
×
(2r−1)ϕ(n)∑
s2=0
Cs2
n−[ρ n]
(2r−1)ϕ(n)∑
s′
2=0
C
s′
2
[ρ n],
THE NORMAL LIMIT DISTRIBUTION OF THE NUMBER OF FALSE SOLUTIONS 125
or, taking into account (58) and (59),
(69)
(2z − 1)N
S
(Δ)
〈(R 1); γ1,...,γΔ〉 (n, r; 1) ≤ 2r n−m
(
1 − 1
2r
)N (
n e
ϕ (n)
)2(2r−1)ϕ(n)
×
× (2r − 1)ϕ (n) .
Since [ρ n] < N = n − m for quite large values of n and ϕ (n) ≥ 2 by virtue of (4),
relations (68) and (69) imply inequality (63).
Denote, by (R2), the restrictions
(R2): (62); i = j = 0 for all i ∈ M2 and j ∈ M̃2.
Let us show that (63) holds under restrictions (R2).
Indeed, if, for the parameter Δ, the restrictions
(70) Δ < 2z − 1 or Δ = 2z − 1 and
∣∣∣M̃1
∣∣∣ < 2r−z − 1,
hold, then (66) implies
(71) S(Δ) (n, r; Q) ≤
∑
1≤γ1<...<γΔ≤2r−1
S
(Δ)
〈(R 2); (70); γ1,...,γΔ〉 (n, r; Q),
where S
(Δ)
〈(R 2); (70); γ1,...,γΔ〉 (n, r; Q) differs from S
(Δ)
〈γ1,...,γΔ〉 (n, r; Q) by the additional con-
ditions (R2) and (70).
Each term on the right-hand side of (71) can be estimated in the following way:
1) for Δ < 2z − 1, we have
(72) S
(Δ)
〈(R 2); (70); γ1,...,γΔ〉 (n, r; Q) ≤ 2r n−z(n−N)
(
1 − 1
2r
)N
,
2) for Δ = 2z − 1 and
∣∣∣M̃1
∣∣∣ < 2r−z − 1, we have
(73) S
(Δ)
〈(R 2); (70); γ1,...,γΔ〉 (n, r; Q) ≤ 2r n−m
(
1 − 1
2r
)[ρ n]
,
Combining (71) – (73), we come to the conclusion that (63) holds under the restrictions
(R2) and (70).
Denote, by s∗ and s̃∗, the sums s∗ =
∑
i∈M2
i and s̃∗ =
∑
j∈M̃2
j. From the conditions
(R2), we obviously have
(74) s∗ + s̃∗ = 0.
Next, let us verify that equality (74) implies that ξα ≥ 3 for all α ∈ {1, 2, ...,Δ}, where
ξα is the parameter from definition (30). Indeed, inequalities (17) and (18) allow us to
conclude that if ξα ≤ 2 for some α ∈ {1, 2, ...,Δ}, then s∗ + s̃∗ ≥ 1, which contradicts
equality (74).
Now, let us check that if Δ = 2z − 1, 1 ≤ z ≤ r, and z ∈ {r, r − 1} or r ∈ {1, 2},
then there exists some α, α ∈ {1, 2, ...,Δ}, such that ξα ≤ 2. Indeed, when z = r or
r ∈ {1, 2}, the existence of the mentioned parameter α is certain. For z = r − 1, the
existence of the parameter α such that ξα ≤ 2 follows from Remark 2.
Therefore, it remains to check relation (63) under restrictions (R3):
(75) ξα ≥ 3, α ∈ {1, 2, 3, ...,Δ} ,
(76) Δ = 2z − 1,
126 VOLODYMYR I. MASOL AND SVITLANA Y. SLOBODYAN
(77)
∣∣∣M̃1
∣∣∣ = 2r−z − 1 for 1 ≤ z ≤ r − 2, 3 ≤ r < ∞.
In analogy to how it was done in work [3], we make use of Proposition 5 and con-
ditions (75) – (77) to verify that there exists an element j∗, j∗ ∈ M̃1, satisfying the
inequality j∗ ≤ ϕ (n). This allows us to obtain the estimation
(78) S
(Δ)
〈(R 3); γ1,...,γΔ〉 (n, r; Q) ≤ 2r n−z m
(
1 − 1
2r
)[ρ n]( [ρ n] e
ϕ (n)
)ϕ(n)√
ϕ (n).
Relation (78) and inequality
S(Δ) (n, r; Q) ≤
∑
1≤γ1<...<γΔ≤2r−1
S
(Δ)
〈(R 3); γ1,...,γΔ〉 (n, r; Q)
prove (63) under the restrictions (R3).
Analyzing restrictions (Ri), i = 1, 2, 3, it is easy to verify that (63) holds for all possible
values of the parameter s and those values of the parameters s′, i, and j that satisfy (62)
and (R∗), for which Δ ≥ 1. The lemma is proved.
Bibliography
1. V.G. Mikhailov, The limit theorems for the number of nontrivial solutions of a system of
random equations in the field GF(2), Theory of probability and it’s application. XLIII (1998),
no. 3, 598–606. (in Russian)
2. V.I. Masol, Moments of the number of solutions of a system of random Boolean equations,
Random Oper. and Stoch. Equations. 1 (1993), no. 2, 171–179.
3. V.I. Masol, The theorem on the limit distribution of the number of false solutions of a system of
nonlinear random Boolean equations, Theory of probability and it’s application. XLIII (1998),
no. 1, 41–56. (in Russian)
E-mail : vimasol@ukr.net
E-mail : sv yaros@rambler.ru
|