Proof. Let $r = \lceil S/2\rceil$ . Among the at least $S$ different magnitudes occurring for the entries of the vector $v$ , there are at least $r$ even numbers or at least $r$ odd numbers. So, upon relabelling the indices, we may assume without loss of generality that the first $r$ entries $v_1,\dots, v_r$ of $v=(v_1,\dots, v_n)\in{\mathbb{R}}^n$ have distinct magnitudes with the same parity and are ordered in decreasing order of magnitudes. Now, for each $i\in [r-1]$ , if $m$ is the magnitude of $v_i$ , then $v_{i+1}$ has magnitude at most $m-2$ . This means that $|v_i|\ge 10^m$ and $|v_{i+1}| \lt 10^{m-1}$ , and therefore $|v_i| \ge 10 |v_{i+1}|$ for every $i\in [r-1]$ .

This implies that for any $\alpha \in{\mathbb{R}}$ , there is at most one assignment for $w_1,\dots, w_r\in \{\pm 1\}$ satisfying $\sum _{i = 1}^r v_iw_i = \alpha$ . Indeed, if there were two distinct such assignments $(w_1,\dots, w_r),\big(w^{\prime}_1,\dots, w^{\prime}_r\big)\in \{\pm 1\}^r$ , then we would have $\sum _{i = 1}^r v_i\big(w_i-w^{\prime}_i\big) = \alpha -\alpha =0$ . So for the minimum index $j\in \{1,\dots, r\}$ with $w_j\ne w^{\prime}_j$ , we would have

\begin{equation*}2|v_j|=\big|v_j\big(w_j-w^{\prime}_j\big)\big|=\left|\sum _{i = j+1}^r v_i\big(w_i-w^{\prime}_i\big)\right|\le \sum _{i = j+1}^r 2|v_i|\le \sum _{i = j+1}^r 2|v_j|/10^{j-i}\lt \frac {2}{9}\cdot |v_j|,\end{equation*}

yielding a contradiction. So for any $\alpha \in{\mathbb{R}}$ , there can be at most one such assignment $(w_1,\dots, w_r)\in \{\pm 1\}^r$ .

Let us now condition on arbitrary outcomes of $w_{r+1},\dots, w_{n}\in \{\pm 1\}$ . Conditional on such fixed outcomes, it suffices to show that, for any $\alpha \in{\mathbb{R}}$ , we have $\sum _{i = 1}^r v_iw_i = \alpha - \sum _{j = r+1}^n v_jw_j$ with probability at most $\left (\frac{2}{3}\right )^{r}$ . Recall that there is at most one assignment for $w_1,\dots, w_r\in \{\pm 1\}$ satisfying this equation. Since $w_1,\dots, w_r$ are independent random variables with

\begin{equation*}{\mathbb {P}}[w_i = 1] \le \frac {2}{3} \quad \text {and} \quad {\mathbb {P}}[w_i = -1] \le \frac {2}{3}\end{equation*}

for every $i\in [r]$ , we obtain

\begin{equation*}{\mathbb {P}}\left [\sum _{i = 1}^r v_iw_i = \alpha - \sum _{j = r+1}^n v_jw_j \, \Bigg | \, w_{r+1},\dots, w_n \right ] \le \left (\frac {2}{3}\right )^r = \left (\frac {2}{3}\right )^{\lceil S/2\rceil }.\end{equation*}

This implies our desired statement.

Proof of Observation 1.3. Suppose $h_1,\dots, h_k$ are hyperplanes forming a skew cover of $\{\pm 1\}^n$ . For $i=1,\dots, k$ , let us write $h_i=\{x\in{\mathbb{R}}^n \mid \langle v_i,x\rangle = \mu _i\}$ . Then for every $i\in [k]$ , all coordinates of the vector $v_i$ are non-zero.

Let $I\subseteq [k]$ be a minimal subset with respect to the property that the hyperplanes $h_i$ for $i\in I$ cover all vertices in $\{\pm 1\}^n$ (and note that $I\ne \emptyset$ ). We claim that these hyperplanes $h_i$ for $i\in I$ form an essential cover of $\{\pm 1\}^n$ . Indeed, conditions (E1) and (E3) in Definition 1.1 are satisfied by the choice of $I$ . Condition (E2) is satisfied because for every index $i\in I$ , all coordinates of $v_i$ are non-zero (so for any $j\in [n]$ , one can take an arbitrary index $i\in I$ in condition (E2)).

Now, taking an arbitrary index $i\in I$ , Lemma 2.4 implies that $n=|\operatorname{supp}(v_i)|\le 2|I|\le 2k$ , so we must have $k\ge n/2$ .

Proof. Apply Lemma 2.5 to the symmetric $\ell \times \ell$ matrix $M:= V V^T$ and the vector $\mu \in{\mathbb{R}}^{\ell }$ . Note that we have $M_{ii} =1$ for all $i\in [\ell ]$ since $||v_i||_2 = 1$ for all $i\in [\ell ]$ . Hence there exists a vector $\varepsilon \in \{\pm 1\}^\ell$ such that

\begin{equation*}\big |(M(\theta \varepsilon ))_i - \mu _i\big |\ge \theta \quad \text {for all } i\in [\ell ].\end{equation*}

Setting $y := \theta V^T \varepsilon \in{\mathbb{R}}^m$ , for every $i\in [\ell ]$ , we obtain

\begin{equation*}\big |\langle v_i, y\rangle - \mu _i\big | =\big |(Vy)_i - \mu _i\big |=\left |(V(\theta V^T \varepsilon ))_i - \mu _i\right |=\left |(VV^T(\theta \varepsilon ))_i - \mu _i\right |=\left |(M(\theta \varepsilon ))_i - \mu _i\right |\ge \theta .\end{equation*}

Furthermore, we have

\begin{align*} ||y||_\infty &= ||\theta V^T\varepsilon ||_\infty = \max _{j\in [m]}\left |\theta \sum _{i = 1}^\ell v_{ij}\varepsilon _i\right | \le \max _{j\in [m]}\theta \sum _{i = 1}^\ell |v_{ij}| = \max _{j\in [m]} \theta ||v_{*j}||_1 \le \frac{1}{3}, \end{align*}

as desired.

Proof of Theorem 1.2. Suppose for contradiction that the hyperplanes $h_1,\dots, h_k$ form an essential cover of the hypercube $\{\pm 1\}^{n}$ of size $k \lt 10^{-2}\cdot n^{2/3}/(\log n)^{2/3}$ . For each $i\in [k]$ , let $h_i=\{x\in{\mathbb{R}}^n \mid \langle v_i,x\rangle = \mu _i\}$ , and let $V\in{\mathbb{R}}^{k\times n}$ be the matrix with rows $v_1,\dots, v_k$ . Then, we can decompose $V$ as in Proposition 3.1. But now by Proposition 3.2, there must be a vertex $w\in \{\pm 1\}^n$ that is not covered by any of the hyperplanes $h_1,\dots, h_k$ . This contradicts condition (E1) in the definition of an essential cover in Definition 1.1.

Proof of Proposition 3.2. Let $[k] = K_1\sqcup K_2\sqcup K_3$ and $[n] = N_1\sqcup N_2$ be partitions satisfying the conditions in Proposition 3.1. Note that these conditions are not affected by rescaling the hyperplane equations $\langle v_i,x\rangle = \mu _i$ describing the hyperplanes $h_i$ for $i\in K_2$ . We may therefore assume that the matrix $V^{\prime}$ in condition (2) in Proposition 3.1 is simply $V^{\prime}=V[K_2\times N_1]$ after rescaling the equations $\langle v_i,x\rangle = \mu _i$ for $i\in K_2$ appropriately (note that this precisely corresponds to rescaling the rows of $V$ with indices in $K_2$ ). Specifically, this means that we have $||v_i|_{N_1}||_2 = 1$ for each $i\in K_2$ , and furthermore, for each $j\in N_1$ , the $j$ -th column $v_{*j}$ of $V$ satisfies $||v_{*j}|_{K_2}||_1\le (60\log n)^{-1/2}$ .

Next, we claim that $K_1\ne [k]$ . Indeed, condition (E2) in Definition 1.1 means that the matrix $V$ cannot have any column with all entries being zero. On the other hand, by condition (1) in Proposition 3.1 the submatrix $V[K_1\times N_1]$ of $V$ is the zero matrix. Therefore, if we had $K_1= [k]$ , then for every $j\in N_1$ the $j$ -th column of $V$ would be all-zero. This would be a contradiction, given that $N_1\ne \emptyset$ . Thus, we indeed have $K_1\ne [k]$ .

Now, we can fix the entries $w_j$ for $j\in N_2$ of our desired vertex $w\in \{\pm 1\}^n$ using the following lemma.

Proof. By condition (E3) in Definition 1.1 applied to some element of $[k]\setminus K_1$ , there exists a vertex $x\in \{\pm 1\}^n$ such that $\langle v_i, x\rangle \ne \mu _i$ for all $i\in K_1$ . We set $\tilde{w} := x|_{N_2}$ . By condition (1) in Proposition 3.1, for every $i\in K_1$ , the restriction $v_i|_{N_1}$ is the all-zero vector. Therefore, for every $w\in \{\pm 1\}^n$ with $w|_{N_2} = \tilde{w}$ , we have

\begin{equation*}\langle v_i, w\rangle = \langle v_i|_{N_2}, \tilde {w}\rangle = \langle v_i|_{N_2}, x|_{N_2}\rangle = \langle v_i, x\rangle \ne \mu _i\end{equation*}

for all $i\in K_1$ , as desired.

Let $\tilde{w}\in \{\pm 1\}^{N_2}$ be as in Lemma 4.1, and fix $w_j = \tilde{w}_j$ for all $j\in N_2$ . Next, we define a probability distribution for the entries $w_j$ for $j\in N_1$ . To do so, we apply Corollary 2.6 to the matrix, $V[K_2\times N_1]$ with $\theta = (6\log n)^{1/2}$ and $\mu ^{\prime}\in{\mathbb{R}}^{K_2}$ defined by $\mu ^{\prime}_i = \mu _i - \langle v_i|_{N_2}, \tilde{w}\rangle$ for all $j\in K_2$ . We have $\theta ||v_{*j}|_{K_2}||_1\le (6\log n)^{1/2}\cdot (60\log n)^{-1/2}\le 1/3$ for all $j\in N_1$ , as well as $||v_i|_{N_1}||_2 = 1$ for all $i\in K_2$ , so the conditions of Corollary 2.6 are satisfied for the matrix $V[K_2\times N_1]$ . So we obtain $y\in{\mathbb{R}}^{N_1}$ such that $||y||_\infty \le 1/3$ and $\left |\langle v_i|_{N_1}, y\rangle - \mu^{\prime}_i \right | \ge \theta$ for all $i\in K_2$ . Then for every $j\in N_1$ , let us take a random variable $w_j\in \{\pm 1\}$ with distribution

(1) \begin{equation} w_j = \begin{cases} 1 & \text{with probability } (1+y_j)/2 \\ -1 & \text{with probability } (1-y_j)/2, \end{cases} \end{equation}

such that the random variables $w_j$ are independent for all $j\in N_1$ . Note that then we have ${\mathbb{E}}[w_j] = y_j$ for each $j\in N_1$ .

Taking the entries of $w$ to be the random variables $w_j$ for $j\in N_1$ together with the fixed values $w_j=\tilde{w}_j$ for $j\in N_2$ defined above, we have now defined a random vertex $w\in \{\pm 1\}^n$ . Our goal is to show that with positive probability $w\in \{\pm 1\}^n$ satisfies $\langle v_i, w\rangle \ne \mu _i$ for all $i\in [k]$ . By the choice of $\tilde{w}$ in Lemma 4.1 we always have $\langle v_i, w\rangle \ne \mu _i$ for all $i\in K_1$ . Next, we show that for $i\in K_2$ we are unlikely to have $ \langle w, v_i\rangle = \mu _i$ .

Claim 4.2. For every $i\in K_2$ , we have

\begin{equation*} {\mathbb {P}} \Big [\langle v_i,w\rangle = \mu _i\Big ] \le \frac {1}{2n}.\end{equation*}

Proof. Fix $i\in K_2$ . By our definition of $\mu ^{\prime}_i=\mu _i - \langle v_i|_{N_2}, \tilde{w}\rangle =\mu _i - \langle v_i|_{N_2}, w|_{N_2}\rangle$ , we have $\langle v_i,w\rangle = \mu _i$ if and only if $\langle v_i|_{N_1},w|_{N_1}\rangle = \mu^{\prime}_i$ . So it suffices to show that

\begin{equation*}{\mathbb {P}} \Big [\langle v_i|_{N_1}, w|_{N_1}\rangle = \mu^{\prime}_i\Big ] \le \frac {1}{2n}.\end{equation*}

Since ${\mathbb{E}}[w_j] = y_j$ for all $j\in N_1$ , by linearity of expectation, we have ${\mathbb{E}}[\langle v_i|_{N_1},w|_{N_1}\rangle ] = \langle v_i|_{N_1},y\rangle$ . In addition, recall that we have $\left |\langle v_i|_{N_1},y\rangle - \mu^{\prime}_i\right |\ge \theta$ , so we obtain

\begin{align*}{\mathbb{P}}\Big [\langle v_i|_{N_1},w|_{N_1}\rangle = \mu^{\prime}_i\Big ] &\le{\mathbb{P}}\Big [\big |\langle v_i|_{N_1},w|_{N_1}\rangle - \langle v_i|_{N_1},y\rangle \big |\ge \theta \Big ]\\[4pt]& ={\mathbb{P}}\Big [\big |\langle v_i|_{N_1},w|_{N_1}\rangle -{\mathbb{E}}[\langle v_i|_{N_1},w|_{N_1}\rangle ]\big |\ge \theta \Big ]. \end{align*}

Now, we can apply Hoeffding’s inequality (Lemma 2.7) to the random variables $v_{ij}w_j$ for $j\in N_1$ , whose sum is $\sum _{j\in N_1}v_{ij}w_j=\langle v_i|_{N_1},w|_{N_1}\rangle$ . Note that the random variables $v_{ij}w_j$ are independent and bounded by $-|v_{ij}|\le v_{ij}w_j\le |v_{ij}|$ for each $j\in N_1$ . Since we have $||v_i|_{N_1}||_2 = 1$ , we obtain

\begin{align*}{\mathbb{P}}\Big [\big |\langle v_i|_{N_1},w|_{N_1}\rangle -{\mathbb{E}}[\langle v_i|_{N_1},w|_{N_1}\rangle ]\big |\ge \theta \Big ] & \le 2\cdot \exp \left ({-}\frac{2\theta ^2}{\sum _{j\in N_1} (2v_{ij})^2}\right )\\ & = 2\cdot \exp \left ({-}\frac{2\theta ^2}{4 ||v_i|_{N_1}||_2^2}\right )\\ &=2\cdot \exp \left ({-}\frac{\theta ^2}{2}\right ). \end{align*}

Substituting in our choice of $\theta = (6\log n)^{1/2}$ , we can deduce (recalling $n\ge 2$ )

\begin{equation*}{\mathbb {P}} \Big [\langle v_i|_{N_1},w|_{N_1}\rangle = \mu^{\prime}_i\Big ] \le 2\exp ({-}3\log n) = \frac {2}{n^3} \le \frac {1}{2n}.\end{equation*}

On the other hand, by condition (3) in Proposition 3.1, for every $i\in K_3$ , the vector $v_i|_{N_1}$ has at least $\lceil 10\log n\rceil$ magnitudes. Thus, by Lemma 2.3 applied to $p\in [1/3,2/3]^{N_1}$ given by $p_j=(1+y_j)/2$ for all $j\in N_1$ , we have

\begin{equation*}{\mathbb {P}}\Big [\langle v_i,w\rangle = \mu _i \Big ] ={\mathbb {P}}\Big [ \langle v_i|_{N_1},w|_{N_1}\rangle = \mu _i -\langle v_i|_{N_2},\tilde {w}\rangle \Big ]\le \left (\frac {2}{3}\right )^{\lceil 10\log n /2\rceil }\le \left (\frac {2}{3}\right )^{5\log n}\le \frac {1}{n^2}\le \frac {1}{2n}\end{equation*}

for every $i\in K_3$ . Together with Claim 4.2, we can take a union bound over all $i\in K_2\cup K_3$ and obtain

\begin{equation*}{\mathbb {P}}\Big [\langle v_i,w\rangle = \mu _i \text { for some }i\in K_2\cup K_3\Big ]\le \sum _{i\in K_2\cup K_3}{\mathbb {P}}\Big [ \langle v_i,w\rangle = \mu _i \Big ]\le k\cdot \frac {1}{2n}\le n\cdot \frac {1}{2n} = \frac {1}{2},\end{equation*}

recalling that $k\le n$ .

Thus, with probability at least $1/2$ , our random vertex $w\in \{\pm 1\}^n$ satisfies $\langle v_i, w\rangle \ne \mu _i$ for all $i\in K_2\cup K_3$ . Recalling that we always have $\langle v_i, w\rangle \ne \mu _i$ for all $i\in K_1$ , this means that with probability at least $1/2$ , we have $\langle v_i, w\rangle \ne \mu _i$ for all $i\in [k]$ . Hence, there exists a vertex in $w\in \{\pm 1\}^n$ such that $\langle v_i, w\rangle \ne \mu _i$ for all $i\in [k]$ .

Proof of Proposition 3.1. We decompose the matrix $V$ using the following algorithm that starts with all the column indices in $N_1$ . At any iteration of the algorithm, we have a partition $[n] = N_1\sqcup N_2$ of the column indices, and furthermore, the row indices $i\in [k]$ are partitioned into three types: being in $K_1$ , active, and inactive (defined later). Throughout the algorithm, we move certain columns from $N_1$ to $N_2$ . When the algorithm terminates, the desired partitions of the row and column indices of the matrix will be formed by taking the sets $K_1$ , $N_1$ , and $N_2$ at the end of the algorithm, as well as taking $K_2$ to be the active row indices and $K_3$ to be the inactive row indices at the end of the algorithm.

1. 1. Initialise $N_1 = [n],\, N_2= \emptyset$ and $K_1= \emptyset$ .

2. 2. For each $i\in [k]\setminus K_1$ such that $v_i|_{N_1}$ is the all-zero vector, we move $i$ into $K_1$ .

3. 3. For each $i\in [k]\setminus K_1$ , we say that $i$ is inactive if the vector $v_i|_{N_1}$ has at least $\lceil 10\log n\rceil$ magnitudes; otherwise, we say that $i$ is active.

4. 4. For each active $i\in [k]\setminus K_1$ and each $j\in N_1$ , we assign a weight $w_{ij}$ to the entry $v_{ij}$ of $V$ as follows: if $v_{ij}=0$ , define $w_{ij}=0$ . If $v_{ij}\ne 0$ , let $m$ be the magnitude of $v_{ij}$ , and let $N_m(i)$ be the number of entries of $v_i|_{N_1}$ with magnitude $m$ , and define $w_{ij}=10/\sqrt{N_m(i)}$ .

5. 5. For every $j\in N_1$ , calculate the total weight $\sum _i w_{ij}$ in column $j$ , where the sum is taken over all active $i\in [k]\setminus K_1$ . If there exists some $j\in N_1$ where this total weight is larger than $(60\log n)^{-1/2}$ , then move this index $j$ from $N_1$ to $N_2$ and remove all weights in column $j$ (if there exist multiple such $j$ , choose one arbitrarily), and go to back to Step 2. If there is no such index $j\in N_1$ , go to Step 6.

6. 6. Terminate and output the current sets $N_1, N_2, K_1$ , output the current set of active row indices as $K_2$ , and output the current set of inactive row indices as $K_3$ .

It is clear that this algorithm must eventually terminate since in every iteration, a column index is moved from $N_1$ to $N_2$ (so the set $N_1$ is getting strictly smaller with every iteration). It is also clear that the algorithm produces a partition $[k] = K_1\sqcup K_2\sqcup K_3$ of the row indices of $V$ and a partition $[n] = N_1\sqcup N_2$ of the column indices. Furthermore, it is not hard to see that these partitions satisfy conditions (1) and (3) in Proposition 3.1. Indeed, condition (1) is satisfied by the rule of moving row indices into $K_1$ in Step 2 of the algorithm, and condition (3) is satisfied by the definition of inactive rows in Step 3.

To show condition (2) in Proposition 3.1, consider the $|K_2|\times |N_1|$ matrix $V^{\prime}$ obtained from $V[K_2\times N_1]$ by normalising every row to have $\ell _2$ -norm equal to $1$ (note that by the condition in Step 2, all the rows of $V[K_2\times N_1]$ are non-zero). Let us write $v^{\prime}_i=(1/||v_i|_{N_1}||_2)v_i|_{N_1}$ for $i\in K_2$ for the rows of $V^{\prime}$ . Now, for every entry $v_{ij}\ne 0$ of $V[K_2\times N_1]$ with some magnitude $m$ , we have $10^{m}\le |v_{ij}| \lt 10^{m+1}$ , and for each $i\in K_2$ , there are $N_m(i)$ such entries in $v_i|_{N_1}$ . Thus, $||v_i|_{N_1}||_2\ge \sqrt{N_m(i)}\cdot 10^{m}$ for every magnitude $m$ appearing among the entries of $v_i|_{N_1}$ , and we can conclude that

\begin{equation*}|v^{\prime}_{ij}|=\frac {|v_{ij}|}{||v_i|_{N_1}||_2}\lt \frac {10^{m+1}}{\sqrt {N_m(i)}\cdot 10^{m}} = \frac {10}{\sqrt {N_m(i)}} = w_{ij}\end{equation*}

for every entry $v_{ij}\ne 0$ of $V[K_2\times N_1]$ with magnitude $m$ . This shows that $|v^{\prime}_{ij}| \le w_{ij}$ for all $i\in K_2$ and $j\in N_1$ (note that in the case $v_{ij}= 0$ , we trivially have $|v^{\prime}_{ij}|=0 = w_{ij}$ ).

Now, to check condition (2), observe that for every $j\in N_1$ , we have $\sum _{i\in K_2} w_{ij}\le (60\log n)^{-1/2}$ since otherwise the algorithm would not have terminated. Consequently, for every $j\in N_1$ , we have $\sum _{i\in K_2} |v^{\prime}_{ij}|\le \sum _{i\in K_2} w_{ij}\le (60\log n)^{-1/2}$ , meaning that the $\ell _1$ -norm of every column in $V^{\prime}$ is at most $(60\log n)^{-1/2}$ .

It remains to show $N_1\ne \emptyset$ . Recall that at the start, we have $N_1=[n]$ , and in every iteration of the algorithm, we move one index from $N_1$ into $N_2$ . So we need to show that the number of column indices moved into $N_2$ throughout the algorithm is less than $n$ . At every step, we consider the total weight in the matrix. Whenever we move a column index from $N_1$ into $N_2$ , this total weight decreases by at least $(60\log n)^{-1/2}$ (by the condition on the column weight in Step 5 of the algorithm).

However, note after moving a column from $N_1$ to $N_2$ , when reassigning the weights in Step 3 in the next iteration, some of the weights in the remaining columns with indices in $N_1$ may increase (indeed, the numbers $N_m(i)$ may decrease by removing a column from $N_1$ ). Furthermore, new row indices may become active as the set $N_1$ gets smaller throughout the algorithm (but note that once a row index becomes active, it cannot become inactive anymore afterwards).

For every row index $i\in [k]$ that becomes active at some point during the algorithm, and every magnitude occurring among the entries of $v_i|_{N_1}$ at the moment when the index $i$ first becomes active, let $N^*_m(i)$ denote the number of entries of $v_i|_{N_1}$ with magnitude $m$ when the row index $i$ first becomes active. At that iteration of the algorithm, each of these $N^*_m(i)$ entries is assigned weight $10/\sqrt{N^*_m(i)}$ . When a column index of some entry of $v_i|_{N_1}$ with magnitude $m$ gets moved into $N_2$ later in the algorithm, the quantity $N_m(i)$ decreases, and so the weights of the remaining entries of $v_i|_{N_1}$ with magnitude $m$ increase. More precisely, when this happens for the $t$ -th time (for $t\in \{1,\dots, N^*_m(i)-1\}$ ), the weight of the $N^*_m(i)-t$ remaining entries of $v_i|_{N_1}$ with magnitude $m$ is increased from $10/\sqrt{N^*_m(i)-t+1}$ to $10/\sqrt{N^*_m(i)-t}$ . Thus, the total weight that is added to the entries with magnitude $m$ in row $i$ throughout the algorithm (both when row $i$ first becomes active and as the weights get re-assigned) is at most

\begin{align*} & N^*_m(i)\cdot \frac{10}{\sqrt{N^*_m(i)}} + \sum _{t = 1}^{N^*_m(i)-1} \left (N^*_m(i) - t\right ) \left (\frac{10}{\sqrt{N^*_m(i) - t}} - \frac{10}{\sqrt{N^*_m(i) - t + 1}}\right )\\ &= 10\sqrt{N^*_m(i)} + 10\sum _{t = 1}^{N^*_m(i) - 1} t \left (\frac{1}{\sqrt{t}} - \frac{1}{\sqrt{t+1}}\right ) = 10\sqrt{N^*_m(i)} + 10\sum _{t = 1}^{N^*_m(i) - 1} t \cdot \frac{\sqrt{t+1} - \sqrt{t}}{\sqrt{t(t+1)}} \\ &\le 10\sqrt{N^*_m(i)} + 10\sum _{t = 1}^{N^*_m(i) - 1} \left (\sqrt{t+1} - \sqrt{t}\right ) \le 10\sqrt{N^*_m(i)} + 10\sqrt{N^*_m(i)} = 20\sqrt{N^*_m(i)} \end{align*}

for any row index $i$ becoming active at some point during the algorithm and any $m$ appearing as magnitude among the entries of $v_i|_{N_1}$ at the moment when the index $i$ first becomes active.

For notational convenience, let $S = \lceil 10\log n\rceil -1$ . Recall that when the row index $i$ becomes active, there are strictly less than $\lceil 10\log n\rceil$ (i.e., at most $S$ ) magnitudes appearing among the entries of $v_i|_{N_1}$ . For these at most $S$ different magnitudes $m$ , the numbers $N^*_m(i)$ defined above (counting the entries of $v_i|_{N_1}$ of magnitude $m$ when the row index $i$ first becomes active) satisfy

\begin{equation*}\sum _m N^*_m(i) = |\operatorname {supp}(v_i|_{N_1})|\le |\operatorname {supp}(v_i)|\le 2k,\end{equation*}

where the last inequality holds by Lemma 2.4. Hence

\begin{equation*}\sum _m 20 \sqrt {N_m(i)}= 20\sum _m \sqrt {N_m(i)}\le 20 \cdot \sqrt {S} \cdot \sqrt {\sum _m N^*_m(i)}\le 20 \cdot \sqrt {S} \cdot \sqrt {2k} \le 30 \sqrt {kS}\end{equation*}

by the Cauchy–Schwarz inequality, so for every row, the total weight added to the entries throughout the algorithm is at most $30 \sqrt{kS}$ . Thus, the total weight increase for the entire $k\times n$ matrix $V$ throughout the algorithm is at most

\begin{equation*}k\cdot 30 \sqrt {kS}=30k^{3/2}\sqrt {S}\le 30k^{3/2}\cdot (10\log n)^{1/2}.\end{equation*}

Recall that whenever we move a column index from $N_1$ into $N_2$ , the weight in the matrix $V$ decreases by at least $(60\log n)^{-1/2}$ . Therefore, at most

\begin{equation*}\frac {30k^{3/2}\cdot (10\log n)^{1/2}}{(60\log n)^{-1/2}}\le 750k^{3/2}\cdot \log n\end{equation*}

column indices can be moved from $N_1$ into $N_2$ . By our assumption $k \le 10^{-2}\cdot n^{2/3}/(\log n)^{2/3}$ , this number of column indices moved from $N_1$ into $N_2$ is at most

\begin{equation*}750k^{3/2}\cdot \log n\le 750\cdot 10^{-3}\cdot \frac {n}{\log n}\cdot \log n \lt n.\end{equation*}

Thus, we have $N_1\ne \emptyset$ at the end of the algorithm, as desired.