Elementary construction of the linear congruent Lehmer sequence with the degree of randomness that is required by the spectral test of Coveyou and MacPherson

Abstract

The ideas of a random number and a random sequence can not be completely formalized. Instead, for whatever
reason, arrays of random number generators are proposed, they are used to create methods for testing them for randomness.
Sequences that pass such an examination are declared random, and each of its elements is a random number, as a result there
are various types of randomness, as many many tests.
The article is devoted to the complete solution of the posed problems, objects and a long, respectable history of research with
instructive conclusions, in the aggregate, we hope, in the higher echelons of Computer Sciences: Lehmer’s Generator (1949) is
one of the most popular if not the most popular sensor and the spectral test of 1965 by Coveyou and MacPherson as "the most
perfect test available", both in conjunction with the 50-year history, in the development detailed in all editions of the monograph
"The Art of Programming" by Donald Erwin Knuth from 1969 to the present, has become being in constant development.
Namely, a little that clarifies the one-sided estimate from above of the main numerical characteristic of randomness νs with
a pessimistic forecast "it would be very difficult to calculate the accuracy νs , when s ≥ 10 " is replaced by an unexpected
asymptotic for all s ≥ 2 - what the problem consisted in ideally, and this is its solution.
The generator of random numbers of Lehmer or the Linear congruential sequence of the maximal period is, by definition,
the recurrence sequence hXni of nonnegative integers
Xn+1 = (aXn + c) mod N, n ≥ 0, (0.1)
where
N − module 0 < N, a − multiplier 0 ≤ a < N,
c − increment 0 ≤ A < N, X0 − initialvalue 0 ≤ X0 < N,
whole numbers a > 1, N > a, τ (a, N) ≥ 2 and 1 ≤ λ (a, N) ≡
(a−1)τ(a,N)
N < (a − 1)τ(a,N)−1
are related by comparisons
(a − 1)τ(a,N) ≡ 0 (modN) and (a − 1)τ(a,N)−1
6≡ 0 (modN) .
As it often occurs, in this case too, the whole problem is reduced to a clearly formulated mathematical problem (all motivations
and details are given in the text of the article): for given s ≥ 2 and τ ≥ 2 and increasing N find the asymptotic value (all
parameters are positive integers)
sup
νs (a, N) : 2 ≤ a < N, (a − 1)τ ≡ 0(modN), (a − 1)τ−1
6≡ 0(modN)

, (0.2

where
νs (a, N) = inf



q
m2
1 + · · · + m2
s
: m = (m1, ..., ms) ∈ Z
s
, m 6= 0,
Xs
j=1
mja
j−1 ≡ 0 (modN)



.
Thus, the problem consists in indicating the number a = a(N) with as large a value as possible νs(a, N) , while for all the
a, N and s only ones we know only the inequalities νs(a, N) ≤ γ(s)N
1
s . As with any upper bound, this inequality can be
greatly overestimated, so the problem has no solution.
In this paper, new and final results are obtained on spectral testing (ST), which are asymptotic in nature, depending on all
possibilities and, therefore, providing a complete solution of the problem under study, the relations between the parameters s, τ
and λ :
ST : ν2

a, N; (a − 1)2 = N

= (a − 1) s
1 − 2
a − 2
(a − 1)2 =
√
N
s
1 − 2
√
N − 1
N
,
ST (2 ≤ s = τ) : N
1
s

1 − (bs − 1) N
− 1
s

= a − bs ≤ νs (a, N; (a − 1)s = N) ≤
≤
p
a
2 + 1 = N
1
s
q
1 + 2N
− 1
s + 2N
− 2
s ,
ST (2 ≤ s < τ, λ ≥ 1) : (Nλ)
1
τ

1 − (bs − 1) (Nλ)
− 1
τ

= (a − bτ ) ≤
≤ νs

a, N; (a − 1)τ = Nλ, 1 ≤ λ ≤ (a − 1)τ−s

≤
p
a
2 + 1 =
= (Nλ)
1
τ
q
1 + 2 (Nλ)
− 1
τ + 2 (Nλ)
− 2
τ ,
ST (s > τ ≥ 2, λ ≥ 1) : νs (a, N; (a − 1)τ = Nλ, λ ≥ 1) ≤
vuutXτ
k=0
τ
k
2
,
where (−bm) is the largest modulo negative binomial coefficient in the expansion of (a − 1)m in powers of a : b2 = 2, b3 = 3 ,
b4 = 4, b5 = 10, b6 = 20, b7 = 35, b8 = 56, b9 = 126, b10 = 252, b11 = 462, b12 = 792, b13 = 1716, b14 = 3432, b15 = 6435, ... etc.
All the constructions on this subject in D. Knuth’s monograph "The Art of Programming" are semi-empirical in nature -
theoretical positions are put forward on the basis of which statistical experiments are conducted. In addition, D. Knuth, using
the example of seemingly undoubtedly random selection of parameters in the "mid-squares" method, von Neumann, comes to
the conclusion that purely experimental searches are unreliable and that some kind of theory is always needed.
We conducted a purely theoretical study.
As follows from the lower bounds in all ST-statements, all of them with an accuracy tending to 1 with increasing N explicitly
written out (which is crucial in practical applications) of the factor γN have the form γN · N
1
s ≤ νs(a, N) .
This means that simultaneously solved two problems (with a single limitation - the computing capabilities of computer
technology)
a) The number of random numbers N must and can be arbitrarily large,
b) The basic characteristic of the randomness of νs(a, N) must and can be so large as ever for all s ≥ 2 .
In this case, the main part N
1
s of the s -dimensional accuracy of the generator hXni due to the small exponent 1/s ,
known as the "curse of dimension", requires N in its inverse to s to be large (this repeats the velocity from a uniform grid in
numerical integration).
A new problem arises: "In each concrete case of using the random number generator (0.1)–(0.2) find out how big N and
νs(a, N) should be?". Of course, this is a separate problem, perhaps even non-trivial.
The asymptotically exact upper bounds νs (a, N) ≤ γN · N
1
s

γN → 1

act as guarantors not to take N and νs(a, N)
unjustifiably large with accompanying high implementation costs.
With the exception of the case s = 2 , all the ST-statements are not exact, but asymptotic, which does not restrict applications
in any way-it does not require exact values of N and νs(a, N) but only approximate boundaries in the contexts required by
the context.
If we pass from the intangible estimate of νs(a, N) directly to the randomness check through the "frequency" (this property
is also called the uniform distribution, from randomness it takes a lot more), where the difficulty, even the extra difficulty of the
posed problem, in which the numbers 0, 1, ..., N −1 must be rearranged in another order X0, . . . , XN−1 as a bijective map onto
itself in such a way that for any segment [α, β] of [0, 1] the number of Xn
N
numbers [α, β] should be close (β − α) , then it
is appeared that any Lehmer sequence with maximal period initially uniformly distributed with unimprovable rate of deviation
1
N
, which can be attributed for remarkable property. Thereby, the problem is connected whith indicator of randomness of
νs(a, N)