betaFeedback

WorksMathematics

A Sharp Distributional Lower Bound for Planar Discrepancy

Abstract

We prove that the unnormalized discrepancy function of every nn-point set in the unit square has absolute value at least c1+log⁡nc\sqrt{1+\log n} on a set of measure at least ηη, with absolute constants c,η>0c,η>0. Consequently, its LpL_p-quasinorm is bounded below by c η1/p1+log⁡nc\,η^{1/p} \sqrt{1+\log n} for every p>0p>0.

Introduction and main results

Let Pn\mathcal{P}_n be a set of n≥1n\ge1 points in [0,1]2[0,1]^2. Its unnormalized discrepancy function is

DPn(x,y)=#(Pn∩([0,x]×[0,y]))−nxy.(1)D_{\mathcal{P}_n}(x,y)=\#(\mathcal{P}_n\cap([0,x]\times[0,y]))-nxy. \tag*{(1)}

The main purpose of this note is to show that ∣DPn∣|D_{\mathcal{P}_n}| exceeds a constant multiple of 1+log⁡n\sqrt{1+\log n} on a set of uniformly positive measure. To state this precisely, define, for u>0u>0,

ΦPn(u)=λ2{(x,y):∣DPn(x,y)∣≥u},\Phi_{\mathcal{P}_n}(u)=\lambda_2\{(x,y):|D_{\mathcal{P}_n}(x,y)|\ge u\},

where λ2\lambda_2 denotes Lebesgue measure on [0,1]2[0,1]^2. Throughout, log⁡\log denotes the natural logarithm. Our main result is

Theorem 1. There exist constants c,η>0c,\eta>0 such that for every n≥1n\ge1 and every nn-point set Pn⊂[0,1]2\mathcal{P}_n\subset[0,1]^2,

ΦPn(c1+log⁡n)≥η.(2)\Phi_{\mathcal{P}_n}\left(c\sqrt{1+\log n}\right)\ge\eta. \tag*{(2)}

An immediate consequence is the following lower bound for the LpL_p-(quasi-)norm, defined for p>0p>0 by

∥f∥Lp=(∫[0,1]2∣f∣p dλ2)1/p.\|f\|_{L_p}=\left(\int_{[0,1]^2}|f|^p\,d\lambda_2\right)^{1/p}.

Corollary 2. For every n≥1n\ge1, every nn-point set Pn⊂[0,1]2\mathcal{P}_n\subset[0,1]^2, and every p>0p>0,

∥DPn∥Lp≥cη1/p1+log⁡n,\|D_{\mathcal{P}_n}\|_{L_p}\ge c\eta^{1/p}\sqrt{1+\log n},

where cc and η\eta are the constants from Theorem 1.

For historical background and further references on discrepancy bounds in various settings and dimensions, we refer to the survey [1]. Corollary 2 confirms [1 Conjecture 3.3] in the planar case.

We briefly recall the classical results in the planar case. Roth proved the planar lower bound of order 1+log⁡n\sqrt{1+\log n} for the L2L_2-norm in [5]. His proof also gives the sharp lower bound of order (1+log⁡n)d−12(1+\log n)^{\frac{d-1}{2}} for the L2L_2-norm in general dimension dd. Schmidt extended this lower bound of order 1+log⁡n\sqrt{1+\log n} to the LpL_p-norm in the range 1<p<21<p<2 in [6], also with the corresponding lower bound in general dimension. For p≥2p\ge2, the same lower bound follows directly from Roth’s L2L_2 estimate by monotonicity of the LpL_p-norms. Halász proved the corresponding estimate for the L1L_1-norm in [4]. His argument does not yield the corresponding lower bound of order (1+log⁡n)(d−1)/2(1+\log n)^{(d-1)/2} in dimensions d>2d>2. Obtaining the corresponding L1L_1 lower bound of order (1+log⁡n)(d−1)/2(1+\log n)^{(d-1)/2} in dimensions d≥3d\ge3 remains a major open problem in discrepancy theory.

The classical construction of Davenport in [3] gives a sequence of point sets in [0,1]2[0,1]^2 with discrepancy of order 1+log⁡n\sqrt{1+\log n} for the L2L_2-norm. By monotonicity of the LpL_p-(quasi-)norms, the same point sets satisfy an upper bound of order 1+log⁡n\sqrt{1+\log n} for every 0<p≤20<p\le2. This proves optimality for 0<p≤20<p\le2. For the remaining range p>2p>2, Chen [2] proved that, for every n≥1n\ge1, there exists an nn-point set Pn⊂[0,1]2\mathcal{P}_n\subset[0,1]^2 satisfying

∥DPn∥Lp≤Cp1+log⁡n.\lVert D_{\mathcal{P}_n}\rVert_{L_p}\le C_p\sqrt{1+\log n}.

Thus Corollary 2 is optimal in its order of growth in nn for every fixed p>0p>0. For a discussion of suitable modifications of the van der Corput point set, see [1 Section 6]. Similarly, the L2L_2 upper bound and Chebyshev’s inequality show that the scale 1+log⁡n\sqrt{1+\log n} in Theorem 1 cannot be replaced by a function of larger order while retaining a uniform positive lower bound for the measure.

The paper is organized as follows. In § 2, we recall necessary notation for the orthogonal system of Haar functions and summarize the needed properties of Haar coefficients of the discrepancy function. A key observation in lower bound proofs is that if the interior of a dyadic rectangle contains no point of Pn\mathcal{P}_n, then the corresponding Haar coefficient depends only on nn and the area of the rectangle. To keep the paper self-contained and clarify which ingredients are classical and which are new, we include concise versions of several known proofs.

A useful, though not entirely accurate, heuristic is to view the planar discrepancy function as a sum of about log⁡n\log n independent Rademacher variables. The main technical problem is to make this heuristic precise and control the deviation from the idealized model. § 3 revisits the classical lower bounds from this probabilistic viewpoint, states the distributional estimate for Haar polynomials in Theorem 4, and uses it to prove Theorem 1. § 4 establishes the averaging lemma, Lemma 7, and then applies it to prove Theorem 4.

The classical arguments in Subsections 3.1–3.3 provide background and motivation but are not needed for the proof of Theorem 1. The principal new ingredients are the distributional estimate in Theorem 4 and the averaging lemma, Lemma 7.

Haar functions and discrepancy coefficients

Let D\mathcal{D} be the collection of dyadic intervals

I=[j2−a,(j+1)2−a),a∈N0,j∈{0,…,2a−1}.I=[j2^{-a},(j+1)2^{-a}),\qquad a\in\mathbb{N}_0,\quad j\in\{0,\ldots,2^a-1\}.

For I∈DI\in\mathcal{D}, let ∣I∣|I| denote its length and IleftI_{\mathrm{left}} and IrightI_{\mathrm{right}} its left and right halves. Define the Haar function with support II by

hI=1Iright−1Ileft.h_I=1_{I_{\mathrm{right}}}-1_{I_{\mathrm{left}}}.

For a dyadic rectangle R=I×JR=I\times J, put hR(x,y)=hI(x)hJ(y)h_R(x,y)=h_I(x)h_J(y) and ∣R∣=∣I∣∣J∣=λ2(R)|R|=|I||J|=\lambda_2(R). These tensor Haar functions are pairwise orthogonal and satisfy

∥hR∥22=∣R∣.\lVert h_R\rVert_2^2=|R|.

For f∈L1([0,1]2)f \in L_1([0,1]^2), we use the Haar expansion coefficients

aR(f)=⟨f,hR⟩∣R∣.a_R(f)=\frac{\langle f,h_R\rangle}{|R|}.

Thus aR(f)a_R(f) is distinguished from the unnormalized inner product ⟨f,hR⟩\langle f,h_R\rangle. Together with the constant function and the one-variable functions hI(x)h_I(x) and hJ(y)h_J(y), the functions hRh_R form a complete orthogonal system in L2([0,1]2)L_2([0,1]^2). In particular, every real f∈L2([0,1]2)f \in L_2([0,1]^2) has a decomposition

f(x,y)=u(x)+v(y)+∑R∈D×DaR(f)hR(x,y),(3)f(x,y)=u(x)+v(y)+\sum_{R\in\mathcal{D}\times\mathcal{D}}a_R(f)h_R(x,y), \tag*{(3)}

with convergence in L2L_2. Here u,v∈L2([0,1])u,v \in L_2([0,1]) contain the constant and one-variable components; the allocation of the constant term does not matter.

For integers k≥0k \ge0 and 0≤a≤k0 \le a \le k, define

Dk,a={I×J:I,J∈D, ∣I∣=2−a, ∣J∣=2−(k−a)}.\mathcal{D}_{k,a}=\{I\times J:I,J\in\mathcal{D},\ |I|=2^{-a},\ |J|=2^{-(k-a)}\}.

Each collection Dk,a\mathcal{D}_{k,a} partitions [0,1)2[0,1)^2 into 2k2^k rectangles of area 2−k2^{-k}. We call aa the shape index and kk the level. We retain the half-open convention when assigning points to rectangles. Identities between functions are understood almost everywhere; in particular, their values on the union of all dyadic boundaries, a set of Lebesgue measure zero, are immaterial.

The coefficients of the discrepancy function

The following well-known calculation separates the contribution of the points from that of the volume term.

Lemma 3. Let R=I×JR=I\times J be a dyadic rectangle and put τI(t)=∫t1hI(x) dx\tau_I(t)=\int_t^1 h_I(x)\,dx. Then

aR(DPn)=1∣R∣∑p∈PnτI(p1)τJ(p2)−n∣R∣16.(4)a_R(D_{P_n})=\frac{1}{|R|}\sum_{p\in P_n}\tau_I(p_1)\tau_J(p_2)-\frac{n|R|}{16}. \tag*{(4)}

In particular, if the interior of RR contains no point of PnP_n, then

aR(DPn)=−n∣R∣16.(5)a_R(D_{P_n})=-\frac{n|R|}{16}. \tag*{(5)}

Proof. The contribution of p=(p1,p2)p=(p_1,p_2) to the counting function is 1[p1,1](x)1[p2,1](y)\mathbf{1}_{[p_1,1]}(x)\mathbf{1}_{[p_2,1]}(y). Hence Fubini’s theorem gives

⟨1[p1,1]⊗1[p2,1],hR⟩=τI(p1)τJ(p2).\left\langle\mathbf{1}_{[p_1,1]}\otimes\mathbf{1}_{[p_2,1]},h_R\right\rangle=\tau_I(p_1)\tau_J(p_2).

Moreover,

∫01xhI(x) dx=∣I∣24,⟨nxy,hR⟩=n∣R∣216.\int_0^1 xh_I(x)\,dx=\frac{|I|^2}{4},\qquad\langle nxy,h_R\rangle=\frac{n|R|^2}{16}.

Dividing the difference by ∣R∣|R| proves (2.2). The function τI\tau_I vanishes outside the interior of II, including at its endpoints. Consequently every point contribution vanishes when the interior of RR is empty, which proves (2.3). □\square

Choose the unique integer ℓ≥2\ell\ge2 such that

2ℓ−2≤n<2ℓ−1,ρ=n2−ℓ∈[1/4,1/2).(6)2^{\ell-2}\le n<2^{\ell-1},\qquad\rho=n2^{-\ell}\in[1/4,1/2). \tag*{(6)}

For each k≥ℓk \ge\ell and 0≤a≤k0 \le a \le k, let

Bk,a={R∈Dk,a:R∩Pn≠∅}\mathcal{B}_{k,a}=\{R\in\mathcal{D}_{k,a}:R\cap P_n\ne\varnothing\}

be the collection of bad rectangles. The remaining rectangles in Dk,a\mathcal{D}_{k,a} are called good. Since rectangles of a fixed shape and level are disjoint,

#Bk,a≤n.(7)\#\mathcal{B}_{k,a}\le n. \tag*{(7)}

In particular, the union of the bad rectangles of any principal shape has measure at most n2−ℓ<1/2n2^{-\ell}<1/2. We use the half-open convention when designating rectangles as good or bad, although the coefficient formula only requires an empty interior.

A dyadic rectangle QQ is an ancestor of RR if R⊆QR\subseteq Q; equality is allowed, and the two side lengths may be enlarged independently. Empty rectangles have only empty descendants. Thus the good rectangles are hereditary: every descendant of a good rectangle is good. Equivalently, every ancestor of a bad rectangle among the levels under consideration is bad.

For the rescaled discrepancy function

f=−16ρDPn,(8)f=-\frac{16}{\rho}D_{P_n}, \tag*{(8)}

Lemma 3 yields

aR(f)=2−s(s≥0, R∈Dℓ+s,a∖Bℓ+s,a).(9)a_R(f)=2^{-s}\qquad(s\ge0,\ R\in\mathcal{D}_{\ell+s,a}\setminus\mathcal{B}_{\ell+s,a}). \tag*{(9)}

The coefficients on bad rectangles need not satisfy this identity.

The regular sums and the Rademacher model

Define the regular sum at level kk by

Hk=∑a=0k∑R∈Dk,ahR.(10)H_k=\sum_{a=0}^{k}\sum_{R\in\mathcal{D}_{k,a}}h_R. \tag*{(10)}

Let εj\varepsilon_j be the jjth Rademacher function on [0,1)[0,1), with value −1-1 when the jjth binary digit of the argument is zero and +1+1 when it is one. Summing the Haar functions over all rectangles of one shape gives

Hk(x,y)=∑a=0kεa+1(x)εk−a+1(y).(11)H_k(x,y)=\sum_{a=0}^{k}\varepsilon_{a+1}(x)\varepsilon_{k-a+1}(y). \tag*{(11)}

For fixed kk, the summands involve disjoint pairs of independent binary digits. They are therefore independent Rademacher variables on the square equipped with Lebesgue probability measure. In particular,

∥Hk∥22=k+1.(12)\lVert H_k\rVert_2^2=k+1. \tag*{(12)}

Different levels are orthogonal, although they need not be independent.

To identify precisely how the discrepancy function differs from these regular sums, let gg consist of the constant and one-variable components of ff, together with its mixed Haar terms of levels k<ℓk<\ell. For R∈Dℓ+s,aR\in\mathcal{D}_{\ell+s,a} put βR=aR(f)−2−s\beta_R=a_R(f)-2^{-s}. The truncation of the expansion of ff at level ℓ+S\ell+S can then be written as

fS=g+∑s=0S2−sHℓ+s+CS,CS=∑s=0S∑a=0ℓ+s∑R∈Bℓ+s,aβRhR.(13)\begin{aligned} f_S&=g+\sum_{s=0}^{S}2^{-s}H_{\ell+s}+C_S,\\ C_S&=\sum_{s=0}^{S}\sum_{a=0}^{\ell+s}\sum_{R\in\mathcal{B}_{\ell+s,a}}\beta_Rh_R. \tag*{(13)} \end{aligned}

Since f∈L2([0,1]2)f \in L_2([0,1]^2), completeness and orthogonality imply fS→ff_S \to f in L2L_2 as S→∞S \to\infty. The principal regular sum HℓH_\ell is exactly a sum of ℓ+1\ell+1 independent signs, and ℓ+1\ell+1 is comparable to 1+log⁡n1+\log n. The remaining terms have different roles. The coarser part gg has a restricted dependence on the binary digits, the regular finer levels have geometrically decreasing coefficients, and the corrections CSC_S occur only on bad rectangles, whose ancestors among the levels under consideration are also bad. Their coefficients may be large, so they cannot simply be discarded as a small error. These features underlie the distributional estimate stated in § 3 and proved in § 4.

From classical lower bounds to a distributional estimate

We first revisit the classical planar lower bounds of Roth, Schmidt, and Halász [5, 6, 4]; see also [1]. The good rectangles at the principal Haar level supply the essential contribution in each case. Orthogonality gives the L2L_2 bound, the product Littlewood–Paley inequality yields the LpL_p bounds for p>1p>1, and a bounded complex Riesz product gives the L1L_1 bound. We then turn from these norm estimates to the distributional statement needed for Theorem 1.

Roth’s bound by orthogonality

Keep the principal level ℓ\ell and the number ρ\rho from (2.4), and put m=ℓ+1m=\ell+1. For every good rectangle RR in the principal level, Lemma 3 gives

aR(DPn)=−ρ16.a_R(D_{P_n})=-\frac{\rho}{16}.

Each principal shape contains at least 2ℓ−12^{\ell-1} good rectangles. Hence orthogonality and Bessel’s inequality yield

∥DPn∥22≥∑a=0ℓ∑R∈Dℓ,a∖Bℓ,a∣aR(DPn)∣2∣R∣≥ρ2m512.\lVert D_{P_n}\rVert_2^2 \ge\sum_{a=0}^{\ell}\sum_{R\in\mathcal{D}_{\ell,a}\setminus\mathcal{B}_{\ell,a}} \lvert a_R(D_{P_n})\rvert^2\lvert R\rvert\ge\frac{\rho^2m}{512}.

Since ρ≥1/4\rho\ge1/4, we obtain Roth’s planar lower bound

∥DPn∥2≥ρm162≥m642.(14)\lVert D_{P_n}\rVert_2 \ge\frac{\rho\sqrt{m}}{16\sqrt{2}} \ge\frac{\sqrt{m}}{64\sqrt{2}}. \tag*{(14)}

Schmidt’s bound via the Littlewood–Paley inequality

For f∈Lp([0,1]2)f\in L_p([0,1]^2), define its mixed dyadic square function by

Sf=(∑R∈D×D∣aR(f)∣21R)1/2.Sf=\left(\sum_{R\in\mathcal{D}\times\mathcal{D}}\lvert a_R(f)\rvert^2\mathbf{1}_R\right)^{1/2}.

For every 1<p<∞1<p<\infty, the product Littlewood–Paley inequality gives a constant Ap>0A_p>0 such that

∥f∥p≥Ap∥Sf∥p.(15)\lVert f\rVert_p\ge A_p\lVert Sf\rVert_p. \tag*{(15)}

see [1 Section 3]. To account explicitly for the one-variable terms, let ExE_x and EyE_y denote averaging in the respective coordinates and put P=(I−Ex)(I−Ey)P=(I-E_x)(I-E_y). Then Sf=S(Pf)Sf=S(Pf), and the product Littlewood–Paley inequality applied to PfPf gives ∥Sf∥p≲p∥Pf∥p≤4∥f∥p\lVert Sf\rVert_p\lesssim_p\lVert Pf\rVert_p\le4\lVert f\rVert_p, which yields (3.2).

Let

M=∑a=0ℓ∑R∈Dℓ,a∖Bℓ,a1RM=\sum_{a=0}^{\ell}\sum_{R\in\mathcal{D}_{\ell,a}\setminus\mathcal{B}_{\ell,a}}\mathbf{1}_{R}

count the good principal rectangles containing a given point. Since at least half of the rectangles of each shape are good,

0≤M≤m,∫[0,1]2M dλ2≥m2.0\le M\le m,\qquad\int_{[0,1]^2}M\,d\lambda_2\ge\frac{m}{2}.

Consequently, the set E={M≥m/4}E=\{M\ge m/4\} has measure at least 1/41/4: indeed,

m2≤∫M dλ2≤m4+mλ2(E).\frac{m}{2}\le\int M\,d\lambda_2\le\frac{m}{4}+m\lambda_2(E).

On EE, the good principal coefficients give

S(DPn)≥ρ16M≥ρm32.S(DP_n)\ge\frac{\rho}{16}\sqrt{M}\ge\frac{\rho\sqrt{m}}{32}.

Applying (3.2), we obtain

∥DPn∥p≥Ap∥S(DPn)∥p≥Apρ324−1/pm≳p1+log⁡n.(16)\|DP_n\|_p\ge A_p\|S(DP_n)\|_p\ge\frac{A_p\rho}{32}4^{-1/p}\sqrt{m}\gtrsim_p\sqrt{1+\log n}. \tag*{(16)}

This recovers Schmidt’s planar lower bound for every 1<p<∞1<p<\infty. The restriction on pp enters only through the Littlewood–Paley inequality.

Halász’s bound via a complex Riesz product

For 0≤a≤ℓ0\le a\le\ell, define

qa=−∑R∈Dℓ,a∖Bℓ,ahR.q_a=-\sum_{R\in\mathcal{D}_{\ell,a}\setminus\mathcal{B}_{\ell,a}}h_R.

These functions satisfy ∣qa∣≤1|q_a|\le1. By Lemma 3 and the count of good rectangles,

⟨DPn,qa⟩=ρ16∑R∈Dℓ,a∖Bℓ,a∣R∣≥ρ32.(17)\langle DP_n,q_a\rangle=\frac{\rho}{16}\sum_{R\in\mathcal{D}_{\ell,a}\setminus\mathcal{B}_{\ell,a}}|R|\ge\frac{\rho}{32}. \tag*{(17)}

Following Halász [4], we combine these Haar polynomials into a bounded complex Riesz product.

We first record an estimate for its higher-order terms. For every k≥0k\ge0 and 0≤a≤k0\le a\le k,

∑R∈Dk,a∣⟨DPn,hR⟩∣≤5n2−k16.(18)\sum_{R\in\mathcal{D}_{k,a}}|\langle DP_n,h_R\rangle|\le\frac{5n2^{-k}}{16}. \tag*{(18)}

Indeed, 0≤τI≤∣I∣/20\le\tau_I\le|I|/2, and each point contributes to at most one rectangle of a given shape and level. By (2.2), the point contributions therefore sum to at most n2−k/4n2^{-k}/4, while the absolute volume contributions sum to n2−k/16n2^{-k}/16.

For distinct indices a1<⋯<ara_1<\cdots<a_r, with r≥2r\ge2, the product qa1⋯qarq_{a_1}\cdots q_{a_r} is a Haar sum over rectangles with side lengths 2−ar2^{-a_r} and 2−(ℓ−a1)2^{-(\ell-a_1)}, with coefficients in {−1,0,1}\{-1,0,1\}. To see this, expand the product and discard empty intersections. On each remaining intersection, the finest Haar function in each coordinate is multiplied only by functions constant on its support. The intersections are disjoint rectangles of the stated shape. Consequently, (3.5) gives

∣⟨DPn,qa1⋯qar⟩∣≤5ρ162−(ar−a1).(19)|\langle DP_n,q_{a_1}\cdots q_{a_r}\rangle|\le\frac{5\rho}{16}2^{-(a_r-a_1)}. \tag*{(19)}

Set γ=1/8\gamma= 1/8, t=γ/mt = \gamma/\sqrt{m}, and

Ψ=Im⁡∏a=0ℓ(1+itqa).\Psi= \operatorname{Im}\prod_{a=0}^{\ell}(1+itq_a).

Since ∣qa∣≤1|q_a| \le1,

∥Ψ∥∞≤(1+t2)m/2≤eγ2/2.(20)\|\Psi\|_\infty\le(1+t^2)^{m/2} \le e^{\gamma^2/2}. \tag*{(20)}

The linear term is t∑a=0ℓqat\sum_{a=0}^{\ell}q_a, and its pairing with the discrepancy function is at least ρmt/32\rho mt/32 by (3.4). The remaining terms have odd degree at least three.

For a fixed span d=ar−a1d=a_r-a_1, there are m−dm-d choices of the endpoints and (d−1r−2)\binom{d-1}{r-2} choices of the interior indices. Thus (3.6) yields

∣⟨DPn,Ψ−t∑a=0ℓqa⟩∣≤5ρ16∑d=1m−1(m−d)2−d∑r=3d+1(d−1r−2)tr≤5ρm16t2∑d=1∞2−d((1+t)d−1−1)=5ρm16t31−t.\begin{aligned} \left|\left\langle D_{P_n},\Psi-t\sum_{a=0}^{\ell}q_a\right\rangle\right| \le\frac{5\rho}{16}\sum_{d=1}^{m-1}(m-d)2^{-d}\sum_{r=3}^{d+1}\binom{d-1}{r-2}t^r \\ &\le\frac{5\rho m}{16}t^2\sum_{d=1}^{\infty}2^{-d}\left((1+t)^{d-1}-1\right) \\ &= \frac{5\rho m}{16}\frac{t^3}{1-t}. \end{aligned}

Here we bounded the sum over odd degrees by the sum over all degrees at least three. Since t≤1/8t\le1/8,

10t21−t≤528<12.\frac{10t^2}{1-t}\le\frac{5}{28}<\frac{1}{2}.

It follows that

⟨DPn,Ψ⟩≥ρmt64.\langle D_{P_n},\Psi\rangle\ge\frac{\rho mt}{64}.

Using (3.7), we obtain

∥DPn∥1≥⟨DPn,Ψ⟩∥Ψ∥∞≥ργ64eγ2/2m≳1+log⁡n.(21)\|D_{P_n}\|_1\ge\frac{\langle D_{P_n},\Psi\rangle}{\|\Psi\|_\infty} \ge\frac{\rho\gamma}{64e^{\gamma^2/2}}\sqrt{m}\gtrsim\sqrt{1+\log n}. \tag*{(21)}

A distributional estimate for Haar expansions

The preceding arguments establish the lower bounds for p≥1p\ge1, but do not directly extend to 0<p<10<p<1. We now state a stronger distributional estimate based on the decomposition from Section 2, deferring its proof to Section 4. The following theorem isolates its essential features: prescribed coefficients on hereditary good rectangles and arbitrary coefficients on bad rectangles.

Fix a principal level ℓ≥0\ell\ge0 and a finite depth S≥0S\ge0. For ℓ≤k≤ℓ+S\ell\le k\le\ell+S and 0≤a≤k0\le a\le k, designate a collection Bk,a⊆Dk,a\mathcal{B}_{k,a}\subseteq\mathcal{D}_{k,a} of bad rectangles. The remaining rectangles are called good.

Theorem 4. Let 0≤δ<10\le\delta<1. Suppose that the good rectangles are hereditary among the levels under consideration and

#Bℓ,a≤δ2ℓ(0≤a≤ℓ).(22)\#\mathcal{B}_{\ell,a}\le\delta2^\ell\qquad(0\le a\le\ell). \tag*{(22)}

Let

f=g+∑s=0S∑a=0ℓ+s∑R∈Dℓ+s,aαRhR,(23)f=g+\sum_{s=0}^{S}\sum_{a=0}^{\ell+s}\sum_{R\in\mathcal{D}_{\ell+s,a}}\alpha_Rh_R, \tag*{(23)}

:::`

where gg is the sum of a finite real linear combination of tensor Haar functions supported on rectangles of area greater than 2−ℓ2^{-\ell} and arbitrary real measurable functions u(x)+v(y)u(x)+v(y), finite almost everywhere. Assume

αR=2−swhenever R∈Dℓ+s,a∖Bℓ+s,a.(24)\alpha_R=2^{-s}\qquad\text{whenever }R\in\mathcal{D}_{\ell+s,a}\setminus\mathcal{B}_{\ell+s,a}. \tag*{(24)}

The bad coefficients are arbitrary real numbers. Then, for every integer K≥0K\ge0,

λ2{∣f∣≥(1−δ)(ℓ+1)8K+1}≥1−δ2564(K+1)(3K+7)9(1−δ)4K.(25)\lambda_2\left\{|f|\ge\frac{\sqrt{(1-\delta)(\ell+1)}}{8\sqrt{K+1}}\right\}\ge\frac{1-\delta}{25}\frac{64(K+1)(3K+7)}{9(1-\delta)^{4K}}. \tag*{(25)}

In particular, when δ≤1/2\delta\le1/2,

λ2{∣f∣≥ℓ+1822}≥1100.(26)\lambda_2\left\{|f|\ge\frac{\sqrt{\ell+1}}{8\sqrt{22}}\right\}\ge\frac{1}{100}. \tag*{(26)}

Remark 5. Apart from heredity, no restriction is imposed on the finer bad collections. For every fixed δ<1\delta<1, the right-hand side of (25) is positive for all sufficiently large KK. Thus the theorem gives a positive measure bound whenever the principal bad proportion is bounded away from one.

To apply Theorem 4 to the full Haar expansion of the discrepancy function, we will pass to the limit in its finite truncations using the following elementary observation.

Proposition 6. Let fq→ff_q\to f in measure on [0,1]2[0,1]^2. If, for some z>0z>0 and η>0\eta>0,

λ2{∣fq∣≥z}≥ηfor every q,\lambda_2\{|f_q|\ge z\}\ge\eta\qquad\text{for every }q,

then

λ2{∣f∣≥z}≥η.\lambda_2\{|f|\ge z\}\ge\eta.

In particular, for fixed ℓ\ell and δ\delta, every bound in Theorem 4 passes to limits in measure of finite expansions satisfying its hypotheses.

Proof. Suppose fq→ff_q\to f in measure and λ2{∣fq∣≥z}≥η\lambda_2\{|f_q|\ge z\}\ge\eta for every qq. For every 0<ε<z0<\varepsilon<z,

λ2{∣f∣≥z−ε}≥η−λ2{∣fq−f∣>ε}.\lambda_2\{|f|\ge z-\varepsilon\}\ge\eta-\lambda_2\{|f_q-f|>\varepsilon\}.

Letting q→∞q\to\infty and then ε↓0\varepsilon\downarrow0 gives λ2{∣f∣≥z}≥η\lambda_2\{|f|\ge z\}\ge\eta.

Application to the discrepancy function

Proof of Theorem 1. Use the level ℓ\ell, the number ρ\rho, and the rescaled function f=−16DPn/ρf=-16D_{P_n}/\rho from § 2. As shown there, the good rectangles are hereditary, the principal bad proportion is less than 1/21/2, and the coefficients on good rectangles have the values required by Theorem 4.

The truncations fSf_S from (13) therefore satisfy (26). Since fS→ff_S\to f in L2L_2, hence in measure, Proposition 6 gives

λ2{∣f∣≥ℓ+1822}≥1100.\lambda_2\left\{|f|\ge\frac{\sqrt{\ell+1}}{8\sqrt{22}}\right\}\ge\frac{1}{100}.

Rescaling and using ρ≥1/4\rho\ge1/4, we obtain

λ2{∣DPn∣≥ℓ+151222}≥1100.(27)\lambda_2\left\{|D_{P_n}|\ge\frac{\sqrt{\ell+1}}{512\sqrt{22}}\right\}\ge\frac{1}{100}. \tag*{(27)}

Finally, (6) implies

log⁡n<(ℓ−1)log⁡2≤ℓ,1+log⁡n≤ℓ+1.\log n < (\ell- 1)\log2 \le\ell,\qquad1+\log n \le\ell+1.

This proves Theorem 1, with c=1/(51222)c=1/(512\sqrt{22}) and η=1/100\eta=1/100.

No attempt has been made to optimize these constants.

Proof of the distributional estimate

An averaging lemma with hereditary interactions

The following lemma gives a distributional lower bound for a sum whose principal terms are products XjYjX_jY_j of independent random signs. We allow additional terms with a prescribed dependence on these signs, including interactions that vanish whenever they cross a good position. The proof averages successively over the YY variables and uses an L2L_2 contraction at each good position.

The additional random variable WW allows the terms and the good positions to depend on randomness other than the displayed signs. It is independent of those signs and may be viewed as a parameter when taking the finite averages over them. In the application to Haar expansions, WW collects the binary digits not selected as XjX_j or YjY_j. The estimates are then integrated over WW; the bounds on the probabilities of bad positions are required only for the full probability space, not for each fixed value of WW.

We write X=(X1,…,XN)X=(X_1,\ldots,X_N), Y=(Y1,…,YN)Y=(Y_1,\ldots,Y_N), X≤j=(X1,…,Xj)X_{\leq j}=(X_1,\ldots,X_j) and Y>j=(Yj+1,…,YN)Y_{>j}=(Y_{j+1},\ldots,Y_N), with the analogous conventions for strict initial and closed terminal segments. A segment may be empty.

Lemma 7. Let N≥1N\geq1, and let X1,…,XN,Y1,…,YNX_1,\ldots,X_N,Y_1,\ldots,Y_N be independent uniform signs, independent also of WW. Suppose the real random variable FF has the representation

F=A0(W,Y)+∑j=1N(Aj(W,X≤j,Y>j)+XjYj+∑k=1jCk,j(W,X≤j,Y≥k)).(28)F=A_0(W,Y)+\sum_{j=1}^{N}\left(A_j(W,X_{\leq j},Y_{>j})+X_jY_j+\sum_{k=1}^{j}C_{k,j}(W,X_{\leq j},Y_{\geq k})\right). \tag*{(28)}

Let W\mathcal{W} denote the measurable space in which WW takes values. The functions

A0:W×{−1,1}N→R,A_0:\mathcal{W}\times\{-1,1\}^{N}\to\mathbb{R},
Aj:W×{−1,1}j×{−1,1}N−j→R(1≤j≤N),A_j:\mathcal{W}\times\{-1,1\}^{j}\times\{-1,1\}^{N-j}\to\mathbb{R}\qquad(1\leq j\leq N),
Ck,j:W×{−1,1}j×{−1,1}N−k+1→R(1≤k≤j≤N)C_{k,j}:\mathcal{W}\times\{-1,1\}^{j}\times\{-1,1\}^{N-k+1}\to\mathbb{R}\qquad(1\leq k\leq j\leq N)

are measurable. Their arguments are ordered as in (28), and {−1,1}0\{-1,1\}^{0} is understood to be a singleton. Fix 0≤δ<10\leq\delta<1. Let Ωi\Omega_i be measurable with respect to σ(W,X<i,Y>i)\sigma(W,X_{<i},Y_{>i}), with P(Ωi)≤δ\mathbb{P}(\Omega_i)\leq\delta. Suppose

1ΩicCk,j=0(1≤k≤i≤j≤N).(29)\mathbf{1}_{\Omega_i^c}C_{k,j}=0\qquad(1\leq k\leq i\leq j\leq N). \tag*{(29)}

We call position ii good on Ωic\Omega_i^c and bad on Ωi\Omega_i. Thus an interaction Ck,jC_{k,j} vanishes whenever a position between kk and jj, inclusive, is good. Then, for every real tt,

∣EeitF∣2≤δ+(1−δ)κ(t)2N,κ(t)=max⁡{∣cos⁡t∣,∣sin⁡t∣}.(30)\left|\mathbb{E}e^{itF}\right|^2\leq\delta+(1-\delta)\kappa(t)^{2N},\qquad\kappa(t)=\max\{|\cos t|,|\sin t|\}. \tag*{(30)}

Furthermore,

P{∣F∣≥(1−δ)N4}≥1−δ25.(31)\mathbb{P}\left\{|F|\geq\frac{\sqrt{(1-\delta)N}}{4}\right\}\geq\frac{1-\delta}{25}. \tag*{(31)}

The proof has a martingale flavour. Averaging over successive YY variables gives conditional expectations with respect to a decreasing family of σ\sigma-algebras. At each stage, we average only up to the last good position. The event selecting that position does not depend on the signs being averaged out, so this choice preserves expectations. An L2L_2 contraction at good positions, together with preservation of the squared modulus at bad positions, then yields the required estimate.

Proof. Let FjF_j denote the partial sum in (28) through index jj, with F0=A0(W,Y)F_0=A_0(W,Y). Let PlP_l average only Y1,…,YlY_1,\ldots,Y_l, keeping WW, all XX variables, and Y>lY_{>l} fixed; P0P_0 is the identity operator. At each step, we average the YY variables up to the last good position. This preserves the expectation while allowing an L2L_2 contraction at each new good position. For 0≤j≤N0\le j\le N, define

Lj=max⁡{i∈{1,…,j}:Ωic occurs}∪{0}.(32)L_j=\max\{i\in\{1,\ldots,j\}:\Omega_i^c\text{ occurs}\}\cup\{0\}. \tag*{(32)}

If l≥1l\ge1, the event {Lj=l}\{L_j=l\} equals Ωlc∩⋂i=l+1jΩi\Omega_l^c\cap\bigcap_{i=l+1}^{j}\Omega_i; for l=0l=0 it equals ⋂i=1jΩi\bigcap_{i=1}^{j}\Omega_i. Hence

{Lj=l}∈σ(W,X≤j,Y>l).(33)\{L_j=l\}\in\sigma(W,X_{\le j},Y_{>l}). \tag*{(33)}

In particular, this event does not depend on the YY variables averaged by PlP_l. Define

Vj=∑l=0j1{Lj=l}PleitFj,Mj=E∣Vj∣2.(34)V_j=\sum_{l=0}^{j}\mathbf{1}_{\{L_j=l\}}P_l e^{itF_j},\qquad M_j=\mathbb{E}|V_j|^2. \tag*{(34)}

These quantities are well-defined even when FF is not integrable, since its complex exponential has modulus one. We have

∣Vj∣≤1,EVj=EeitFj,M0=1.(35)|V_j|\le1,\qquad\mathbb{E}V_j=\mathbb{E}e^{itF_j},\qquad M_0=1. \tag*{(35)}

The middle equality follows from (33) by averaging separately on each event {Lj=l}\{L_j=l\}. We prove the recurrence

Mj≤κ(t)2Mj−1+(1−κ(t)2)δ.(36)M_j\le\kappa(t)^2M_{j-1}+\left(1-\kappa(t)^2\right)\delta. \tag*{(36)}

Bad positions. On Ωj∩{Lj−1=l}\Omega_j\cap\{L_{j-1}=l\} one has Lj=l<jL_j=l<j. For l≥1l\ge1, the position ll is good; therefore (29) implies Ck,j=0C_{k,j}=0 there whenever k≤lk\le l. Each remaining term of Fj−Fj−1F_j-F_{j-1} does not depend on Y1,…,YlY_1,\ldots,Y_l. The same assertion is vacuous when l=0l=0. Moreover, the event under consideration is itself independent of Y1,…,YlY_1,\ldots,Y_l. Factoring the increment out of the corresponding average in (34) gives

Vj=eit(Fj−Fj−1)Vj−1on Ωj.(37)V_j=e^{it(F_j-F_{j-1})}V_{j-1}\quad\text{on }\Omega_j. \tag*{(37)}

Thus the bad part preserves the squared modulus:

E[1Ωj∣Vj∣2]=E[1Ωj∣Vj−1∣2].(38)\mathbb{E}\left[\mathbf{1}_{\Omega_j}|V_j|^2\right]=\mathbb{E}\left[\mathbf{1}_{\Omega_j}|V_{j-1}|^2\right]. \tag*{(38)}

Good positions. On Ωjc\Omega_j^c all the terms Ck,jC_{k,j} vanish and Lj=jL_j=j. Because Ωj\Omega_j depends on neither XjX_j nor YjY_j, and is also independent of Y<jY_{<j}, it follows that

Vj=eitAjEYj[eitXjYjPj−1eitFj−1]on Ωjc.(39)V_j=e^{itA_j}\mathbb{E}_{Y_j}\left[e^{itX_jY_j}P_{j-1}e^{itF_{j-1}}\right]\quad\text{on }\Omega_j^c. \tag*{(39)}

The following conditional averaging identity is useful:

Pj−1eitFj−1=Pj−1Vj−1.(40)P_{j-1}e^{itF_{j-1}}=P_{j-1}V_{j-1}. \tag*{(40)}

To verify it, set Z=eitFj−1Z=e^{itF_{j-1}} and Γl={Lj−1=l}\Gamma_l=\{L_{j-1}=l\}. Since Γl\Gamma_l does not depend on Y≤lY_{\le l},

Pj−1(1ΓlPlZ)=Pj−1Pl(1ΓlZ)=Pj−1(1ΓlZ).P_{j-1}(1_{\Gamma_l}P_lZ)=P_{j-1}P_l(1_{\Gamma_l}Z)=P_{j-1}(1_{\Gamma_l}Z).

Summing over l=0,…,j−1l=0,\ldots,j-1 proves (40).

For a function vv on {−1,1}\{-1,1\}, define

(Ktv)(x)=12∑y=±1eitxyv(y).(K_tv)(x)=\frac{1}{2}\sum_{y=\pm1}e^{itxy}v(y).

On the two-dimensional Hilbert space with uniform probability measure, its matrix is

12(eite−ite−iteit).\frac{1}{2}\begin{pmatrix} e^{it} & e^{-it} \\ e^{-it} & e^{it} \end{pmatrix}.

The vectors (1,1)(1,1) and (1,−1)(1,-1) are orthogonal eigenvectors, with eigenvalues cos⁡t\cos t and isin⁡ti\sin t, respectively. Hence

∥Kt∥2→2=κ(t).(41)\lVert K_t\rVert_{2\to2}=\kappa(t). \tag*{(41)}

For fixed (W,X<j,Y>j)(W,X_{<j},Y_{>j}), the function Pj−1Vj−1P_{j-1}V_{j-1} depends on YjY_j but not on XjX_j. Apply (41) to (39), use (40), and then apply conditional Jensen. This gives

E[1Ωjc∣Vj∣2]≤κ(t)2E[1Ωjc∣Pj−1Vj−1∣2]≤κ(t)2E[1Ωjc∣Vj−1∣2].(42)\begin{aligned} \mathbb{E}[1_{\Omega_j^c}|V_j|^2]\leq\kappa(t)^2\mathbb{E}[1_{\Omega_j^c}|P_{j-1}V_{j-1}|^2] \\ &\leq\kappa(t)^2\mathbb{E}[1_{\Omega_j^c}|V_{j-1}|^2]. \tag*{(42)} \end{aligned}

The independence of Ωj\Omega_j from the variables being averaged is essential in both inequalities. Combining (38) and (42), we obtain

Mj≤κ(t)2Mj−1+(1−κ(t)2)E[1Ωj∣Vj−1∣2]≤κ(t)2Mj−1+(1−κ(t)2)δ.M_j\leq\kappa(t)^2M_{j-1}+(1-\kappa(t)^2)\mathbb{E}[1_{\Omega_j}|V_{j-1}|^2]\leq\kappa(t)^2M_{j-1}+(1-\kappa(t)^2)\delta.

This proves (36). Starting from M0=1M_0=1, induction gives

MN≤δ+(1−δ)κ(t)2N.M_N\leq\delta+(1-\delta)\kappa(t)^{2N}.

By (35) and Cauchy–Schwarz, ∣EeitF∣2=∣EVN∣2≤MN|\mathbb{E}e^{itF}|^2=|\mathbb{E}V_N|^2\leq M_N, proving (30).

To deduce (31), put θ=1−δ\theta=1-\delta and t=1/(2N)t=1/(2\sqrt{N}). Then 0<t≤1/20<t\leq1/2, so κ(t)=cos⁡t\kappa(t)=\cos t. The inequality cos⁡t≤e−t2/2\cos t\leq e^{-t^2/2} on this interval implies

κ(t)2N≤e−1/4<45,∣EeitF∣≤1−θ/5≤1−θ/10.\kappa(t)^{2N}\leq e^{-1/4}<\frac{4}{5},\qquad|\mathbb{E}e^{itF}|\leq\sqrt{1-\theta/5}\leq1-\theta/10.

Consequently,

E(1−cos⁡(tF))≥θ/10.(43)\mathbb{E}(1-\cos(tF))\geq\theta/10. \tag*{(43)}

Set z=θN/4z=\sqrt{\theta N}/4. On {∣F∣<z}\{|F|<z\}, 1−cos⁡(tF)≤t2z2/2=θ/1281-\cos(tF)\leq t^2z^2/2=\theta/128; everywhere it is at most 22. Thus (43) yields

P{∣F∣≥z}≥12(θ10−θ128)=59θ1280≥θ25.\mathbb{P}\{|F|\geq z\}\geq\frac{1}{2}\left(\frac{\theta}{10}-\frac{\theta}{128}\right)=\frac{59\theta}{1280}\geq\frac{\theta}{25}.

This completes the proof.

Remark 8. The estimate P(Ωi)≤δ\mathbb{P}(\Omega_i)\leq\delta in the lemma is unconditional: no bound on P(Ωi∣W)\mathbb{P}(\Omega_i\mid W) is required. All energy estimates are integrated over WW. This distinction is needed when the lemma is applied after retaining only some of the Rademacher variables.

Proof of the Haar distributional estimate

We now apply Lemma 7 to prove Theorem 4. We retain suitably separated pairs of Rademacher variables and include all remaining digits in the auxiliary variable WW. The main task is to express the Haar expansion in the form (28) and verify the hereditary vanishing condition (29).

Proof of Theorem 4. Let m=ℓ+1m=\ell+1 and θ=1−δ\theta=1-\delta. For R∈Dℓ+s,aR\in\mathcal{D}_{\ell+s,a} put βR=αR−2−s\beta_R=\alpha_R-2^{-s}. Thus βR=0\beta_R=0 on good rectangles. Using the regular sums HkH_k from (10), put

C=∑s=0S∑a=0ℓ+s∑R∈Bℓ+s,aβRhR.C=\sum_{s=0}^{S}\sum_{a=0}^{\ell+s}\sum_{R\in\mathcal{B}_{\ell+s,a}}\beta_R h_R.

Then

f=g+∑s=0S2−sHℓ+s+C(44)f=g+\sum_{s=0}^{S}2^{-s}H_{\ell+s}+C \tag*{(44)}

The sum CC contains every bad correction, without alteration or truncation. Recall the Rademacher representation (11). For the principal level write

ξi=εi(x),ηi=εm+1−i(y)(1≤i≤m).(45)\xi_i=\varepsilon_i(x),\qquad\eta_i=\varepsilon_{m+1-i}(y)\qquad(1\leq i\leq m). \tag*{(45)}

These 2m2m signs are independent and uniform, and Hℓ=∑i=1mξiηiH_\ell=\sum_{i=1}^{m}\xi_i\eta_i.

Fix an integer K≥0K\geq0 and retain every (K+1)(K+1)st principal pair of signs (ξi,ηi)(\xi_i,\eta_i). This ensures that no regular term from the first KK finer levels contains two retained signs. The remaining regular levels will be estimated in L2L_2. Specifically, retain the indices

pi=1+(i−1)(K+1),1≤i≤N,N=⌊mK+1⌋.p_i=1+(i-1)(K+1),\qquad1\leq i\leq N,\qquad N=\left\lfloor\frac{m}{K+1}\right\rfloor.

Set Xi=ξpiX_i=\xi_{p_i} and Yi=ηpiY_i=\eta_{p_i}. Let WW consist of all the other binary digits of xx and yy, i.e., all digits excluding those at positions pip_i in xx and m+1−pim+1-p_i in yy, 1≤i≤N1\leq i\leq N.

Except on the null set of ambiguous binary expansions, this identifies Lebesgue measure with the product of the retained independent signs and WW. It also accommodates the measurable summands u(x)u(x) and v(y)v(y).

Remove the regular tail only:

RK=∑s=K+1S2−sHℓ+s,G=f−RK(46)R_K=\sum_{s=K+1}^{S}2^{-s}H_{\ell+s},\qquad G=f-R_K \tag*{(46)}

where the sum is zero if S≤KS\leq K. We verify the representation (28) and the vanishing condition (29) for GG.

The principal term. The retained terms of HℓH_\ell are ∑i=1NXiYi\sum_{i=1}^{N}X_iY_i. Its other terms depend only on WW and are included in A0A_0.

The remaining regular finer levels. Consider Hℓ+sH_{\ell+s} with 1≤s≤min⁡{K,S}1\leq s\leq\min\{K,S\}. A summand in (11) is εj(x)εm+s+1−j(y)\varepsilon_j(x)\varepsilon_{m+s+1-j}(y). If both factors have indices represented in (45), it is ξjηj−s\xi_j\eta_{j-s}. For 1≤s≤K1\leq s\leq K, these two distinct indices cannot both be retained, since distinct retained indices are at least K+1K+1 apart. If a factor has an index outside the principal range, it is already a component of WW. Thus every term is constant or depends on a single retained sign, with a coefficient depending on WW. Such terms can be included among the AiA_i: a function of XiX_i can be assigned to AiA_i, and a function of YiY_i to Ai−1A_{i-1}.

Coarser terms. We now consider the terms collected in gg: the tensor Haar terms supported on rectangles of area greater than 2−ℓ2^{-\ell} and v(y)v(y). For a rectangle with side lengths 2−a2^{-a} and 2−b2^{-b}, hRh_R depends only on the first a+1a+1 binary digits of xx and the first b+1b+1 binary digits of yy. In the ordering (45), it is therefore a function of WW and the signs

{Xi:pi≤a+1}and{Yi:pi≥m−b}.(47)\{X_i:p_i\le a+1\}\quad\text{and}\quad\{Y_i:p_i\ge m-b\}. \tag*{(47)}

If a+b<ℓ=m−1a+b<\ell=m-1, then a+1<m−ba+1<m-b, so the two retained segments in (47) are disjoint. Thus there is an index jj such that the term depends only on (W,X≤j,Y>j)(W,X_{\le j},Y_{>j}), and it can be included in AjA_j. Also u(x)u(x) depends only on (W,X≤N)(W,X_{\le N}), and v(y)v(y) only on (W,Y≥1)(W,Y_{\ge1}); they can be assigned to ANA_N and A0A_0.

Bad corrections. Consider a term βRhR\beta_R h_R with βR≠0\beta_R\ne0 and side lengths 2−a,2−b2^{-a},2^{-b}. Put

j=max⁡{i:pi≤a+1},k=min⁡{i:pi≥m−b},j=\max\{i:p_i\le a+1\},\qquad k=\min\{i:p_i\ge m-b\},

with the conventions j=0j=0 or k=N+1k=N+1 when the corresponding set is empty. By (47), the term is measurable with respect to (W,X≤j,Y≥k)(W,X_{\le j},Y_{\ge k}). If j<kj<k, then Y≥kY_{\ge k} is a subcollection of Y>jY_{>j}, so the term depends only on (W,X≤j,Y>j)(W,X_{\le j},Y_{>j}) and is included in AjA_j. If k≤jk\le j, it is included in Ck,jC_{k,j}.

This completes the decomposition of GG in the form (28). It remains to define the bad events Ωi\Omega_i and verify their measurability, probability bounds, and the vanishing condition (29).

For each retained index ii, let Ωi\Omega_i be the event that the principal rectangle of shape

∣I∣=2−(pi−1),∣J∣=2−(m−pi)|I|=2^{-(p_i-1)},\qquad|J|=2^{-(m-p_i)}

containing (x,y)(x,y) is bad. Membership in that rectangle depends only on the first pi−1p_i-1 digits of xx and the first m−pim-p_i digits of yy. Therefore

Ωi∈σ(W,X<i,Y>i),P(Ωi)=2−ℓ#Bℓ,pi−1≤δ.(48)\Omega_i\in\sigma(W,X_{<i},Y_{>i}),\qquad\mathbb{P}(\Omega_i)=2^{-\ell}\#\mathcal{B}_{\ell,p_i-1}\le\delta. \tag*{(48)}

If k≤i≤jk\le i\le j, then pi≤a+1p_i\le a+1 and pi≥m−bp_i\ge m-b. Consequently, RR is contained in its unique principal ancestor of the shape associated with pip_i. Since βR≠0\beta_R\ne0, RR is bad, so this ancestor must be bad by heredity. It follows that

1ΩicβRhR=0(k≤i≤j).\mathbf{1}_{\Omega_i^c}\beta_Rh_R=0\qquad(k\le i\le j).

Summing over all terms assigned to Ck,jC_{k,j} gives

1ΩicCk,j=0(k≤i≤j).\mathbf{1}_{\Omega_i^c}C_{k,j}=0\qquad(k\le i\le j).

This verifies (29). All remaining dependence on the unretained digits is included in WW.

Lemma 7 now applies to GG. Since N≥m/(K+1)N\ge m/(K+1),

λ2{∣G∣≥θm4K+1}≥θ25.(49)\lambda_2\left\{|G|\ge\frac{\sqrt{\theta m}}{4\sqrt{K}+1}\right\}\ge\frac{\theta}{25}. \tag*{(49)}

For the tail, orthogonality gives ∥Hℓ+s∥22=m+s\|H_{\ell+s}\|_2^2=m+s, and different levels are orthogonal. Hence

∥RK∥22≤∑s=K+1∞(m+s)4−s≤m∑s=K+1∞(s+1)4−s.(50)\|R_K\|_2^2\le\sum_{s=K+1}^{\infty}(m+s)4^{-s}\le m\sum_{s=K+1}^{\infty}(s+1)4^{-s}. \tag*{(50)}

With zK=θm/(8K+1)z_K=\sqrt{\theta m}/(8\sqrt{K}+1), Chebyshev’s inequality gives

λ2{∣RK∣≥zK}≤64(K+1)θ∑s=K+1∞(s+1)4−s.\lambda_2\{|R_K|\ge z_K\}\le\frac{64(K+1)}{\theta}\sum_{s=K+1}^{\infty}(s+1)4^{-s}.

Since

{∣G∣≥2zK}∖{∣RK∣≥zK}⊆{∣f∣≥zK},\{|G| \ge2z_K\} \setminus\{|R_K| \ge z_K\} \subseteq\{|f| \ge z_K\},

these estimates and the identity

∑s=K+1∞(s+1)4−s=3K+79⋅4K\sum_{s=K+1}^{\infty} (s+1)4^{-s} = \frac{3K+7}{9 \cdot4^K}

prove (25).

If δ≤1/2\delta\le1/2, the hypotheses also hold with δ=1/2\delta= 1/2. Taking K=10K = 10 in (25), we obtain

λ2{∣f∣≥m822}≥150−40773728>1100.\lambda_2\left\{|f| \ge\frac{\sqrt{m}}{8\sqrt{22}}\right\} \ge\frac{1}{50} - \frac{407}{73728} > \frac{1}{100}.

This proves (26).

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process

The author formulated the main ideas and the proof strategy, including the representation of Haar functions by random variables and the use of an averaging lemma. Over several years, the author made repeated attempts to implement this approach but was unable to resolve the technical difficulties needed for a complete proof of the result now stated as Lemma 7. The part of the argument dealing with the incorporation of the coarse Haar levels had already been developed by the author but remained unpublished. ChatGPT (OpenAI) was used to develop the technical details needed to incorporate the finer levels and complete the proof within this framework, and to assist with literature searches, the exposition, and the preparation of the LaTeX source. The author critically reviewed and revised the generated material, verified the proofs and references, and takes full responsibility for the content of the manuscript.

References

  1. [1]D. Bilyk, On Roth’s orthogonal function method in discrepancy theory, Uniform Distribution Theory 6 (2011), no. 1, 143–184. https://www-users.cse.umn.edu/~dbilyk/papers/bilyk-survey.pdf.
  2. [2]W. W. L. Chen, On irregularities of distribution, Mathematika 27 (1980), no. 2, 153–170.DOI
  3. [3]H. Davenport, Note on irregularities of distribution, Mathematika 3 (1956), 131–135.DOI
  4. [4]G. Halász, On Roth’s method in the theory of irregularities of point distributions, in: Recent Progress in Analytic Number Theory, Vol. 2 (Durham, 1979), Academic Press, London, 1981, pp. 79–94.
  5. [5]K. F. Roth, On irregularities of distribution, Mathematika 1 (1954), 73–79.DOI
  6. [6]W. M. Schmidt, Irregularities of distribution. X, in: Number Theory and Algebra (H. Zassenhaus, ed.), Academic Press, New York, 1977, pp. 311–329.

Paper details

vlnc:W_j4gm87x7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT (OpenAI)

View statement
Looking for related papers…
Contents