One of the key principles of parametric optimization is that, when you are faced with optimizing the nonlinear combination of two linear values (sums of element weights, costs, etc) you should instead look at the set of optima for all possible linear combinations of the same two values. Let's see how this applies to the number-theoretic knapsack problems I posted about earlier this week.

In the knapsack problem, we are trying to optimize the total profit of a subset of the given elements, subject to the condition that their total size is at most a given threshold. This can be expressed as a nonlinear combination of these two linear values in which the function of profit and size is the identity function on profit when the size is small enough and zero otherwise. This isn't the nice sort of quasiconvex function that parametric methods are best-suited for, but the fractional knapsack problem instead involves a greedy algorithm for maximizing the profit/size ratio, and this sort of ratio is quasiconvex. So in any case, following the parametric approach, let's replace both of these nonlinear combinations by the linear combination profit − \( \lambda \)·size, let the parameter \( \lambda \) vary, and see what solutions we get.

For any particular value of \( \lambda, \) the answer is very simple: the optimal solutions are the ones that take all elements for which profit/size\( {}\gt\lambda \) (the ones that make a positive contribution to the solution value), and any subset of the elements for which profit/size\( {}=\lambda \) (the ones whose contribution is zero). The smallest-size optimal solution is the one that takes only the elements for which profit/size\( {}\gt\lambda. \) So the set of all smallest-size optimal solutions is almost exactly the same as the set of solutions generated by the greedy algorithm that adds one element at a time in order by the profit/size ratio. To make this algorithm generate exactly the smallest-size optimal solutions, we need to modify it so that when there are ties in profit/size ratio it adds all tied elements at once rather than adding them one at a time. When the set of profit/size values is discrete (as it is in our problems) this set of solutions also has the property that each solution is the unique optimal solution for a nonempty range of parameter values.

Now suppose we go back to the number-theoretic sequences that I started with (the highly abundant numbers and the highly composite numbers), expand out the definition of the profit and size functions in the parametric optimization functions profit − \( \lambda \)·size, and eliminate the logs in these functions by exponentiating. Then the sequence of smallest-size optimal solutions for these objective functions are exactly how the colossally abundant numbers and superior highly composite numbers are defined. That is, it is no coincidence that starting with the knapsack-problem formulations of the highly abundant and highly composite numbers, and then applying the greedy algorithm to the resulting knapsack problems, gave these other two sequences: it falls out directly from the parametric analysis above and the definitions of these sequences.

However, OEIS states that the correctness of the generation algorithm for the successive factors of the colossally abundant numbers is still conjectural rather than proven. How can this be, when we have seen above that the greedy algorithm always works for sequences like this? The part that must still be unknown concerns the possibility of ties: is it ever possible for two or more knapsack elements to have the same profit/cost ratio? If so we must take both or all of them at once rather than letting them be chosen one at a time. And this is problematic from the algorithmic point of view because it involves testing complicated expressions involving logarithms for exact equality.

Specifically, in the highly abundant number version of the problem, we need to know whether there can exist two prime powers \( p^i \) with the same value of the expression \[ \log_p\frac{p^{i+1}-1}{p^i-1}. \] In the highly composite number version of the problem, we need to know whether there can exist two prime powers with the same value of the expression \[ \log_p\frac{i+1}{i}. \] In both cases, it seems unlikely, but obviously that's not a proof. More generally, Alaoglu and Erdős conjectured in 1944 (in connection with this problem) that two expressions \( \log_p q \) with different prime bases and rational arguments can only be equal if they're both integers, but (although it is known that there can be no three-way ties) this remains unproven.