1999 | OriginalPaper | Chapter
More Lower Bounds and the Fourier Transform
Author : Jiří Matoušek
Published in: Geometric Discrepancy
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In the previous chapters, we have seen several approaches to lower bounds in combinatorial and geometric discrepancy. Here we are going to discuss another, very powerful method developed by Beck, based on the Fourier transform. Although one can argue that, deep down, this method is actually related to eigenvalues and proofs using orthogonal or near-orthogonal functions, proofs via the Fourier transform certainly look different, being less geometric and more akin to classical harmonic analysis. For many results obtained by this method, such as the tight lower bound for the discrepancy for discs of a single fixed radius, no other proofs are known.