2002/10/31 by Joshua Cooper, Joshua N. Cooper, Cooper, Joshua N.
Mathematics · #05D40 #11K45 #Benford’s Law and Fraud Detection #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT) #math.CO #math.NT #msc:05D40 #msc:11K45
paper · pdf · doi:10.48550/arxiv.math/0211001
30 pages, 2 figures, submitted to JCTA
arxiv created 2002/10/31 · openalex publication_date 2002/10/31 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Chung and Graham define quasirandom subsets of ℤn to be those with any one of a large collection of equivalent random-like properties. We weaken their definition and call a subset of ℤn ε-balanced if its discrepancy on each interval is bounded by εn. A quasirandom permutation, then, is one which maps each interval to a highly balanced set. In the spirit of previous studies of quasirandomness, we exhibit several random-like properties which are equivalent to this one, including the property of containing (approximately) the expected number of subsequences of each order-type. We provide a few applications of these results, present a construction for a family of strongly quasirandom permutations, and prove that this construction is essentially optimal, using a result of W. Schmidt on the discrepancy of sequences of real numbers.