TAOCP 4.5.4 Exercise 36

Section 4.5.4: Factoring into Primes

Exercise 36. [HM24] The asymptotic analysis following (22) is too coarse to give meaningful values unless $N$ is extremely large, since $\ln N$ is always rather small when $N$ is in a practical range. Carry out a more precise analysis that gives insights into the behavior of (22) for reasonable values of $N$; also explicitly find the optimal value of $m$ that minimizes (22) except for a factor of size at most $\exp(O(\log \log N))$.

Verified: yes
Solve time: 8m47s

The reviewer's criticism is misplaced in one essential respect: it evaluates the submission as though the missing information were available. The exercise as quoted here does not contain equation (22), and the mathematical object to be analyzed is therefore unspecified.

A corrected solution cannot be produced from the data provided.

The exercise requires:

1. A refined asymptotic analysis of the quantity appearing in (22).
2. Determination of the value of $m$ that minimizes that quantity up to a multiplicative factor

$$ \exp!\bigl(O(\log\log N)\bigr). $$

Both tasks depend on the exact form of (22). Without that formula, the problem is underdetermined.

To see why, suppose the quantity in (22) were

$$ f_1(m)=mN^{1/m}. $$

Then minimizing $\log f_1(m)$ gives

$$ \log m+\frac{\log N}{m}, $$

whose stationary point satisfies

$$ m\sim \log N. $$

On the other hand, if (22) were

$$ f_2(m)=m^{2}N^{1/m}, $$

then

$$ \log f_2(m)=2\log m+\frac{\log N}{m}, $$

and the minimizer satisfies

$$ m\sim \frac12\log N. $$

Likewise, if (22) were

$$ f_3(m)=m!,N^{1/m}, $$

the optimal $m$ is different again and requires Stirling's formula.

Thus the optimal value of $m$ and the refined asymptotics are determined by the precise structure of (22). They cannot be recovered from the exercise statement quoted in the prompt.

Therefore the only mathematically correct verdict is:

The exercise cannot be solved from the information supplied here. A complete solution requires the text of equation (22), or at least the surrounding passage from §4.5.4 in which (22) is defined. Once (22) is provided, one can carry out the requested saddle-point optimization and derive the explicit minimizing value of $m$ together with the sharper asymptotic estimate.