## ON THE STRUCTURE OF BAD SCIENCE MATRICES

ALEX ALBORS, HISHAM BHATTI, LUKSHYA GANJOO, RAYMOND GUO, DMITRIY KUNISKY, ROHAN MUKHERJEE, ALICIA STEPIN, AND TONY ZENG

Abstract. The bad science matrix problem consists in finding, among all matrices A ∈ R n × n with rows having unit ℓ 2 norm, one that maximizes

$$\beta ( A ) = \frac { 1 } { 2 ^ { n } } \sum _ { x \in \{ - 1, 1 \} ^ { n } } \| A x \| _ { \infty }.$$

Our main contribution is an explicit construction of an n × n matrix A showing that β A ( ) ≥ √ log 2 ( n +1) which is only 18% smaller than the asymptotic rate. We prove that the every entry of any optimal matrix is a square root of a rational number, and we find provably optimal matrices for n ≤ 4.

## 1. Introduction

The bad science matrix problem [4] is concerned with understanding, for matrices A ∈ R n × n whose rows are normalized to have ℓ 2 -length 1, the size of the quantity

$$\beta ( A ) = \frac { 1 } { 2 ^ { n } } \sum _ { x \in \{ - 1, 1 \} ^ { n } } \| A x \| _ { \infty }.$$

While originally only defined for square matrices in [4], its definition naturally makes sense for A ∈ R m n × where one measures the ∞ -norm of the 2 n vertices of the cube which are mapped to 2 n vertices in R m . We note that the problem can also be framed probabilistically, with the objective function becoming

$$\beta ( A ) = \mathbb { E } \, \| A X \| _ { \infty }$$

where X ∈ {-1 1 , } n is an n -dimensional Rademacher random vector (i.e., with entries drawn independently and uniformly at random from {± } 1 ). We will use this notation throughout when we mention probabilistic interpretations of various quantities. The problem is interesting for a variety of different reasons. We list four.

1.1. Bad Science. The name is derived from the following thought experiment: we are given a sequence of coin tosses x ∈ {-1 1 , } n and are trying to understand whether they come from a fair coin or not. One natural way of testing is to fix a vector a 1 ∈ R n , normalized to ∥ a 1 ∥ 2 = 1, and consider the size of the inner product ⟨ a , x 1 ⟩ : Hoeffding's inequality guarantees that if, the coin is fair, then the inner product should be small. Similar reasoning suggests that we could take two vectors ∥ a 1 ∥ 2 = 1 = ∥ a 2 ∥ 2 and consider both inner products: they should both be small and if one of them is large, that is probably indicative of the coin not being fair. We may also think of this case as two statistical tests being run. Note that, since we do not make any assumptions about a 1 and a 2 , these tests need not

be independent. The question now is whether it is possible to construct n vectors a , . . . , a 1 n corresponding to n fair statistical tests such that, for a typical sequence of random coin tosses x ∈ {-1 1 , } n , at least one of the statistical tests will typically end up with a large result even though the coin is fair. This motivates the name of 'bad science matrix problem': the bad scientist is running a battery of (fair) tests to find an abnormal result even though the coins are not abnormal.

- 1.2. Rotating the Cube. Since the rows are normalized to have length 1, we deduce that the Frobenius norm of the matrix is

$$\| A \| _ { F } ^ { 2 } = \sum _ { i, j = 1 } ^ { n } A _ { i j } ^ { 2 } = n.$$

The Frobenius norm is simultaneously the sum of the squares of the singular values of the matrix and therefore

$$n = \sum _ { i = 1 } ^ { n } \sigma _ { i } ( A ) ^ { 2 }.$$

Geometrically, this means that the matrix cannot be too expansive. A very simple example of matrices with this property is the identity matrix Id n × n or, more generally, orthogonal matrices Q ∈ R n × n . Given such a matrix A , we could now ask where it ends up sending the unit cube {-1 1 , } n

$$A \left \{ - 1, 1 \right \} ^ { n } = \left \{ \sum _ { i = 1 } ^ { n } \varepsilon _ { i } c _ { i } \, \colon \varepsilon _ { i } \in \left \{ - 1, 1 \right \} \right \},$$

where c 1 , . . . , c n ∈ R n are the columns of the matrix A . Using a , . . . , a 1 n ∈ R n to denote the rows of the matrix A , we then have

$$\frac { 1 } { 2 ^ { n } } \sum _ { x \in \{ - 1, 1 \} ^ { n } } \| A x \| _ { 2 } ^ { 2 } = \frac { 1 } { 2 ^ { n } } \sum _ { x \in \{ - 1, 1 \} ^ { n } } \sum _ { i = 1 } ^ { n } \langle a _ { i }, x \rangle ^ { 2 } = \sum _ { i = 1 } ^ { n } \frac { 1 } { 2 ^ { n } } \sum _ { x \in \{ - 1, 1 \} ^ { n } } \langle a _ { i }, x \rangle ^ { 2 } \,.$$

For any arbitrary vector y ∈ R n , we have

̸

$$& \text{For any arbitrary vector } y \in \mathbb { R } ^ { n }, \, \text{we have} \\ & \frac { 1 } { 2 ^ { n } } \sum _ { x \in \{ - 1, 1 \} ^ { n } } \langle y, x \} ^ { 2 } = \mathbb { E } [ \langle y, x \} ^ { 2 } ] = \mathbb { E } \left [ \left ( \sum _ { i = 1 } ^ { n } y _ { i } x _ { i } \right ) ^ { 2 } \right ] = \mathbb { E } \left [ \sum _ { i, j = 1 } ^ { n } y _ { i } y _ { j } x _ { i } x _ { j } \right ] \\ & \quad = \sum _ { i, j = 1 } ^ { n } y _ { i } y _ { j } \mathbb { E } [ x _ { i } x _ { j } ] = \sum _ { i = 1 } ^ { n } y _ { i } ^ { 2 } \underline { \mathbb { E } [ x _ { i } ^ { 2 } ] } + \sum _ { i \neq j } y _ { i } y _ { j } \underline { \mathbb { E } [ x _ { i } x _ { j } ] } _ { 0 } \\ & \quad = \sum _ { i = 1 } ^ { n } y _ { i } ^ { 2 } = \| y \| ^ { 2 } \\ & \text{and therefore} \quad.$$

and therefore

$$\frac { 1 } { 2 ^ { n } } \sum _ { x \in \{ 1, 1 \} ^ { n } } \| A x \| _ { 2 } ^ { 2 } = \| A \| _ { F } ^ { 2 } = n.$$

One way of interpreting the results is that the normalization on the rows shows that A rotates the vertices of the cube to points whose average ℓ 2 -norm remains fixed. The question is now: can these points have the property that the typical largest entry of such a vertex ends up being significantly larger than the average?

- 1.3. The Koml´ os Conjecture. Another motivation is given by the Koml´s cono jecture. It is known (see Banaszczyk [1]) that there exists a constant C &gt; 0 such that for all matrices A ∈ R n × n whose columns are of size ≤ 1 in ℓ 2 , there always exists a sign vector ε ∈ {-1 1 , } n such that

$$\| A \varepsilon \| _ { \ell ^ { \infty } } \leq C \sqrt { \log n }.$$

The open question is whether the √ log n term is necessary or whether the result remains true with a universal constant C . It is known that if this were true, the constant C cannot be too small: Kunisky [3] has proven that for each η &gt; 0 there exists a matrix A ∈ R n × n so that

$$\forall \, \varepsilon \in \{ - 1, 1 \} ^ {$$

The bad science matrix problem is somewhat dual: one can think of the Koml´s o problem as the problems of balancing the columns of a matrix to ensure that the final sum is in a small ℓ ∞ -box centered at the origin. Our problem is less a vector balancing problem and more of a 'functional-balancing' question: we have n functionals ⟨ a , i ·⟩ whose operator norm is 1 and ask whether they can be arranged so that a typical random ± 1 is outside a large ℓ ∞ -box. To further underscore the similarity, an idea of Kunisky [3] shown to be useful in the setting of the Koml´s o problem, will also be useful in the setting of bad science matrices.

- 1.4. Extremizers. One final possible motivation why this functional may be of intrinsic interest are the results: extremal matrices appear to have an interesting structure. We illustrate this with an example taken from [4]: the currently best known example for n = 5 is the matrix

$$\begin{array} {$$

This shows that

$$\max _ { A \in \mathbb { R } ^ { 5 \times 5 } } \$$

Moreover, the way this matrix acts on the 2 5 = 32 vertices of the hypercube {-1 1 , } 5 is interesting: 8 of the 32 vertices are sent to vectors with maximal entry 2 (in absolute value) and the remaining 24 vertices are sent to vertices with maximal coordinate √ 3 (in absolute value). We do not know whether this matrix is indeed optimal. Indeed, even for relatively small dimensions, like n = 3 or n = 4, rigorously proving that a certain candidate matrix is indeed extremal appears to be a highly nontrivial problem.

- 1.5. Known Results. Relatively little is known for the bad science matrix problem. Steinerberger proved that, as n →∞ , the 'worst' matrix scales as

$$\beta ( A ) = ( 1 + o ( 1 ) ) \cdot \sqrt { 2$$

The upper bound follows relatively quickly from Hoeffding's inequality and the union bound. As for the lower bound, it is shown that a random matrix with

entries ± 1 / √ n very nearly saturates the upper bound. The proof is completely non-constructive and does not yield a single example of a truly 'bad' bad science matrix. Moreover, some basic numerical experiments suggest that the extremal matrices (at least in low dimensions, say, n ≤ 8) are quite different from random ± 1 / √ n matrices and have interesting behavior: in particular, their entries were noted to be exclusively algebraic numbers like √ 3 or 3 / √ 29. We also note that the bad science matrix problem appears to admit many extremal matrices: there is an obvious symmetry in permuting rows and columns but it appears that there is a great degree of non-uniqueness. Finally, nothing is known about the more general bad science matrix problem for rectangular matrices.

## 2. Main Results

2.1. Structure Theorem and Consequences. Our first main result is a theorem about the structure of extremal matrices. The result proves a strong one-to-one correspondence between the i th row of an extremal matrix and the vertices of the hypercube {-1 1 , } n that are being mapped by the matrix to a point whose coordinates attain their maximum absolute value in the i th coordinate.

Theorem 1 (Structure Theorem) . Let A = [ a 1 · · · a m ] ⊤ be an m × n matrix maximizing the value of β A ( ) among all such matrices with rows normalized in ℓ 2 . Introducing the set W i of vertices of the hypercube that are being mapped to a vector whose largest entry is in the i th coordinate,

$$W _ { i } = \left \{ x \in \left \{ - 1, 1 \$$

then the i th row of A is given by

$$a _ { i } = \frac { \sum _ { x \in W _ { i } } x } { \| \sum _ { x \in W _ { i } } x \| }.$$

This structure theorem has a number of immediate consequences. The first consequence is something that was already observed (without proof) in [4]: entries of extremal entries appear to be either rational numbers or square roots of rational number (indeed, this was essentially in the construction of extremal candidates in [4]). This is indeed the case and follows easily from the Structure Theorem.

Corollary 1. The entries of an optimal bad science matrix are square roots of rational numbers.

We observe that Theorem 1 gives us something much stronger; it shows that extremal entries are really rescaled vectors which themselves are merely the sum of all vertices of a subset of the hypercube. We will use this structural restriction to solve the bad science matrix problem in dimensions n ≤ 4 .

Corollary 2 (Cases n ≤ 4) . If A ∈ R n × n has normalized rows, then

$$i$$

$$\mathbb { E } \| A X \| _ { \infty } \leq \begin{cases} \sqrt { 2 } & \text{when $n$ } n = 2, \\ ( \sqrt { 2 } + \sqrt { 3 } ) / 2 & \text{when $n$ } n = 3, \\ \sqrt { 3 } & \text{when $n$ } n = 4. \end{cases}$$

$$\frac { 1 } { \sqrt { 2 } } \begin{bmatrix} 1 & 1 \\ 1 & - 1 \end{bmatrix}, \quad \begin{bmatrix} \frac { 1 } { \sqrt { 3 } } & \frac { 1 } { \sqrt { 3 } } & \frac { 1 } { \sqrt { 3 } } \\ - \frac { 1 } { \sqrt { 2 } } & 0 & \frac { 1 } { \sqrt { 2 } } \end{bmatrix}, \quad a n d \quad \frac { 1 } { \sqrt { 3 } } \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & - 1 & - 1 & 0 \\ 1 & - 1 & 1 & 0 \\ 1 & 1 & - 1 & 0 \end{bmatrix}.$$

Our proof of Corollary 2 makes extensive use of the computer: the structure theorem can be used to deduce that extremal matrices have to be of a very specific form. One can then, for small values of n , explicitly analyze matrices of that size. Thus, in some sense, our proof of Corollary 2 is based on explicit enumeration. However, this scales rather badly in n and even the case n = 5 appears to be firmly out of reach. It is rather remarkable that we do not currently have a simple way of establishing extremality for small n . We conclude with a very simple observation.

## Corollary 3. The number of extremal n × n matrices is at most 2 n · 2 n .

This can be seen very easily: the number of subsets of {-1 1 , } n is ≤ 2 2 n which shows that there are at most this many possibilities for each row. There are n rows bmatrixbmatrixand the inequality follows. Since there is always at least one extremal matrix (by compactness), permutation of rows and columns shows that the number of extremal matrices is at least n ! and probably much larger. It could be interesting if this number could be further narrowed down but this appears to be a difficult problem.

- 2.2. Construction 1: Lifting Construction. One natural question is whether it is possible to explicitly construct examples of matrices A for which β A ( ) is large. In what follows, we present a number of different approaches to this question. The first observation is that from one good example, one can obtain larger good examples: this is somewhat similar to Sylvester's construction of Hadamard matrices and uses a classic lifting trick.

Theorem 2 (Lifting Theorem) . For any A ∈ R n × n with rows normalized to length

1, the matrix

$$B = \frac { 1 } { \sqrt { \beta ( A ) ^ { 2 } + 1 } } \left [ \begin{array} { c c } \beta ( A ) \cdot A & \text{Id} _ { n \times n } \\ \beta ( A ) \cdot A & - \text{Id} _ { n \times n } \end{array} \right ] \ s a t i s f i e s \ \beta ( B ) = \sqrt { \beta ( A ) ^ { 2 } + 1 }.$$

In particular, starting with the optimal 2 × 2 matrix A 2 and applying Theorem 2 repeatedly, we arrive at an explicit infinite family of matrices ( A 2 k × 2 k ) ∞ k =1 .

## Corollary 4. We have

$$\beta ( A _ { 2 ^ { k } \times 2 ^ { k } } ) = \sqrt { k + 1 } = \sqrt { \log _ { 2 } ( n ) + 1 }.$$

We note that, in particular,

$$\beta ( A _ { 2 \times 2 } ) = \sqrt { 2 }, \quad \beta ( A _ { 4 \times 4 } ) = \sqrt { 3 }, \quad \text{and} \quad \beta ( A _ { 8 \times 8 } ) = 2$$

which matches the currently best known constructions in these dimensions (see [4]). Moreover, by Corollary 2 above, we know that the 2 × 2 and 4 × 4 constructions are

optimal. It stands to reason that the so arising 8 × 8 matrix is also optimal but this remains open. Since √ 2 log n/ √ log 2 n = √ 2 log 2 ≈ 1 177, this construction is a . factor of approximately 1.177 away from optimal. The family of matrices matches a construction given by Steinerberger [4] which is itself based on a construction used by Kunisky [3] for the Koml´s problem. o We note that the construction is limited to n × n matrices where n = 2 k is a power of 2. The next two constructions do not suffer from this drawback.

- 2.3. Construction 2: Unsatisfiable Trees. A more general construction can be given using highly balanced binary trees. We quickly recall their definition.

Definition 1 (Highly balanced binary trees) . For a fixed integer n ≥ 1, fill up a binary tree with vertices from left to right until one has n leaves, and finally add an edge that points into the root.

We label the edges of such a highly balanced binary tree in the following way: edges that point left have label -1, edges that point right have label 1, and the edge that points to the root has label 1. From here, for a leaf v , walk along the unique path from the root to v . Then the edge labels of this path becomes a row of the matrix this method generates, where if the length of the path is less than n , we make the rest of the entries 0. The case n = 4 is illustrated in Fig. 1. One of our main results is a precise analysis of this construction: as it turns out, the construction performs exactly as well as the Hadamard-style tensor construction when n is a power of 2.









Figure 1. An unsatisfiable tree and the corresponding matrix.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00933v2-figure-44b96452-f2e6-4d10-b13e-fdab0d611575.jpg)

Theorem 3 (Unsatisfiability Theorem) . Let A ∈ R n × n be the matrix whose rows correspond to the n prefixes in the binary tree described above. This construction yields

$$\beta ( A ) = \left ( 2 \sqrt { \lfloor \log _ { 2 } ( n ) + 1 \rfloor } - \sqrt { \lfloor \log _ { 2 } n \rfloor + 2 } \right ) \\ + \frac { n } { 2 ^ { \lfloor \log _ { 2 } n \rfloor } } \left ( \sqrt { \lfloor \log _ { 2 } n \rfloor + 2 } - \sqrt { \lfloor \log _ { 2 } n \rfloor + 1 } \right )$$

When n = 2 k is itself a power of 2, the matrices derived from this method satisfy β A ( 2 k × 2 k ) = √ k +1 which matches Corollary 4. However, the construction is more versatile and gives good examples of n × n matrices where n is not a power of 2.

2.4. Wide Matrices. So far, our focus has been on n × n matrices, however, there is no particular reason for doing so. The 1 × n case can be quickly resolved by Jensen's or Khintchine's inequality [2], and we state it as a useful lemma.

Lemma 4 (Contraction Lemma) . For any vector a ∈ R n , we have

$$\mathbb { E } | \langle a, X \rangle | = \frac { 1 } { 2 ^ { n } } \sum _ { x \in \{ - 1, 1 \} ^ { n } } | \langle a, x \rangle | \leq \| a \| _ { 2 }.$$

Equality is attained when a is a standard unit basis vector.

The 2 × n case is the next natural subject of interest. This case appears to already be remarkably challenging and gives rise to some amusing problems. We believe to have identified the correct answer and verified it numerically in low dimensions, but were unable to prove this rigorously.

Conjecture 1. An optimal 2 × n matrix is given by

$$A = \frac { 1 } { \sqrt { 2 } } \begin{bmatrix} 1 & 1 & 0 & \cdots & 0 \\ 1 & - 1 & 0 & \cdots & 0 \end{bmatrix}$$

The structure theorem immediately suggests the connection to set partitions. While investigating this connection, we came across a question that we were able to resolve and which appears to be of intrinsic interest.

Theorem 5 (Partition Theorem) . For any A ⊂ {-1 1 , } n we have

$$\left \| \sum _ { x \in A } x \right \| _ { 2 } \leq 2 ^ { n - 1 }$$

with equality if we choose A to be the set of all vectors whose i th coordinate is fixed to be either 1 or -1 .

Remark 1. Dividing by 2 n , we see that Theorem 5 equivalently states that a random vector X that is uniformly distributed in the Boolean cube {-1 1 , } n satisfies

$$\left \| \mathbb { E } [ X \mathbf 1 _ { X \in A } ] \right \| _ { 2 } \leq \frac { 1 } { 2 }$$

for any A ⊂ {-1 1 , } n . Actually, the same is true not just for the uniform distribution on the Boolean cube, but for any mean zero isotropic random vector (a random vector X is isotropic if E [ XX ⊤ ] = Id n or equivalently E [ ⟨ X,v ⟩ 2 ] = || v || 2 2 for all v ∈ R n ). We state this generalization (for suggesting which we thank an anonymous reviewer) separately below.

Proposition 1 (Theorem 5 for Centered Isotropic Vectors) . Let X be a mean zero isotropic random vector in R n and let A be a measurable subset of R n . Then

$$\left | \left | \mathbb { E } [ X \mathbf 1 _ { X \in A } ] \right | \right | _ { 2 } \leq \frac { 1 } { 2 }.$$

2.5. ℓ p Variants. The ℓ ∞ norm leads to fascinating extremizers but is otherwise difficult to deal with. A natural question is whether and in what way things change if we investigate the problem for other p . As it turns out, the natural other cases p = 1 and p = 2 are not quite as interesting and can be easily resolved. For 2 &lt; p &lt; ∞ we are unable to compute extremizers but can characterize the twosided asymptotic behavior.

## Proposition 2 ( p = 1 and p = 2) . We have

$$\max _ { A \in \mathbb { R } ^ { n \times n } } \mathbb { E } \left \| A X \right \| _ { 1 } = n$$

with equality being attained at the identity matrix. Moreover,

$$\max _ { A \in \mathbb { R } ^ { n \times n } } \mathbb { E } \left \| A X \right \| _ { 1 } = \sqrt { n }$$

with equality if A is an isometry.

We note that the problem of finding optimal matrices in the intermediate range 2 &lt; p &lt; ∞ remains open but Theorem 6 below is a first attempt at characterizing the correct orders of growth. Even though the bounds are not sharp in the cases p = 1 2, the argument works for all , p ∈ [1 , ∞ ], so we state it in its full generality.

Theorem 6 (1 ≤ p ≤ ∞ ) . As before, let X be a random vector with entries drawn independently and uniformly at random from {-1 1 , } . Then, we have

$$\max _ { A \in \mathbb { R } ^ { n \times n } } \mathbb { E } \| A X \| _ { p } \asymp \begin{cases} \sqrt { p } n ^ { 1 / p } & \text{if $p \leq \log n$,} \\ \sqrt { \log n } & \text{if $p \geq \log n$.} \end{cases}$$

3. Proofs

## 3.1. Proof of the Structure Theorem.

↦

Proof of Theorem 1. Define W i to be the set of x ∈ {± } 1 n so that i is the smallest index with absolute largest coordinate in Ax . By construction, we see that the W i are closed under x →-x , that they are disjoint, and hence partition {± } 1 n . Thus we can write:

$$\beta ( A ) = \mathbb { E } \left \| A X \right \| _ { \infty } = \frac { 1 } { 2 ^ { n } } \sum _ { x \in \{ \pm 1 \} ^ { n } } \left \| A x \right \| _ { \infty } = \frac { 1 } { 2 ^ { n } } \sum _ { i = 1 } ^ { n } \sum _ { x \in W _ { i } } | a _ { i } ^ { \top } x |$$

Now take U i = { x ∈ W i ∣ ∣ | a T i x | = a T i x } to be the positive half of W i . For each x ∈ W i with a T i x = 0, U i will include both x and -x , but we will eventually want U i to be antipodal. So in this case keep only one of x and -x . Then we have that:

$$\sum _ { x \in W _ { i } } | a _ { i } ^ { \top } x | = 2 \sum _ { x \in U _ { i } } a _ { i } ^ { \top } x.$$

The idea is to now optimize each of the sums ∑ x ∈ U i a ⊤ i x separately, since we have removed the independence among the rows from the objective function. One has

$$2 \sum _ { x \in U _ { i } } \langle a _ { i }, x \rangle = 2 \left \langle a _ { i }, \sum _ { x \in U _ { i } } x \right \rangle$$

By the Cauchy-Schwarz inequality,

$$\left \langle a _ { i }, \sum _ { x \in U _ { i } } x \right \rangle \leq \| a _ { i } \| \left \| \sum _ { x \in U _ { i } } x \right \| = \left \| \sum _ { x \in U _ { i } } x \right \|$$

since each of A 's rows have norm 1. Now, if A does not have equality for all of the above inequalities, then we could replace A 's rows with

$$\frac { \sum _ { x \in U _ { i } } x } { \| \sum _ { x \in U _ { i } } x \| }$$

to make the objective function strictly larger. But A is optimal, so we see that a i is a positive multiple of the above vector, again by Cauchy-Schwarz. Since a has unit norm, we conclude that completing the proof.

$$a _ { i } = \pm \frac { \sum _ { x \in U _ { i } } x } { \| \sum _ { x \in U _ { i } } x \| },$$

Notice that since each of the x ∈ U i are vectors on the hypercube, namely have every coordinate of ± 1, ∑ x ∈ U i x is a vector with integer coordinates. Thus we see that ∥∑ ∥ x ∈ U i x ∥ ∥ is a square root of an integer, and hence every entry of a i is a square root of a rational number.

## 3.2. Proof of Corollary 2.

Proof of Corollary 2. This argument uses a computer search to check all possible candidate matrices. Theorem 1 implies each row a i of an optimal matrix A is a normalized sum of vectors contained in some subset V ⊆ {-1 1 , } n , i.e.

$$a _ { i } = \frac { \sum _ { x \in V } x } { \| \sum _ { x \in V } x \| }.$$

We can now check all possible matrices formed by combining rows of this form. Note, however, that this exhaustive search becomes prohibitive very quickly. Indeed, there are 2 2 n possible subsets of {-1 1 , } n , and must consider all possible n -tuples of rows of this form. Na¨ ıvely, this yields (2 2 n ) n = 2 n · 2 n matrices to check. For n = 3 the search space is of size 2 24 ≈ 1 7 . × 10 , 7 and for n = 4 we have 2 64 ≈ 1 8 . × 10 19 possibilities. We exploit the following symmetries.

- (i) The β value of a matrix is invariant under permutations over rows.
- (ii) An optimal matrix may not have duplicate rows.
- (iii) An optimal matrix doesn't have zero rows.

- (iv) The β value of a matrix is invariant under row-wise sign flips

Observations (i) and (ii) allow us to consider row combinations instead, yielding ( 2 2 n n ) matrices to check. By observation (iii), we further reduce the search space by deleting the zero rows (for instance the full subset V = {-1 1 , } n yields such a row) and by observation (iv) we eliminate duplicate rows equal up to a sign flip (for instance, we keep only one of the rows arising from the subsets V 1 = { 1 } × {-1 1 , } n -1 and V 2 = {- } × {-1 1 1 , } n -1 ).

For the n = 3 case, we start with 2 2 3 = 256 rows, 238 of which are non-zero. Furthermore, since there may be multiple subsets V leading to the same row, we eliminate redundant ones, yielding 50 unique rows. Finally, removing redundant rows up to a sign-change reduces the search space to 25 final rows. This leaves ( 25 3 ) = 2300 candidate matrices, which can be easily computed.

The n = 4 case is approached in the same manner. Performing the same reductions as before, we go from 2 2 4 = 65536 rows to 680 candidate rows, yielding ( 680 4 ) = 8830510430 matrices to check. These can be checked in a rather long but attainable amount of time. For context, a na¨ ıve sequential search took 72 hours to complete but we suspect it could be vastly parallelized to reduce the runtime.

However, the n = 5 case is prohibitively expensive, since the initial rows 2 2 5 ≈ 4 3 . × 10 9 cannot even be loaded into memory. Similarly, the rectangular bad science problem of dimensions 2 × 3, 2 × 4 and 3 × 4 can be checked, with search spaces of size ( 25 2 ) = 300 , ( 680 2 ) = 230860 and ( 680 3 ) = 52174360, respectively. The first two cases took less than a minute to run, but the 3 × 4 took one hour on Google Colab. The Jupyter Notebooks containing the row reductions and the exhaustive search, with step-by-step comments, can be found in the Github repository [5]. □

## 3.3. Proof of Theorem 2.

Proof of Theorem 2. Fix

$$\gamma = \frac { \beta ( A ) } { \sqrt { \beta ( A ) ^ { 2 } + 1 } }$$

and let x = [ x 1 x 2 ] ∈ {-1 1 , } 2 n 0 , with x 1 ∈ {-1 1 , } n 0 and x 2 ∈ {-1 1 , } n 0 . Then, Bx can be written as

$$B x = \begin{bmatrix} \gamma A x _ { 1 } + \sqrt { 1 - \gamma ^ { 2 } } x _ { 2 } \\ \gamma A x _ { 1 } - \sqrt { 1 - \gamma ^ { 2 } } x _ { 2 } \end{bmatrix}$$

Note that coordinate j of Bx has the form

$$( B x ) _ { j } = \begin{cases} \gamma a _ { j } ^ { \top } x _ { 1 } + \sqrt { 1 - \gamma ^ { 2 } } ( x _ { 2 } ) _ { j } & \text{if } \ 1 \leq j \leq n _ { 0 } \\ \gamma a _ { j - n _ { 0 } } ^ { \top } x _ { 1 } - \sqrt { 1 - \gamma ^ { 2 } } ( x _ { 2 } ) _ { j - n _ { 0 } } & \text{if } \ n _ { 0 } < j \leq 2 n _ { 0 } \end{cases}$$

We now note that each term of the form γ · a ⊤ j x 1 contributes to two different coordinates of Bx : it does once to coordinate j , with the term being added to √ 1 -γ 2 ( x 2 ) j , and again to coordinate j + n 0 , with the term being subtracted √ 1 -γ 2 ( x 2 ) j . Now, we may bound the absolute value of the coordinates of Bx

in a straightforward manner. Letting the index 1 ≤ i ≤ n 0 be the one for which ∥ Ax 1 ∥ ∞ = | a ⊤ i x 1 | holds, for 1 ≤ j ≤ n 0 we have

$$| ( B x ) _ { j } | & \leq \max \{ | \gamma a _ { j } ^ { \top } x _ { 1 } + \sqrt { 1 - \gamma ^ { 2 } } ( x _ { 2 } ) _ { j } |, | \gamma a _ { j } ^ { \top } x _ { 1 } - \sqrt { 1 - \gamma ^ { 2 } } ( x _ { 2 } ) _ { j } | \} \\ & \leq \gamma | a _ { j } ^ { \top } x _ { 1 } | + \sqrt { 1 - \gamma ^ { 2 } } \\ & \leq \gamma | a _ { i } ^ { \top } x _ { 1 } | + \sqrt { 1 - \gamma ^ { 2 } } = \gamma \, \| A x _ { 1 } \| _ { \infty } + \sqrt { 1 - \gamma ^ { 2 } } \\. \quad. \quad. \quad. \cdots.. \cdots.. \cdots........................................................................................................................................................................................................$$

and equally for the second half of the coordinates | ( Bx ) j + n 0 | . Thus

$$\| B x \| _ { \infty } \leq \gamma \, \| A x _ { 1 } \| _ { \infty } + \sqrt { 1 - \gamma ^ { 2 } }.$$

The important observation comes from noting that if the terms a ⊤ j x 1 and √ 1 -γ 2 ( x 2 ) j agree in sign, then coordinate j will be larger in absolute value than coordinate j + n 0 , and vice-versa if a ⊤ j x 1 and √ 1 -γ 2 ( x 2 ) j disagree in sign. With this in mind, we see that one of the choices j = i or j = + i n 0 (the one in which the terms γa ⊤ i x 1 and √ 1 -γ 2 ( x 2 ) i or γa ⊤ i x 1 and -√ 1 -γ 2 ( x 2 ) i agree in sign) achieves equality in each step, yielding ∥ Bx ∥ ∞ = γ ∥ Ax 1 ∥ ∞ + √ 1 -γ 2 . It is easy to see that summing over all possible x = {-1 1 , } 2 n 0 translates this result to the β setting:

$$\dots \dots \, r \dots \dots \, \lambda \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psigma \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psis \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psilon \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psp \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psu \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psim \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psip \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psj \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psus \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \pss \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psing \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \ps i \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psig \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psiv \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psio \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psI \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psphi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \ps} \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \psi \quad \ps$$

Plugging in γ = β A / ( ) √ β 2 ( A ) + 1, we obtain

$$\beta ( B ) = \frac { 1 } { \sqrt { \beta ( A ) ^ { 2 } + 1 } } + \frac { \beta ^ { 2 } ( A ) } { \sqrt { \beta ( A ) ^ { 2 } + 1 } } = \sqrt { \beta ( A ) ^ { 2 } + 1 }.$$

Finally, we note that if A has normalized rows then B does too, since γ 2 +1 -γ 2 = 1. This completes the proof. □

## 3.4. Proof of Theorem 3.

Definition 2. We define A as a set of square matrices which we construct from building a binary tree which is highly balanced as in Definition 1. Every row in the matrix corresponds to some leaf in the tree, and every column in the matrix corresponds to a level of the binary tree. Given this binary tree we yield the corresponding matrix in the following way:

- · We let the first column be the all 1's column.
- · For every path from the root to the leaves: we correspond A i,j to the leaf with index i ∈ [ n ] at the j 'th vertex in the path from the root. If this vertex represents the left child of its parent vertex, we let this entry be -1, otherwise we let this entry be +1. Entries that do not correspond to vertices in this tree correspond to 0's in the matrix.

## Example of binary tree with five leaves.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00933v2-figure-189ff82c-5da5-4d71-adaf-3d4a70609a53.jpg)

We construct the corresponding matrix by mapping every leaf to the row with the same index and the index of every column corresponding to the level in the tree. For example, to construct row 3, we examine the root-to-leaf path of the leaf labeled with 3 which is { +1 , -1 +1 . , } We set the first 3 entries of the row to match this prefix and set the rest of the entries of the row to 0. We repeat this process for the rest of the rows in this binary tree and before normalization, the corresponding matrix would look as follows:

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00933v2-figure-df35ccce-88b4-4a69-880d-b2e3b01a1f86.jpg)

We would then normalize the rows of this matrix to discuss its β value. We now use these matrices to prove Theorem 3.

Proof of Theorem 3. Suppose 2 k &lt; n &lt; 2 k +1 (deferring the case when n = 2 k to Corollary 4), i.e. k = log ( ⌊ 2 n ) ⌋ . Note that all rows of A are of the form {± } 1 k +1 followed by n -k -1 zeros or {± } 1 k +2 followed by n -k -2 zeros. We leverage the fact that if | a T i x | = ∥ Ax ∥ ∞ for x in the cube, then x = ± a i entry-wise except for the zero entries of a i . This is because if we let ˜ be obtained by truncating the a zeros off of a i , Cauchy-Schwarz tells us that max ∥ ˜ x ∥ =1 | ˜ a T ˜ x | is obtained at ˜ = x ± ˜. a Therefore, for any x ∈ {-1 1 , } n , ∥ Ax ∥ ∞ is √ k +1 or √ k +2, corresponding to the length of the matched prefix. The number of possible vectors x which agree (in the aforementioned manner) with a i is given by either 2 n - -k 1 · 2 or 2 n - -k 2 · 2, (two choices for each zero entry, and one last doubling to account for negation). Then,

we have that

$$\text{we have that} \\ \beta ( A ) & = \frac { 1 } { 2 ^ { n } } \cdot \left [ \sqrt { k + 1 } \cdot ( 2 ^ { k + 1 } - n ) \cdot 2 ^ { n - k } + \sqrt { k + 2 } \cdot ( 2 n - 2 ^ { k + 1 } ) \cdot 2 ^ { n - k - 1 } \right ] \\ & = \sqrt { k + 1 } \cdot \frac { 2 ^ { k + 1 } - n } { 2 ^ { k } } + \sqrt { k + 2 } \cdot \frac { 2 n - 2 ^ { k + 1 } } { 2 ^ { k + 1 } } \\ & = \left ( 2 \sqrt { k + 1 } - \sqrt { k + 2 } \right ) + \frac { n } { 2 ^ { k } } \cdot \left ( \sqrt { k + 2 } - \sqrt { k + 1 } \right ) \\ \text{Renlacing} \sigma \, k \, \text{ as } | \log ( n ) | \text{ recovers the desired expression.} } \quad \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{                                                                                                                                                                                                         } \text{                                                                                                                                                                                                    } \text{ }$$

Replacing k as ⌊ log 2 ( n ) ⌋ recovers the desired expression.

□

## 3.5. Proof of Lemma 4.

Proof of Lemma 4. We may assume without loss of generality that ∥ a ∥ ℓ 2 = 1. First, recallling that

$$\beta ( a ) = \mathbb { E } \left \| a ^ { \top } X \right \| _ { \infty } = \frac { 1 } { 2 ^ { n } } \sum _ { x \in \{ - 1, 1 \} ^ { n } } | a ^ { \top } x |.$$

we let x be a Rademacher vector. It remains to prove E [ | a ⊤ X | ] ≤ 1. We start by showing that E [ XX ⊤ ] = Id n × n . Notice that

$$\mathbb { E } [ X X ^ { \top } ] _ { i j } = \mathbb { E } [ X _ { i } X _ { j } ] = \begin{cases} 1 & i = j \\ 0 & \text{otherwise}. \end{cases}$$

Now by Jensen's inequality,

$$\mathbb { E } [ | a ^ { \top } X | ] & = \mathbb { E } \left [ \sqrt { ( a ^ { \top } X ) ^ { 2 } } \right ] \leq \sqrt { \mathbb { E } [ a ^ { \top } X X ^ { \top } a ] } = \sqrt { a ^ { \top } \mathbb { E } [ X X ^ { \top } ] a } \\ & = \sqrt { a ^ { \top } a } = 1$$

since ∥ a ∥ 2 = 1. This completes the proof.

3.6. Proof of Theorem 5. We first start with a simple Lemma.

$$\text{Lemma} \ 7. \ T h e \ s e t \ A \subset \{ - 1, 1 \} ^ { n } \ m a x i m i z i n g$$

$$A \rightarrow \left \| \sum _ { a \in A } a \right \| _ { 2 }$$

has cardinality # A = 2 n -1 and does not contain any antipodal points.

Proof. For the sake of contradiction, assume the optimal set A contains a set of antipodal points a, -a ∈ A . Then, A = U ∪ {-a, a } for some set U ⊂ {-1 1 , } n . We now consider the term ∥∑ ∥ u ∈ U u ∥ ∥ 2 . By switching a with -a if necessary, we may without loss of generality assume that ⟨ ∑ u ∈ U u, a ⟩ ≥ 0. Then, by adding the strictly positive term ∥ a ∥ 2 and the nonnegative term 2 〈∑ u ∈ U u, a 〉 , we obtain the

□

strict inequality

$$\left \| \sum _ { u \in U } u \right \| ^ { 2 } < \left \| \sum _ { u \in U } u \right \| ^ { 2 } + 2 \left \langle \sum _ { u \in U } u, a \right \rangle + \| a \| ^ { 2 } = \left \| \sum _ { u \in U \cup \{ a \} } u \right \| ^ { 2 }.$$

Finally, we note that ∥∑ ∥ u ∈ A u ∥ ∥ 2 = ∥∑ ∥ u ∈ U u ∥ ∥ 2 since a and -a cancel out in the sum. This shows the set A is not optimal, a contradiction. Having established this, it is easy to see that # A = 2 n -1 . Indeed, for an optimal set A , if # A &gt; 2 n -1 the pigeonhole principle ensures two antipodal points, a contradiction. If # A &lt; 2 n -1 , we may apply the pigeonhole principle to the complement set {-1 1 , } n \ A of size 2 n -# A &gt; 2 n -2 n -1 &gt; 2 n -1 , which shares the same objective value as A , to determine it is non-optimal. □

̸

Proof of Theorem 5. Lemma 7 shows that it suffices to consider sets A of size 2 n -1 with no pair of antipodal points (if a ∈ A then -a ∈ A ). Working under such assumptions, we let u = ∑ a ∈ A a , expand the square of the norm, and use the linearity of the inner product:

$$\left \| \sum _ { a \in A } a \right \| ^ { 2 } = \sum _ { a, b \in A } a ^ { \top } b = \sum _ { b \in A } \, \left ( \sum _ { a \in A } a \right ) ^ { \top } b = \sum _ { b \in A } u ^ { \top } b.$$

Next, we bound each term by its absolute value and add all the antipodal points into the sum, dividing the total expression by 2 to maintain equality:

$$\sum _ { b \in A } u ^ { \top } b \leq \sum _ { b \in A } | u ^ { \top } b | = \frac { 1 } { 2 } \sum _ { b \in \{ \pm 1 \} ^ { n } } | u ^ { \top } b | \,.$$

̸

We furthermore assume that u = 0 since this case is trivially suboptimal. Thus, we normalize u by multiplying and dividing by ∥ u ∥ ,

$$\frac { 1 } { 2 } \sum _ { b \in \{ \pm 1 \} ^ { n } } \left | u ^ { \top } b \right | = \frac { \left \| u \right \| } { 2 } \sum _ { b \in \{ \pm 1 \} ^ { n } } \left | \frac { u } { \left \| u \right \| } ^ { \top } b \right |$$

Since we have a normalized vector and sum over all possible hypercube vectors, we may apply Theorem 4 to obtain

$$\frac { \| u \| } { 2 } \sum _ { b \in \{ \pm 1 \} ^ { n } } \left | \frac { u } { \| u \| } ^ { \top } b \right | \leq \frac { \| u \| } { 2 } \sum _ { b \in \{ \pm 1 \} ^ { n } } \left | e _ { i } ^ { \top } b \right |$$

for all 1 ≤ i ≤ n , where e i ∈ R n is the i th standard unit vector. Since | e ⊤ i b | = 1 for all b ∈ {-1 1 , } n , the right hand side is simply

$$\frac { \| u \| } { 2 } \sum _ { b \in \{ \pm 1 \} ^ { n } } \left | e _ { i } ^ { \top } b \right | = \frac { \| u \| } { 2 } \cdot 2 ^ { n } = \| u \| \, 2 ^ { n - 1 }.$$

It now suffices to divide both sides by ∥ u ∥ = ∥∑ ∥ a ∈ A a ∥ ∥ to obtain the upper bound ∥∑ ∥ a ∈ A a ∥ ∥ ≤ 2 n -1 . Finally, we determine the optimal sets by asking when equality is achieved. By Theorem 6, we note that the inequalities become equalities if and

only if u/ ∥ u ∥ = e i . We see that A = A i = { a ∈ {-1 1 , } n : a i = 1 } satisfies

$$\frac { \sum _ { a \in A } a } { \| \sum _ { a \in A } a \| } = e _ { i },$$

and the proof is complete.

□

3.7. Proof of Proposition 1. We thank an anonymous reviewer for suggesting the proof technique used below.

Proof of Proposition 1. Define the random variable

$$\Phi = \begin{cases} 1 & \text{if $X\in A$,} \\ - 1 & \text{if $X\in \bar{A}$.} \end{cases}$$

Then 2 X 1 X A ∈ = Φ X + X . Since X is mean-zero,

$$2 \mathbb { E } [ X \mathbf 1 _ { X \in A } ] = \mathbb { E } [ \Phi X ] \, \coloneqq v.$$

Then expanding yields

$$\begin{array} {$$

Dividing both sides by ∥ 2 E [ X 1 X A ∈ ] ∥ 2 then completes the proof. □

## 3.8. Proof of Proposition 2.

Proof of Proposition 2. For 1 ≤ p ≤ ∞ and n ∈ N , we abbreviate

$$\beta _ { n, p } = \max _ { A \in \mathbb { R }$$

We also note that ∥ A ∥ F = √ ∑ i,j A 2 ij = √ n since A has normalized rows.

The case p = 1 : Taking a i to be the i th row of A , we have that,

$$\frac { 1 } { 2 ^ { n } } \sum _ { x \in \{ -$$

since E [ | a T i X | ] ≤ 1 when x is a vector with ± 1 random entries with equal probability, and | a i | = 1 by Theorem 2.3 (the 1 × n case). The identity matrix achieves this, since ∥ x ∥ 1 = n for every x ∈ {± } 1 n .

The case p = 2 : Again by Jensen's inequality, we have that

$$\mathbb { E } \left [ \| A X \| _ { 2 } \right ]$$

Then, since if b ∈ R then we can treat b as a 1 × 1 matrix and have b = Tr( ), b yielding

$$\begin{array} {$$

The entry of AA ⊤ at position ( i, i ) is just a ⊤ i a i = ∑ j A 2 ij if a i is the i th row of A . The sum of all these is then seen to be ∑ i,j A 2 ij = n as we showed above. This shows that,

$$\mathbb { E } [ \| A X \| _ { 2 } ] \leq \sqrt { n }$$

Now we shall show that if A is orthogonal then the above becomes an equality. Recall that Jensen's inequality becomes an equality if the random variable is constant. When A is orthogonal, we have that ∥ Ax ∥ 2 2 = x ⊤ A Ax ⊤ = x ⊤ x = n . Thus in this case x ⊤ A Ax ⊤ is constant and the above becomes an equality. □

## 3.9. Proof of Theorem 6.

Proof of Theorem 6. We thank an anonymous reviewer for suggesting an improved proof technique that appears below.

Upper bounds. The simplest case is when p ≥ log n , which follows immediatelty after observing n 1 /p ≤ n 1 / log n = e and using Steinerberger's asymptotic result on ∥ AX ∥ ∞ [4], which gives

$$\| A X \| _ { p } \leq n ^ { 1 / p } \| A X \| _ { \infty } \lesssim \| A X \| _ { \infty } \lesssim \sqrt { \log n }.$$

The case 2 &lt; p ≤ log n may be tackled by Khintchine's inequality [2],

$$\mathbb { E } | a ^ { \top } X | ^ { p } \leq \frac { 2 ^ { p / 2 } } { \sqrt { \pi } } \Gamma \left ( \frac { p + 1 } { 2 } \right ) \leq 2 ^ { p / 2 } ( p / 2 )!$$

Thus, by Jensen's inequality and Stirling's approximation,

$$\i i n s, \, \L y \, \text{euse} \, s \, \text{equality} \, \text{and} \, \text{using} \, s \, \text{app} \, \text{touse} \, \text{on}, \\ \mathbb { E } \left [ \| A X \| _ { p } \right ] & \leq \left ( \sum _ { i = 1 } ^ { n } \mathbb { E } | a _ { i } ^ { \top } X | \right ) ^ { 1 / p } \leq \left ( n \cdot 2 ^ { p / 2 } ( p / 2 )! \right ) ^ { 1 / p } \\ & \leq C n ^ { 1 / p } ( p / 2 )! ^ { 1 / p } \leq C n ^ { 1 / p } \frac { ( p / 2 ) ^ { 1 / 2 + 1 / p } } { e ^ { 1 / 2 - 1 / p } } \leq C n ^ { 1 / p } ( e / 2 ) ^ { 1 / p } p ^ { 1 / p } p ^ { 1 / 2 } \\ & \leq C p ^ { 1 / 2 } n ^ { 1 / p }, \\ \hat { \epsilon } \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdots$$

for some constant C independent of p (which we allow to change from line to line; in this case the constant changed 3 times in 1 line).

Lower bounds . We consider the case where a Rademacher-valued vector X ∈ {-1 1 , } n is fixed and the randomness instead comes from the matrix, which has

independent and uniformly random ± 1 / √ n entries. The case p ≥ log n is again straightforward using Steinerberger's asymptotic bound,

$$\mathbb { E } \left \| A X \right \| _ { p } \geq \mathbb { E } \left \| A X \right \| _ { \infty } \gtrsim \sqrt { \log n }.$$

↦

To improve this bound in the case p ≤ log n , partition the set { 1 , . . . , n } into n/e p disjoint sets I j of cardinality approximately e p . By concavity of x → x 1 /p , we apply Jensen's inequality,

$$\mathbb { E } \left \| A X \right \| _ { p } & \geq \left ( \sum _ { j = 1 } ^ { n / e ^ { p } } \mathbb { E } \sum _ { i = 1 } ^ { e ^ { p } } | \langle a _ { i }, X \rangle | ^ { p } \right ) ^ { 1 / p } \\ & \geq \left ( \sum _ { j = 1 } ^ { n / e ^ { p } } \mathbb { E } \max _ { i \in I _ { j } } | \langle a _ { i }, X \rangle | ^ { p } \right ) ^ { 1 / p } \\ \intertext { a n e d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d e d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n D i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i N d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d i n d ierrow$$

where the second inequality comes from replacing the sum with the maxima. For a fixed j we may apply Steinerberger's asymptotic lower bound again to obtain E max i ∈ I j |⟨ a , X i ⟩| p ≳ √ log | I j | ≳ √ p , hence

$$\mathbb { E } \left \| A X \right \| _ { p } \gtrsim \left ( n / e ^ { p } \right ) ^ { 1 / p } \sqrt { p } \gtrsim n ^ { 1 / p } \sqrt { p }$$

Having obtained the desired bounds for this case, we conclude the proof using Fubini-Tonelli:

$$\max _ { A } \mathbb { E } \left \| A X \right \| _ { p } \geq \mathbb { E } _ { A } \, \mathbb { E } _ { X } \left \| A X \right \| _ { p } = \mathbb { E } _ { X } \, \mathbb { E } _ { A } \left \| A X \right \| _ { p } \gtrsim \begin{cases} \sqrt { p } n ^ { 1 / p } & \text{if $p \leq \log n$} \\ \sqrt { \log n } & \text{if $p \geq \log n$} \end{cases}$$

where E A denotes the expectation with respect to the matrices with uniformly random entries in ± 1 / √ n , and E X to the uniformly distributed Rademacher vectors. □

## References

- [1] W. Banaszczyk, Balancing vectors and gaussian measures of n -dimensional convex bodies, Random Structures &amp; Algorithms, 12(4):351-360, 1998.
- [2] U. Haagerup, The best constants in the Khintchine inequality, Studia Mathematica 70.3 (1981): p. 231-283.
- [3] D. Kunisky, The discrepancy of unsatisfiable matrices and a lower bound for the Koml´s o conjecture constant, SIAM Journal on Discrete Mathematics 37.2 (2023): p. 586-603.
- [4] S. Steinerberger, Bad science matrices, arXiv:2402.03205.
- [5] Bad Science Matrix Optimization GitHub repository (2024), https://github.com/ alexalbors7/Bad-Science-Matrix-Optimization .

University of Washington, Seattle, WA 98195, USA

Email address : aalbors@uw.edu

University of Washington, Seattle, WA 98195, USA

Email address : hishamb@uw.edu

University of Washington, Seattle, WA 98195, USA

Email address : lganjoo@uw.edu

University of Washington, Seattle, WA 98195, USA

Email address : rpg360@uw.edu

Department of Applied Mathematics and Statistics, Johns Hopkins University, MD 21211, USA

Email address : kunisky@jhu.edu

University of Washington, Seattle, WA 98195, USA

Email address : rbmuk@uw.edu

University of Washington, Seattle, WA 98195, USA

Email address :

astepin@uw.edu

Department of Mathematics, University of Washington, Seattle, WA 98195, USA

Email address :

txz@uw.edu
Alex Albors Hisham Bhatti Lukshya Ganjoo Raymond Guo Dmitriy Kunisky Rohan Mukherjee Alicia Stepin Tony Zeng
On the Structure of Bad Science Matrices
The bad science matrix problem consists in finding, among all matrices $A \in
\mathbb{R}^{n \times n}$ with rows having unit $\ell^2$ norm, one that
maximizes $\beta(A) = \frac{1}{2^n} \sum_{x \in \{-1, 1\}^n} \|Ax\|_\infty$.
Our main contribution is an explicit construction of an $n \times n$ matrix $A$
showing that $\beta(A) \geq \sqrt{\log_2(n+1)}$, which is only 18% smaller than
the asymptotic rate. We prove that every entry of any optimal matrix is a
square root of a rational number, and we find provably optimal matrices for $n
\leq 4$.