# Finding maximum via sum oracle

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?

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.