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
Normal 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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references