This week I am giving a talk at the Department of Mathematics and Systems Analysis of Aalto University where I will discuss results from a recent paper with Mihalis Kolountzakis. I will give a short introduction to different notions of discrepancy together with a description of the main set-up and results in the checkerboard setting. I will also describe our main questions and results and some further problems related to checkerboard colorings. Our work with Mihalis Kolountzakis is a natural continuation of the previous papers [K], [IK] where similar questions have been considered. In fact our current papers answers some of the questions posed by Kolountzakis and Iosevich in [IK].
1. Notions of Discrepancy
I will begin this post by briefly recalling some notions of discrepancy that have been extensively studied in the literature, namely geometric and combinatorial discrepancy. I will close this introduction by describing the set-up for our current topic, that is discrepancy of sets on checkerboards. This notion was introduced by Kolountzakis in [K]. Although the notion has some characteristics in common with the two notions of discrepancy just mentioned, it can not be put in the context of either one. Thus some new definitions and investigations are necessary.
1.1. Geometric Discrepancy
This refers to the following set-up. Consider the unit cube and let
be an -point set in . Now consider to be a family of sets such as rectangles, circles, convex polygons and so on. We are interested in studying the discrepancy of the point set with respect to the family . For we set
Here denotes the Lebesgue measure of a set . We are interested in the absolute value of the quantity above which describes the difference of the actual number of points of in minus the expected number of points in . Thus only the part of the set that lies inside is relevant. The -discrepancy is just the supremum over all sets :
A point distribution with `small’ discrepancy can be used to approximate the volume of any by the average . Let us now give a more concrete example by specializing the family to be the family of all rectangles contained in with one corner anchored at the origin and another corner in the interior of . For we write
for the rectangle anchored at and at . Let be an -point distribution in . The star or corner discrepancy is then defined as:
It turns out that the `size’ of this function (in many different senses) must necessarily grow to infinity with The most typical manifestation of this claim is the following lower bounds which are essentially optimal:
We have the corresponding theorem in , originally due to Schmidt:
for all .
These theorems are sharp as to the order of magnitude. In particular we have the following theorem:
Constructing point distribution that are extremal for discrepancy is a delicate matter, especially in high dimensions. For more extremal constructions see [Roth '74, '80], [Chen '81].
A nice motivating application of geometric discrepancy is the Koksma-Hlawka inequality . Let be a function of bounded variation (in the sense of Hardy and Krause). Then
In dimension the variation of a function can be expressed as . In higher dimensions there is an expression for involving the partial derivatives of , assuming sufficient smoothness. Observe that if we replace by in the Koksma-Hlawka inequality, we recover the definition of the discrepancy function on the left hand-side.
Remark 1 (Highly structured sets are bad for discrepancy)
Here it is implied that the `structure’ is consistent with the axis-parallel nature of the discrepancy function. Let us for example consider for example a lattice in . Considering a very thin axis parallel rectangle of the form for some we see that , much worse than the bound from Davenport’s theorem.
Remark 2 (Random sets are bad) Let be chosen independently and uniformly in . Consider the rectangle . Then
which implies that
This in turn means that with high probability. Another way to express this is to observe that by the Central limit theorem we get that
The discrepancy of a random set is thus of the order , again much larger than the optimal point distribution discrepancy .
For a much more detailed discussion on star discrepancy you can also check this older post on my blog.
1.2. Combinatorial discrepancy
Let be a set of elements and be a family consisting of subsets of . A coloring of is a function and let us agree that corresponds to white colored points and corresponds to black colored points of . Given a family the goal here is to color the elements of in such a way so that any of the sets in contains roughly the same number of `black points’ and `white points’. As in the geometric set-up it turns out that this is in most of the interesting cases not possible.
The relevant combinatorial discrepancy is defined as
The corresponding discrepancy is then
Of course it makes sense to consider discrepancies in the obvious way. To give an example, if one considers as the family of all subsets of then the corresponding discrepancy is large, at least , no matter how clever we are in coloring the elements of . That is, there exists a subset of with
uniformly for all colorings On the other hand, a good upper bound is obtained by coloring the set randomly, that is, each is colored black or white with probability and independently of other points of . Then for any system of subsets of we have
for all sets simultaneously with probability at least .
1.3. Discrepancy for checkerboard colorings
Consider the Euclidean plane as a union of congruent cells
where . Now color each square in the union, black or white, in an arbitrary manner. This amounts to defining a function , where is constant on each one of the cells . We will call such a coloring a checkerboard coloring of the (infinite) Euclidean plane. Now let be a family of sets and for simplicity let us assume that consists of line segments. The question is whether one can choose a checkerboard coloring such that, for any line segment , the `white length’ of minus its `black length’ is bounded uniformly by an absolute constant. Note that the corresponding discrepancy here can be defined as
where is the arc-length measure on the segment , while the discrepancy
Like in many other similar questions in discrepancy theory it turns out that this is not possible. In particular there exist arbitrarily long line segments such that the discrepancy is at least for all checkerboard colorings of the plane. This is essentially best possible (up to an -loss): a random coloring has discrepancy about for every segment .
We will take up these issues in detail in the rest of this post. A general remark is the following. Although in most cases we want to prove lower bounds for a supremum like quantity, the -discrepancy, it is often more convenient to bound a corresponding average discrepancy. For this one has to place an appropriate measure on the family of sets . For example the set of lines can be parametrized by where is the one dimensional unit circle and there is the natural product measure on this space. The same principle holds for other types of geometric discrepancy.
2. The discrepancy of a line segment on a checkerboard
Like before we fix some checkerboard coloring where is constant on each cell , The family of sets consists of (finite) line segments of arbitrary position and length. We now translate the problem to a corresponding problem on a finite checkerboard as follows. Let where will be a large positive integer. Consider as a union of congruent cells as before:
A finite checkerboard coloring of is a function which is constant and identically equal to either or on each cell and identically zero on the complement of . We define the discrepancy
The main theorem proved in [K] says that for every large , there exists a line segment, contained in with discrepancy
Observe that this `finite checkerboard’ result implies the corresponding statement for the infinite coloring since can be arbitrarily large.
Let us parametrize the set of lines in the plane by their distance from the origin and the unit vector along the line. Thus any line can be described as
This is the discrepancy of the line segment with respect to the coloring . At the same time it is the Radon transform of , hence the notation In order to consider all possible line segments one has to vary and . For any consider the quantities
where denotes the normalized Lebesgue measure on . Finally observe that the measure of the support of is about so we define the normalized discrepancies
Now observe that Plancherel’s theorem and the Fourier slice theorem imply that
An easy calculation shows that
where is the (bi-variate) trigonometric polynomial
and is the color corresponding to the cell . Observing the elementary bound
2.1. Some remarks on discrepancies for .
Kolountzakis proves in [K] that for random colorings we have with high probability so, ignoring -losses, the for the -discrepancies we have
For one can use the convexity of the norms to get the bound
On the other hand consider a coloring where each one of the lines of the checkerboard has a single color and adjacent lines have different colors. It is then easy to check that
Thus, while the previous bounds are sharp for , the discrepancy can be much smaller, of the order . See the end of this post for some related open questions.
3. Discrepancy of a circle on a checkerboard
Here we consider the family consisting initially of all circles in the Euclidean plane, of any center and radius. For the infinite checkerboard problem this is an appropriate set-up. Translating the problem to the finite checkerboard requires some discussion in this case. Fix some large and a coloring of . In this set-up, it makes sense to restrict the radii of the circles considered to be at most of the order otherwise one can consider radius tending to infinity so that the circle essentially becomes a line with respect to the checkerboard scale which is . If is a circle the relevant discrepancy now is
where we integrate with respect to the arc-length measure on the circle . Remember that we have assumed that is identically zero outside . This means that the previous integral ignores circles that do not `hit’ the finite checkerboard . This is of no consequence when translating to the infinite set-up. However, the previous integral takes into account arcs as well as circles if no restriction is imposed on the centers and radii of the circles. Thus if we manage to find a circle of radius say such that
is large this only amounts to arc in the infinite checkerboard which has large discrepancy. This is a technical difficulty to which we will come back later on.
Let us now write down a convenient formula for the circle discrepancy. Fixing we set
where denotes the circle of center and radius and denotes the arc length measure on the circle . Note that is not normalized so that
In our considerations below we will only consider radii which implies that the measure of the support of is about . Thus we define the normalized discrepancy for any :
By Plancherel’s theorem we have as usual
The main tool for the study of the discrepancy is the classical asymptotic description of the Fourier transform of the arc-length measure on the circle. We have
Studying the asymptotic description of one easily sees that the main obstruction in proving a lower bound for are the zeros of which, as , become almost periodic. This problem was dealt with in [IK] by also averaging in the radial variable, in an interval of the form . Since the zeros of are isolated this provides a lower bound for which is of the order . However the bound in [IK] only implies a bound for arcs in the infinite checkerboard. Furthermore, as a result of the averaging in the radial variable, the radius of the arc is not specified exactly; it lies in some interval of the form .
Our first result answers the problem of finding a full circle with large discrepancy.
Proof: A sketch of the proof of this result is the following. A simple calculation as before shows that
Here is a positive constant to be chosen appropriately. Now assume, as we may, that behaves likes when is large, which corresponds to the term . The cosine term above is zero exactly when
From the previous expression of the (approximate) zeros of one readily sees that if some real number is a zero, say for some non-negative integer , then That is if is a zero then stays bounded away from the zeros of ; we get that
The estimate for is thus:
For one needs to note that for an appropriate choice of , the disk has a positive distance from the first zero of so that in that region. We get the better estimate
since . Summing the estimates for and we get
by another use of the basic estimate (1).
where is the -th order Bessel function and is an error term that satisfies . A direct computation then shows that (2) is valid whenever (say). For one can check directly the validity of (2) either by looking up the zeros of in a table or by drawing the graph of the function. Finally, by looking up the zeros of one checks again that the first zero of is so that has no zero for and the estimate for is also valid. Thus the previous argument works for .
Using Theorem 4 we have the following easy corollary
Proof: Given consider the finite checkerboard with and the corresponding finite coloring . Theorem 4 then shows that
where has a fixed value equal to either or . Consider the cube . We have
4. Single radius discrepancy for arcs
The previous discussion answers our main question by showing that for every there exists a full circle of radius either or , with discrepancy . If there is an unsatisfying element in this result it is exactly that we cannot prove the corresponding statement for every radius . Observe that we did not completely avoid the averaging in the radial direction, albeit we only only averaged between two discrete values and . An attempt to deal with this problem is contained in the following discussion. In order to avoid the ambiguity in the choice of the radius of the circle with large discrepancy we replace the radial averaging with pointwise estimates. Our methods however only work under the restriction for the finite checkerboard. As a result, the simple argument of Corollary 5, which required , does not work any longer and our current methods only prove the following:
where is an absolute constant, independent of , and .
Once again we actually prove the corresponding lower bound for the discrepancy of the finite checkerboard. In particular we show that for we have
Here, the restriction is essential and results to the existence of an arc, instead of a full circle, in the infinite checkerboard with discrepancy The idea is the following. We write
Assuming arbitrarily large values of we can assume that the asymptotic description
is valid. We denote by
the roots of the cosine term as before. It will also be convenient to introduce a notation for annular neighbourhoods around the roots by setting
where is a large constant, which may depend on , which is chosen so that for the asymptotic expansion of is valid. On the other hand for we have no asymptotic description of be we now that its zeros are of the form where is a finite sequence without accumulation points. This can be seen by arguing via the -th order Bessel function as before, or, alternatively, by noting that is radial and can only have isolated zeros in the radial direction since it is the Fourier transform of a compactly supported measure. We conclude by compactness that
Setting the previous considerations imply that
Note that the implicit constant in the estimate above depends on the parameter which is yet to be chosen. The main idea to complete the proof is that for small enough , the integral
captures a positive proportion of the integral
This can be formulated more generally for any reasonable function as follows:
and set Define as before the annuli
Then for we have
Before giving the proof of this proposition let us see how we can use it to complete the proof of Theorem 6. We have
since . Thus for small enough, but not depending on any of the parameters of the problem. We now give the proof of Proposition 7.
Proof: } Fix and for consider the annulus with . For and we have
Using and Cauchy-Schwarz we get
Multiplying both sides by and integrating for and we have
Now for and we have
For the first term on the right hand side we estimate
since Finally, for the last term in the right hand side (5) we have
Summing up the previous estimates we get for every :
Summing the previous estimates for we get
Now adding the term to both sides of the estimate above gives the claim of the proposition.
5. Some open questions
We close the discussion on the discrepancy for checkerboard colorings by summarizing some of the open questions that we alluded to earlier:
Question 8 Is it true that for every there is a full circle with discrepancy ? In particular, is it true that
for all ?
We believe that yes but the methods discussed here do not seem to be sufficient to prove such a result.
Consider the discrepancies of circles defined in the obvious way
As we just saw we have for all , at least whenever .
Question 9 Construct a coloring with , such that . A simple interpolation argument shows that if then we have
Is this best possible? (probably yes). What is the correct order of magnitude of ?
Consider the discrepancy of a segment on a checkerboard defined above:
and the corresponding discrepancies
As we saw in the introduction we have the bounds (up to -losses)
The following question is open:
Question 10 Is it true that
for any coloring of the finite checkerboard? Failing that, one could try to show that we have
for any coloring .
[IK] Alex Iosevich and Mihail N. Kolountzakis, The discrepancy of a needle on a checkerboard. II, Unif. Distrib. Theory 5 (2010), no. 2.
[K] Mihail N. Kolountzakis, The discrepancy of a needle on a checkerboard, Online J. Anal. Comb. 3 (2008), Art.7, 5.
[KP] Mihail N. Kolountzakis and Ioannis Parissis, Circle Discrepancy for Checkerboard measures, (2012), preprint, arXiv:1201.5544.