Теория приближений, Вычислительная математика и Численный анализ в новой концепции в свете Компьютерного (вычислительного) поперечника

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 \textit{$\nu _{s} $} with a pessimistic forecast \textit{"it would be very difficult to calculate the accuracy $\nu _{s} $, when $s\ge 10$"} is replaced by an unexpected asymptotic for all $s\ge2$ - 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 $\left\langle X_n\right\rangle$ of nonnegative integers
\begin{equation}\tag{0.1} X_{n+1}=\left(aX_{n} +c\right)\bmod N, n\ge 0, \end{equation}
where \[\begin{split}&{N  -  module   0<N, a-multiplier  0\le a<N,} &{c-    increment    0\le A<N,  X_{0}   -  initial value      0\le X_{0} <N,} \end{split}\] whole numbers $a>1, N>a, \tau\left(a, N\right)\ge 2$ and $\ 1\le \lambda\left(a, N\right)\equiv\frac{{\left(a-1\right)}^{\tau\left(a, N\right)}}{N}<{\left(a-1\right)}^{\tau\left(a, N\right)-1}$ are related by comparisons $\left(a-1\right)^{\tau \left(a, N\right)} \equiv 0\left(\bmod N\right)$ and $\left(a-1\right)^{\tau\left(a, N\right)-1}\not\equiv 0\ \left(\bmod N\right)$.
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\ge 2$ and $\tau \ge 2$ and increasing $N$ find the asymptotic value (all parameters are positive integers)
\begin{equation}\tag{0.2} \sup \left\{\nu _{s} \left(a, N\right):2\le a<N, (a-1)^{\tau} \equiv 0(\bmod N), (a-1)^{\tau -1} \not \equiv 0(\bmod N)\right\}, \end{equation}
where \[\nu_{s} (a, N)=\inf \{\sqrt{m_{1}^{2} +\cdots+m_{s}^{2}}:m=(m_{1},..., m_{s} )\in Z^{s}, m\ne 0, \sum _{j=1}^{s} m_{j} a^{j-1} \equiv 0(\bmod N)\}. \]
Thus, the problem consists in indicating the number $a=a(N)$ with as large a value as possible $\nu _{s} (a,N)$, while for all the $a, N$ and $s$ only ones we know only the inequalities $\nu _{s} (a,N)\le \gamma (s)N^{\frac{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,\ \tau $ and $\lambda $: \[ \begin{split} \mathbf{ST}&:\nu _{2} (a, N; (a-1)^{2}=N)=(a-1)\sqrt{1-2\frac{a-2}{(a-1)^{2}}}=\sqrt{N} \sqrt{1-2\frac{\sqrt{N} -1}{N}},
\mathbf{ST}&(2\le s=\tau ): N^{\frac{1}{s}}(1-(b_{s}-1)N^{-\frac{1}{s}} )=a-b_{s} \le \nu _{s} (a, N;(a-1)^{s} =N)\le
&\le\sqrt{a^{2}+1}=N^{\frac{1}{s}}\sqrt{1+2N^{-\frac{1}{s}}+2N^{-\frac{2}{s}}},
\mathbf{ST}&(2\le s<\tau, \lambda \ge 1): (N\lambda)^{\frac{1}{\tau}}(1-(b_{s}-1)(N\lambda )^{-\frac{1}{\tau}} )=(a-b_{\tau} )\le
&\le\nu _{s} (a, N;(a-1)^{\tau}=N\lambda, 1\le \lambda \le (a-1)^{\tau -s} ) \le \sqrt{a^{2} +1}=
&=(N\lambda )^{\frac{1}{\tau}} \sqrt{1+2(N \lambda )^{-\frac{1}{\tau}} +2(N\lambda )^{-\frac{2}{\tau}}},
\mathbf{ST}&(s>\tau \ge 2, \lambda \ge 1): \nu _{s} (a, N;(a-1)^{\tau}=N\lambda, \lambda \ge 1)\le \sqrt{\sum _{k=0}^{\tau }(\binom{\tau}{k}) ^{2}}, \end{split} \] \textit{where ${(-b}_m)$ is the largest modulo negative binomial coefficient in the expansion of ${(a-1)}^m$ in powers of $a: b_{2} =2, b_{3} =3$, $b_{4} =4, b_{5} =10, b_{6} =20, b_{7} =35, b_{8} =56, b_{9} =126, b_{10} =252, b_{11} =462, b_{12} =792, b_{13} =1716, b_{14} =3432, b_{15} =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 $\overline{{\gamma}_N}$ have the form ${\overline{{\gamma}_N}\cdot N}^{\frac{1}{s}}\le {\nu }_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) \textit{The basic characteristic of the randomness of ${\nu}_s(a,N)$ must and can be so large as ever for all $s\ge2$.}

In this case, the main part $N^{\frac{1}{s}}$ of the $s$-dimensional accuracy of the generator $\left\langle{X}_n\right\rangle$ 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 $\nu_s(a,N)$ should be?". Of course, this is a separate problem, perhaps even non-trivial.
The asymptotically exact upper bounds $\nu_s\left(a, N\right)\le \overline{\overline{\gamma_N}}\cdot N^{\frac{1}{s}} \left(\overline{\overline{\gamma_N}}\to 1\right)$ act as guarantors not to take $N$ and ${\nu }_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 ${\nu}_s(a,N)$ but only approximate boundaries in the contexts required by the context.
If we pass from the intangible estimate of ${\nu}_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 $X_0,\dots, X_{N-1}$ as a bijective map onto itself in such a way that for any segment $[\alpha, \beta]$ of $[0,1]$ the number of $\frac{X_n}{N}$ numbers $[\alpha, \beta]$ should be close $(\beta-\alpha)$, then it is appeared that any Lehmer sequence with maximal period initially uniformly distributed with unimprovable rate of deviation $\frac{1}{N}$, which can be attributed for remarkable property. Thereby, the problem is connected whith indicator of randomness of $\nu_s(a,N)$.