On the minimum number of completely 3-scrambling permutations

A family P={π1,…,πq}P={π1,…,πq} of permutations of [n]={1,…,n}[n]={1,…,n} is completely k-scrambling [Spencer, Acta Math Hungar 72; Füredi, Random Struct Algor 96] if for any distinct k   points x1,…,xk∈[n]x1,…,xk∈[n], permutations πiπi's in PP produce all k!k! possible orders on πi(x1),…,πi(xk)πi(x1),…,πi(xk). Let N*(n,k)N*(n,k) be the minimum size of such a family. This paper focuses on the case k=3k=3. By a simple explicit construction, we show the following upper bound, which we express together with the lower bound due to Füredi for comparison. 2log2elog2n⩽N*(n,3)⩽2log2n+(1+o(1))log2log2n.We also prove the existence of limn→∞N*(n,3)/log2n=c3. Determining the value c3c3 and proving the existence of limn→∞N*(n,k)/log2n=ck for k⩾4k⩾4 remain open.