\input style
\chapnotrue\chapno=3\subchno=3\subsubchno=3
MENXSHEJ CHEM~$(a+6)/m$. tOCHNOE ZNACHENIE MOZHNO |FFEKTIVNO VYCHISLITX S
POMOSHCHXYU VYRAZHENIYA~(17), ISPOLXZUYA LEMMY~B I~C.
\proofend
iZ SOOTNOSHENIYA~(40) VYTEKAYUT NEKOTORYE ZASLUZHIVAYUSHCHIE UPOMINANIYA SLEDSTVIYA.
vO-PERVYH, ONO DOKAZYVAET, CHTO NADO IZBEGATX MALYH ZNACHENIJ~$a$. s DRUGOJ
STORONY, BOLXSHIE ZNACHENIYA~$a$ ESHCHE NE GARANTIRUYUT TOGO, CHTO KORRELYACIYA
BUDET MALA, KAK BYLO POKAZANO V PRIMERE~1; OSHIBKA VYRAZHENIYA~(40)
MOZHET DOSTIGATX~$a/m$, I TOGDA PRI BOLXSHIH ZNACHENIYAH~$a/m$ PRIBLIZHENIE
STANOVITSYA PLOHIM. eSLI~$a\approx\sqrt{m}$, ZNACHENIYA KO|FFICIENTA
POSLEDOVATELXNOJ KORRELYACII OGRANICHENY VELICHINOJ~$2/\sqrt{m}$.

sOOTNOSHENIE~(40) POMOGAET I PRI VYBORE ZNACHENIYA~$c$. dO SIH POR MY ZNALI
OTNOSITELXNO~$c$ TOLXKO ODNO: CHISLA~$c$ I~$m$ DOLZHNY BYTX, VZAIMNO
PROSTYMI. eSLI, KROME TOGO,
$$
\eqalign{
{c\over m} \approx {1\over 2}-{1\over 6}\sqrt{3}&\approx 0.21132\,48654\,051871 \approx \cr
                                                &\approx {\it (0.15414\,54272\,33746\,34354\,55716)}_8, \cr
}
\eqno(41)
$$
KO|FFICIENT POSLEDOVATELXNOJ KORRELYACII BUDET NEBOLXSHIM, TAK KAK KORNI
URAVNENIYA~$1-6x+6x^2=0$ RAVNY~${1\over 2}\pm{1\over 6}\sqrt{3}$. eTIM
KRITERIEM MOZHNO POLXZOVATXSYA, ESLI OTSUTSTVUYUT DRUGIE SOOBRAZHENIYA
OTNOSITELXNO VYBORA~$c$.

dO SIH POR RECHX SHLA O KORRELYACII MEZHDU~$X_n$ I~$X_{n+1}$. zhELATELXNO TAKZHE
IMETX NIZKUYU KORRELYACIYU MEZHDU~$X_n$ I~$X_{n+2}$, I VOOBSHCHE BYLO BY NEPLOHO,
ESLI BY KORRELYACIYA MEZHDU~$X_n$ I~$X_{n+t}$ BYLA NIZKOJ, SKAZHEM,
DLYA~$1\le t \le 10$. rANEE BYLO POKAZANO (SM.\ FORMULU~(3.2.1-6)), CHTO
$$
X_{n+t}=(a_t X_n+c_t) \bmod m,
\eqno(42)
$$
GDE
$$
a_t=a^t \bmod m, \qquad c_t=(a^t-1)c/(a-1)\bmod m.
\eqno(43)
$$
\emph{s POMOSHCHXYU PODVEDENNYH VYSHE FORMUL MOZHNO VYCHISLITX KO|FFICIENT
KORRELYACII MEZHDU~$X_n$ I~$X_{n+t}$, ESLI VMESTO~$a$  I~$c$
PODSTAVITX~$a_t$ I~$c_t$.} kONECHNO, $c_t$ UZHE NE BUDET UDOVLETVORYATX
USLOVIYU~(41), NO S |TIM PRIDETSYA SMIRITXSYA.

pRIBLIZHENNOE VYRAZHENIE~(40) VPERVYE POLUCHIL r.~kOV|YU ({\sl JACM,\/} {\bf 7}
(1960), 72--74) V REZULXTATE USREDNENIYA PO VSEM \emph{DEJSTVITELXNYM
CHISLAM}~$x$ MEZHDU~$0$ I~$m$, A NE TOLXKO PO CELYM ZNACHENIYAM (SM.~UPR.~21).
mETODY, POZVOLYAYUSHCHIE POLUCHITX TOCHNYJ REZULXTAT, BYLI POZDNEE RAZVITY
m.~gRINBERGEROM
({\sl Math. Comp.,\/} {\bf 15} (1961), 383--389) I b.~yaNSSONOM
({\sl BIT,\/} {\bf 4} (1964), 6--27). v IH FORMULAH SUMMY dEDEKINDA NE
ISPOLXZOVALISX. yaNSSON SOSTAVIL TABLICY DLYA KO|FFICIENTA POSLEDOVATELXNOJ
KORRELYACII, NO, K SOZHALENIYU, ON RASSMATRIVAL SLISHKOM PROSTYE MNOZHITELI,
%%102
POLXZOVATXSYA KOTORYMI NE REKOMENDUETSYA. oN POKAZAL NAPRIMER, CHTO
KO|FFICIENT KORRELYACII MEZHDU~$X_n$ I~$X_{n+t}$ MENXSHE~$0.000003$ DLYA
DATCHIKA S~$m=2^{35}$, $a=2^{24}+5$, $c=1$ PRI VSEH~$t\le 2500$. s POMOSHCHXYU
SPEKTRALXNOGO TESTA (SM.~P.~3.3.4) MOZHNO POKAZATX, CHTO POLXZOVATXSYA |TIM
DATCHIKOM NE SLEDUET; TEM NE MENEE REZULXTAT yaNSSONA---HOROSHEE SVIDETELXSTVO
TOGO, CHTO U VYBRANNOGO NAUGAD DATCHIKA, OSNOVANNOGO NA LINEJNOM
KONGRU|NTNOM METODE I OBLADAYUSHCHEGO VYSOKOJ MOSHCHNOSTXYU, MOZHNO
OZHIDATX NIZKUYU POSLEDOVATELXNUYU KORRELYACIYU. [\emph{zAMECHANIE.} yaNSSON
TAKZHE POLUCHIL FORMULY DLYA KO|FFICIENTA POSLEDOVATELXNOJ KORRELYACII V
POSLEDOVATELXNOSTYAH S~$c=0$ I MNOZHITELEM, OBESPECHIVAYUSHCHIM MAKSIMALXNYJ
PERIOD PRI~$m=2^e$. eTI REZULXTATY V SUSHCHNOSTI ANALOGICHNY RASSMOTRENNYM
V |TOJ KNIGE; SM.~UPR.~3.2.1 2-9.]

sUMMY dEDEKINDA~$\sigma(h, k, c)$ I ZAKON VZAIMNOSTI (DLYA
CHASTNOGO SLUCHAYA~$c=0$) BYLI VPERVYE RASSMOTRENY r.~dEDEKINDOM V~1892~G.\
V EGO RABOTE, POSVYASHCHENNOJ |LLIPTICHESKIM FUNKCIYAM. eTA FUNKCIYA
ISPOLXZOVALASX MNOGIMI AVTORAMI; SPISOK LITERATURY PO DANNOMU VOPROSU
MOZHNO NAJTI V RABOTAH u.~dITERA
[{\sl Journal f\"ur die reine und angewandte Mathematik,\/} {\bf 201}
(1959), 37--70], A TAKZHE g.~rADEMAHERA I~e.~uAJTM|NA
[{\sl American Journal of Mathematics,\/} {\bf 63} (1941), 377--407].

eSHCHE NESKOLXKO \emph{APRIORNYH} TESTOV BUDET OPISANO V UPRAZHNENIYAH K
|TOMU RAZDELU. gLAVNYJ VYVOD, KOTORYJ SLEDUET IZ NIH, ZAKLYUCHAETSYA V
SLEDUYUSHCHEM: \emph{MNOZHITELX V LINEJNOM KONGRU|NTNOM METODE DOLZHEN BYTX
DOSTATOCHNO VELIK.} sM. TAKZHE UPR.~3.3.4-7, GDE PRIVODITSYA DALXNEJSHEE
RAZVITIE TEOREMY~P.

\excercises (pervaya chast')
\ex[m07] oB®YASNITE, POCHEMU VYRAZHENIE~(7) RAVNO CHISLU ZNACHENIJ~$x$,
DLYA KOTORYH~$s(x)<x$, $0\le x < m$.

\ex[m24] dOKAZHITE SPRAVEDLIVOSTX SOOTNOSHENIYA~(12)

\ex[vm22] rAZLOZHITE V RYAD fURXE (VYRAZITE CHEREZ SINUSY I KOSINUSY)
FUNKCIYU~$f(x)=\dlp x \drp$.

\rex[m18] kAKOVO NAIBOLXSHEE VOZMOZHNOE ZNACHENIE~$d$ (V OBOZNACHENIYAH
TEOREMY~P), ESLI~$m=10^{10}$, A MOSHCHNOSTX DATCHIKA RAVNA~$10$?

\ex[M21] vYVEDITE FORMULU~(17).

\ex[m27] pUSTX~$hh'+kk'=1$ (a)~pOKAZHITE, NE POLXZUYASX LEMMAMI~B I~C, CHTO
$$
\sigma(h, k, c)=\sigma(h, k, 0)+12\sum_{0\le j < c}\dlp{h' j \over k} \drp + 6 \dlp {h' c \over k} \drp
$$
DLYA VSEH~$c\ge 0$. (b)~pOKAZHITE, CHTO PRI~$0 \le c < h$ I~$0 \le c < k$
$$
\dlp {h' c \over k} \drp + \dlp {k' c \over h} \drp = {c \over hk}.
$$
(c)~v PREDPOLOZHENIYAH LEMMY~B POKAZHITE SPRAVEDLIVOSTX RAVENSTVA~(20).

\rex[m24] pREDLOZHITE DOKAZATELXSTVO ZAKONA VZAIMNOSTI~(19) PRI~$c=0$,
OSNOVANNOE NA IDEYAH UPR.~1.2.4-45.

%% 103
\rex[M34] pUSTX
$$
\rho(p, q, r)=12 \sum_{0\le j < r} \dlp{jp\over r}\drp \dlp{jq\over r}\drp.
$$
oBOBSHCHAYA METOD, ISPOLXZOVANNYJ PRI DOKAZATELXSTVE LEMMY~B, DOKAZHITE
SLEDUYUSHCHEE KRASIVOE SOOTNOSHENIE (POLUCHENNOE rADEMAHEROM): "eSLI~$p$, $q$
I~$r$ POPARNO VZAIMNO PROSTY, TO
$$
\rho(p, q, r)+\rho(q, r, p)+\rho(r, p, q)={p\over qr}+{q\over rp}+{r\over pq}=3."
$$
(zAKON VZAIMNOSTI DLYA SUMM  dEDEKINDA PRI~$c=0$ YAVLYAETSYA CHASTNYM
SLUCHAEM |TOGO RAVENSTVA PRI~$r=1$.)

\ex[M40] sUSHCHESTVUET LI PROSTOE DOKAZATELXSTVO SOOTNOSHENIYA
rADEMAHERA (SM.~UPR.~8), KOTOROE YAVLYAETSYA CHASTNYM SLUCHAEM DOKAZATELXSTVA,
RASSMOTRENNOGO V UPR.~7?

\ex[m20] dOKAZHITE SOOTNOSHENIYA~(34) OB IZMENENII ZNAKA PARAMETROV, VHODYASHCHIH
V~$\sigma(h, k, c)$.

\ex[M30] fORMULY V TEKSTE DAYUT VOZMOZHNOSTX VYCHISLITX~$\sigma(h, k, c)$,
KOGDA~$h$ I~$k$ VZAIMNO PROSTY. v OBSHCHEM SLUCHAE POLOZHIM~$hh'\equiv d \pmod{k}$,
GDE~$d$---NAIBOLXSHIJ OBSHCHIJ DELITELX~$h$ I~$k$. pOKAZHITE, CHTO
$$
\sigma(h, k, c)=\sigma(h/d, k/d, \floor{c/d})+\delta,
$$
GDE~$\delta=0$ PRI~$c \bmod d =0$ I
$$
\delta=6\dlp{\floor{c/d} h'd \over k}\drp
$$
PRI~$c\bmod d\ne 0$.

\ex[m24] pOKAZHITE, CHTO ESLI~$h$ I~$k$ VZAIMNO PROSTY,
TO~$\abs{\sigma(h, k, c)}<(k-1)(k-2)/k$.

\ex[m22] v~(37) PRIVEDENO \emph{PRIBLIZHENNOE} ZNACHENIE DLYA KO|FFICIENTA
POSLEDOVATELXNOJ KORRELYACII PRI~$m=2^{35}$, $a=2^{34}+1$, $c=1$. chEMU
RAVNO TOCHNOE ZNACHENIE?

\rex[m24] pRI PROVERKE POSLEDOVATELXNOJ KORRELYACII U LINEJNOGO
KONGRU|NTNOGO DATCHIKA S~$m=2^{35}$, $a=2^{18}+1$, $c=1$ BYLI ISSLEDOVANY
TRI OTREZKA POSLEDOVATELXNOSTI PO 1000~CHISEL V KAZHDOM; VO VSEH SLUCHAYAH
KO|FFICIENT KORRELYACII POLUCHILSYA DOVOLXNO BOLXSHIM: OT~$0.2$ DO~$0.3$.
kAKIM BUDET KO|FFICIENT POSLEDOVATELXNOJ KORRELYACII DLYA |TOGO DATCHIKA PO
VSEMU PERIODU V $2^{35}$~CHISEL?

\ex[m22] oPREDELITE TOCHNOE ZNACHENIE KO|FFICIENTA
POSLEDOVATELXNOJ KORRELYACII V CHASTNOM SLUCHAE~$a=1$.

\ex[m24] kAK MY UZHE ZNAEM, LINEJNYJ, KONGRU|NTNYJ METOD DAET
PLOHIE SLUCHAJNYE CHISLA PRI~$a=1$. pOKAZHITE S POMOSHCHXYU TEOREMY~P, CHTO,
NESMOTRYA NA |TO, MOZHNO PODOBRATX TAKOE S, CHTO VEROYATNOSTX VYPOLNENIYA
NERAVENSTVA~$(X_{n+1}<X_n)$ BUDET OCHENX BLIZKA K~$1/2$ DAZHE PRI~$a=1$.
mOZHNO TAKZHE PODOBRATX TAKOE~$c$, CHTO KO|FFICIENT POSLEDOVATELXNOJ
KORRELYACIYA BUDET OCHENX NIZKIM. mOZHNO LI VYBRATX ZNACHENIE~$c$ TAK, CHTOBY
VYPOLNYALISX OBA |TI USLOVIYA ODNOVREMENNO?

\ex[M21] oB®YASNITE, KAK VYBRATX TAKOE ZNACHENIE~$a$, CHTOBY KAK~$c$, TAK
I~$c_2$ UDOVLETVORYALI PRIBLIZHENNOMU SOOTNOSHENIYU~(41), GDE~$c_2$---PRIRASHCHENIE
POSLEDOVATELXNOSTI, ZADANNOE~(43).

\rex[M35] pOLOZHIM
$$
S(h, k, c, z)=\sum_{0\le j <z}\dlp{hj+c\over k}\drp.
$$
pRI VZAIMNO PROSTYH~$h$ I~$k$ POLUCHITE "FORMULY VZAIMNOSTI", KOTORYE
POMOGUT |FFEKTIVNO VYCHISLYATX ZNACHENIYA |TOJ FUNKCII, PODOBNO TOMU, KAK S
POMOSHCHXYU LEMM~B I~C VYCHISLYAYUTSYA ZNACHENIYA~$\sigma(h, k, c)$.
[\emph{uKAZANIE:} SM.~UPR.~6.]

%% 104
\rex[M35] \emph{pROVERKU SERIJ,} OPISANNUYU V PREDYDUSHCHEM RAZDETO MOZHNO
PROVODITX NA POLNOM PERIODE. pUSTX~$\alpha$, $\beta$, $\gamma$,
$\delta$---CELYE CHISLA, PRICHEM~$0\le\alpha<\beta\le m$,
$0\le\gamma<\delta\le m$. vYVEDITE SOOTNOSHENIE DLYA VEROYATNOSTI TOGO,
CHTO~$\alpha\le X_n<\beta$ I~$\gamma\le X_{n+1}<\delta$.

\ex[M24] oBOBSHCHITE~(26) TAKIM oBRAZOM, CHTOBY POLUCHALOSX VYRAZHENIE DLYA~$\sigma(h, k, c)$.

\excercises (vtoraya chast')
vO MNOGIH SLUCHAYAH TOCHNYE RASCHETY S CELYMI CHISLAMI SLISHKOM SLOZHNY, ODNAKO
MOZHNO POPYTATXSYA PRI OPREDELENII VEROYATNOSTEJ PROVODITX USREDNENIE NE PO
CELYM ZNACHENIYAM, A PO VSEMU INTERVALU IZMENENIYA~$x$. hOTYA TAKIE REZULXTATY
BUDUT PRIBLIZHENNYMI, ONI PROLXYUT SVET NA OBSUZHDAEMYJ PREDMET.

uDOBNEE VSEGO IMETX DELO S CHISLAMI~$U_n$, ZAKLYUCHENNYMI MEZHDU NULEM
I EDINICEJ; DLYA LINEJNYH KONGRU|NTNYH POSLEDOVATELXNOSTEJ~$U_n=X_n/m$, TAK
CHTO~$U_{n+1}=\{aU_n+\theta\}$, GDE~$\theta=c/m$, A~$\{x\}$ OZNACHAET~$x\bmod 1$.
nAPRIMER, FORMULA DLYA KO|FFICIENTA POSLEDOVATELXNOJ KORRELYACII
PRINIMAET VID
$$
C=\left(\int_0^1 x\{ax+\theta\}\,dx-\left(\int_0^1 x\, dx\right)^2\right)
\bigg/ \left(\int_0^1 x^2\, dx-\left(\int_0^1 x\,dx\right)^2\right).
$$

\rex[BM23] (r. kOV|YU.) chEMU RAVNO~$C$ V TOLXKO CHTO PRIVEDENNOJ FORMULE?

\rex[M22] pUSTX~$a$---CELOE CHISLO I~$0\le\theta<1$.
eSLI~$x$---DEJSTVITELXNOE CHISLO, NAHODYASHCHEESYA MEZHDU~$0$ I~$1$,
A~$s(x)=\{ax+\theta\}$, TO KAKOVA VEROYATNOSTX, CHTO~$s(x)<x$? (eTO ANALOG
TEOREMY~P DLYA DEJSTVITELXNYH CHISEL.)

\ex[M28] pREDYDUSHCHEE UPRAZHNENIE DAET VEROYATNOSTX TOGO, CHTO~$U_{n+1}<U_n$.
kAKOVA VEROYATNOSTX TOGO, CHTO~$U_{n+2}<U_{n+1}<U_n$, ESLI~$U_n$---SLUCHAJNYE
DEJSTVITELXNYE CHISLA,  ZAKLYUCHENNYE MEZHDU NULEM I EDINICEJ?

\ex[M29] sOHRANYAYA USLOVIYA PREDYDUSHCHEJ ZADACHI I POLOZHIV~$\theta=0$, POKAZHITE,
 CHTO VEROYATNOSTX VYPOLNENIYA NERAVENSTV~$U_n>U_{n+1}>\cdots>U_{n+t-1}$ V
TOCHNOSTI RAVNA
$$
{1\over t!}\left(1+{1\over a}\right)\ldots\left(1+{t-2\over a}\right).
$$
kAKOVA SREDNYAYA DLINA UBYVAYUSHCHEGO RYADA CHISEL, NACHINAYUSHCHEGOSYA SO
SLUCHAJNO VYBRANNOGO MEZHDU NULEM I EDINICEJ CHISLA~$U_n$?

\rex[M25] pUSTX~$\alpha$, $\beta$, $\gamma$, $\delta$---DEJSTVITELXNYE
CHISLA, PRICHEM~$0\le\alpha<\beta\le1$, $0\le \gamma<\delta\le 1$. kAKOVA
VEROYATNOSTX TOGO, CHTO~$\alpha\le x < \beta$ I~$\gamma\le s(x)<\delta$,
ESLI VYPOLNENY PREDPOLOZHENIYA UPR.~22?  (eTO ANALOG UPR.~19 DLYA
DEJSTVITELXNYH CHISEL.)

\ex[M21] rASSMOTRIM DATCHIK, OSNOVANNYJ NA METODE fIBONACHCHI
S~$U_{n+1}=\{U_n+U_{n-1}\}$. pREDPOLAGAYA, CHTO~$U_1$ I~$U_2$ VYBIRAYUTSYA
NEZAVISIMO SLUCHAJNYM OBRAZOM MEZHDU NULEM I EDINICEJ, NAJDITE VEROYATNOSTX
TOGO, CHTO~$U_1<U_2<U_3$, $U_1<U_3<U_2$, $U_2<U_1<U_3$ I~T.~D.
[\emph{uKAZANIE:} RAZDELITX "EDINICHNYJ KVADRAT", T.~E.\ TOCHKI NA
PLOSKOSTI~$\{\,(x, y) \mid 0\le x, y<1\,\}$, NA SHESTX CHASTEJ, V
ZAVISIMOSTI OT SOOTNOSHENIYA MEZHDU~$x$, $y$ I~$\{x+y\}$, I OPREDELITX
PLOSHCHADX KAZHDOJ CHASTI.]

\ex[M27] pUSTX ISHODNYE CHISLA DLYA DATCHIKA, OPISANNOGO V PREDYDUSHCHEM
UPRAZHNENII, VYBIRAYUTSYA NEZAVISIMO V EDINICHNOM KVADRATE, POSLE CHEGO BOLXSHEE
IZ NIH BERETSYA V KACHESTVE~$U_0$, A MENXSHEE---$U_1$. oPREDELITE VEROYATNOSTX
TOGO, CHTO~$U_1$ OKAZHETSYA NACHALXNOJ TOCHKOJ VOZRASTAYUSHCHEGO RYADA DLINY~$k$,
T.~E.~$U_0>U_1<\ldots<U_k>U_{k+1}$. sRAVNITE REZULXTAT S SOOTVETSTVUYUSHCHIMI
VEROYATNOSTYAMI DLYA SLUCHAJNOJ POSLEDOVATELXNOSTI.

\rex[M35] dLYA LINEJNOGO KONGRU|NTNOGO DATCHIKA MOSHCHNOSTI~$2$ VYPOLNYAETSYA
USLOVIE~$X_{n-1}-2X_n+X_{n+1}\equiv (a-1)c \pmod{m}$
(SM.~FORMULU~(3.2.1.3-5)). rASSMOTRITE DATCHIK, KOTORYJ YAVLYAETSYA
NEPRERYVNYM ANALOGOM, POLOZHIV~$U_{n+1}=\{\alpha+2U_n-U_{n-1}\}$. tAK ZHE
KAK V UPR.~26, RAZDELITE EDINICHNYJ KVADRAT
%% 105
NA CHASTI, DOKAZYVAYUSHCHIE VOZMOZHNYE SOOTNOSHENIYA MEZHDU~$U_{n-1}$,
$U_n$I~$U_{n+1}$ DLYA KAZHDOJ PARY~$(U_{n-1}, U_n)$. sUSHCHESTVUET LI
ZNACHENIE~$\alpha$, PRI KOTOROM KAZHDOE IZ SHESTI VOZMOZHNYH SOOTNOSHENIJ MEZHDU
|TIMI CHISLAMI OSUSHCHESTVLYAETSYA S VEROYATNOSTXYU~$1/6$, ESLI~$U_{n-1}$ I~$U_n$
VYBIRAYUTSYA SLUCHAJNO V EDINICHNOM
KVADRATE?

\subsubchap{sPEKTRALXNYJ TEST} % 3.3.4
vAZHNYJ TEST DLYA PROVERKI SLUCHAJNOSTI POLUCHENNYH NA evm CHISLOVYH
POSLEDOVATELXNOSTEJ SFORMULIROVALI V 1965~G.\ r.~kOV|YU I~r.~mAKFERSON.
eTOT TEST ZAMECHATELEN TEM, CHTO VSE IZVESTNYE PLOHIE DATCHIKI, OSNOVANNYE
NA LINEJNOM KONGRU|NTNOM METODE, BYLI IM \emph{ZABRAKOVANY,} V TO VREMYA,
KAK VSE HOROSHIE DATCHIKI PROSHLI UDOVLETVORITELXNO! bEZUSLOVNO, |TO NAIBOLEE
SOVERSHENNYJ IZ IMEYUSHCHIHSYA TESTOV, V SVYAZI S CHEM ON ZASLUZHIVAET OSOBOGO VNIMANIYA.

sPEKTRALXNYJ TEST OBLADAET SVOJSTVAMI KAK "|MPIRICHESKIH", TAK I
"TEORETICHESKIH" TESTOV, RASSMOTRENNYH V PREDYDUSHCHIH RAZDELAH. kAK I V
TEORETICHESKIH TESTAH, V NEM RASSMATRIVAYUTSYA VELICHINY, USREDNENNYE PO VSEMU
PERIODU. s DRUGOJ STORONY, DLYA POLUCHENIYA REZULXTATOV ISPYTANIJ TREBUYUTSYA
MASHINNYE RASCHETY, CHTO DELAET EGO POHOZHIM NA |MPIRICHESKIE TESTY.

oBOSNOVANIE |TOGO TESTA TREBUET ISPOLXZOVANIYA MATEMATIKI V ZNACHITELXNYH
DOZAH. chITATELYU BEZ OSOBOJ SKLONNOSTI K MATEMATIKE REKOMENDUETSYA PEREJTI
PRYAMO K PODPUNKTU~D DANNOGO PUNKTA, GDE PRIVODITSYA OPISANIE VPOLNE
KONKRETNOGO SPEKTRALXNOGO TESTA.

\section{A.~tEORIYA, LEZHASHCHAYA V OSNOVE TESTA}. mATEMATICHESKIM OBOSNOVANIEM
SPEKTRALXNOGO TESTA SLUZHIT "KONECHNOE PREOBRAZOVANIE fURXE" FUNKCII,
OPREDELENNOJ NA KONECHNOM MNOZHESTVE. oDNOMERNYJ SLUCHAJ KONECHNOGO
PREOBRAZOVANIYA fURXE UZHE ISPOLXZOVALSYA V PREDYDUSHCHEM RAZDELE PRI
DOKAZATELXSTVE LEMMY~3.3.3~B; RASSMOTRIM TEPERX TEHNIKU PREOBRAZOVANIYA
fURXE V OBSHCHEM SLUCHAE.

dLYA LYUBOJ PRINIMAYUSHCHEJ KOMPLEKSNYE ZNACHENIYA
FUNKCII~$F(t_1, t_2,~\ldots, t_n)$, OPREDELENNOJ DLYA VSEH KOMBINACIJ CELYH
CHISEL~$t_k$, GDE~$0\le t_k < m$ PRI~$1\le k \le n$, VVEDEM
\dfn{PREOBRAZOVANIE fURXE}
$$
f(s_1, s_2, \ldots, s_n)=
\sum_{0\le t_1,\ldots, t_n<m} \exp\left({-2\pi i \over m}
(s_1t_1+\cdots+s_nt_n)\right) F(t_1, \ldots, t_n).
\eqno(1)
$$

fUNKCIYA~$f$ OPREDELENA DLYA VSEH KOMBINACIJ CELYH~$s_k$; |TO PERIODICHESKAYA
FUNKCIYA V TOM SMYSLE,
CHTO~$f(s_1,~\ldots, s_n)=f(s_1 \bmod m,~\ldots, s_n \bmod m)$. chTOBY
SVYAZATX |TO OPREDELENIE S
%% 106
FORMULAMI PREDYDUSHCHEGO RAZDELA, OTMETIM, CHTO
$$
\exp\left({-2\pi i \over m} (s_1 t_1 + s_2 t_2 + \cdots + s_n t_n)\right)
=\omega^{-(s_1t_1+s_2t_2+\cdots+s_nt_n)},
$$
ESLI~$\omega=e^{2\pi i/m}$---KORENX $m\hbox{-J}$~STEPENI IZ EDINICY.
tERMIN "PREOBRAZOVANIE" V DANNOM SLUCHAE OPRAVDAN, TAK KAK ISHODNUYU
FUNKCIYU~$F(t_1,~\ldots, t_n)$ MOZHNO VOSSTANOVITX PO EE
PREOBRAZOVANIYU~$f(s_1,~\ldots, s_n)$ I PREDSTAVITX V SLEDUYUSHCHEM VIDE (SM.~UPR.~1):
$$
F(t_1,~\ldots, t_n)={1\over m^n}\sum_{0\le s_1, \ldots, s_n<m}
\exp\left({2\pi i\over m} (s_1t_1+\cdots+s_nt_n)\right) f(s_1,~\ldots, s_n).
\eqno(2)
$$
eTU FORMULU MOZHNO ZAPISATX, ISPOLXZUYA SINUSY I KOSINUSY DLYA BOLXSHEGO
SHODSTVA S BESKONECHNYMI RYADAMI fURXE. vELICHINA~$(1/m^n)f(s_1,~\ldots, s_n)$
YAVLYAETSYA AMPLITUDOJ $n\hbox{-MERNOJ}$ KOMPLEKSNOJ PLOSKOJ VOLNY S
CHASTOTAMI~$s_1/m$,~\dots, $s_n/m$, ESLI~$F(t_1,~\ldots, t_n)$ PREDSTAVLENA
V VIDE~(2).

iZ SOOTNOSHENIJ~(1) I~(2) SLEDUET, CHTO TEORETICHESKI MOZHNO OPREDELITX LYUBYE
SVOJSTVA~$F$ PO EE PREOBRAZOVANIYU~$f$, I NAOBOROT. chASTO BYVAET UDOBNEE
RABOTATX S PREOBRAZOVANIEM fURXE FUNKCII, A ZATEM PROIZVESTI OBRATNOE
PREOBRAZOVANIE, CHTOBY VYVESTI NEOCHEVIDNYE SVOJSTVA ISHODNOJ FUNKCII.

pOPROBUEM PRIMENITX |TU KONCEPCIYU K PROBLEME VYRABOTKI SLUCHAJNYH CHISEL.
pUSTX ZADANA BESKONECHNAYA POSLEDOVATELXNOSTX CELYH CHISEL $X_0$, $X_1$,
$X_2$,~\dots, PRICHEM~$0\le X_k < m$, I PUSTX~$n$---FIKSIROVANNOE (OBYCHNO
NEBOLXSHOE) POLOZHITELXNOE CELOE CHISLO. oPREDELIM
$$
F(t_1, \ldots, t_n)=\lim_{N\to\infty} {1\over N}
\sum_{0\le k <N} \delta_{X_k t_1} \delta_{X_{k+1}t_2} \ldots\delta_{X_{k+n-1}t_n}.
\eqno(3)
$$
eTA FUNKCIYA RAVNA PREDELXNOJ PLOTNOSTI CHISLA POYAVLENIJ
KOMBINACII~$(t_1,~\ldots, t_n)$ V VIDE $n$~SLEDUYUSHCHIH DRUG ZA DRUGOM |LEMENTOV
POSLEDOVATELXNOSTI~$X_0$, $X_1$, $X_2$,~$\ldots\,$. tAK KAK NAS INTERESUYUT
PERIODICHESKIE POSLEDOVATELXNOSTI~$X_0$, $X_1$, $X_2$,~\dots, MOZHNO SCHITATX,
CHTO PREDEL V~(3) SUSHCHESTVUET, PRICHEM DLYA VYCHISLENIYA PREDELA MOZHNO
VZYATX~$N$ RAVNYM DLINE PERIODA. v DEJSTVITELXNO SLUCHAJNOJ
POSLEDOVATELXNOSTI S RAVNOMERNYM RASPREDELENIEM LYUBYE KOMBINACII IZ
$t$~CHISEL DOLZHNY POYAVLYATXSYA S ODINAKOVOJ CHASTOTOJ, TAK CHTO
$F(t_1,~\ldots, t_n)$~DOLZHNO BYTX RAVNO~$1/m^n$ DLYA LYUBYH~$t_1$,~\dots, $t_n$.

pROIZVODYA PREOBRAZOVANIE fURXE FUNKCII~(3), POLUCHIM
$$
f(s_1,~\ldots, s_n)=\lim_{N\to\infty}{1\over N}\sum_{0\le k < N}
\exp\left({-2\pi i \over m}(s_1 X_k+s_2X_{k+1}+\cdots+s_n X_{k+n-1})\right).
\eqno(4)
$$
%% 107
kOGDA MY IMEEM DELO S DEJSTVITELXNO SLUCHAJNOJ POSLEDOVATELXNOSTXYU, DOLZHEN
POLUCHITXSYA OBRAZ KONSTANTY~$1/m^n$; TAK CHTO \emph{DLYA SLUCHAJNOJ
POSLEDOVATELXNOSTI MY DOLZHNY POLUCHITX}
$$
f(s_1,~\ldots, s_n)=\cases{
 1, & ESLI $s_1\equiv \cdots \equiv s_n \equiv 0 \pmod{m}$; \cr
 0 & V PROTIVNOM SLUCHAE.\cr
}
\eqno(5)
$$

v TEORETICHESKIH TESTAH, RASSMOTRENNYH RANEE, ISPOLXZUYUTSYA SREDNIE ZNACHENIYA
PO POLNOMU PERIODU. dLYA OPREDELENIYA SREDNEGO OT KAKOJ-LIBO FUNKCII,
ZAVISYASHCHEJ OT~$n$ SLEDUYUSHCHIH DRUG ZA DRUGOM |LEMENTOV, DOSTATOCHNO V
PRINCIPE ZNATX~$F(t_1,~\ldots, t_n)$. nAPRIMER, VEROYATNOSTX TOGO,
CHTO~$X_k<X_{k+1}$, RAVNA VELICHINE~$F(t_1, t_2)$, PROSUMMIROVANNOJ PO
VSEM~$0\le t_1 < t_2 < m$; TOCHNO TAK ZHE SLUCHAJ~$n=2$ POZVOLYAET OPREDELITX
KO|FFICIENT POSLEDOVATELXNOJ KORRELYACII (SM.~UPR.~5).

tAK KAK OBRAZ~$f(s_1,~\ldots, s_n)$ SODERZHIT V SEBE VSYU
INFORMACIYU OB~$F(t_1,~\ldots, t_n)$, EGO TAKZHE MOZHNO ISPOLXZOVATX V
\emph{LYUBOM} TEORETICHESKOM TESTE. sLEDOVATELXNO, MOZHNO OZHIDATX, CHTO
VELICHINU OTKLONENIYA~$f(s_1,~\ldots, s_n)$ OT ZNACHENIJ~(5), OTVECHAYUSHCHIH
DEJSTVITELXNO SLUCHAJNOJ POSLEDOVATELXNOSTI, MOZHNO ISPOLXZOVATX
DLYA PROVERKI SLUCHAJNOSTI.

dLYA LINEJNYH KONGRU|NTNYH POSLEDOVATELXNOSTEJ~$f(s_1,~\ldots, s_n)$ IMEET
OCHENX PROSTOJ VID, CHEGO NELXZYA SKAZATX OB~$F(t_1,~\ldots, t_n)$.
rASSMOTRIM LINEJNUYU KONGRU|NTNUYU POSLEDOVATELXNOSTX S PARAMETRAMI~$a$,
$m$, $c$ I~$X_0$, IMEYUSHCHUYU \emph{MAKSIMALXNUYU DLINU PERIODA} V SOOTVETSTVII
S TEOREMOJ~3.2.1.2a. dLYA TAKOJ POSLEDOVATELXNOSTI
$$
\eqalignno{
f(s_1,~\ldots, s_n)&={1\over m}
 \sum_{0\le k < m} \exp\left({-2\pi i \over m} (s_1 X_k+s_2 X_{k+1}+\cdots+s_n X_{k+n-1})\right)=\cr
&={1\over m}
 \sum_{0\le k < m} \exp\left({-2\pi i \over m}\left(s(a)X_k+{s(a)-s(1)\over a-1} c \right) \right), & (6) \cr
}
$$
GDE
$$
s(a)=s_1+s_2 a+ s_3 a^2+\cdots+s_n a^{n-1},
\eqno(7)
$$
TAK KAK
$$
X_{k+r}\equiv a^r X_k+{a^r-1\over a-1} c \pmod{m}
$$
SOGLASNO FORMULE~(3.2.1-6). mY PREDPOLOZHILI, CHTO POSLEDOVATELXNOSTX IMEET
MAKSIMALXNYJ PERIOD, TAK CHTO V NEJ VSTRECHAYUTSYA VSE ZNACHENIYA~$X_k$;
SLEDOVATELXNO, (6) SVODITSYA K
$$
{1\over m} \sum_{0\le k <m}
 \exp\left({-2\pi i \over m}\left(s(a)k+{s(a)-s(1)\over a-1} c\right)\right).
$$
%% 108
eTO SUMMA GEOMETRICHESKOJ PROGRESSII, PO|TOMU MOZHNO ZAPISATX SLEDUYUSHCHUYU
OSNOVNUYU FORMULU:
$$
f(s_1, \ldots, s_n)=\exp \left({-2\pi i c \over m} \left({s(a)-s(1) \over a-1}\right )\right) \delta\left({s(a)\over m}\right),
\eqno(8)
$$
GDE~$\delta(x)=1$, ESLI~$x$---CELOE, I~$\delta(x)=0$ V PROTIVNOM SLUCHAE.

nAPOMNIM, CHTO FORMULA~(2) POZVOLYAET
INTERPRETIROVATX~$f(s_1, s_2,~\dots, s_n)/m^n$ FIZICHESKI KAK AMPLITUDU
$n\hbox{-MERNOJ}$  KOMPLEKSNOJ PLOSKOJ VOLNY
$$
\omega(t_1, \ldots, t_n)=\exp\left(2\pi i \left({s_1\over m}t_1+\cdots+{s_n \over m} t_n\right)\right).
\eqno(9)
$$
"vOLNOVOE CHISLO"~$\nu$, SOOTVETSTVUYUSHCHEE "CHASTOTE" |TOJ VOLNY,
OPREDELYAETSYA PO FORMULE
$$
\nu=\sqrt{s_1^2+\cdots+s_n^2}
\rem {PRI~$\abs{s_k}\le {m \over 2}$ DLYA~$1\le k < n$.}
\eqno (10)
$$

sOGLASNO~(5), NIKAKIH VOLN, KROME POSTOYANNOJ VOLNY (S NULEVOJ CHASTOTOJ),
NE DOLZHNO POYAVLYATXSYA, ESLI POSLEDOVATELXNOSTX $X_0$, $X_1$, $X_2$,~\dots{}
DEJSTVITELXNO SLUCHAJNAYA. pO|TOMU SUSHCHESTVOVANIE KOMPONENT S NENULEVOJ
CHASTOTOJ GOVORIT OB OTKLONENII OT SLUCHAJNOSTI. oCHENX MALYE
ZNACHENIYA~$f(s_1,~\ldots, s_n)$ MALO VLIYAYUT NA SLUCHAJNOSTX. nAPRIMER, ESLI VZYATX
DEJSTVITELXNO SLUCHAJNUYU POSLEDOVATELXNOSTX I IZMENITX TOLXKO KAZHDYJ EE
$N\hbox{-J}$~CHLEN (PRI BOLXSHOM~$N$), POSLEDOVATELXNOSTX OSTANETSYA
SLUCHAJNOJ, A ZNACHENIYA~$f(s_1,~\ldots, s_n)$ BUDUT PORYADKA~$1/N$; TAKIMI
ZNACHENIYAMI MOZHNO PRENEBRECHX. oTMETIM, ODNAKO, CHTO, SOGLASNO~(8),
ZNACHENIYA~$f(s_1,~\ldots,  s_n)$ RAVNY LIBO~$0$, LIBO~$1$, A
PRI~$\abs{f(s_1,~\ldots, s_n)}=1$ O SLUCHAJNOSTI NE MOZHET BYTX I RECHI. v
SVETE |TOGO INTERESNO OTMETITX, CHTO \emph{NIZKOCHASTOTNYE KOMPONENTY
SILXNEE VLIYAYUT NA SLUCHAJNOSTX, CHEM VYSOKOCHASTOTNYE.} pOSMOTRIM, NAPRIMER,
CHTO PROIZOJDET, ESLI ZAMENITX~$X_k$ NA~$2X_k$ I~$m$ NA~$2m$. sOGLASNO~(4),
$f(s_1,~\ldots, s_n)$ NE IZMENITSYA, NO TEPERX BUDUT IGRATX ROLX
KOMPONENTY S~$\abs{s_k}\le m$, A NE S~$\abs{s_k}\le m/2$. iZUCHENIE |TOJ
SITUACII POKAZYVAET, CHTO ESLI VZYATX SLUCHAJNUYU POSLEDOVATELXNOSTX CELYH
CHISEL~$X_0$, $X_1$, $X_2$,~\dots{} S~$m=2^e$ I NACHATX OTBRASYVATX MLADSHIE
RAZRYADY V DVOICHNOM PREDSTAVLENII KAZHDOGO CHLENA POSLEDOVATELXNOSTI, TO PRI
OTBRASYVANII ODNOGO, DVUH, TREH I T.~D.\ DVOICHNYH RAZRYADOV BUDUT
POYAVLYATXSYA KOMPONENTY S VOLNOVYMI CHISLAMI~$2^{e-1}$, $2^{e-2}$,
$2^{e-3}$ I~T.~D. eTOT FAKT, A TAKZHE PRIMER, PRIVEDENNYJ V UPR.~(10),
PRIVODYAT K SLEDUYUSHCHEMU INTUITIVNOMU ZAKLYUCHENIYU.
\emph{eSLI~$\nu_n$---NAIMENXSHEE NENULEVOE ZNACHENIE VOLNOVOGO CHISLA~(10), DLYA
KOTOROGO~$f(s_1,~\ldots, s_n)\ne 0$ V LINEJNOJ KONGRU|NTNOJ
POSLEDOVATELXNOSTI S MAKSIMALXNYM PERIODOM, TO POSLEDOVATELXNOSTX~$X_0/m$,
$X_1/m$, $X_2/m$,~\dots{} MOZHNO SCHITATX POSLEDOVATELXNOSTXYU SLUCHAJNYH
CHISEL, RAVNOMERNO RASPREDELENNYH MEZHDU~$0$ I~$1$
%% 109
I PREDSTAVLENNYH S "TOCHNOSTXYU" ILI S "OSHIBKOJ OKRUGLENIYA"~$1/\nu_n$,
PRICHEM RECHX IDET O NEZAVISIMOSTI $n$~POSLEDOVATELXNYH ZNACHENIJ S
USREDNENIEM PO POLNOMU PERIODU.} v UPR.~27 SODERZHITSYA ESHCHE ODNO
PODTVERZHDENIE |TOGO PRINCIPA VMESTE S GEOMETRICHESKOJ INTERPRETACIEJ,
POKAZYVAYUSHCHEJ BOLEE OTCHETLIVO VAZHNOSTX ZNACHENIYA~$\nu_n$.

fORMULA~(8) DAET "SPEKTR" LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTI,
T.~E.\ POKAZYVAET, KAKIE TIPY VOLN IMEYUTSYA V PREOBRAZOVANII fURXE
FUNKCII~$F(t_1, \ldots, t_n)$. mY VIDIM, CHTO~$f(s_1,~\ldots, s_n)=0$
VSEGDA, KROME SLUCHAEV, KOGDA
$$
s_1+s_2 a+s_3 a^2 + \cdots + s_n a^{n-1} \equiv 0\pmod{m},
\eqno (11)
$$
I PRI |TOM~$\abs{f(s_1,~\ldots, s_n)}=1$. sLEDOVATELXNO, \emph{DLYA
LINEJNYH KONGRU|NTNYH POSLEDOVATELXNOSTEJ S MAKSIMALXNYM PERIODOM
NAIMENXSHEE NENULEVOE VOLNOVOE CHISLO V SPEKTRE RAVNO
$$
\nu_n=\min\sqrt{s_1^2+s_2^2+\cdots+s_n^2},
\eqno(12)
$$
GDE MINIMIM BERETSYA PO VSEM $n\hbox{-NABORAM}$ CELYH CHISEL
$(s_1, s_2,~\ldots, s_n) \ne (0, 0,~\ldots, 0)$, UDOVLETVORYAYUSHCHIM~(11).}
oTMETIM, CHTO |TO USLOVIE NE ZAVISIT OT PRIRASHCHENIYA~$c$ LINEJNOJ
KONGRU|NTNOJ POSLEDOVATELXNOSTI.

oDNIM IZ SLEDSTVIJ VSEGO SKAZANNOGO YAVLYAETSYA VOZMOZHNOSTX
OPREDELENIYA VERHNEGO PREDELA SLUCHAJNOSTI LYUBOJ LINEJNOJ KONGRU|NTNOJ
POSLEDOVATELXNOSTI. iSPOLXZUYA DOVOLXNO GLUBOKIE TEORETIKO-CHISLOVYE METODY,
MOZHNO POKAZATX, CHTO
$$
\nu_n \le \gamma_n m^{1/n},
\eqno(13)
$$
GDE~$\gamma_n$ PRINIMAET ZNACHENIYA
$$
1,  (4/3)^{1/4}, 2^{1/6}, 2^{1/4}, 2^{3/10}, (64/3)^{1/12}, 2^{3/7}, 2^{1/2}
$$
DLYA~$n=1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$ [SM.~UPR.~9, A TAKZHE STR.~332
V KNIGE J.~W.~S.~Cassels, An Introduction to the Geometry of
Numbers, Springer, Berlin (1959)]. dLYA LYUBOJ PERIODICHESKOJ (S
PERIODOM~$m$) POSLEDOVATELXNOSTI~$U_0$, $U_1$, $U_2$,~\dots{} CHISEL,
LEZHASHCHIH MEZHDU~$0$ I~$1$, SLEDOVALO BY OZHIDATX GRANICY, IZMENYAYUSHCHEJSYA
KAK~$m^{1/n}$. dELO V TOM, CHTO, SOGLASNO SFORMULIROVANNOMU VYSHE PRAVILU,
VYPOLNENIE S TOCHNOSTXYU~$1/\nu$ PREDPOLOZHENIYA O NEZAVISIMOSTI
POSLEDOVATELXNYH ZNACHENIJ |KVIVALENTNO (PRI CELOM~$\nu$) TOMU, CHTO KAZHDOE
IZ~$\nu^n$ VOZMOZHNYH ZNACHENIJ ($\floor{\nu U_{k+1}}$,
$\floor{\nu U_{k+2}}$,~\dots, $\floor{\nu U_{k+n}}$) DOLZHNO POYAVLYATXSYA
PRIBLIZITELXNO S ODINAKOVOJ CHASTOTOJ V PREDELAH PERIODA; SLEDOVATELXNO, IZ
INTUITIVNYH SOOBRAZHENIJ MY POLUCHAEM PRIBLIZHENNOE NERAVENSTVO~$\nu^n \le m$.

\section{B. pRIMERY}. dLYA BOLXSHEJ YASNOSTI PROILLYUSTRIRUEM VYSHESKAZANNOE
NA PRIMERE. vOZXMEM LINEJNUYU KONGRU|NTNUYU
%% 110
POSLEDOVATELXNOSTX S
$$
X_0=0, \qquad a=3141592621, \qquad c=1, \qquad m=10^{10}.
\eqno (14)
$$
mINIMALXNOE NENULEVOE ZNACHENIE~$s_1^2+s_2^2$, DLYA KOTOROGO
$$
s_1+3141592621s_2 \equiv 0 \pmod{10^{10}},
$$
SOOTVETSTVUET~$s_1=67654$, $s_2=226$, TAK CHTO
$$
\nu_2=\sqrt{67654^2+226^2} \approx 67654.4.
$$
eTO OZNACHAET, CHTO POSLEDOVATELXNOSTX
$$
U_0, U_1, U_2, \ldots = X_0/m, X_1/m, X_2/m, \ldots
$$
MOZHNO SCHITATX SLUCHAJNOJ V SMYSLE NEZAVISIMOSTI PAR SLEDUYUSHCHIH DRUG ZA
DRUGOM CHISEL~$(U_k, U_{k+1})$ NA POLNOM PERIODE, ESLI OGRANICHITXSYA
TOCHNOSTXYU~$1/67654$; T.~E.\ PERVYE 16~RAZRYADOV V DVOICHNOM PREDSTAVLENII
CHISEL MOZHNO SCHITATX SLUCHAJNYMI V UKAZANNOM SMYSLE. aNALOGICHNO, MINIMALXNOE
NENULEVOE ZNACHENIE~$s_1^2+s_2^2+s_3^2$, DLYA KOTOROGO
$$
s_1+3141592621s_2+3141592621^2s_3 \equiv 0 \pmod{10^{10}},
$$
SOOTVETSTVUET~$s_1=227$, $s_2=983$, $s_3=130$; SLEDOVATELXNO,
$$
\nu_3=\sqrt{1034718}\approx 1017.2.
$$
tAKIM OBRAZOM, ESLI RASSMATRIVAETSYA NEZAVISIMOSTX TROEK~$(U_k, U_{k+1},
U_{k+2})$, MY IMEEM TOCHNOSTX VSEGO V 10~DVOICHNYH RAZRYADOV. vEROYATNO,
$3141592621$---NE OCHENX HOROSHIJ MNOZHITELX;
POZDNEE MY UVIDIM, CHTO ON YAVLYAETSYA PRIEMLEMYM, NO NE LUCHSHIM (NAPRIMER,
POHOZHIJ MNOZHITELX~$3141592821$ DAET~$\nu_3\approx 1912$, NO MENXSHEE
ZNACHENIE~$\nu_2$). sOGLASNO~(13), PRI~$m=10^{10}$ NEVOZMOZHNO POLUCHITX~$\nu_3>2425$.

mINIMALXNOE NENULEVOE ZNACHENIE~$s_1^2+s_2^2+s_3^2+s_4^2$, DLYA KOTOROGO
$$
s_1+3141592621s_2+3141592621^2s_3+3141592621^3s_4 \equiv 0 \pmod{10^{10}},
$$
IMEET MESTO PRI~$s_1=52$, $s_2=-203$, $s_3=-54$, $s_4=125$, TAK CHTO
$$
\nu_4=\sqrt{62454} \approx 249.9.
$$

tREBOVANIE NEZAVISIMOSTI \emph{CHETVEROK} PONIZHAET TOCHNOSTX DO 8~DVOICHNYH
ZNAKOV (DLYA BOLXSHINSTVA PRILOZHENIJ |TOGO VPOLNE DOSTATOCHNO).

zNACHENIYA~$\nu_n$ DLYA~$n=5$, $6$,~\dots{} MENEE VAZHNY, TAK KAK VRYAD LI
NEZAVISIMOSTX PYATEROK VSEGDA DEJSTVITELXNO NEOBHODIMA. nAPRIMER, PRI
PROVERKE SERIJ (SM.~P.~3.3.2) REDKO UCHITYVAYUTSYA DAZHE CHETVERKI. (pRI
RASSMOTRENII SREDNIH PO VSEMU PERIODU, KAK V NASHEM SLUCHAE, SLEDUET
SOBLYUDATX OSTOROZHNOSTX, PO|TOMU PRENEBREGATX CHETVERKAMI V SPEKTRALXNOM
TESTE NE STOIT; ODNAKO RASPREDELENIE
%% 111
PYATEROK VRYAD LI MOZHET PONADOBITXSYA, VO VSYAKOM SLUCHAE
PRI~$m<2^{40}$.) dLYA RASSMATRIVAEMOGO DATCHIKA~$s_1=-8$, $s_2=-14$, $s_3=6$,
$s_4=-18$, $s_5=34$ I
$$
\eqalign{
\nu_5 &= \sqrt{1776} \approx 42.2, \cr
\nu_6&=\sqrt{542}\approx 23.3.\cr
}
$$

tAK KAK NIKTO NE ZNAET, KAKOVY NAILUCHSHIE DOSTIZHIMYE ZNACHENIYA~$\nu_n$,
TRUDNO TOCHNO OPREDELITX, KAKIE ZNACHENIYA~$\nu_n$ MOZHNO SCHITATX
UDOVLETVORITELXNYMI. pREDSTAVLYAETSYA RAZUMNYM ISPOLXZOVATX V KACHESTVE
MERY SLUCHAJNOSTI OB®EM |LLIPSOIDA V $n\hbox{-MERNOM}$ PROSTRANSTVE,
OPREDELENNOGO SOOTNOSHENIEM~$(x_1 m-x_2a-x_3a^2-\cdots-x_na^{n-1})^2+x_2^2+\cdots+x_n^2\le \nu_n^2$,
TAK KAK |TOT OB®EM PROPORCIONALEN VEROYATNOSTI POPADANIYA V |LLIPSOID
TOCHEK~$(x_1, x_2,~\ldots, x_n)$---\emph{CELOCHISLENNYH} RESHENIJ
URAVNENIJ~(11). tAKIM OBRAZOM, DLYA OPREDELENIYA |FFEKTIVNOSTI MNOZHITELYA~$a$
V LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTI S MAKSIMALXNYM PERIODOM MY
PREDLAGAEM VYCHISLYATX VELICHINU
$$
C_n={\pi^{n/2}\nu_n^n \over (n/2)!m}.
\eqno(15)
$$
$\bigl($~v |TOJ FORMULE
$$
\left({n\over 2}\right)!=\left({n\over2}\right) \left({n\over2}-1\right)
\ldots \left({1\over2}\right)\sqrt{\pi} \rem{DLYA NECHETNYH~$n$.}\bigr)
\eqno(16)
$$
tAKIM OBRAZOM,
$$
C_1=2\nu_1/m, \quad C_2=\pi\nu_2^2/m, \quad C_3={4\over3}\pi_3^3/m,
C_4={1\over2}\pi^2\nu_4^4/m \rem{I T. D.}
$$
bOLXSHIE ZNACHENIYA~$C_n$ SOOTVETSTVUYUT SLUCHAJNOSTI, MALYE---OTSUTSTVIYU
SLUCHAJNOSTI. v TABL.~1 PREDSTAVLENY ZNACHENIYA DLYA NEKOTORYH TIPICHNYH
POSLEDOVATELXNOSTEJ ($C_1$ VSEGDA RAVNO~$2$). dATCHIKI, PREDSTAVLENNYE
V STROKAH~1--4 |TOJ TABLICY, BYLI UZHE RASSMOTRENY V P.~3.3.1 (SM.~RIS.~2 I~5).
u DATCHIKOV~1 I~2 SLISHKOM MAL MNOZHITELX. oCHENX PLOHOJ DATCHIK~3 DAET
HOROSHEE ZNACHENIE~$C_2$, NO OCHENX PLOHIE~$C_3$ I~$C_4$; DLYA NEGO~$\nu_3=6$
I~$\nu_4=2$. u DATCHIKA~4 "SLUCHAJNYJ" MNOZHITELX; |TOT DATCHIK USPESHNO PROSHEL
ISPYTANIYA S ISPOLXZOVANIEM |MPIRICHESKIH TESTOV, NO ZNACHENIYA~$C_2$, $C_3$
I~$C_4$ U NEGO NE OCHENX VELIKI.

dATCHIK~7 MY TOLXKO CHTO RASSMATRIVALI; RYADOM S NIM PREDSTAVLENY DATCHIKI S
BLIZKIMI PARAMETRAMI. oTMETIM, CHTO MNOZHITELX~$3141592221$ PRIVODIT K
ANOMALXNO NIZKOMU ZNACHENIYU~$C_3$ (SM.~STROKU~5), ODNAKO PRI TOM ZHE
ZNACHENII~$a$ S~$m=2^{35}$ (SM. \ STROKU~9) POLUCHAYUTSYA HOROSHIE REZULXTATY.

%% 112

\htable{tABLICA 1}%
{nEKOTORYE REZULXTATY, POLUCHENNYE PRI POMOSHCHI SPEKTRALXNOGO TESTA}%
{\hfil$#$\bskip&&\bskip$#$\bskip\hfil\cr
sTROKA & a & m & C_2 & C_3 & C_4 \cr
\noalign{\hrule}
 1 & 23              & 10^8+1  & 0.000017 & 0.00051     & 0.014       \cr
 2 & 2^7+1           & 2^{35}  & 0.000002 & 0.00026     & 0.040       \cr
 3 & 2^{18}+1        & 2^{35}  & 3.14     & 0.000000002 & 0.000000003 \cr
 4 & 3141592653      & 2^{35}  & 0.27     & 0.13        & 0.11        \cr
 5 & 3141592221      & 10^{10} & 1.35     & 0.06        & 4.67        \cr
 6 & 3141592421      & 10^{10} & 2.69     & 0.35        & 0.54        \cr
 7 & 3141592621      & 10^{10} & 1.44     & 0.43        & 1.91        \cr
 8 & 3141592821      & 10^{10} & 0.16     & 2.90        & 0.34        \cr
 9 & 3141592221      & 2^{35}  & 1.24     & 1.69        & 1.11        \cr
10 & 3141592621      & 2^{35}  & 3.02     & 0.17        & 1.25        \cr
11 & 2718281821      & 2^{35}  & 2.59     & 1.15        & 1.75        \cr
12 & 2^{23}+2^{12}+5 & 2^{35}  & 0.015    & 2.78        & 0.066       \cr
13 & 2^{23}+2^{13}+5 & 2^{35}  & 0.015    & 1.48        & 0.066       \cr
14 & 2^{23}+2^{14}+5 & 2^{35}  & 1.12     & 1.66        & 0.066       \cr
15 & 2^{22}+2^{13}+5 & 2^{35}  & 0.75     & 0.30        & 0.066       \cr
16 & 2^{24}+2^{13}+5 & 2^{35}  & 0.0008   & 2.92        & 0.066       \cr
17 & 5^{13}          & 2^{35}  & 3.03     & 0.61        & 1.84        \cr
18 & 5^{15}          & 2^{35}  & 2.02     & 4.12        & 4.04        \cr
   & \hbox{\emph{vERHNYAYA GRANICA SOGLASNO}~(13):} \span & 3.63 & 5.90 & 9.86 \cr
}

u DATCHIKOV~12--16 V DVOICHNOM PREDSTAVLENII~$a$ VSEGO PO 4~EDINICY;
PRIEMLEMYM MOZHNO SCHITATX TOLXKO DATCHIK~14, NO I U NEGO PODOZRITELXNO
NIZKOE ZNACHENIE~$C_4$. pO STRANNOMU SOVPADENIYU VSE |TI 5~DATCHIKOV DAYUT
ODINAKOVOE ZNACHENIE~$C_4$; BOLEE TOGO, VO VSEH SLUCHAYAH~$s_1=-125$,
$s_2=75$, $s_3=15$, $s_4=1$! kURXEZNYM YAVLYAETSYA TAKZHE NALICHIE U
DATCHIKA~16 VYSOKOGO ZNACHENIYA~$C_3$ PRI NIZKOM~$C_2$; V |TOM
SLUCHAE~$\nu_2=\nu_3$, TAK KAK MINIMUM PRI~$n=3$ DOSTIGAETSYA
PRI~$s_1=-2043$, $s_2=2047$, $s_3=0$.

v DATCHIKAH~17 I~18 ISPOLXZOVANY MNOZHITELI, KOTORYE INTENSIVNO
PRIMENYALISX S TEH POR, KAK IH PREDLOZHILA o.~tAUSSKI V NACHALE 50-H GODOV.
pO SLUCHAJNOMU SOVPADENIYU NAIBOLEE POPULYARNYJ MNOZHITELX~$5^{15}$ DAET
NAILUCHSHIE REZULXTATY IZ VSEH SLUCHAEV, POKAZANNYH V TABL.~1.

rEZULXTATY, PRIVEDENNYE V TABL.~1, I POSLEDUYUSHCHIJ OPYT RABOTY S MNOGIMI IZ
PREDSTAVLENNYH ZDESX DATCHIKOV POZVOLYAYUT SKAZATX, CHTO MNOZHITELX~$a$
\emph{USPESHNO PROSHEL SPEKTRALXNYJ TEST}, ESLI KAZHDOE IZ~$C_2$, $C_3$
I~$C_4\ge 0.1$; ESLI VSE ONI BOLXSHE (ILI RAVNY) EDINICY, TO MOZHNO SCHITATX,
CHTO SPEKTRALXNYJ TEST PROJDEN S BLESKOM. pREZHDE CHEM REKOMENDOVATX DATCHIK
DLYA OBSHCHEGO POLXZOVANIYA, MOZHNO VYCHISLITX TAKZHE~$C_5$, $C_6$ I~T.~D. dLYA
TOGO CHTOBY UBEDITXSYA,  CHTO MODULX~$m$ DOSTATOCHNO VELIK DLYA OBESPECHENIYA
%% 113
TREBUEMOJ TOCHNOSTI SLUCHAJNYH CHISEL, NADO ANALIZIROVATX ZNACHENIYA~$\nu_2$,
$\nu_3$  I~$\nu_4$; PRI MALYH~$m$ UDOVLETVORITELXNYE REZULXTATY, POLUCHENNYE
S POMOSHCHXYU SPEKTRALXNOGO TESTA, ESHCHE NE GARANTIRUYUT PRIGODNOSTI DATCHIKA DLYA
RASCHETOV METODOM mONTE-kARLO S VYSOKIM RAZRESHENIEM.

\section{C.~vYVOD VYCHISLITELXNOGO METODA}. pRIVEDENNYE PRIMERY
ILLYUSTRIRUYUT SPOSOBY PRIMENENIYA SPEKTRALXNOGO TESTA. oDNAKO V NASHIH
RASSUZHDENIYAH OSTAETSYA, KONECHNO, SUSHCHESTVENNYJ PROBEL:
SUSHCHESTVUET LI HOTX KAKAYA-NIBUDX VOZMOZHNOSTX OPREDELITX ZNACHENIE~$\nu_n$,
ZATRACHIVAYA NE SLISHKOM MNOGO MASHINNOGO VREMENI? kAK, NAPRIMER, MOZHNO
VYYASNITX, CHTO IMENNO ZNACHENIYAM~$s_1=227$, $s_2=983$ I~$s_3=130$
SOOTVETSTVUET MINIMUM SUMMY~$s_1^2+s_2^2+s_3^2$ PRI SOBLYUDENII
USLOVIYA~$s_1+3141592621s_2+3141592621^2s_3\equiv 0 \pmod{10^{10}}$?
oCHEVIDNO, CHTO O PROSTOM PEREBORE NE MOZHET BYTX I RECHI.

pOPYTAEMSYA OTYSKATX PODHODYASHCHIJ VYCHISLITELXNYJ METOD DLYA RESHENIYA |TOJ
ZADACHI. pREZHDE VSEGO PEREJDEM OT TOLXKO CHTO PRIVEDENNOJ FORMULIROVKI,
OPIRAYUSHCHEJSYA NA FORMULY~(11) I~(12), K SLEDUYUSHCHEJ |KVIVALENTNOJ ZADACHE:
OPREDELITX MINIMUM SUMMY
$$
(x_1m-ax_2-a^2x_3-\cdots-a^{n-1}x_n)^2+x_2^2+x_3^2+\cdots+x_n^2
\eqno(17)
$$
PRI CELYH ZNACHENIYAH~$x_1$, $x_2$,~\dots, $x_n$, IZ KOTORYH HOTYA BY ODNO NE
RAVNO NULYU.

bUDET INTERESNO I, VEROYATNO, POLEZNEE RAZRABOTATX CHISLENNYJ METOD
RESHENIYA BOLEE OBSHCHEJ ZADACHI: \emph{OPREDELITX MINIMUM SUMMY
$$
(a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n)^2+\cdots+(a_{n1}x_1+a_{n2}x_2+\cdots+a_{nn}x_n)^2
\eqno(18)
$$
PRI CELYH ZNACHENIYAH~$x_1$,~\dots, $x_n$, IZ KOTORYH HOTYA BY ODNO NE RAVNO
NULYU,} I PRI USLOVII, CHTO MATRICA KO|FFICIENTOV~$A=(a_{ij})$ NE VYROZHDENA.
vYRAZHENIE~(18) NAZYVAETSYA "POLOZHITELXNO OPREDELENNOJ KVADRATICHNOJ FORMOJ".

v DALXNEJSHEM BUKVAMI~$x$, $y$,~\dots{} BUDUT OBOZNACHATXSYA VEKTOR-STOLBCY
$$
\pmatrix{
 x_1\cr
 x_2\cr
 \vdots\cr
 x_n\cr
},
\pmatrix{
 y_1\cr
 y_2\cr
 \vdots\cr
 y_n\cr
}, \ldots
$$
"sKALYARNOE PROIZVEDENIE" $x\cdot y = x_1 y_1+\cdots+x_ny_n$ MOZHET BYTX
ZAPISANO V MATRICHNYH OBOZNACHENIYAH KAK~$x^Ty$, GDE $T$~OBOZNACHAET ZAMENU
STOLBCOV NA STROKI, I NAOBOROT (TRANSPONIROVANIE). dLYA UDOBSTVA VVEDEM
SLEDUYUSHCHIE OPREDELENIYA:
$$
Q=A^TA, \quad B=A^{-1}, \quad R=Q^{-1}=BB^T.
\eqno(19)
$$
%% 113
pUSTX $A_j$~OBOZNACHAET $j\hbox{-J}$~\emph{STOLBEC} MATRICY~$A$,
A~$B_i$---$i\hbox{-YU}$~\emph{STROKU} MATRICY~$B$. tOGDA IMEEM
$$
B_i\cdot A_j=\delta_{ij}, \quad Q_{ij}=A_i\cdot A_j, \quad R_{ij}=B_i\cdot B_j.
\eqno (20)
$$
nASHA ZADACHA SOSTOIT V TOM, CHTOBY MINIMIZIROVATX~(18), T.~E.\
MINIMIZIROVATX~$(Ax)\cdot(Ax)=x^TA^TAx=x^TQx$ DLYA CELYH VEKTOROV~$x\ne0$.

pREZHDE VSEGO SDELAEM ZADACHU KONECHNOJ, T.~E.\ POKAZHEM, CHTO NE NADO
PEREBIRATX VSE BESKONECHNOE MNOZHESTVO VEKTOROV~$x$, CHTOBY NAJTI MINIMUM.
pUSTX~$e_k$---VEKTOR, $k\hbox{-YA}$~KOMPONENTA KOTOROGO RAVNA~$1$, A
OSTALXNYE NULYU. tOGDA
$$
x_k = e_k^T x = e_k^T B Ax = (B^T e_k)\cdot(Ax) = B_k\cdot (Ax)
$$
I, SOGLASNO NERAVENSTVU shVARCA,
$$
(B_k\cdot (Ax))^2 \le (B_k\cdot B_k) ((Ax)\cdot(Ax))=R_{kk}(x^TQx).
$$
sLEDOVATELXNO, ESLI~$x$---NENULEVOJ VEKTOR, MINIMIZIRUYUSHCHIJ~$x^T Qx$, TO
$$
x_k^2\le R_{kk}(x^T Qx) \le R_{kk}(e_j^T Qe_j)=R_{kk}Q_{jj},
\rem{$1\le j$, $k\le n$.}
\eqno(21)
$$
eTO OZNACHAET, CHTO CHISLO VEKTOROV~$x$, KOTORYE NADO RASSMOTRETX PRI POISKE
MINIMUMA, OGRANICHENO. nA SAMOM DELE MY POLUCHILI SLEDUYUSHCHIJ BOLEE OBSHCHIJ REZULXTAT.

\proclaim lEMMA~A. eSLI
$$
x=\pmatrix{
x_1\cr
\vdots\cr
x_n\cr
}
$$
---NENULEVOJ CELOCHISLENNYJ VEKTOR S MINIMALXNYM ZNACHENIEM~$x^TQx$,
a~$q$---ZNACHENIE~$y^TQ$ DLYA NEKOTOROGO NENULEVOGO CELOCHISLENNOGO
VEKTORA~$y$, TO
$$
x_k^2\le R_{kk}q. \endmark
\eqno(22)
$$

oCHEVIDNO, CHTO PRAVAYA CHASTX~(22) MOZHET BYTX VSE ESHCHE SLISHKOM BOLXSHOJ, CHTOBY
PROSTOJ PEREBOR BYL PRAKTICHESKI OSUSHCHESTVIM, TAK CHTO TREBUETSYA PROIZVESTI
DALXNEJSHIE USOVERSHENSTVOVANIYA. oBRATIMSYA K ODNOMU IZ NAIBOLEE PROSTYH I
SHIROKO RASPROSTRANENNYH V MATEMATIKE PRIEMOV---METODU ZAMENY PEREMENNYH.
rASSMOTRIM PODSTANOVKU VIDA
$$
y=Ux,
\eqno(23)
$$
GDE~$U$---CELOCHISLENNAYA MATRICA, OPREDELITELX KOTOROJ~$\det U=\pm 1$. eTO
OZNACHAET, CHTO ESLI~$x$---VEKTOR-STOLBEC, SOSTOYASHCHIJ IZ CELYH CHISEL, TO TAKOV
ZHE I~$y$, I OBRATNO, ESLI VEKTOR~$y$ ZADAN, TO~$x$ MOZHNO OPREDELITX IZ
SOOTNOSHENIYA~$x=U^{-1}y$. (eLEMENTY MATRICY~$U^{-1}$
%% 115
BUDUT CELYMI, TAK KAK ONA RAVNA~$\adj (U)/\det(U)$.) sLEDOVATELXNO, ESLI V
KACHESTVE~$x$ PEREBRATX VSE CELOCHISLENNYE VEKTORY, TO |TO ZHE MNOZHESTVO
ZNACHENIJ PROBEZHIT I~$y=Ux$, I OBRATNO; DALEE, $y=0$ TOLXKO PRI~$x=0$.
pO|TOMU MOZHNO PEREJTI OT ZADACHI O MINIMIZACII~$(Ax)\cdot(Ax)$ DLYA
CELYH~$x\ne0$ K |KVIVALENTNOJ ZADACHE O NAHOZHDENII
MINIMUMA~$(AU^{-1}y)\cdot(AU^{-1}y)$ DLYA CELYH~$y\ne0$.

\proclaim lEMMA~B. pUSTX~$U$---LYUBAYA CELOCHISLENNAYA MATRICA S~$\det U=\pm1$, I PUSTX
$$
A'=AU^{-1}, \quad B'=Ub, \quad Q'=(U^{-1})^T QU^{-1}, \quad R'=URU^T.
\eqno(24)
$$
zADACHA MINIMIZACII, OPREDELENNAYA MATRICAMI~$A'$, $B'$, $Q'$, $R'$,  IMEET
TO ZHE SAMOE RESHENIE, CHTO I ZADACHA, OPREDELENNAYA MATRICAMI~$A$, $B$, $Q$, $R$.\endmark

tEPERX MOZHNO OPREDELITX |FFEKTIVNYJ SPOSOB VYCHISLENIYA MINIMALXNOGO
ZNACHENIYA SLEDUYUSHCHIM OBRAZOM: PEREJTI OT ISHODNOJ ZADACHI K DRUGOJ S POMOSHCHXYU
PODHODYASHCHEJ MATRICY~$U$ I POVTORYATX |TO DO TEH POR, POKA NE POLUCHITSYA
ZADACHA, DLYA KOTOROJ NERAVENSTVO V LEMME~A POZVOLYAET PROIZVESTI POLNYJ
PEREBOR NE SLISHKOM DOROGOJ CENOJ.

dOSTATOCHNO PROSTOJ I PRIGODNOJ DLYA NASHIH CELEJ MATRICEJ, OPREDELITELX
KOTOROJ RAVEN~$1$, MOZHET SLUZHITX MATRICA
$$
\eqalign{
U&=\pmatrix{
1   \cr
    & \ddots \cr
    &        & 1       \cr
c_1 & \ldots & c_{k-1} & 1 & c_{k+1} & \ldots & c_n \cr
    &        &         &   & 1       \cr
    &        &         &   &         & \ddots \cr
    &        &         &   &         &        & 1 \cr
} \cr
U^{-1}&=\pmatrix{
1    \cr
     & \ddots \cr
     &        & 1        \cr
-c_1 & \ldots & -c_{k-1} & 1 & -c_{k+1} & \ldots & -c_n \cr
     &        &          &   & 1        \cr
     &        &          &   &          & \ddots \cr
     &        &          &   &          &        & 1    \cr
} \cr
}
\eqno(25)
$$
GDE~$c_1$,~\dots, $c_n$---LYUBYE CELYE ZNACHENIYA, $k$---FIKSIROVANNOE CELOE
CHISLO. vSE |LEMENTY MATRIC, KROME UKAZANNYH, RAVNY NULYU. v |TOM SLUCHAE
SOOTNOSHENIE~$y=Ux$ OZNACHAET PROSTO, CHTO~$y_j=x_j$ DLYA~$j\ne k$
I~$y_k=x_k+\sum_{j\ne k} c_j x_j$; BEZUSLOVNO, |TO NAIBOLEE ESTESTVENNYJ
SPOSOB PODSTANOVKI. vYCHISLITX PROIZVEDENIYA, PERECHISLENNYE
%%116
V~(24), V |TOM SLUCHAE OCHENX LEGKO:
$$
\eqalignter{
A'_j&=A_j-c_jA_k & \rem{DLYA~$j\ne k$, $A_k'=A_k$;}\cr
B'_j&=B_j & \rem{DLYA~$j\ne k$, $B'_k=B_k+\sum_{j\ne k} c_j B_j$.}\cr
}
\eqno(26)
$$
tEPERX NUZHNO PODOBRATX PODHODYASHCHIE CELYE ZNACHENIYA~$k$ I~$c_j$. pRI
LYUBYH~$c_j$ I CELYH~$k$ MATRICA~$U$ V~(25) V PRINCIPE YAVLYAETSYA VPOLNE
PRIEMLEMYM PREOBRAZOVANIEM. v SOOTVETSTVII S~(21) ZHELATELXNO VYBRATX
CELYE CHISLA~$c_1$,~\dots, $c_{k-1}$, $c_{k+1}$,~\dots, $c_n$ TAK, CHTOBY
\emph{DIAGONALXNYE |LEMENTY} KAK MATRICY~$Q'$, TAK I~$R'$ BYLI KAK MOZHNO
MENXSHE. v SVYAZI S |TIM ESTESTVENNO VOZNIKAYUT DVA SLEDUYUSHCHIH VOPROSA:

\medskip
\item{a)}\emph{kAK LUCHSHE VSEGO VYBRATX DEJSTVITELXNYE CHISLA~$c_j$
PRI~$j\ne k$, CHTOBY MINIMIZIROVATX ZNACHENIYA DIAGONALXNYH |LEMENTOV
MATRICY~$Q'=(U^{-1})^T Q U^{-1}$?}

\item{b)}\emph{kAK LUCHSHE VSEGO VYBRATX DEJSTVITELXNYE CHISLA~$c_j$
PRI~$j\ne k$, CHTOBY MINIMIZIROVATX ZNACHENIYA DIAGONALXNYH |LEMENTOV MATRICY~$R'=URU^T$?}
\medskip

v SLUCHAE~(a) DIAGONALXNYE |LEMENTY MATRICY~$Q'$, RAVNYE~$A'_j\cdot A'_j$
SOGLASNO~(20), BUDUT IZMENENY PREOBRAZOVANIEM~$U$ PRI VSEH~$j\ne k$. lEGKO
VIDETX, CHTO MINIMUM VYRAZHENIYA
$$
\eqalign{
(A_j-c_jA_k)\cdot(A_j-c_jA_k)&=Q_{jj}-2c_jQ_{jk}+c_j^2Q_{kk}=\cr
                             &=Q_{kk}(c_j-Q_{jk}/Q_{kk})^2+Q_{jj}-Q_{jk}^2/Q_{kk}\cr
}
$$
DOSTIGAETSYA PRI
$$
c_j=Q_{jk}/Q_{kk}.
\eqno(27)
$$

gEOMETRICHESKI (RIS.~8) ZADACHA ZAKLYUCHAETSYA V TAKOM VYBORE KO|FFICIENTA PRI
VEKTORE~$A_k$, CHTOBY PRI VYCHITANII~$c_jA_k$ IZ VEKTORA~$A_j$
REZULXTIRUYUSHCHIJ VEKTOR~$A'_j$ IMEL MINIMALXNUYU DLINU. dLYA |TOGO NADO
VYBRATX TAKOE~$c_j$, CHTOBY $A'_j$~BYLO PERPENDIKULYARNO K~$A_k$
(T.~E.~$A'_j\cdot A'_k=Q'_{jk}=0$), A |TO DOSTIGAETSYA S POMOSHCHXYU~(27).

v SLUCHAE~(b) DIAGONALXNYE |LEMENTY MATRIC~$R'$ I~$R$ SOVPADAYUT,
KROME~$R'_{kk}=B'_k\cdot B'_k$. zDESX NAM NADO VYBRATX~$c_j$ TAK, CHTOBY
\picture{rIS. 8. gEOMETRICHESKAYA INTERPRETACIYA VYVODA FORMULY (27).}
%% 117
VEKTOR~$B_k+\sum_{j\ne k} c_jB_j$ IMEL MINIMALXNUYU DLINU. gEOMETRICHESKI
|TO OZNACHAET, CHTO MY DOBAVLYAEM K VEKTORU~$B_k$ NEKOTORYJ VEKTOR, LEZHASHCHIJ V
$(n-1)\hbox{-MERNOJ}$ GIPERPLOSKOSTI, OPREDELYAEMOJ
VEKTORAMI~$\{\,B_j \mid j\ne k\,\}$. tAK ZHE, KAK V SLUCHAE, POKAZANNOM NA
RIS.~8, MINIMUM DOSTIGAETSYA, KOGDA $B'_k$~PERPENDIKULYAREN GIPERPLOSKOSTI,
$B'_k$~PERPENDIKULYAREN VSEM~$B'_j$ PRI~$j\ne k$. tAKIM OBRAZOM,
NEOBHODIMO RESHITX SISTEMU URAVNENIJ~$B'_kB'_j=0$, T.~E.
$$
R_{kj}+\sum_{i\ne k} c_i R_{ij}=0, \rem{$1\le j \le n$, $j \ne k$.}
\eqno(28)
$$
sTROGOE DOKAZATELXSTVO TOGO, CHTO ZADACHA~(b) SVODITSYA K
RESHENIYU URAVNENIJ~(28), RASSMOTRENO V UPR.~12.

tEPERX, KOGDA OBE ZADACHI~(a) I~(b) RESHENY, MY PREBYVAEM V NEKOTOROM
NEDOUMENII: VYBIRATX LI ZNACHENIYA~$c$ V SOOTVETSTVII S~(27), CHTOBY
MINIMIZIROVATX DIAGONALXNYE |LEMENTY MATRICY~$Q'$, ILI V SOOTVETSTVII
S~(28), CHTOBY MINIMIZIROVATX DIAGONALXNYE |LEMENTY~$R'$? v OBOIH SLUCHAYAH
PRAVAYA CHASTX~(21) UTOCHNYAETSYA, PO|TOMU NEYASNO, KAKOJ VARIANT
PREDPOCHTITELXNEE. k SCHASTXYU, OTVET CHREZVYCHAJNO PROST: USLOVIYA~(27) I~(28)
SOVERSHENNO ODINAKOVY! rAVENSTVO~$R'=(Q')^{-1}$ OZNACHAET, CHTO
NEDIAGONALXNYE |LEMENTY V $k\hbox{-J}$~STROKE I
$k\hbox{-M}$~STOLBCE~$Q'$ RAVNY NULYU TOGDA I TOLXKO TOGDA, KOGDA RAVNY
NULYU NEDIAGONALXNYE |LEMENTY V $k\hbox{-J}$~STROKE I~$k\hbox{-M}$~STOLBCE
MATRICY~$R'$. pO|TOMU U ZADACH~(a) I~(b) ODNO I TO ZHE RESHENIE. v REZULXTATE
OKAZYVAETSYA, CHTO MOZHNO SDELATX MINIMALXNYMI ODNOVREMENNO DIAGONALXNYE
|LEMENTY~$Q$ I~$R$. (zAMETIM, CHTO MY TOLXKO CHTO OTKRYLI ZANOVO TAK
NAZYVAEMYJ "PROCESS ORTOGONALIZACII shMIDTA".)

kONECHNO, NA SAMOM DELE USLOVIYA~(a) I~(b) VYPOLNYAYUTSYA PRI NECELYH
ZNACHENIYAH~$c_j$, A MY MOZHEM ISPOLXZOVATX V MATRICE~$U$ TOLXKO CELYE
ZNACHENIYA. pRI |TOM SDELATX~$A'_j$ V TOCHNOSTI PERPENDIKULYARNYM~$A'_k$
NEVOZMOZHNO. eSLI, ODNAKO, VYBRATX V KACHESTVE~$c_j$ \emph{BLIZHAJSHIE
K~$Q_{jk}/Q_{kk}$ CELYE CHISLA,} TO |TO BUDET NAILUCHSHIM CELYM RESHENIEM
ZADACHI~(a) I BLIZKIM K (NO \emph{NE} VSEGDA RAVNYM) NAILUCHSHEMU RESHENIYU ZADACHI~(b).

pROIZVODYA PREOBRAZOVANIYA VIDA~(25) PRI RAZNYH~$k$ I PRI~$c_j$, RAVNYH
BLIZHAJSHEMU CELOMU K~$Q_{jk}/Q_{kk}$, MOZHNO OZHIDATX, CHTO POSTEPENNO VERHNYAYA
GRANICA, OPREDELYAEMAYA VYRAZHENIEM~(21), SPUSTITSYA DO UROVNYA, PRI KOTOROM
VOZMOZHEN POLNYJ PEREBOR. nA |TOM PREDPOLOZHENII OSNOVAN PRIVEDENNYJ NIZHE
ALGORITM. pRI NAPISANII NASTOYASHCHEJ GLAVY AVTOR PROVEL NESKOLXKO SOTEN
MASHINNYH RASCHETOV PO |TOMU ALGORITMU, PRICHEM SHODIMOSTX
OKAZYVALASX GORAZDO BOLEE BYSTROJ, CHEM OZHIDALOSX. dOSTATOCHNO BYLO
PRIMENITX PREOBRAZOVANIE~(25) VSEGO 21~RAZ, CHTOBY V VARIANTAH S~$n=6$ I
S OGROMNYMI ZNACHENIYAMI |LEMENTOV MATRIC~$Q$ I~$R$ OSTAVALOSX MENEE
500~SLUCHAEV DLYA PRYAMOGO PEREBORA. v REZULXTATE RASCHETY NA evm ZANIMALI
VSEGO NESKOLXKO SEKUND.

%% 118

\section{D.~rEALIZACIYA SPEKTRALXNOGO TESTA}. pRIVEDEM VYCHISLITELXNUYU
PROCEDURU, VYTEKAYUSHCHUYU IZ VSEGO SKAZANNOGO VYSHE.

\alg S.(sPEKTRALXNYJ TEST.) sPEKTRALXNYJ TEST PRIMENYAETSYA DLYA OCENKI VYBORA
MNOZHITELYA~$a$ V LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTI S MAKSIMALXNYM
PERIODOM. (vOPROS O RASPROSTRANENII |TOGO TESTA NA DRUGIE LINEJNYE
KONGRU|NTNYE POSLEDOVATELXNOSTI RASSMOTREN V UPR.~20 I~21.) kROME
ZNACHENIYA~$a$ ZADAETSYA TAKZHE MODULX~$m$. tEST PROVERYAET STATISTICHESKUYU
NEZAVISIMOSTX POSLEDOVATELXNYH OTREZKOV IZ $n$~CHISEL. chASHCHE VSEGO TEST
PRIMENYAETSYA PRI~$n=2$, $3$, $4$ I INOGDA PRI NESKOLXKO BOLXSHIH ZNACHENIYAH~$n$.

v ALGORITME PREDPOLAGAETSYA, CHTO NA VHODE ZADANY~$a$, $m$ I~$n$;
VYCHISLYAETSYA~$q=\nu_n^2$ (SM.~(12)). iSPOLXZUYUTSYA
$n\times n\hbox{-MATRICY}$~$Q$ I~$R$ I VSPOMOGATELXNYE $n\hbox{-MERNYE}$
VEKTORY~$X$ I~$c$. vSE OPERACII S CELYMI CHISLAMI DOLZHNY PROIZVODITXSYA
TOCHNO; DLYA |TOGO MOZHET POTREBOVATXSYA PRIVLECHENIE OPERACIJ S POVYSHENNOJ
TOCHNOSTXYU. bOLEE PODROBNO |TOT VOPROS BUDET RASSMOTREN NIZHE.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX~$X[1]\asg1$, $X[k+1]\asg (aX[k])\bmod m$
DLYA~$1\le k < n$. eSLI KAKOE-LIBO~$X[k]$ BOLXSHE~$m/2$,
USTANOVITX~$X[k]\asg X[k]-m$. zATEM SFORMIROVATX MATRICY
$$
\eqalign{
Q&=\pmatrix{
   m^2  &  -m X_2 & -m X_3  & \ldots & -m X_n  \cr
 -m X_2 & 1+X_2^2 & X_2 X_3 & \ldots & X_2 X_n \cr
 -m X_3 & X_2 X_3 & 1+X_3^2 & \ldots & X_3 X_n \cr
 \vdots &         &         &        & \vdots  \cr
 -m X_n & X_2 X_n & X_3 X_n & \ldots & 1+X_n^2 \cr
},\cr
R&=\pmatrix{
 \sum X_j^2 & m X_2 & m X_3 & \ldots & m X_n  \cr
      m X_2 & m^2   & 0     & \ldots & 0      \cr
      m X_3 & 0     & m^2   & \ldots & 0      \cr
     \vdots &       &       &        & \vdots \cr
       mX_n & 0     & 0     & \ldots & m^2    \cr
}.\cr
}
\eqno(29)
$$
dLYA |TOGO USTANOVITX~$Q[1, 1]\asg m^2$, $R[1, 1]\asg \sum_{1\le j \le n} X[j]^2$;
DLYA~$1<j\le n$ USTANOVITX~$Q[1,j]\asg Q[j,1]\asg -mX[j]$, $R[1,j]\asg R[j,1]\asg mX[j]$,
$Q[j, j]\asg 1+X[j]^2$, $R[j,j]\asg m^2$; I DLYA~$1<j<k\le n$
USTANOVITX~$Q[j, k]\asg Q[k, j]\asg X[j]X[k]$, $R[j,k]\asg R[k,j]\asg 0$.
(eTO TE SAMYE MATRICY~$Q$ I~$R$, KOTORYE FIGURIRUYUT V~(19), ZA
ISKLYUCHENIEM TOGO, CHTO~$R=m^2Q^{-1}$, A NE~$Q^{-1}$, TAK CHTO VSE
POSLEDUYUSHCHIE VYCHISLENIYA PROIZVODYATSYA S CELYMI CHISLAMI.)

dALEE POLAGAEM~$k\asg n$ I~$q\asg m^2$.

\st[nAJTI MINIMUM~$Q_{jj}$.] dLYA~$1\le j \le n$, ESLI~$Q[j, j]<q$,
 USTANOVITX~$q\asg Q[j, j]$.

%% 119

\st[pEREHODITX K PEREBORU?] dLYA~$1\le j \le n$ USTANOVITX~$c[j]\asg \floor{\sqrt{qR[j,j]}/m}$.
eSLI TEPERX~$\prod_{1\le j \le n} (2c[j]+1)\le 1000$,
PEREJTI K SHAGU~\stp{6}. (sOGLASNO LEMME~A, DLYA MINIMALXNOGO
RESHENIYA~$X[1]$,~\dots, $X[n]$ PRI LYUBOM~$j$  VYPOLNYAETSYA USLOVIE---$c[j]\le X[j]\le c[j]$.
sMYSL DANNOGO SHAGA V TOM, CHTOBY PEREJTI NA~\stp{6}, ESLI
DLYA POISKA TOCHNOGO MINIMUMA TREBUETSYA PEREBRATX NE BOLEE~$1000$,---A NA
SAMOM DELE, KAK BUDET POKAZANO NIZHE,--- MENEE $500$~SLUCHAEV. kONECHNO, NET
NEOBHODIMOSTI VYCHISLYATX TOCHNOE ZNACHENIE~$\prod (2c_j+1)$; PRI |TOM, KSTATI,
VOZMOZHNO PEREPOLNENIE. dOSTATOCHNO UBEDITXSYA, PREVYSHAET LI |TO ZNACHENIE~$1000$.)

\st[pREOBRAZOVATX.] dLYA~$1\le j \le n$, $j\ne k$, PRISVOITX~$c[j]$
CELYE ZNACHENIYA, KAK MOZHNO BOLEE BLIZKIE K~$Q[j,k]/Q[k,k]$,
NAPRIMER~$\floor{Q[j,k]/Q[k,k]+{1\over2}}$ (SM.~(27)). zATEM DLYA~$1\le j \le n$,
$j\ne k$ I~$c[j]\ne 0$ VYPOLNITX OPERACII~$|TRANS|(Q, j, k,-c[j])$ I~$|TRANS|(R, k, j, c[j])$.

oPERACIYA~$|TRANS|(P, i, j, t)$ NAD MATRICEJ~$P$ OPREDELYAETSYA SLEDUYUSHCHIM
OBRAZOM. dLYA~$1\le r \le n$ USTANOVITX~$P[i,r]\asg P[i,r]+tP[j,r]$;
\emph{ZATEM} DLYA~$1\le r \le n$ USTANOVITX~$P[r,i]\asg R[r,i]+tP[r, j]$.
[tAKIM OBRAZOM, STROKA~$j$ UMNOZHAETSYA NA~$t$ I PRIBAVLYAETSYA K STROKE~$i$,
ZATEM STOLBEC~$j$ UMNOZHAETSYA NA~$t$ I PRIBAVLYAETSYA K STOLBCU~$i$. v
REZULXTATE NA SHAGE~\stp{4} PROIZVODITSYA PREOBRAZOVANIE~(24) S
ISPOLXZOVANIEM MATRICY~$U$ VIDA~(25).]

\st[iZMENITX~$k$.] uMENXSHITX~$k$ NA~$1$; ZATEM, ESLI~$k=0$,
USTANOVITX~$k\asg n$. pEREJTI NA~\stp{2}.

\st[pODGOTOVKA K PEREBORU.] (tEPERX BUDET OPREDELYATXSYA ABSOLYUTNYJ
MINIMUM S POMOSHCHXYU PRYAMOGO PEREBORA.) uSTANOVITX~$k\asg n$ I~$X[j]\asg 0$
DLYA~$1\le j \le n$.

\st[pEREJTI K SLEDUYUSHCHEMU ZNACHENIYU~$X[k]$.] uSTANOVITX~$X[k]\asg X[k]+1$.
eSLI~$X[k]>c[k]$, PEREJTI NA~\stp{9}.

\st[pEREJTI K SLEDUYUSHCHEMU~$k$.] uSTANOVITX~$k\asg k+1$. eSLI~$k\le n$,
USTANOVITX~$X[k]\asg -c[k]$ I POVTORITX SHAG~\stp{8}. eSLI~$k>n$,
USTANOVITX~$q'\asg \sum_{1\le i \le n} \sum_{1\le j \le n} X[i]X[j]Q[i,j]$,
I, ESLI~$q'<q$, USTANOVITX~$q\asg q'$.

\st[uMENXSHITX~$k$.] uSTANOVITX~$k\asg k-1$. eSLI~$k\ge 1$,
VERNUTXSYA NA~\stp{7}, V PROTIVNOM SLUCHAE VYPOLNENIE ALGORITMA
ZAKANCHIVAETSYA. (zAMECHANIE: SHAGI~\stp{6}--\stp{9} YAVLYAYUTSYA
PROSTEJSHIM SLUCHAEM METODA OBRATNOGO PEREBORA, KOTORYJ PODROBNO OPISAN V GL.~7.)
\algend

oPREDELENNAYA S POMOSHCHXYU |TOGO ALGORITMA VELICHINA~$q$ POZVOLYAET
VYCHISLITX~$\nu_n=\sqrt{q}$ I OPREDELITX~$C_n$ PO FORMULE~(15). zNACHENIE
%%120
VELICHIN~$\nu_n$ I~$C_n$ I USLOVIYA, PRI VYPOLNENII KOTORYH MOZHNO
SCHITATX, CHTO MNOZHITELX~$a$ PROSHEL ISPYTANIE UDOVLETVORITELXNO,
OBSUZHDALISX VYSHE V PODPUNKTE~v.

tAK KAK OBYCHNO~$m$---|TO RAZMER SLOVA MASHINY, NA KOTOROJ PROIZVODITSYA
REALIZACIYA ALGORITMA~S, NEOBHODIMO PRI RASCHETAH PO |TOMU ALGORITMU
POLXZOVATXSYA ARIFMETIKOJ NAD CELYMI CHISLAMI S UVELICHENNOJ TOCHNOSTXYU.
oPYT POKAZYVAET, CHTO DOSTATOCHNO TROJNOJ TOCHNOSTI (KOGDA KAZHDOE CELOE CHISLO
RAZMESHCHAETSYA V TREH YACHEJKAH). nAPRIMER, PRI PODGOTOVKE TABL.~1 AVTOR
ISPOLXZOVAL 76-RAZRYADNUYU ARIFMETIKU. eTOGO BYLO DOSTATOCHNO PRI~$m=10^{10}$
I~$n\ge 6$, ODNAKO PRI~$m=2^{35}$ VO MNOGIH SLUCHAYAH
PROISHODILO PEREPOLNENIE. pO-VIDIMOMU, POCHTI DLYA VSEH VARIANTOV
S~$m=2^{35}$ BUDET DOSTATOCHNO PRIMERNO 90~DVOICHNYH RAZRYADOV.
kAKIH-LIBO TEORETICHESKIH DANNYH OTNOSITELXNO VELICHINY
PROMEZHUTOCHNYH REZULXTATOV POKA NE SUSHCHESTVUET.

nA PRAKTIKE ALGORITM~S OKAZYVAETSYA UDIVITELXNO |FFEKTIVNYM;
PRI~$m=2^{35}$ CHISLO POVTORENIJ SHAGOV~S2--S5 OKAZYVALOSX RAVNYM~$6$, $10$,
$14$, $17$, $21$ DLYA~$n=2$, $3$, $4$, $5$, $6$. oDNAKO DO SIH POR NET
TEORII, POLNOSTXYU OPISYVAYUSHCHEJ ALGORITM, I NA SAMOM DELE V NEKOTORYH
SLUCHAYAH \emph{METOD MOZHET PROSTO ZACIKLITXSYA.} tAK CHTO TERMIN "ALGORITM" V
DANNOM SLUCHAE, STROGO GOVORYA, NEPRIMENIM. lEGKO IZMENITX |TU PROCEDURU TAK,
CHTOBY CHISLO ITERACIJ BYLO OGRANICHENO (SM.~UPR.~16). dOSTATOCHNO VVESTI
ESHCHE ODNU PEREMENNUYU~$d$ I USTANAVLIVATX~$d\asg 0$ NA SHAGE~S1 I V
OPERACII~|TRANS|. kROME TOGO, V KONCE SHAGA~S3 DOBAVITX: "$d\asg d+1$;
ESLI~$d>n$, PEREJTI NA~S6". oDNAKO, VOZMOZHNO, CHTO |TO PRIVEDET K OCHENX
DLINNOMU PEREBORU NA SHAGAH~S6--S9, KAK POKAZANO V UPR.~18. v TAKOJ
SITUACII ZNACHITELXNYMI PREIMUSHCHESTVAMI OBLADAYUT PRIEMY, KOTORYE OBSUZHDAYUTSYA
V UPR.~22 I~23. aLGORITM ZACIKLIVAETSYA PRI~$n=2$, $a=1025$, $m=2^{46}$,
HOTYA PODOBNAYA NEUDACHA BYVAET REDKO.

v ODNOM IZ PROSCHITANNYH AVTOROM SLUCHAEV PRI~$n=6$ "OZHIDAEMAYA DLINA
PEREBORA"~$\prod (2c_j+1)$ NA SHAGE~S3 PRINIMALA POSLEDOVATELXNO
SLEDUYUSHCHIE ZNACHENIYA:
$$
\eqalign{
 &1\times 10^{43}, 6\times 10^{42}, 2\times 10^{42}, 9\times 10^{41},
   2\times 10^{41}, 6\times 10^{33}, 4\times 10^{33},\cr
 &1\times 10^{29}, 1\times 10^{20}, 6\times 10^{19}, 4\times 10^{18},
   9\times 10^{12}, 4\times 10^{10}, 3\times 10^{8},\cr
 &1\times 10^8, 8\times 10^7, 1\times 10^7, 7\times 10^6, 1.7\times 10^7,
   1.8\times 10^7, 7\times 10^5,\cr
 &1\times 10^5, 5\times 10^4, 3825, 3825, 675.\cr
}
$$

tAKIM OBRAZOM, |TA VELICHINA UMENXSHAETSYA OT~$10^{43}$ DO ZNACHENIYA
NIZHE~$1000$, PRICHEM NE MONOTONNO: DVAZHDY ZNACHENIE \emph{UVELICHIVAETSYA.}
vEROYATNO, DALXNEJSHIE ITERACII ESHCHE BOLXSHE SNIZYAT ZNACHENIE~$675$, TAK CHTO,
PO-VIDIMOMU, KONSTANTU~$1000$ V SHAGE~S3 SLEDUET UMENXSHITX, SKAZHEM,
DO~$100$. (\emph{zAMECHANIE.} iSTINNOE CHISLO NABOROV~$X[1]$,~\dots, $X[n]$,
ISPYTANNYH V POLNOM PEREBORE (SHAGI
%%121
\bye