%rev 18/II/97 jm

\title{An $L_p$ version of the Beck-Fiala conjecture}
\newif\ifafour

\afourfalse

\ifafour
\documentstyle[11pt]{article}
\else
\documentstyle{article}
\fi




\ifafour
\addtolength{\textwidth}{2.8cm}
\addtolength{\textheight}{5cm}
\addtolength{\oddsidemargin}{-4mm}
\addtolength{\evensidemargin}{-28mm}
\addtolength{\topmargin}{-3cm}
\else
\addtolength{\textwidth}{-1cm}
\addtolength{\textheight}{-2cm}
\addtolength{\oddsidemargin}{-2.3cm}
\addtolength{\evensidemargin}{-3.5cm}
% \addtolength{\topmargin}{4.7cm}

% 2pp.sty - POSTSCRIPT hack to put 2 A5 pages per A4 page
% \special{! userdict begin
% /Width 596 def
% /Height 843 def
% /start-hook {TeXDict /eop {clear SI restore eop-hook}put} def
% /DinA5count 0 def
% /bop-hook {gsave DinA5count 
%  Width 0 translate 90 rotate 1 and 0 ne {Height 2 div
% 0 translate} if}def
% /eop-hook {grestore DinA5count dup 1 and 0 ne {showpage} if
% 1 add /DinA5count exch store } def
% /end-hook {DinA5count 1 and 0 ne {showpage} if} def
% end}
%

\fi

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}

\newtheorem{lem}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{corol}[theorem]{Corollary}


\newcommand{\eps}{\varepsilon}
\newcommand{\fu}{\varphi}
\newcommand{\FF}{{\cal F}}
\newcommand{\HH}{{\cal H}}
\newcommand{\SS}{{\cal S}}

\newcommand{\restr}[1]{|_{\textstyle #1}}
\newcommand{\heading}[1]{\vspace{1ex}\par\noindent{\bf #1}}
\newcommand{\subh}[1]{\noindent{\em #1}}

\newcommand{\cei}[1]{{\left\lceil #1 \right\rceil}}
\newcommand{\flo}[1]{{\left\lfloor #1 \right\rfloor}}

\newcommand{\disc}{{\mathop {\rm disc} \nolimits}}

\newcommand{\ui}[1]{^{(#1)}}
\newcommand{\uiq}{\ui{q}}
\newcommand{\tfrac}[2]{{\textstyle{\frac{#1}{#2}}}}


\author{
 {\sc Ji\v{r}\'{\i} Matou\v{s}ek}\thanks{Research supported by
Czech Republic Grant GA\v{C}R 0194/1996 and by Charles University grants
 No. 193,194/1996.}\\
   {\footnotesize Department of Applied Mathematics}\\[-1.5mm]
   {\footnotesize  Charles University}\\[-1.5mm]
   {\footnotesize  Malostransk\'{e} n\'{a}m. 25, 118~00~~Praha~1}\\[-1.5mm]
   {\footnotesize Czech Republic}
%\\[-1.5mm]   {\footnotesize e-mail: {\tt matousek@kam.mff.cuni.cz}}
     }
\date{}

\begin{document}

\maketitle

\begin{abstract}
Beck and Fiala conjectured in 1981 that for any set system $\SS$
of maximum degree $t$ on a
finite ground set $X$, a coloring $\chi:X\to \{-1,+1\}$
exists such that $|\chi(S)|=O(\sqrt t)$ holds for all $S\in\SS$,
where $\chi(S)=\sum_{x\in S}\chi(X)$. We prove a weaker
statement, namely that for any fixed $p\geq 1$, a coloring $\chi$
exists such that the $p$th degree average of $|\chi(S)|$ over
$S\in \SS$ is $O(\sqrt t)$. The result also holds if each set is
assigned a nonnegative real weight and the $p$th degree
average is taken with these weights (with $\chi$
depending on the weights).
\end{abstract}

\section{Introduction}
Let $X$ be a finite set and $\SS\subseteq 2^X$ be a family of
subsets of $X$.
By a {\em coloring\/} we mean a mapping  $\chi:X\to\{-1,+1\}$.
The   {\em   discrepancy\/}   of   $\SS$,  denoted  by
$\disc(\SS)$, is the minimum, over all colorings $\chi$, of
\begin{equation} \label{e:maxd}
\disc(\SS,\chi)= \max_{S\in \SS}\left|\chi(S)\right|\, ,
\end{equation}
where we use the shorthand $\chi(S)$ for $\sum_{x\in S}\chi(x)$.
A very significant result in discrepancy theory is a theorem of
Beck and Fiala \cite{bf-imt-81}: {\sl The discrepancy of
any\footnote{We only consider set systems with a finite ground set
in this paper.}
set system $\SS$ is at most $2t-1$, where $t$ denotes the maximum
degree of $\SS$, i.e. $t=\max_{x\in X}|\{S\in\SS;\, x\in S\}|$.
} % end sl
Beck and Fiala conjectured that the upper bound can be improved
to $C\sqrt t$, with an absolute constant $C$ (this, if true, is
the best possible bound one can hope for, since set systems exist
with maximum degree $t$ and discrepancy of the order $\sqrt t$).
A more detailed discussion (heuristic reasons for the validity of
the conjecture, related conjectures, and background information)
can be found in \cite{s-tlpm-87} (see also \cite{as-pm-93},
\cite{bs-dt-95}).

Here we prove an analogue of the Beck-Fiala conjecture for a
weaker notion of discrepancy, where instead of the maximum
(worst set in $\SS$) as in (\ref{e:maxd}) one takes an average
over the sets of $\SS$. Namely, for a number $p\in [1,\infty)$
we define
$$
\disc_p(\SS,\chi) = \left(\frac 1{|\SS|} \sum_{S\in \SS}
|\chi(S)|^p\right)^{1/p}\,;
$$
$\disc_p(\SS)$ is then defined as the minimum of
$\disc_p(\SS,\chi)$ over all colorings $\chi$. More generally,
we can consider a weight function $w:\SS\to (0,\infty)$, and set
$$
\disc_{p,w}(\SS,\chi) = \left(\frac 1{w(\SS)} \sum_{S\in \SS}
w(S)|\chi(S)|^p\right)^{1/p}\,.
$$
Srinivasan \cite{s-idbsm-96} proved that under the hypothesis
of the Beck-Fiala theorem, we have
$\disc_p(\SS)= O(t^{3/4}\log t)$ for each $p$, with the constant of
proportionality depending on $p$.
Here we establish an asymptotically  tight bound:

\begin{theorem}\label{t:}
For each $p\in [1,\infty)$ there exists a constant $C_p$ such
that for any set system $\SS$ of maximum degree $t$
and for any weight function $w:\SS\to (0,\infty)$, we have
$$
\disc_{p,w}(\SS) \leq C_p\sqrt t\,.
$$
\end{theorem}

The proof follows a known technique, but the adjustment of its
numerous parameters seems to require some subtlety for obtaining
the tight bound.

Theorem \ref{t:}
 can be regarded as a certain support for believing in
the Beck-Fiala conjecture itself. On the other hand, situations are
known in geometric discrepancy theory where the $p$th degree
average discrepancy is provably smaller than the worst-case
discrepancy (for instance, for axis-parallel rectangles in the
plane; see e.g., \cite{bc-id-87}). In combinatorial discrepancy,
a natural case where $\disc_p(.)$ is asymptotically smaller than
$\disc(.)$ is noted in \cite{m-dbdsf-94}. Also, the method
of our proof of Theorem~\ref{t:} seems to be inadequate
for attacking the Beck-Fiala conjecture.

\section{Summary of the entropy method}

Let us define a {\em partial coloring\/} to be a mapping
$\chi:X\to \{0,+1,-1\}$, and a let {\em substantial\/}
partial coloring be a partial coloring $\chi$ with
$\chi(x)\neq 0$ for at least $|X|/2$ points $x\in X$.
The points $x$ with $\chi(x)=0$ will be called {\em uncolored\/}
by $\chi$.

A method invented, in its original form, by Beck \cite{b-redis-81}
and further elaborated by Beck, Spencer, Boppana, and the author
(see e.g., \cite{s-ssds-85}, \cite{ms-dap-96} and references therein)
allows one prove the existence, under suitable assumptions, of a
substantial partial coloring of a given set system $\SS$.
In more recent applications, the method is referred to as the
{\em entropy method\/}, since technically it amounts to
estimating the entropy of certain random variables associated
with the considered set system. Here we need not introduce the
entropy concept and explain the way the required partial coloring
is produced. The following proposition, summarizing
results of calculations made in \cite{ms-dap-96}, can be used as
a black box:

\begin{prop}[Entropy method] \label{p:ent}
Let $\SS$ be a set system on an $n$-point set $X$,
and let a number $\Delta_S > 0$ be given for each $S\in \SS$.
Suppose that
\begin{equation}\label{e:sumh}
\sum_{S\in \SS} h\left({\Delta_S\over\sqrt{|S|}}\right)\leq \frac n5
\end{equation}
holds,
where the function $h(\lambda)$ can be estimated by
$$
 h(\lambda)\leq  g(\lambda) = \left\{ \begin{array}{ll}
Ke^{-\lambda^2/9} & \mbox{if $\lambda> 0.1$}  \\
K\ln(\lambda^{-1}) & \mbox{if $\lambda\leq 0.1$}
\end{array}
\right.
$$
with an absolute constant $K$. Then there exists a substantial
partial coloring $\chi:X\to \{\pm 1\}$ such that
$|\chi(S)|\leq\Delta_S$ for all $S\in\SS$.
\end{prop}

As a warm-up example of an application of this result, let us
re-prove an upper bound for the discrepancy under the conditions
of the Beck-Fiala theorem. This bound is the best known one for
the case when $|X|$ is less than exponential in $t$. It was
proved by Srinivasan \cite{s-idbsm-96}, improving previous
slightly weaker results of Beck and Spencer.

\begin{theorem}[\cite{s-idbsm-96}] \label{t:sri}
Let $\SS$ be a set system of maximum degree $t$ on an $n$-point
set $X$. Then $\disc(\SS)=O(\log n\sqrt t)$, with an absolute
constant of proportionality.
\end{theorem}

\heading{Proof. }
Using Proposition \ref{p:ent}, we prove that any set system $\SS$
of maximum degree $t$ has a substantial partial coloring with
discrepancy $O(\sqrt t)$. Having established this, the theorem is
proved by a standard iteration argument. Namely, given a set
system $\SS$ on an $n$-point set $X$, we consider a substantial
partial coloring $\chi_0$ of $X$ with discrepancy $O(\sqrt t)$.
We let $X_1$ be the set of at most $n/2$ points uncolored by
$\chi_0$, and let $\SS_1$ be $\SS$ restricted to $X_1$. The
maximum degree of $\SS_1$ is again at most $t$, and hence a
substantial partial coloring $\chi_1$ of $X_1$ exists with
$\disc(\SS_1,\chi_1)=O(\sqrt t)$. The partial colorings $\chi_0$
and $\chi_1$ together leave at most $n/4$ points uncolored, and
for these we produce another partial coloring $\chi_2$, etc.
After $O(\log n)$ iterations of this partial coloring step, we
end up with at most a constant number of points still uncolored,
and these can be colored arbitrarily. The resulting coloring of
$X$ has discrepancy $O(\log n\sqrt t)$.


To get a substantial partial coloring $\chi$ for a set system
$\SS$ with maximum degree $t$, we apply Proposition~\ref{p:ent}
with $\Delta_S= C\sqrt t$ for a large enough constant $C$; all we
need to do is checking the condition (\ref{e:sumh}).
To this end, we observe that for any given size
$s$, $1\leq s\leq n$, $\SS$ contains at most $nt/s$ sets of size
$\geq s$, where $n$ is the size of the ground set.
In order to sum up the contributions of sets of various
sizes conveniently, we put $s_i=2^{-i}100 C^2t $ ($i$ an integer,
possibly also negative), and we let $\SS_i$
consist of the sets of $\SS$ whose size lies in the interval
$(\frac{s_i}2,s_i]$. Then
$$
\sum_{S\in\SS} h\left({C\sqrt t \over \sqrt{|S|}}\right)\leq
\sum_i |\SS_i| h\left({C\sqrt t\over \sqrt{s_i}}\right)\leq
\sum_i {2nt\over s_i}h\left(\tfrac{2^{i/2}}{10}\right)
\leq
$$ $$
{ K \over 50 C^2}\, n \left[
\sum_{2^i\geq 1} 2^i e^{-2^{i}/900 }
+
\sum_{2^i < 1} 2^i \ln (10.2^{-i/2}) \right]\,.
$$
Clearly, both  sums in brackets are bounded by absolute constants,
and hence this bound can be pushed below $\frac n 5$ by taking
$C$ large enough.
$\Box$


\section{The case of equal weights}

In this section we prove a particular case of Theorem~\ref{t:},
namely that $\disc_p(\SS)\leq C_p\sqrt t$ holds for any set
system $\SS$ of maximum degree $t$ on a ground set $X$
with $m=|\SS|\geq n=|X|$. Hopefully, this might help
in reading the (much messier) proof of the general case
(arbitrary set weights).

The desired coloring $\chi$ will be produced similarly as in the
above proof of Theorem~\ref{t:sri}. A partial coloring step is
iterated until only negligibly few uncolored points remain.
The choice of the numbers $\Delta_S$ is slightly different,
however, as will be specified below.

\subh{Notational convention. } Instead of numbering the
iterations of the partial coloring step consecutively,
we assign the index $k$ to an iteration of the partial coloring
step such that the number of yet uncolored points at the
beginning of the iteration is in the interval $(\frac n{2^{k+1}},
\frac n{2^{k}}]$. Since in each step, at least half of the currently uncolored
points becomes colored, no two steps receive the same indices,
but the indices need not form a contiguous sequence. The symbol
$\sum_k$ in the sequel means the summation over the indices
of all iterations performed.

Let $X_k$ be the set of yet  uncolored
points at the beginning of step with index $k$,
let $n_k=|X_k|\in \left({n\over 2^{k+1}},{n\over 2^{k}}\right]$
 be their number, and let $\chi_k$
denote the partial coloring produced in that step.
As in the proof of Theorem~\ref{t:sri}, put
$s_i= 2^{-i} 100C^2t$ for a (possibly negative) integer $i$,
and let $\SS_{k,i}$ be the system of all sets in $\SS$ restricted
to $X_k$ whose size lies in the interval $(\frac {s_i}2, s_i]$.

For the sets $S\in \SS_{k,i}$, we put
$$
\Delta_S= \Delta_i = C\sqrt t\,\fu(i)\,,
$$
where $\fu(i)= 2^{-|i|/4p}$ is an auxiliary
``bump-like'' function (it is 1 for $i=0$ and decreases
geometrically  but slowly enough
for $i$ going away from 0 in both directions). Hence we require
that $|\chi_k(S)|\leq \Delta_i$ for all $S\in \SS_{k,i}$.

First need to show that such partial colorings can indeed be enforced,
i.e. to check the condition (\ref{e:sumh}) in
Proposition~\ref{p:ent}. This is fairly similar to the
calculation in the proof of Theorem~\ref{t:sri}, so we omit
this part and pass directly to verification that
$\disc_p(\SS,\chi)=O(\sqrt t)$ holds for the resulting coloring.

For a vector $v$ indexed by the sets of $\SS$, write
$\|v\|_p=\left(\frac 1m \sum_{S\in\SS} |v(S)|^p\right)^{1/p}$
(where $m=|\SS|$).
With this notation, we prove the estimate
$$
\|\chi_k\|_p\leq   \alpha(k)\sqrt t
$$
with an auxiliary function $\alpha(k)$ such that
$\sum_{k=0}^\infty \alpha(k) =O(1)$. Then we get
$$
\disc_p(\SS,\chi)=\|\chi\|_p\leq \sum_k \|\chi_k\|_p = O(\sqrt t)
$$
as claimed.

We have
$$
\|\chi_k\|_p^p =\frac 1m \sum_i  \Delta_i^p |\SS_{k,i}|\leq
{(C \sqrt t)^p\over m} \sum_i \fu(i)^p \min\left(m,{ 2n_k t \over s_i
}\right)\leq
$$
$$
(C \sqrt t)^p \sum_i \fu(i)^p
 \min\left(1,  2^i { n \over C_1 2^k m}\right)
$$
where $C_1=50 C^2$. Let $i_0=i_0(k) = \log_2 {C_1 2^k m\over n}$.
Since we assume $m\geq n$, we get that $i_0\geq k-O(1)$.
We can re-write
$$
\sum_i \fu(i)^p \min\left(1,  2^i {n \over C_1 2^k m}\right)
=
\sum_{i\geq i_0} \fu(i)^p + \sum_{i<i_0} \fu(i)^p 2^i { n \over
C_1 2^k m}=
$$
$$
\sum_{i\geq i_0} \fu(i)^p + O(\fu(i_0)^p) = \sum_{i\geq
k}\fu(i)^p+O(\fu(k)^p) =O(\fu(k)^p)\,.
$$
Therefore $\|\chi_k\|_p = O(\sqrt t\, \fu(k))$ and the proof
of the considered particular case of Theorem~\ref{t:}
is complete. $\Box$

\section{The general case}

Here we prove Theorem~\ref{t:}. For a more convenient notation,
we will use $f\ll g$ as a shorthand for $f=O(g)$. The implicit constant in
the $O(.)$ notation may depend on $p$ and other parameters
declared  as constant.

As in the preceding section,
$p\geq 1$ is a fixed number,
$\SS\subseteq 2^X$ is the considered set system of maximum degree
at most $t$, $n=|X|$, and $m=|\SS|$. Moreover, we consider a real
weight function $w:\SS\to (0,\infty)$. By a suitable re-scaling,
we may assume that $w(\SS)=\sum_{S\in\SS} w(S)=m$.

As a first step, we define a new weight function $\bar w$ as follows:
$$
\bar w(S) =\min\{2^q;\, 2^q\geq w(S),\, q=0,1,2,\ldots\}\,.
$$
Since $\bar w(S)\leq 2w(S)+1$ for all $S\in\SS$,
we have $\bar w(\SS)\leq 3m$.
Hence it suffices to prove the
existence of a coloring $\chi:X\to\{-1,+1\}$ such that
$$
\left(\frac 1m \sum_{S\in\SS} \bar w(S) |\chi(S)|^p\right)^{1/p}
\ll \sqrt t\,.
$$
The advantage of $\bar w$ is that it only attains values of the
form $2^q$ for nonnegative integers $q$. Let $\SS\uiq$ consist of the
sets $S\in \SS$ with weight $\bar w(S)=2^q$.

The coloring $\chi$ will again be obtained by an iteration of a
partial coloring step as in the previous proofs.
From the proof in the preceding section, we preserve the indexing
of the iterations, the notation $X_k$ (uncolored points before iteration $k$),
$n_k=|X_k|\in (\frac n{2^{k+1}},\frac n{2^k}]$, and the set size thresholds
$s_i= 2^{-i} 100 C^2 t$. We let $\SS_{k}\uiq$ be the restriction
of the system $\SS\uiq$ on $X_k$ (with empty sets deleted), and
$\SS_{k,i}\uiq$ are the sets of $\SS_k\uiq$ whose size is
in the interval $(\frac {s_i}2,s_i]$.

The difference compared to the previous
proof is that this time the maximum allowed discrepancy of
 a set $S\in\SS$ under $\chi_k$
will also depend on $k$ and on the weight of $S$ (besides the size of $S$
as in the proof in the preceding section). Namely, for
$S\in \SS_{k,i}\uiq$, we set
$$
\Delta_S=\Delta_{k,i}\uiq = C\sqrt t\, \fu(i)\psi(k,q)\,,
$$
where $C$ is a large enough constant, $\fu(i)=
2^{-|i|/4p}$ is as in the preceding proof, and $\psi(k,q)$ is another
auxiliary function.

Before defining $\psi(q,k)$ formally, let us try to
indicate its intended meaning. Because of the factor $\fu(i)$,
the only sets whose discrepancy under $\chi_k$ may be close to
$\sqrt t$ are those with $i\approx 0$, i.e. of size about $t$.
For simplicity, let us consider only sets of this ``critical''
size $t$ for a moment.
If we have $m\geq n$ sets, all of weight 1, as in the preceding
section, the discrepancy $\disc_p(\SS,\chi_k)$ is an average of
$m\geq n$ numbers.
At step $k$, the number of sets of size $t$
is at most $n_k\approx n/2^k$, and hence the contribution of
size-$t$ sets
to the $p$th degree average discrepancy $\disc_p(\SS,\chi_k)$
starts at $O(\sqrt t)$ at step $k=0$ and then decreases geometrically
with $k$. On the other hand, if the set weights are arbitrary, $\SS$ may
contain some small number (much smaller than $n$) of sets of size
$t$ whose weight is a large fraction of the total weight. The
entropy method gives us no control which points get colored by a
partial coloring. Hence it might possibly happen that for each of
these few critical size-$t$ sets, only about $\sqrt t$ points are
colored in each step, while their discrepancy also increases by
about $\sqrt t$ in each such step. But we
observe that the number of  sets making this kind of troubles
at step $k$ must be  considerably smaller than $n_k$,
and hence we can put a more strict limit on their
 discrepancy under $\chi_k$ while
preserving the condition(\ref{e:sumh}). To make this idea work
in all cases, we need a bit complicated definition of
$\psi(k,q)$.

Let  $m_q=|\SS\uiq|$ be the number of sets of weight $2^q$,
and for $j=0,1,2,\ldots,\flo{\log_2 m}$, let us put
$$
Q(j)=\{q;\, 2^{j}\leq m_q <2^{j+1}\}\,.
$$
Define $j_q$ as the $j$ with $q\in Q(j)$, and further set
$$
\delta(q) =|\{q'\in Q(j_q);\, q'\geq q\}|\,.
$$
Now we are ready to define $\psi(k,q)$:
$$
\psi(k,q) = \min\left(1, { C m_q 2^{\delta(q)}\over n_k }\right)\,.
$$
This finishes the definition of the discrepancy limits
$\Delta_{k,i}\uiq$; it remains to check that the
condition (\ref{e:sumh}) holds and thus the required
partial colorings $\chi_k$ satisfying the above-defined limits
exist, and that the resulting coloring $\chi$ has
$\disc_{p,\bar w}(\SS,\chi)=O(\sqrt t)$. We begin with the latter
calculation.


\heading{Discrepancy calculation. } We need to show
$$
\sum_{S\in \SS} \bar w(S) |\chi(S)|^p \ll m(\sqrt t\,)^p\,.
$$
The left-hand side can be re-written to
\begin{equation}\label{e:1}
\sum_{q\geq 0} 2^q \sum_{S\in\SS\uiq} |\chi(S)|^p \leq
\sum_{q\geq 0} 2^q
 \left[\sum_k \left(
         \sum_{S\in\SS_k\uiq} |\chi_k(S)|^p
   \right)^{1/p}\right]^p\,.
\end{equation}
For the innermost sum, which we denote by $A(k,q)$, we get
$$
A(k,q)=\sum_{S\in\SS_k\uiq} |\chi_k(S)|^p \leq
\sum_i |\SS_{k,i}\uiq| \left(\Delta_{k,i}\uiq\right)^p \ll
$$
$$
(\sqrt t\,)^p \psi(k,q)^p
     \sum_i \min\left(m_q, {2n_k t\over s_i}\right)\fu(i)^p\leq
$$
$$
(\sqrt t\,)^p \psi(k,q)^p m_q
     \sum_i \min\left(1, 2^i {n_k \over C_1  m_q }\right)\fu(i)^p
$$
with $C_1=50C^2$.
Similarly to the proof in the unweighted case, we split the last
sum into two parts at $i=i_0=
i_0(k,q)=\log_2({C_1 m_q\over n_k})$. The terms with
$i<i_0$ decrease geometrically with decreasing $i$, and so we get
$$
A(k,q)\ll (\sqrt t\,)^p \psi(k,q)^p m_q \sum_{i\geq
i_0}\fu(i)^p\,.
$$
Now if $i_0\leq 0$, i.e. the summation range contains 0, the sum is
$O(1)$, and otherwise it is $\ll \fu(i_0)^p\ll
\left({n_k\over C_1  m_q}\right)^{1/4}$.

Considering the second innermost sum in (\ref{e:1}), we thus have
$$
\frac 1{\sqrt t} \sum_k A(k,q)^{1/p} \ll  m_q^{1/p} \sum_k \psi(k,q)
\min\left[1,\left({n_k\over C_1 m_q}\right)^{1/4p}\right]=
$$
$$
m_q^{1/p}\sum_k
\min\left(1, { C  m_q 2^{\delta(q)}\over n_k }\right)
\min\left[1,\left({n_k\over C_1  m_q}\right)^{1/4p}\right]\,.
$$
The value of the last sum over $k$ is proportional to the number
of its addends that are close to 1 (for $k$ getting smaller, the
first $\min$ decreases geometrically, and for $k$ getting
larger, the second $\min$ does). The number of such addends
is $O(\delta(q))$, and hence
$$
\sum_q 2^q \left[\sum_k A(k,q)^{1/p}\right]^p \ll  (\sqrt t\,)^p
 \sum_q 2^q m_q \delta(q)^p\,.
$$
Further
$$
\sum_q 2^q m_q \delta(q)^p \leq
\sum_{j} 2^{j+1} \sum_{q\in Q(j)} 2^q \delta(q)^p \leq
\sum_j 2^{j+1} \sum_{\ell=1}^{|Q(j)|} 2^{\max Q(j)-\ell+1}
\ell^p\ll
$$
$$
\sum_j 2^{j} 2^{\max Q(j)} \leq  \sum_{q} m_q 2^q
\ll m  \,.
$$
Hence $\disc_{p,\bar w}(\SS,\chi)\ll \sqrt t$ is verified.

\heading{Estimating the entropy. }
First we check some simple properties of the function
$g(\lambda)$ defined in Proposition~\ref{p:ent}.

\begin{lemma}\label{l:}
The function $g(\lambda)$ is nonincreasing for $\lambda>0$, and for any
$\mu\in (0, 0.1]$ and any  $\lambda>0$ we have
$g(\mu\lambda)\leq 2g(\mu)+ g(\lambda)$.
\end{lemma}

\subh{Proof of the Lemma. }
The monotonicity is obvious from definition.
The second property is inspired by properties of entropy
(whose estimate $g(\lambda)$ really is), but it can be verified
purely formally, by discussing few cases. Namely, for
$\lambda\leq 0.1$ we have
$g(\mu\lambda) = g(\mu)+g(\lambda)$. For $\mu\lambda\geq 0.1$,
we get $g(\mu\lambda)\leq K <2K\ln 10 < 2g(\mu)$,
and finally for the intermediate case $0.1\leq \lambda\leq 0.1/\mu$
we get $g(\mu\lambda)= K\ln(\mu^{-1})+K\ln(\lambda^{-1})\leq
2K\ln(\mu^{-1})=2g(\mu)$. $\Box$
\medskip

In the rest of the proof, the constants implicit in the $O(.)$
and $\ll$ notation will be independent of $C$.
To conclude the proof of Theorem~\ref{t:}, we need to verify
that the condition (\ref{e:sumh}) is satisfied at each step $k$,
which in our case means
$$
\sum_{q} \sum_i |\SS_{k,i}\uiq|\,\,
g\left({\Delta_{k,i}\uiq\over\sqrt s_i}\right) \leq \frac {n_k}5
$$
for all $k$.
By plugging in the expressions for $s_i$ and for $\Delta_{k,i}\uiq$,
distinguishing the cases $\psi(k,q)\leq 0.1$ and
$\psi(k,q)>0.1$, and applying Lemma~\ref{l:},
 the l.h.s. can be bounded as follows:
$$
\sum_{q} \sum_i |\SS_{k,i}\uiq|\,\,
g\left(\tfrac{2^{i/2}\fu(i)\psi(k,q)}{10}\right)
\leq
$$
$$
\sum_{q;\,\psi(k,q)\geq 0.1} \sum_i |\SS_{k,i}\uiq|\,\,
    g\left(\tfrac{2^{i/2}\fu(i)}{100}\right)  +
\ifafour\else
$$
$$
\ \ \ \ 
\fi
\sum_{q;\,\psi(k,q)< 0.1} \sum_i |\SS_{k,i}\uiq|\left[
    g\left(\tfrac{2^{i/2}\fu(i)}{10}\right)+
                   2g(\psi(k,q))\right] 
\leq
$$
\begin{equation}\label{e:2}
\sum_i |\SS_{k,i}|\,\, g\left(\tfrac{2^{i/2}\fu(i)}{100}\right)
+
\sum_{q;\,\psi(k,q)< 0.1} |\SS\uiq|.2g(\psi(k,q))\,.
\end{equation}
Now the first sum doesn't depend on the set weights, and a
precisely the same calculation as in the unweighted case
(with $n_k$ instead of $n$) shows that it can be made smaller
than $\frac {n_k}{10}$ by setting $C$ large enough. So it remains
to deal with the second sum:
$$
\sum_{q;\,\psi(k,q)<0.1} m_q.2K  \ln \frac 1{\psi(k,q)}\ll
 \sum_{q;\, m_q 2^{\delta(q)} < n_k/10 C}
   m_q \ln {n_k \over C  m_q 2^{\delta(q)} } \leq
$$
$$
 \sum_{j} 2^{j+1} \sum_{q\in Q(j)}
  \max\left(\log_2 {n_k\over C 2^{j+\delta(q)}},0\right) \leq
$$
$$
\sum_{j} 2^{j+1} \sum_{{q\in Q(j)}\atop{j+\delta(q)\leq
\log_2(n_k/C)}}
    \left[\log_2\tfrac{n_k}C-j-\delta(q)\right]\,.
$$
The inner sum has at most $\log_2\frac{n_k}C-j$ terms, each of value
no bigger than $\log_2\frac{n_k}C-j$, and so we get that the sum over
$j$ is at most
$$
\sum_{j\leq \log_2(n_k/C)} 2^j (\log_2\tfrac{n_k}C-j)^2 \ll {n_k\over C}\,,
$$
with the constant of proportionality independent of $C$.
Hence also the second sum in (\ref{e:2}) can
 be made smaller than $\frac {n_k}{10}$ by setting $C$ large
enough, and Theorem~\ref{t:} is proved. $\Box$



%\bibliographystyle{plain}
%\bibliography{../bib/cg,../bib/geom}

\begin{thebibliography}{10}

\bibitem{as-pm-93}
N.~Alon and J.~Spencer.
\newblock {\em The probabilistic method}.
\newblock J. Wiley \& Sons, 1993.

\bibitem{b-redis-81}
J.~Beck.
\newblock Roth's estimate on the discrepancy of integer sequences is nearly
  sharp.
\newblock {\em Combinatorica}, 1(4):319--325, 1981.

\bibitem{bc-id-87}
J.~Beck and W.~Chen.
\newblock {\em Irregularities of distribution}.
\newblock Cambridge University Press, 1987.

\bibitem{bf-imt-81}
J.~Beck and T.~Fiala.
\newblock ``{I}nteger making'' theorems.
\newblock {\em Discr. Appl. Math}, 3:1--8, 1981.

\bibitem{bs-dt-95}
J.~Beck and V.~{S\'os}.
\newblock Discrepancy theory.
\newblock In {\em Handbook of Combinatorics}, pages 1405--1446. North-Holland,
  Amsterdam, 1995.

\bibitem{m-dbdsf-94}
J.~Matou\v{s}ek.
\newblock On discrepancy bounds via dual shatter function.
\newblock KAM Series (Tech. Report) 94--273, Charles University, Prague, 1994.
\newblock Also to appear in {\em Mathematika\/}.

\bibitem{ms-dap-96}
J.~Matou\v{s}ek and J.~Spencer.
\newblock Discrepancy in arithmetic progressions.
\newblock {\em J. Amer. Math. Soc.}, 9:195--204, 1996.

\bibitem{s-ssds-85}
J.~Spencer.
\newblock Six standard deviations suffice.
\newblock {\em Trans. Amer. Math. Soc.}, 289:679--706, 1985.

\bibitem{s-tlpm-87}
J.~Spencer.
\newblock {\em Ten lectures on the probabilistic method}.
\newblock CBMS-NSF. SIAM, 1987.

\bibitem{s-idbsm-96}
A.~Srinivasan.
\newblock Improving the discrepancy bound for sparse matrices: better
  approximations for sparse lattice approximation problems.
\newblock {\em Proc. ACM Symposium on Discrete Algorithms\/}, to appear, 1997.

\end{thebibliography}


\newpage\thispagestyle{empty}~~
\newpage\thispagestyle{empty}~~

\end{document}
