Discrepancy theory ($\mathrm{disc}(\mathcal{F})$)

Discrepancy theory measures how evenly a finite configuration or coloring can satisfy many constraints at once. For a finite set $X$ and a family $\mathcal{F}$ of subsets, its two-color discrepancy isThe sum is the difference between the two color counts in $S$. A single balanced total does not guarantee small discrepancy on every constrained subset.

If $X=\{1,\dots ,n\}$ and $\mathcal{F}$ contains all contiguous intervals, alternating the colors gives discrepancy at most one: each even-length interval has equal counts, and each odd-length interval differs by one. Singleton constraints show that one is optimal. More complicated overlapping families can force much larger imbalance.

A related geometric formulation compares point counts in test regions with their expected volume. Star discrepancy uses boxes anchored at the origin. Such bounds quantify how well a deterministic point set approximates uniform integration, linking combinatorics with numerical integration.

For points $x_1,\dots ,x_N$ in $[0,1{)}^d$, star discrepancy compares their empirical frequencies in anchored boxes with Lebesgue measure:The half-open box convention makes boundary membership precise. Small star discrepancy means that every such box contains nearly its uniform share of points; it does not mean the points are independent random samples.

In one dimension, take midpoint points $x_i=(i-1/2)/N$. Between consecutive points, the empirical count is constant while the interval length increases linearly. Just before or after a point the largest difference is $1/(2N)$, so $D_N^{\ast }=1/(2N)$. Repeating a single point instead leaves large gaps and large discrepancy. The definition directly controls the integration error for indicators of anchored boxes and motivates deterministic sampling for numerical integration.