Hey there, let's work through your problem systematically—you're closer than you think! Let's break down the key insights and actionable steps to solve this stably within your complexity constraints.

核心问题转化：从有理函数到多项式求根 #

First, let's clarify your goal: you need the minimum value of (c_k) such that the Taylor expansion (TE(x) = 0) has a real root. You've already isolated (c_k) as a rational function of (x):
[c_k(x) = \frac{\sum_{j \neq k} c_j x^j}{xk}]
(Quick note: technically, from (TE(x)=0), this should be (c_k(x) = -\frac{\sum_{j \neq k} c_j x^j}{xk})—don't forget the negative sign! It won't change the method, just the final sign of your minimum value.)

The critical realization here is that finding the global minimum of this rational function doesn't require working with rational function derivatives directly. Let's define (P(x) = \sum_{j \neq k} c_j x^j) (a fully known polynomial, since all (c_j \neq c_k) are given). Then (c_k(x) = \frac{P(x)}{x^k}). Using the quotient rule to compute its derivative:
[c_k'(x) = \frac{P'(x)x^k - P(x) \cdot k x^{k-1}}{x{2k}}]
For the derivative to be zero (critical points), the numerator must be zero (denominator is non-zero since (x \neq 0) is required for (c_k(x)) to be defined). Simplify the numerator:
[x P'(x) - k P(x) = 0]
This is a polynomial equation! Let's call this polynomial (R(x)):
[R(x) = \sum_{j \neq k} (j - k) c_j x^j]
All coefficients of (R(x)) are known (since you have every (c_j) except (c_k)), so now your problem reduces to finding all real roots of (R(x))—way more manageable!

稳定高效的多项式实根求解：VCA算法 #

You mentioned the Vincent-Collins-Akritas (VCA) algorithm, which is perfect here. VCA is a deterministic, interval-based method built on Budan's Theorem that finds all real roots of a polynomial with O(n log n) time complexity (specifically (O(n \log (B/\epsilon))), where (B) is an upper bound on root magnitudes and (\epsilon) is your desired precision). This is well within your quadratic time limit.

How VCA works in practice:

• Set root bounds: Use a simple rule like Cauchy's Bound to find an interval ([-B, B]) that contains all real roots of (R(x)). Cauchy's Bound says (B = 1 + \max\left(\frac{|c_j|}{|c_n|}\right)) where (c_n) is the highest-degree coefficient of (R(x)).
• Interval subdivision: Use Budan's Theorem to count how many real roots lie in each subinterval. If an interval has exactly one root, narrow it down using bisection or linear fractional transformations until you reach your desired precision. If it has multiple roots, split it further.
• Collect all roots: The algorithm will systematically find every real root without missing any, unlike Newton's method which can diverge or skip roots depending on initial guesses.

计算全局最小值 #

Once you have all real roots of (R(x)) (these are the critical points of (c_k(x))), do the following:

1. Evaluate (c_k(x)) at each critical point: Plug each root (x^) into (c_k(x) = \frac{P(x^*)}{(x)^k}) to get the corresponding (c_k) value.
2. Check asymptotic limits: Don't forget to evaluate the behavior of (c_k(x)) as (x \to +\infty) and (x \to -\infty):
   • If (n - k > 0): The leading term of (c_k(x)) is (c_n x^{n-k}). The limit depends on the sign of (c_n) and whether (n-k) is even/odd.
   • If (n - k < 0): (c_k(x) \to 0) as (x \to \pm\infty).
   • If (n - k = 0): (c_k(x)) approaches (c_n) as (x \to \pm\infty).
3. Find the minimum value: Compare all critical point values and asymptotic limits—the smallest one is your answer for the minimum (c_k).

额外注意事项 #

• Exclude (x=0): (c_k(x)) is undefined at (x=0) (either division by zero or a non-real value if (k) is negative), so you can ignore this point entirely.
• Monotonic edge case: If (R(x)) has no real roots, (c_k(x)) is strictly monotonic. In this case, the minimum will be one of the asymptotic limits.
• Precision handling: If you're working with floating-point coefficients, use interval arithmetic alongside VCA to avoid missing roots due to numerical errors.

备注：内容来源于stack exchange，提问作者keshav