Nils Hebbinghaus, Tomasz Schoen, Anand Srivastav:

One-Sided Discrepancy of Linear Hyperplanes in Finite Vectorspaces

In this paper we investigate the $c$--color discrepancy, $c\geq 2$ and the one-sided $c$--color discrepancy of linear hyperplanes in the finite vector space $\mathbb{F}_{q}^{r}$. We denote by ${\mathcal H}$ the hypergraph with vertex set $\mathbb{F}_{q}^{r}$ and all linear hyperplanes (i.e. subspaces of codimension $1$) in $\mathbb{F}_{q}^{r}$ as hyperedges. We show that the discrepancy of ${\mathcal H}$ is $\Theta_{q}\left(\sqrt{nz(1-z)}\right)$, where $n= ¦\mathbb{F}_{q}^{r} ¦$ and $z=\tfrac{(q-1)\mod c}{c}$. With Fourier analysis on $\mathbb{F}_{q}^{r}$ we further prove that the one-sided discrepancy of ${\mathcal H}$ is bounded from below by $\Omega_{q}\left(\sqrt{\tfrac{nz(1-z)}{c}}\right)$ which differs from the upper bound by a factor of $\sqrt{c}$. For large $c$, i.e. $c\geq qn^{1/3}$ we close the gap proving a $\Theta_{q}\left(\sqrt{\tfrac{n}{c}}\right)$ behaviour of the one-sided discrepancy. All together this exhibits a new example for a hypergraph with (almost) tight discrepancy bounds.

Mathematics Subject Classification (1991): 11K38

Keywords: Discrepancy, finite vectorspaces, Fourier analysis

Mail an Jens Burmeister

[Thu Feb 19 18:56:36 2009]

Impressum