On exact discretization of the $L_2$-norm in the space spanned by the first $N$ Rademacher functions

Technical Summary: On Exact Discretization of the L2-norm in the Space Spanned by the First N Rademacher Functions

Problem Statement
The paper investigates the problem of exact discretization of the $L^2$-norm within the $N$-dimensional subspace $R_N \subset L^2([0,1])$ spanned by the first $N$ Rademacher functions, denoted as $\langle r_0, \dots, r_{N-1} \rangle$. The core objective is to determine the minimal number of nodes, $m(R_N)$, and the corresponding weights $\{\lambda_j\}$ required to satisfy the exact Marcinkiewicz-type discretization identity:
$$\int_0^1 f^2(x) dx = \sum_{j=1}^m \lambda_j f^2(\xi_j)$$
for every function $f \in R_N$. The study distinguishes between the general case allowing arbitrary real weights ($m(R_N)$) and the restricted case requiring strictly positive weights ($m_+(R_N)$).

Methodology
The approach translates the discretization condition into a matrix algebra problem. By partitioning the interval $[0,1)$ into $2^N$ dyadic intervals, the problem is reformulated using a matrix $A$ whose entries correspond to the values of Rademacher functions on these intervals. The condition for exact discretization with weights $\Lambda = \text{diag}(\lambda_1, \dots, \lambda_m)$ and nodes corresponding to columns of $A$ is equivalent to the matrix equation:
$$A_j \Lambda_j A_j^T = E_N$$
where $A_j$ is the $N \times m$ submatrix of $A$ corresponding to the selected nodes, $\Lambda_j$ is the diagonal matrix of non-zero weights, and $E_N$ is the $N \times N$ identity matrix.

The analysis proceeds by:

1. Establishing a lower bound for $m$ using rank arguments.
2. Investigating the structural properties of $A_j$ when $m=N$, linking the existence of a solution to the existence of Hadamard matrices.
3. Constructing explicit solutions for $m=N+1$ to establish an upper bound.
4. Analyzing the constraints on weights for $m=N+1$ when $N$ satisfies specific modular arithmetic conditions ($N \equiv 1, 2 \pmod 4$) to determine if positive weights are possible.

Key Contributions and Results

1. Lower Bound and Connection to Hadamard Matrices:
   The paper proves that the minimal number of nodes satisfies $m(R_N) \ge N$. Furthermore, it establishes that $m(R_N) = N$ if and only if a Hadamard matrix of order $N$ exists. In this case, the optimal weights are uniform ($\lambda_j = 1/N$) and positive.

2. Upper Bound and Explicit Construction:
   The author provides an explicit construction demonstrating that $m(R_N) \le N + 1$ for all $N$. This construction utilizes $N+1$ specific dyadic intervals and assigns weights such that $N$ weights equal $1/4$ and the $(N+1)$-th weight equals $(4-N)/4$. This construction yields a valid discretization but may involve negative weights if $N > 4$.

3. Characterization of Minimal Node Counts:
   The paper derives a precise formula for the minimal number of nodes based on the Hadamard conjecture:
   $$m(R_N) = \begin{cases} N & \text{if a Hadamard matrix of order } N \text{ exists} \\ N + 1 & \text{otherwise} \end{cases}$$
   This result highlights a direct dependency between the discretization efficiency of Rademacher spaces and the existence of Hadamard matrices.

4. Impossibility of Positive Weights for Specific $N$:
   A significant contribution is the proof that for certain dimensions, strictly positive weights are impossible when using the minimal number of nodes. Specifically, if $N \equiv 1 \pmod 4$ ($N \ge 5$) or $N \equiv 2 \pmod 4$ ($N \ge 6$), then $m_+(R_N) > m(R_N) = N + 1$.

   • For $N \equiv 1 \pmod 4$, the proof utilizes orthogonality arguments to show that assuming positive weights leads to a contradiction with the non-existence of a Hadamard matrix of order $N+1$.
   • For $N \equiv 2 \pmod 4$, the proof employs combinatorial counting of sign agreements among Rademacher functions to derive a contradiction regarding the divisibility of $N$ by 4.

Significance and Claims
The paper claims to resolve the exact discretization problem for Rademacher subspaces by determining the minimal number of nodes required and characterizing the nature of the weights (positive vs. negative). The work demonstrates that the problem is intrinsically linked to the Hadamard conjecture.

The author notes that the gap between the minimal number of nodes allowing general weights ($m(R_N)$) and those requiring positive weights ($m_+(R_N)$) is closely tied to the Hadamard conjecture. If the conjecture holds (that Hadamard matrices exist for all orders divisible by 4), the paper asserts that the difference between these two quantities is uniformly bounded:
$$m_+(R_N) - m(R_N) \le 2$$
The study serves to clarify the limitations of positive-weight discretization in high-dimensional spaces generated by Rademacher functions, showing that negative weights are sometimes necessary to achieve the theoretical minimum number of nodes.