2
$\begingroup$

I've been reading about discrepancy theory and trying to understand some of the open problems in the field. Wikipedia has a list of some of the open problems, but the descriptions are terrible. In particular, I am curious about:

"Axis-parallel rectangles in dimensions three and higher (folklore)"

Curious if anyone knows what problem the author was referring to, i.e. if this is some famous topic that everyone in discrepancy knows of and if there is a good reference to look at? (Or is the above quote just nonsense?)

$\endgroup$

1 Answer 1

2
$\begingroup$

Perhaps the issue is to establish a tight lowerbound for the discrepancy of $n$ points in dimension $d$ with respect to $d$-dimensional boxes. In

Matousek, Jiri, ed. Geometric discrepancy: An illustrated guide. Vol. 18. Springer Science & Business Media, 2009,

after discussing the planar case, where the optimal $\Omega( \log n)$ bound is established, Matousek says for $d$-dimensional boxes (p.176),

       Matousek

In particular, perhaps the $\tfrac{1}{2}$ in the exponent $\tfrac{d-1}{2}$ is not needed (as it is not needed in $d=2$). But this book is now a decade old. I am not certain of the current status.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.