Skip to main content
3 of 3
edited tags
YCor
  • 63.9k
  • 5
  • 187
  • 286

Minimizing a ratio related to scalar subset sums

Let $a = (a_1, a_2, \cdots, a_n)$ be non-zero real numbers. Let $[n] = \{1,2,\cdots,n\}$ be a set of indices. Define the maximum absolute subset sum of the array $a$ as: $$\mathrm{MASS}(a) = \max_{T \subseteq [n]} \big\lvert \sum_{i \in T} a_i \big\rvert.$$ Meanwhile, define its average absolute subset sum as: $$\mathrm{AASS}(a) = \frac{1}{2^n} \sum_{T \subseteq [n]} \big\lvert \sum_{i \in T} a_i \big\rvert.$$

Now I am looking for the following quantity given any array size $n \ge 1$: $$R_n = \min_{a \in (\mathbb{R}/\{0\})^n} \frac{\mathrm{AASS}(a)}{\mathrm{MASS}(a)}.$$


Motivation: Somehow related to estimating the smoothness of neural networks, and if provable, a lemma that may lead to more interesting corollaries.

Example: It can be verified that $R_3 = 3/8$, where one assignment of $a$ that obtains the minimum can be $a = (\frac{1}{2}, \frac{1}{2}, -\frac{1}{2})$, so that $\mathrm{MASS}(a) = 1$ and $\mathrm{AASS}(a) = 3/8$.

Observation:

  • The order of elements in array $a$ does not matter (thus $a$ should perhaps be treated as a multiset instead...)
  • $R_4 = 3/8$, minimum obtained when $a=(\frac{c}{2}, \frac{c}{2}, -\frac{c}{3}, -\frac{c}{3})$ or $a=(\frac{c}{3}, \frac{c}{3}, \frac{c}{3}, -\frac{c}{2})$ for any non-zero real number $c$.
  • $R_5 = 5/16$, minimum obtained when $a=(\frac{c}{3}, \frac{c}{3}, \frac{c}{3}, -\frac{c}{3}, -\frac{c}{3})$ for any non-zero real number $c$.

Conjecture: For any $n \ge 1$, denote $n_+ = \lceil n/2 \rceil$ and $n_- = n - n_+$. The minimum ratio of AASS and MASS is obtained e.g. when $a$ consists of $n_+$ elements each being $\frac{1}{n_+}$ and $n_-$ elements each being $-\frac{1}{1+n_-}$.


Question:

  1. Could we prove or disprove this conjecture? If the conjecture turns out wrong, could you correct it?
  2. Does $R_n$ have a closed-form expression?
  3. For more general cases, given a monotonically-increasing weight function $\phi: [0,+\infty) \rightarrow [0,+\infty)$, we define weighted average absolute subset sum as $$\mathrm{WAASS}_\phi(a) = \frac{\sum_{T \subseteq [n]} \phi(\big\lvert \sum_{i \in T} a_i \big\rvert) \cdot \big\lvert \sum_{i \in T} a_i \big\rvert}{\sum_{T \subseteq [n]} \phi(\big\lvert \sum_{i \in T} a_i \big\rvert)}.$$ Does the assignment of $a$ described in the conjecture still yield a minimum ratio of WAASS and MASS and why (not)?

It's my first time posting, so I apologize if I was not making things clear. Also, any typo corrections/advice is welcome.

Nango
  • 11
  • 2