On finite pseudorandom lattices of \(k\) symbols (Q5962362): Difference between revisions

The finite binary sequences and their generalization -- sequences of \(k\) symbols -- have many applications in different branches of science, specially in Monte Carlo methods. The measures of pseudorandomness show the quality of these sequences. In the present paper measures for pseudorandomness of lattices of \(k\) symbols are introduced and studied for ``truly random'' lattices. In the introduction of the paper, a brief review of the measures for the pseudorandomness of binary sequences, as the well-distribution measure and the correlation measure of order \(l\), are given. Sequences in several dimension, the so-called \(n\)-dimensional \(N\)-lattices, which is related with the function \(\eta({\mathbf x})\) are considered. In Definition 1 the notion of a pseudorandom measure of order \(l\) of \(\eta\) \(Q_l(\eta)\) is reminded. The asymptotic behaviour of \(Q_l(\eta)\) is discussed. In Section 2 the pseudorandomness of lattices of \(k\) symbols are studied. In Definition 2 two measures \(\omega_l(\eta, \cdot)\) and \(\Omega_l(\eta)\) for pseudorandomness of a lattice of \(k\) symbols are introduced. They are a generalization of the \(\varepsilon\)-well-distribution measure. In Theorem 1 it is shown that with a probability bigger or equal to \(1 - \varepsilon\), the measure \(\Omega_l(\eta)\) has a low bound \(\displaystyle \delta{N^{n \over 2} \over k \sqrt{k}}\) and with a probability less than \(\varepsilon\), the measure \(\Omega_l (\eta)\) has a low bound \(6 k^2(lN^n \log N^n)^{1 \over 2}.\) Section 3 is devoted to present and prove four auxiliary lemmas, which are used to prove the main result of the paper. In Section 4 Theorem 1 is proved. In section 5 a construction whose pseudorandom measure has a good upper bound is presented. The concrete lattice \(\eta({\mathbf x})\) is defined. In Theorem 2 the measure \(\Omega_l(\eta)\) of the \(n\)-dimensional lattice \(\eta\) is estimated from above with the quantity \(k l q^{1 \over 2}(1 + \log p)^n\). To the end of this section Theorem 2 is proved.