{'fraction_non_alphanumeric': 0.046262254901960786, 'fraction_numerical': 0.012561274509803922, 'mean_word_length': 3.717485549132948, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Newton's Method as a Formal Recurrence

Iterating Newton's method symbolically for the general quadratic yields a rational function, the numerator and denominator of which are polynomials with highly composite coefficients.


Introduction
If f : C → C is a differentiable function, then Newton's method, applied recursively to an initial value of z 0 , yields the sequence of values z 1 , z 2 , . . . defined as which, in many cases, converges to a root of f . We restrict our attention to the general quadratic f (x) = ax 2 + bx + c for the purposes of this paper. Instead of using equation (1) as a numerical method, we are interested in iterating symbolically by letting the initial guess be z 0 = x where x ∈ C. Doing so, we obtain where P n (x) and Q n (x) are relatively prime polynomials in C [x]. An interesting observation, pointed out to us by Jim Propp, is that the coefficients of these polynomials, though very large, have no prime factors ≥ 2 n . On his suggestion that this divisibility property might imply some combinatorial interpretation not immediately apparent in the formulation of equation (1), we have derived an explicit symbolic formula for each iterate. The aim of this paper is to show that the polynomials P n and Q n are given by the following explicit formulas: The binomial coefficients immediately explain the maximum size of the prime divisors of the coefficients of these polynomials. Furthermore, equation (2) provides a good starting point for investigating any combinatorial meaning of P n and Q n , which is discussed at the end of this paper.
Let C * denote the Riemann sphere C ∪ {∞}. A fractional linear transformation is a map β : C * → C * of the form β(τ ) = aτ + b cτ + d where a, b, c, d ∈ C and ad − bc = 0. This function is a conformal map which is analytic everywhere except the pole at τ = − d c . For our purposes, we define a particular fractional linear transformation ϕ(τ ) as where r 1 and r 2 are the two distinct roots of the quadratic polynomial f (x) = ax 2 + bx + c. This particular approach exploits the fact that Newton's method for quadratics (with distinct roots) is conjugate to z → z 2 , with respect to ϕ, the fractional linear transformation which sends the roots of the quadratic to 0 and ∞. Rick Kenyon [2] was the first to point this out to us; expositions can be found in both Cayley [1] and McMullen [3]. For distinct roots r 1 and r 2 , the fractional linear transformation ϕ −1 (τ ) exists and the formula from equation (1) can be expressed as That is, the following diagram of maps is commutative: Thus, the formula for the nth iterate of Newton's method is Using this formula, we shall prove the equations in (2).

Proof of Explicit Formula
Theorem 1. Given a quadratic polynomial f (x) = ax 2 + bx + c, with b 2 − 4ac = 0, define polynomials P n and Q n as follows.
Then the polynomials given in equation (5) are equal to those in equation (2) which are reproduced below.
Before we begin the proof of the theorem, we will need the following lemma.

Lemma 1.
For all x, y ∈ R, and all n ∈ N, n ≥ 1, the following identity holds Proof of Lemma 1. We proceed by induction. For n = 1, 2 the equality is easily verified, so assume the identity is valid for all k ≤ n. Let T (n) be the right-hand side of equation (7). Since we need only prove that Combining the sums on the right side of equation (8) by shifting indices, we have Applying Pascal's identity and bringing the leftmost term inside the sum, we obtain Finally, we note that for n ≥ 1 the binomial coefficient is 0 when i = n. Therefore, this last expression is equal to T (n + 1), and so we are done.
Proof of Theorem 1. Begin by expanding equation (5) via the binomial theorem to obtain We can now apply lemma (1) to the expressions of the form x n − y n in both P n and Q n . Doing so and canceling the factor of r 1 − r 2 (since b 2 − 4ac = 0) yields Replacing r 1 and r 2 with their values in terms of the coefficients a, b, c gives the final form These equations are the same as equations (2a) and (2b), which was to be proved.

Further Remarks
Though this paper does not discuss any combinatorial interpretation of the polynomials P n and Q n we suspect that their may be some fruitful combinatorial equivalence yet to be discovered. To aid further research in this area, we make a couple of observations about P n and Q n . Simply iterating Newton's method for the general quadratic gives where P 0 (x) = x and Q 0 (x) = 1 so that the initial term is z 0 = x as before. The question is whether the numerator and denominator of equation (9) are relatively prime so that we may define P n and Q n recursively in the natural way. This is, in fact, true as the following lemma proves.
(For the duration of the statement and proof of Lemma 2, we are suspending the definition of P n and Q n given earlier, but it will be an immediate consequence of Lemma 2 that the two definitions agree.) Proof. We proceed inductively by assuming that P i and Q i are relatively prime for all i ≤ n. Assume P n+1 and Q n+1 are not relatively prime to derive a contradiction. Then there exists an irreducible polynomial α such that α | P n+1 and α | Q n+1 . If α | Q n , then, since α | aP 2 n −cQ 2 n , it follows that α | P n which contradicts the induction hypothesis that P n and Q n are relatively prime. Hence α | Q n . Since α | 2aP n Q n + bQ 2 n , we know that α | 2aP n + bQ n . But then α | P n + b 2a Q n and also α | P n ± c a Q n . Consequently, α divides their difference, so α | b 2a ∓ c a Q n which only occurs when b 2 − 4ac = 0. In combinatorics it is sometimes useful to consider two formal variables x, y which do not commute with each other but instead obey yx = qxy where q is another formal variable that commutes with both x and y. This approach, due to Schützenberger [4], is useful in applications such as counting lattice paths. In our case, the polynomials P n and Q n can be easily generalized to the non-commuting case. As a generalization of the usual binomial coefficient, the q-binomial coefficient is defined as 1 − q i+k 1 − q i and the following q-binomial theorem for non-commuting variables x, y due to Schützenberger [4] is (x + y) n = n k=0 n k q x k y n−k Analogously to the above, we can then define non-commuting polynomials P ′ n and Q ′ n recursively as where P ′ 0 = x, Q ′ 0 = y, and yx = qxy. We conjecture explicit formulas for both P ′ n and Q ′ n which happen to be the same as equations (2a) and (2b) except for the presence of a q-binomial coefficient: