About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
May 2023 - Solution
May 2023 Solution:
The numerical results are
52390.274 for
156032.269 for
We have accepted other, less exact solutions.
The naive solution for computing requires
steps (ignoring
).
Instead, We describe here a clever way to compute the form in
steps, based on the solution
communicated to us by Lorenzo Gianferrari Pini.
First of all, note that takes values from the length
vector
, so we can rewrite the sum by
agglomerating over the values of
:
Define a length vector
by
. Given
, the requested solution is
.
From now on we can focus on computing for a specific value of
. This is done using a technique similar
to the inclusion-exclusion principle.
We illustrate this for and
In this case, since Q_2 agree precisely on the indices
and disagree on
. Since
Agrees with
on index
and
with
on index
, it does not participate in this sum.
We now present a different way of obtaining this sum (more efficient when used in general). For any subset
Define an indicator function
taking the value 1 if
and
agree on the indices in
(indices not in
are not considered at all) and 0 otherwise.
Now note that the sum can be written using
indicators:
Opening the product, we obtain a sum of products of the form
Each summand is an indicator for a set which is a superset of
. The sign of the summand is related to the
oddity of the extra number of indices added to
(indices not from
, which come from a term of the form
). We can write this in short form as
Switching the summation order we obtain
We are left with the question of how to compute . This is relatively easy
since we do not require
to be distinct in the indices not present in
. This means the relation
is an equivalence relation over the set
, and we can write:
In our example, we have
And indeed
This works in general. For any , denote by
the set of indices in the binary
representation of
which are
. We have
Since the expression is independent of
, it suffices to compute it once, for every subset
. We create a vector
such that
The inclusion-exclusion part is handled by defining a matrix
Recall that we defined
Such that is the required solution. We have now seen that
Thus, the algorithm for solving the problem efficiently is
1. Compute the matrix using the formula
2. Compute the vector using the formula
3. Compute
Steps 1 and 3 involve operations polynomial in ; the main computation is done in step 2, where for each of the
values of
, one has to go over the
vector
and sum according to the equivalance classes.
An unoptimized Python code for this computation is
import functools import numpy as np k = 5 @functools.lru_cache(maxsize=None) def Q(i): return [int((2**k)* (np.sin((i+1)*(t+1))-np.floor(np.sin((i+1)*(t+1))))) for t in range(k)] def num_to_set(t): binary = bin(t)[2:] return {i for i, bit in enumerate(binary[::-1]) if bit == '1'} def M(t, s): A = num_to_set(s) B = num_to_set(t) if not A.issuperset(B): return 0 else: diff = len(A.difference(B)) if diff % 2 == 0: return 1 else: return -1 def equiv_class_sum(t, x): A = num_to_set(t) results = {} for i in range(n): Qi = Q(i) subQ = tuple([Qi[j] for j in A]) if subQ not in results: results[subQ] = 0 results[subQ] += x[i] return sum(res**2 for res in results.values()) n = 2**30 a = np.linspace(0, 1, 2**k).reshape((1,2**k)) M = np.array([[M(t,s) for s in range(2**k)] for t in range(2**k)]) x = np.linspace(-1,1,n) v = np.array([equiv_class_sum(t, x) for t in range(2**k)]).reshape((2**k,1)) print((a @ M @ v)[0][0])