Permutations with Low Discrepancy Consecutive k-sums

✍ Scribed by Richard Anstee; Ron Ferguson; Jerrold R. Griggs

• Book ID: 102587398
• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 160 KB
• Volume: 100
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.2002.3304

✦ Synopsis

Consider the permutation p ¼ ðp 1 ; . . . ; p n Þ of 1; 2; . . . ; n as being placed on a circle with indices taken modulo n: For given k4n there are n sums of k consecutive entries. We say the maximum difference of any consecutive k-sum from the average k-sum is the discrepancy of the permutation. We seek a permutation of minimum discrepancy. We find that in general the discrepancy is small, never more than k þ 6; independent of n: For g ¼ gcdðn; kÞ > 1; we show that the discrepancy is 4 7 2 : For g ¼ 1 it is more complicated. Our constructions show that the discrepancy never exceeds k=2 by more than 9 for large n; while it is at least k=2 for infinitely many n:

We also give an analysis for the easier case of linear permutations, where we view the permutation as written on a line. The analogous discrepancy is at most 2 for all