Let X denote a finite set, k and n denote natural numbers and S~ ..... Sn denote subsets of X. Assume that no point of X lies in more than k of these subsets. In 1981 Beck and Fiala proved that there is a 2-coloring of X such that each of the subsets has discrepancy less than 2k. This result has an interpretation as a theorem about incidence matrices and its generalization to real matrices (with essentially the same proof) is called the continuous Beck-Fiala theorem. We investigate the continuous version of the conjecture of Beck and Fiala that 'less than 2k' could be replaced by 'less than or equal to k'. For matrices with nonnegative entries, we show that the answer to the corresponding continuous problem is 'no', so the continuous Beck-Fiala theorem is optimal in this case. However our methods do not provide a counterexample to Beck and Fiala's original conjecture. On the other hand we show that the answer to the corresponding continuous problem is 'yes' when the dimension of the matrix that corresponds tonis 1,2or3.
Throughout this note we shall use boldface letters to denote vectors in II~ n. Thus, if xl ~ R for 1 ~< i ~< n, then we write x = (xl ..... x,); it will often be convenient to write x(i) for the ith coordinate of x. As usual the E Β°~-and Β’l-norms on R n are defined by h[xlh~ = max Ix(i)l and Ilxlll = ~ Ix(i)l.
l <~i <~n i=l
In [2] Beck and Fiala proved the following theorem.
Theorem 1 (Beck and Fiala [2]). Suppose A = [ao] is an n x m matrix with real entries and write d=max{~'laΒ°l:l<<'J<~m} ",=1