Finding maximum via sum oracle

Question

Let $A$ be an array of real numbers with a unique maximum element, such that $size(A)=O(2^N)$. Assume that we have an oracle that can evaluate a sum over any subset of indices of $A$ in $O(1)$ time. Using this oracle, is it possible to find the index of the maximum of $A$ in $O(poly(N))$ time?

Answer 1

Assume, that there is an algorithm with such an oracle, which can find a maximum in $O(poly(N))$ time. Consider a set of variables $X = \{x_1, \ldots, x_{2^N}\}$. Let $L_X$ be a linear space over $\mathbb{R}$ with basis $X$. We call an arbitrary element $p \in L_{X}^{*}$ of dual space an assignment of variables $X$. Each assignment $p$ gives an instance of our problem. Let $A = \{a_1 = p(x_1), \ldots, a_{2^N} = p(x_{2^N})\}$ be one such assignment on which our hypothetical algorithm measured $m$ sums, given by sets of indices of elements which constitute these sums: $I_k = \{i_{k, 1}, \ldots, i_{k,j_k}\}$, where $k \in \{1, \ldots, m\}$, $\forall k \forall t \;i_{k,t} \in \{1, \ldots, 2^N\}$ and $\forall k \forall t \;i_{k,t} < i_{k,t+1}$. Let's denote $\widetilde{S}_k = \sum_{i \in I_k} x_i$ and $S_k = \sum_{i \in I_k} a_i = p(\widetilde{S}_k)$.

We know that $m = O(poly(N))$ therefore $m < 2^N$ and $\widetilde{S}_1, \ldots, \widetilde{S}_m$ do not span the whole $L_X$. It means that there exists index $l$ such that $x_l$ does not lie in a linear span of $\widetilde{S}_1, \ldots, \widetilde{S}_m$.

Now let's consider one more set of indices $1 \leq t_1 < \ldots < t_r \leq 2^N$ and corresponding sum $\widetilde{S} = \sum_{i=1}^{r}x_{t_i}$. If $\widetilde{S}$ is linearly dependent of $\widetilde{S}_1, \ldots, \widetilde{S}_m$, then for any assignment of variables $\{x_1, \ldots x_{2^N}\}$ the value of sum $\widetilde{S}$ is uniquely determined by values of sums $\widetilde{S}_1, \ldots, \widetilde{S}_m$. On the other hand if $\widetilde{S}$ is linearly independent of $\widetilde{S}_1, \ldots, \widetilde{S}_m$ then for each $a \in \mathbb{R}$ there exists at least one assignment $p'\in L_X^{*}$ such that $p'(\widetilde{S}) = a$ and $\forall k \in \{1, \ldots, m\} \;p'(\widetilde{S}_k) = S_k$.

From all of the above, it follows that there exists an assignment $p'$ such that $p'(x_l) = max(a_1, \ldots, a_{2^N}) + 1$ and $\forall k \in \{1, \ldots, m\} \;p'(\widetilde{S}_k) = S_k$. But in this case our hypothetical algorithm will give the same answer as for the input $\{a_1, \ldots, a_{2^N}\}$ which is obviously incorrect.