IBM Ponder This #301 · May 2023

This problem was suggested by Lorenzo Gianferrari Pini and Radu-Alexandru Todor - thanks!

Let $x\in {\mathbb{R}}^n$ be a length $n$ vector $(x_0,x_1,\dots ,x_{n-1})$ and $A\in {\mathbb{R}}^{n\times n}$ be an $n\times n$ matrix. We seek to compute the quadratic form $x^{T}Ax$.

Assume $x$ is equally spaced between $-1$ and $1$, e.g., for $n=5$, we have

$x=(-1,-0.5,0,0.5,1)$

The matrix $A$ is generated in the following manner:

Let $k\in \mathbb{N}$ be a natural number and define a vector $a\in {\mathbb{R}}^{2^k}$ that is equally spaced between $0$ and $1$, i.e., $a_t=\frac{t}{2^k-1}$ for $t=0,1,\dots ,2^k-1$. The values of $A$ will be taken from the vector $a$ in the following manner:

We are given a sequence $Q_0,Q_1,\dots ,Q_{n-1}$, with each $Q_i\in {\mathbb{N}}^k$ being a vector of $k$ natural numbers. Given two such vectors, define $Q_i==Q_j$ as the binary vector of length $k$ that has 1s in the entries that are equal in $Q_i,Q_j$ and 0s in the other entries. Let $[Q_i==Q_j]$ be the natural number whose binary representation is $Q_i==Q_j$, where the least significant bit is on index 0. For example, if

$Q_i=(1,5,7,8)$

$Q_j=(2,5,6,8)$

Then

$Q_i==Q_j=(0,1,0,1)$

And

$[Q_i==Q_j]$ = $10$ (since the vector $(0,1,0,1)$ stands for the binary representation 1010).

Now define $A_{ij}=a_{[Q_i==Q_j]}$.

So one can think of $A_{ij}$ as taking on a value from a fixed list of $2^k$ values based on the "similarity" between $Q_i$ and $Q_j$.

The values of the $Q_i$'s are chosen pseudo-randomly using the formula

$Q_i[t]=\lfloor 2^k\cdot (\sin ((i+1)\cdot (t+1))-\lfloor \sin ((i+1)\cdot (t+1))\rfloor )\rfloor$

For example, if $k=5$, then $Q_{13}=(31,8,2,15,24)$

Your goal: Find $x^{T}Ax$ (rounded to three decimals) for $k=5,n=2^{20}$.

A bonus "*" will be given for finding $x^{T}Ax$ (rounded to three decimals) for $k=5,n=2^{30}$.

Solution

Best opened after a real attempt

To be added.