Six Permutation Patterns Force Quasirandomness

arXiv2303.04776MaRDI QIDQ6428871FDOQ6428871

Authors: Gabriel Crudele, Peter Dukes, Jonathan A. Noel 

Publication date: 8 March 2023

Abstract: A sequence $p{i}_1,p{i}_2,dots$ of permutations is said to be "quasirandom" if the induced density of every permutation $sigma$ in $p{i}_n$ converges to $1/|sigma|!$ as $noinfty$. We prove that $p{i}_1,p{i}_2,dots$ is quasirandom if and only if the density of each permutation $sigma$ in the set ${\displaystyle }${123,321,2143,3412,2413,3142}${\displaystyle }$ converges to $1/|sigma|!$. Previously, the smallest cardinality of a set with this property, called a "quasirandom-forcing" set, was known to be between four and eight. In fact, we show that there is a single linear expression of the densities of the six permutations in this set which forces quasirandomness and show that this is best possible in the sense that there is no shorter linear expression of permutation densities with positive coefficients with this property. In the language of theoretical statistics, this expression provides a new nonparametric independence test for bivariate continuous distributions related to Spearman's $ho$.

This page was built for publication: Six Permutation Patterns Force Quasirandomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6428871)