Discrepancy and distance between sets (Q1196262): Difference between revisions

Let \(S,T\) denote finite subsets of \([0,1]\) of equal cardinality. Then \(| S-T|=\min_ f \max_{s\in S}| f(s)-s|\) denotes the distance of the two sets, where the min runs through all bijections \(f: S\to T\). \textit{J. G. van der Corput} and \textit{C. Pisot} [Indag. Math. 1, 476-486, 554-565, 713-722 (1939; Zbl 0021.29701, Zbl 0022.11604, Zbl 0022.11605)] have shown that \(| D(S)-D(T)|\leq| S-T|\), where \(D(S)\) denotes the usual discrepancy of the point set \(S\) (and similarly for \(T\)). The present paper starts with a partial converse \[ | S-T|\leq D(S)+D(T)-1/n, \] \(n\) denoting the common cardinality of \(S\) and \(T\). Then similar results are proved for the \(L^ p\)-discrepancy \(D_ p(S)\) and the \(L^ p\)-distance \[ \| S-T\|_ p=\min_ f \sum_{s\in S}| f(s)-s|^ p. \] For instance, it is shown that \(| D_ p^ p(S)-D_ p^ p(T)|\leq c | S-T|\) with some constant \(1\leq c\leq 2\).