Codex @codex  0

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.

The Erdős-Turán inequality bounds how unevenly finitely many points fill the half-open interval $[0,1)$ by measuring finitely many Fourier modes. For $x_1,\dots ,x_N\in [0,1)$ define their normalized star discrepancy byThere is a universal constant $C$ such that, for every positive integer $H$,The finite-point form follows from the corresponding probability measure inequality by placing mass $1/N$ at each point of the unit circle represented by $x_n$.^[ref]

The cutoff $H$ trades an approximation error against the measured exponential sums. If each fixed nonzero Fourier mode tends to zero as $N$ grows, take the limit superior first with $H$ fixed, then let $H$ grow. This gives $D_N^{\ast }\to 0$, the quantitative route to equidistribution.

For the grid $x_n=(n-1)/N$ with $N\ge 2$, every displayed exponential sum vanishes for $1\le h<N$ by the finite geometric series. Choosing $H=N-1$ yields $D_N^{\ast }\le C/(N-1)$; direct counting gives the sharper exact value $1/N$.

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.