Tusnády Problem Guide

Contents

Introduction

This guide answers three questions

The main result of the paper takes one line: the worst-case combinatorial discrepancy of $n$ points in the plane with respect to axis-parallel rectangles is $\Theta(\log^{3/2} n)$ . Three questions surround it, and the guide takes them in this order.

Why earlier methods fell short

The earlier lower-bound methods all stopped at $\log n$ . Part II explains, one by one, how they work and where their ceiling is.

Why it works now

The paper asks a different question. The points are placed at random. First fix one coloring and show that the probability that it is “good” is as small as $e^{-cn}$ ; then rule out all $2^n$ colorings together. Part III explains this change of question.

What the new technique is

A quantity called “local oscillation”. On a good transition, refining horizontally and merging vertically gives a positive conditional expected gain. With the past fixed, changing one point’s next horizontal digit changes the new potential only a little. Part IV gives the full derivation.

Prerequisites

The guide assumes only second-year undergraduate mathematics: sums and inequalities, exponentials and logarithms, probability, expectation and independence. Tools such as conditional expectation and the Cauchy–Schwarz inequality are explained, with a proof, in a box labeled “Tool” where they first appear. Collapsible blocks labeled “Derivation” or “Proof” are complete proofs and are open by default. Blocks labeled “Optional” can be skipped without losing the main line. The line above each section title gives its level: Basics, Intermediate, or Core argument.

Overview: the proof in five sentences

§ 8Place

n

points independently and uniformly at random in the unit square. Fix a coloring

\chi

, and let

F_\chi(x,y)

be the signed count of the points in the anchored rectangle

[0,x]\times[0,y]

[0, y]

. If the probability that “

F_\chi

is small everywhere” is much smaller than

2^{-n}

, a union bound rules out all

2^n

colorings at once.

§ 11–12Cut the square in base

b

. At stage

j

, the horizontal intervals have width

b^{-j}

and the vertical blocks have height

b^{j-h}

. For each horizontal interval take the average

a_I(y)

of the values at its two endpoints, measure its maximum minus its minimum on each block, and then average over all intervals and blocks. This gives

Z_j

. It satisfies

Z_j\ge0

and

Z_j\le2\max|F_\chi|

2 max ∣ F_{χ} ∣

§ 13–15Refining by one step horizontally and merging by one step vertically is one transition; there are

h

transitions in all. In each “comparison rectangle”, the sum of the oscillations after the refinement does not decrease on average, and it gains something extra: at least

\frac14\sqrt{m_R}

, where

m_R

is the number of points in the inner region of the comparison rectangle. On the other hand, changing the next digit of one point changes

Z

by at most

\frac1M

, where

M

is the number of comparison rectangles in each transition.

§ 16–17Split the total increase of

Z

into the “conditional gains” of the transitions and one “fluctuation term”. As long as the points are spread out, the conditional gain of a transition is at least a constant multiple of

\sqrt{n/M}

, where

\frac nM

is the average number of points of a comparison rectangle. The points are spread out at all

h

transitions with overwhelming probability, and this event does not depend on the coloring. The probability that the fluctuation term is very negative is controlled by the bounded-differences inequality; it is so small that it stays small after multiplication by

2^n

§ 18Take the number of transitions

h

of order

\log n

, and

\frac nM

of order

h

. Then, outside an exceptional event of probability at most

e^{-An}

, every coloring has

\max|F_\chi|>\frac h{64b^{3/2}}\sqrt{n/M}

\frac{h}{64 b ^{3/2}} n / M

, which is of order

h^{3/2}

, that is, of order

\log^{3/2}n

All of this notation is defined later. On a first reading the general idea is enough.

This guide is based on version r65 of the paper, provided by the author. Part IV follows the proof in Section 2 of the paper section by section: equations (1)–(18), Lemmas 2.1 and 2.3–2.6, Fact 2.2, Proposition 2.7, and Fact A.1 of the appendix all carry the same numbers as in version r65. The proof in the paper is compact; the guide fills in the steps it omits and adds examples and interactive figures. Section 20 gives the paper's four-step summary and matches it to the sections of the guide. The derivations, examples and interactive figures added by the guide are no substitute for formal verification, nor for independent review. For every statement the paper is authoritative. Material marked “Background” comes from the related literature and is not in the body of the paper.

Part I · Sections 1–3

The problem

First we make the problem itself clear: how the coloring game is played, why one dimension is easy, where the difficulty lies in two dimensions, and what notation such as “ $\log^{3/2} n$ ” actually says.

§ 1 · BasicsA coloring game

There are $n$ points in the plane. Your task is to color each point red or blue. When you are done, an opponent may pick any rectangle with sides parallel to the coordinate axes and count how many more red points than blue points it contains, or how many fewer. The absolute value of this difference, the imbalance of the rectangle, is your loss.

You want the loss to be as small as possible, and the colors must be fixed before the opponent picks the rectangle. So a coloring is judged by how it does on the worst rectangle.

Trying a few point sets shows two things. First, when there are few points, the optimum is usually just 1 or 2. Second, a coloring chosen without much thought is often far from the optimum. The question of the whole paper is: when the number of points $n$ is large, how large can this optimum be in the worst case?

To make computations easier, from now on red is written $+1$ and blue is written $-1$ . Then “the number of red points minus the number of blue points” in a rectangle is the sum of the colors of all points in it.

§ 2 · BasicsFrom one dimension to two

One dimension: alternating colors are enough

Start with the simple case. If all points lie on a line, a “rectangle” degenerates to an interval. Sort the points from left to right and color them red and blue alternately.

The points in an interval form a consecutive run in the sorted order. A consecutive run of alternating

\pm1

can only add up to

-1

0

+1

The answer in one dimensionWarm-up

Take any $n\ge1$ points on a line and color them alternately in sorted order. Then the sum of the colors in every interval has absolute value at most $1$ . So in one dimension the discrepancy is always $1$ , independently of $n$ .

Two dimensions: alternating along one coordinate is not enough

Points in the plane have two orders: one by $x$ -coordinate and one by $y$ -coordinate. If we alternate the colors by $x$ -coordinate only, every vertical strip is well balanced, but horizontal strips can be very bad. The playground above has a “Special point set” button. It puts the points in odd positions of the $x$ -order in the lower half and those in even positions in the upper half. If we now alternate by $x$ , all points in the lower half of the square are red.

Worse, a rectangle puts conditions on $x$ and on $y$ at the same time. The points that fall in a rectangle need not be consecutive in the $x$ -order, and they need not be consecutive in the $y$ -order either. The “consecutive run” argument from one dimension does not apply at all.

This is exactly what Tusnády asked: can one also achieve some constant independent of $n$ in two dimensions? In 1981 Beck answered this question negatively, and at the same time proved that the discrepancy is at most of order $\log^4 n$ . Since then, the problem has been to determine its exact rate of growth.

“Anchored rectangles” are enough

First translate the point set into the first quadrant, so that all coordinates are positive. A rectangle $A(x,y)=[0,x]\times[0,y]$ $[0, y]$ , whose lower left corner is fixed at the origin, is called an anchored rectangle. It has only two parameters and is much easier to handle than a general rectangle. Moreover, looking only at anchored rectangles loses at most a factor of 4.

The lower left piece is subtracted twice, so it has to be added back once. This is the inclusion–exclusion principle.

As a formula: for a rectangle $R=(x_1,x_2]\times(y_1,y_2]$ and any coloring $\chi$ ,

\begin{aligned}\chi(P\cap R)={}&\chi\bigl(P\cap A(x_2,y_2)\bigr)-\chi\bigl(P\cap A(x_1,y_2)\bigr)\\&-\chi\bigl(P\cap A(x_2,y_1)\bigr)+\chi\bigl(P\cap A(x_1,y_1)\bigr).\end{aligned}

Each of the four terms on the right has absolute value at most “the maximum imbalance over anchored rectangles”, so the imbalance of a general rectangle is at most 4 times that. Conversely, an anchored rectangle is itself a rectangle. Hence the discrepancies under the two definitions differ by a constant factor of at most 4, and for the rate of growth it is enough to look at anchored rectangles. The lower bound of the paper even holds directly for anchored rectangles.

§ 3 · BasicsNotation and growth rates

Three levels of min and max

Let $P$ be a finite set of points in the plane. A coloring is a function $\chi:P\to\{+1,-1\}$ ${+ 1, - 1}$ . For a set $R$ in the plane, write

\chi(P\cap R)=\sum_{p\in P\cap R}\chi(p).

The discrepancy of the point set $P$ , and the worst-case discrepancy of $n$ points, are defined as

\disc(P)=\min_{\chi}\ \max_{R}\ \bigl|\chi(P\cap R)\bigr|,\qquad \Delta_2(n)=\max_{|P|=n}\disc(P),

where $R$ ranges over all axis-parallel rectangles. The subscript 2 stands for the plane. The three levels can be read as a game with three moves:

maxThe opponent first chooses the positions of the

n

points, to make things hard for you.

minAfter seeing the points, you choose a coloring

\chi

, so that even the worst rectangle is balanced.

maxAfter seeing the coloring, the opponent chooses a rectangle

R

, the one with the largest imbalance.

Pitfall

Proving an upper bound and proving a lower bound are two entirely different tasks. This distinction will be used again and again.

Upper bound $\Delta_2(n)\le K$ $K$ : for every $n$ -point set, we must find one coloring under which every rectangle has imbalance at most $K$ .

Lower bound $\Delta_2(n)> K$ $K$ : we must find one $n$ -point set for which every coloring leaves some rectangle with imbalance more than $K$ . There are $2^n$ colorings, and all of them have to be ruled out, without exception.

Asymptotic notation

We care about the rate of growth as $n\to\infty$ $\infty$ , not about constant factors. The three symbols mean the following:

$f(n)=O(g(n))$ $O (g (n))$ : there is a constant $C$ such that $f(n)\le C\,g(n)$ when $n$ is large enough. Read: “of order at most $g$ ”.
$f(n)=\Omega(g(n))$ $Ω (g (n))$ : there is a constant $c>0$ such that $f(n)\ge c\,g(n)$ when $n$ is large enough. Read: “of order at least $g$ ”.
$f(n)=\Theta(g(n))$ $Θ (g (n))$ : both of the above hold, so the order is completely determined.

Also, $\log^{3/2}n$ is shorthand for $(\log n)^{3/2}$ . The base of the logarithm does not affect the order, because changing the base only changes a constant factor. Where specific numbers are needed, we say whether we use the base-2 logarithm $\log_2$ or the natural logarithm $\ln$ .

Numerically, the two differ only by a factor of $\sqrt{\log_2 n}$ : about 4.5 for a million points. Compared with the $\sqrt{n\log n}$ that a random coloring can guarantee, both are tiny. But the mathematical question is which of the two is the true rate of growth, and “roughly the same” is not an answer to it.

The result of the paperCorollary 1.2 of the paper; it follows from Theorem 1.1 and Nikolov's upper bound

There is a constant $c>0$ such that $\Delta_2(n)\ge c\log^{3/2}n$ for every $n\ge1$ $1$ . Together with the known upper bound, $\Delta_2(n)=\Theta(\log^{3/2}n)$ $Θ (lo g^{3/2} n)$ .

What the paper actually proves is a stronger statement: a random point set is almost always this hard to color. The precise statement is in Section 8.

Part II · Sections 4–7

What was known, and why it stopped

The upper bound came down step by step from $\log^4 n$ to $\log^{3/2}n$ , while the lower bound stayed at $\log n$ . This part goes through the methods on both sides. The main question is where each lower-bound tool stops, and why.

§ 4 · BasicsHistory of the bounds

This part is background material. The paper only summarizes this work, with one paragraph in the introduction and one in Section 3 of the paper. The derivations here are taken from the standard literature; a few are supplied by this guide, and those are marked where they appear.

The upper bound and the lower bound were pushed forward with two entirely different sets of tools. The figure below shows the known results in one plot; the vertical axis is the exponent of $\log n$ .

Table view (Table 1 of the paper)

Bound	Reference	Year	Remark
$O(\log^4 n)$	Beck	1981
$O(\log^{3.5+\varepsilon} n)$	Beck	1989	every fixed $\varepsilon>0$
$O(\log^3 n)$	Bohus	1990
$O(\log^{2.5} n)$	Srinivasan	1997
$O(\log^2 n)$	Bansal and Garg	2017	constructive (gives an algorithm)
$O(\log^{3/2} n)$	Nikolov	2017
$\Omega(\log n)$	Schmidt	1972	via transference
$\Omega(\log n)$	Matoušek and Nikolov	2015	factorization norms; $\Omega(\log^{d-1}n)$ in dimension $d$
$\Omega(\log^{3/2} n)$	this paper		attained by random point sets

Three things can be read off the figure.

The upper-bound line comes down one step at a time and reaches $\log^{3/2}n$ in 2017.
The lower-bound line stays flat. Schmidt's 1972 theorem is about continuous discrepancy; it becomes a lower bound for the coloring problem only through the transference principle of Section 6. In 2015 a completely new method gave $\log n$ again.
This left a gap of $\sqrt{\log n}$ . It was not clear in advance which side was right: the paper notes that Bansal, in his talk at the 2022 International Congress of Mathematicians, conjectured that the lower bound $\log n$ is tight. The paper's result goes the other way: the upper bound $\log^{3/2}n$ is tight. The 2026 survey of Bansal and Nikolov also discusses this remaining gap in the plane.

Both ends of the gap were plausible. The order $\log n$ is the correct answer to another classical problem (continuous discrepancy, see Section 6). The order $\log^{3/2}n$ is what the best coloring method achieves. Whether the coloring methods could still be improved, or the lower-bound proofs were not strong enough, had not been settled.

§ 5 · IntermediateWhere the upper bound comes from

The paper proves the lower bound. But the ideas behind the upper bound contain a structure that returns in the lower-bound proof: split the problem into $\log n$ scales and pay a price at each scale. So it is worth a look first.

The simplest approach: random coloring

Each point gets its color from an independent coin flip. How far does this get? We need three tools from probability. Two of them, Markov's inequality and the union bound, will be used again later.

Tool · Markov's inequality

Let $X\ge0$ be a random variable and let $a>0$ $0$ . Then $\Pr[X\ge a]\le \EE[X]/a$ $E [X] / a$ .

The proof is one line: $\EE[X]\ge \EE\bigl[X\cdot\one_{\{X\ge a\}}\bigr]\ge a\cdot\Pr[X\ge a]$ $a]$ . In words: if a nonnegative quantity has a small mean, it is unlikely to be large.

Tool · Union bound

For any events $E_1,\dots,E_N$ , we have $\Pr[E_1\cup\dots\cup E_N]\le\sum_i\Pr[E_i]$ $\sum_{i} Pr [E_{i}]$ . The probability that at least one bad event happens is at most the sum of the probabilities of the bad events. Proof: the indicator of the union is at most the sum of the indicators of the events; take expectations on both sides.

Tool · Tail bound for a sum of

\pm1

signs

Let $S=\eps_1+\dots+\eps_s$ $ϵ_{s}$ , where the $\eps_i$ are independent and each takes the values $\pm1$ with equal probability. Then for every $a>0$ $0$ , $\Pr[\,|S|\ge a\,]\le 2e^{-a^2/(2s)}$ $2 e^{- a^{2} / (2 s)}$ .

ProofThe tail bound

For every $t>0$ $0$ , independence gives $\EE[e^{tS}]=\prod_i\EE[e^{t\eps_i}]=(\cosh t)^s$ $(cosh t)^{s}$ , where $\cosh t=\tfrac12(e^t+e^{-t})$ $e^{- t})$ .
Compare the power series term by term: $\cosh t=\sum_{k\ge0}\dfrac{t^{2k}}{(2k)!}$ and $e^{t^2/2}=\sum_{k\ge0}\dfrac{t^{2k}}{2^k\,k!}$ $\sum_{k \geq 0} \frac{t ^{2 k}}{2 ^{k} k !}$ . Since $(2k)!=k!\cdot(k+1)(k+2)\cdots(2k)\ge k!\cdot2^k$ $2^{k}$ , we get $\cosh t\le e^{t^2/2}$ $e^{t^{2} /2}$ .
Apply Markov's inequality to the nonnegative random variable $e^{tS}$ : $\Pr[S\ge a]=\Pr[e^{tS}\ge e^{ta}]\le e^{-ta}\,\EE[e^{tS}]\le e^{st^2/2-ta}$ $e^{s t^{2} /2 - t a}$ .
Take $t=a/s$ $a / s$ ; the exponent becomes $-a^2/(2s)$ . By symmetry, $\Pr[S\le -a]$ satisfies the same bound. Adding the two gives the claim.

Now fix an $n$ -point set and a rectangle $R$ . Suppose $R$ contains $s\le n$ points. Under a random coloring, $\chi(P\cap R)$ is exactly a sum of $s$ independent $\pm1$ signs. With $a=\sqrt{10\,n\ln n}$ $10 n ln n$ ,

\Pr\bigl[\,|\chi(P\cap R)|\ge a\,\bigr]\le 2e^{-a^2/(2n)}=2n^{-5}.

There are infinitely many rectangles, but they cut out only finitely many subsets of the points: a subset is determined by “which stretch of the $x$ -order” and “which stretch of the $y$ -order”, so there are at most $\bigl(\tfrac{n(n+1)}2\bigr)^2\le n^4$ of them. By the union bound, the probability that some rectangle exceeds the threshold is at most $n^4\cdot2n^{-5}=2/n$ $2/ n$ , which is less than 1 for $n\ge3$ $3$ . So some coloring keeps every rectangle below the threshold:

\Delta_2(n)\le\sqrt{10\,n\ln n}\qquad(n\ge3).

This bound is very far from the truth, which is a power of $\log n$ . But the derivation shows a basic technique: proving existence by probability. Part III will use the same technique in the reverse direction.

Splitting a prefix into dyadic intervals

To reach a power of $\log n$ we have to use the structure of rectangles. Divide the $x$ -direction into $m=2^h$ columns. An interval whose length is a power of $2$ and whose position is aligned is called a dyadic interval: level 0 is all of $[1,m]$ , level 1 consists of the left and right halves, and so on down to level $h$ , the single columns.

Two facts will be used later:

Every column belongs to exactly $h+1$ dyadic intervals, one per level.
Every prefix $[1,v]$ is a union of at most $h+1$ pairwise disjoint dyadic intervals, at most one per level. This is just the binary expansion of $v$ .

So an anchored rectangle (its width is a prefix $[1,v]$ , and its height runs up to some point) splits into at most $h+1$ “dyadic strips”. If a coloring keeps the error inside every dyadic strip at most $E$ , then the error of an anchored rectangle is at most $(h+1)E$ $1) E$ . Each strip on its own is a one-dimensional problem, which is easy. The difficulty is that one coloring has to serve all $h+1$ levels at once.

Historically, most upper bounds followed this idea of working level by level. The early proofs used partial coloring: each round fixes the colors of only some of the points while controlling the error on a family of standard rectangles, and leaves the remaining points for the next round. Every round and every scale loses something, so the result is a high power of $\log n$ . Later improvements mainly reduced these losses.

The best upper bound known

In 2017 Nikolov proved $\Delta_2(n)=O(\log^{3/2}n)$ $O (lo g^{3/2} n)$ . The proof relies on a deep theorem of Banaszczyk. The theorem itself is far beyond the second-year level, so we treat it as a black box and only look at how it combines with the dyadic decomposition.

OptionalFrom Banaszczyk's theorem to

O(\log^{3/2}n)

: a skeleton

Banaszczyk's theorem (prefix-sum version)Background · 2012

Let $v_1,\dots,v_n\in\R^d$ be vectors of length at most 1, and let $\mathcal K\subset\R^d$ be a convex body symmetric about the origin such that a standard Gaussian random vector lies in $\mathcal K$ with probability at least $1-\frac1{2n}$ $\frac{1}{2 n}$ . Then there are signs $\eps_i\in\{\pm1\}$ such that all prefix sums $\sum_{i\le u}\eps_iv_i$ ( $u=1,\dots,n$ $1, \dots, n$ ) lie in $5\mathcal K$ .

Order the points by height as $p_1,\dots,p_n$ , and let $r_i$ be the rank of $p_i$ in the $x$ -direction. The signed count of an anchored rectangle is $A(u,v)=\sum_{i\le u,\ r_i\le v}\eps_i$ $\sum_{i \leq u, r_{i} \leq v} ϵ_{i}$ .
Take $h=\lceil\log_2n\rceil$ and treat the ranks $1,\dots,2^h$ as columns. Give each point a vector $v_i$ whose coordinates are indexed by the dyadic intervals $I$ : the coordinate is $1/\sqrt{h+1}$ if $r_i\in I$ $I$ , and 0 otherwise. Each point lies in exactly $h+1$ dyadic intervals, so $\norm{v_i}=1$ $1$ .
For each $v$ , let $b_v$ be the indicator vector of the dyadic decomposition of the prefix $[1,v]$ ; it has at most $h+1$ ones. The decomposition is disjoint, so $\ip{b_v}{v_i}=\one_{\{r_i\le v\}}/\sqrt{h+1}$ $1_{{r_{i} \leq v}} / h + 1$ .
Take $\mathcal K=\{y:\ |\ip{b_v}{y}|\le t\ \text{for}\ v=1,\dots,n\}$ $1, \dots, n}$ , a convex set symmetric about the origin (strictly speaking, it is bounded only after restricting to the subspace spanned by these $b_v$ ; this does not affect the argument). For a Gaussian vector $g$ , $\ip{b_v}{g}$ is normally distributed with variance at most $h+1$ $1$ , so $\Pr[|\ip{b_v}{g}|>t]\le2e^{-t^2/(2(h+1))}$ $2 e^{- t^{2} / (2 (h + 1))}$ . A union bound over these $n$ values of $v$ shows that $t=\sqrt{2(h+1)\ln(4n^2)}$ satisfies the hypothesis of the theorem.
The signs given by the theorem satisfy $\bigl|\sum_{i\le u}\eps_i\ip{b_v}{v_i}\bigr|\le5t$ $5 t$ , that is, $|A(u,v)|\le5t\sqrt{h+1}=5(h+1)\sqrt{2\ln(4n^2)}=O(\log^{3/2}n).$

The two factors have clear sources: $h+1\approx\log n$ comes from the number of levels of the dyadic decomposition, and $\sqrt{\log n}$ comes from requiring $n$ constraints to hold simultaneously. The original paper treats general dimension and is written in the language of factorization norms; refer to it for the details.

The story of the upper bound stops here. It leaves an impression: there are $\log n$ levels, and each level costs an extra $\sqrt{\log n}$ . The paper proves that none of this cost can be saved.

§ 6 · IntermediateWhere the lower bound comes from: continuous discrepancy and transference

An older problem: how evenly are the points spread?

Forget colorings and ask only this: when $n$ points are placed in the unit square $[0,1]^2$ , what does it mean for them to be evenly spread? If the points are evenly spread, a rectangle of area $a$ should contain about $an$ points. The continuous discrepancy of a point set $P$ is defined as the worst deviation

D(P)=\sup_{R}\ \Bigl|\,|P\cap R|-n\cdot\mathrm{area}(R)\Bigr|,\qquad D(n)=\min_{|P|=n}D(P),

where $R$ ranges over the axis-parallel rectangles in $[0,1]^2$ . Note that here you place the points yourself, hence the $\min$ .

The grid and the random points both have deviation of order $\sqrt n$ . The third point set is called a binary net; its deviation is only of order $\log n$ . We derive this below, because the derivation again has the structure “ $\log n$ levels, each contributing a constant”.

Binary nets: error at most 1 per level

Let $N=2^s$ $2^{s}$ . Write an integer $i\in\{0,\dots,N-1\}$ with $s$ bits, then read these $s$ bits in reverse order as a binary fraction, denoted $\varphi(i)$ . For example, for $s=3$ and $i=6=(110)_2$ we get $\varphi(6)=(0.011)_2=3/8$ $3/8$ . The point set is

P=\bigl\{\,(i/N,\ \varphi(i))\ :\ i=0,1,\dots,N-1\,\bigr\}.

Net propertyBackground · Hammersley point set

Let $p+q=s$ $s$ . Every box of the form $\bigl[\frac a{2^p},\frac{a+1}{2^p}\bigr)\times\bigl[\frac b{2^q},\frac{b+1}{2^q}\bigr)$ (its area is exactly $1/N$ ) contains exactly one point of $P$ .

ProofThe net property, and

D(P)\le 4(\log_2N+1)

Net property. The number $i/N$ lies in the first interval exactly when the top $p$ bits of $i$ are the binary representation of $a$ . The number $\varphi(i)$ lies in the second interval exactly when the first $q$ fractional bits of $\varphi(i)$ are the binary representation of $b$ , that is, when the lowest $q$ bits of $i$ are determined. Since $p+q=s$ $s$ , all $s$ bits of $i$ are determined, so there is exactly one such $i$ .
Splitting. Consider the anchored rectangle $[0,X)\times[0,Y)$ $[0, Y)$ . By the binary expansion, $[0,X)$ splits into at most $s$ pairwise disjoint dyadic intervals (of distinct lengths $2^{-p}$ , $1\le p\le s$ $s$ ) plus a remainder of length less than $1/N$ . For $X=1$ it is the single interval $[0,1)$ .
One dyadic strip. Let $I$ be a dyadic interval of length $2^{-p}$ . There are $2^{s-p}$ points with horizontal coordinate in $I$ . By the net property (with $q=s-p$ $p$ ), exactly one of them has its vertical coordinate in each $\bigl[\frac b{2^q},\frac{b+1}{2^q}\bigr)$ . So the number of points in $I\times[0,Y)$ is between $\lfloor Y2^q\rfloor$ and $\lceil Y2^q\rceil$ , while the “number it should contain” is $N\cdot2^{-p}\cdot Y=Y2^q$ $Y 2^{q}$ . The error is at most 1.
Remainder. All horizontal coordinates are multiples of $1/N$ , so an interval of length less than $1/N$ contains at most one point, and the number it should contain is less than 1. The error is at most 1.
Total. The deviation of an anchored rectangle is at most $s+1=\log_2N+1$ $1$ . A general rectangle is a signed combination of four anchored rectangles, so $D(P)\le4(\log_2N+1)$ $1)$ .

Arbitrary point counts. For any $n\ge2$ , take $(i/n,\varphi(i))$ for $0\le i<n$ , where $\varphi$ reverses the binary digits of $i$ into a fraction (leading zero digits do not matter). An anchored rectangle selects a prefix of $k$ indices with $|k-nX|\le1$ . Split this prefix into aligned blocks of power-of-two lengths. There are at most $\lfloor\log_2 n\rfloor+1$ blocks; in each block, the reversed digits put one point in every equal dyadic vertical interval, so its counting error is at most 1. Adding these errors and $|k-nX|Y\le1$ gives $O(\log n)$ for every $n$ ; general rectangles cost at most a factor of four.

The other direction is a theorem that Schmidt proved in 1972: however the points are placed, $D(n)\ge c\log n$ $c lo g n$ . We do not go into its proof here. Together, the two results determine continuous discrepancy completely:

D(n)=\Theta(\log n).

The version with anchored rectangles only is $\sup_{x,y}\bigl|\,|P\cap([0,x]\times[0,y])|-nxy\,\bigr|$ $n x y$ ; its minimum is also $\Theta(\log n)$ . Dividing it by $n$ gives what is usually called the star discrepancy, whose optimal order is $(\log n)/n$ .

Transference: good colorings produce evenly spread point sets

There is a bridge between continuous discrepancy and combinatorial discrepancy, called the transference principle. Its proof is elementary and rather neat: color repeatedly and keep only the red points.

Transference principle (simplified form)Background · simplified standard argument; constants from this guide

For all $n\ge2$ $2$ , we have $D(n)\le2\,\Delta_2(2n^2)+5$ $5$ . In other words, if every point set can be colored in a well-balanced way, then there must be a very evenly spread point set.

The old deviation is halved at each step; the new deviation is the discrepancy of that step's coloring.

ProofThe transference principle

Halving. Let $P$ have $N$ points ( $N$ even), and let $\chi$ be a coloring with $|\chi(P\cap R)|\le f$ for all rectangles. Let $P^+$ be the set of red points. For every rectangle $R$ , the number of red points is $|P^+\cap R|=\frac12\bigl(|P\cap R|+\chi(P\cap R)\bigr)$ $R))$ , so $\Bigl|\,|P^+\cap R|-\tfrac12|P\cap R|\,\Bigr|\le\tfrac f2.$ Taking $R$ to be the whole square gives $\bigl||P^+|-\frac N2\bigr|\le\frac f2$ $\frac{f}{2}$ .
Fixing the number of points. The set $P^+$ may not have exactly $N/2$ points, but it is off by at most $f/2$ . Delete or add that many points to get a set $P'$ with exactly $N/2$ points. Each point deleted or added changes the number of points in any rectangle by at most 1, so $\bigl||P'\cap R|-\frac12|P\cap R|\bigr|\le f$ $f$ .
Recursion for continuous discrepancy. By the triangle inequality, $\begin{aligned}\Bigl|\,|P'\cap R|-\tfrac N2\,\mathrm{area}(R)\Bigr|&\le\Bigl|\,|P'\cap R|-\tfrac12|P\cap R|\,\Bigr|+\tfrac12\Bigl|\,|P\cap R|-N\,\mathrm{area}(R)\Bigr|\\&\le f+\tfrac12D(P).\end{aligned}$ Taking the supremum over $R$ gives $D(P')\le\frac12D(P)+f$ $f$ .
$\Delta_2$ is nondecreasing in the number of points. Add one more point far away from a point set. Every original rectangle can be shrunk slightly to avoid the new point, so the discrepancy does not decrease.
Iteration. Take $k=\lceil\log_2n\rceil$ $⌈ lo g_{2} n ⌉$ , start from a set $P_0$ of $N_0=2^kn$ points, and halve $k$ times; $P_j$ has $2^{k-j}n$ points. Since $2^k<2n$ $2 n$ , every $P_j$ has fewer than $2n^2$ points, so at every step there is a coloring with discrepancy at most $f=\Delta_2(2n^2)$ $Δ_{2} (2 n^{2})$ . Unrolling the recursion, $D(P_k)\le\frac{D(P_0)}{2^k}+f\cdot\Bigl(1+\frac12+\frac14+\dots\Bigr)\le\frac{D(P_0)}{2^k}+2\,\Delta_2(2n^2).$
Starting point. Let $P_0$ be a $\lceil\sqrt{N_0}\rceil\times\lceil\sqrt{N_0}\rceil$ grid with the surplus points removed. Counting grid points directly gives $D(P_0)\le5\sqrt{N_0}$ $5 N_{0}$ . Hence $D(P_0)/2^k\le5\sqrt{n/2^k}\le5$ $5$ , because $2^k\ge n$ $n$ .
Conclusion. The set $P_k$ has exactly $n$ points, so $D(n)\le D(P_k)\le2\,\Delta_2(2n^2)+5$ $5$ .

Combining this with Schmidt's theorem $D(n)\ge c\log n$ gives $\Delta_2(2n^2)\ge\frac12(c\log n-5)$ $5)$ . Using monotonicity once more, we get $\Delta_2(N)=\Omega(\log N)$ for all $N$ . This is where the classical lower bound comes from.

Ceiling

The logic of this route is “combinatorial discrepancy cannot be smaller than continuous discrepancy”. But continuous discrepancy is exactly $\Theta(\log n)$ , and the binary net already achieves it. So this route by itself cannot prove a lower bound larger than $\log n$ .

Transference goes in one direction only: good colorings produce evenly spread point sets, but the existence of evenly spread point sets does not guarantee good colorings. The paper's result shows that the two really are different: in the plane, combinatorial discrepancy is larger than continuous discrepancy by a factor of $\sqrt{\log n}$ .

§ 7 · IntermediateOther lower-bound tools, and where they stop

Besides transference, two other kinds of methods have given $\Omega(\log n)$ . Their ideas are similar: for every coloring, the same procedure produces evidence that “a bad rectangle exists”.

The orthogonal-function method

This method was introduced by Roth in 1954. Write the deviation as a function $D(x,y)$ on the square, and find a test function $F$ such that the inner product $\ip{D}{F}=\iint DF$ is large while $F$ itself is not large. By the Cauchy–Schwarz inequality, the mean square of $D$ then cannot be small. The test function is assembled from Haar functions: each dyadic box carries a small wavelet with values $\pm1$ , and boxes of different shapes give mutually orthogonal functions.

OptionalRoth's theorem in full:

D(N)\ge\frac1{128}\sqrt{\log_2N}

Let $P\subset[0,1)^2$ have $N$ points, and let $D(x,y)=\#\bigl(P\cap[0,x)\times[0,y)\bigr)-Nxy$ $N x y$ .

Scale. Choose an integer $n$ with $2N\le2^n<4N$ $4 N$ . For each $r=(r_1,r_2)$ with $r_1+r_2=n$ $n$ , cut the square into $2^n$ dyadic boxes of size $2^{-r_1}\times2^{-r_2}$ $2^{- r_{2}}$ , each of area $2^{-n}$ . There are $n+1$ such $r$ .
Haar functions. For an interval $I$ , let $h_I$ be $+1$ on the left half, $-1$ on the right half, and 0 outside the interval. For a box $R=I\times J$ $J$ , let $h_R(x,y)=h_I(x)h_J(y)$ $h_{I} (x) h_{J} (y)$ .
Inner product on an empty box. Integrating directly, $\int_I x\,h_I(x)\,dx=-|I|^2/4$ $- ∣ I ∣^{2} /4$ , so $\iint Nxy\,h_R=N|R|^2/16$ $N ∣ R ∣^{2} /16$ . On the other hand, if $R$ contains no point of $P$ , then for each point $p$ the counting function $\one_{\{p_x<x\}}\one_{\{p_y<y\}}$ is constant on $R$ in at least one of the two variables, and $h_I$ and $h_J$ both have integral 0, so the counting part has inner product 0 with $h_R$ . Hence an empty box satisfies $\ip{D}{h_R}=-N|R|^2/16$ $- N ∣ R ∣^{2} /16$ .
Test function for one level. Let $f_r=-\sum h_R$ $- \sum h_{R}$ , summed over all empty boxes of type $r$ . Since $N\le2^{n-1}$ $2^{n - 1}$ , there are at least $2^{n-1}$ empty boxes, so $\ip{D}{f_r}\ge2^{n-1}\cdot\frac{N\,4^{-n}}{16}=\frac{N2^{-n}}{32}>\frac1{128},\qquad\norm{f_r}^2\le2^n\cdot2^{-n}=1.$
Orthogonality. If $r\ne r'$ $r^{'}$ , we may assume $r_1<r_1'$ $r_{1}^{'}$ . A box of type $r'$ is narrower in the $x$ -direction: its $x$ -interval is either disjoint from $I$ or contained in one half of $I$ , and then $h_I$ is constant on it, so the integral is 0. Hence $\ip{f_r}{f_{r'}}=0$ $0$ .
Putting it together. Let $F=\sum_rf_r$ $\sum_{r} f_{r}$ . Then $\ip{D}{F}>\frac{n+1}{128}$ and $\norm{F}^2=\sum_r\norm{f_r}^2\le n+1$ $1$ . By Cauchy–Schwarz, $\sup|D|\ \ge\ \norm{D}_2\ \ge\ \frac{\ip{D}{F}}{\norm{F}}>\frac{\sqrt{n+1}}{128}\ge\frac{\sqrt{\log_2N}}{128}.$

Each level $r$ contributes a constant, and there are $n+1\approx\log N$ levels. In the mean-square sense these contributions combine as “the square root of the sum of squares”, which gives $\sqrt{\log N}$ . Schmidt's 1972 theorem raised this to $\log N$ . Later, Halász reproved this result within Roth's framework with a more delicate test function, which makes the contributions of the levels add up directly.

Applying the same idea to colorings, Wei and Yi proved that the combinatorial discrepancy of binary nets is $\Omega(\log n)$ . In proofs of this kind the gain accumulates scale by scale: there are $\log n$ levels, and each contributes a constant.

For the binary net of Section 6 this is already the limit of what can be proved, because that net really can be colored this well. The verification below is supplied by this guide and is not in the paper; it uses only the tools of Section 6.

DerivationThe binary net of Section 6 can be colored with discrepancy

4(\log_2N+1)

Coloring. The $i$ -th point $(i/N,\varphi(i))$ gets the color $(-1)^{b(i)}$ , where $b(i)$ is the number of ones in the binary expansion of $i$ .
Colors in one dyadic strip. Let $I$ be a dyadic interval of length $2^{-p}$ , and let $q=s-p$ $p$ . The points with horizontal coordinate in $I$ are $i=a\cdot2^q+j$ $j$ , $j=0,\dots,2^q-1$ $1$ . Sorting them by vertical coordinate is the same as sorting them by $r$ , the $q$ -bit reversal of $j$ . Reversal does not change the number of ones, so the point in position $r$ has color $\pm(-1)^{b(r)}$ , with the same sign for the whole strip.
Prefix sums are at most 1 in absolute value. The sequence $(-1)^{b(r)}$ , $r=0,1,2,\dots$ $0, 1, 2, \dots$ , is $+,-,-,+,-,+,+,-,\dots$ . Since $b(2r+1)=b(2r)+1$ $1$ , its terms come in pairs, and each pair is $(+,-)$ or $(-,+)$ . Every prefix sum is therefore $-1$ , $0$ or $1$ .
Total. The points in the strip $I\times[0,Y)$ form a prefix of this order, so their signed count has absolute value at most 1. As in Section 6, split an anchored rectangle into at most $s$ strips plus a remainder; its signed count then has absolute value at most $s+1$ $1$ . For a general rectangle, multiply by 4.

So as long as a proof is aimed at point sets of this kind, its conclusion cannot exceed $\log n$ . To get past this, a different kind of point set is needed.

The factorization norm $\gamma_2$

The second kind of method comes from linear algebra. Record “which point lies in which rectangle” as a 0–1 matrix $A$ . Factor $A$ as a product of two matrices, $A=BC$ $BC$ , and define

\gamma_2(A)=\min_{A=BC}\ \bigl(\text{length of the longest row of}\ B\bigr)\times\bigl(\text{length of the longest column of}\ C\bigr).

Matoušek, Nikolov and Talwar proved that this quantity bounds the discrepancy from both sides (more precisely, the “hereditary discrepancy”: the worst discrepancy over all subsets of the point set; Tusnády's problem can be reduced to this quantity on a grid):

\frac{\gamma_2(A)}{C\log M}\le\operatorname{herdisc}(A)\le C\sqrt{\log M}\,\gamma_2(A).

Here $M$ is the number of rows and $C$ is a constant. The dyadic decomposition in Section 5 gives a factorization of the one-dimensional prefix matrix: the maximum row norm and column norm are each at most $\sqrt{h+1}$ , so their product is at most $h+1$ . For anchored boxes on a full equal-sided $d$ -dimensional product grid with $n$ points, $\gamma_2=\Theta_d(\log^d n)$ . The lower bound below uses hereditary discrepancy to select a subset of that grid; it does not assert this value for every point set. For an arbitrary $n$ -point set, embedding coordinate ranks in a grid gives the needed upper bound on $\gamma_2$ . Thus, for fixed $d$ , the general inequalities give

\Omega(\log^{d-1}n)\ \le\ \Delta_d(n)\ \le\ O(\log^{d+1/2}n).

Ceiling

Each of the two inequalities loses a logarithmic factor, and it is known that neither loss can be improved for general matrices. On the planar product grid $\gamma_2\approx\log^2n$ $lo g^{2} n$ , and dividing by $\log n$ on the lower-bound side gives exactly $\log n$ once again. The true value $\log^{3/2}n$ lies strictly between the two bounds; this general-purpose ruler cannot measure it.

Summary: three methods, the same number

Method	Lower bound obtained	Why it stops there
Continuous discrepancy + transference	$\Omega(\log n)$	Continuous discrepancy itself is $\Theta(\log n)$
Orthogonal-function method	$\Omega(\log n)$	The known arguments gain only a constant per level; the binary net of Section 6 itself can be colored with discrepancy $O(\log n)$
Factorization norm $\gamma_2$	$\Omega(\log^{d-1}n)$ , which is $\log n$ in the plane	The general inequalities come with a logarithmic loss
The paper: random point sets, a probability estimate for each coloring	$\Omega(\log^{3/2}n)$	Matches the upper bound

The specific arguments reviewed here have two features. First, they do not give the paper's uniform lower bound for random point sets: transference and factorization norms produce bad point sets among the subsets of a grid, while the combinatorial-discrepancy application of the orthogonal-function method presented above concerns binary nets. The method itself is not restricted to such point sets. Second, the arguments presented here that count their gain scale by scale gain a constant per level, for a total of $\log n$ over $\log n$ levels. The paper changes both: the points are random, and each scale gains an amount of order $\sqrt{\log n}$ . The skeleton of the proof is still a gain collected level by level, and in this it descends directly from the orthogonal-function method. What differs is how much each level gains, and how to make the bound hold for all $2^n$ colorings simultaneously.

Part III · Sections 8–10

A different question

Instead of constructing a bad point set, we place the points at random and then prove that any given coloring is extremely unlikely to be good. This part explains this change of viewpoint, what it demands of the probability estimates, and a small tool that is used from here on: revealing a random number one digit at a time.

§ 8 · BasicsRandom points, one coloring at a time

Section 3 stressed that a lower bound has to rule out all $2^n$ colorings. The classical arguments described above do not give the paper’s lower bound for random point sets, simultaneously for all colorings. The paper sets things up differently:

PointsNo construction. Place

n

points

P_1,\dots,P_n

independently and uniformly at random in the unit square

[0,1]^2

, and write

P_i=(U_i,V_i)

(U_{i}, V_{i})

ColoringGive the

i

-th point a color

\chi_i\in\{+1,-1\}

{+ 1, - 1}

. A coloring is a vector

\chi=(\chi_1,\dots,\chi_n)

(χ_{1}, \dots, χ_{n})

, and there are

2^n

of them. Colors are assigned by the index of the point, and they are fixed before the points are placed.

GoalFor each fixed

\chi

, prove that the probability of “this coloring is well balanced on every anchored rectangle” is extraordinarily small.

Write the signed count of the points in the anchored rectangle $[0,x]\times[0,y]$ as a function of two variables:

F_\chi(x,y)=\sum_{i=1}^n\chi_i\,\one_{\{U_i\le x,\ V_i\le y\}}.

Here $\one_{\{\cdots\}}$ is the indicator function: it equals 1 if the condition holds and 0 otherwise. We also write $\norm{F_\chi}_\infty=\max_{0\le x,y\le1}\abs{F_\chi(x,y)}$ $max_{0 \leq x, y \leq 1} ∣ F_{χ} (x, y)∣$ ; this is the largest imbalance of this coloring over the anchored rectangles. The main theorem of the paper is the following statement.

Theorem 1.1 (Random points)Theorem 1.1 of the paper

For every $A>0$ $0$ , there is a constant $c_A>0$ such that the following holds for every integer $n\ge1$ $1$ . If $P_1,\dots,P_n$ are independent uniform points in $[0,1]^2$ , then

\Pr\Bigl[\ \text{for every}\ \chi\in\{\pm1\}^n,\ \norm{F_\chi}_\infty\ge c_A(\log_2n)^{3/2}\ \Bigr]\ \ge\ 1-e^{-An}.

The event in the brackets is a statement about the point set, not about any one coloring: however these points are colored, some anchored rectangle has imbalance at least $c_A(\log_2n)^{3/2}$ . So the coloring may well be chosen after seeing all the points. The coloring you choose is still one of the $2^n$ vectors, and the conclusion holds for it too.

Three things follow at once from this theorem.

Bad point sets exist. An event of positive probability is not empty, and random points are almost surely distinct (that is, distinct with probability 1). So there is at least one $n$ -point set for which every coloring leaves an anchored rectangle with imbalance at least $c_A(\log_2n)^{3/2}$ . Anchored rectangles are rectangles, so $\Delta_2(n)\ge c\log^{3/2}n$ $c lo g^{3/2} n$ . Together with Nikolov's upper bound, $\Delta_2(n)=\Theta(\log^{3/2}n)$ $Θ (lo g^{3/2} n)$ .
Random point sets are as bad as possible. No clever construction is needed: points placed at random attain the worst-case order with probability extremely close to 1.
$A$ can be arbitrarily large. Even a failure probability of $e^{-100n}$ is possible; the constant $c_A$ just becomes smaller. The paper does not optimize $c_A$ . It is very small, so the bound is of interest only for large $n$ ; the end of Section 18 gives the actual numbers.

The two steps of the proof

Write $t=c_A(\log_2n)^{3/2}$ $c_{A} (lo g_{2} n)^{3/2}$ . The proof has two steps, and the first one is the main body of the whole paper.

Fixed coloringFor each fixed

\chi

, prove that

\Pr\bigl[\norm{F_\chi}_\infty\le t\bigr]\le e^{-(A+\ln2)n}

e^{- (A + l n 2) n}

Union bound“Some coloring

\chi

is good” is a union of

2^n

events, so its probability is at most

2^n\cdot e^{-(A+\ln2)n}=e^{-An}

e^{- A n}

The second step uses only the union bound of Section 5, and it needs no independence whatsoever among these $2^n$ events. But it makes a strong demand on the first step: for every coloring, the probability that it is “good” must be smaller than $2^{-n}$ . If we could only prove $0.9^n$ , multiplying by $2^n$ would give $1.8^n$ , which says nothing. In other words, each additional point must, on average, more than halve the probability that the coloring is good.

The proof in Part IV is slightly more refined than these two steps. The event “the coloring is good” is split into two events. One depends only on the positions of the points; it is the same event for every coloring, so it has to be ruled out only once. Only the other one has to be estimated coloring by coloring and then multiplied by $2^n$ . But the demand is unchanged: for the part that is estimated coloring by coloring, the probability must be far below $2^{-n}$ .

	Random coloring of Section 5 (upper bound)	Here (lower bound)
What is random	the coloring	the positions of the points
What is fixed	the point set, and one rectangle	one coloring
What the union bound runs over	at most $n^4$ rectangles	$2^n$ colorings
How small each probability must be	$n^{-5}$ is enough	must be below $2^{-n}$
Conclusion	a good coloring exists	with very high probability, there is no good coloring

Once $\chi$ is fixed, all the randomness is in the positions of the points: each point carries its preassigned color and lands, independently, at a uniform position in the square. Moreover, the horizontal coordinate $U_i$ and the vertical coordinate $V_i$ of the same point are independent. Section 10 uses this: it treats all vertical coordinates as known and lets only the horizontal coordinates be random.

§ 9 · IntermediateWhat to aim for: guessing the exponent $\frac32$

Before starting the proof, let us estimate how large $t$ can be. This section is a heuristic calculation. It corresponds to the first half of the paragraph “The Brownian sheet and Talagrand's proof” in Section 3 of the paper. It is not part of the proof, but it explains where the exponent $\frac32$ comes from.

Fix $\chi$ and write $S=\sum_i\chi_i$ $\sum_{i} χ_{i}$ . Then $F_\chi(x,y)$ is a sum of $n$ independent terms, each of which contributes $\pm1$ with probability $xy$ and 0 otherwise. Its mean is $S\,xy$ , and its fluctuations around the mean are of order $\sqrt n$ . Subtract the mean and divide by $\sqrt n$ : the resulting process has covariance $\min(x,x')\min(y,y')-xy\,x'y'$ $x y x^{'} y^{'}$ . Probability theory has a random surface that is very similar, the Brownian sheet, written $W(x,y)$ . It is the two-dimensional version of Brownian motion: $W(x,y)$ is normally distributed with mean 0 and variance $xy$ , its covariance is $\min(x,x')\min(y,y')$ , and its increments over disjoint rectangles are independent. The extra term $xy\,x'y'$ corresponds to pinning the sheet at the upper right corner, that is, to $W(x,y)-xy\,W(1,1)$ $x y W (1, 1)$ . Below we borrow the Brownian sheet only to guess the scale; we do not distinguish the two processes, and we ignore the mean.

Small-ball estimateBackground · Bass 1988, Talagrand 1994

The probability that the Brownian sheet stays in $[-\varepsilon,\varepsilon]$ on the whole square satisfies

-\log\Pr\bigl[\norm{W}_\infty\le\varepsilon\bigr]\ \asymp\ \varepsilon^{-2}\log^3(1/\varepsilon)\qquad(\varepsilon\to0),

where $\asymp$ means that the two sides agree up to constant factors. The upper bound on the left-hand side is due to Bass, and the matching lower bound is due to Talagrand. We will also use $\gtrsim$ and $\lesssim$ : “at least” and “at most” up to constant factors.

The one-dimensional analogue is easier to understand. The probability that Brownian motion $B(s)$ stays in $[-\varepsilon,\varepsilon]$ throughout $[0,1]$ is about $e^{-c/\varepsilon^2}$ . The reason is this. Cut time into pieces of length $\varepsilon^2$ . In each piece it gets beyond $\pm\varepsilon$ with constant probability, and it has to stay inside for $1/\varepsilon^2$ pieces in a row. The extra $\log^3(1/\varepsilon)$ in two dimensions has no such simple explanation; it is exactly the content of Talagrand's theorem.

Now substitute this into the demand of Section 8. The event “ $\norm{F_\chi}_\infty\le t$ $t$ ” corresponds to “ $\norm{W}_\infty\le\varepsilon$ $ε$ ” with $\varepsilon=t/\sqrt n$ $t / n$ . This suggests the guess

\Pr\bigl[\norm{F_\chi}_\infty\le t\bigr]\ \approx\ \exp\Bigl(-c\,\frac{n}{t^2}\,\log^3\frac{\sqrt n}{t}\Bigr).

For this to be smaller than $2^{-n}$ , the exponent must be at least of order $n$ :

\frac{n}{t^2}\,\log^3\frac{\sqrt n}{t}\ \gtrsim\ n\qquad\Longleftrightarrow\qquad t\ \lesssim\ \log^{3/2}\frac{\sqrt n}{t}.

When $t$ is only a power of $\log n$ , we have $\log\frac{\sqrt n}t\approx\frac12\log n$ $\frac{1}{2} lo g n$ . So the threshold is exactly at $t\asymp\log^{3/2}n$ $lo g^{3/2} n$ : for smaller $t$ the union bound suffices, and for larger ones it does not. The $\frac32$ is half of 3: the cube of the logarithm in the small-ball estimate turns into the power $\frac32$ when the square root is taken.

Problem	Random process	Small-ball exponent	Resulting $t$	True answer
intervals on the line	Brownian motion	$\varepsilon^{-2}$	a constant	1 (Section 2)
rectangles in the plane	Brownian sheet	$\varepsilon^{-2}\log^3(1/\varepsilon)$	$\log^{3/2}n$	$\Theta(\log^{3/2}n)$ (the paper)

The first row is a sanity check: in one dimension the exponent has no logarithm, and solving for $t$ gives a constant. This agrees with Section 2: “color alternately, and the largest imbalance is always 1”.

This is only a guess

“Looks like a Brownian sheet” is a statement about a limit in distribution, which describes typical fluctuations. The probabilities to be estimated here are as small as $e^{-n}$ , and weak convergence by itself does not control exponentially small probabilities. As the paper puts it, the calculation predicts only the scale: $F_\chi$ is not a Gaussian process, and a Gaussian limit cannot control probabilities that small. So Part IV has to give a proof directly for finitely many points.

Also, the analogy leaves out two things: the limit process is pinned at the upper right corner, and when the colors are unbalanced $F_\chi$ has the mean $S\,xy$ ; if every point is red, $F_\chi(1,1)=n$ $n$ , which is not of order $\sqrt n$ at all. They can be set aside when guessing the scale, but not in a proof.

The proof in Part IV does not use Gaussian distributions at all. But the relation between the parameters that it ends up with is exactly the one in the calculation above; Section 19 comes back to compare the two.

§ 10 · IntermediateRevealing digit by digit: a random number as a sequence of dice

The randomness in the proof is released a little at a time. First we look at how to take one random number apart. Take an integer $b\ge2$ as the base. Cut $[0,1]$ into $b$ equal pieces; the index of the piece that contains $U$ is its first digit $d_1\in\{1,\dots,b\}$ ${1, \dots, b}$ . Then cut that piece into $b$ equal smaller pieces; the index of the one that contains $U$ is $d_2$ . Continue in this way. This is the base- $b$ expansion of $U$ , except that the digits are counted from 1, so that they match “the $r$ -th child” later on.

Each row takes the highlighted piece of the row above, magnifies it to full width, and cuts it into four equal pieces again.

Tool · The digits of a uniform random number

If $U$ is uniformly distributed on $[0,1]$ , then its digits $d_1,d_2,\dots$ are independent, and each of them is uniformly distributed on $\{1,\dots,b\}$ .

Proof: “the first $j$ digits are $r_1,\dots,r_j$ , in this order” is equivalent to “ $U$ lies in one particular interval of length $b^{-j}$ ”, which has probability $b^{-j}=\frac1b\cdot\frac1b\cdots\frac1b$ $\frac{1}{b} \dots \frac{1}{b}$ . The joint probability is the product of the individual probabilities, and this is exactly the definition of being independent and uniform.

So a uniform random number can be viewed as a sequence of independent $b$ -sided dice. After the first $j$ dice have been rolled, we know only which interval of length $b^{-j}$ contains $U$ . The next die decides which child of this interval the number falls into, and it is independent of the earlier rolls.

Information and conditional expectation

The proof proceeds in stages, numbered from 0 to $h$ (here $h$ is the number of transitions; it is fixed in Section 11). Let $\mathcal F_j$ be the information at stage $j$ : the vertical coordinates $V_1,\dots,V_n$ of all $n$ points, together with the first $j$ digits of every horizontal coordinate $U_i$ . So $\mathcal F_0$ contains only the vertical coordinates. Each further stage reveals one more digit of every point.

The points are independent, and $U_i$ is independent of $V_i$ . So, conditional on $\mathcal F_j$ , the next digits of the $n$ points are $n$ independent uniform $b$ -sided dice. This is all the randomness that is added between stage $j$ and stage $j+1$ $1$ .

Tool · Conditional expectation

$\EE[X\mid\mathcal F_j]$ means: treat the information as constant, and average only over the digits that have not been revealed yet. The result is a quantity determined by the information. We will use four of its properties.

Linearity. $\EE[X+Y\mid\mathcal F_j]=\EE[X\mid\mathcal F_j]+\EE[Y\mid\mathcal F_j]$ $F_{j}]$ ; no independence is needed.

Known quantities can be taken out. If $Y$ is determined by $\mathcal F_j$ , then $\EE[YX\mid\mathcal F_j]=Y\cdot\EE[X\mid\mathcal F_j]$ $F_{j}]$ . In the average, $Y$ is a constant.

Tower property. Averaging first over the digits revealed later and then over those revealed earlier is the same as averaging over all of them at once: $\EE\bigl[\EE[X\mid\mathcal F_{j+1}]\bigm|\mathcal F_j\bigr]=\EE[X\mid\mathcal F_j]$ $F_{j}]$ , and in particular $\EE\bigl[\EE[X\mid\mathcal F_j]\bigr]=\EE[X]$ $E [X]$ .

Absolute value. $\bigl|\EE[X\mid\mathcal F_j]\bigr|\le\EE\bigl[\,|X|\bigm|\mathcal F_j\bigr]$ $F_{j}]$ . The absolute value of an average is at most the average of the absolute values; this is the triangle inequality.

If there are only finitely many possible outcomes, a conditional expectation is just a weighted average, and all four properties can be checked directly. That is the situation here: each step involves only $n$ dice, with $b^n$ outcomes in total, each of probability $b^{-n}$ . Only at one place, in Section 13, do we have to average over a continuous position; it is explained there.

Part IV · Sections 11–18

Local oscillation

This part is the proof itself, following version r65 of the paper. Its central object is a quantity $Z_j$ that measures local oscillation. The proof rests on three things. In one transition, $Z$ increases on average by a definite amount (Lemmas 2.1, 2.3, 2.4 and Fact 2.2). When the points are spread out, this amount is large enough, and the points are almost always spread out (Lemma 2.5). The actual increase is unlikely to fall far below the average (Lemma 2.6). Proposition 2.7 combines these and takes a union bound over all colorings.

The route is as follows. We first cut the square into cells, stage by stage, and define $Z_j$ (Sections 11 and 12). Inside one rectangle we prove that the refinement does not decrease the expected oscillation and in fact adds an extra term (Sections 13 and 14), and that one digit has very little effect on $Z$ (Section 15). Then we chain the $h$ transitions together (Section 16), show that all transitions are good with high probability when $M\le n$ (Section 17), and finish by choosing the parameters (Section 18). The equation numbers (1)–(18), Lemmas 2.1 and 2.3–2.6, Fact 2.2, Proposition 2.7 and Fact A.1 of the appendix all agree with the paper. In a few places the order of presentation differs from the paper for the sake of the explanation; this is noted where it happens.

§ 11 · Basics $h+1$ stages, a family of rectangles of equal area

From here to Section 17 the coloring $\chi$ is fixed, and we write $F$ for $F_\chi$ . Almost surely, all points have distinct vertical coordinates, and no coordinate of a point has the form $k/b^r$ with integers $k$ and $r\ge0$ $0$ . We work on this event only. All intervals below have endpoints of the form $k/b^r$ , so no point lies on a dividing line.

We use three parameters:

the base $b\ge3$ $3$ , an integer;
the number of transitions $h\ge1$ $1$ , an integer;
$M=b^{h-1}$ $b^{h - 1}$ .

Their values are chosen only in Section 18: $b$ is a large constant that depends only on $A$ , and $h$ is about $\log n$ divided by $\log b$ .

Stages. For $j=0,1,\dots,h$ $0, 1, \dots, h$ , stage $j$ cuts the square as follows:

Horizontally, into $b^j$ intervals $I$ of length $b^{-j}$ . Two horizontal coordinates lie in the same interval exactly when their first $j$ digits agree.
Vertically, into $b^{h-j}$ blocks $B$ of height $b^{j-h}$ . Blocks are closed at the bottom and open at the top.

The rectangles $I\times B$ are the cells of stage $j$ . There are $b^j\cdot b^{h-j}=b^h=bM$ of them, each of area $b^{-j}\cdot b^{j-h}=b^{-h}$ $b^{- h}$ . Neither the number nor the area depends on $j$ ; only the shape changes. Stage 0 consists of $b^h$ thin horizontal strips, and stage $h$ of $b^h$ thin vertical strips.

There are $h+1$ stages, $j=0,1,\dots,h$ $0, 1, \dots, h$ . The passage from stage $j$ to stage $j+1$ is called the transition $j\to j+1$ . Here $j=0,\dots,h-1$ $1$ , so there are $h$ transitions.

In one transition, two things happen at once:

Every interval $I$ is cut into $b$ children $C_1,\dots,C_b$ , numbered from left to right. The next digit of a point decides which child it falls into.
Every $b$ adjacent old blocks $B_1,\dots,B_b$ (from bottom to top) merge into one new block $J$ .

One transition takes place inside a rectangle

R=I\times J

(compare Figure 2 and the left panel of Figure 3 in the paper). The

b

old cells

I\times B_\ell

on the left and the

b

new cells

C_k\times J

on the right cover the same region.

Such an $R=I\times J$ is called a comparison rectangle: $I$ is an interval of stage $j$ , and $J$ is a block of stage $j+1$ $1$ . There are $b^j\cdot b^{h-j-1}=M$ comparison rectangles, each of area $\frac1M$ . So

\frac nM=\text{average number of points of a comparison rectangle}.

This ratio will come up again and again. Section 18 will show that it should be of order $h$ .

A family of rectangles of the same area and of different shapes is nothing new: Roth's method in Section 7 uses dyadic boxes of fixed area. What is new is that we will measure a different quantity on this family.

§ 12 · IntermediateEndpoint average and oscillation

Endpoint average

For a horizontal interval $I=[s,t]$ $[s, t]$ , take the mean of the two values of $F$ at its endpoints:

a_I(y)=\frac{F(s,y)+F(t,y)}2.\tag{2}

The paper writes $I^-$ , $I^+$ for the endpoints and $a^{(I)}$ for this function, shortened to $a$ while $I$ is fixed. Equation (1) is the definition of $Z_j$ below; the paper states it already in the introduction.

It is a function of $y$ , called the endpoint average of $I$ . Let us see how much each point counts in it. Among the points whose vertical coordinate is at most $y$ , $F(s,y)$ counts those to the left of $I$ , each with its color, and $F(t,y)$ counts these points and also those in $I$ . So:

The weight of a point in

a_I

depends only on whether the point lies to the left of

I

, in

I

, or to the right of

I

a_I(y)=\sum_{i=1}^n\chi_i\,w_I(U_i)\,\one_{\{V_i\le y\}},\qquad w_I(u)=\begin{cases}1,&u\ \text{to the left of}\ I,\\[2pt]\tfrac12,&u\ \text{in}\ I,\\[2pt]0,&u\ \text{to the right of}\ I.\end{cases}

So $a_I(y)$ is a step function: each time $y$ moves up past a point, it jumps by $\chi_iw_I(U_i)$ , that is, by $\pm1$ , by $\pm\frac12$ , or not at all. The $\frac12$ may look odd; Sections 13 and 14 will show that the whole proof turns on it. The factor $w_I(U_i)$ is called the weight of the point in $I$ .

Example

Take $b=4$ and $h=1$ $1$ . Consider the interval $I=[\frac14,\frac12]$ and three points: a red point to the left of $I$ , at height 0.3; and, in $I$ , a blue point at height 0.55 and a red point at height 0.8. Their weights are $1$ , $\frac12$ , $\frac12$ , in this order. Let $y$ move from the bottom to the top:

a_I(y)=\begin{cases}0,&y<0.3,\\1,&0.3\le y<0.55,\\1-\frac12=\frac12,&0.55\le y<0.8,\\\frac12+\frac12=1,&y\ge0.8.\end{cases}

Below 0.3 there is no point. Passing the red point on the left adds 1; passing the blue point subtracts $\frac12$ ; passing the last red point adds $\frac12$ .

Take $b=4$ and 12 points. The left panel overlays the two anchored rectangles $[0,s]\times[0,y]$ and $[0,t]\times[0,y]$ $[0, y]$ : the strip to the left of $I$ is covered twice and the inside of $I$ only once, which gives the weights 1 and $\frac12$ . The right panel plots $a_I$ as a function of the height, with the height axis aligned with the left panel. Drag the height $y$ and watch how far the right panel jumps each time the dashed line passes a point.

A few things are worth trying. Set the stage to 0. Then $I=[0,1]$ $[0, 1]$ , the rectangle of the left endpoint is empty, $a_I(y)=\frac12F(1,y)$ $\frac{1}{2} F (1, y)$ , and every point has weight $\frac12$ . Move the interval all the way to the right: almost every point has weight 1, and $a_I$ is close to $F(1,y)$ itself. Flip the color of a point in $I$ : the part of $a_I$ above this point shifts by 1. Flip a point to the left of $I$ : it shifts by 2. Flip a point to the right: nothing changes.

Oscillation

The function $a_I(y)$ is a step function with finitely many jumps, so it has a maximum and a minimum on every block. For a function $f$ of the height and a vertical interval $B$ , define

\operatorname{osc}_B\,f=\max_Bf-\min_Bf,\qquad\operatorname{mid}_B\,f=\frac{\max_Bf+\min_Bf}2,\tag{3}

called the oscillation and the midpoint of $f$ on $B$ . The oscillation measures how wide the range of values of $f$ on $B$ is, and the midpoint measures where this range lies. The maximum and the minimum are $\operatorname{mid}_B\,f\pm\frac12\operatorname{osc}_B\,f$ $\frac{1}{2} osc_{B} f$ . Vertical intervals are closed at the bottom and open at the top.

Tool · Three properties of the oscillation

Shift invariance. Adding a constant $c$ on the whole block moves the maximum and the minimum together, so the oscillation does not change; the midpoint increases by $c$ .

Triangle inequality. $\operatorname{osc}_B(f+g)\le\operatorname{osc}_B\,f+\operatorname{osc}_B\,g$ $osc_{B} g$ . Reason: $\max(f+g)\le\max f+\max g$ and $\min(f+g)\ge\min f+\min g$ $min g$ ; subtract the second from the first. Applied repeatedly, it extends to finite sums. Also, multiplying by a constant $c$ multiplies the oscillation by $|c|$ : $\operatorname{osc}_B(cf)=|c|\operatorname{osc}_B\,f$ $∣ c ∣ osc_{B} f$ .

Reverse triangle inequality. $\bigl|\operatorname{osc}_B(f+g)-\operatorname{osc}_B\,f\bigr|\le\operatorname{osc}_B\,g$ $osc_{B} g$ . Reason: write $f$ as $(f+g)+(-g)$ $(- g)$ ; the triangle inequality and $\operatorname{osc}_B(-g)=\operatorname{osc}_B\,g$ then give $\operatorname{osc}_B\,f\le\operatorname{osc}_B(f+g)+\operatorname{osc}_B\,g$ $osc_{B} g$ . The other direction is the triangle inequality itself.

The first property is the reason for choosing the oscillation: when a point whose height is not in $B$ is moved, the function on $B$ only changes by an additive constant. The second property is used in Section 13, and the third in Section 15.

The potential $Z_j$

Average the oscillations over all cells of stage $j$ :

Z_j=\frac1{bM}\sum_{I\times B}\operatorname{osc}_B\,a_I,\tag{1}

where the sum runs over the $bM$ cells $I\times B$ of stage $j$ . We call $Z_j$ the potential. In the example above, $I$ is an interval of stage 1, the only block is all of $[0,1)$ , and $a_I$ takes the three values $0$ , $\frac12$ , $1$ on it, so the oscillation is $1-0=1$ $1$ .

Two basic properties of

Z_j

Eq. (9) of the paper and the paragraph after it

0\le Z_j\le2\norm F_\infty,\tag{9}

and $Z_j$ is determined by $\mathcal F_j$ .

In the paper, (9) appears only in Section 2.4; we use its number here ahead of time.

ProofThe two properties

Lower bound. Every term is a maximum minus a minimum, so it cannot be negative.
Upper bound. By (3), an oscillation is a difference of two values of $a_I$ . By (2), each value of $a_I$ is an average of two values of $F$ , so its absolute value is at most $\norm F_\infty$ . So every oscillation is at most $2\norm F_\infty$ , and so is their average.
Determined by $\mathcal F_j$ . The endpoints of the intervals of stage $j$ are integer multiples of $b^{-j}$ . The first $j$ digits of a point tell whether it lies to the left or to the right of such an endpoint. So every weight $w_I(U_i)$ is determined by $\mathcal F_j$ , and the vertical coordinates are known anyway.

Note that $Z_0$ need not be 0: the blocks of stage 0 are very short, but they may still contain points. Later we only use $Z_0\ge0$ $0$ .

The upper bound in (9) is the only link between $Z$ and the discrepancy, but it is all we need:

\norm{F_\chi}_\infty\ \ge\ \tfrac12Z_h.

So if $Z_h$ is large, then this coloring has an anchored rectangle with large imbalance. We start from $Z_0\ge0$ and take $h$ steps. The plan for what follows is to show that $Z$ increases on average at every step, and that its actual value is unlikely to fall far below the average.

Move the stage from 0 to 3; three things can be seen. At stage 0 the blocks are very short, a block usually contains between zero and two or three points, and the oscillation is mostly 0, $\frac12$ or 1, so $Z_0$ is small. For this point set, at later stages the cells become narrower and taller, every block is taller and contains more points, the colors get deeper overall, and $Z_j$ grows with them. But whatever happens, the bars never cross the dashed line; this is (9). Now switch to the coloring “Alternate in y order”: it keeps $F(1,y)$ very small, and yet in this sample $Z_j$ still grows, because $a_I$ on a narrow interval sees only part of the points, and there the alternating pattern is broken.

All of this describes one sample. In a single realization $Z_j$ can perfectly well decrease, and two points suffice: take $b=3$ and $h=1$ $1$ , color the point $(\frac45,\frac15)$ red and the point $(\frac9{10},\frac45)$ blue, and the definitions give $Z_0=\frac13$ and $Z_1=\frac16$ $\frac{1}{6}$ . What the proof shows later is that the conditional expectation increases; the deviation of the actual value from the conditional expectation is controlled separately.

Why the endpoint average, and why the oscillation

The endpoint average makes the refinement clean: cut $I$ into $b$ children, let each point fall into one of them at random, and average the endpoint averages of the children; the expectation is exactly the old $a_I$ (Eq. (7) in Section 14). Taking only the right endpoint does not have this property.

The oscillation is shift invariant: adding a constant on a whole block moves the maximum and the minimum together, and their difference does not change. If one point moves horizontally, then for each fixed interval I only the oscillation of the vertical block containing its height can change (Section 15). The maximum of $|a_I|$ would not achieve this.

§ 13 · Core argumentThe comparison in one rectangle, part 1: the deterministic part

Goal of these two sections

Fix a comparison rectangle $R=I\times J$ $J$ . Before the refinement, $R$ consists of the $b$ horizontal strips $I\times B_\ell$ $B_{ℓ}$ ; after it, of the $b$ vertical strips $C_k\times J$ $J$ . Remove the bottom and top horizontal strips of $R$ . What remains is called the inner region of $R$ , and we write $m_R$ for the number of points in it:

R^{\mathrm{in}}=I\times(B_2\cup\dots\cup B_{b-1}),\qquad m_R=|P\cap R^{\mathrm{in}}|.

The inner region is not empty because $b\ge3$ $3$ . These two sections prove Lemma 2.3: in expectation, the oscillations on the vertical strips add up to at least those on the horizontal strips plus an extra term,

\EE\Bigl[\,\sum_{k=1}^b\operatorname{osc}_J\,a_{C_k}\Bigr]\ \ge\ \sum_{\ell=1}^b\operatorname{osc}_{B_\ell}\,a_I\ +\ \frac14\sqrt{m_R}.

This section does the part that involves no probability and obtains (5) and (6). They hold for every outcome of the dice. The next section takes expectations.

To save subscripts, in these two sections we write $a$ for $a_I$ and call it the old function, and we write $a_k$ for $a_{C_k}$ and call these the child functions. The paper uses the same notation.

Step 1: an inequality for step functions

Forget the points and the dice for a moment, and consider a function $f$ on $J$ with finitely many values. How is its oscillation on $J$ related to its oscillations on the $b$ old blocks? The first thing that comes to mind is that $J$ contains every old block, so $\operatorname{osc}_J\,f\ge\operatorname{osc}_{B_\ell}\,f$ $osc_{B_{ℓ}} f$ ; adding these $b$ inequalities gives $b\operatorname{osc}_J\,f\ge\sum_\ell\operatorname{osc}_{B_\ell}\,f$ $\sum_{ℓ} osc_{B_{ℓ}} f$ . Lemma 2.1 says that there is in fact an extra term.

Lemma 2.1 (Vertical comparison)Lemma 2.1 of the paper

Let $f$ be a function on $J$ with finitely many values. Then

b\,\operatorname{osc}_J\,f\ \ge\ \sum_{\ell=1}^b\operatorname{osc}_{B_\ell}\,f+2\,\bigl|\operatorname{mid}_{B_b}f-\operatorname{mid}_{B_1}f\bigr|.\tag{4}

We call $\operatorname{mid}_{B_b}f-\operatorname{mid}_{B_1}f$ the offset between the top block and the bottom block: it tells by how much the center of the range of values of $f$ on the top block differs from the center of its range of values on the bottom block.

ProofLemma 2.1

The bottom and top blocks together. $B_1$ and $B_b$ are both contained in $J$ , and the maximum and the minimum of $f$ on a block $B$ are $\operatorname{mid}_B\,f\pm\frac12\operatorname{osc}_B\,f$ $\frac{1}{2} osc_{B} f$ . Subtract the minimum on the bottom block from the maximum on the top block, and then do the same with the two blocks exchanged: $\begin{aligned}\operatorname{osc}_J\,f&\ \ge\ \max_{B_b}f-\min_{B_1}f=\frac{\operatorname{osc}_{B_1}f+\operatorname{osc}_{B_b}f}2+\bigl(\operatorname{mid}_{B_b}f-\operatorname{mid}_{B_1}f\bigr),\\[4pt]\operatorname{osc}_J\,f&\ \ge\ \max_{B_1}f-\min_{B_b}f=\frac{\operatorname{osc}_{B_1}f+\operatorname{osc}_{B_b}f}2-\bigl(\operatorname{mid}_{B_b}f-\operatorname{mid}_{B_1}f\bigr).\end{aligned}$
Take the larger one. The two right-hand sides differ only in the sign in front of the offset, so $\operatorname{osc}_J\,f\ \ge\ \frac{\operatorname{osc}_{B_1}f+\operatorname{osc}_{B_b}f}2+\bigl|\operatorname{mid}_{B_b}f-\operatorname{mid}_{B_1}f\bigr|.$
The middle blocks. For each of the $b-2$ middle blocks, use $\operatorname{osc}_J\,f\ge\operatorname{osc}_{B_\ell}\,f$ $osc_{B_{ℓ}} f$ . Add these $b-2$ inequalities and twice the inequality of Step 2; the left-hand sides add up to $b$ times $\operatorname{osc}_J\,f$ .

The bottom and top blocks are shaded gray. In this example the oscillations on the four blocks are

1,\ 2,\ 1,\ 1.5

and the offset is

0.75

; the right-hand side of (4) is

5.5+2\times0.75=7

7

, and the left-hand side is

4\times2.5=10

10

The offset is the source of the gain that comes later. Add a constant to $f$ on the top block: this changes the offset, but none of the oscillations on the blocks. So among the terms of (4), only the oscillation on $J$ , on the left-hand side, can register it.

Step 2: after the refinement, average the child functions

Now cut $I$ into $b$ children $C_1,\dots,C_b$ . Each child has its own endpoint average $a_k=a_{C_k}$ $a_{C_{k}}$ . We do not study them one by one, but first average them:

\bar a(y)=\frac1b\sum_{k=1}^ba_k(y).

By the triangle inequality for the oscillation (Section 12), the oscillations of the $b$ functions add up to at least the oscillation of their sum, and their sum is $b\,\bar a$ :

\sum_{k=1}^b\operatorname{osc}_J\,a_k\ \ge\ \operatorname{osc}_J\Bigl(\sum_{k=1}^ba_k\Bigr)=b\,\operatorname{osc}_J\,\bar a.

The right-hand side has exactly the form of the left-hand side of Lemma 2.1. Apply Lemma 2.1 to $f=\bar a$ $\overset{a}{ˉ}$ :

Average first, then compareEq. (5) of the paper

\sum_{k=1}^b\operatorname{osc}_J\,a_k\ \ge\ \sum_{\ell=1}^b\operatorname{osc}_{B_\ell}\,\bar a+2\,\bigl|\operatorname{mid}_{B_b}\bar a-\operatorname{mid}_{B_1}\bar a\bigr|.\tag{5}

The left-hand side is the sum of the oscillations on the $b$ vertical strips after the refinement, which is exactly the quantity we want. The right-hand side involves only one function, $\bar a$ : its oscillations on the $b$ old blocks, plus twice its offset between the top block and the bottom block. The details of the $b$ individual children have disappeared.

Up to this point no probability has been used. Inequality (5) holds no matter which children the points fall into.

Step 3: the weight of a point in $\bar a$

To compare $\bar a$ with the old function $a$ , we first compute the weight of each point in $\bar a$ . By (2), the function $\bar a$ counts each point with the average of its weights in the $b$ children, whereas $a$ counts it with its weight in $I$ , which we call its old weight. A point to the left of $I$ has weight 1 in every $a_k$ , so the average is again 1; a point to the right of $I$ has weight 0 in all of them. These two kinds of points count in $\bar a$ exactly as they do in $a$ .

A point in $I$ has old weight $\frac12$ , and its new weight depends on the child it falls into. Suppose it falls into $C_r$ . It lies to the left of the $b-r$ children on its right, and each of them gives it weight 1; its own child gives it weight $\frac12$ ; the children on its left give it weight 0. So its weight in $\bar a$ is

\frac{(b-r)+\frac12}b=\frac12+\frac{b+1-2r}{2b}\qquad(r=1,\dots,b).

Here $r$ is the index of the child, that is, the outcome of the die.

For $b=4$ $4$ , put the weights that the children give to the point into a table, with one row for each child $k$ and one column for each outcome $r$ of the die. The average of each column is the weight of the point in $\bar a$ :

	$r=1$	$r=2$	$r=3$	$r=4$
weight in $a_1$	$\frac12$	0	0	0
weight in $a_2$	1	$\frac12$	0	0
weight in $a_3$	1	1	$\frac12$	0
weight in $a_4$	1	1	1	$\frac12$
weight in $\bar a$	$\frac78$	$\frac58$	$\frac38$	$\frac18$
deviation from $\frac12$	$+\frac38$	$+\frac18$	$-\frac18$	$-\frac38$

The formula above splits the weight into two parts. The first part, $\frac12$ , is the old weight. The second part is a deviation, which can be positive or negative. Multiply it by the color: for the $i$ -th point, lying in the child $C_r$ , let

X_i=\chi_i\cdot\frac{b+1-2r}{2b},

and call $X_i$ the jump of this point: it is the extra jump that $\bar a$ makes, compared with $a$ , at the height of the point. So $\bar a$ is $a$ plus the jumps of the points in $I$ :

\bar a

equals

a

plus the jumpsEq. (6) of the paper

\bar a(y)=a(y)+\sum_{i:\ U_i\in I,\ V_i\le y}X_i.\tag{6}

The sum runs over the points in $I$ of height at most $y$ . In words, $\bar a$ follows the old function and makes an extra jump $X_i$ at the height of each point in $I$ . This is still an identity; no probability is involved.

Take $b=4$ $4$ , draw one comparison rectangle $R$ , and consider only the points in $R$ . First select “ $a$ ”: the right panel shows the step function $a(y)$ , and the thick line next to each old block runs from the minimum to the maximum on this block, so its length is the oscillation on the block. Then select “ $\bar a$ ”: the solid line is $\bar a$ after the dice have been rolled, and the dashed line is the old function $a$ ; on the thick lines of the bottom and top blocks, a dot marks the midpoint. The thick line below the plot runs from one midpoint to the other, and its length is the absolute value of the offset. Click $C_1,\dots,C_4$ to see the function of each child and its oscillation on the whole of $J$ .

Press “Roll again” a few times. Each time $\bar a$ is different, and it moves to either side of the dashed line $a$ . But the chain of inequalities in the readout holds every time: the sum of the oscillations on the four vertical strips is at least $4\operatorname{osc}_J\bar a$ , which in turn is at least the right-hand side of (5).

Pitfall

The function $\bar a(y)$ is itself random: it depends on the dice. The next section shows that its expectation is $a(y)$ . But after one roll, the weight of a point may be $\frac78$ , and it may be $\frac18$ ; for $b=4$ no outcome gives exactly $\frac12$ (for odd $b$ , only the middle child gives $\frac12$ ).

The $\frac12$ cannot be replaced either. Suppose that we did not take the endpoint average and used only the value of $F$ at the right endpoint of the interval. Then a point would have weight 1 in its own child, and its weight in the average would become $\frac{b-r+1}b$ . The mean of this over $r$ is $\frac{b+1}{2b}$ , whereas the weight of the point in $I$ would be 1, so the two sides do not match.

Another view: conditional expectation

Choose a horizontal coordinate $x$ uniformly at random in the interval $I$ , independently of all the points. Then $a_I(y)$ is the conditional expectation of $F(x,y)$ given $\mathcal F_j$ : a point in $I$ and $x$ are both uniform in $I$ , so each of them is to the left of the other with probability one half. Section 3 of the paper writes this as $a_I(y)=\EE\bigl[\frac1{|I|}\int_IF(x,y)\,dx\bigm|\mathcal F_j\bigr]$ and notes that it is the conditional version of the horizontal average in Talagrand's proof. In the same way, $\bar a(y)$ is the conditional expectation of the same quantity given $\mathcal F_{j+1}$ , with one more digit known. (The average here also runs over the exact positions of the points inside the interval, so it is no longer a weighted average over finitely many outcomes, but the four properties of Section 10 still hold.)

§ 14 · Core argumentThe comparison in one rectangle, part 2: expectation, baseline and gain

The previous section gave (5), which holds for every outcome of the dice:

\sum_{k=1}^b\operatorname{osc}_J\,a_k\ \ge\ \sum_{\ell=1}^b\operatorname{osc}_{B_\ell}\,\bar a+2\,\bigl|\operatorname{mid}_{B_b}\bar a-\operatorname{mid}_{B_1}\bar a\bigr|.

This section takes the expectation of the right-hand side, in two parts. First: the expected oscillation of $\bar a$ on each old block is at least the oscillation of $a$ ; this is the baseline. Second: the expected absolute value of the offset is at least $\frac18\sqrt{m_R}$ ; multiplied by 2, this is the gain. Together they give Lemma 2.3.

What is random

First, what is fixed and what is random. All colors and all heights are fixed, and so is the position of every point relative to $I$ (to the left of $I$ , in $I$ , or to the right of $I$ ). Each point in $I$ falls into one of the $b$ children, uniformly at random and independently of the other points; that is, each of them rolls its own $b$ -sided die. This is the local experiment. In the local experiment the old function $a$ is fixed, and the child functions $a_1,\dots,a_b$ are random. Every $\EE$ below is taken over these dice.

Nothing else needs to be specified: a point outside $I$ lies on the same side of every child, so the child functions depend on the horizontal coordinates only through two things: the position of each point relative to $I$ , and the child that each point in $I$ falls into. Section 16 will show that, conditionally on $\mathcal F_j$ , this is exactly the experiment that takes place in every comparison rectangle during one transition.

Step 1: the jumps are symmetric, so $\EE\,\bar a=a$

Consider the jump $X_i=\chi_i\cdot\frac{b+1-2r}{2b}$ of a point in $I$ , where $r$ is uniform on $1,\dots,b$ . As $r$ runs from 1 to $b$ , the number $b+1-2r$ takes the values $b-1,\ b-3,\ \dots,\ -(b-1)$ $1)$ , and this set is symmetric about 0. So, whatever the color is, $X_i$ takes each value and its negative with the same probability: it is symmetric (it has the same distribution as $-X_i$ ), and in particular $\EE X_i=0$ $0$ . Different points use different dice, so the jumps are independent.

By (6), $\bar a(y)$ equals $a(y)$ plus a number of jumps, each with expectation 0. So

The expectation of the average is the old functionEq. (7) of the paper

\EE\,\bar a(y)=a(y)\qquad\text{for every height }y.\tag{7}

Refine once and then average: in expectation, this gives back the old function. This is what Section 12 meant by saying that the endpoint average makes the refinement clean.

Step 2: the baseline

Tool · The expectation of a maximum is at least the maximum of the expectations

Let $\phi(y)$ be a random function (its value at each $y$ is a random variable), and let $B$ be a set. For every fixed $y_0$ in $B$ we always have $\max_{y\in B}\phi(y)\ge\phi(y_0)$ $ϕ (y_{0})$ . Taking expectations on both sides gives $\EE\max_{y\in B}\phi(y)\ge\EE\,\phi(y_0)$ $E ϕ (y_{0})$ . This holds for every $y_0$ , so

\EE\max_{y\in B}\phi(y)\ \ge\ \max_{y_0\in B}\EE\,\phi(y_0).

In the same way, $\EE\min_{y\in B}\phi(y)\le\min_{y_0\in B}\EE\,\phi(y_0)$ $min_{y_{0} \in B} E ϕ (y_{0})$ .

Intuitively: looking at the dice first and then picking the best height is, on average, no worse than fixing a height in advance. Apply the tool to $\bar a$ and each old block $B_\ell$ , and then use (7):

\EE\operatorname{osc}_{B_\ell}\bar a=\EE\max_{B_\ell}\bar a-\EE\min_{B_\ell}\bar a\ \ge\ \max_{B_\ell}a-\min_{B_\ell}a=\operatorname{osc}_{B_\ell}a.

The old oscillation is kept. Sum over $\ell=1,\dots,b$ $1, \dots, b$ , and take expectations on both sides of (5):

The baseline, plus the expected offsetEq. (8) of the paper

\EE\Bigl[\,\sum_{k=1}^b\operatorname{osc}_J\,a_k\Bigr]\ \ge\ \sum_{\ell=1}^b\operatorname{osc}_{B_\ell}\,a+2\,\EE\,\bigl|\operatorname{mid}_{B_b}\bar a-\operatorname{mid}_{B_1}\bar a\bigr|.\tag{8}

The first term on the right is the sum of the oscillations over the horizontal strips before the refinement; this step says that nothing is lost. The second term is the gain, and the next three steps bound it from below.

Step 3: separating the contribution of the points of the inner region

The points of the inner region $R^{\mathrm{in}}=I\times(B_2\cup\dots\cup B_{b-1})$ have a special property: they all lie above $B_1$ and below $B_b$ . Let

D=\sum_{i:\ P_i\in R^{\mathrm{in}}}X_i

be the sum of the jumps of these $m_R$ points, and let $g$ be the function in (6) without these jumps:

g(y)=a(y)+\sum_{i:\ U_i\in I,\ P_i\notin R^{\mathrm{in}},\ V_i\le y}X_i.

Then:

on $B_1$ , none of the points of the inner region has been counted yet, so $\bar a=g$ $g$ ;
on $B_b$ , all of them have been counted, so $\bar a=g+D$ $D$ , which is $g$ raised by the constant $D$ on the whole block.

This corresponds to Figure 3 (left and middle) of the paper. The 10 points of the inner region determine

D

. The 4 faint points in the two gray blocks at the bottom and the top enter only

g

: their heights lie in

B_1

B_8

, so their jumps affect only part of a block and cannot be pulled out as a constant.

Adding a constant $D$ on a whole block adds $D$ to both the maximum and the minimum, and therefore adds $D$ to the midpoint. So

The offset contains

D

Step 4 of the proof of Lemma 2.3 in the paper

\operatorname{mid}_{B_b}\bar a-\operatorname{mid}_{B_1}\bar a=\theta+D,\qquad\text{where}\ \ \theta=\operatorname{mid}_{B_b}g-\operatorname{mid}_{B_1}g.

$\theta$ is the offset of $g$ itself: how far apart the top block and the bottom block already are without the jumps of the points of the inner region.

Example

Take $b=4$ $4$ . To keep things simple, suppose there are only two points in all, both in $R$ : a red point in $B_2$ and a blue point in $B_3$ , so both are points of the inner region. Before the refinement, $a$ rises from 0 to $\frac12$ at the red point and falls back to 0 at the blue point. The oscillations on the four old blocks are $0,\frac12,\frac12,0$ , and their sum is 1. Note that $a$ is identically 0 on both the bottom block and the top block: the two colors cancel, and there is no offset between the two blocks.

After the refinement, suppose the red point falls into $C_r$ and the blue point into $C_{r'}$ . There are no other points, so $g=a$ $a$ , $\theta=0$ $0$ , and $D=\frac{5-2r}8-\frac{5-2r'}8=\frac{r'-r}4$ $\frac{r ^{'} - r}{4}$ . The average $\bar a$ is 0 on $B_1$ and the constant $D$ on $B_4$ , so the offset is $D$ . Among the sixteen equally likely outcomes:

$\|D\|$	0	$\frac14$	$\frac12$	$\frac34$
number of outcomes	4	6	4	2

So $\EE|D|=\frac1{16}\bigl(6\cdot\frac14+4\cdot\frac12+2\cdot\frac34\bigr)=\frac5{16}$ $\frac{5}{16}$ . Before the refinement the top and bottom blocks were exactly level; after it, they remain level only one time in four. The second term on the right of (8) is $2\cdot\frac5{16}=\frac58$ $\frac{5}{8}$ ; Lemma 2.3 guarantees $\frac14\sqrt2\approx0.35$ $0.35$ .

The offset is a fixed number $\theta$ plus a random sum $D$ . For a particular outcome of the dice, $D$ may happen to cancel the offset $\theta$ that is already there. But $D$ is a sum of independent symmetric jumps, and such a sum does not stay close to any one number, so on average it cannot cancel the offset. The next step turns this sentence into an inequality.

Step 4: a sum of symmetric random variables is not close to any fixed point

First compute two moments of a jump. $X_i^2$ does not depend on the color, and $r$ is uniform on $1,\dots,b$ :

\EE X_i^2=\frac1b\sum_{r=1}^b\Bigl(\frac{b+1-2r}{2b}\Bigr)^2=\frac{b^2-1}{12b^2}=:\sigma^2.

Also $|X_i|\le\frac{b-1}{2b}$ (with equality for $r=1$ or $b$ ), so $X_i^4\le\bigl(\frac{b-1}{2b}\bigr)^2X_i^2$ $(\frac{b - 1}{2 b})^{2} X_{i}^{2}$ , and hence

\EE X_i^4\le\Bigl(\frac{b-1}{2b}\Bigr)^2\sigma^2\le\frac{b^2-1}{4b^2}\,\sigma^2=3\sigma^4.

DerivationThe two moments

Second moment. The number $b+1-2r$ takes the values $b-1,\ b-3,\ \dots,\ -(b-1)$ $1)$ , and the sum of their squares is $\frac{b(b^2-1)}3$ (for example, for $b=4$ $4$ : $9+1+1+9=20=\frac{4\cdot15}3$ $\frac{4 \cdot 15}{3}$ ). So $\EE X_i^2=\frac1b\cdot\frac{b(b^2-1)}{3\cdot4b^2}=\frac{b^2-1}{12b^2}$ $\frac{b ^{2} - 1}{12 b ^{2}}$ . The paper computes this differently: $X_i^2=\bigl(r-\frac{b+1}2\bigr)^2/b^2$ $\frac{b + 1}{2})^{2} / b^{2}$ , and the variance of $r$ is $\frac{(b+1)(2b+1)}6-\frac{(b+1)^2}4=\frac{b^2-1}{12}$ $\frac{b ^{2} - 1}{12}$ .
Fourth moment. The middle inequality is $(b-1)^2\le b^2-1$ $1$ , that is, $b\ge1$ $1$ . The final equality is $\frac{b^2-1}{4b^2}=3\sigma^2$ $3 σ^{2}$ .

For large $b$ , $\sigma^2$ is close to $\frac1{12}$ , which is the variance of the uniform distribution on $[-\frac12,\frac12]$ .

Tool · The Cauchy–Schwarz inequality (for expectations)

For any random variables $X,Y$ , we have $\EE|XY|\le\sqrt{\EE[X^2]\cdot\EE[Y^2]}$ $E [X^{2}] \cdot E [Y^{2}]$ .

Proof: for every $s>0$ $0$ , the inequality $(\sqrt s\,|X|-|Y|/\sqrt s)^2\ge0$ gives $|XY|\le\frac12\bigl(sX^2+Y^2/s\bigr)$ $Y^{2} / s)$ . Take expectations, and then take $s=\sqrt{\EE[Y^2]/\EE[X^2]}$ $E [Y^{2}] / E [X^{2}]$ . If one of the second moments is 0, the claim is trivial.

Fact 2.2 (Sums of symmetric variables)Fact 2.2 of the paper; proved in Appendix A.1

Let $X_1,\dots,X_m$ be independent symmetric random variables. Suppose that $\EE X_i^2=\sigma^2$ and $\EE X_i^4\le3\sigma^4$ for every $i$ , where $\sigma>0$ $0$ . Then, for every real $\theta$ ,

\EE\,\bigl|\theta+X_1+\dots+X_m\bigr|\ \ge\ \sigma\sqrt{\frac m3}.

For uniform $\pm1$ signs this is Khintchine's inequality (with a weaker constant); the fourth-moment hypothesis holds for uniform signs, and we have just checked it for the jumps.

ProofFact 2.2

Write $Y=X_1+\dots+X_m$ $X_{m}$ . For $m=0$ the right-hand side is 0 and the claim is trivial, so let $m\ge1$ $1$ .

The shift does not hurt. Every $X_i$ is symmetric, and they are independent. So $Y$ and $-Y$ have the same distribution, and $\EE|\theta+Y|=\EE|\theta-Y|$ $Y ∣$ . Averaging the two and using $|\theta+y|+|\theta-y|\ge2|y|$ gives $\EE|\theta+Y|\ge\EE|Y|$ $E ∣ Y ∣$ .
Second moment. $\EE Y^2=\sum_{i,j}\EE[X_iX_j]=\sum_i\EE X_i^2=m\sigma^2$ $m σ^{2}$ , because $\EE[X_iX_j]=\EE X_i\cdot\EE X_j=0$ for $i\ne j$ $j$ .
Fourth moment. Expand $Y^4$ . If some index appears an odd number of times in a term, then by independence and symmetry the term has expectation 0. Two kinds of terms survive: the terms $X_i^4$ with four equal indices, and the terms $X_i^2X_j^2$ ( $i<j$ $j$ ) with two pairs of equal indices, each of which arises $\binom42=6$ times. So $\EE Y^4=\sum_i\EE X_i^4+6\sum_{i<j}\EE X_i^2\,\EE X_j^2\le3m\sigma^4+3m(m-1)\sigma^4=3m^2\sigma^4.$
Cauchy–Schwarz, twice. Split $Y^2$ as $|Y|^{1/2}\cdot|Y|^{3/2}$ $∣ Y ∣^{3/2}$ , and then split $|Y|^3$ as $|Y|\cdot Y^2$ $Y^{2}$ : $\EE Y^2\le\bigl(\EE|Y|\bigr)^{1/2}\bigl(\EE|Y|^3\bigr)^{1/2},\qquad\EE|Y|^3\le\bigl(\EE Y^2\bigr)^{1/2}\bigl(\EE Y^4\bigr)^{1/2}.$ Square the first inequality and insert the second: $(\EE Y^2)^2\le\EE|Y|\cdot(\EE Y^2)^{1/2}(\EE Y^4)^{1/2}$ $(E Y^{2})^{1/2} (E Y^{4})^{1/2}$ , that is, $\EE|Y|\ge(\EE Y^2)^{3/2}/(\EE Y^4)^{1/2}$ $(E Y^{2})^{3/2} / (E Y^{4})^{1/2}$ . At this point the paper applies Hölder's inequality once (with exponents $\frac32$ and 3); the result is the same.
Substituting. $\EE|Y|\ge\dfrac{m^{3/2}\sigma^3}{\sqrt3\,m\sigma^2}=\sigma\sqrt{\dfrac m3}$ $σ \frac{m}{3}$ .

Drag the shift: the curve is lowest at $\theta=0$ $0$ , which is Step 1 of the proof. The three horizontal lines are ordered from top to bottom, which is Steps 4 and 5. Move the number of terms from 1 to 12, and the three lines rise together at the rate $\sqrt m$ : the more terms there are, the more the sum spreads out, and the larger its average distance from any given point becomes. This is where the gain of order $\sqrt m$ from $m$ points of the inner region comes from.

Step 5: putting it together to get Lemma 2.3

Split the dice into two groups: the dice of the points of the inner region, and the dice of the other points in $I$ (the points whose heights lie in $B_1$ , in $B_b$ , or outside $J$ ). First treat the second group as known, and average only over the first group. Then $g$ is a fixed function and $\theta$ is a fixed number. And $D$ is a sum of $m_R$ independent symmetric jumps, which are independent of the second group of dice.

Apply Fact 2.2 to $\theta+D$ $D$ , with $m=m_R$ $m_{R}$ . The conditional expectation of the absolute value of the offset is at least

\sigma\sqrt{\frac{m_R}3}=\frac{\sqrt{b^2-1}}{6b}\,\sqrt{m_R}\ \ge\ \frac18\sqrt{m_R}.

The last inequality is $16(b^2-1)\ge9b^2$ $9 b^{2}$ , which holds for $b\ge2$ $2$ . This lower bound is the same for every $\theta$ , so no outcome of the second group of dice can reduce it; after averaging over the second group as well (the tower property of Section 10), it still holds:

\EE\,\bigl|\operatorname{mid}_{B_b}\bar a-\operatorname{mid}_{B_1}\bar a\bigr|\ \ge\ \frac18\sqrt{m_R}.

Substituting into (8):

Lemma 2.3 (Local gain)Lemma 2.3 of the paper

In the local experiment,

\EE\Bigl[\,\sum_{k=1}^b\operatorname{osc}_J\,a_k\Bigr]\ \ge\ \sum_{\ell=1}^b\operatorname{osc}_{B_\ell}\,a\ +\ \frac14\sqrt{m_R}.

The left-hand side is the sum of the oscillations over the $b$ vertical strips of $R$ after the refinement, and the first term on the right is the sum of the oscillations over the $b$ horizontal strips before it. Cutting $R$ into vertical strips instead of horizontal ones increases the total oscillation in expectation, by at least $\frac14\sqrt{m_R}$ . The paper calls this lemma the heart of the proof.

How large is this gain? A comparison rectangle contains $\frac nM$ points on average, and a fraction $1-\frac2b$ of them lie in the inner region. So typically each refinement of each comparison rectangle increases the sum of the oscillations by an amount of order $\sqrt{n/M}$ . This is the price mentioned at the end of Section 5: one extra square root per level.

One more point will be used later: the number $m_R$ , which sets the size of the gain, only counts points and does not look at their colors. The coloring changes $\theta$ , and it changes the signs of the $X_i$ ; but each $X_i$ is symmetric, so changing its sign does not change its distribution, and Fact 2.2 holds for every $\theta$ .

Take $b=8$ $8$ , draw a single comparison rectangle $R$ , and consider only the points in $R$ . In the left picture, the horizontal bands are the 8 old blocks and the columns are the 8 children; the two gray bands are the bottom and top old blocks. Each press of “Roll again” lets every point fall into a random child again. The table compares, on each old block, the oscillation of $a$ with the oscillation of $\bar a$ for this roll. The readouts give the two parts of the right-hand side of (5) and the new sum on its left-hand side, and then the averages over many rolls.

Roll a few times, and then press “Average over 20,000 rolls”. Three things should be visible. The long-run average of the sum of the oscillations of $\bar a$ is at least the old sum; this is the baseline. The long-run average of twice the offset is clearly larger than $\frac14\sqrt{m_R}$ , which is only a conservative lower bound. And the long-run average of the new sum is considerably larger than “baseline plus gain”: the triangle inequality for the oscillation and Lemma 2.1 both give something away. Increase the number of points, and the offset grows roughly like the square root of the number of points.

What one rectangle gives, and what is missing

What does Lemma 2.3 give when it is applied directly to the whole square? Take $I=[0,1]$ and $J=[0,1)$ $[0, 1)$ , so that $R$ is the unit square without its top edge. Every oscillation of a child function is a difference of two values of $a_k$ , and each of them is an average of two values of $F$ , so it is at most $2\norm F_\infty$ ; hence the left-hand side in the lemma is at most $2b\,\EE\norm F_\infty$ . When the heights are fixed and the horizontal coordinates are independent and uniform, the first digits perform the local experiment, and the lemma gives

\EE\,\norm F_\infty\ \ge\ \frac{\sqrt{m_R}}{8b}.

For typical heights, the inner region contains about $(1-\frac2b)n$ points, so this is of order $\sqrt n$ , far larger than the $\log^{3/2}n$ that we want to prove.

Pitfall

This is not a discrepancy lower bound. The coloring above was fixed before the horizontal coordinates were sampled, and a coloring chosen after seeing the points achieves $O(\log^{3/2}n)$ (Nikolov). We need a bound for all $2^n$ colorings simultaneously, so each fixed coloring may fail only with probability well below $2^{-n}$ . One comparison on one rectangle gives only an expectation, and that is far from this requirement.

The next four sections therefore use $M$ small rectangles in place of one large rectangle, and repeat the comparison at $h$ successively finer horizontal scales. Lemma 2.3 is designed for this: its output (a sum of oscillations over vertical strips) has the same form as its input (a sum of oscillations over horizontal strips), so the output of one transition can be used directly as the input of the next. Two things are then still missing:

Point countsThe gain depends on how many points each inner region receives. Can the points crowd together too much? Section 17, Lemma 2.5.

ExpectationLemma 2.3 holds only in expectation. Can the actual value be much smaller than the expectation? Sections 15 and 16, Lemma 2.6.

§ 15 · IntermediateThe effect of changing one digit

Lemma 2.3 is a statement about an average. To turn an average into “almost always”, we need to know how sensitive the oscillations after the refinement are to each single die. The answer is: hardly at all. This section contains no probability. It uses only two properties from Section 12: the shift invariance of the oscillation, and the reverse triangle inequality $\bigl|\operatorname{osc}_B(f+g)-\operatorname{osc}_B\,f\bigr|\le\operatorname{osc}_B\,g$ $osc_{B} g$ . In the paper this is Step 1 of the proof of Lemma 2.6.

The effect of one digitStep 1 of the proof of Lemma 2.6 in the paper

In the transition $j\to j+1$ $1$ , change the next digit of a single point $P_i$ , that is, move it to another child of its old interval $I$ , and leave all other points where they are. Then, among the $bM$ cells of stage $j+1$ $1$ , the oscillation can change in only $b$ of them, and in each by at most 1. So

Z_{j+1}\ \text{changes by at most}\ \frac b{bM}=\frac1M.

ProofWhy only

b

cells are affected

Which functions change. Suppose that $P_i$ moves from $C_r$ to $C_{r'}$ . Its weight changes only in the $b$ children of $I$ : seen from any other interval, the point is still on the same side. Its weight in $a_k$ is $1$ , $\frac12$ or $0$ , and after the move it is again one of these three numbers. So $a_k(y)\ \text{changes by}\ e_k\,\one_{\{V_i\le y\}},\qquad|e_k|\le1,$ where $e_k$ is $\chi_i$ times the difference between the new weight and the old weight. This is a step function with a single jump, at height $V_i$ .
The height is not in the block. Consider a cell $C_k\times B$ of stage $j+1$ $1$ , where $B$ is a new block. If $V_i\notin B$ $B$ , then $B$ lies either entirely below $V_i$ or entirely above it, and the change displayed above is constant on $B$ . The oscillation is shift invariant, so $\operatorname{osc}_B\,a_k$ does not change.
The height is in the block. On $B$ the change takes only the two values 0 and $e_k$ , so its own oscillation is $|e_k|\le1$ $1$ . By the reverse triangle inequality, $\operatorname{osc}_B\,a_k$ changes by at most 1.
In total. Exactly one new block contains $V_i$ ; call it $J$ . The affected cells are the $b$ cells $C_1\times J,\dots,C_b\times J$ $J$ , and together they form the comparison rectangle $I\times J$ $J$ . The potential $Z_{j+1}$ is the sum of the $bM$ oscillations divided by $bM$ , so it changes by at most $\frac b{bM}$ .

This shows why we measure oscillation. With the past fixed, changing one point’s next horizontal digit changes $a_k$ at every height above the point, so many blocks may be affected. But the oscillation changes in only one of these blocks; in the others the function is merely shifted by a constant. If we measured the maximum of $|a_k|$ instead, all of these blocks would have to be counted.

However you move the point, the marked cells all lie in one row, namely the block that contains the point, and the absolute values of the changes sum to at most $b=4$ $4$ . We now have both facts about one refinement step:

AverageLemma 2.3: in every comparison rectangle, the sum of the oscillations increases on average by at least

\frac14\sqrt{m_R}

EffectChanging the next digit of one point changes the sum of the oscillations only in the comparison rectangle that contains the point, and there by at most

b

;

Z_{j+1}

changes by at most

\frac1M

§ 16 · Core argumentAll $h$ transitions: the plan, conditional gain and fluctuations

The last three sections looked at one comparison rectangle and one refinement. We now return to $Z_0,Z_1,\dots,Z_h$ from Section 12 and put the $h$ transitions together. This section first lists the plan for the rest of the proof and then carries out two of its steps: Lemma 2.4 says how much each transition gains on average, and Lemma 2.6 says that the actual increment is unlikely to be far below this average.

Step 1: splitting the increment into “conditional gain” and “fluctuation”

The potential $Z_j$ is determined by $\mathcal F_j$ . So the actual increment in each transition can be written as two parts:

Z_{j+1}-Z_j=\underbrace{\EE\bigl[Z_{j+1}-Z_j\bigm|\mathcal F_j\bigr]}_{\text{conditional gain: the average increment}}+\underbrace{\bigl(Z_{j+1}-\EE[Z_{j+1}\mid\mathcal F_j]\bigr)}_{\text{fluctuation: actual value minus average}}.

Summing over $j=0,\dots,h-1$ gives the identity

Initial value, conditional gains and fluctuation termEq. (10) of the paper

Z_h=Z_0+\sum_{j<h}\EE\bigl[Z_{j+1}-Z_j\bigm|\mathcal F_j\bigr]+T,\qquad T=\sum_{j<h}\bigl(Z_{j+1}-\EE[Z_{j+1}\mid\mathcal F_j]\bigr).\tag{10}

We call $\EE[Z_{j+1}-Z_j\mid\mathcal F_j]$ the conditional gain of the transition $j\to j+1$ $1$ , and $T$ the fluctuation term. By (9), $Z_0\ge0$ and $Z_h\le2\norm F_\infty$ $2 ∥ F ∥_{\infty}$ . So $\norm F_\infty$ is large as soon as the sum of the last two terms on the right is large. The rest of the proof has three steps.

(a)Each conditional gain is at least a number

\delta_j

that depends only on the positions of the points, not on the coloring. Lemma 2.4, this section.

(b)When

M\le n

and

b

is large,

\delta_j

is large for every

j

, except with exponentially small probability. Lemma 2.5, Section 17.

(c)For a fixed coloring, the fluctuation term

T

is unlikely to be very negative. Lemma 2.6, this section.

Proposition 2.7 (Section 18) puts the three steps together and takes a union bound over all colorings.

Step 2: the average gain of each transition

The transition $j\to j+1$ has $M$ comparison rectangles, each of area $\frac1M$ . As in Section 13, the inner region of a comparison rectangle $R$ is $R$ without its bottom and top old cells, and $m_R$ is the number of points in it.

Lemma 2.4 (Conditional gain)Lemma 2.4 of the paper

For every $0\le j<h$ $h$ , almost surely

\EE\bigl[\,Z_{j+1}-Z_j\bigm|\mathcal F_j\bigr]\ \ge\ \delta_j:=\frac1{4bM}\sum_R\sqrt{m_R},\tag{11}

where $R$ ranges over the $M$ comparison rectangles of the transition $j\to j+1$ $1$ .

ProofLemma 2.4

Group by comparison rectangle. Every old cell is a horizontal strip of exactly one comparison rectangle, and every new cell is a vertical strip of exactly one: $R=I\times J$ contains the $b$ old cells $I\times B_\ell$ and the $b$ new cells $C_k\times J$ $J$ . So $bM\,(Z_{j+1}-Z_j)=\sum_R\Bigl(\sum_k\operatorname{osc}_J\,a_{C_k}-\sum_\ell\operatorname{osc}_{B_\ell}\,a_I\Bigr).$
Every comparison rectangle carries a local experiment. Given $\mathcal F_j$ : all heights are known; the position of every point relative to every old interval $I$ is known; and the next digits of the points in $I$ are independent uniform dice, which decide the child that each point falls into. This is exactly the local experiment of Section 14, and it is performed in every $R$ at once. Here $a_I$ is the old function and $a_{C_1},\dots,a_{C_b}$ are the child functions.
Sum. Apply Lemma 2.3 to each $R$ : the conditional expectation of the quantity in parentheses is at least $\frac14\sqrt{m_R}$ . Adding over all $R$ and dividing by $bM$ gives (11).

The number $\delta_j$ is not negative, so on average the potential does not decrease in any transition. How large is $\delta_j$ ? If every inner region held about $\frac nM$ points, we would add $M$ terms $\sqrt{n/M}$ and divide by $4bM$ , so $\delta_j$ would be about $\frac1{4b}\sqrt{n/M}$ . Over $h$ transitions this accumulates to the order of $h\sqrt{n/M}$ . But an “if” is not a guarantee; Section 17 deals with it.

The number $\delta_j$ has one more feature: $m_R$ counts points and ignores their colors. So $\delta_j$ is the same number for all $2^n$ colorings.

Each term of the middle sum in (10) is at least $\delta_j\ge0$ $0$ . Each term of $T$ has mean 0 given $\mathcal F_j$ , and it can be positive or negative. To prove that $Z_h$ is large, only one thing can go wrong: $T$ is a very negative number and eats up the gain. We now show that this has extremely small probability.

Step 3: bounded differences

Tool · A bounded random variable with mean zero

Let $c>0$ , $\mathbb E Y=0$ and $|Y|\le c$ . For every real $t$ , $\mathbb E e^{tY}\le\cosh(tc)\le e^{t^2c^2/2}$ . If $c=0$ , then $Y=0$ almost surely and the bound is immediate.

Proof: the function $y\mapsto e^{ty}$ is convex, so on the interval $[-c,c]$ it lies below the chord that joins its two endpoints:

e^{tY}\le\frac{c+Y}{2c}\,e^{tc}+\frac{c-Y}{2c}\,e^{-tc}.

Take expectations. Since $\EE\,Y=0$ $0$ , the right-hand side becomes $\frac12(e^{tc}+e^{-tc})=\cosh(tc)$ $cosh (t c)$ . The second inequality, $\cosh x\le e^{x^2/2}$ $e^{x^{2} /2}$ , was proved in Section 5.

The same holds for conditional expectations: if the conditional expectation of $Y$ given some information is 0, and $|Y|\le c$ $c$ , then the conditional expectation of $e^{tY}$ is at most $e^{t^2c^2/2}$ . The proof is the same word for word, with every $\EE$ replaced by a conditional expectation.

The circles all lie below the chord, so their center of mass also lies below the chord, and the height of the chord at 0 is exactly $\cosh(tc)$ . When the distribution takes only the two endpoint values, the center of mass lies exactly on the chord; this is the worst case. A little higher still is $e^{t^2c^2/2}$ . If you make $tc$ negative, the picture is mirrored left to right and the conclusion is the same.

Fact A.1 (Bounded differences)Fact A.1 of the paper (Appendix A.2)

Let $\xi_1,\dots,\xi_n$ be independent random variables, and let $\Gamma$ be a random element independent of the vector $(\xi_1,\dots,\xi_n)$ . Suppose $\varphi$ is measurable, $f=\varphi(\Gamma,\xi_1,\dots,\xi_n)$ is integrable, and $c>0$ . For each fixed value of $\Gamma$ , changing one coordinate $\xi_i$ changes $\varphi$ by at most $c$ . Then, for every real $t$ , almost surely

\EE\Bigl[\exp\bigl(t\,(f-\EE[f\mid\Gamma])\bigr)\Bigm|\Gamma\Bigr]\ \le\ \exp\Bigl(\frac{n\,t^2c^2}2\Bigr).

ProofFact A.1

Since $\Gamma$ is independent of the $\xi_i$ , conditioning on $\Gamma$ amounts to fixing the first argument of $\varphi$ at a value $\gamma$ . So it suffices to prove, for each fixed $\gamma$ , the unconditional bound $\EE\exp\bigl(t(f-\EE f)\bigr)\le\exp\bigl(\frac{nt^2c^2}2\bigr)$ $exp (\frac{n t ^{2} c ^{2}}{2})$ , where $f=\varphi(\gamma,\xi_1,\dots,\xi_n)$ $φ (γ, ξ_{1}, \dots, ξ_{n})$ . From now on, $\gamma$ is fixed.

Reveal one at a time. Let $f_i=\EE[f\mid\xi_1,\dots,\xi_i]$ $ξ_{1}, \dots, ξ_{i}]$ , that is, the best guess for $f$ once the first $i$ variables are known; in particular $f_0=\EE f$ and $f_n=f$ $f$ . Put $Y_i=f_i-f_{i-1}$ $f_{i - 1}$ . Then $f-\EE f=\sum_{i=1}^nY_i$ $\sum_{i = 1}^{n} Y_{i}$ .
Each step has mean 0. By the tower property, $\EE[f_i\mid\xi_1,\dots,\xi_{i-1}]=f_{i-1}$ $f_{i - 1}$ , so $\EE[Y_i\mid\xi_1,\dots,\xi_{i-1}]=0$ $0$ .
Each step is bounded. Since the variables are independent, $f_i$ is computed as follows: fix the first $i$ variables at their revealed values, and average over the later variables. Regard this as a function of the $i$ -th variable. When the $i$ -th variable takes another value, every term in the average changes by at most $c$ , so the average also changes by at most $c$ . And $f_{i-1}$ is the average of this function over the $i$ -th variable. A function whose values all lie within a range of width at most $c$ is never more than $c$ away from its own average. So $|Y_i|\le c$ $c$ .
Peel off the steps, starting from the last. The differences $Y_1,\dots,Y_{n-1}$ are determined by $\xi_1,\dots,\xi_{n-1}$ , so they can be factored out; to $Y_n$ we apply the conditional version of the tool above: $\begin{aligned}\EE\,e^{t\sum_{i\le n}Y_i}&=\EE\Bigl[e^{t\sum_{i<n}Y_i}\cdot\EE\bigl[e^{tY_n}\bigm|\xi_1,\dots,\xi_{n-1}\bigr]\Bigr]\\[4pt]&\le e^{t^2c^2/2}\cdot\EE\,e^{t\sum_{i<n}Y_i}.\end{aligned}$ Repeating this $n$ times gives $\exp\bigl(\frac{nt^2c^2}2\bigr)$ .

This is a moment-generating-function form of the bounded-differences inequality (McDiarmid), and its proof is the martingale argument of Azuma. The standard version has a better constant, which we do not need here. A sequence of quantities like $Y_1,Y_2,\dots$ , each with mean 0 given everything revealed before it, is called a sequence of martingale differences.

In this example there is an explicit formula for $f_i$ . If the first $i$ dice have shown $s$ different values, then each of the remaining $8-s$ values fails to appear among the last $10-i$ dice with probability $\bigl(\frac78\bigr)^{10-i}$ , so $f_i=(8-s)\bigl(\frac78\bigr)^{10-i}$ $s) (\frac{7}{8})^{10 - i}$ .

The picture matches the proof in two places. Each step can be positive or negative: a new value makes the guess jump down, a repeated value moves it up a little, and the average of the two, weighted by their probabilities, is 0. This is Step 2. (The first die is an exception: it always shows a new value, and this step is exactly 0.) Each step lands inside the light vertical bar. This is Step 3. Run 30 more rounds: the final values are scattered in a modest range on both sides of $\EE f$ .

Step 4: the fluctuation term is unlikely to be very negative

Lemma 2.6 (Fluctuations)Lemma 2.6 of the paper

Fix a coloring, and let $T$ be the fluctuation term of (10). Then, for every $\lambda>0$ $0$ ,

\Pr[\,T\le-\lambda\,]\ \le\ \exp\Bigl(-\frac{\lambda^2M^2}{2hn}\Bigr).\tag{13}

ProofLemma 2.6

Write $T_j=Z_{j+1}-\EE[Z_{j+1}\mid\mathcal F_j]$ for the fluctuation in the transition $j\to j+1$ $1$ , so that $T=T_0+\dots+T_{h-1}$ $T_{h - 1}$ .

One digit. Changing the next digit of one point changes $Z_{j+1}$ by at most $\frac1M$ . This is Section 15.
One transition. The potential $Z_{j+1}$ is a function of the $n$ next digits, and it also depends on the information in $\mathcal F_j$ (the heights and the first $j$ digits of all points). These $n$ digits are independent of each other and of $\mathcal F_j$ . Apply Fact A.1 with $\Gamma$ the information in $\mathcal F_j$ , with $\xi_1,\dots,\xi_n$ the next digits, with $c=\frac1M$ $\frac{1}{M}$ , and with $-t$ in place of $t$ . For every $t>0$ $0$ , $\EE\bigl[e^{-tT_j}\bigm|\mathcal F_j\bigr]\ \le\ \exp\Bigl(\frac{n\,t^2}{2M^2}\Bigr).$
Multiplying over the $h$ transitions. Given $\mathcal F_{h-1}$ , the terms $T_0,\dots,T_{h-2}$ are already determined, so they can be factored out: $\EE\,e^{-tT}=\EE\Bigl[e^{-t(T_0+\dots+T_{h-2})}\cdot\EE\bigl[e^{-tT_{h-1}}\bigm|\mathcal F_{h-1}\bigr]\Bigr]\le\exp\Bigl(\frac{n\,t^2}{2M^2}\Bigr)\cdot\EE\,e^{-t(T_0+\dots+T_{h-2})}.$ Doing the same with $\mathcal F_{h-2}$ , then $\mathcal F_{h-3}$ , and so on down to $\mathcal F_0$ , we get $\EE\,e^{-tT}\le\exp\bigl(\frac{hn\,t^2}{2M^2}\bigr)$ $exp (\frac{hn t ^{2}}{2 M ^{2}})$ .
Markov's inequality, then the choice of $t$ . As in Section 5, the event “ $T\le-\lambda$ $- λ$ ” is the same as “ $e^{-tT}\ge e^{t\lambda}$ $e^{t λ}$ ”, so $\Pr[T\le-\lambda]\le e^{-t\lambda}\cdot\EE\,e^{-tT}\le\exp\Bigl(-t\lambda+\frac{hn\,t^2}{2M^2}\Bigr).$ The exponent is a quadratic function of $t$ . It is smallest at $t=\frac{\lambda M^2}{hn}$ $\frac{λ M ^{2}}{hn}$ , where its value is $-\frac{\lambda^2M^2}{2hn}$ .

This step does not need the transitions to be independent of each other. Conditional on the information available at each transition, the next digits are independent dice, and changing one of them changes $Z_{j+1}$ by at most $\frac1M$ . We apply the conditional exponential-moment bound to this transition and then iterate conditional expectations; each of the $h$ transitions contributes a factor $\exp\bigl(\frac{n\,t^2}{2M^2}\bigr)$ , and this is how the $hn$ and the $M^2$ in the exponent of (13) accumulate.

Pitfall

The argument must not be shortened to “ $T$ is a function of $hn$ digits, each with an effect of at most $\frac1M$ ”. Changing an early digit also changes $Z$ and the conditional expectations at all later transitions, and its effect on $T$ can exceed $\frac1M$ . A small example: $b=3$ $3$ , $h=2$ $2$ , $n=3$ $3$ , so $M=3$ $3$ ; colors $(+1,-1,+1)$ , heights $(\frac1{10},\frac34,\frac{19}{20})$ , horizontal coordinates $(\frac{11}{18},\frac1{18},\frac12)$ . Change the horizontal coordinate of the second point to $\frac{13}{18}$ , that is, change its first digit from 1 to 3 and nothing else. Computing directly from the definitions, $T$ changes from $\frac{14}{81}$ to $-\frac{22}{81}$ , a change of $\frac49>\frac13$ $\frac{1}{3}$ .

So the bound is used one transition at a time: within a transition only the current digits vary, and all earlier digits count as known.

Inequality (13) is a statement about one fixed coloring: $Z_j$ depends on the coloring, and for another coloring $T$ is a different random variable. To handle all $2^n$ colorings, the right-hand side has to be multiplied by $2^n$ , so $\lambda$ must be chosen so that the exponent $\frac{\lambda^2M^2}{2hn}$ is larger than $n\ln2$ . Section 18 does this.

Where the next two sections are going. The number

\delta_*

is defined in Section 17 and is of order

\sqrt{n/M}

. The good event used to lower-bound the conditional gains depends only on the point positions and is handled once for all colorings; the conditional gains themselves may still depend on the coloring. The fluctuation term on the right is handled one coloring at a time, followed by a union bound.

Take $b=8$ and $h=3$ $3$ , so $M=64$ $64$ . Place $n$ points at random, choose a coloring, and compute $Z_0,\dots,Z_3$ . The polyline starts at $Z_0$ and adds the numbers $\delta_j$ one transition at a time; the rise of each segment is the lower bound for the conditional gain of that transition. The last two columns of the table belong to Section 17: the fraction of the points that lie in inner regions that are not heavy in this transition (at least one half means a good transition), and the lower bound $\delta_*$ that a good transition guarantees. The button “Repeat a few dozen times” repeats the experiment and shows how small $Z_h$ can get.

Three things are worth noticing in the picture; all of them are statements about the sample on the screen. First, $Z_j$ rises in every transition, and each increment is far above $\delta_j$ ; the table lets you compare them directly. Keep in mind that $\delta_j$ is a lower bound for a conditional expectation: the increment of a single realization has no such guarantee and can even be negative. Second, if you switch to the coloring that alternates along a Z-shaped curve, $\max|F|$ becomes much smaller and $Z_h$ becomes smaller with it, but in this sample every transition still gains. Third, over a few dozen repetitions the minimum and the mean of $Z_h$ in these samples are of the same order, and no run drops close to 0. This is an observation from finitely many experiments and says nothing about tail probabilities; for a probability as small as $e^{-cn}$ we need (13).

§ 17 · IntermediateNo crowding: heavy regions and good transitions

In (11), the number $\delta_j=\frac1{4bM}\sum_R\sqrt{m_R}$ is about $\frac1{4b}\sqrt{n/M}$ when every inner region holds about $\frac nM$ points. But this is not guaranteed. If the points crowd into a few inner regions, or if many of them fall into the bottom and top old cells of the comparison rectangles, the sum is small; in the extreme case no point lies in an inner region, and $\delta_j=0$ $0$ . This section shows that when $M\le n$ $n$ , except with exponentially small probability, a fraction of this number that depends only on $b$ is retained at every transition. This is step (b) of the plan in Section 16.

Heavy regions and good transitions

A comparison rectangle holds $\frac nM$ points on average. Fix the transition $j\to j+1$ $1$ . For its $M$ comparison rectangles we define:

HeavyAn inner region is heavy if the number

m_R

of points in it is more than

\dfrac{bn}M

, that is, if it holds more than

b

times the average number of points of a comparison rectangle.

GoodThe transition is good if at least

\dfrac n2

points lie in inner regions that are not heavy.

A good transition is one where at least half of the points are spread out well enough. Let $G_j$ be the event that the transition $j\to j+1$ is good, and let $G=G_0\cap\dots\cap G_{h-1}$ be the event that all $h$ transitions are good. These events depend only on the positions of the points, not on the coloring. Put

The lower bound that a good transition guaranteesEq. (12) of the paper

\delta_*=\frac1{8\,b^{3/2}}\sqrt{\frac nM}.\tag{12}

It is $\frac1{2\sqrt b}$ times the “ideal value” $\frac1{4b}\sqrt{n/M}$ .

Lemma 2.5 (Good transitions)Lemma 2.5 of the paper

Let $0\le j<h$ $h$ .

(i) On $G_j$ , we have $\delta_j\ge\delta_*$ $δ_{*}$ .

(ii) If $M\le n$ $n$ , then $\Pr[\,G_j\ \text{fails}\,]\le\bigl(\frac{48}b\bigr)^{n/2}$ $(\frac{48}{b})^{n /2}$ , and hence $\Pr[\,G\ \text{fails}\,]\le h\bigl(\frac{48}b\bigr)^{n/2}$ $h (\frac{48}{b})^{n /2}$ .

Proof(i): on a good transition,

\delta_j\ge\delta_*

In a region that is not heavy, the square root is not too small. For $0<m_R\le bn/M$ , we have $\sqrt{m_R}=m_R/\sqrt{m_R}\ge m_R/\sqrt{bn/M}$ . If $m_R=0$ , the final inequality holds directly, with both sides zero.
Sum. Keep only the regions that are not heavy. On a good transition they hold at least $\frac n2$ points in total: $\sum_R\sqrt{m_R}\ \ge\ \frac1{\sqrt{bn/M}}\sum_{R\ \text{not heavy}}m_R\ \ge\ \frac n2\sqrt{\frac M{bn}}.$
Divide by $4bM$ . $\delta_j\ge\dfrac1{4bM}\cdot\dfrac n2\sqrt{\dfrac M{bn}}=\dfrac1{8\,b^{3/2}}\sqrt{\dfrac nM}=\delta_*$ $δ_{*}$ .

Why discard the heavy regions? The square root is concave: for the same number of points, the sum of the square roots is large when the points are spread over many regions, and small when they crowd into one region. Once a region holds more than $b$ times the average number of points, the additional points contribute almost nothing to $\sum\sqrt{m_R}$ , so we simply do not count them.

The probability that a transition is not good

A boundary strip is the bottom or the top old cell of a comparison rectangle. Every point lies either in an inner region or in a boundary strip.

Proof(ii): if

M\le n

n

, then

\Pr[\,G_j\ \text{fails}\,]\le\bigl(\frac{48}b\bigr)^{n/2}

What “not good” means. If the transition is not good, fewer than $\frac n2$ points lie in inner regions that are not heavy. Every other point lies in a heavy inner region or in a boundary strip. So more than $\frac n2$ points lie in the set $W$ , the union of the boundary strips and all the heavy regions.
There are few heavy regions. No point lies in two inner regions, each heavy region contains more than $\frac{bn}M$ points, and there are only $n$ points in all. So there are fewer than $n\big/\frac{bn}M=\frac Mb$ heavy regions.
$W$ is not a fixed set. Which regions are heavy depends on where the points fall. So we cannot directly compute “the probability that a point falls into $W$ ”. Instead, we list all the possibilities: consider every collection $\mathcal S$ of fewer than $\frac Mb$ inner regions, whether or not its regions are heavy. Let $W_{\mathcal S}$ be the union of the boundary strips and of the regions in $\mathcal S$ , and let $E_{\mathcal S}$ be the event that at least $\frac n2$ points lie in $W_{\mathcal S}$ . Steps 1 and 2 say: if the transition $j\to j+1$ is not good, then $E_{\mathcal S}$ occurs for the collection $\mathcal S$ of all heavy regions. So the event “not good” is contained in the union of the events $E_{\mathcal S}$ .
$W_{\mathcal S}$ is small. Fix $\mathcal S$ . The boundary strips are two of the $b$ old cells of every comparison rectangle, so they cover an area of $\frac2b$ . There are fewer than $\frac Mb$ regions in $\mathcal S$ , each of area less than $\frac1M$ , so they cover an area of less than $\frac1b$ . Hence $W_{\mathcal S}$ is a fixed set of area at most $\frac3b$ .
A given set of points all falls into it. If $E_{\mathcal S}$ occurs, then there is a set of $\lceil\frac n2\rceil$ indices whose points all lie in $W_{\mathcal S}$ . The $n$ points are independent and uniform, so the points of a given set all lie in the fixed set $W_{\mathcal S}$ with probability at most $\bigl(\frac3b\bigr)^{\lceil n/2\rceil}\le\bigl(\frac3b\bigr)^{n/2}$ (since $\frac3b\le1$ $1$ ). There are at most $2^n$ sets of indices, so by the union bound $\Pr[E_{\mathcal S}]\le2^n\bigl(\frac3b\bigr)^{n/2}$ $2^{n} (\frac{3}{b})^{n /2}$ .
A union bound over $\mathcal S$ . There are $M$ inner regions in all, so there are at most $2^M$ choices of $\mathcal S$ : $\Pr[\,G_j\ \text{fails}\,]\ \le\ 2^{M+n}\Bigl(\frac3b\Bigr)^{n/2}\ \le\ 4^n\Bigl(\frac3b\Bigr)^{n/2}=\Bigl(\frac{48}b\Bigr)^{n/2}.$ The middle step uses $M\le n$ $n$ . One more union bound, over the $h$ transitions, gives the bound on $\Pr[\,G\ \text{fails}\,]$ .

Steps 1 to 4 of the proof. The gray and the red parts together have area at most

\frac3b

; if the transition is not good, more than half of the points must lie in these two parts. Which regions are red is not known in advance, so Step 6 takes a union bound over all possible choices.

Take $b=64$ $64$ ; one transition then has $M=4096$ comparison rectangles. Each small square in the left panel stands for one inner region: the darker the color, the more points, and red means heavy. The bar on the right splits the $n$ points into three parts: those in inner regions that are not heavy, those in heavy inner regions, and those in boundary strips. The transition is good once the teal segment passes one half. With uniform random points, the default sample is a good transition; in general, Lemma 2.5 guarantees a good transition only with very high probability. Use the sliders to force a share of the points into 16 regions, or into the boundary strips, and see how far you have to go before the transition is no longer good.

Try the three presets. In the sample of uniform random points there are no heavy regions, and about $97\%$ of the points lie in inner regions that are not heavy. Force 40% of the points into 16 regions: these 16 regions all turn red, but the remaining points are still more than half, so the transition is still good, and $\delta_j$ is still at least $\delta_*$ . Once the forced share passes about one half, the transition is no longer good; the third preset uses 60%. For random points to end up like this by themselves, the probability is at most the last readout, which is about $2^{-850}$ for $b=64$ and $n=M$ $M$ .

Three points are worth pausing over. First, what is random here is the positions of the points, and whether a transition is good depends only on the positions. So $G$ is the same event for all $2^n$ colorings, and it has to be ruled out only once. Second, the condition $M\le n$ is used in Step 6: there are $2^M$ choices of $\mathcal S$ , and for $\bigl(\frac3b\bigr)^{n/2}$ to outweigh them, $M$ must not be larger than $n$ . Third, the inner regions have different shapes at different transitions, and the events that the individual transitions are good are not independent; the proof only takes a union bound over the $h$ transitions and does not need independence.

§ 18 · Core argumentFinishing the proof: Theorem 1.1

Theorem 1.1 is stated in Section 8.

Putting the three steps together: Proposition 2.7

Steps (a), (b) and (c) of the plan in Section 16 are now all in place. For a coloring $\chi$ , consider two events:

Event 1

G

fails: some transition is not good. This depends only on the positions of the points, not on the coloring. When

M\le n

n

, its probability is at most

h\bigl(\frac{48}b\bigr)^{n/2}

(Lemma 2.5).

Event 2The fluctuation term of the coloring

\chi

satisfies

T\le-\lambda

- λ

, where

\lambda=\frac14h\delta_*

\frac{1}{4} h δ_{*}

. This depends on the coloring. Its probability is bounded by Lemma 2.6.

Proposition 2.7 (Simultaneous probability bound)Proposition 2.7 of the paper

If $M\le n$ $n$ , then

\Pr\Bigl[\,\text{there is}\ \chi\ \text{with}\ \norm{F_\chi}_\infty\le\frac h{64\,b^{3/2}}\sqrt{\frac nM}\,\Bigr]\ \le\ h\Bigl(\frac{48}b\Bigr)^{n/2}+2^n\exp\Bigl(-\frac{hM}{2048\,b^3}\Bigr).\tag{14}

ProofProposition 2.7

The threshold on the left is exactly $\frac18h\delta_*$ . Fix a coloring, and suppose that $G$ holds and $\norm F_\infty\le\frac18h\delta_*$ $\frac{1}{8} h δ_{*}$ .

The sum of the conditional gains. On $G$ , the conditional gain of every transition is at least $\delta_j$ (Lemma 2.4), and $\delta_j\ge\delta_*$ (Lemma 2.5 (i)). So (10) and $Z_0\ge0$ give $Z_h\ \ge\ h\,\delta_*+T.$
A small $F$ forces Event 2. By (9), $Z_h\le2\norm F_\infty\le\frac14h\delta_*$ $\frac{1}{4} h δ_{*}$ . Together with Step 1 this gives $T\le-\frac34h\delta_*$ $- \frac{3}{4} h δ_{*}$ , and in particular $T\le-\lambda$ for $\lambda=\frac14h\delta_*$ $\frac{1}{4} h δ_{*}$ . The paper uses only the latter; the constants are not optimized.
The probability of Event 2. By (12), $\delta_*^2=\frac n{64\,b^3M}$ $\frac{n}{64 b ^{3} M}$ . With this $\lambda$ , the exponent in (13) is $\frac{\lambda^2M^2}{2hn}=\frac{h\,\delta_*^2M^2}{32\,n}=\frac{hM}{2048\,b^3}.$ Therefore $\Pr\bigl[\,G\ \text{holds and}\ \norm F_\infty\le\frac18h\delta_*\,\bigr]\le\exp\bigl(-\frac{hM}{2048b^3}\bigr)$ $exp (- \frac{h M}{2048 b ^{3}})$ .
Union bound. If there is a coloring with $\norm{F_\chi}_\infty\le\frac18h\delta_*$ $\frac{1}{8} h δ_{*}$ , then either $G$ fails, or $G$ holds and $F_\chi$ is small for this coloring. There is only one event of the first kind. There is one event of the second kind for each coloring, $2^n$ in all: $\Pr\bigl[\exists\chi:\ \norm{F_\chi}_\infty\le\tfrac18h\delta_*\bigr]\le\Pr[\,G\ \text{fails}\,]+\sum_\chi\Pr\bigl[\,G\ \text{holds and}\ \norm{F_\chi}_\infty\le\tfrac18h\delta_*\bigr].$ Now insert Lemma 2.5 (ii) and Step 3.

Of the two terms on the right, only the second is multiplied by $2^n$ . Event 1 is shared by all colorings, so it is enough to rule it out once.

Choice of parameters

It remains to choose $b$ and $h$ . The goal is to make the right-hand side of (14) at most $e^{-An}$ , while keeping the threshold on the left at least $c_A(\log_2n)^{3/2}$ . Given $A>0$ $0$ , choose an integer $b$ so large that the following two conditions hold ( $\ln$ is the natural logarithm; the paper writes $\log$ ):

\frac12\ln\frac b{48}\ \ge\ A+2,\qquad\frac b{4096}\ \ge\ A+2+\ln2.\tag{15}

Such a $b$ depends only on $A$ , and $b>48$ $48$ , so that $64\le b^4$ $b^{4}$ . Next set

c_A=\frac{b^{-8}}{(1+\log_2b)^{3/2}}.

For every $n\ge1$ $1$ , let $h$ be the largest positive integer with $b^{-5}h\,b^{h-1}\le n$ $n$ , and set $M=b^{h-1}$ $b^{h - 1}$ . For $h=1$ the left-hand side is $b^{-5}\le1$ $1$ , and it tends to infinity with $h$ , so such an $h$ exists.

Relations between the parametersEqs. (16)–(18) of the paper

b^{-5}hM\ \le\ n\ <\ 2\,b^{-4}hM,\tag{16}

\log_2n\ <\ (1+\log_2b)\,h,\tag{17}

c_A(\log_2n)^{3/2}\ <\ b^{-8}h^{3/2}.\tag{18}

Proof(16), (17) and (18)

The left inequality in (16) is the definition of $h$ . Since $h$ is the largest such integer, $h+1$ does not satisfy the condition: $n<b^{-5}(h+1)b^h$ $1) b^{h}$ . With $h+1\le2h$ and $b^h=bM$ this gives $n<2h\,b^{-4}M$ $2 h b^{- 4} M$ , which is the right inequality in (16). With $h+1\le2^h$ and $b^{-5}\le1$ the same inequality gives $n<(2b)^h$ $(2 b)^{h}$ , and taking logarithms to base 2 gives (17). Raising both sides of (17) to the power $\frac32$ and multiplying by $c_A$ gives (18).

Inequality (16) says that the average number $\frac nM$ of points of a comparison rectangle lies between $b^{-5}h$ and $2b^{-4}h$ , so it is of order $h$ . Inequality (17) says that $h>\frac{\log_2n}{1+\log_2b}$ $\frac{l o g _{2} n}{1 + l o g _{2} b}$ , so $h$ is at least of order $\log n$ . Conversely, $h$ cannot be larger than that, because its definition requires $b^{-5}h\,b^{h-1}\le n$ $n$ .

Why $b^{-5}$ ? The lower bound in (16) makes the threshold in (14) at least $\frac{h^{3/2}}{64b^4}$ . The upper bound makes the last exponent in (14) more than $\frac{bn}{4096}$ , which outweighs $2^n$ when $b$ is large enough. With $b^{-4}$ instead, this exponent would only be guaranteed to be more than $\frac n{4096}$ , which is not enough against the $2^n$ colorings.

Why is the density $\frac nM$ taken to be of order $h$ ? With a larger density, every $\delta_j$ would be larger. But when $\lambda$ is of the order of the total gain, the exponent in (13) is of order $hM$ (for fixed $b$ ), whatever the density is, and it must exceed $n\ln2$ . So $n$ is at most of order $hM$ , and the density is at most of order $h$ .

Proof of Theorem 1.1

ProofTwo cases

Case 1: $M>n$ $n$ . Proposition 2.7 needs $M\le n$ $n$ , so this case has to be treated separately. By (16), $b^{-5}hM\le n<M$ $M$ , so $h<b^5$ $b^{5}$ ; by (18), $c_A(\log_2n)^{3/2}<b^{-8}\cdot b^{15/2}<1$ $1$ . So it suffices to find an anchored rectangle that has imbalance 1 under every coloring. Almost surely all heights are distinct, so the lowest point is unique. The anchored rectangle $[0,1]\times[0,\min_iV_i]$ contains just this point, and its signed count is $\pm1$ . In this case the claim of the theorem holds with probability 1.
Case 2: $M\le n$ $n$ . The first term on the right-hand side of (14). Now $h\le2^{h-1}\le M\le n$ $n$ . By the first condition in (15), $\bigl(\frac{48}b\bigr)^{n/2}=\exp\bigl(-\frac n2\ln\frac b{48}\bigr)\le e^{-(A+2)n}$ $e^{- (A + 2) n}$ , so the first term is at most $n\,e^{-(A+2)n}$ .
The second term. By (16), $hM>\frac12nb^4$ $\frac{1}{2} n b^{4}$ , so $\frac{hM}{2048\,b^3}>\frac{bn}{4096}\ge(A+2+\ln2)\,n$ $ln 2) n$ , where the last step is the second condition in (15). Hence $2^n\exp\bigl(-\frac{hM}{2048b^3}\bigr)\le e^{n\ln2}\cdot e^{-(A+2+\ln2)n}=e^{-(A+2)n}$ $e^{- (A + 2) n}$ .
Adding the two terms. The right-hand side of (14) is at most $(n+1)\,e^{-(A+2)n}=(n+1)e^{-2n}\cdot e^{-An}\le e^{-An}$ $e^{- A n}$ , since $n+1\le e^{2n}$ $e^{2 n}$ .
Converting to $\log n$ . Outside this exceptional event, every coloring satisfies $\norm{F_\chi}_\infty>\frac h{64\,b^{3/2}}\sqrt{\frac nM}\ \ge\ \frac h{64\,b^{3/2}}\sqrt{\frac h{b^5}}=\frac{h^{3/2}}{64\,b^4}\ \ge\ b^{-8}h^{3/2}\ >\ c_A(\log_2n)^{3/2}.$ The steps use, in this order, $\frac nM\ge\frac h{b^5}$ from (16), then $64\le b^4$ $b^{4}$ , and finally (18).

Step 5 is where the exponent $\frac32$ finally appears: the threshold is $h\cdot\sqrt{n/M}$ $n / M$ , and $\frac nM$ is at least a constant multiple of $h$ , so the threshold is of order $h^{3/2}$ . Step 4 explains why (15) has $A+2$ and not $A$ : the extra $e^{-2n}$ absorbs the factor $n+1$ $1$ , which comes from the factor $h\le n$ in front of the first term and from the second term.

Write every factor on the right-hand side of (14) in the form $e^{(\,\cdot\,)n}$ and look only at the number in the parentheses. Each of the two events has its own ledger. The two cost lines of Event 1 come from the proof of Lemma 2.5: the $2^M\le2^n$ choices of $\mathcal S$ , and the $2^n$ choices of the set of indices. Event 2 needs a union bound over the $2^n$ colorings, hence a line $\ln2$ . When both subtotals are at most $-(A+2)$ $2)$ , Steps 2 to 4 of the proof go through. The factor $h$ in front of the first term is not exponential and is not entered in the ledger. To make the slider convenient, we take $b=2^L$ here; the paper only requires $b$ to be an integer.

Each ledger has costs and payoffs. The payoff of Event 1 is $\frac12\ln\frac b3$ , which grows only logarithmically with $b$ ; the payoff of Event 2 is $\frac b{4096}$ , which grows linearly with $b$ but starts late. For small $A$ , Event 2 is the binding one: for $A=0.5$ it requires $b\ge13080$ $13080$ , whereas Event 1 only requires $b\ge7124$ $7124$ . For large $A$ it is the other way round and Event 1 is the binding one, because the logarithm grows slowly. Both subtotals become arbitrarily negative as $b$ grows. This is why $A$ can be arbitrarily large in the theorem: the smaller the failure probability we want, the larger we take the base $b$ .

The horizontal axis is the number of points, with $\log_2n$ on a logarithmic scale. The vertical axis is the average number $\frac nM$ of points of a comparison rectangle. The band is the range $b^{-5}h\le\frac nM<2b^{-4}h$ given by (16), and the dot is the current $n$ . A dot below the horizontal line $\frac nM=1$ is in the case $M>n$ $n$ ; a dot above it is in the case $M\le n$ $n$ . To make the picture fit, we take $b=2^L$ here, with $L$ only from 4 to 8.

Drag the number of points to see that $h$ is about $\frac{\log_2n}{\log_2b}$ and grows very slowly with $n$ . The ratio $\frac nM$ itself is a sawtooth: it rises with $n$ , and each time $h$ increases by 1 it drops to $\frac1b$ of its value. But it always stays inside the band, and the band moves up slowly with $h$ . For the band to cross 1, $h$ has to reach the order of $\frac12b^4$ to $b^5$ . The last readout shows the expression $b^{-8}h^{3/2}$ ; it exceeds 1 even later. The displayed bases b = 16,…,256 do not satisfy (15), so this is a scale illustration, not a probability guarantee. The theorem requires $b$ above ten thousand. The picture then has the same shape as here, only with a much longer horizontal axis; the note “On the constants” below gives the actual numbers.

This completes the proof of Theorem 1.1. The random point set satisfies the conclusion with positive probability, and its points are almost surely distinct, so there is an $n$ -point set for which every coloring leaves an anchored rectangle with imbalance at least $c_A(\log_2n)^{3/2}$ . Together with Nikolov's upper bound:

\Delta_2(n)=\Theta(\log^{3/2}n).

On the constants

The constant that the proof gives is very small. Take the failure probability $2^{-n/2}$ as an example, that is, $A=\frac12\ln2$ $\frac{1}{2} ln 2$ : the smallest integer that satisfies (15) is $b=12451$ $12451$ , and then $c_A\approx2^{-114.6}$ $2^{- 114.6}$ . For the lower bound $c_A(\log_2n)^{3/2}$ to exceed 1, $\log_2n$ must be larger than $c_A^{-2/3}\approx2^{76.4}$ $2^{76.4}$ . Before that, the bound of the theorem is below 1, which is weaker than the trivial fact that the imbalance is at least 1.

This is common for asymptotic results: the theorem determines the order of growth, not specific values. The paper says so right after the theorem: it does not optimize $c_A$ , which is very small, so the bound is of interest only for large $n$ .

Part V · Sections 19–22

Looking back

The proof is complete. This part first goes through the accounting for the exponent $\frac32$ once more, then answers the three questions from the beginning, and then looks at what is still open. At the end come the dependency map, the table of notation and the references.

§ 19 · IntermediateThe accounting for $\frac32$

Three numbers are at work in the proof:

h

The number of transitions, that is, of passages from one stage to the next. By (17), it is of order

\log n

\delta_*\asymp\sqrt{n/M}

At every good transition, the conditional gain of

Z

is at least

\delta_*=\frac1{8b^{3/2}}\sqrt{n/M}

\frac{1}{8 b ^{3/2}} n / M

. Here

\frac nM

is the average number of points of a comparison rectangle.

\frac nM\asymp h

The choice of parameters, (16). So every good transition gains an amount of order

\sqrt h

, and all

h

transitions are good, for a total of

h\cdot\sqrt h=h^{3/2}

h^{3/2}

\norm{F_\chi}_\infty\ >\ \frac{h\,\delta_*}8=\frac h{64\,b^{3/2}}\sqrt{\frac nM}\ \asymp\ h^{3/2}\ \asymp\ (\log n)^{3/2}.

The 8 in $\frac{h\delta_*}8$ arises as follows. If $\norm{F_\chi}_\infty$ is at most this number, then $Z_h\le2\norm{F_\chi}_\infty\le\frac{h\delta_*}4$ $\frac{h δ _{*}}{4}$ , which falls short of the sum $h\delta_*$ of the conditional gains by $\frac34h\delta_*$ , and only the fluctuation term can make up this difference. The paper uses only $\frac14h\delta_*$ of it; the constants are not optimized.

Why $\frac nM$ cannot be larger

The gain per transition is $\sqrt{n/M}$ , so it seems that the larger $\frac nM$ , the better. The restriction comes from the union bound. With $\lambda=\frac{h\delta_*}4$ in (13), the exponent is $\frac{hM}{2048b^3}$ ; to beat the $2^n$ colorings, it must exceed $n\ln2$ . So $hM$ must be at least a constant multiple of $b^3$ times $n$ , that is,

\frac nM\ \lesssim\ \frac h{b^3}.

The choice $\frac nM<\frac{2h}{b^4}$ of Section 18 lies in this range, with a factor $b$ to spare, which is used to push the failure probability down to $e^{-An}$ . The introduction of the paper puts it this way: a denser choice would increase the gain of each transition; but for a deviation of the order of the total gain, the fluctuation bound has an exponent of order $hM$ , whatever the density is, and this exponent must exceed $n\ln2$ . So a density $\frac nM$ of order $h$ is already the largest that the argument allows.

The intuition in one sentence

Each transition has $M$ comparison rectangles, so the $h$ transitions have $hM$ in total. For a fixed coloring, $Z_h$ can be abnormally small only if the random sums in most comparison rectangles happen to cancel. If these $hM$ rectangles are treated as independent, each with a constant probability of such a cancellation, the probability is about $e^{-c\,hM}$ altogether. There are $2^n$ colorings to choose from, and the union bound needs $2^n\cdot e^{-c\,hM}$ to be small. So we need $hM\gtrsim n$ $n$ , that is, $\frac nM\lesssim h$ $h$ .

This is only a heuristic for the scale: the comparison rectangles and the transitions are not independent. The proof uses the conditional exponential-moment bound of Section 16, iterated over the transitions, that is, inequality (13): when $\lambda$ is of the order of the total gain, the exponent on its right-hand side is exactly a constant multiple of $hM$ .

Compare this with continuous discrepancy. For the binary net of Section 6, every dyadic strip has error at most 1, and the $\log n$ levels add up to $\log n$ . Here the gain of each transition is of order $\sqrt{\log n}$ , and the total is $\log^{3/2}n$ . The factor $\sqrt{\log n}$ between the two problems is this extra square root at each level.

Comparing with the guess of Section 9

Section 9 guessed the scale from the small-ball estimate for the Brownian sheet. Now we translate the parameters of the proof into that language. The scale of the discrepancy is $t\asymp h\sqrt{n/M}$ $h n / M$ , and the corresponding small-ball radius is $\varepsilon=t/\sqrt n\asymp h/\sqrt M$ $h / M$ .

Small-ball estimate	The proof here
radius $\varepsilon$	$h/\sqrt M$
$\log(1/\varepsilon)$	$\frac12\log M-\log h$ $lo g h$ , which is of order $h$ ( $b$ is a constant)
exponent $\varepsilon^{-2}\log^3(1/\varepsilon)$	$\frac M{h^2}\cdot h^3=hM\asymp n$

The last row says that, with these parameters, the exponent of the small-ball probability is exactly of order $n$ , which is just enough to pay for the union bound over the $2^n$ colorings. Both sides use the same “cube”: $n\asymp\varepsilon^{-2}h^3$ $ε^{- 2} h^{3}$ . The proof does not use the Brownian sheet, but it lands on the scale that the Brownian sheet predicts. Section 3 of the paper carries out the calculation of Section 9; substituting the parameters of the proof back into it, as done here, is an addition of this guide.

§ 20 · BasicsWhy earlier methods fell short, and why it works now

Why earlier methods fell short

Borrowing from continuous discrepancy. Transference can only carry over the lower bound for continuous discrepancy, and continuous discrepancy is exactly $\Theta(\log n)$ . By itself this road ends at $\log n$ .
The orthogonal-function method. In the classical argument presented in Section 7, the gain of the test function accumulates scale by scale: there are $\log n$ levels, and each contributes a constant.
Factorization norms. The two general inequalities between $\gamma_2$ and discrepancy each lose a logarithmic factor, and in the plane the lower-bound side lands exactly on $\log n$ .

These specific arguments do not give the paper's uniform lower bound for random point sets. The combinatorial-discrepancy application of the orthogonal-function method presented here concerns binary nets; the other two routes produce bad point sets among the subsets of a grid. A binary net itself can be colored with discrepancy $O(\log n)$ (see Section 7), so nothing more can be proved on it.

Why it works now

New pointsThe points are placed at random. A point set such as a binary net can keep the errors at all scales small simultaneously. For random points, every digit is a freshly rolled die, and every scale brings new fluctuations.

New questionFix one coloring at a time, estimate the probability that it is “good”, and then take a union bound over the

2^n

colorings. This needs a probability as small as

e^{-cn}

, with

c

large enough.

New quantityInstead of looking at the maximum of

F

directly, use the local oscillation potential

Z_j

. On a good transition, its conditional expected gain is at least

\delta_*=(8b^{3/2})^{-1}\sqrt{n/M}

. With the revealed information fixed, changing one point’s next horizontal digit changes

Z_{j+1}

by at most

1/M

Elementary probabilityCauchy–Schwarz (the paper uses Hölder), the bounded-differences inequality, Markov's inequality and the union bound. Throughout, only maxima and minima of step functions and conditional averages are used. The abstract of the paper calls the proof “surprisingly simple and elementary”.

	Earlier methods	The paper
Point set	a binary net, or a subset of some grid	random points
How all $2^n$ colorings are handled	a certificate for each coloring (test function, factorization norm)	for each coloring, estimate the probability that it is “good”; then take a union bound
Key estimate needed	inner products with the test function, the factorization norm of a matrix	the average gain of the potential, and the effect of a single point
Contribution of each scale	a constant, $\log n$ in total	$\sqrt{\log n}$ , $\log^{3/2}n$ in total

The connections with the earlier methods are also worth mentioning. The family of rectangles that become “narrower horizontally and taller vertically, with the same area” is exactly the family used in the orthogonal-function method of Roth and Halász. In its discussion of related work, the paper also points out a connection with Talagrand's proof of the small-ball estimate for the Brownian sheet. Talagrand's proof contains a deterministic recursion that averages in one coordinate and selects representative points in the other, and the local comparison of the paper uses the same pair of opposing scales. Averaging the child functions preserves the old function in expectation, and the independent symmetric jumps that come from the points of the inner region supply the gain. The endpoint average $a_I$ , in turn, is the conditional-expectation version of Talagrand's horizontal average (end of Section 13).

The paper's four steps and this guide

The introduction of the paper summarizes the proof in four steps. Part IV presents exactly these four steps, in a slightly different order: here “the effect of one digit” is moved forward to Section 15, and the good transitions come after the fluctuations.

Step in the paper	Content	In the paper	This guide
(1) Potential	revealing the horizontal coordinates digit by digit; endpoint average, oscillation, $Z_j$ ; $Z_j\le2\norm F_\infty$	Eqs. (1)–(3), (9)	§ 10–§ 12
(2) Local gain	in one comparison rectangle, the oscillations on the vertical strips add up, on average, to at least $\frac14\sqrt{m_R}$ more than those on the horizontal strips; sum over all comparison rectangles	Lemma 2.1, Fact 2.2, Lemma 2.3, Lemma 2.4	§ 13, § 14, § 16
(3) Good transitions	heavy inner regions, good transitions; when $M\le n$ $n$ , every transition is good, except with exponentially small probability, and this does not depend on the coloring	Lemma 2.5	§ 17
(4) All colorings	one digit changes $Z_{j+1}$ by at most $\frac1M$ ; bounded differences control the fluctuation term; union bound over the $2^n$ colorings; choice of parameters	Lemma 2.6, Fact A.1, Proposition 2.7, Section 2.5 (Parameters)	§ 15, § 16, § 18

List of techniques

Technique	What it does	Where
Random points, union bound over the colorings	reduces “every coloring is bad” to a probability estimate for one fixed coloring	§ 8
Revealing the horizontal coordinates digit by digit	each transition releases only $n$ independent dice	§ 10
Endpoint average $a_I$ (Eq. (2))	after refinement, the average of the child functions returns to the old function in expectation	§ 12, § 14
Potential $Z_j$ , the local oscillation (Eq. (1))	shift invariant: for each affected horizontal interval, only the block containing the point’s height can change oscillation	§ 12, § 15
Vertical comparison (Lemma 2.1, Eq. (4))	the oscillation on $J$ sees the offset between the bottom and the top block; the oscillation on a single block does not	§ 13
Average first, then compare (Eqs. (5), (6))	merges the $b$ child functions into one average $\bar a$ , which equals the old function plus the jumps of the points	§ 13
A sum of symmetric jumps is not close to any fixed point (Fact 2.2)	the sum $D$ of the jumps of the points of the inner region, plus any fixed offset, has expected absolute value at least $\frac18\sqrt{m_R}$	§ 14
Conditional gain plus fluctuation term (Eq. (10), Lemma 2.4)	writes $Z_h$ as its initial value, the sum of the conditional gains, and a fluctuation term with mean 0; the conditional gains have a common lower bound that does not depend on the coloring	§ 16
Bounded differences (Fact A.1, Lemma 2.6)	the fluctuation term is unlikely to be very negative; no independence between the transitions is needed	§ 15, § 16
Heavy inner regions and good transitions (Lemma 2.5)	with high probability, all transitions are good when M ≤ n; this event is common to all colorings	§ 17

§ 21 · BasicsConstants, formalization and open problems

Explicit bad point sets

The proof is probabilistic: it shows that almost all random point sets are bad, but it cannot point to a specific one. Is there an explicit family of point sets with discrepancy $\Omega(\log^{3/2}n)$ ? The paper names the main issue: how to retain the oscillation gained across many scales when the independent random digits are replaced by a deterministic choice.

Higher dimensions

For boxes in dimension $d\ge3$ $3$ , it is known that $\Omega_d(\log^{d-1}n)\le\Delta_d(n)\le O_d(\log^{d-1/2}n)$ $O_{d} (lo g^{d - 1/2} n)$ ; the gap is again $\sqrt{\log n}$ . (The $\log^{d+1/2}n$ of Section 7 is a weaker upper bound given by the factorization-norm method; Nikolov later improved it to $\log^{d-1/2}n$ .) Bansal conjectured that the answer in $d$ dimensions is $O(\log^{d-1}n)$ ; the theorem of the paper shows that this fails for $d=2$ $2$ .

Which side is right in higher dimensions? Carry the calculation of Section 9 over to dimension $d$ : the Brownian-sheet small-ball conjecture predicts the exponent $\varepsilon^{-2}\log^{2d-1}(1/\varepsilon)$ , and balancing it against $n\ln2$ gives $\log^{d-1/2}n$ , which matches the known upper bound. The paper also stresses that this heuristic calculation does not transfer the conclusion to finite point sets. As for the proof, the argument of the paper uses two opposing resolutions, horizontal and vertical: when one coordinate is refined, the influence of a point is confined to a single vertical block (Section 15). An extension to higher dimensions needs an analogous local comparison when several coordinates are refined or coarsened at once.

Constants

As computed at the end of Section 18, the constant $c_A$ given by the proof is extremely small: for $A=\frac12\ln2$ we get $b=12451$ and $c_A\approx2^{-114.6}$ $2^{- 114.6}$ , so the statement has real content only for astronomically large $n$ . The paper says explicitly that it does not optimize $c_A$ .

Formalization and AI

The paper ends with an “AI methodology statement”. In brief: the author has been thinking about this problem since 2013; from July 2026 on, the author worked on it interactively with GPT and Claude, which first led to a proof based on a “killed suffix walk” and then to its simplification, the local-oscillation proof in Section 2 and the appendix of the paper; the same tools, together with Xean, were used to check the proof and to prepare the manuscript; there is a Lean formalization of the main lower-bound theorem, produced with GPT according to the paper; and the author verified the correctness and originality of all content. The code of the formalization is at github.com/wzskytop/tusnady-lean; for the tools used and the record of checks, the current description in that repository is authoritative. The paper is at arXiv:2610.08130.

The scope of the formalization should be kept clear. It covers the new lower bound of the paper: Theorem 1.1 for random points, and the deterministic lower bound that follows from it. The cited upper bound, the resulting statement $\Theta(\log^{3/2}n)$ , the historical account, and the explanations and interactive figures added by this guide are outside its scope.

The repository's paper-to-code correspondence table maps the theorems and lemmas to their Lean declarations.

This guide adds derivations, examples and interactive figures. They are no substitute for formal verification, nor for independent review.

Other directions

In its discussion of related work, the paper mentions two directions. The first is online discrepancy: for points that arrive at random, earlier work studied online algorithms for intervals, stripes and Tusnády's problem. For uniform random arrivals in $[0,1]^d$ , it is known that every online algorithm incurs discrepancy $\Omega_d(\log^{d/2}T)$ within the first $T$ arrivals, with constant probability (Bansal, Jiang, Singla and Sinha). Theorem 1.1 holds for every coloring, online or offline, so in the plane it raises this bound from $\log T$ to $\log^{3/2}T$ . The second is data structures: discrepancy is related to lower bounds for range searching and approximate range counting, and the hard instances of the paper are random, so they may be useful for average-case lower bounds.

§ 22 · AppendixDependency map, notation and references

Dependencies in the proof

Notation

Symbol	Meaning	First appears
$P,\ n$	the point set and the number of points	§ 1
$\chi$	a coloring, with values $\pm1$ ; $\chi(P\cap R)$ is the sum of the colors in $R$	§ 3
$\disc(P),\ \Delta_2(n)$	the discrepancy of a point set; the worst-case discrepancy of $n$ points	§ 3
$D(P),\ D(n)$	continuous discrepancy	§ 6
$P_i=(U_i,V_i)$	the horizontal and the vertical coordinate of the $i$ -th random point	§ 8
$F_\chi(x,y),\ \norm{F_\chi}_\infty$	the signed count of the points in the anchored rectangle $[0,x]\times[0,y]$ $[0, y]$ ; its maximum absolute value. Written $F$ from Section 11 on	§ 8
$A,\ c_A$	the exponent in the failure probability $e^{-An}$ ; the constant in Theorem 1.1	§ 8
$W,\ \varepsilon$	the Brownian sheet; the radius of the small ball	§ 9
$b,\ L$	the base, an integer, $b\ge3$ $3$ ; it is chosen very large in the proof of the theorem (see (15)). In the interactive figure of Section 18 it is a power of 2, $b=2^L$	§ 10, § 18
$\mathcal F_j$	the information at stage $j$ : all vertical coordinates and the first $j$ digits of every horizontal coordinate	§ 10
$h,\ M$	the number of transitions: the stages are numbered $j=0,\dots,h$ $0, \dots, h$ , so there are $h$ transitions, and the passage from stage $j$ to stage $j+1$ is the transition $j\to j+1$ $1$ ; $M=b^{h-1}$ is the number of comparison rectangles in each transition	§ 11
$I,\ B$	a horizontal interval (of width $b^{-j}$ ) and a vertical block (of height $b^{j-h}$ ) of stage $j$ ; $I\times B$ is a cell	§ 11
$C_k,\ J,\ R$	the $k$ -th child of $I$ ; a new block, the union of $b$ old blocks $B_1,\dots,B_b$ ; the comparison rectangle $I\times J$	§ 11
$a_I(y),\ w_I(u)$	the endpoint average, the mean of the two values of $F$ at the endpoints of $I=[s,t]$ $[s, t]$ , Eq. (2); the paper writes $a^{(I)}$ . A point with horizontal coordinate $u$ enters it with the weight $w_I(u)$ , which is one of $1,\frac12,0$	§ 12
$\operatorname{osc}_B\,f,\ \operatorname{mid}_B\,f$	oscillation: the maximum of $f$ on $B$ minus its minimum; midpoint: the average of the maximum and the minimum. Eq. (3)	§ 12
$Z_j$	the potential (the local oscillation): the average of the oscillations of $a_I$ over the cells of stage $j$ , Eq. (1)	§ 12
$R^{\mathrm{in}},\ m_R$	the inner region $I\times(B_2\cup\dots\cup B_{b-1})$ of $R$ ; the number of points in it	§ 13
$a,\ a_k,\ \bar a$	shorthand while $I$ is fixed: the old function $a=a_I$ $a_{I}$ ; the child functions $a_k=a_{C_k}$ $a_{C_{k}}$ ; their average $\bar a=\frac1b\sum_ka_k$	§ 13
offset	$\operatorname{mid}_{B_b}f-\operatorname{mid}_{B_1}f$ $mid_{B_{1}} f$ : the top block against the bottom block	§ 13
$r,\ X_i$	the outcome of the die (the point falls into $C_r$ ); the jump $\chi_i\frac{b+1-2r}{2b}$ of this point	§ 13
$D,\ g,\ \theta$	the sum of the jumps of the points of the inner region; the function $\bar a$ without these jumps; the offset of $g$ itself	§ 14
$\sigma^2$	the second moment $\frac{b^2-1}{12b^2}$ of one jump	§ 14
conditional gain	$\EE[Z_{j+1}-Z_j\mid\mathcal F_j]$ $F_{j}]$ : the average increment in the transition $j\to j+1$	§ 16
$T,\ T_j$	the fluctuation term $\sum_j\bigl(Z_{j+1}-\EE[Z_{j+1}\mid\mathcal F_j]\bigr)$ $F_{j}])$ , Eq. (10); its term for the transition $j\to j+1$	§ 16
$\delta_j$	the lower bound $\frac1{4bM}\sum_R\sqrt{m_R}$ for the conditional gain of the transition $j\to j+1$ $1$ , Eq. (11)	§ 16
$\Gamma,\ \xi_i,\ \varphi,\ c,\ t$	in Fact A.1: the given information, the independent variables, the function, the bound on the effect of a single variable, and the parameter in the exponent	§ 16
$\lambda$	the size of the deviation in Lemma 2.6; Proposition 2.7 takes $\frac14h\delta_*$	§ 16, § 18
heavy, good transition	an inner region is heavy if $m_R>\frac{bn}M$ $\frac{bn}{M}$ ; a transition is good if at least $\frac n2$ points lie in inner regions that are not heavy	§ 17
$G_j,\ G$	the transition $j\to j+1$ is good; all $h$ transitions are good	§ 17
$\delta_*$	the lower bound $\frac1{8b^{3/2}}\sqrt{n/M}$ that a good transition guarantees, Eq. (12)	§ 17
boundary strips, $\mathcal S,\ W_{\mathcal S},\ E_{\mathcal S}$	the bottom and the top old cell of every comparison rectangle; a collection of fewer than $\frac Mb$ inner regions; the union of this collection and the boundary strips; the event “at least half of the points lie in $W_{\mathcal S}$ ”. In Section 17, $W$ without a subscript is the union of the boundary strips and all heavy regions; it has nothing to do with the Brownian sheet of Section 9	§ 17

References

The bibliographic details below are taken from the reference list of version r65 of the paper. The two entries marked “Background” were added by this guide.

Z. Wei. Tight Bounds for Tusnády's Problem in the Plane. arXiv:2610.08130. The paper that this guide explains; the guide follows the manuscript version r65, whose TeX source was checked on 2026-10-07 and is byte-for-byte identical to the arXiv v1 TeX source.
C. Aistleitner, D. Bilyk, and A. Nikolov. Tusnády's problem, the transference principle, and non-uniform QMC sampling. MCQMC 2016 (Springer, 2018).
K. Azuma. Weighted sums of certain dependent random variables. Tôhoku Mathematical Journal 19(3), 1967.
W. Banaszczyk. On series of signed vectors and their rearrangements. Random Structures & Algorithms 40(3), 2012.
N. Bansal. Discrepancy theory and related algorithms. Proceedings of the International Congress of Mathematicians 2022, Vol. 7. EMS Press, 2023.
N. Bansal and S. Garg. Algorithmic discrepancy beyond partial coloring. STOC 2017.
N. Bansal, H. Jiang, R. Meka, S. Singla, and M. Sinha. Online discrepancy minimization for stochastic arrivals. SODA 2021.
N. Bansal, H. Jiang, S. Singla, and M. Sinha. Online vector balancing and geometric discrepancy. STOC 2020.
N. Bansal and A. Nikolov. Discrepancy theory: an algorithmic and geometric perspective. arXiv:2608.00140, 2026.
R. F. Bass. Probability estimates for multiparameter Brownian processes. The Annals of Probability 16, 1988.
J. Beck. Balanced two-colorings of finite sets in the square I. Combinatorica 1(4), 1981.
J. Beck. Balanced two-colorings of finite sets in the cube. Discrete Mathematics 73, 1989.
D. Bilyk and M. Lacey. The supremum norm of the discrepancy function: recent results and connections. MCQMC 2012 (Springer, 2013).
G. Bohus. On the discrepancy of 3 permutations. Random Structures & Algorithms 1(2), 1990.
G. Halász. On Roth's method in the theory of irregularities of point distributions. Recent Progress in Analytic Number Theory, Vol. 2, 1981.
H. Jiang, J. Kulkarni, and S. Singla. Online geometric discrepancy for stochastic arrivals with applications to envy minimization. arXiv:1910.01073, 2019.
K. G. Larsen. On range searching in the group model and combinatorial discrepancy. SIAM Journal on Computing 43(2), 2014.
J. Matoušek. Geometric Discrepancy: An Illustrated Guide. Springer, 1999.
J. Matoušek and A. Nikolov. Combinatorial discrepancy for boxes via the $\gamma_2$ norm. SoCG 2015.
J. Matoušek, A. Nikolov, and K. Talwar. Factorization norms and hereditary discrepancy. IMRN, 2020.
C. McDiarmid. On the method of bounded differences. Surveys in Combinatorics, 1989. Cambridge University Press, 1989.
A. Nikolov. Tighter bounds for the discrepancy of boxes and polytopes. Mathematika 63(3), 2017.
W. M. Schmidt. Irregularities of distribution. VII. Acta Arithmetica 21, 1972.
A. Srinivasan. Improving the discrepancy bound for sparse matrices: better approximations for sparse lattice approximation problems. SODA 1997.
M. Talagrand. The small ball problem for the Brownian sheet. The Annals of Probability 22(3), 1994.
Z. Wei and K. Yi. The space complexity of 2-dimensional approximate range counting. SODA 2013. Journal version: Tight space bounds for two-dimensional approximate range counting, ACM Transactions on Algorithms, 2018.
C. Xu. Xean. GitHub repository, 2026. github.com/chaoxu/xean.
Background: K. F. Roth. On irregularities of distribution. Mathematika 1, 1954.
Background: the account of binary nets, the transference principle and the $\gamma_2$ norm in Sections 6 and 7 follows Matoušek's monograph above and the papers of Matoušek, Nikolov and Talwar and of Nikolov.

This guide answers three questions

Why earlier methods fell short

Why it works now

What the new technique is

Prerequisites

Overview: the proof in five sentences

The problem

§ 1 · BasicsA coloring game

§ 2 · BasicsFrom one dimension to two

One dimension: alternating colors are enough

Two dimensions: alternating along one coordinate is not enough

“Anchored rectangles” are enough

§ 3 · BasicsNotation and growth rates

Three levels of min and max

Asymptotic notation

What was known, and why it stopped

§ 4 · BasicsHistory of the bounds

§ 5 · IntermediateWhere the upper bound comes from

The simplest approach: random coloring

Splitting a prefix into dyadic intervals

The best upper bound known

§ 6 · IntermediateWhere the lower bound comes from: continuous discrepancy and transference

An older problem: how evenly are the points spread?

Binary nets: error at most 1 per level

Transference: good colorings produce evenly spread point sets

§ 7 · IntermediateOther lower-bound tools, and where they stop

The orthogonal-function method

The factorization norm γ2\gamma_2γ2​

Summary: three methods, the same number

A different question

§ 8 · BasicsRandom points, one coloring at a time

The two steps of the proof

§ 9 · IntermediateWhat to aim for: guessing the exponent 32\frac3223​

§ 10 · IntermediateRevealing digit by digit: a random number as a sequence of dice

Information and conditional expectation

Local oscillation

§ 11 · Basicsh+1h+1h+1 stages, a family of rectangles of equal area

§ 12 · IntermediateEndpoint average and oscillation

Endpoint average

Oscillation

The potential ZjZ_jZj​

§ 13 · Core argumentThe comparison in one rectangle, part 1: the deterministic part

Step 1: an inequality for step functions

Step 2: after the refinement, average the child functions

Step 3: the weight of a point in aˉ\bar aaˉ

§ 14 · Core argumentThe comparison in one rectangle, part 2: expectation, baseline and gain

What is random

Step 1: the jumps are symmetric, so E aˉ=a\EE\,\bar a=aEaˉ=a

Step 2: the baseline

Step 3: separating the contribution of the points of the inner region

Step 4: a sum of symmetric random variables is not close to any fixed point

Step 5: putting it together to get Lemma 2.3

What one rectangle gives, and what is missing

§ 15 · IntermediateThe effect of changing one digit

§ 16 · Core argumentAll hhh transitions: the plan, conditional gain and fluctuations

Step 1: splitting the increment into “conditional gain” and “fluctuation”

Step 2: the average gain of each transition

Step 3: bounded differences

Step 4: the fluctuation term is unlikely to be very negative

§ 17 · IntermediateNo crowding: heavy regions and good transitions

Heavy regions and good transitions

The probability that a transition is not good

§ 18 · Core argumentFinishing the proof: Theorem 1.1

Putting the three steps together: Proposition 2.7

Choice of parameters

Proof of Theorem 1.1

Looking back

§ 19 · IntermediateThe accounting for 32\frac3223​

Why nM\frac nMMn​ cannot be larger

Comparing with the guess of Section 9

§ 20 · BasicsWhy earlier methods fell short, and why it works now

Why earlier methods fell short

Why it works now

The paper's four steps and this guide

List of techniques

§ 21 · BasicsConstants, formalization and open problems

Explicit bad point sets

Higher dimensions

Constants

Formalization and AI

The factorization norm $\gamma_2$

§ 9 · IntermediateWhat to aim for: guessing the exponent $\frac32$

§ 11 · Basics $h+1$ stages, a family of rectangles of equal area

The potential $Z_j$

Step 3: the weight of a point in $\bar a$

Step 1: the jumps are symmetric, so $\EE\,\bar a=a$

§ 16 · Core argumentAll $h$ transitions: the plan, conditional gain and fluctuations

§ 19 · IntermediateThe accounting for $\frac32$

Why $\frac nM$ cannot be larger