Distribution of nonlinear congruential pseudorandom numbers modulo almost squarefree integers (Q2503138)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Distribution of nonlinear congruential pseudorandom numbers modulo almost squarefree integers |
scientific article |
Statements
Distribution of nonlinear congruential pseudorandom numbers modulo almost squarefree integers (English)
0 references
14 September 2006
0 references
Let \(M\geq 2\) be an integer. By \(\rho(M )\) denote the largest squarefree divisor \(R\) of \(M\) with gcd\((R, M/R) = 1,\) and by \(\omega(M )\) the number of distinct prime divisors of \(M\). Let \(\mathbb Z_M = \mathbb Z/M\mathbb Z\) be the residue ring modulo \(M\). Define a sequence \((u_n )\) by \(u_{n+1} = f (u_n )(\text{mod }M ), 0\leq u_n\leq M - 1, n = 0, 1, \dots ,\) with an initial value \(u_0 = v\in \mathbb Z_M\), where \(f (X)\in \mathbb Z_M [X]\) is a polynomial of degree \(d\geq 2\). Let \(D_s (v; M, N )\) denote the discrepancy of the points \((u_n /M, \dots, u_{n+s-1} /M ), n = 0, \dots , N -1\) in the \(s\)-dimensional unit cube \([0, 1)^s\). The authors prove that if \(\omega(M )\leq 2 \log \log M\), and \(\rho(M ) \geq M (\log \log M )^{-2}\), and the sequence \((u_n )\) is purely periodic with period \(t\geq N\), then we have \[ D_s (v; M, N ) = O(N^{ -1/2} M^{ 1/2} (\log \log M )^{s+1/2} (\log M )^{-1/2} ), \] where and later on the implied constant depends only on \(s\) and \(d\). Moreover, if \(f (X)\in \mathbb Z_M [X]\) is a permutation polynomial of degree \(d\geq 2\) modulo every prime divisor of \(M\), then for \(N\geq (\log M/ \log \log M )^{3/2}\), the discrepancy bound on average \[ \delta_{s} (M, N ) :=\frac {1}{M}\sum_{v\in \mathbb Z_M} D_s (v; M, N ) = O((\log \log M )^{s+1/2} (\log M )^{-1/2} ) \] is proved.
0 references
pseudorandom number
0 references
nonlinear congruential method
0 references
discrepancy
0 references
exponential sums
0 references
0 references
0 references
0 references
0 references