July 15, 2026
Towards a characterization of idempotent Schur multipliers
Marcel K. GohHamed Hatami
Abstract.It is conjectured that every idempotent Schur multiplier can be written as a finite sum of contractive idempotents. This conjecture is equivalent to the statement that any boolean matrix \(A\) with factorization norm \(|\!|A|\!|_{\gamma_2}\) at most \(\gamma\) can be expressed as a signed sum \[A = \sum_{i=1}^L \pm B_i,\] where, up to permutation of rows and columns, each \(B_i\) is a blow-up of an identity matrix, and \(L\) depends only on \(\gamma\). In this note we show that if \(A\) is an \(n\times n\) boolean matrix with \(|\!|A|\!|_{\gamma_2}\le \gamma\), then it admits such an expression with \(L = 2^{O(\gamma^9) + \mathop{\mathrm{log}^*}\nolimits\!n}\), where \(\mathop{\mathrm{log}^*}\nolimits\!\) is the iterated logarithm function.
As an application, any sequence of matrices with bounded factorization norm belongs to the complexity class \(\mathrm{P}^{\rm\scriptsize EQ}\) of communication problems with polylogarithmic equality-oracle complexity. Keywords.Schur multipliers, factorization norm, communication complexity. MSC2020 Classification.15B36, 47L80, 94D10.
Each bounded operator \(T\) on the space \(\ell_2\) of infinite square-summable real sequences admits the unique matrix representation \(\bigl( \langle Te_i, e_j\rangle \bigr)\) with respect to the standard basis \((e_i)\) of \(\ell_2\). We write \(B(\ell_2)\) for the set of bounded linear operators \(T:\ell_2\to \ell_2\), namely those with finite operator norm \(\left|\!\left|T\right|\!\right|\), and we freely identify each such \(T\) with its matrix.
Any infinite-dimensional real-valued matrix \(A\) acts on the space of infinite-dimensional matrices by sending \(T\mapsto A\circ T\), where \(\circ\) denotes the entrywise (Hadamard) product. We call \(A\) a Schur multiplier if \(A\circ T\in B(\ell_2)\) for every \(T\in B(\ell_2)\), or equivalently, if its Schur multiplier norm \[\left|\!\left|A\right|\!\right|_{\rm m}= \sup_{\substack{T\in B(\ell_2) \\ T \neq 0}} \frac{\left|\!\left|A\circ T\right|\!\right|}{\left|\!\left|T\right|\!\right|},\] is finite.
Because \(\left|\!\left|A\circ B\right|\!\right|_{\rm m}\le \left|\!\left|A\right|\!\right|_{\rm m}\cdot\left|\!\left|B\right|\!\right|_{\rm m}\) for all Schur multipliers \(A\) and \(B\), the set of Schur multipliers is a Banach algebra with respect to this norm. A Schur multiplier \(A\) is said to be idempotent if \(A\circ A = A\); any matrix satisfying this identity must be boolean, but not all infinite boolean matrices have finite Schur multiplier norm. There is, however, a simple characterization of boolean matrices with Schur multiplier norm at most \(1\) (the so-called contractive elements of the Schur multiplier algebra).
We say that a boolean matrix \(B:\mathbf{N}\times \mathbf{N}\to \{0,1\}\) is blocky if there exist families \(\{X_i\}_{i\in \mathbf{N}}\) and \(\{Y_i\}_{i\in \mathbf{N}}\), each pairwise disjoint, such that the support of \(B\) is exactly \[\bigcup_{i\in \mathbf{N}} X_i\times Y_i.\] Equivalently, blocky matrices are exactly those matrices that can be obtained by blowing up identity matrices (arbitrarily duplicating rows and columns), adding zero rows and columns, and applying a permutation to the rows and columns. For instance, identity matrices, zero matrices, and all-ones matrices are all blocky. It was shown by Livshits that a boolean matrix \(A\) satisfies \(\left|\!\left|A\right|\!\right|_{\rm m}\le 1\) if and only if it is blocky [1].
We define the block complexity \(\mathop{\mathrm{block}}(A)\) of a matrix \(A\) to be the smallest integer \(L\) such that there exist signs \(\sigma_1,\ldots,\sigma_L\) and blocky matrices \(B_1,\ldots,B_L\) with \[A = \sum_{i=1}^L \sigma_i B_i.\] By the triangle inequality, we have \(\left|\!\left|A\right|\!\right|_{\rm m}\le \mathop{\mathrm{block}}(A)\), and hence any boolean matrix with bounded block complexity is a Schur multiplier. Whether this represents a full characterization of all idempotent Schur multipliers is an open problem; that is, we do not know if every idempotent Schur multiplier can be written as a finite sum of contractive idempotents. This question dates back at least twenty years to a paper of Katavolos and Paulsen [2], and is considered a difficult open problem in the domain (see, e.g., [3] and [4]). A compactness argument shows that a positive resolution to the aforementioned question about infinite dimensional Schur multipliers is equivalent to the following conjecture concerning finite-dimensional matrices.
Let \(A\) be a finite-dimensional boolean matrix with \(\left|\!\left|A\right|\!\right|_{\rm m} \le \gamma\). Then \[\mathop{\mathrm{block}}(A)\le L,\] where \(L\) depends only on \(\gamma\).
[conjblocky] parallels the Cohen’s theorem regarding idempotents in the Fourier algebra [5] as well as its quantitative analogue, due to Green and Sanders [6]. We refer the reader to [7] for a fuller exposition.
The first progress toward [conjblocky] was made by Balla, Hambardzumyan, and Tomon [8], who proved that any finite-dimensional boolean matrix of bounded Schur multiplier norm contains a monochromatic submatrix of constant density.
For an \(n\times n\) boolean matrix \(A\), the bound \(\mathop{\mathrm{block}}(A)\le 2^{O(\gamma^7)}(\log n)^2\) was obtained in a previous paper of the authors [7]. In the present paper we improve this bound significantly. In the statement of the following theorem and throughout this paper, we use \(\mathop{\mathrm{log}^*}\nolimits\!\) to denote the iterated binary logarithm; for a real number \(x\ge 1\), \(\mathop{\mathrm{log}^*}\nolimits\!x\) is the number of times one has to apply the binary logarithm before obtaining a number at most \(1\).
Let \(A\) be an \(n\times n\) boolean matrix with \(\left|\!\left|A\right|\!\right|_{\rm m}\le \gamma\). Then \[\mathop{\mathrm{block}}(A) \le 2^{O(\gamma^9)+\mathop{\mathrm{log}^*}\nolimits\!n}\]
The bound we obtain falls short of proving [conjblocky] only by a factor of \(2^{\mathop{\mathrm{log}^*}\nolimits\!n}\). For a sense of scale, let \(\log^{(j)}\) denote the \(j\)-fold composition of \(\log\) with itself, and note that since the function \(\mathop{\mathrm{log}^*}\nolimits\!(n) = o(\log^{(j)}n)\) for all \(j\ge 1\), we also have \(2^{\mathop{\mathrm{log}^*}\nolimits\!n} = o(\log^{(j)}n)\) for all \(j\).
In the proof of [thmmain], instead of working directly with the definition of the Schur multiplier norm, we instead use the following alternative definition. The \(\gamma_2\) factorization norm (or the \(\gamma_2\) norm for short) of a real matrix \(A\) is defined to be \[|\!|A|\!|_{\gamma_2} = \min_{UV = A} \left|\!\left|U\right|\!\right|_{\rm row} \left|\!\left|V\right|\!\right|_{\rm col},\] where the minimum is taken over all factorizations \(UV\) of \(A\), \(\left|\!\left|U\right|\!\right|_{\rm row}\) is the largest \(\ell_2\)-norm of a row in \(U\) and \(\left|\!\left|V\right|\!\right|_{\rm col}\) is the largest \(\ell_2\)-norm of a column in \(V\). The \(\gamma_2\) norm cannot increase by restricting to a submatrix, since removing rows of \(U\) or columns of \(V\) never increases \(\left|\!\left|U\right|\!\right|_{\rm row}\) or \(\left|\!\left|V\right|\!\right|_{\rm col}\). In particular, \(|\!|A|\!|_{\gamma_2}\) is at least \(|\!|A|\!|_{\rm max} = \max_{(x,y)\in X\times Y} \bigl|A(x,y)\bigr|\). By a result of Grothendieck [9], \(\left|\!\left|A\right|\!\right|_{\rm m} = |\!|A|\!|_{\gamma_2}\) for every matrix \(A\).
We briefly record a consequence of [thmmain] in the realm of communication complexity. Let \(X\) and \(Y\) be finite sets and let \(A\in \{0,1\}^{X\times Y}\) be a boolean matrix indexed by these sets. Alice and Bob have access to an oracle that can take arbitrary inputs \(s\) and \(t\) from Alice and Bob respectively and output the bit \(\mathop{\mathbf{1}}\nolimits_{[s=t]}\) at unit cost. Together they wish to devise a protocol so that if Alice knows \(x\in X\) and Bob knows \(y\in Y\), they can determine the value of the bit \(A(x,y)\) in as few calls to the oracle as possible. The maximum number of oracle invocations needed (over all \(x\) and \(y\)) is the cost of a protocol, and the minimum cost of any protocol is the equality-oracle complexity of \(A\), denoted \(\mathop{\mathrm{D}}^{\rm\scriptsize EQ}(A)\). It is known [10] that \[\frac{1}{2}\log \mathop{\mathrm{block}}(A) \le \mathop{\mathrm{D}}^{\rm\scriptsize EQ}(A) \le \mathop{\mathrm{block}}(A)\] holds for any boolean matrix \(A\). [thmmain] implies that any \(n \times n\) boolean matrix \(A\) with \(|\!|A|\!|_{\gamma_2}\le \gamma\) has \(\mathop{\mathrm{D}}^{\rm\scriptsize EQ}(A)\lesssim_\gamma 2^{\mathop{\mathrm{log}^*}\nolimits\!n}\). Hence any sequence of matrices \(A_n\) with \(|\!|A_n|\!|_{\gamma_2} = O(1)\) belongs to the complexity class \(\mathrm{P}^{\rm\scriptsize EQ}\) of communication problems with polylogarithmic equality-oracle complexity.
Everywhere in this paper, \(\log\) denotes the binary logarithm. The expression \(f\lesssim g\) is synonymous with \(f = O(g)\), and \(f\gtrsim g\) with \(f=\Omega(g)\). These expressions always hide absolute constants unless we write, e.g., \(f \lesssim_\alpha g\) or \(f = \Omega_\alpha(g)\) to indicate that the implied constant depends on some parameter \(\alpha\).
We write \(A \in R^{X\times Y}\) to mean that \(A\) is a matrix with rows indexed by elements of \(X\), columns indexed by elements of \(Y\), and entries taking values in the set \(R\). For subsets \(X'\subseteq X\) and \(Y'\subseteq Y\), the expression \(A_{X'\times Y'}\) denotes the matrix \(A\) restricted to rows in \(X'\) and columns in \(Y'\).
In this section we collect auxiliary results that will be necessary in the proof of [thmmain]. The first synthesizes two propositions from [7].
Let \(\eta>0\) be a parameter and suppose that \(A\in \mathbf{R}^{X\times Y}\) has \(|\!|A|\!|_{\gamma_2}\le \gamma\) and \(|\!|A|\!|_{\rm max}\le M\). Then there exists a subset \(S\subseteq Y\) with \[|S|\ge |Y| \biggl(\frac{\eta}{\lceil 16M\rceil}\biggr)^{O(\gamma^4)}\] and a function \(g : X\to [-M,M]\) such that for every \(x\in X\), \[\Pr_{y \in S}\Bigl[\bigl| A(x,y) - g(x)\bigr|\ge 1/4 \Bigr]\le\eta.\]
Proof. Apply Propositions 3.2 and 3.1 of [7] (in that order) with \(\alpha = 1/8\). ◻
In addition to this, we also import the following two lemmas verbatim from [7].
Lemma 1 ([7], Proposition 4.1). Every \(A\in \mathbf{Z}^{X\times Y}\) satisfies \[\mathop{\mathrm{block}}(A) \le 2 \max_{x\in X} \sum_{y\in Y} \bigl| A(x,y)\bigr|.\]
Lemma 2 ([7], Proposition 4.2). Let \(v_1, \ldots, v_r\) be vectors in a Hilbert space, and let \(\widehat v = \mathop{\mathbf{E}}\nolimits_{i\in [r]} v_i\) denote their average. If \(\left|\!\left|v_i\right|\!\right| \le \gamma\) for all \(1\le i\le r\), and \(\left|\!\left|\widehat v\right|\!\right| = \theta\), then \[S = \bigl\{ i\in [r] : \left|\!\left|v_i-\widehat v\right|\!\right|^2 \le \left|\!\left|v_i\right|\!\right|^2 - \theta^2/2\bigr\},\] satisfies \(|S| \ge \theta^2 r / (2\gamma^2)\).
Lastly, we shall need the following technical lemma concerning the iterated logarithm.
Lemma 3 (Iterated logarithm). Given \(c>1\), let \(K_c = 2^{4 c \log (2c)}\) and for \(n\ge 2\), set \[t(n) = \begin{cases} 1, & n \le K_c; \\ 1+t(\log(n)^c), & n>K_c. \end{cases}\] Then for all \(n\ge 2\), \[t(n) \le \mathop{\mathrm{log}^*}\nolimits\!n .\]
Proof. The claim is immediate when \(n\le K_c\), so suppose that \(n>K_c\). Denote \(T=t(n)\), define the sequence \(n_1,\ldots, n_T\) recursively by \(n_1=n\) and \(n_{i+1}=(\log n_i)^c\) for every \(i\le T-1\). Note \(n_T \le K_c\), and \(n_i>K_c\) for all \(i<T\). Taking the logarithms, let \(\ell_i= \log n_i\), and note that \[\ell_{i+1}=c \log \ell_i.\] for all \(i\). Let \(M\) be the smallest positive integer such that \(\log^{(M)}n\leq 2\log(2c)\). We have \(2 \le M \le \mathop{\mathrm{log}^*}\nolimits\!n\), and it suffices to show that \(T\le M\). Suppose otherwise, so that \(T\ge M+1\); then \(n_1,\ldots,n_M\) are defined and, since \(i<T\) implies \(n_i>K_c\), we have \[\label{eq:l95i} \ell_i>\log K_c=4c\log(2c)\tag{1}\] for all \(i\le M\). We claim that \[\label{eq:superlog} \ell_j\le 2c\log^{(j)}n\tag{2}\] for every \(2\le j\le M-1\). First we see that \(\ell_2=c\log\ell_1=c\log^{(2)}n\), so () holds for \(j=2\). For the inductive step, suppose () holds for some \(j\) with \(j+1\le M-1\). Since \(j+1<M\), minimality of \(M\) gives \(\log^{(j+1)}n>2\log(2c)>\log(2c)\), and hence \[\ell_{j+1}=c\log\ell_j\le c\log\!\bigl(2c\log^{(j)}n\bigr)=c\log(2c)+c\log^{(j+1)}n\le 2c\log^{(j+1)}n,\] and our proof of () for all \(2\le j\le M-1\) is complete.
We now bound \(\ell_M\) to obtain a contradiction. If \(M=2\), then \[\ell_M=\ell_2=c\log^{(M)}n\le 2c\log(2c).\] If \(M\ge 3\), then () at \(j=M-1\) gives \(\ell_{M-1}\le 2c\log^{(M-1)}n\), so \[\ell_M=c\log\ell_{M-1}\le c\log(2c)+c\log^{(M)}n\le c\log(2c)+2c\log(2c)=3c\log(2c),\] where we have used the fact that \(\log^{(M)}n\le 2\log(2c)\). In either case, \(\ell_M\le 3c\log(2c)<4c\log(2c)\), contradicting (). Hence \(T\le M\le\mathop{\mathrm{log}^*}\nolimits\!n\). ◻
Just as in [7], we prove the main theorem by inductively proving a stronger statement regarding almost-integer matrices. Given a matrix \(A\in \mathbf{R}^{X\times Y}\), let \(A_\mathbf{Z}\in \mathbf{Z}^{X\times Y}\) denote the entrywise rounding of \(A\) to the nearest integer matrix, where we round \(m+1/2\) down to \(m\) for all \(m\in \mathbf{Z}\). For any parameter \(\epsilon> 0\), we say that a real-valued matrix \(A\in \mathbf{R}^{X\times Y}\) is \(\epsilon\)-almost integer-valued if \(|\!|A-A_\mathbf{Z}|\!|_{\rm max}\le \epsilon\).
Let \(A\in \mathbf{R}^{X\times Y}\) be a real-valued matrix. For any row \(x\in X\), let \[R_x(A) = \sum_{y\in Y} \bigl| A_\mathbf{Z}(x,y)\bigr|,\] and define \(D(A) = \max_{x\in X} R_x(A)\). Since \(\mathop{\mathrm{block}}(A_\mathbf{Z})\le 2D(A)\) holds unconditionally, the bound we are after is trivial unless \(D(A)\) is large. We may therefore assume throughout that \(D(A)=D\ge 4\), to guarantee \(\log D\ge 2\) for convenience.
Our main result shall be proved by iterating the following key lemma.
There is an absolute constant \(C'\ge 1\) such that the following holds for all \(\gamma\ge 1/2\) and all \(\epsilon,\eta>0\) with \[\eta\le\frac{1}{16\gamma^2} \qquad\text{and}\qquad \epsilon+4\gamma\eta\le\frac{1}{8} .\] Let \(A\in\mathbf{R}^{X\times Y}\) be a finite \(\epsilon\)-almost integer-valued matrix with \(|\!|A|\!|_{\gamma_2} \le \gamma\) and \(D(A)=D\ge 4\). Then there is an \(\epsilon'\)-almost integer-valued matrix \(A'\in\mathbf{R}^{X\times Y}\) such that
\(|\!|A-A'|\!|_{\gamma_2}^2\le\gamma^2-1/8\) and \(D(A-A')\le D\);
\(A'\) is a blow-up of a matrix \(G\) with \(|\!|G|\!|_{\gamma_2}\le\gamma\) and \(D(G)\le\eta^{-C'\gamma^5}\log D\);
\(\epsilon'\le\epsilon+4\gamma\eta\).
Proof. Write \(M=|\!|A|\!|_{\rm max}\) and recall the bound \(M\le\gamma\), which we shall invoke freely. Since \(D\ge 4\), some entry satisfies \(A_\mathbf{Z}(x,y)\ne 0\), whence \(M\ge 1-\epsilon\ge 1/2\). Fix a \(\gamma\)-factorization \(A=UV\), so that \[A(x,y)=\langle u_x,v_y\rangle,\qquad \left|\!\left|u_x\right|\!\right|\le 1,\qquadand\qquad\left|\!\left|v_y\right|\!\right|\le\gamma .\] To begin with, assume that \(A_\mathbf{Z}\) has no all-zero column; we shall justify this assumption at the very end of the proof.
We construct a partition \(Y=Y_1\cup\cdots\cup Y_t\) greedily. Suppose \(Y_1,\dots,Y_{i-1}\) have been built, let \[Z_i= Y\setminus(Y_1\cup\cdots\cup Y_{i-1}),\] and let \(A_i = A_{X\times Z_i}\) be the matrix of remaining columns. Put \(D_i= D(A_i)\) and let \(x_i\in X\) be a row attaining this value of \(D\), so that \(R_{x_i}(A_i)=D_i\). Since every column of \(A_\mathbf{Z}\) has a nonzero entry, \(D_i\ge 1\) as long as \(Z_i\ne\emptyset\).
The row \(x_i\) has \(R_{x_i}(A_i)=D_i\) and each of its entries has absolute value at most \(M+1\), so it has at least \(D_i/(M+1)\) nonzero entries in \(A_\mathbf{Z}\). These entries take at most \(2M+1\) distinct nonzero integer values, so by the pigeonhole principle there is a nonzero integer \(b_i\) with \(|b_i|\le M+1\) for which the set \[S_i=\bigl\{y\in Z_i:\;A_\mathbf{Z}(x_i,y)=b_i\bigr\}\] satisfies \[|S_i| \ge \frac{D_i}{(M+1)(2M+1)} \ge \frac{D_i}{12 M^2}.\]
By [propalphasubset], for each \(i\) there is a subset \(S_i'\subseteq S_i\) with \[|S_i'| \ge |S_i|\biggl( \frac{\eta}{\lceil 16M\rceil}\biggr)^{O(\gamma^4)} \gtrsim {\eta}^{O(\gamma^5)} D_i\] and a function \(g_i' : X\to [-M,M]\) satisfying \[\Pr_{y \in S'_i}\Bigl[\bigl| A(x,y) - g_i'(x)\bigr|\ge 1/4 \Bigr]\le\eta.\] Rounding this function \(g_i'\) to an integer-valued function \(g_i : X\to [-M-1, M+1]\), for every \(x\in X\) we have \[\label{eq:gi-agrees} \Pr_{y\in S_i'} \bigl[ A_\mathbf{Z}(x,y)\ne g_i(x) \bigr]\le \Pr_{y\in S_i'} \Bigl[ \bigl| A(x,y) - g_i'(x) \bigr| \ge 1/4\Bigr] \le \eta.\tag{3}\]
Let \(\widehat v_i=\mathop{\mathbf{E}}\nolimits_{y\in S_i'}v_y\). Since \(A_\mathbf{Z}(x_i,y)=b_i\) for all \(y\in S_i'\subseteq S_i\) and \(A\) is \(\epsilon\)-almost integer-valued, \[\bigl|\langle u_{x_i},\widehat v_i\rangle\bigr| =\Bigl|\mathop{\mathbf{E}}\nolimits_{y\in S_i'}A(x_i,y)\Bigr| \ge |b_i|-\epsilon\ge 1-\frac{1}{8} \ge \frac{1}{2} ,\] so \(\left|\!\left|\widehat v_i\right|\!\right|\ge 1/2\) by the Cauchy–Schwarz inequality and \(\left|\!\left|u_{x_i}\right|\!\right|\le 1\). Applying 2 to the vectors \(\{v_y\}_{y\in S_i'}\) (whose norms are at most \(\gamma\), and whose average \(\widehat v_i\) has norm \(\theta \ge 1/2\)) produces a set of columns \(Y_i\subseteq S_i'\) with \[\label{eq:Yi-size} |Y_i| \ge \frac{\theta^2}{2\gamma^2}|S_i'| \ge \frac{|S_i'|}{8\gamma^2} \gtrsim \eta^{O(\gamma^5)}D_i ,\tag{4}\] such that for every \(y\in Y_i\), \[\left|\!\left|v_y-\widehat v_i\right|\!\right|^2 \le \left|\!\left|v_y\right|\!\right|^2-\frac{\theta^2}{2} \le \gamma^2-\frac{1}{8} .\] Since \(Y_i\ne\emptyset\) at each stage, the procedure must terminate, producing the desired partition \(Y=Y_1\cup\cdots\cup Y_t\) together with rows \(x_i\), integers \(b_i\), functions \(g_i\), sets \(S_i'\supseteq Y_i\), and vectors \(\widehat v_i\). Since \(|S_i'|\le 8\gamma^2|Y_i|\) and \(\eta\le 1/(16\gamma^2)\), we have \[\label{eq:Si-vs-Yi} \eta|S_i'|\le 8\gamma^2\eta\,|Y_i|\le\frac{1}{2}|Y_i|.\tag{5}\]
Define \(G\in\mathbf{R}^{X\times[t]}\) by \[G(x,i)=\langle u_x,\widehat v_i\rangle\] and \(A'\in\mathbf{R}^{X\times Y}\) by \[\label{eq:A39factor} A'(x,y)=\mathop{\mathbf{E}}\nolimits_{y'\in S_i'}A(x,y')=\langle u_x,\widehat v_i\rangle=G(x,i)\tag{6}\] for \(y \in Y_i\). (Note that the average is over \(S_i'\), not \(Y_i\).) By construction \(A'\) is a blow-up of \(G\) (each column \(i\) of \(G\) being repeated \(|Y_i|\) times).
For \(y\in Y_i\), set \(\widetilde{v}_y= v_y-\widehat v_i\), so that \(\left|\!\left|\widetilde{v}_y\right|\!\right|^2\le\gamma^2-1/8\). Then \[A(x,y)-A'(x,y)=\langle u_x,\,v_y-\widehat v_i\rangle=\langle u_x,\widetilde{v}_y\rangle\] for each pair \((x,y)\in X\times Y_i\), and this factorization shows that \(|\!|A-A'|\!|_{\gamma_2}^2\le\gamma^2-1/8\). Moreover, each \(\widehat v_i\) is an average of vectors of norm at most \(\gamma\), so \(\left|\!\left|\widehat v_i\right|\!\right|\le\gamma\) and by (), we have \(|\!|G|\!|_{\gamma_2}\le\gamma\).
For every \(x\in X\), the fact that \(A\) is \(\epsilon\)-almost integer-valued combined with our earlier bound \[\Pr_{y\in S_i'}\bigl[ A_\mathbf{Z}(x,y)\ne g_i(x)\bigr] \le \eta\] shows that for all \(i\) and all \((x,y)\in X\times Y_i\), \[\bigl| A'(x,y) - g_i(x)\bigr| = \Bigl|\bigl(\mathop{\mathbf{E}}\nolimits_{y'\in S_i'} A(x,y') - g_i(x) \bigr)\Bigr| \le (1-\eta)\epsilon+ \eta (2M+1),\] yielding claim (iii) and also proving that \[\label{eq:A39round} A'_\mathbf{Z}(x,y)=g_i(x)=G_\mathbf{Z}(x,i)\tag{7}\] for all \(x\in X\) and \(y\in Y_i\).
We claim that for every row \(x\in X\) and every nonzero integer \(b\), \[\label{clm:multiplicity} \Bigl| \bigl\{i\in[t]: g_i(x)=b\bigr\}\Bigr| \le \eta^{-O(\gamma^5)}\log D.\tag{8}\] To prove the claim, fix a row \(x\in X\) and a nonzero integer \(b\), and abbreviate \(R_i= R_x(A_i)\). Since \(A_{i+1}\) is obtained from \(A_i\) by deleting the columns in \(Y_i\), the sequence \((R_i)\) is nonincreasing, and \[R_i-R_{i+1}=\sum_{y\in Y_i}\bigl|A_\mathbf{Z}(x,y)\bigr| .\] Suppose now that \(g_i(x)=b\). By (), all but at most \(\eta|S_i'|\) of the columns \(y\in Y_i\subseteq S_i'\) satisfy \(A_\mathbf{Z}(x,y)=b\), and each such column contributes \(|b|\ge 1\) to the sum above. Hence, using (), \[R_i-R_{i+1}\;\ge\;|b|\bigl(|Y_i|-\eta|S_i'|\bigr) \ge \frac{1}{2}|Y_i|.\]
On the other hand, by (), \[R_i \le D_i \le \eta^{-O(\gamma^5)}|Y_i|,\] so every \(1\le i\le t\) with \(g_i(x) = b\) must satisfy \[R_{i+1} \le \bigl(1-\eta^{O(\gamma^5)}\bigr) R_i \le e^{-\eta^{O(\gamma^5)}}R_i,\] and this together with \(R_1 \le D\) implies (). From here, one need only note that \[R_x(G) \le (2M+1)(M+1)\cdot\eta^{-O(\gamma^5)}\log D \le \eta^{-O(\gamma^5)}\log D,\] since \(R_x(G)=\sum_{i\in[t]}|g_i(x)|\). Hence \(D(G) \le \eta^{-O(\gamma^5)} \log D\).
Since \(\epsilon+\epsilon'<1/2\), we have \((A-A')_\mathbf{Z}=A_\mathbf{Z}-A'_\mathbf{Z}\). Fix a row \(x\in X\), and let \[E_i=\bigl\{y\in Y_i: A_\mathbf{Z}(x,y)\ne g_i(x)\bigr\}\] for each \(1\le i\le t\). By () and () we have \(|E_i|\le\eta|S_i'|\le |Y_i|/2\) for all \(i\), and therefore \(|E_i| \le |Y_i \setminus E_i|\). Then from (), we know that \(A'_\mathbf{Z}(x,y)=g_i(x)\) for all \(y\in Y_i\), so \(A_\mathbf{Z}-A'_\mathbf{Z}\) vanishes outside of \(\bigcup_i E_i\), and the triangle inequality gives \[\begin{align} R_x(A-A') & =\sum_i\sum_{y\in E_i}\bigl|A_\mathbf{Z}(x,y)-g_i(x)\bigr| \cr &\le \sum_i\sum_{y\in E_i}\bigl|A_\mathbf{Z}(x,y)\bigr| +\sum_i|E_i| \bigl|g_i(x)\bigr| \\ & \le \sum_i\sum_{y\in E_i}\bigl|A_\mathbf{Z}(x,y)\bigr| +\sum_i|Y_i \setminus E_i| \bigl|g_i(x)\bigr| \cr &=R_x(A). \cr \end{align}\] Taking the maximum over \(x\) yields \(D(A-A')\le D\).
Suppose finally that \(A_\mathbf{Z}\) has a nonempty set \(Y_0\) of all-zero columns. Run the above construction on \(A_{X\times(Y\setminus Y_0)}\), which has no such column and the same value of \(D\), and extend \(A'\) by setting \(A'(x,y)= A(x,y)\) for \(y\in Y_0\). Then \(A-A'\) vanishes on \(Y_0\), so (i) is unaffected; \(A'\) agrees with \(A\) on \(Y_0\), so it is still \(\epsilon'\)-almost integer-valued and the factorization \(A'(x,y)=\langle u_x,v_y\rangle\) on \(Y_0\) (together with () elsewhere) keeps \(|\!|A'|\!|_{\gamma_2}\le\gamma\). Finally, we append the \(Y_0\) columns of \(A\) to \(G\). The extended matrix still satisfies \(|\!|G|\!|_{\gamma_2}\le\gamma\), still has \(A'\) as a blow-up, and the appended columns round to zero, so \(D(G)\) is unchanged. ◻
Applying [lemkey] in an inductive argument now furnishes our desired bound on \(\mathop{\mathrm{block}}(A_\mathbf{Z})\). [thmmain] follows from the following more general statement about almost integer-valued matrices.
Theorem 1 (Generalized main theorem). There is an absolute constant \(C\ge 1\) such that every \(\epsilon\)-almost integer-valued matrix \(A\in \mathbf{R}^{X\times Y}\) with \(|\!|A|\!|_{\gamma_2} = \gamma\), \(D(A) = D \ge 4\), and \[\epsilon\le ( \log D)^{-8 \gamma^2}\] satisfies \[\mathop{\mathrm{block}}(A_\mathbf{Z}) \le 2^{C \gamma^9+\mathop{\mathrm{log}^*}\nolimits\!D }.\]
Proof. Because \(\epsilon\) will need to be bounded in terms of \(\gamma\) and \(D\) throughout our inductive proof, let \(\epsilon(s,D) = ( \log D)^{-8 s}\) to facilitate tracking these relations explicitly. For parameters \(s\ge 0\) and \(D\ge 4\), let \(b(s,D)\) denote the supremum of \(\mathop{\mathrm{block}}(A_\mathbf{Z})\) over all finite \(\epsilon\)-almost integer-valued matrices \(A\) with \(|\!|A|\!|_{\gamma_2}^2 \le s\), \(D(A) \le D\), and \(\epsilon\le \epsilon(s,D)\). Our goal is to bound \(b(\gamma^2,D)\).
Let \(C'\) be the constant from [lemkey]. By increasing \(C'\) if necessary, we may assume that \(C' \ge 1000\). First, suppose that \[\label{eq:D95large} \gamma \ge \frac{1}{2} \qquad \text{and}\qquad \log D>2^{20C'} \gamma^8,\tag{9}\] and suppose that \(A\) is a matrix realizing the value \(b(\gamma^2,D)\). By (), we can apply [lemkey] with \(\eta=\epsilon(\gamma^2,D)\) and write \(A=A_1+A_2\), where
\(|\!|A_1|\!|_{\gamma_2}^2\le\gamma^2-1/8\) and \(D(A_1)\le D\);
\(A_2\) is a blow-up of a matrix \(G\) with \(|\!|G|\!|_{\gamma_2}^2\le\gamma^2\) and \[\label{eq:Dexpo} D(G)\le\eta^{-C'\gamma^5}\log D=(\log D)^{8C'\gamma^7}\log D\le(\log D)^{9 C' \gamma^7},\tag{10}\] since \(C' \gamma^7 \ge 1\); and
both \(A_1\) and \(A_2\) are \(\epsilon'\)-almost integer-valued with \(\epsilon'\le 2\epsilon+4\gamma\eta\).
To recurse on \(A_1\) and on \(G\), we must check that the new bound \[\epsilon' \le 2\epsilon+4\gamma\eta\le (2+4\gamma)(\log D)^{-8\gamma^2}\] on the error keeps it within the required range.
For \(A_1\), whose parameters are \((\gamma^2-1/8, D)\), we have \[\frac{2\epsilon+4\gamma\eta}{\epsilon(\gamma^2-1/8,D)} \le \frac{(2+4\gamma)(\log D)^{-8\gamma^2}}{(\log D)^{1-8\gamma^2}}=\frac{2+4\gamma}{\log D} \le 1\] by (). For \(G\), whose parameters are \((\gamma^2,D(G))\) with \(\log D(G)\le 9 C' \gamma^7 \log\log D\), \[\label{eq:G95eps} \frac{2\epsilon+4\gamma\eta}{\epsilon(\gamma^2,\,D(G))} \le(2+4\gamma)\Bigl(\frac{9 C' \gamma^7 \log\log D}{\log D}\Bigr)^{8\gamma^2} \le (2+4\gamma) 2^{-8 \gamma^2} \le 1,\tag{11}\] where we have applied () to bound \[\frac{9 C' \gamma^7 \log\log D}{\log D} < \frac{1}{2}.\] We have thus verified that the error parameters resulting from our invocation of [lemkey] are compatible with the respective new values of \(\gamma\) and \(D\) to which they pertain. We now quantitatively analyze the recursion itself.
Fix \(\lambda=\gamma\), the factorization norm of the input matrix. Since the factorization norm never increases during the recursive step, every matrix that arises has factorization norm at most \(\lambda\); this lets us use the same exponent \[c= 9 C' \lambda^7\] throughout. Note that \[A_\mathbf{Z}=(A_1)_\mathbf{Z}+(A_2)_\mathbf{Z},\] and therefore \[\mathop{\mathrm{block}}(A_\mathbf{Z}) \le \mathop{\mathrm{block}}((A_1)_\mathbf{Z})+\mathop{\mathrm{block}}((A_2)_\mathbf{Z})= \mathop{\mathrm{block}}((A_1)_\mathbf{Z})+\mathop{\mathrm{block}}(G_\mathbf{Z}).\] Consequently, we have \[\label{eq:recb} b(\gamma^2,D)\le b\bigl(\gamma^2-1/8,D\bigr)+b\bigl(\gamma^2,\,(\log D)^c\bigr)\tag{12}\] whenever () holds, and by 1, \[\label{eq:recb-triv} b(\gamma^2,D)\le 2D\tag{13}\] holds unconditionally.
Towards a recursive computation of the function \(b\), we establish two base cases.
If \(\log D \le \max(\log K_c,2^{20C'} \gamma^8)\) (with \(K_c\) as in 3), then \[b(\gamma^2,D)\le 2D< 2^{O(\lambda^9)}.\]
If \(\gamma^2<1/4\), then \(|\!|A|\!|_{\rm max}<1/2\). Therefore, \(A_\mathbf{Z}=0\) and \(b(\gamma^2,D)\le 1\).
We can then expand () into a binary recursion tree, declaring a node a leaf as soon as (a) or (b) holds. At any internal node, the bounds () are satisfied and hence [lemkey] applies.
Along any root-to-leaf path, the first branch decreases \(\gamma^2\) by \(1/8\) and fixes \(D\), while the second branch fixes \(\gamma^2\) and applies \(D \mapsto(\log D)^{c}\). Therefore any path may contain at most \(8 \gamma^2\) steps of the first kind, and (by 3 applied to \(D\)) at most \(\mathop{\mathrm{log}^*}\nolimits\!D\) steps of the second kind. The tree has depth at most \(8 \gamma^2+\mathop{\mathrm{log}^*}\nolimits\!D\) and at most \(2^{8 \gamma^2+\mathop{\mathrm{log}^*}\nolimits\!D}\) leaves, each contributing at most \(2^{O(\lambda^9)}\) by (a) and (b). Consequently \[b(\gamma^2,D )\le 2^{8 \gamma^2+\mathop{\mathrm{log}^*}\nolimits\!D } \cdot2^{O(\gamma^9)} =2^{O(\gamma^9)+\mathop{\mathrm{log}^*}\nolimits\!D},\] as claimed. ◻
[thmmain] is now immediate, since any boolean \(n\times n\) matrix \(A\) is \(\epsilon\)-almost integer-valued for any \(\epsilon>0\) and satisfies \(D(A)\le n\).
Department of Mathematics and Statistics, McGill University, Montreal, Quebec, Canada
E-mail address: marcel.goh@mail.mcgill.ca
School of Computer Science, McGill University, Montreal, Quebec, Canada
E-mail address: hatami@cs.mcgill.ca