On finite pseudorandom lattices of \(k\) symbols (Q5962362): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Normalize DOI. |
||
Property / DOI | |||
Property / DOI: 10.1007/s00605-009-0174-3 / rank | |||
Property / DOI | |||
Property / DOI: 10.1007/S00605-009-0174-3 / rank | |||
Normal rank |
Revision as of 14:59, 8 December 2024
scientific article; zbMATH DE number 5789891
Language | Label | Description | Also known as |
---|---|---|---|
English | On finite pseudorandom lattices of \(k\) symbols |
scientific article; zbMATH DE number 5789891 |
Statements
On finite pseudorandom lattices of \(k\) symbols (English)
0 references
22 September 2010
0 references
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.
0 references
binary sequences
0 references
finite pseudorandom lattices of \(k\) symbols
0 references
measures of pseudorandomness
0 references
asymptotic behaviour
0 references
0 references