WorksMathematics
A Sharp Distributional Lower Bound for Planar Discrepancy
Abstract
We prove that the unnormalized discrepancy function of every -point set in the unit square has absolute value at least on a set of measure at least , with absolute constants . Consequently, its -quasinorm is bounded below by for every .
Introduction and main results
Let be a set of points in . Its unnormalized discrepancy function is
The main purpose of this note is to show that exceeds a constant multiple of on a set of uniformly positive measure. To state this precisely, define, for ,
where denotes Lebesgue measure on . Throughout, denotes the natural logarithm. Our main result is
Theorem 1. There exist constants such that for every and every -point set ,
An immediate consequence is the following lower bound for the -(quasi-)norm, defined for by
Corollary 2. For every , every -point set , and every ,
where and 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 for the -norm in [5]. His proof also gives the sharp lower bound of order for the -norm in general dimension . Schmidt extended this lower bound of order to the -norm in the range in [6], also with the corresponding lower bound in general dimension. For , the same lower bound follows directly from Roth’s estimate by monotonicity of the -norms. Halász proved the corresponding estimate for the -norm in [4]. His argument does not yield the corresponding lower bound of order in dimensions . Obtaining the corresponding lower bound of order in dimensions remains a major open problem in discrepancy theory.
The classical construction of Davenport in [3] gives a sequence of point sets in with discrepancy of order for the -norm. By monotonicity of the -(quasi-)norms, the same point sets satisfy an upper bound of order for every . This proves optimality for . For the remaining range , Chen [2] proved that, for every , there exists an -point set satisfying
Thus Corollary 2 is optimal in its order of growth in for every fixed . For a discussion of suitable modifications of the van der Corput point set, see [1 Section 6]. Similarly, the upper bound and Chebyshev’s inequality show that the scale 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 , then the corresponding Haar coefficient depends only on 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 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 be the collection of dyadic intervals
For , let denote its length and and its left and right halves. Define the Haar function with support by
For a dyadic rectangle , put and . These tensor Haar functions are pairwise orthogonal and satisfy
For , we use the Haar expansion coefficients
Thus is distinguished from the unnormalized inner product . Together with the constant function and the one-variable functions and , the functions form a complete orthogonal system in . In particular, every real has a decomposition
with convergence in . Here contain the constant and one-variable components; the allocation of the constant term does not matter.
For integers and , define
Each collection partitions into rectangles of area . We call the shape index and 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 be a dyadic rectangle and put . Then
In particular, if the interior of contains no point of , then
Proof. The contribution of to the counting function is . Hence Fubini’s theorem gives
Moreover,
Dividing the difference by proves (2.2). The function vanishes outside the interior of , including at its endpoints. Consequently every point contribution vanishes when the interior of is empty, which proves (2.3).
Choose the unique integer such that
For each and , let
be the collection of bad rectangles. The remaining rectangles in are called good. Since rectangles of a fixed shape and level are disjoint,
In particular, the union of the bad rectangles of any principal shape has measure at most . 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 is an ancestor of if ; 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
Lemma 3 yields
The coefficients on bad rectangles need not satisfy this identity.
The regular sums and the Rademacher model
Define the regular sum at level by
Let be the th Rademacher function on , with value when the th binary digit of the argument is zero and when it is one. Summing the Haar functions over all rectangles of one shape gives
For fixed , 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,
Different levels are orthogonal, although they need not be independent.
To identify precisely how the discrepancy function differs from these regular sums, let consist of the constant and one-variable components of , together with its mixed Haar terms of levels . For put . The truncation of the expansion of at level can then be written as
Since , completeness and orthogonality imply in as . The principal regular sum is exactly a sum of independent signs, and is comparable to . The remaining terms have different roles. The coarser part has a restricted dependence on the binary digits, the regular finer levels have geometrically decreasing coefficients, and the corrections 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 bound, the product Littlewood–Paley inequality yields the bounds for , and a bounded complex Riesz product gives the 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 and the number from (2.4), and put . For every good rectangle in the principal level, Lemma 3 gives
Each principal shape contains at least good rectangles. Hence orthogonality and Bessel’s inequality yield
Since , we obtain Roth’s planar lower bound
Schmidt’s bound via the Littlewood–Paley inequality
For , define its mixed dyadic square function by
For every , the product Littlewood–Paley inequality gives a constant such that
see [1 Section 3]. To account explicitly for the one-variable terms, let and denote averaging in the respective coordinates and put . Then , and the product Littlewood–Paley inequality applied to gives , which yields (3.2).
Let
count the good principal rectangles containing a given point. Since at least half of the rectangles of each shape are good,
Consequently, the set has measure at least : indeed,
On , the good principal coefficients give
Applying (3.2), we obtain
This recovers Schmidt’s planar lower bound for every . The restriction on enters only through the Littlewood–Paley inequality.
Halász’s bound via a complex Riesz product
For , define
These functions satisfy . By Lemma 3 and the count of good rectangles,
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 and ,
Indeed, , 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 , while the absolute volume contributions sum to .
For distinct indices , with , the product is a Haar sum over rectangles with side lengths and , with coefficients in . 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
Set , , and
Since ,
The linear term is , and its pairing with the discrepancy function is at least by (3.4). The remaining terms have odd degree at least three.
For a fixed span , there are choices of the endpoints and choices of the interior indices. Thus (3.6) yields
Here we bounded the sum over odd degrees by the sum over all degrees at least three. Since ,
It follows that
Using (3.7), we obtain
A distributional estimate for Haar expansions
The preceding arguments establish the lower bounds for , but do not directly extend to . 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 and a finite depth . For and , designate a collection of bad rectangles. The remaining rectangles are called good.
Theorem 4. Let . Suppose that the good rectangles are hereditary among the levels under consideration and
Let
:::`
where is the sum of a finite real linear combination of tensor Haar functions supported on rectangles of area greater than and arbitrary real measurable functions , finite almost everywhere. Assume
The bad coefficients are arbitrary real numbers. Then, for every integer ,
In particular, when ,
Remark 5. Apart from heredity, no restriction is imposed on the finer bad collections. For every fixed , the right-hand side of (25) is positive for all sufficiently large . 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 in measure on . If, for some and ,
then
In particular, for fixed and , every bound in Theorem 4 passes to limits in measure of finite expansions satisfying its hypotheses.
Proof. Suppose in measure and for every . For every ,
Letting and then gives .
Application to the discrepancy function
Proof of Theorem 1. Use the level , the number , and the rescaled function from § 2. As shown there, the good rectangles are hereditary, the principal bad proportion is less than , and the coefficients on good rectangles have the values required by Theorem 4.
The truncations from (13) therefore satisfy (26). Since in , hence in measure, Proposition 6 gives
Rescaling and using , we obtain
Finally, (6) implies
This proves Theorem 1, with and .
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 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 variables and uses an contraction at each good position.
The additional random variable 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, collects the binary digits not selected as or . The estimates are then integrated over ; the bounds on the probabilities of bad positions are required only for the full probability space, not for each fixed value of .
We write , , and , with the analogous conventions for strict initial and closed terminal segments. A segment may be empty.
Lemma 7. Let , and let be independent uniform signs, independent also of . Suppose the real random variable has the representation
Let denote the measurable space in which takes values. The functions
are measurable. Their arguments are ordered as in (28), and is understood to be a singleton. Fix . Let be measurable with respect to , with . Suppose
We call position good on and bad on . Thus an interaction vanishes whenever a position between and , inclusive, is good. Then, for every real ,
Furthermore,
The proof has a martingale flavour. Averaging over successive variables gives conditional expectations with respect to a decreasing family of -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 contraction at good positions, together with preservation of the squared modulus at bad positions, then yields the required estimate.
Proof. Let denote the partial sum in (28) through index , with . Let average only , keeping , all variables, and fixed; is the identity operator. At each step, we average the variables up to the last good position. This preserves the expectation while allowing an contraction at each new good position. For , define
If , the event equals ; for it equals . Hence
In particular, this event does not depend on the variables averaged by . Define
These quantities are well-defined even when is not integrable, since its complex exponential has modulus one. We have
The middle equality follows from (33) by averaging separately on each event . We prove the recurrence
Bad positions. On one has . For , the position is good; therefore (29) implies there whenever . Each remaining term of does not depend on . The same assertion is vacuous when . Moreover, the event under consideration is itself independent of . Factoring the increment out of the corresponding average in (34) gives
Thus the bad part preserves the squared modulus:
Good positions. On all the terms vanish and . Because depends on neither nor , and is also independent of , it follows that
The following conditional averaging identity is useful:
To verify it, set and . Since does not depend on ,
Summing over proves (40).
For a function on , define
On the two-dimensional Hilbert space with uniform probability measure, its matrix is
The vectors and are orthogonal eigenvectors, with eigenvalues and , respectively. Hence
For fixed , the function depends on but not on . Apply (41) to (39), use (40), and then apply conditional Jensen. This gives
The independence of from the variables being averaged is essential in both inequalities. Combining (38) and (42), we obtain
This proves (36). Starting from , induction gives
By (35) and Cauchy–Schwarz, , proving (30).
To deduce (31), put and . Then , so . The inequality on this interval implies
Consequently,
Set . On , ; everywhere it is at most . Thus (43) yields
This completes the proof.
Remark 8. The estimate in the lemma is unconditional: no bound on is required. All energy estimates are integrated over . 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 . 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 and . For put . Thus on good rectangles. Using the regular sums from (10), put
Then
The sum contains every bad correction, without alteration or truncation. Recall the Rademacher representation (11). For the principal level write
These signs are independent and uniform, and .
Fix an integer and retain every st principal pair of signs . This ensures that no regular term from the first finer levels contains two retained signs. The remaining regular levels will be estimated in . Specifically, retain the indices
Set and . Let consist of all the other binary digits of and , i.e., all digits excluding those at positions in and in , .
Except on the null set of ambiguous binary expansions, this identifies Lebesgue measure with the product of the retained independent signs and . It also accommodates the measurable summands and .
Remove the regular tail only:
where the sum is zero if . We verify the representation (28) and the vanishing condition (29) for .
The principal term. The retained terms of are . Its other terms depend only on and are included in .
The remaining regular finer levels. Consider with . A summand in (11) is . If both factors have indices represented in (45), it is . For , these two distinct indices cannot both be retained, since distinct retained indices are at least apart. If a factor has an index outside the principal range, it is already a component of . Thus every term is constant or depends on a single retained sign, with a coefficient depending on . Such terms can be included among the : a function of can be assigned to , and a function of to .
Coarser terms. We now consider the terms collected in : the tensor Haar terms supported on rectangles of area greater than and . For a rectangle with side lengths and , depends only on the first binary digits of and the first binary digits of . In the ordering (45), it is therefore a function of and the signs
If , then , so the two retained segments in (47) are disjoint. Thus there is an index such that the term depends only on , and it can be included in . Also depends only on , and only on ; they can be assigned to and .
Bad corrections. Consider a term with and side lengths . Put
with the conventions or when the corresponding set is empty. By (47), the term is measurable with respect to . If , then is a subcollection of , so the term depends only on and is included in . If , it is included in .
This completes the decomposition of in the form (28). It remains to define the bad events and verify their measurability, probability bounds, and the vanishing condition (29).
For each retained index , let be the event that the principal rectangle of shape
containing is bad. Membership in that rectangle depends only on the first digits of and the first digits of . Therefore
If , then and . Consequently, is contained in its unique principal ancestor of the shape associated with . Since , is bad, so this ancestor must be bad by heredity. It follows that
Summing over all terms assigned to gives
This verifies (29). All remaining dependence on the unretained digits is included in .
Lemma 7 now applies to . Since ,
For the tail, orthogonality gives , and different levels are orthogonal. Hence
With , Chebyshev’s inequality gives
Since
these estimates and the identity
prove (25).
If , the hypotheses also hold with . Taking in (25), we obtain
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]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]W. W. L. Chen, On irregularities of distribution, Mathematika 27 (1980), no. 2, 153–170.DOI
- [3]H. Davenport, Note on irregularities of distribution, Mathematika 3 (1956), 131–135.DOI
- [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]K. F. Roth, On irregularities of distribution, Mathematika 1 (1954), 73–79.DOI
- [6]W. M. Schmidt, Irregularities of distribution. X, in: Number Theory and Algebra (H. Zassenhaus, ed.), Academic Press, New York, 1977, pp. 311–329.