--- abstract: | The $\gamma_2$ norm of a real $m\times n$ matrix $A$ is the minimum number $t$ such that the column vectors of $A$ are contained in a $0$-centered ellipsoid $E\subseteq{{\mathbb{R}}}^m$ which in turn is contained in the hypercube $[-t, t]^m$. We prove that this classical quantity approximates the *hereditary discrepancy* $\operatorname{herdisc}A$ as follows: $\gamma_2(A) = {O(\log m)}\cdot \operatorname{herdisc}A$ and $\operatorname{herdisc}A = O(\sqrt{\log m}\,)\cdot\gamma_2(A) $. Since $\gamma_2$ is polynomial-time computable, this gives a polynomial-time approximation algorithm for hereditary discrepancy. Both inequalities are shown to be asymptotically tight. We then demonstrate on several examples the power of the $\gamma_2$ norm as a tool for proving lower and upper bounds in discrepancy theory. Most notably, we prove a new lower bound of $\Omega(\log^{d-1} n)$ for the *$d$-dimensional Tusnády problem*, asking for the combinatorial discrepancy of an $n$-point set in ${{\mathbb{R}}}^d$ with respect to axis-parallel boxes. For $d>2$, this improves the previous best lower bound, which was of order approximately $\log^{(d-1)/2}n$, and it comes close to the best known upper bound of $O(\log^{d+1/2}n)$, for which we also obtain a new, very simple proof. author: - | <span>Jiří Matoušek</span>[^1]\ <span>Department of Applied Mathematics</span>\ <span>Charles University, Malostranské nám. 25</span>\ <span>118 00 Praha 1, Czech Republic, and</span>\ <span>Department of Computer Science</span>\ <span>ETH Zurich, 8092 Zurich, Switzerland</span> - | <span>Aleksandar Nikolov</span>\ <span>Microsoft Research</span>\ <span>Redmond, WA, USA</span> - | <span>Kunal Talwar</span>\ <span>Google</span>\ <span>Mountain View, CA, USA</span> bibliography: - 'cg.bib' title: Factorization Norms and Hereditary Discrepancy --- Introduction ============ <span>**Discrepancy and hereditary discrepancy.** </span> Let $V=[n]:=\{1,2,\ldots,n\}$ be a ground set and ${\mathcal{F}}=\{F_1,F_2,\ldots,F_m\}$ be a system of subsets of $V$. The *discrepancy* of ${\mathcal{F}}$ is $$\operatorname{disc}{\mathcal{F}}:=\min_{x\in\{-1,1\}^n} \operatorname{disc}({\mathcal{F}},x),$$ where the minimum is over all choices of a vector $x\in\{-1,+1\}^n$ of signs for the points, and $\operatorname{disc}({\mathcal{F}},x):=\max_{i=1,2,\ldots,m}\bigl|\sum_{j\in F_i}x_j\bigr|$. (A vector $x\in\{-1,1\}^n$ is usually called a *coloring* in this context.) This combinatorial notion of discrepancy originated in the classical theory of *irregularities of distribution*, as treated, e.g., in @bc-id-87 [@drm-ti; @abc-gd-97], and more recently it has found remarkable applications in computer science and elsewhere (see @s-tlpm-87 [@Chazelle-book; @m-gd] for general introductions and, e.g., @larsen14 for a recent use). For the subsequent discussion, we also need the notion of discrepancy for matrices: for an $m\times n$ real matrix $A$ we set $\operatorname{disc}A :=\min_{x\in\{-1,1\}^n}\|Ax\|_\infty$, where $\|\cdot\|_\infty$ is the usual $\ell_\infty$ norm on ${{\mathbb{R}}}^m$. If $A$ is the incidence matrix of the set system ${\mathcal{F}}$ as above (with $a_{ij}=1$ if $j\in F_i$ and $a_{ij}=0$ otherwise), then the matrix definition coincides with the one for set systems. We can add elements to the sets in any set system with arbitrarily large discrepancy to get a new set system with small, even zero, discrepancy. This phenomenon was exploited in @charikar-al-disc-inapprox for showing that, assuming P$\,\ne\,$NP, no polynomial-time algorithm can distinguish systems ${\mathcal{F}}$ with zero discrepancy from those with discrepancy of order $\sqrt n$ in the regime $m = O(n)$, which practically means that $\operatorname{disc}{\mathcal{F}}$ cannot be approximated at all in polynomial time. A better behaved notion is the *hereditary discrepancy* of ${\mathcal{F}}$, given by $$\operatorname{herdisc}{\mathcal{F}}:=\max_{J\subseteq V}\operatorname{disc}({\mathcal{F}}|_J),$$ were ${\mathcal{F}}|_J$ denotes the *restriction* of the set system ${\mathcal{F}}$ to the ground set $J$, i.e., $\{F\cap J:F\in{\mathcal{F}}\}$. Similarly, for a matrix $A$, $\operatorname{herdisc}A := \max_{J\subseteq[n]}{\operatorname{disc}A_J}$ where $A_J$ is the submatrix of $A$ consisting of the columns indexed by the set $J$. At first sight, hereditary discrepancy may seem harder to deal with than discrepancy. For example, while $\operatorname{disc}{\mathcal{F}}\le k$ has an obvious polynomial-time verifiable certificate, namely, a suitable coloring $x\in\{-1,1\}^n$, it is not at all clear how one could certify either $\operatorname{herdisc}{\mathcal{F}}\le k$ or $\operatorname{herdisc}{\mathcal{F}}>k$ in polynomial time. Nevertheless, hereditary discrepancy has turned out to have significant advantages over discrepancy. Most of the classical upper bounds for discrepancy of various set systems actually apply to hereditary discrepancy as well. The *determinant lower bound*, a powerful tool introduced by Lovász, Spencer and Vesztergombi @lsv-dssm-86, works for hereditary discrepancy and *not* for discrepancy. The determinant lower bound for a matrix $A$ is the following algebraically defined quantity: $$\operatorname{detlb}A= \max_k\max_B |\det B\,|^{1/k},$$ where $B$ ranges over all $k\times k$ submatrices of $A$. Lovász et al. proved that $\operatorname{herdisc}A\ge\frac12\operatorname{detlb}A$ for all $A$. Later it was shown in @almosttight that $\operatorname{detlb}A$ also bounds $\operatorname{herdisc}A$ from above up to a polylogarithmic factor; namely, $\operatorname{herdisc}A=O(\log(mn)\sqrt{\log n}\,)\cdot\operatorname{detlb}(A)$. While the quantity $\operatorname{detlb}A$ enjoys some pleasant properties, there is no known polynomial-time algorithm for computing it. Bansal @bansal-di provided a polynomial-time algorithm that, given a system ${\mathcal{F}}$ with $\operatorname{herdisc}{\mathcal{F}}\le D$, computes a coloring $x$ witnessing $\operatorname{disc}{\mathcal{F}}=O(D\log(mn))$. However, this is not an approximation algorithm for the hereditary discrepancy in the usual sense, since it may find a low-discrepancy coloring even for ${\mathcal{F}}$ with large hereditary discrepancy. <span>**The $\gamma_2$ factorization norm.** </span> The first polynomial-time approximation algorithm with a polylogarithmic approximation factor for hereditary discrepancy was found by the last two authors and Zhang @NTZ-diffprivacy. Here we strengthen and streamline this result, and show that hereditary discrepancy is approximated by the $\gamma_2$ factorization norm from Banach space theory. (This connection was implicit in @NTZ-diffprivacy.) A preliminary version of our results, which we have simplified and extended, appeared in the conference publications @NT [@e8-tusnady]. For some of the simplifications we are indebted to Noga Alon and Assaf Naor, who pointed out that the geometric quantity used in @NT [@e8-tusnady] is in fact equivalent to the $\gamma_2$ norm. The $\gamma_2$ norm of an $m\times n$ matrix $A$, taken as a linear operator from $\ell_1^n$ to $\ell_\infty^m$, is defined as $$\gamma_2(A) := \min\{\|B\|_{2\to\infty}\|C\|_{1\to 2}: A = BC\}.$$ Above, $\|\cdot\|_{p\to q}$ stands for the $\ell_p \to \ell_q$ operator norm, and $B:\ell_1^n \to \ell_2$, $C:\ell_2\to \ell_\infty^m$ range over linear operators. Without loss of generality, we can assume that the rank of $B$ and $C$ is at most the rank of $A$. Treating $B$ and $C$ as matrices, it is easy to see that $\|B\|_{2\to\infty}$ is equal to the largest Euclidean norm of row vectors of $B$, and $\|C\|_{1\to 2}$ is equal to the largest Euclidean norm of column vectors of $C$. Moreover, by a standard compactness argument, the minimum is achieved in this finite-dimensional case. We will also make use of an equivalent geometric definition of ${\gamma_2(A)}$. Let the $\ell_\infty$ norm $\|E\|_\infty$ of an ellipsoid $E$ be defined as the largest $\ell_\infty$ norm of any point in $E$. Then ${\gamma_2(A)}$ is equal to the minimum $\ell_\infty$ norm of a $0$-centered ellipsoid $E$ that contains all column vectors of $A$, as is illustrated in the next picture (for $m=2$): Given a factorization $A=BC$ witnessing $\gamma_2(A)$, an optimal ellipsoid can be defined as $\{Bx: \|x\|_2 \leq \|C\|_{1\to 2}\}$. In the reverse direction, given a 0-centered ellipsoid $E = \{x: x^T M x \leq 1\}$, defined by a positive definite matrix $M$ with positive square root $M^{1/2}$, and containing the columns of $A$, the factorization $A = M^{-1/2} (M^{1/2}A)$ satisfies $\|M^{-1/2}\|_{2\to\infty} = \|E\|_\infty$ and $\|M^{1/2}A\|_{1\to 2} \leq 1$. We use the notation ${\gamma_2({\mathcal{F}})}$ for a set system ${\mathcal{F}}$ to mean the $\gamma_2$ norm of the incidence matrix of ${\mathcal{F}}$. <span>**Results on the $\gamma_2$ norm.** </span> A number of useful properties of $\gamma_2$ are known, such as the non-obvious fact that it is indeed a norm @Tomczak-J-book (we give an example of how the triangle inequality fails for $\operatorname{detlb}$), and the fact that it is is multiplicative under the *Kronecker product* (or tensor product) of matrices @LeeSS08. We further prove a stronger form of the triangle inequality for matrices supported on disjoint subsets of the columns. <span>**Relationship between $\gamma_2$ and $\operatorname{herdisc}$.** </span> Next we prove the following two inequalities relating ${\gamma_2(A)}$ and $\operatorname{herdisc}A$, which are central to our work: there exists a constant $C$ such that for every matrix $A$ with $m$ rows, $$\begin{aligned} &\operatorname{herdisc}A\ge \frac {{\gamma_2(A)}} {C\log m}, \mbox{ and} \label{e:NTineq1}\\ &\operatorname{herdisc}A \le {\gamma_2(A)} \cdot C\sqrt{\log m}\label{e:NTineq2}\end{aligned}$$ (As we will see in Section \[s:simplified-ineq1\] below, is actually valid with $\log\operatorname{rank}A$ instead of $\log m$.) Moreover, ${\gamma_2(A)}$ can be approximated to any desired accuracy in polynomial time using semidefinite programming @LinialMSS07-signmatrices. These results together provide an $O(\log^{3/2}m)$-approximation algorithm for $\operatorname{herdisc}A$, improving on the $O(\log^3 m)$-approximation from @NTZ-diffprivacy. The lower bound is proved using a dual characterization of $\gamma_2(A)$ in terms of the trace norm @LeeSS08, which we relate to $\operatorname{detlb}A$. Our proof also implies that ${\gamma_2(A)}$ is between $\operatorname{detlb}A$ and $O(\log m) \cdot\operatorname{detlb}(A)$. The upper bound is proved using a result of Banaszczyk @banasz98. It is not constructive, in the sense that we do not know of a polynomial-time algorithm that computes a coloring achieving the upper bound. Nevertheless, the algorithms of Bansal @bansal-di or Rothvoss @Rothvoss14-convex can be used to find colorings with discrepancy $O(\log m)\cdot {\gamma_2(A)}$ in polynomial time. We show that both inequalities and are asymptotically tight in the worst case. For , the asymptotic tightness is demonstrated on the following simple example: for the system ${\mathcal{I}}_n$ of initial segments of $\{1,2,\ldots,n\}$, whose incidence matrix is the lower triangular matrix $T_n$ with $1$s on the main diagonal and below it, we prove that the $\gamma_2$ norm is of order $\log n$, while the hereditary discrepancy is well known to be $1$. It is interesting to compare our bounds on $\gamma_2(T_n)$ with a related but incomparable result of Fredman @Fredman82, who showed that in any factorization $T_n = AB$, with $A$ and $B$ matrices over the integers, the smallest achievable total number of non-zero entries in $A$ and $B$ is $2n\log_\lambda n + O(n)$ for $\lambda=3+2\sqrt{2}$. We have computed optimal ellipsoids witnessing ${\gamma_2(T_n)}$ numerically for moderate values of $n$, and they display a remarkable and aesthetically pleasing "limit shape". It would be interesting to understand these optimal ellipsoids theoretically—we leave this as an open problem. <span>**Applications in discrepancy theory.** </span> In the second part of the paper we apply the $\gamma_2$ norm to prove new results on combinatorial discrepancy, as well as to give simple new proofs of known results. The most significant result is a new lower bound for the $d$-dimensional Tusnády's problem; before stating it, let us give some background. <span>**The "great open problem."** </span> Discrepancy theory started with a result conjectured by van der Corput @c-vI-35 [@c-vII-35] and first proved by van Aardenne-Ehrenfest @a-pijd-45 [@a-ijd-49], stating that every infinite sequence $(u_1,u_2,\ldots)$ of real numbers in $[0,1]$ must have a significant deviation from a "perfectly uniform" distribution. Roth @r-id-54 found a simpler proof of a stronger bound, and he re-cast the problem in the following setting, dealing with finite point sets in the unit square $[0,1]^2$ instead of infinite sequences in $[0,1]$: Given an $n$-point set $P\subset [0,1]^2$, the *discrepancy* of $P$ is defined as $$D(P,{\mathcal{R}}_2):=\sup\Bigl \{\Bigl||P\cap R|-n\lambda^2(R\cap[0,1]^d) \Bigr|: R\in{\mathcal{R}}_2\Bigr\},$$ where ${\mathcal{R}}_2$ denotes the set of all $2$-dimensional axis-parallel rectangles (or $2$-dimensional intervals), of the form $R=[a_1,b_1]\times [a_2,b_2]$, and $\lambda^2$ is the area (2-dimensional Lebesgue measure). More precisely, $D(P,{\mathcal{R}}_2)$ is the *Lebesgue-measure discrepancy* of $P$ w.r.t. axis-parallel rectangles. Further let $D(n,{\mathcal{R}}_2)=\inf_{P:|P|=n} D(P,{\mathcal{R}}_2)$ be the best possible discrepancy of an $n$-point set. Roth proved that $D(n,{\mathcal{R}}_2)=\Omega(\sqrt{\log n})$, while earlier work of van der Corput yields $D(n,{\mathcal{R}}_2)=O(\log n)$. Later Schmidt @s-idVII-72 improved the lower bound to $\Omega(\log n)$. Roth's setting immediately raises the question about a higher-dimensional analog of the problem: letting ${\mathcal{R}}_d$ stand for the system of all axis-parallel boxes (or $d$-dimensional intervals) in $[0,1]^d$, what is the order of magnitude of $D(n,{\mathcal{R}}_d)$? There are many ways of showing an upper bound of $O(\log^{d-1}n)$, the first one being the Halton–Hammersley construction @h-mcmsm-60 [@h-ecqsp-60], while Roth's lower bound method yields $D(n,{\mathcal{R}}_d)=\Omega(\log^{(d-1)/2}n)$. In these bounds, $d$ is considered fixed and the implicit constants in the $O(.)$ and $\Omega(.)$ notation may depend on it. Now, over 50 years later, the upper bound is still the best known, and Roth's lower bound has been improved only a little: first for $d=3$ by Beck @b-tdaet-89 and by Bilyk and Lacey @bl-sbi3D, and then for all $d$ by Bilyk, Lacey, and Vagharshakyan @blv-sbi. The lower bound from @blv-sbi has the form $\Omega((\log n)^{(d-1)/2+\eta(d)})$, where $\eta(d)>0$ is a constant depending on $d$, with $\eta(d)\ge c/d^2$ for an absolute constant $c>0$. Thus, the upper bound for $d\ge 3$ is still about the square of the lower bound, and closing this significant gap is called the "great open problem" in the book @bc-id-87. <span>**Tusnády's problem.** </span> Here we essentially solve a combinatorial analog of this problem. In the 1980s Tusnády raised a question which, in our terminology, can be stated as follows. Let $P\subset{{\mathbb{R}}}^2$ be an $n$-point set, and let ${\mathcal{R}}_2(P):=\{R\cap P: R\in{\mathcal{R}}_2\}$ be the system of all subsets of $P$ induced by axis-parallel rectangles $R\in{\mathcal{R}}_2$. What can be said about the discrepancy of such a set system for the worst possible $n$-point $P$? In other words, what is $$\operatorname{disc}(n,{\mathcal{R}}_2)=\max\{\operatorname{disc}{\mathcal{R}}_2(P): |P|=n\}?$$ We stress that for the Lebesgue-measure discrepancy $D(n,{\mathcal{R}}_d)$ we ask for the best placement of $n$ points so that each rectangle contains approximately the right number of points, while for $\operatorname{disc}(n,{\mathcal{R}}_2)$ the point set $P$ is given by an adversary, and we seek a $\pm1$ coloring so that the points in each rectangle are approximately balanced. Tusnády actually asked if $\operatorname{disc}(n,{\mathcal{R}}_2)$ could be bounded by a constant independent of $n$. This was answered negatively by Beck @b-btcfs-81, who also proved an upper bound of $O(\log^4 n)$. His lower bound argument uses a "transference principle," showing that the function $\operatorname{disc}(n,{\mathcal{R}}_2)$ in Tusnády's problem cannot be asymptotically smaller than the smallest achievable Lebesgue-measure discrepancy of $n$ points with respect to axis-aligned boxes. (This principle is actually simple to prove and quite general; Simonovits attributes the idea to V.T.Sós. The main observation is that for any coloring with discrepancy $D_1$ of an $n$-point set with Lebesgue measure discrepancy $D_2$, the smaller of the two color classes has Lebesgue measure discrepancy at most $\frac12 (D_1 + D_2)$.) The upper bound was improved to $O((\log n)^{3.5+{\varepsilon}})$ by Beck @b-btcfs-89, to $O(\log^3 n)$ by Bohus @b-odtp-90, and to the current best bound of $O(\log^{2.5} n)$ by Srinivasan @s-idbsm-96. The obvious $d$-dimensional generalization of Tusnády's problem was attacked by similar methods. All known lower bounds so far relied on the transference principle mentioned above. The current best upper bound for $d\ge 3$ is $O(\log^{d+1/2}n)$ due to Larsen @larsen14, which is a a slight strengthening of a previous bound of $O(\log^{d+1/2} n\sqrt{\log\log n}\,)$ from @m-dipol-97. Here we improve on the lower bound for the $d$-dimensional Tusnády's problem significantly; while up until now the uncertainty in the exponent of $\log n$ was roughly between $(d-1)/2$ and $d+1/2$, we reduce it to $d-1$ versus $d+1/2$. \[t:tusnady\] For every fixed $d\ge 2$ and for infinitely many values of $n$, there exists an $n$-point set $P\subset{{\mathbb{R}}}^d$ with $$\operatorname{disc}{\mathcal{R}}_d(P)=\Omega(\log^{d-1}n),$$ where the constant of proportionality depends only on $d$. From the point of view of the "great open problem," this result is perhaps somewhat disappointing, since it shows that, in order to determine the asymptotics of the Lebesgue-measure discrepancy $D(n,{\mathcal{R}}_d)$, one has to use some special properties of the Lebesgue measure—combinatorial discrepancy cannot help, at least for improving the upper bound. In Section \[s:Lpbound\] we will discuss a bound on *average* discrepancy, which in a sense separates the combinatorial discrepancy (as in Tusnády's problem) from the Lebesgue-measure discrepancy. Using the $\gamma_2$ norm as the main tool, our proof of Theorem \[t:tusnady\] is surprisingly simple. In a nutshell, first we observe that, since the target bound is polylogarithmic in $n$, instead of estimating the discrepancy for some cleverly constructed $n$-point set $P$, we can bound from below the hereditary discrepancy of the regular $d$-dimensional grid $[n]^d$, where $[n]=\{1,2,\ldots,n\}$. By a standard and well known reduction, instead of all $d$-dimensional intervals in ${\mathcal{R}}_d$, it suffices to consider only "anchored" intervals, of the form $[0,b_1]\times\cdots\times[0,b_d]$. Now the main observation is that the set system ${\mathcal{G}}_{d,n}$ induced on $[n]^d$ by anchored intervals is a $d$-fold product of the system ${\mathcal{I}}_n$ of one-dimensional intervals mentioned earlier, and its incidence matrix is the $d$-fold Kronecker product of the matrix $T_n$. Thus, by the properties of the $\gamma_2$ norm, we get that ${\gamma_2({\mathcal{G}}_{d,n})}$ is of order $\log^d n$, and inequality finishes the proof of Theorem \[t:tusnady\]. At the same time, using the other inequality , we obtain a new proof of the best known upper bound $\operatorname{disc}(n,{\mathcal{R}}_d)=O(\log^{d+1/2}n)$, with no extra effort. This proof is very different from the previously known ones and relatively simple. The same method also gives a surprisingly precise upper bound on the discrepancy of the set system of all subcubes of the $d$-dimensional cube $\{0,1\}^d$, where this time $d$ is a variable parameter, not a constant as before. This discrepancy has previously been studied in @chl-tbhd [@chaz-lvov-boxes; @NT-HAP], and it was known that it is between $2^{c_1d}$ and $2^{c_2d}$ for some constants $c_2>c_1>0$. In Section \[s:hibox\] we show that it is $2^{(c_0+o(1))d}$, for $c_0=\log_2(2/\sqrt 3)\approx 0.2075$. <span>**General theorems on discrepancy.** </span> Transferring the various properties of the $\gamma_2$ norm into the setting of hereditary discrepancy via inequalities , , we obtain general results about the behavior of discrepancy under operations on set systems. In particular, we get a sharper version of a result of @almosttight concerning the discrepancy of the union of several set systems, and a new bound on the discrepancy of a set system ${\mathcal{F}}$ in which every set $F\in{\mathcal{F}}$ is a disjoint union $F_1\cup\cdots\cup F_t$, where ${\mathcal{F}}_1,\ldots,{\mathcal{F}}_t$ are given set systems and $F_i\in{\mathcal{F}}_i$, $i=1,2,\ldots,t$. These consequences are presented in Section \[s:disc-thms\], together with some examples showing them to be quantitatively near-tight. <span>**Other problems in combinatorial discrepancy: new simple proofs.**</span> In Section \[s:sbounds\] we revisit two set systems for which discrepancy has been studied extensively: arithmetic progressions in $[n]$ and intervals in $k$ permutations of $[n]$. In both of these cases, asymptotically tight bounds have been known. Using the $\gamma_2$ norm we recover almost tight upper bounds, up to a factor of $\sqrt{\log n}$, with very short proofs. <span>**Immediate applications in computer science.**</span> Our lower bound for Tusnády's problem implies a lower bound of $\sqrt{t_ut_q} = \Omega(\log^{d}n)$ on the update time $t_u$ and query time $t_q$ of constant multiplicity oblivious data structures for orthogonal range searching in ${{\mathbb{R}}}^d$ in the group model. This is tight up to a constant, and strengthens a prior result of Larsen, who showed $\sqrt{t_ut_q} \geq \log^{(d-1)/2} n$ @larsen14. Our lower bound is incomparable with the results of Fredman @Fredman82, who proved the lower bound $(t_u + t_q)/2 = \Omega(\log n)$ only for $d=1$ but in a stronger model that makes no assumption on multiplicity. The relationship between hereditary discrepancy and differential privacy from @MN-stoc12 and the lower bound for Tusnády's problem imply that the necessary error for computing orthogonal range counting queries under differential privacy is $\Omega(\log^{d-1}n)$, which is best possible up to a factor of $\log n$. Our lower and upper bounds on the discrepancy of subcubes of the Boolean cube $\{0,1\}^d$ and the results from @NTZ-diffprivacy imply that the necessary and sufficient error for computing marginal queries on $d$-attribute databases under differential privacy is $(2/\sqrt{3})^{d+o(d)}$. <span>**Discrepancy in communication complexity.**</span> A notion that is also known as discrepancy, but distinct from combinatorial or hereditary discrepancy, is a standard tool for proving lower bounds in communication complexity. It is commonly defined for an $m\times n$ matrix $A$ with entries in $\{-1, 1\}$ as $$\operatorname{rdisc}A := \min_P \max_{I,J} \Bigl|\sum_{i \in I, j \in J}{p_{ij}a_{ij}}\Bigr|,$$ where $P$ ranges over $m\times n$ matrices with non-negative entries such that $\sum{p_{ij}} = 1$, $I$ ranges over subsets of the rows of $A$, and $J$ ranges over subsets of the columns. To distinguish this notion from $\operatorname{disc}$, we call it "rectangle discrepancy". Linial and Shraibman @LinialS09-learning related $\operatorname{rdisc}$ to $\gamma_2$: they proved that $(\operatorname{rdisc}A)^{-1}$ is equal, up to constant factors, to $\min_B \gamma_2(B)$, where $B$ ranges $m\times n$ real matrices satisfying $a_{ij}b_{ij} \geq 1$ for all $i$ and $j$. Together with our results, this implies that there exists an absolute constant $C$ so that for any $m\times n$ matrix $A$ with entries in $\{-1, 1\}$ $$C\sqrt{\log m} \geq (\operatorname{rdisc}A)(\min_B\operatorname{herdisc}B) \geq \frac{1}{C\log m},$$ with the minimum taken over matrices $B$ as above. This is the first formal connection between hereditary discrepancy and rectangle discrepancy that we are aware of. The papers @LinialMSS07-signmatrices [@LinialS09-CC; @LinialS09-learning] further connect the $\gamma_2$ norm to various other complexity measures of sign matrices, in particular the margin and dimension complexity from learning theory, and randomized and quantum communication complexity. Using and , we can replace $\gamma_2$ with $\operatorname{herdisc}$ in each of these results, at the cost of losing polylogarithmic factors in the bounds. Properties of the $\gamma_2$ norm {#s:props} ================================= The $\gamma_2$ norm has various favorable properties, which make it a very convenient and powerful tool in studying hereditary discrepancy, as we will illustrate later on. We begin by recalling some classical facts. Known properties of $\gamma_2$ ------------------------------ Observe that the norm $\|B\|_{ 2\to\infty}$ is monotone non-increasing under removing rows of $B$. Similarly, $\|C\|_{1\to 2}$ is monotone non-increasing under removing columns of $C$. It then follows that $\gamma_2(A)$ is monotone non-increasing under taking an arbitrary submatrix of $A$: for any subset $I$ of the rows and any subset $J$ of the columns we have $$\label{e:monotone} \gamma_2(A_{I,J}) \leq \gamma_2(A),$$ where $A_{I,J}$ is the submatrix of $A$ induced by $I$ and $J$. This trivial observation turns out to be crucial for relating $\gamma_2$ and hereditary discrepancy. Next we observe that $\gamma_2$ is invariant under transposition. This is surely a well-known fact, but we give the short proof for completeness. \[l:transp\] ${\gamma_2(A)}={\gamma_2(A^T)}$. Let $A = B_0C_0$ be a factorization that achieves $\gamma_2(A)$, i.e. $\gamma_2(A) = \|B_0\|_{2\to\infty}\|C_0\|_{1\to 2}$. Since $A^T = C_0^T B_0^T$, $\|C_0^T\|_{2\to \infty} = \|C_0\|_{1\to 2}$ and $\|B_0^T\|_{1 \to 2} = \|B_0\|_{2\to \infty}$, we have $$\gamma_2(A^T) \leq \|C_0^T\|_{2\to \infty} \|B_0^T\|_{1\to 2} = \|C_0\|_{1\to 2} \|B_0\|_{2\to\infty}= \gamma_2(A).$$ The reverse inequality $\gamma_2(A) \leq \gamma_2(A^T)$ follows by symmetry. The next (non-obvious) fact implies that $\gamma_2$ is indeed a norm. For a proof see e.g. @Tomczak-J-book. \[Triangle inequality\]\[p:mnorm\] We have ${\gamma_2(A+B)}\le{\gamma_2(A)}+{\gamma_2(B)}$ for every two $m\times n$ real matrices $A,B$. <span>**Remark on the determinant lower bound.** </span> Here is an example showing that the determinant lower bound of Lovász et al. does not satisfy the (exact) triangle inequality: for $$A=\begin{pmatrix}1&1\\0&1\end{pmatrix}, \ \ B=\begin{pmatrix}1&0\\-1&1\end{pmatrix},$$ we have $\operatorname{detlb}A=\operatorname{detlb}B=1$, but $\operatorname{detlb}(A+B)=\sqrt 5$. It may still be that the determinant lower bound satisfies an approximate triangle inequality, say in the following sense: $\operatorname{detlb}(A_1+\cdots+A_t)\stackrel{?}{\le} O(t)\cdot \max_i \operatorname{detlb}A_i$. However, at present we can only prove this kind of inequality with $O(t^{3/2})$ instead of $O(t)$. <span>**Kronecker Product.**</span> Let $A$ be an $m\times n$ matrix and $B$ a $p\times q$ matrix. We recall that the *Kronecker product* $A\otimes B$ is the following $mp\times nq$ matrix, consisting of $m\times n$ blocks of size $p\times q$ each: $$\begin{pmatrix} a_{11}B& a_{12}B&\ldots& a_{1n}B\\ \vdots &\vdots&\vdots&\vdots\\ a_{m1}B& a_{m2}B&\ldots&a_{mn}B \end{pmatrix}$$ In @LeeSS08 it was shown that $\gamma_2$ is multiplicative with respect to the Kronecker product: \[<span>@LeeSS08 [Thm. 17]</span>\]\[t:krone\] For every two matrices $A,B$ we have $${\gamma_2(A\otimes B)}={\gamma_2(A)}\cdot{\gamma_2(B)}.$$ <span>**Semidefinite and dual formulations.**</span> We recall a formulation of ${\gamma_2(A)}$ as a semidefinite program. For matrices with entries in $\{-1, 1\}$ this program was given in @LinialMSS07-signmatrices; the (easy) generalization to general matrices can be found in @LeeSS08. We have $$\begin{array}{rll} {\gamma_2(A)} = \min t&\mbox{s.t. }\\ &X_{ii} \leq t& i=1, \ldots, m+n,\\ &X_{i,m+j} = a_{ij}& i= 1, \ldots, m, j = 1, \ldots, n,\\ &X \succeq 0 \end{array}$$ Using standard techniques in convex optimization, e.g. the ellipsoid algorithm @gls-gaco-88, the program above can be solved to any given degree of accuracy in time polynomial in $m$, $n$, and the bit representation of $A$. This gives a polynomial time algorithm to approximate $\gamma_2(A)$ arbitrarily well. Using the semidefinite formulation, and the duality theory for semidefinite programming, Lee, Shraibman and Špalek @LeeSS08 derived a dual characterization of the $\gamma_2$ norm as a maximization problem. This characterization is a basic tool for bounding $\gamma_2$ from below. Let $\|A\|_*$ denote the *nuclear norm* of a matrix $A$, which is the sum of the singular values of $A$ (other names for $\|A\|_*$ are *Schatten $1$-norm*, *trace norm*, or *Ky Fan $n$-norm*; see the text by Bhatia @Bhatia-MA for general background on symmetric matrix norms). \[<span>@LeeSS08 [Thm. 9]</span>\]\[t:e8dual\] We have $${\gamma_2(A)}=\max\{\|P^{1/2}AQ^{1/2}\|_*: P,Q \mbox{ diagonal}, \mbox{nonnegative}, \operatorname{Tr}P=\operatorname{Tr}Q=1\}.$$ In particular, several times we will use this theorem with $A$ a square matrix and $P=Q=\frac 1n I_n$, in which case it gives ${\gamma_2(A)}\ge \frac1n\|A\|_*$. Putting matrices side-by-side ----------------------------- We can strengthen the triangle inequality for $\gamma_2$ when the matrices have disjoint supports. <span>**On ellipsoids.** </span> An ellipsoid $E$ in ${{\mathbb{R}}}^m$ is often defined as $\{x\in{{\mathbb{R}}}^m: x^TMx\le 1\}$, where $M$ is a positive definite matrix. Here we will mostly work with the *dual matrix* $D=M^{-1}$. Using this dual matrix we have (see, e.g., @combinElli) $$\label{e:duel} E =E(D)= \{ z\in {{\mathbb{R}}}^m : z^Tx \leq \sqrt{x^TDx} \mbox{ for all } x\in {{\mathbb{R}}}^m\}.$$ This definition can also be used for $D$ only positive semidefinite; if $D$ is singular, then $E(D)$ is a flat (lower-dimensional) ellipsoid. We will use the following formula for $\|E(D)\|_\infty$: \[l:dual-e8\] For any $m\times m$ positive semidefinite matrix $D$, $\|E(D)\|_\infty = \max_i \sqrt{d_{ii}}$. Let $t:= \max_i \sqrt{d_{ii}}$, and let $e_i$ be the $i$-th standard basis vector of ${{\mathbb{R}}}^m$. By the definition of $E(D)$, we have that $\forall z \in E(D): z_i = z^T e_i \leq \sqrt{e_i^T De_i} = \sqrt{d_{ii}}$, and, similarly, $-z_i \leq \sqrt{d_{ii}}$. This implies that for any $z \in E(D)$, $\|z\|_\infty \leq t$, and, therefore, $\|E(D)\|_\infty \leq t$. Next we show that there exists a point $z \in E(D)$ such that $\|z\|_\infty \geq t$, which implies $\|E(D)\|_\infty \geq t$ as well. Let $i_0$ be such that $\sqrt{d_{i_0, i_0}} = t$, and define $z:= De_{i_0}/t$. Then, by the Cauchy-Schwarz inequality $$\forall x \in {{\mathbb{R}}}^m: z^T x = \frac{1}{t} e_{i_0}^T D x \leq \frac1t \sqrt{(e_{i_0}^TDe_{i_0})(x^TDx)} = \sqrt{x^TDx},$$ so $z \in E(D)$. Moreover, $\|z\|_\infty \geq z_{i_0} = d_{i_0,i_0}/t = t$. \[l:union\] Let $A,B$ be matrices, each with $m$ rows, and let $C$ be a matrix in which each column is a column of $A$ or of $B$. Then $${\gamma_2(C)}^2\le{\gamma_2(A)}^2+{\gamma_2(B)}^2.$$ After possibly reordering the columns of $C$, we can write $C=\tilde A+\tilde B$, where the first $k$ columns of $\tilde A$ are among the columns of $A$ and the remaining $\ell$ columns are zeros, and the last $\ell$ columns of $\tilde B$ are among the columns of $B$ and the first $k$ are zeros. By , $a:={\gamma_2(\tilde A)}\le {\gamma_2(A)}$, $b:={\gamma_2(\tilde B)}\le{\gamma_2(B)}$. We will work with the geometric definition of $\gamma_2$. Let $E_1=E(D_1)$ and $E_2=E(D_2)$ be ellipsoids witnessing ${\gamma_2(\tilde A)}$ and ${\gamma_2(\tilde B)}$, respectively. We claim that the ellipsoid $E(D_1+D_2)$ contains all columns of $A$ and also all columns of $B$. This is clear from the definition of the ellipsoid $E(D)=\{z:z^Tx\le\sqrt{x^TDx}\mbox{ for all }x\}$, since for every $x$, we have $$x^T(D_1+D_2)x=x^TD_1x+x^TD_2x\ge \max\{ x^TD_1x, x^TD_2x\}$$ by the positive semidefiniteness of $D_1$ and $D_2$. All the diagonal entries of $D_1$ are bounded above by $a^2$, those of $D_2$ are at most $b^2$, and hence $\|E\|_\infty\le \sqrt{a^2+b^2}$ by Lemma \[l:dual-e8\]. \[l:disjsupp\] If $C$ is a block-diagonal matrix with blocks $A$ and $B$ on the diagonal, then ${\gamma_2(C)}=\max\{{\gamma_2(A)},{\gamma_2(B)}\}$. The inequality ${\gamma_2(C)} \geq \max\{{\gamma_2(A)},{\gamma_2(B)}\}$ is a direct consequence of . Next we prove the reverse direction. If $D_1$ is the dual matrix of the ellipsoid witnessing ${\gamma_2(A)}$ and similarly for $D_2$ and $B$, then the block-diagonal matrix $D$ with blocks $D_1$ and $D_2$ on the diagonal defines an ellipsoid containing all columns of $C$. This is easy to check using the formula defining $E(D)$ and the fact that a sum of positive definite matrices is positive definite. The inequality ${\gamma_2(C)} \leq \max\{{\gamma_2(A)},{\gamma_2(B)}\}$ then follows from Lemma \[l:dual-e8\]. Relating the $\gamma_2$ norm and hereditary discrepancy {#s:devi} ======================================================= Here we prove the inequalities and relating ${\gamma_2(.)}$ and $\operatorname{herdisc}(.)$. We also argue that the is asymptotically tight. In Section \[s:ints\] we will give an example on which is asymptotically tight as well. The $\gamma_2$ norm is at most $\log m$ times herdisc {#s:simplified-ineq1} ----------------------------------------------------- We will actually establish the following inequalities relating the $\gamma_2$ norm to the determinant lower bound. \[t:detlb-E8\] For any $m \times n$ matrix $A$ of rank $r$, $$\operatorname{detlb}A \leq {\gamma_2(A)} \leq O(\log r)\cdot \operatorname{detlb}A.$$ Inequality is an immediate consequence of the second inequality in the theorem (and of $r \leq \min\{m,n\}$): $${\gamma_2(A)}\le O(\log \min\{m,n\})\cdot \operatorname{detlb}A\le O(\log \min\{m,n\})\operatorname{herdisc}A,$$ where the last inequality uses the Lovász–Spencer–Vesztergombi bound $\operatorname{herdisc}A\ge\frac12\operatorname{detlb}A$. First we prepare a lemma for the proof of Theorem \[t:detlb-E8\]; it is similar to an argument in @almosttight. As a motivation, we recall the Binet–Cauchy formula: if $A$ is a $k\times n$ matrix, $k\le n$, then $\det AA^T=\sum_{J} (\det A_J)^2$, where the sum is over all $k$-element subsets $J\subseteq[n]$, and $A_J$ denotes the submatrix of $A$ consisting of the columns indexed by $J$. Consequently, for at least one of the $J$'s we have $(\det A_J)^2\ge {n\choose k}^{-1}\det AA^T$. The next lemma is a weighted version of this argument, where the columns of $A$ are given nonnegative real weights. \[l:binetcauchy\] Let $A$ be an $k\times n$ matrix, and let $W$ be a nonnegative diagonal unit-trace $n\times n$ matrix. Then there exists a $k$-element set $J \subseteq [n]$ such that $$|\det A_J|^{1/k} \geq \sqrt{k/e}\cdot|\det AWA^T|^{1/2k}.$$ Applying the Binet–Cauchy formula to the matrix $AW^{1/2}$ and slightly simplifying, we have $$\det AWA^T = \sum_{J}{(\det A_J)^2\prod_{j \in J}{w_{jj}}}.$$ Now $\sum_J \prod_{j \in J}{w_{jj}}\le \frac{1}{k!} \bigl(\sum_{j=1}^n{w_{jj}}\bigr)^k = \frac{1}{k!}$, because each term of the left-hand side appears $k!$-times on the right-hand side (and the weights $w_{jj}$ are nonnegative and sum to 1). Therefore $$\begin{aligned} \det AWA^T &\leq & \Bigl(\max_J (\det A_J)^2\Bigr) \sum_J\prod_{j \in J}w_{jj}\\ &\leq &\frac{1}{k!} \max_J (\det A_J)^2. \end{aligned}$$ So there exists a $k$-element $J$ with $$|\det A_J|^{1/k} \geq (k!)^{1/2k}|\det AWA^T|^{1/2k} \geq \sqrt{k/e}\cdot |\det AWA^T|^{1/2k},$$ where the last inequality follows from the estimate $k! \geq (k/e)^k$. \[Proof of Theorem \[t:detlb-E8\]\] For the inequality $\operatorname{detlb}A \leq {\gamma_2(A)}$, we first observe that if $B$ is a $k\times k$ matrix, then $$\label{e:AGsing} |\det B|^{1/k}\le \frac 1k\|B\|_*$$ Indeed, the left-hand side is the geometric mean of the singular values of $B$, while the right-hand side is the arithmetic mean. Now let $B$ be a $k\times k$ submatrix of $A$ with $\operatorname{detlb}A=|\det B|^{1/k}$; then $$\operatorname{detlb}A=|\det B|^{1/k}\le \frac 1k\|B\|_*\le {\gamma_2(B)}\le{\gamma_2(A)}.$$ For the second inequality ${\gamma_2(A)} = O(\log m)\cdot \operatorname{detlb}A$, the idea is, roughly speaking, to compare $\det BB^T$ and the nuclear norm of $B$ for a (rectangular) matrix $B$ whose singular values are all nearly the same, say within a factor of $2$, since then the arithmetic-geometric inequality is nearly an equality. Obtaining a suitable $B$ and relating $\det BB^T$ to the determinant of a square submatrix of $A$ needs some work, and it relies on Lemma \[l:binetcauchy\]. First let $P_0$ and $Q_0$ be diagonal unit-trace matrices with ${\gamma_2(A)}=\|P_0^{1/2}AQ_0^{1/2}\|$ as in Theorem \[t:e8dual\]. For brevity, let us write $\tilde A:=P_0^{1/2}AQ_0^{1/2}$, and let $\sigma_1\ge\sigma_2\ge\cdots\ge \sigma_r > 0$ be the nonzero singular values of $\tilde A$. By a standard bucketing argument (see, e.g., @almosttight [Lemma 7]), there is some $t>0$ such that if we set $K:=\{i\in[m]: t\le\sigma_i<2t\}$, then $$\sum_{i\in K}\sigma_i\ge \Omega(\tfrac1{\log r})\sum_{i=1}^m\sigma_i.$$ Let us set $k:=|K|$. Next, we define a suitable $k\times n$ matrix with singular values $\sigma_i$, $i\in K$. Let $\tilde A=U\Sigma V^T$ be the singular-value decomposition of $\tilde A$, with $U$ and $V$ orthogonal and $\Sigma$ having $\sigma_1,\ldots,\sigma_r$ on the main diagonal. Let $\Pi_K$ be the $k\times m$ matrix corresponding to the projection on the coordinates indexed by $K$; that is, $\Pi_K$ has $1$s in positions $(1,i_1), \ldots, (k, i_k)$, where $i_1 < \ldots < i_k$ are the elements of $K$. The matrix $\Pi_K\Sigma=\Pi_KU^T \tilde A V=U_K^T\tilde AV$ has singular values $\sigma_i$, $i\in K$, and so does the matrix $U_K^T\tilde A$, since right multiplication by the orthogonal matrix $V^T$ does not change the singular values. This $k\times m$ matrix $U_K^T\tilde A$ is going to be the matrix $B$ alluded to in the sketch of the proof idea above. We have $$|\det BB^T|^{1/2k}=\Bigl(\prod_{i\in K}\sigma_i\Bigr)^{1/k}\ge \frac{1}{2k}\sum_{i\in K}\sigma_i=\Omega\bigl(\tfrac 1{k\log r}\bigr){\gamma_2(A)}.$$ It remains to relate $\det BB^T$ to the determinant of a square submatrix of $A$, and this is where Lemma \[l:binetcauchy\] is applied—actually applied twice, once for columns, and once for rows. First we set $C:=U_K^T P_0^{1/2}A$; then $B=CQ_0^{1/2}$. Applying Lemma \[l:binetcauchy\] with $C$ in the role of $A$ and $Q_0$ in the role of $W$, we obtain a $k$-element index set $J\subseteq [n]$ such that $$|\det C_J|^{1/k}\ge \sqrt{k/e}\cdot |\det BB^T|^{1/2k}.$$ Next, we set $D:= P_0^{1/2}A_J$, and we claim that $\det D^TD\ge (\det C_J)^2$. Indeed, we have $C_J = U_K^TD$, and, since $U$ is an orthogonal transformation, $(U^TD)^T(U^TD) = D^T D$. Then, by the Binet–Cauchy formula, $$\begin{aligned} \det D^T D = \det (U^TD)^T (U^TD) &= \sum_{L}{(\det U_L^TD)^2} \\ &\geq (\det U^T_KD)^2 = (\det C_J)^2.\end{aligned}$$ The next (and last) step is analogous. We have $D^T=A_J^TP_0^{1/2}$, and so we apply Lemma \[l:binetcauchy\] with $A_J^T$ in the role of $A$ and $P_0$ in the role of $W$, obtaining a $k$-element subset $I\subseteq[m]$ with $|\det A_{I,J}|^{1/k}\ge \sqrt{k/e}\cdot|\det D^TD|^{1/2k}$ (where $A_{I,J}$ is the submatrix of $A$ with rows indexed by $I$ and columns by $J$). Following the chain of inequalities backwards, we have $$\begin{aligned} \operatorname{detlb}A&\ge & |\det A_{I,J}|^{1/k}\ge \sqrt{k/e}\cdot|\det D^TD|^{1/2k}\ge \sqrt{k/e}\cdot |\det C_J|^{1/k}\\ &\ge &(k/e)|\det BB^T|^{1/2k}= \Omega\bigl(\tfrac 1{\log r}\bigr){\gamma_2(A)},\end{aligned}$$ and the theorem is proved. In Section \[s:ints\] we will see that inequality is asymptotically tight. Let us now mention a simple but perhaps useful observation, which gives a somewhat weaker result. There are examples of set systems ${\mathcal{F}}_1,{\mathcal{F}}_2$ on an $n$-point set $X$ such that $|{\mathcal{F}}_1|,|{\mathcal{F}}_2|=O(n)$, $\operatorname{herdisc}{\mathcal{F}}_1$ and $\operatorname{herdisc}{\mathcal{F}}_2$ are bounded by a constant (actually by $1$), and $\operatorname{herdisc}({\mathcal{F}}_1\cup{\mathcal{F}}_2)= \Omega(\log n)$ @palvo-wedges [@newman2012beck]. Therefore, no quantity obeying the triangle inequality (possibly up to a constant), such as the $\gamma_2$ norm, can approximate $\operatorname{herdisc}$ with a factor better than $\log n$. The hereditary discrepancy is at most $\sqrt{\log m}$ times $\gamma_2$ ---------------------------------------------------------------------- In the proof of inequality we use a remarkable result of Banaszczyk, which we state next. \[@banasz98\]\[t:bana\] Let $c_1,\ldots,c_n$ be vectors in the Euclidean unit ball $B^m\subset{{\mathbb{R}}}^m$ and let $K\subseteq{{\mathbb{R}}}^m$ be a convex body with Gaussian measure $$(2\pi)^{-m/2}\int_Ke^{-\|x\|^2/2}{\,\mathrm{d}x}\ge\frac 12.$$ Then there is a vector $x=(x_1,\ldots,x_n)\in\{-1,1\}^n$ of signs such that $\sum_{j=1}^n x_jc_j\in D_0\cdot K$, where $D_0$ is an absolute constant. We prove the following theorem: \[t:ub\] For any $m\times n$ matrix $A$, $$\operatorname{disc}A = O(\sqrt{\log m})\cdot \gamma_2(A).$$ While Theorem \[t:ub\] at first appears weaker than inequality , it in fact implies it, due to the monotonicity of $\gamma_2$. Indeed, by , we have $$\operatorname{herdisc}A = \max_{J\subseteq[n]}\operatorname{disc}A_J \leq O(\sqrt{\log m}\,)\cdot \max_{J\subseteq [n]}\gamma_2(A_J) \leq O(\sqrt{\log m})\gamma_2(A).$$ \[Proof of Theorem \[t:ub\]\] Let $A = B_0C_0$ be a factorization of $A$ achieving $\gamma_2(A)$, such that $\|C_0\|_{1\to 2} = 1$ and $\|B_0\|_{2\to\infty} = \gamma_2(A)$. Without loss of generality, we can assume that $B_0$ is an $m\times m$ matrix and $C_0$ is an $m\times n$ matrix. Let $b_1, \ldots, b_m\in{{\mathbb{R}}}^m$ be the rows of $B_0$ and $c_1, \ldots, c_n \in {{\mathbb{R}}}^m$ be the columns of $C_0$. By our choice of $B_0$ and $C_0$, $\|b_i\|_2 \leq \gamma_2(A)$ for all $1 \leq i \leq m$, and $\|c_j\|_2 \leq 1$ for all $1 \leq j \leq n$. Define the convex body $K := \{x: \|B_0x\|_\infty \leq D\gamma_2(A)\}$ for a scalar $D$ to be determined later. $K$ is the intersection of the $m$ centrally symmetric slabs $\{x: |b_i^T x| \leq D\gamma_2(A)\}$, $i = 1, \ldots, m$. By Šidak's lemma (see @Ball01-survey for a simple proof), the Gaussian measure of $K$ is at least the product of the measures of the slabs, i.e. $$(2\pi)^{-m/2}\int_Ke^{-\|x\|^2/2}{\,\mathrm{d}x} \geq \prod_{i = 1}^m{\sqrt{2\pi}\int_{-\beta_i}^{\beta_i}e^{-y^2/2}{\,\mathrm{d}y}},$$ where $\beta_i := \frac{D\gamma_2(A)}{\|b_i\|_2} \geq D$ is the half-width of the $i$-th slab. By standard Gaussian concentration results, we have $\sqrt{2\pi}\int_{-\beta_i}^{\beta_i}e^{-y^2/2}{\,\mathrm{d}y} \geq 1 - e^{-\beta_i^2/2} \geq 1 - e^{-D^2/2}$, and, therefore, $$(2\pi)^{-m/2}\int_Ke^{-\|x\|^2/2}{\,\mathrm{d}x} \geq (1-e^{-D^2/2})^m.$$ Letting $D$ be a suitable constant multiple of $\sqrt{\log m}$, the above inequality implies that the Gaussian measure of $K$ is at least $1/2$. We can then apply Theorem \[t:bana\] and conclude that there exists a vector of signs $x = (x_1, \ldots, x_n) \in \{-1, 1\}^n$ so that $$\sum_j{x_j c_j} \in D_0\cdot K \Leftrightarrow \|Ax\|_\infty = \Bigl\|\sum_j{x_j Bc_j}\Bigr\|_\infty \leq D_0D\cdot\gamma_2(A).$$ Since $D = O(\sqrt{\log m}\,)$, this completes the proof. An argument similar to the proof above was used by Larsen in his work on oblivious data structures in the group model @larsen14. Next, we show that $\sqrt{\log m}$ in inequality cannot be replaced by any asymptotically smaller factor. \[t:biggerherdisc\] For all $m$, there are $m\times n$ matrices $A$, with $n=\Theta(\log m)$, such that $$\operatorname{disc}A\ge \Omega(\sqrt{\log m}\,)\cdot{\gamma_2(A)}.$$ A very simple example is the incidence matrix $A$ of the system of all subsets of $[n]$, with $m=2^n$, whose discrepancy is $n/2=\Theta(\log m)$. Indeed, the characteristic vectors of all sets have Euclidean norm at most $\sqrt n$, and hence, using the trivial factorization $A = AI$, the $\gamma_2$ norm is at most $\sqrt n=O(\sqrt{\log m}\,)$. Here is another proof, which perhaps provides more insight into the geometric reason behind the theorem. Let us consider the unit cube $C^m:=[-1,1]^m$ in ${{\mathbb{R}}}^m$. By the quantitative Dvoretzky theorem, there is a linear subspace $F\subset{{\mathbb{R}}}^m$ of dimension $k=\Theta(\log m)$ such that the slice $S:=F\cap C^m$ is $2$-almost spherical; that is, if $B_F$ denotes the largest Euclidean ball in $F$ centered at $0$ contained in $S$, then $S\subseteq 2B_F$ (see, e.g., @Ball-ln [Lect. 2]). Let $r$ be the radius of $B_F$. Let us choose a system $a_1,\ldots,a_k$ of orthogonal vectors in $B_F$ of length $r$. These are the columns of the matrix $A$. We have ${\gamma_2(A)}\le 1$, since $B_F$ is a (degenerate) ellipsoid containing the $a_i$ and contained in $C^m$. (We are using the geometric definition of $\gamma_2$ here.) Every linear combination $\sum_{i=1}^k x_ia_i$, where $x_i\in\{-1,1\}$, has Euclidean norm $r\sqrt k$, and hence it does not belong to the cube $D\cdot C^m$ for any $D<\frac 12\sqrt k$. So $\operatorname{disc}A\ge \frac12\sqrt k= \Omega(\sqrt{\log m}\,)$. The $\gamma_2$ norm for intervals {#s:ints} ================================= In this section we deal with a particular example: the system ${\mathcal{I}}_n$ of all initial segments $\{1,2,\ldots,i\}$, $i=1,2,\ldots,n$, of $\{1,2,\ldots,n\}$. Its incidence matrix is $T_n$, the $n\times n$ matrix with $0$s above the main diagonal and $1$s everywhere else. It is well known, and easy to see, that $\operatorname{herdisc}T_n=1$. We will prove that ${\gamma_2(T_n)}$ is of order $\log n$. This shows that the $\gamma_2$ norm can be $\log n$ times larger than the hereditary discrepancy, and thus the inequality is asymptotically tight. Moreover, this example is one of the key ingredients in the proof of the lower bound on the $d$-dimensional Tusnády problem. \[p:ints\] We have ${\gamma_2(T_n)}=\Theta(\log n)$. The upper bound is easy but we discuss it a little in Section \[s:TnUB\]. The lower bound can be proved by combining results from @ForsterSS01 and @LinialMSS07-signmatrices. Forster et al. consider the $n\times n$ sign matrix $\tilde{T}_n$ with entries equal to $1$ above the main diagonal and $-1$ everywhere else. They show that the margin complexity of $\tilde{T}_n$ is $\Omega(\log n)$; since Linial et al. proved in @LinialMSS07-signmatrices that the margin complexity of any matrix is a lower bound on its $\gamma_2$ norm, it follows that $\gamma_2(\tilde{T}_n) = \Omega(\log n)$. Using the equality $T_n = \frac12 J_n - \frac12 T_n$, where $J_n$ is the $n$ by $n$ all-ones matrix, and the triangle inequality for $\gamma_2$, we get $\gamma_2(T_n) \geq \frac12 \gamma_2(\tilde{T}_n) - \frac12 = \Omega(\log n)$ as well. Below we give a more direct proof of the lower bound using the dual characterization of $\gamma_2$ from Theorem \[t:e8dual\]. Lower bound on ${\gamma_2(T_n)}$ {#s:singvals} --------------------------------- \[Proof of the lower bound in Proposition \[p:ints\]\] The nuclear norm $\|T_n\|_*$ can be computed exactly (we are indebted to Alan Edelman and Gil Strang for this fact); namely, the singular values of $T_n$ are $$\frac1{2\sin \frac{(2j-1)\pi}{4n+2}},\ \ \ j=1,2,\ldots,n.$$ Using the inequality $\sin x\le x$ for $x\ge 0$, we get $${\gamma_2(T_n)}\ge \frac 1n\|T_n\|_*\ge\frac {2n+1}{\pi n}\sum_{j=1}^n\frac 1{2j-1}=\Omega(\log n),$$ as needed. The singular values of $T_n$ can be obtained from the eigenvalues of the matrix $S_n:=(T_nT_n^T)^{-1}$ which, as is not difficult to check, has the following simple tridiagonal form: $$\begin{pmatrix} 2& -1& 0& 0&0& \ldots& 0&0&0\\ -1&2&-1&0&0&\ldots&0&0&0\\ 0&-1&2&-1&0&\ldots&0&0&0\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ 0&0&0&0&0&\ldots&-1&2&-1\\ 0&0&0&0&0&\ldots&0&-1&1 \end{pmatrix}$$ (the $1$ in the lower right corner is exceptional; the rest of the main diagonal are $2$s). By general properties of eigenvalues and singular values, if $\lambda_1,\ldots,\lambda_n$ are the eigenvalues of $S_n$, then the singular values of $T_n$ are $\lambda_1^{-1/2},\ldots, \lambda_n^{-1/2}$. The eigenvalues of $S_n$ are computed, as a part of more general theory, in Strang and MacNamara @StraMacNama [Sec. 9]; the calculation is not hard to verify since they also give the eigenvectors explicitly. One can also calculate the characteristic polynomial $p_n(x)$ of $S_n$: it satisfies the recurrence $p_{n+1} = (2-x)p_n - p_{n-1}$ with initial conditions $p_1 = 1-x$ and $p_0 = 1$, from which one can check that $p_n(x) = U_n\bigl(\frac{2-x}{2}\bigr) - U_{n-1}\bigl(\frac{2-x}{2}\bigr)$, where $U_n$ is the degree-$n$ Chebyshev polynomial of the second kind. The claimed roots of $p_n$ can then be verified using the trigonometric representation of $U_n$. <span>**Lower bound by Fourier analysis.**</span> The lower bound in Proposition \[p:ints\] can also be proved by relating $T_n$ to a circulant matrix, whose singular values can be estimated using Fourier analysis. Observe that if we put four copies of $T_n$ together in the following way $$\begin{pmatrix} T_n & T_n^T\\ T_n^T & T_n \end{pmatrix},$$ we obtain a circulant matrix, which we denote by ${C_{n+1,2n}}$; for example, for $n=3$, we have $$C_{4,6}=\begin{pmatrix} 1&0&0&1&1&1\\ 1&1&0&0&1&1\\ 1&1&1&0&0&1\\ 1&1&1&1&0&0\\ 0&1&1&1&1&0\\ 0&0&1&1&1&1 \end{pmatrix}.$$ We have $\|{C_{n+1,2n}}\|_* \leq 4\|T_n\|_*$ by the triangle inequality for the nuclear norm (and since $\|T_n^T\|_*= \|T_n\|_*$ and adding zero rows or columns does not change $\|.\|_*$). Thus, it suffices to prove $\|{C_{n+1,2n}}\|_*=\Omega(n\log n)$. Let $c$ be the first column of ${C_{n+1,2n}}$, i.e. a vector of $n+1$ ones followed by $n-1$ zeros, and let us use the shorthand $C := {C_{n+1,2n}}$. Let further $\omega = e^{-i 2\pi/n}$, where $i = \sqrt{-1}$ is the imaginary unit. It is well known that the eigenvalues of a circulant matrix with first column $c$ are the Fourier coefficients $\hat{c}_0, \ldots, \hat{c}_{n-1}$ of $c$: $$\hat{c}_j = \sum_{k = 0}^{s-1}{\omega^{jk}} = \frac{\omega^{js}- 1}{\omega^{j}-1}.$$ Since $C$ is a normal matrix (because $C^TC = CC^T$), its singular values are equal to the absolute values of its eigenvalues. Therefore, $\|C\|_* = \sum_{j = 0}^{n-1}{|\hat{c}_j|}$, so we need to bound this sum from below by $\Omega(n\log n)$. The sum can be estimated analogously to the well-known estimate of the $L_1$ norm of the Dirichlet kernel, giving the desired bound. An asymptotic upper bound and optimal ellipsoids {#s:TnUB} ------------------------------------------------ There are several ways of showing ${\gamma_2(T_n)}=O(\log n)$. One of them is using $\operatorname{herdisc}T_n=1$ and the inequality relating $\gamma_2$ to $\operatorname{herdisc}$. Here is another, explicit argument using the triangle inequality. As the next picture indicates, the lower triangular matrix $T_n$ can be expressed as $T_n=A_1+\cdots+A_t$, $t=O(\log n)$. (The shaded regions contain $1$s and the white ones $0$s; the picture is for $n=8$.) This decomposition corresponds to the decomposition of intervals into canonical (binary) ones, which is a standard trick in discrepancy theory. We have ${\gamma_2(A_i)}=1$ for each $i$: an all-ones matrix has $\gamma_2$ norm $1$ (since it can be factored as the outer product of the all-ones vector with itself), and each $A_i$ can be obtained from all-ones matrices by the block-diagonal construction as in Lemma \[l:disjsupp\] and by adding zero rows and columns. Hence ${\gamma_2(T_n)}\le \sum_{i=1}^t{\gamma_2(A_i)}=O(\log n)$. The upper bound obtained from this argument is actually $\lfloor\log_2n\rfloor+1$. Using the semidefinite programming formulation in @LinialMSS07-signmatrices and the SDP solvers SDPT3 and SeDuMi (for verification), with an interface through Matlab and the CVX system, we have calculated the values of ${\gamma_2(T_n)}$ and the corresponding optimal primal and dual solutions numerically, for $n$ up to $2^7=128$. The resulting values of ${\gamma_2(T_n)}$ are shown in Fig. \[f:optEllv2\], together with the $\lceil\log_2n\rceil+1$ upper bound and the lower bound of $\frac 1n\|T_n\|_*$ as in Section \[s:singvals\]. One can see that while $\frac 1n\|T_n\|_*$ is quite a good approximation, it is not tight, and also that the upper bound $\lceil\log_2n\rceil+1$ overestimates the actual value almost four times. We have also plotted the value of $\|B\|_{2\to\infty}\|C\|_{1\to 2}$ for a factorization $T_n = BC$ due to Fredman @Fredman82; asymptotically, the value achieved by his method is $\log_\lambda n + O(\log \log n)$ for $\lambda = 3 + 2\sqrt{2}$. Fredman's factorization uses matrices with entries in $\{-1, 0, 1\}$ and it is asymptotically optimal over such factorizations with respect to $\max\{\|B\|_{2\to\infty}, \|C\|_{1\to 2}\}$. It would be interesting to find the exact value of ${\gamma_2(T_n)}$ theoretically and to understand what the optimal ellipsoids look like. Fig. \[f:surf50mth\] shows a 3-dimensional plot of the entries of the dual matrix $D$ of an optimal ellipsoid for $T_{50}$; the two horizontal axes correspond to the rows and columns of $D$, and the vertical axis shows the magnitude of the entries. Similarly, in Fig. \[f:plot-dual50\] we have plotted the diagonal entries of $P$ in an optimal solution $(P,Q)$ to the dual program in Theorem \[t:e8dual\]; the horizontal axis corresponds to an index $i$ and the vertical axis to the value $P_{ii}$. The diagonal entries of the optimal $Q$ appear to be identical to those of $P$ after a rearrangement: $Q_{ii} = P_{n-i + 1, n-i + 1}$. For both plots the values are defined for integer indexes only, and we have used interpolation to produce smooth graphs. It seems that, as $n\to\infty$, the matrices of the optimal ellipsoids should converge (in a suitable sense) to some nice function, and so should the optimal dual solutions, but we do not yet have a guess what these functions might be—they may very well be known in some area of mathematics. General theorems about discrepancy {#s:disc-thms} ================================== <span>**Union of set systems.** </span> Using the inequality in Lemma \[l:union\] and inequalities ,, we obtain the following result, which is a somewhat sharper version of a theorem proved in @almosttight using the determinant lower bound: \[Union of set systems\] \[t:un\] Let ${\mathcal{F}}_1,\ldots,{\mathcal{F}}_t$ be set systems on an $n$-point ground set $V$, and let ${\mathcal{F}}={\mathcal{F}}_1\cup\cdots\cup{\mathcal{F}}_t$. Then $$\operatorname{herdisc}{\mathcal{F}}\le O\Bigl(\sqrt{\log|{\mathcal{F}}|}\Bigr) \biggl(\sum_{i=1}^t(\log|{\mathcal{F}}_i|)^2(\operatorname{herdisc}{\mathcal{F}}_i)^2\biggr)^{1/2}.$$ We note that if the set systems ${\mathcal{F}}_1$ and ${\mathcal{F}}_2$ have disjoint ground sets, then $\operatorname{herdisc}({\mathcal{F}}_1\cup{\mathcal{F}}_2)=\max(\operatorname{herdisc}{\mathcal{F}}_1, \operatorname{herdisc}{\mathcal{F}}_2)$, which can be regarded as a counterpart of Lemma \[l:disjsupp\]. <span>**Building sets from disjoint pieces.** </span> In a similar vein, the triangle inequality for $\gamma_2$ together with , immediately yield the following consequence: \[t:disjpieces\] Let ${\mathcal{F}}_1,\ldots,{\mathcal{F}}_t$ be set systems on an $n$-point ground set $V$, and let ${\mathcal{F}}$ be a set system such that for each $F\in{\mathcal{F}}$ there are pairwise disjoint sets $F_1\in{\mathcal{F}}_1$,…, $F_t\in{\mathcal{F}}_t$ so that $F=F_1\cup\cdots\cup F_t$. Then $$\operatorname{herdisc}{\mathcal{F}}\le O\Bigl(\sqrt{\log|{\mathcal{F}}|}\Bigr)\sum_{i=1}^t(\log|{\mathcal{F}}_i|)\operatorname{herdisc}{\mathcal{F}}_i.$$ In Section \[s:tusnady\] below, we will obtain an example showing that if each of the systems ${\mathcal{F}}_i$ in the theorem has hereditary discrepancy at most $D$, the system ${\mathcal{F}}$ may have discrepancy about $tD$, up to a logarithmic factor, and thus in this sense, the theorem is not far from worst-case optimal. <span>**Product set systems.** </span> Let ${\mathcal{F}}$ be a set system on a ground set $V$, and ${\mathcal{G}}$ a set system on a ground set $W$. Following Doerr, Srivastav, and Wehr @Doerr-al-productdisc (and probably many other sources), we define the product ${\mathcal{F}}\times{\mathcal{G}}$ as the set system $\{F\times G:F\in{\mathcal{F}}, G\in{\mathcal{G}}\}$ on $V\times W$. Since the incidence matrix of ${\mathcal{F}}\times{\mathcal{G}}$ is the Kronecker product of the incidence matrices of ${\mathcal{F}}$ and ${\mathcal{G}}$, from Theorem \[t:krone\] and the usual inequalities ,, we get that the hereditary discrepancy is approximately multiplicative: \[t:mult\] Let ${\mathcal{F}}_1,\ldots,{\mathcal{F}}_t$ be set systems, let $m_i=|{\mathcal{F}}_i|>1$ for all $i$, let ${\mathcal{F}}={\mathcal{F}}_1\times\cdots\times{\mathcal{F}}_t$, and let $D:=\prod_{i=1}^t\operatorname{herdisc}{\mathcal{F}}_i$. Then $$\frac{D} {C^t \log |{\mathcal{F}}| \prod_{i=1}^t\sqrt{\log m_i}} \le \operatorname{herdisc}{\mathcal{F}}\le D\cdot C^t\sqrt{\log |{\mathcal{F}}|}\prod_{i=1}^t\log m_i$$ with a suitable absolute constant $C$. In the proof of the bounds for Tusnády's problem in Section \[s:tusnady\] we will see that the upper bound is not far from being tight. Here we give a simple example showing that the lower bound is near-tight as well. Let $m=2^k$ with $k$ even and let ${\mathcal{P}}=2^{[k]}$ be the system of all subsets of the $k$-element set $[k]$. Then $|{\mathcal{P}}|=m$ and $\operatorname{herdisc}{\mathcal{P}}=k/2$. The lower bound in the theorem for the hereditary discrepancy of the $t$-fold product ${\mathcal{P}}^t$, assuming $t$ constant, is of order $D/\log^{t/2+1}m$, where $D=\operatorname{herdisc}({\mathcal{P}})^t$. On the other hand, it is well known that any system of $M$ sets on $n$ points has discrepancy $O(\sqrt{n\log M}\,)$ (this is witnessed by a random coloring; see, e.g., @s-tlpm-87 [@Chazelle-book; @m-gd]), which in our case, with $n=k^t$ and $M=m^t$, shows that $\operatorname{herdisc}({\mathcal{P}}^t)$ is at most of order $k^{t/2+1/2}\approx D/(\log m)^{t/2-1/2}$, which differs from the lower bound only by a factor of $\log^{3/2}m$, independent of $t$. On Tusnády's problem {#s:tusnady} ==================== \[Proof of Theorem \[t:tusnady\]\] The proof was already sketched in the introduction, so here we just present it slightly more formally. Let ${\mathcal{A}}_d\subseteq{\mathcal{R}}_d$ be the set of all *anchored* axis-parallel boxes, of the form $[0,b_1]\times\cdots\times [0,b_d]$. Clearly $\operatorname{disc}(n,{\mathcal{A}}_d)\le\operatorname{disc}(n,{\mathcal{R}}_d)$, and since every box $R\in{\mathcal{R}}_d$ can be expressed as a signed combination of at most $2^d$ anchored boxes, we have $\operatorname{disc}(n,{\mathcal{R}}_d)\le 2^d\operatorname{disc}(n,{\mathcal{A}}_d)$. Let us consider the $d$-dimensional grid $[n]^d\subset{{\mathbb{R}}}^d$ (with $n^d$ points), and let ${\mathcal{G}}_{d,n}={\mathcal{A}}_d([n]^d)$ be the subsets induced on it by anchored boxes. It suffices to prove that $\operatorname{herdisc}{\mathcal{G}}_{d,n}=\Omega(\log^{d-1}n)$, and for this, in view of inequality , it is enough to show that ${\gamma_2({\mathcal{G}}_{d,n})}=\Omega(\log^d n)$. Now ${\mathcal{G}}_{d,n}$ is (isomorphic to) the $d$-fold product ${\mathcal{I}}_n^d$ of the system of initial segments in $\{1,2,\ldots,n\}$, and so ${\gamma_2({\mathcal{G}}_{d,n})}={\gamma_2(T_n)}^d=\Theta(\log^dn)$ (Theorem \[t:krone\] and Proposition \[p:ints\]). This finishes the proof of the lower bound. To prove the upper bound $\operatorname{disc}(n,{\mathcal{R}}_d)=O(\log^{d+1/2}n)$, we consider an arbitrary $n$-point set $P\subset{{\mathbb{R}}}^d$. Since the set system ${\mathcal{A}}_d(P)$ is not changed by a monotone transformation of each of the coordinates, we may assume $P\subseteq [n]^d$. Hence $$\operatorname{disc}({\mathcal{A}}_d(P))\le\operatorname{herdisc}{\mathcal{G}}_{d,n} \le O({\gamma_2({\mathcal{G}}_{d,n})}\sqrt{\log n^d}\,)= O(\log^{d+1/2}n).$$ <span>**Near-optimality of the bounds in Theorems \[t:disjpieces\] and \[t:mult\].**</span> In Theorem \[t:mult\] (discrepancy for the product of set systems), if we set ${\mathcal{F}}_i={\mathcal{I}}_m$ for all $i=1,2,\ldots,t$, then the product of $\operatorname{herdisc}{\mathcal{F}}_i$ is $D=1$, while the hereditary discrepancy of the product is $\Omega(\log^{t-1}m)$ assuming $t$ constant. The upper bound in Theorem \[t:mult\] is $O(\log^{t+1/2}m)$. For Theorem
{'source': 'arXiv_out/1408'}