A complexity proof for monotonic-pruning DP on a divisor set

Recently we encountered a difficult problem in computer science, but since it is very closely related to mathematics, I was unsure which board would be more appropriate. In the end I posted it here on the mathematics board. To make the problem easier to understand, I will give both a computer-science formulation, which is closer to the original problem and less abstract, and a mathematical formulation, which does not require any computer-science background.

Problem statement

Computer-science formulation

Let $m$ be a given positive integer. Define $S$ to be the set of all positive divisors of $m$:

$$ S=\{d\in\mathbb Z^+ : d\mid m\}. $$

Clearly, $1\in S$ and $m\in S$.

For any integer $x\in[0,m-1]$, we consider writing $x$ as a sum of elements from $S$, with repetition allowed. Define $f(x)$ to be the minimum number of elements needed. Since $1\in S$, $f(x)$ is always finite; we also define $f(0)=0$. Formally, if $T$ is a multiset whose elements all lie in $S$ and $\sum T_i=x$, then $f(x)$ is the minimum possible value of $|T|$.

A straightforward C++ implementation of $f$ is:

for (int i = 0; i < m; i++) {
    for (int j = 0; j < S.size() && i + S[j] < m; j++) {
        f[i + S[j]] = min(f[i + S[j]], f[i] + 1);
    }
}

The time complexity of this code is $O(m\times d(m))$, where $d(m)$ denotes the number of divisors of $m$, i.e. $d(m)=|S|$.

Now define $g(x)$ as follows: among all optimal representations of $x$ (that is, multisets of size $f(x)$), let $g(x)$ be the maximum possible value of the largest divisor appearing in the multiset. We also define $g(0)=0$. Formally, if $T$ is a multiset with elements in $S$, $\sum T_i=x$, and $|T|=f(x)$, then $g(x)$ is

$$ g(x)=\max \max_{d\in T} d, $$

where the outer maximum is taken over all optimal multisets $T$.

We noticed that during transitions, $g(x)$ can be used for pruning.

More precisely, when processing state $i$, there is no need to enumerate all of $S$; it is enough to enumerate those divisors $j\in S$ satisfying $j\ge g(i)$.

The core implementation is:

long long cnt_ops = 0;
sort(S.begin(), S.end());
for (int i = 0; i < m; ++i) {
    for (int j = g[i]; j < S.size() && i + S[j] < m; ++j) {
        cnt_ops++;
        if (f[i] + 1 < f[i + S[j]]) {
            f[i + S[j]] = f[i] + 1;
            g[i + S[j]] = j;
        } else if (f[i] + 1 == f[i + S[j]]) {
            g[i + S[j]] = max(g[i + S[j]], j);
        }
    }
}

We are interested in a sharp upper bound on the total number of iterations of the inner loop, i.e. on cnt_ops. Mathematically, this is equivalent to bounding

$$ \sum_{i=0}^{m-1}\sum_{j\in S}[j\ge g(i)\land i+j<m]. $$

The algorithm runs extremely fast, strongly suggesting that the total complexity is only $O(m)$ or $O(m\log\log m)$. However, giving a rigorous proof appears very difficult. We tested all integers $m\le 10^7$ with $m\times d(m)\ge 5\times 10^8$, and the maximum value of cnt_ops was $41143829$, attained at $m=9979200$.

Mathematical formulation

Let $m$ be a given positive integer. Define $S$ to be the set of all positive divisors of $m$:

$$ S=\{d\in\mathbb Z^+ : d\mid m\}. $$

Clearly, $1\in S$ and $m\in S$.

For any integer $x\in[0,m-1]$, we consider writing $x$ as a sum of elements from $S$, with repetition allowed. Define:

1. $f(x)$: the minimum number of elements needed. Since $1\in S$, $f(x)$ is always finite; we also define $f(0)=0$. Formally, if $T$ is a multiset whose elements all lie in $S$ and $\sum T_i=x$, then $f(x)$ is the minimum possible value of $|T|$.

2. $g(x)$: the maximum possible value of the largest divisor appearing in the multiset. We also define $g(0)=0$. Formally, if $T$ is a multiset with elements in $S$, $\sum T_i=x$, and $|T|=f(x)$, then $g(x)$ is

   $$ g(x)=\max \max_{d\in T} d, $$

   where the outer maximum is taken over all optimal multisets $T$.

We want to bound

$$ \sum_{i=0}^{m-1}\sum_{j\in S}[j\ge g(i)\land i+j<m]. $$

We conjecture that this is $O(m)$ or perhaps $O(m\log\log m)$. However, giving a rigorous proof appears very difficult. We tested all integers $m\le 10^7$ with $m\times d(m)\ge 5\times 10^8$, and the maximum value of cnt_ops was $41143829$, attained at $m=9979200$.

What we have tried

Extending $S$ to an arbitrary set

We first tried to see whether, if we drop the number-theoretic restriction that $S$ must be a divisor set and merely assume that $S$ is an arbitrary set of positive integers containing $1$ and $n$, then an upper bound of the form $O(\operatorname{lcm}S+\sum S)$ might hold.

This conjecture is false. Hack by GPT:

Let $K\ge 3$, and define

$$ a=\operatorname{lcm}(1,2,\dots,K),\qquad n=a(a-1), $$

$$ S=\{1,\;a,\;n\}\cup\{t(a-1):2\le t\le K\}. $$

Clearly,

$$ \operatorname{lcm}(S)=n, $$

and

$$ \sum_{s\in S}s =1+a+n+\sum_{t=2}^{K}t(a-1) =O(n), $$

so

$$ \operatorname{lcm}(S)+\sum_{s\in S}s=O(n). $$

Now consider integers $i=qa+r$, where

$$ 1\le q\le a-2,\qquad 0\le r\le a-2-q. $$

The number of such integers is

$$ \frac{(a-1)(a-2)}{2}\ge \frac{n}{4} $$

for $a\ge 4$. All such $i$ satisfy $i<n$, so the element $n$ cannot be used.

Suppose we use $x$ copies of $1$, $y$ copies of $a$, and $z_t$ copies of $t(a-1)$. Let

$$ D=\sum t z_t,\qquad Z=\sum z_t. $$

Then

$$ i=x+ay+(a-1)D=a(y+D)+(x-D). $$

Comparing this with $i=qa+r$ (with $0\le r<a$), we obtain

$$ y+D=q+p,\qquad x-D=r-ap \qquad (p\in\mathbb Z). $$

If $p\ge 1$, then $D\ge ap-r$, and combining this with $D\le q+p$ gives

$$ ap-r\le q+p. $$

Since $q+r\le a-2$, this implies

$$ p(a-1)\le q+r\le a-2, $$

which is impossible. Hence $p\le 0$.

The number of element is

$$ x+y+Z =(D+r-ap)+(q+p-D)+Z =q+r+Z-p(a-1) \ge q+r, $$

with equality only when $p=0$ and $Z=0$. In that case $y=q$ and $x=r$, so the optimal solution uses only $1$ and $a$, and therefore $g(i)=a$.

For each such $i$, we have $g(i)=a$, and there are $K+1$ elements of $S$ that are at least $a$. Therefore the left-hand side satisfies

$$ \ge (K+1)\cdot\frac{n}{4}. $$

Hence

$$ \frac{\text{left-hand side}} {\operatorname{lcm}(S)+\sum_{s\in S}s} \ge \frac{(K+1)n/4}{4n} = \frac{K+1}{16}. $$

Since

$$ a=\operatorname{lcm}(1,2,\dots,K) $$

satisfies

$$ \log a=\Theta(K), $$

this counterexample in fact yields

$$ \text{left-hand side} = \Omega\!\bigl( \operatorname{lcm}(S)\log \operatorname{lcm}(S) \bigr). $$

Therefore, the assumption that $S$ is a divisor set appears to be essential; the phenomenon does not persist for arbitrary sets $S$.

Question

Can one prove a nontrivial upper bound for

$$ \sum_{i=0}^{m-1}\sum_{j\in S}[j\ge g(i)\land i+j<m] $$

when $S$ is the full divisor set of $m$?

Is it possible to show that this quantity is always $O(m)$, $O(m\log\log m)$, or at least $o(m\times d(m))$?