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:

Theorem 1 (Roth ’54)For all dimensions and all point distributions , we have that

We have the corresponding theorem in , originally due to Schmidt:

Theorem 2 (Schmidt ’77)For all dimensions and all point distributions , we have thatfor all .

These theorems are sharp as to the order of magnitude. In particular we have the following theorem:

Theorem 3 (Davenport ’56)Let and . For any positive integer , there exists a point distribution such that

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 thatThis 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

We set

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

the previous calculation shows

which in turn implies that

so that .

** 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

and

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.

Theorem 4Let be a real number and a large positive integer. We have that

*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).

Remark 3To make the previous argument rigorous on needs to make an explicit choice of the constant and prove that

One way to do that is the following. Fro classical estimates we have thatwhere 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

Corollary 5Let and be any checkerboard coloring of the infinite Euclidean plane. There exists a constant and a circle of radius , where is equal to either or , such that

*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

since .

**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:

Theorem 6For every radius and every coloring of the infinite checkerboard there existsa circular arc, of radius , withwhere 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 small real parameter. Now using the asymptotic expansion of it is easy to see that

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

Using (4) and (3) we can write for every small parameter the estimate

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:

Proposition 7For consider any ball and let . Fix a finite sequence

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

where by (4) and (3) we see that is either or and tha in every case we have

so for , where is some numerical constant, the hypotheses of the proposition are satisfied. We thus get

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

and

so that . Thus the last estimate can be written in the form

We integrate the previous inequality for . For the left hand side 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 :

Observe that

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 8Is it true thatfor everythere is afull circlewith discrepancy ? In particular, is it true thatfor 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 9Construct 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 10Is it true thatfor 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.