PaperlayerView exact revision on arXiv

Source-linked AI summary

A Complete Resolution of Forsythe's Conjecture for Restarted Conjugate Gradients

Matthew J. Colbrook, George Stepaniants, Alex Townsend

arXiv:2609.04659v1math.NAmath.DSmath.OC

TL;DR

The unresolved question is whether restarted CG residual directions converge separately on even and odd restart subsequences, which norm-decay estimates do not generally determine. The proof uses a certified transverse Hopf point at s=4, analytic periodic-orbit and shadowing arguments, and degree elevation to extend counterexamples to larger s. For s=2,3, every instance either terminates or has unit vectors ye and yo; for each s≥4, some diagonal positive definite matrix in dimension s+4 yields nontermination and nonconvergent (y2k).

  • Problem

    The unresolved question is whether restarted CG residual directions converge separately on even and odd restart subsequences, which norm-decay estimates do not generally determine.

    Source: §1 · pp. 2–3

  • Method

    The proof uses a certified transverse Hopf point at s=4, analytic periodic-orbit and shadowing arguments, and degree elevation to extend counterexamples to larger s.

    Source: §1 · p. 4

  • Results

    For s=2,3, every instance either terminates or has unit vectors ye and yo; for each s≥4, some diagonal positive definite matrix in dimension s+4 yields nontermination and nonconvergent (y2k).

    Source: §1 · p. 3

  • Takeaways & Limitations

    The universal termination-or-two-cycle conclusion holds exactly for restart lengths s∈{1,2,3}, and fails for every s≥4.

    Source: §1 · p. 2

    The spectral-core analysis excludes the already-terminated case r0=0 and retains only distinct eigenvalues with nonzero initial-residual projection.

    Source: The degree-independent spectral core · p. 6

Abstract

from arXiv · show

Forsythe's conjecture, published in 1968, asserts that for each restart length $s$, every exact-arithmetic restarted conjugate-gradient iteration on a real symmetric positive definite problem either terminates or has normalised residuals that converge separately along the even and odd restart subsequences. Apart from the classical steepest-descent case, this asymptotic question remained unresolved in full generality for nearly six decades. We give a complete classification by restart length in the original finite-dimensional setting and identify a sharp threshold. For $s=2$ and $s=3$, every problem either terminates or has convergent even and odd residual directions. For every $s\ge4$, there is a diagonal positive definite counterexample of dimension $s+4$ which never terminates and whose even residual directions do not converge. Together with Akaike's theorem for $s=1$, this shows that the conjectured universal conclusion is true precisely for $s\in\{1,2,3\}$ and false for every $s\ge4$. The positive results follow from a degree-independent double-orthogonality identity and an analysis of the low-degree fixed-point sets. At restart length four, rational interval arithmetic and Sturm sequences certify a transverse Hopf point of the leading vector field of the rescaled squared-weight map. Analytic periodic-orbit and shadowing arguments yield the counterexample at restart length four, and degree elevation extends the construction to every larger restart length.

1. Introduction

The paper classifies restarted conjugate-gradient residual directions by restart length, establishing a sharp threshold at s = 4. A degree-independent spectral argument underpins the positive cases, while a Hopf mechanism constructs counterexamples from s = 4 onward.

1. Introduction

  • For s = 1, 2, and 3, every instance terminates or has convergent even and odd residual directions; for each s ≥ 4, a diagonal SPD example of dimension s + 4 never terminates and has divergent even directions.The s = 1 result is Akaike’s theorem [FM51, Aka59].Source: §1 · pp. 2–3
  • Fixed-length restarting induces nonlinear dynamics of the normalized residual direction, which classical convergence estimates for residual norms do not determine.Source: §1 · p. 3
  • For s = 2 and 3, low-degree rigidity rules out sustained motion along two-cycle families; the proofs use logarithmic balance laws and control of transverse and neutral modes.For s = 2, a uniform endpoint retraction gives finite parameter variation; for s = 3, the limiting support has four, five, or six nodes.Source: §1 · pp. 3–4
  • At s = 4, a transverse Hopf point creates a periodic profile in the leading rescaled dynamics, which an exact restarted-CG orbit shadows; degree elevation extends the construction to every s ≥ 4.Only the finite inequalities at s = 4 are computer-certified; the periodic-orbit, shadowing, and degree-elevation arguments are analytic.Source: §1 · p. 4

AI-assistance

  • The authors describe using ChatGPT with GPT-5.6 over several weeks, checking proposed arguments themselves and developing the s = 2 and s = 3 proofs before identifying the higher-degree oscillatory obstruction.That discussion led to the s = 4 Hopf construction and shadowing argument.Source: AI-assistance · p. 5

The degree-independent spectral core

  • A monotone two-block energy and a double-orthogonality identity yield convergent even and odd orthogonal factors and confine every limit to resonant support of between s + 1 and 2s nodes.This reduces convergence to motion within the corresponding fixed set of the two-block map.Source: The degree-independent spectral core · pp. 7–9

Part A. Convergence at restart length two

At restart length two, the support bound restricts accumulation points to three or four nodes. Three-node points are rigid, while four-node points form a compact one-parameter family of exact two-cycles.

Part A. Convergence at restart length two

  • Convergence at restart length two reduces to controlling motion along the compact family of four-node exact two-cycles, since three-node accumulation points are rigid.The support bound leaves only three- and four-node accumulation points.Source: Part A. Convergence at restart length… · p. 9

A.1. The theorem for restart length two and the spectral map … Part B. Convergence at restart length three

This section develops the convergence analysis for restarted conjugate gradients at restart lengths two and three. For length two, it proves convergence of even and odd normalized residual directions unless the run terminates, and then outlines the external-mode and boundary-stratum analysis for length three.

A.1. The theorem for restart length two and the spectral map

  • At restart length two, every run terminates or its normalized residual directions converge separately on even and odd indices; a block terminates only on support of at most two nodes.The spectral reduction confines each repeated eigenspace to the line generated by its initial projection, and the weight map preserves zero coordinates.Source: §A.1 · pp. 9–11

A.2. Energy, spectral localisation, and polynomial convergence

  • A monotone block energy and summable same-parity displacement yield convergent parity factors, while every ω-limit support lies in a resonant spectral set of at most four nodes.Limit supports have three or four nodes, and the support bound leaves a rigid three-node case or a one-parameter family of four-node two-cycles.Source: §A.2 · pp. 11, 13

A.3. Three- and four-node limiting geometry

  • Three-node limiting weights are uniquely determined by their support and quadratic, forcing parity convergence; four-node limits instead lie on paired segments of exact two-cycles.In the four-node case, convergence requires the orbit to approach a single point on its limiting segment.Source: §A.3 · pp. 13–15

A.4. Dynamics on the four-node family

  • On the four-node family, the defect c_k determines parameter drift through α_{k+1}−α_k=c_kR(α_k) and enters the polynomial relation q_k=R+H_{k+1}+c_kK_{α_k}.The section introduces a divided-difference transport law for the defect to control its sign.Source: §A.4 · pp. 15–16
  • On the resonant four-node face, exact-map identities control the dynamics, while estimates on external perturbations preserve the drift orientation near three-node endpoints.The identities provide a relative neighbourhood with positivity and bounded first derivatives; the perturbation estimates control influence uniformly at the endpoints.Source: §A.4 · p. 16

A.5. External modes and convergence of the weights

  • External coordinates with multiplier −1 are annihilated after finitely many blocks; every external coordinate that survives forever decays geometrically.The surviving coordinates have |ρλ| < 1, yielding a uniform geometric estimate after taking the maximum over the finitely many nodes.Source: §A.5 · pp. 17–18

A.6. Signed recovery and proof of the theorem for restart length two

  • Both parity weight sequences converge in the four-node case, and signed recovery yields convergent normalised residual directions in the original eigenbasis.Coordinates with positive limiting weights have eventually constant signs; coordinates with vanishing weights tend to zero. The argument also covers repeated eigenvalues and initially absent spectral components.Source: §A.5 · pp. 19–20, §A.6 · p. 20

Part B. Convergence at restart length three

  • For restart length three, limiting cubics determine a monic sextic, and stable, unstable, and neutral external coordinates require distinct treatments across the boundary strata.Stable coordinates use shadowing, unstable coordinates disappear after finitely many returns, and neutral coordinates are governed by logarithmic cocycles on five- and six-node strata.Source: Part B. Convergence at restart length… · p. 20

B.1. The theorem for restart length three · B.2. Spectral reduction and the signed residual map

For restart length three, every exact iteration either terminates or has separately convergent even and odd residual directions. The spectral reduction represents the iteration through active eigenvalue weights and signs, enabling analysis of termination and parity convergence.

B.1. The theorem for restart length three

  • At restart length three, every SPD problem either terminates or has even and odd residual directions converging separately in Euclidean norm.Each restart step minimizes the A-norm error over x_k + K3(A, r_k).Source: §B.1 · p. 21

B.2. Spectral reduction and the signed residual map

  • Squared coordinates determine the monic orthogonal cubic, while coordinate signs recover the residual direction.The parity return is L^2, so the analysis studies squared spectral weights before recovering signs.Source: §B.2 · pp. 22, 24
  • The spectral reduction uses distinct eigenvalues with nonzero initial residual projections as active nodes; repeated eigenspaces contribute only their initial oriented residual lines.No direction orthogonal to the initial projection within a repeated eigenspace can later appear.Source: §B.2 · pp. 22–23
  • The residual grade equals the number of active nodes, and when that count exceeds three the exact block polynomial is uniquely determined by the degree-three Galerkin conditions.The proof uses independence of the Krylov vectors and positive definiteness of the associated bilinear form.Source: §B.2 · p. 23
  • A block terminates exactly when at most three active coordinates remain; any coordinate that becomes zero stays zero, so support loss is permanent.When more than three active nodes remain, termination is impossible for a degree-at-most-three residual polynomial normalized to one at zero.Source: §B.2 · p. 23
  • For weights on at least four positive nodes, the monic orthogonal cubic has three simple positive roots, at least three sign changes across active nodes, and a negative value at zero.This sign structure identifies the normalized cubic with the block residual polynomial and yields the signed residual map F(y) = −L(y), F^2(y) = L^2(y).Source: §B.2 · pp. 23–24

B.3. Parity energy and ω-limit sets

For the s = 3 parity return, finite quadratic energy and support separation constrain the orbit’s ω-limit states. Those states localize to connected sets of exact signed two-cycles, with phase rigidity ruling out merely projective cycles.

B.3. Parity energy and ω-limit sets

  • Along every nonterminating orbit, the two interlaced monic-cubic norm sequences increase to a common positive limit and satisfy finite quadratic energy.Source: §B.3 · pp. 24–25
  • Every ω-limit state has at least four positive coordinates, and the degree-three moment Gram matrix is uniformly nonsingular on the orbit closure.Source: §B.3 · p. 25
  • Each parity ω-limit state has four to six positive coordinates; paired accumulation points form exact signed two-cycles, and both parity and paired ω-limit sets are compact and connected.Source: §B.3 · pp. 25–26
  • For positive weights on a common support related mutually by T, phase rigidity makes every signed lift an exact signed two-cycle, not merely a projective one.Source: §B.3 · p. 26

B.4. Algebra of fixed two-cycles and collision coordinates

The section analyzes fixed two-cycles and their fixed strata through quadratic completion and collision coordinates, extending the descriptions across support losses and boundary strata. It establishes drift and energy control, uniform local bounds near collision and boundary configurations, and symbolic-power properties of the associated algebraic sets.

Lemma B.4.1

  • Each regular fixed state has a monic quadratic completion polynomial Ω=K_JΛ_J, with coordinates that remain regular when nodes are lost or P and Q share a root.For six ordered nodes, Ω=(t−ρ)(t−σ) with (ρ,σ) in [λ2,λ3]×[λ4,λ5]; the rectangle interior, edges, and corners correspond to six, five, and four positive weights.Source: §B.4 · pp. 26–27

Lemma B.4.2

  • Near a coprime fixed component, the affine normal has quadratic leading drift, and both quadratic-root normal coefficients are strictly positive, including their limits at common-factor collisions.The root-normal formulas have finite, strictly positive limits as collisions are approached.Source: §B.4 · pp. 28, 29, 32
  • A signed two-block return is characterized exactly by the sextic identity PQ=D+H0, with equal squared monic norms at the two phases.Conversely, the identity implies the affine normal U vanishes, giving the exact fixed-cycle equivalence.Source: §B.4 · p. 29

Lemma B.4.3

  • Common-root collisions on positive six-node fixed sets occur off-node at nondegenerate critical points of D, and the fixed ideal is a radical complete intersection.The positive quadratic norm gain extends through every simple or simultaneous collision.Source: §B.4 · p. 32
  • The union of adjacent five- and six-node fixed strata at one omitted +1-multiplier node has a radical complete-intersection ideal.The collision coordinates use a signed amplitude for the omitted node.Source: §B.4 · pp. 32–33

B.4. Algebra of fixed two-cycles and collision coordinates

  • The fixed-stratum union ideals are radical, and their symbolic powers equal their ordinary powers.The real-analytic assertions follow by faithfully flat complexification and descent.Source: §B.4 · pp. 33, 35, 36, 37
  • Three simultaneous off-node collisions produce four factor-allocation branches; the triple-collision ideal is a radical complete intersection.One and two simultaneous collisions yield one and two branches, respectively; the branches have height two.Source: §B.4 · p. 34

Lemma B.4.4. Energy control of the completion polynomial

  • On compact regular neighborhoods of four-, five-, or six-node fixed points, the norm gain and same-parity chord are coercive in the squared fixed-ideal distance.The positive-definite quadratic control extends to simultaneous collisions through equality of symbolic and ordinary powers.Source: §B.4 · pp. 35, 37

B.4. Algebra of fixed two-cycles and collision coordinates

  • With one or two omitted +1 nodes, the signed fixed quotients are reduced, and the union ideals are I1 = (A, xη) and I2 = (xηα, yηβ).Each has height two and is a complete intersection; the two-loss chart has four codimension-two component ideals.Source: §B.4 · p. 36

Lemma B.4.4. Energy control of the completion polynomial

  • At four nodes, the return map is exactly the identity; on the five-node fixed component, its first return changes only the pivot and fixes the completion.The five-node fixed set is a reduced principal complete intersection.Source: §B.4 · pp. 38–39

B.4. Algebra of fixed two-cycles and collision coordinates

  • The symbolic-square assertion holds on all four components, with completion coefficients in the localized square at each minimal prime.At the four-node prime the coefficients are even in x and y; the other component cases use absent-amplitude derivatives, a support-five θ-shear, or the six-node tangent return with completion D.Source: §B.4 · p. 40
  • The matrix M has a uniformly invertible diagonal limit, and bounded estimates persist through off-node collisions and analytic chart overlaps.The perturbation bound depends only on |xy|, so it remains uniform as x^2/y^2 tends to zero or infinity; overlap changes have unit determinant and uniformly bounded derivatives and inverses.Source: §B.4 · pp. 40–41
  • Retained even polynomials change by O(x^2), while deleting a positive active coordinate makes the point nonfixed and bounds the completion drift.The nonfixed case has ||GY − Y|| ≥ δ > 0 on a small neighbourhood.Source: §B.4 · p. 41
  • A finite subcover of the compact collision and boundary strata, with finitely many node patterns, yields uniform constants in (B.4.24).The proof takes the largest upper bound and smallest positive lower bound among the finite cover.Source: §B.4 · p. 41

B.5. Convergence of the completion polynomial and external modes

The cubic orbit has a limiting completion polynomial whose roots contain every active node of an ω-limit state, while off-completion coordinates fall into stable, unstable, or neutral modes. When a neutral mode persists, the normalized core’s radial and normal deviations are controlled by the parity-energy tail.

B.5. Convergence of the completion polynomial and external modes

  • The completion polynomials converge to monic D*, P*, and Q* with P*Q* = D* + C*, and every active limiting node is a root of D*, which has at most six roots.The coefficient and factor-product errors are bounded by C(τ − ean); ω-limit states have at least four active nodes.Source: §B.5 · pp. 42–43
  • Off-completion coordinates with |mj| < 1 decay exponentially, those with |mj| > 1 are eventually deleted, and neutral coordinates have mj = −1.If a neutral coordinate persists, total stable weight is o(Eneu,n), and stable weight decays exponentially.Source: §B.5 · pp. 43–44
  • With a persistent neutral mode, the normalized core satisfies xn < 0, cXn ≤ −xn ≤ CXn, and |xn| + ∥Un∥ ≤ CXn.Persistent neutral weights are O(Xn^2), while total external weight is O(Xn^2) after unstable modes are deleted.Source: §B.5 · pp. 44–45
  • On compact regular signed charts, the normalized-core maps are analytic in core coordinates and external weights, including at factor collisions and support incidences.External-coordinate derivatives are uniformly bounded but are not generally O(E); their nonzero values at E = 0 are the Uvarov derivatives.Source: §B.5 · p. 45

B.6. Intrinsic convergence and removal of stable modes

This section establishes convergence of the six-node limiting dynamics, including through collisions and support loss, and constructs a positive orbit on an invariant coordinate face. It also shows that stable modes can be removed by shadowing and are negligible relative to persistent neutral modes in the reduced recurrence.

B.6. Intrinsic convergence and removal of stable modes

  • On the six-node limiting face, the squared parity state converges to one point, including through simple or simultaneous off-node root collisions and one or two weights tending to zero.The result assumes no external forcing; if a weight becomes exactly zero, the remaining tail lies on an invariant lower-support face.Source: §B.6 · pp. 46, 50
  • Strict normal drift makes each normal coordinate either remain negative or cross once into the nonnegative half-line, while the root increments have uniformly signed leading coefficients.These bounds yield summable variation and convergence of the root coordinates, then of the limiting polynomial and core weights.Source: §B.6 · pp. 48–50
  • If every surviving external mode is stable, the full tail is exponentially close to an exact positive-weight orbit on the invariant face; with persistent neutral modes, stable forcing is o(Eneu,n).Deleting stable weights changes analytic quantities by O(sum of stable signed amplitudes), or O(Est,n) for quantities even in each deleted amplitude; both errors are o(Eneu,n) when neutral modes persist.Source: §B.6 · p. 50
  • On six- and five-node fixed components, the derivative is the identity plus a nilpotent map from a normal direction into the fixed tangent, while on four-node components the squared return is the identity.The nilpotence identity extends across support incidences and factor collisions, enabling a uniform derivative bound for the shadowing construction.Source: §B.6 · pp. 50–52
  • Substitution into the defining equation for Ψ_n proves the exact recurrence χ̄_{n+1} = f(χ̄_n).Source: §B.6 · p. 53
  • The shadowing construction yields a positive orbit on an invariant coordinate face, with total mass one and supports that avoid termination.Coordinate faces are invariant under the restricted return map.Source: §B.6 · pp. 53–54
  • When a neutral external weight persists, stable weights decay geometrically while the neutral weight’s successive ratio tends to one, yielding comparison bounds that are little-oh of total neutral forcing.The argument uses specified log-increments only after analytic boundary extensions; it makes no assertion about logarithms of vanishing coordinates.Source: §B.6 · p. 54
  • Unstable modes disappear, while stable modes remain in the exact recurrence but contribute o(E_neu,n) to analytic returned coordinates and O(E_st,n) to coordinates even in stable signed amplitudes.These comparisons reduce the problem to the normalised core on the invariant S*-face with persistent neutral modes retained explicitly.Source: §B.6 · p. 54

B.7. Four-node limits and five-node limits without persistent neutral modes

On four nodes, the exact two-block return is the identity and outside squared mass is summable. On five nodes without a persistent neutral mode, the pivot dynamics yield convergence of the squared parity state.

B.7. Four-node limits and five-node limits without persistent neutral modes

  • For five nodes without a persistent neutral mode, fixed states form a pivot-parametrized interval, and an orientation argument yields convergence along it.At either interval endpoint exactly one weight vanishes while the other four remain positive.Source: §B.7 · pp. 55–56
  • On four nodes, the exact signed—and therefore squared—two-block return is the identity, while summable outside mass yields convergence of all squared coordinates.The outside coordinates tend to zero.Source: §B.7 · p. 55
  • A nonterminating exact five-node tail with no external forcing has a convergent squared parity state.The pivot is bounded and converges; the norm, cubic factors, and each squared weight then converge, including at endpoint limits.Source: §B.7 · pp. 56, 59
  • For supports of at most five nodes with no persistent neutral external mode, the squared parity state converges.Unstable modes are deleted, and an exact orbit on the support face transfers its limit to the original tail.Source: §B.7 · p. 59

B.8. Neutral external modes at a five-node limit

This section analyzes five-node tails with persistent neutral external modes, characterizing their geometry and return behavior and establishing squared-weight limit behavior across neutral-node configurations, including root collisions, pivot endpoints, confluent completions, and exact deletion.

B.8. Neutral external modes at a five-node limit

  • No neutral external node lies in the pivot interval: the missing completion root α stays outside it, separated by a positive gap.The root lies in (λ1, λ5) but outside [ℓ, r], and P(h)Q(h) has opposite signs on the pivot interval and at a neutral external node.Source: §B.8 · p. 60
  • The unforced return has positive transverse quadratic curvature at the neutral root, with the coefficient extending through simple and simultaneous off-node collisions.The quadratic coefficient is expressed as cθ = Γα dθ|g|^3 > 0 and remains uniform at pivot endpoints and collisions.Source: §B.8 · pp. 61–64
  • The external affine completion response has endpoint signs sign Ah(ρ) = sign(h − ρ) and sign Ah(σ) = sign(σ − h).The distinct-root moment coefficient is finite, nonzero, and signed at both pivot endpoints.Source: §B.8 · p. 64
  • The cited identities give qh = 3P(h)kQ(·, h) and qout = 4P(h)kQ, preserving the distinct coefficients and the h-argument in the first expression.Source: §B.8 · p. 65
  • The neutral-source cancellation used in the external-mode argument is restricted to neutral sources; the corresponding general-source relation holds only when m_k ≠ 1.The conormal identity follows by equating derivatives that vanish on the fixed-component tangent space, and the external insertion response establishes (B.8.17b).Source: §B.8 · p. 68
  • If all persistent neutral modes lie on one side of the pivot interval, A crosses zero at most once and the pivot coordinate θ_n converges.When every neutral mode is on the pivot side of α, the transverse recurrence satisfies q⁺ − q ≤ −c(dθa² + E_neu), with q ≥ 0.Source: §B.8 · p. 68
  • The single-crossing proof uses a common neutral forcing sign to make a half-line invariant, while retaining stable modes in the exact recurrence.A uniformly coercive full-state parity chord and summable stable contributions support the convergence argument through endpoints and collisions.Source: §B.8 · pp. 69–70
  • For mixed neutral configurations, the distinct-root Lagrange cocycle cancels first-order intrinsic drift and has a uniform remainder through pivot endpoints and factor collisions.The stated remainder is bounded by C{(|x| + |e| + |a|)^2 + E}.Source: §B.8 · pp. 71–72
  • Stable-mass deletion bounds the extended log-increment, not the generally unbounded logarithm of S_h.Source: §B.8 · p. 73
  • Strict Lagrange or confluent log-increment estimates transfer from the stable-free comparison state to the exact full state.The stable modes contribute only o(E_neu,n) forcing, allowing the neutral-mode classification to apply to the exact recurrence.Source: §B.8 · pp. 74–75
  • Every five-node tail has a singleton squared-weight ω-limit set, covering persistent neutral modes, confluent roots, factor collisions, pivot endpoints, and exact deletion into a four-node face.If no exact deletion occurs, the pivot converges and every retained squared weight converges; exact deletion is treated separately.Source: §B.8 · pp. 75, 77
  • When neutral nodes straddle the pivot interval, their endpoint exponents have opposite signs, so the paired scalar selects exactly one possible pivot endpoint.The positional cases for neutral modes on either side of α are exhaustive; modes selecting opposite endpoints cannot both persist, while the surviving family fixes the pivot limit.Source: §B.8 · p. 76
  • After exact deletion of a pivot-endpoint coordinate, the remaining four-node map is the identity and every outside coordinate tends to zero.The retained squared weights therefore converge in the deleted-face case as well.Source: §B.8 · pp. 76–77

B.9. Neutral external modes at a six-node limit

This section analyzes neutral external-mode terms at a six-node limit using cancellation, endpoint signs and parity, a logarithmic neutral cocycle, and bounded-tail estimates to constrain completion roots. Persistent-neutral-mode tails have convergent roots except in two boundary cases, which are resolved by reduction to five-node faces.

B.9. Neutral external modes at a six-node limit

  • A logarithmic neutral cocycle constrains global accumulation, with its radial term dominating the exact full tail when neutral mass persists.Stable-mode forcing is negligible relative to persistent neutral mass.Source: §B.9 · pp. 77, 79
  • A persistent neutral external mode forces the completion roots with endpoint signs sign A_h(ρ) = sign(h − ρ) and sign A_h(σ) = sign(σ − h).These signs describe the local forcing of the root coordinates.Source: §B.9 · p. 77
  • Every six-node tail with a persistent neutral mode has convergent roots except an IL-mode with σ_n → λ5 or an IR-mode with ρ_n → λ2.The endpoint-sign classification makes these the only remaining boundary cases.Source: §B.9 · pp. 80–81
  • The two remaining boundary cases have convergent roots and squared core weights, uniformly through pivot endpoints, factor collisions, and exact deletion into a five-node face.This resolves the cases where the six-node coordinates meet five-node strata.Source: §B.9 · p. 81
  • The κvq increment cancels the vq2f2 term, endpoint parity contributes dθ to mixed a-terms, and neutral terms have a favourable sign while stable linear tails are absorbed into rn.Remaining terms are absorbed into dθa2 + Eneu or have a tail bound; the bound is incomplete in the supplied passage.Source: §B.9 · p. 83

Appendix B.A1.5.5 proves the energy estimate

The appendix derives an energy estimate from the exact full two-parity chord identity and completes the six-node analysis. Boundary dynamics and all possible support losses yield convergence of the squared weights.

Energy estimate

  • The energy estimate follows from the exact full two-parity chord identity, with E including neutral and stable external masses; this also gives uniformity at endpoints and collisions.Source: Appendix B · p. 83

Boundary reductions

  • At the upper boundary, persistent IL- or IM-modes select opposite endpoint limits for θ, and at least one IL-mode ensures θ converges in the residual case.If core coordinates are deleted, permanent deletion reduces the analysis to the five-node case or the four-node projection argument.Source: Appendix B · p. 84
  • The boundary reductions yield convergence of all six squared core weights, including any coordinate that vanishes only asymptotically.The proof uses convergence of P_n, Q_n, C_n, U_n → 0, and the recovery formula (B.6.42).Source: Appendix B · p. 84

Six-node completion

  • Every six-node completion tail has a singleton squared-weight ω-limit set, including neutral-mode cases and all possible exact support-loss chains.When no core coordinate is deleted during neutral analysis, all external weights tend to zero; three or more simultaneous deletions are excluded.Source: Appendix B · p. 85

B.10. Signed recovery, the opposite parity, and the original problem … B.A1.4. Divisibility, the single-crossing estimate, and root variation.

The section analyzes exact return-map behavior, including parity-specific residual directions for restart length three and the effect of those limits on the original SPD problem. It also gives boundary-crossing, finite-variation, and root-variation estimates under the stated neutral-node condition.

B.10. Signed recovery, the opposite parity, and the original problem

  • For every nonterminating restart-length-three orbit, even squared weights converge, yielding convergence of both signed parity residuals in the original SPD coordinates, including repeated eigenvalues, zero components, and permanent support loss.The proof handles limiting supports of four, five, or six nodes before recovering signed limits and transferring them through the fixed spectral isometry.Source: §B.10 · pp. 85–86

Appendix B. Exact algebra for Lemmas B.9.1–B.9.4

  • The appendix derives the six-node return calculations by combining Uvarov derivatives, residue identities, and boundary-stratum analysis, with collision continuation supported by analytic-germ identities and uniform C2 bounds.The calculations follow the order in which they are used: returned core, endpoint signs and logarithmic cocycle, then boundary strata.Source: Appendix B · p. 86

B.A1.2. Endpoint signs.

  • Endpoint-sign calculations prove B.9.5, while the intrinsic first-order variation of the two factors in J_h cancels, yielding a primitive for root variation and the exact logarithmic cocycle.The endpoint signs describe direct forcing of the two roots.Source: B.A1.2. Endpoint signs · pp. 89–90

B.A1.4. Divisibility, the single-crossing estimate, and root variation.

  • Signed amplitudes and analytic divisibility yield exact divided recurrences governing boundary-root approach, with positive coefficients on a sufficiently late tube.These recurrences are used in Lemma B.9.3.Source: B.A1.4. Divisibility, the… · pp. 91–92
  • If no persistent neutral node lies in IL, the exact return eventually leaves zρ ≥ 0 invariant, and negative zρ can cross into that half-space at most once.Persistent neutral nodes then satisfy h > ρ; on the boundary, their positive contribution is bounded below by a constant times Eneu, while stable-mode contributions are o(Eneu).Source: B.A1.4. Divisibility, the… · p. 92
  • The external energy estimate retains stable modes using the full-state chord, a limiting Gram matrix with positive external diagonal terms, and a uniform lower singular-value bound.The chord’s leading external component is (f M_h − 1)ξ_h e_h, and the normalised core’s dependence on ξ_h starts at E_h = ξ_h^2; the parity-chord identity is then applied.Source: B.A1.4. Divisibility, the… · p. 92
  • After the possible crossing, ρ_n has finite total variation; reflection gives the same conclusion for σ_n.The variation opposite to the leading term is bounded by remaining summable terms, and boundedness of ρ makes its variation in the other direction finite.Source: B.A1.4. Divisibility, the… · p. 92
  • At a cluster point, a factor in (B.9.16) can be unbounded only when a vanishing support-boundary factor has a negative exponent.Source: B.A1.4. Divisibility, the… · p. 93

B.A1.5. Analysis of the remaining boundary faces. … C.2. The spectral map for restarted CG

This section develops boundary estimates and uniform local expansions to analyze remaining boundary-face alternatives and fixed strata, including explicit generators after two support losses. It also presents counterexamples for every restart length s ≥ 4, reducing the restart-four construction to a positive orbit of a squared-spectral-weight map.

B.A1.5. Analysis of the remaining boundary faces.

  • The inner corner is the unique cluster point: a middle mode with positive exponents at both vanishing factors contradicts the cocycle product’s positive lower bound.At the outer corner, the increasing cocycle product would tend to zero, giving the same contradiction.Source: B.A1.5. Analysis of the remaining… · p. 93

B.A1.5.1. First-order expansions in the transverse and pivot variables.

  • The distinct-root cocycle has only specified linear terms in a and e, while its remainder is uniformly bounded by C_h((|x| + |a| + |e|)^2 + E).The x-jet vanishes, and external squared-mass jets have uniformly bounded coefficients.Source: B.A1.5.1. First-order expansions in… · p. 98
  • The moment normal coordinate and a are uniformly equivalent throughout the neighbourhood, including at pivot endpoints.Their relation has a nonzero analytic-unit coefficient at either endpoint.Source: B.A1.5.1. First-order expansions in… · p. 99
  • After two support losses, the endpoint fixed-strata union has ideal (pa, yq), a radical complete intersection whose symbolic powers equal its ordinary powers.An analytic generator change with unit determinant transfers these properties to the stated ideal.Source: B.A1.5.1. First-order expansions in… · p. 99
  • At the remaining boundary faces, the intrinsic remainder belongs to the ordinary square, while the cocycle’s nonzero first jet remains isolated.The expansion analysis identifies the four minimal primes of the fixed ideal and removes the first-order normal terms.Source: B.A1.5.1. First-order expansions in… · p. 100

B.A1.5.5. Tail energy and endpoint selection.

  • The tail-energy argument establishes uniform diagonal dominance of the signed-chord coefficients, including through positive-unit endpoints and root collisions.The diagonal coefficients are analytic units, and the off-diagonal operator norm is bounded by half their common lower bound.Source: B.A1.5.5. Tail energy and endpoint… · pp. 102–103

C.1. Counterexamples at restart lengths at least four

  • For every s ≥ 4, an (s + 4)-dimensional SPD problem has a nonterminating restarted-CG orbit whose even normalised residuals do not converge.At restart length four, the certified example is eight-dimensional.Source: §C.1 · p. 104

C.1. Outline of the construction.

  • The restart-four construction builds a transverse Hopf point, shadows a nonconstant periodic profile by an exact orbit, and extends to higher lengths by adjoining distant core nodes.The construction reconstructs an eight-dimensional SPD instance at restart length four; degree elevation preserves the Hopf crossing.Source: §C.1.1 · p. 104

C.2. The spectral map for restarted CG

  • A restarted-CG block is an A-norm error minimisation over its affine Krylov space, and a nonzero next residual induces a map on squared spectral weights.The Krylov space is span{r, Ar, …, A^(s−1)r}.Source: §C.2 · pp. 105–106
  • With eight active nodes and restart length four, nontermination reduces to constructing a positive orbit of T4 whose even squared weights do not converge.If all weights and block factors remain nonzero, the grade stays eight, exceeding the restart length.Source: §C.2 · p. 106

C.3. The certified Hopf point at restart length four … C.7. Shadowing by an orbit of the exact map

This section develops weight-coordinate tools and certifies a transverse Hopf point for the restart-length-four leading vector field. It then constructs a nearby nonconstant periodic orbit and an exact-map orbit that shadows it with positive reconstructed weights.

C.3. The certified Hopf point at restart length four

  • The seed is an exact six-node two-cycle of the core squared-weight map, with two external nodes whose squared two-block multipliers equal one.The parameter q moves the associated leading field through a transverse Hopf crossing.Source: §C.3 · pp. 106–107
  • A unique analytic critical branch has α(q) in [0.2952193, 0.29521955], and at a unique interior q* the linearisation has simple eigenvalues including ±iω* and 1 ± iω*, with a nonzero a-component.The certified frequency satisfies 3.72 < ω* < 3.724.Source: §C.3 · pp. 109–110
  • The Hopf crossing is certified transverse: Dθ < −55.40 throughout the branch, and the Hopf functional derivative lies in (109.89, 110.82).The Hopf functional has opposite strict signs at the rational endpoints of QH.Source: §C.3 · p. 111

C.4. Weight coordinates and the return-map expansion

  • Translating every centred node by five places all eight nodes in (1, 10); the certified lift has induced row-sum bound <220 and midpoint-residual Neumann defect below 1/4.Source: §C.4 · p. 112
  • The exact rescaled two-block weight map has a uniformly bounded analytic expansion; for t>0, reconstructed states have positive core weights, E_g>0, and nonzero successive factors.The successive one-block factors are nonzero at all eight nodes in the stated tube.Source: §C.4 · pp. 113, 116

C.5. The Hopf point in weight coordinates

  • At the critical branch, the scalar and weight-coordinate leading fields are analytically conjugate through an invertible tangent map that preserves δa and includes the equilibrium shear.The tangent conjugacy identifies the two linearizations in weight coordinates.Source: §C.5 · pp. 116, 119
  • The scalar rescaled map has (C.3.12) as its leading vector field, with coefficients justified by intrinsic, external, and factor-identity calculations.The coefficient calculations establish the weighted Taylor expansion of the exact two-block map.Source: §C.5 · p. 118
  • The leading vector field in weight coordinates has a simple transverse Hopf point whose Hopf eigenvector has nonzero a-component.Source: §C.5 · p. 119

C.6. Construction of a periodic orbit

  • A quantitative Hopf contraction yields a unique solution in the certified ball, defining a nonconstant periodic orbit that stays in the positive chart and within QH.The rational ball and conditions uniquely determine the periodic profile and its parameter, frequency, and phase.Source: §C.6 · pp. 120–121

C.7. Shadowing by an orbit of the exact map

  • An exact forward orbit of the squared-weight return map shadows the periodic curve, yielding a restarted-CG counterexample with every reconstructed weight positive.The shadowing construction accommodates nonhyperbolic phase dynamics and every value of the first Lyapunov coefficient.Source: §C.7 · pp. 121, 122, 125

C.8. Accumulation along the periodic orbit … C.12. The distant spectral atom

The sections establish nonconvergence for a fixed restart-four SPD problem and develop a scalar two-cycle framework with degree-elevation arguments extending the construction to every restart length r ≥ 4.

C.8. Accumulation along the periodic orbit

  • The harmonic time mesh accumulates at every phase of the nonconstant periodic profile, giving the even squared weights and normalized residuals multiple accumulation points.The mesh increments are 1/n and tend to zero; distinct phases have distinct recovery-root coordinates, yielding distinct accumulation values.Source: §C.8 · pp. 125–126

C.9. Reconstruction of the SPD counterexample

  • The fixed eight-dimensional SPD construction has positive squared weights at every restart and never terminates; its even residual directions do not converge.The even squared-weight vectors have two distinct accumulation points, which rules out convergence of the even normalized residuals.Source: §C.9 · pp. 126–127

Degree elevation and arbitrary restart length

  • Starting from restart length four, the construction raises the degree one step at a time while preserving the critical branch and transverse crossing, yielding counterexamples for every r ≥ 4.At each elevated length, the return-map expansion and functional-analytic arguments are repeated.Source: Degree elevation and arbitrary restart… · p. 127

C.10. Scalar two-cycle configurations with two external nodes

  • The scalar two-cycle framework uses positive phase weights and two neutral external modes, and restart length four supplies a positive transverse Hopf configuration for degree elevation.At external nodes, the signed two-block multiplier is −1 and its square is +1; the Hopf condition includes a simple imaginary pair with nonzero crossing speed and nonzero recovery-root component.Source: §C.10 · pp. 128–129

C.11. One-step degree elevation

  • For sufficiently large R, one-step degree elevation continues the bounded roots, adds two real simple roots, and preserves positive phase weights and coprimality.At the continued external roots, the squared two-block multiplier remains exactly +1.Source: §C.11 · pp. 129–130

C.12. The distant spectral atom

  • The distant spectral atom’s reproducing-kernel contribution is controlled: on bounded arguments the kernel approaches the unelevated kernel, with phase-specific error bounds and uniform derivative estimates.The complementary term is O(R^-1) in the P-phase and O(R^(1-2r)) in the Q-phase.Source: §C.12 · pp. 130–131

C.13. Persistence of the critical point and Hopf crossing

The section proves that the critical point and transverse Hopf crossing persist under degree elevation: for every sufficiently large finite R, the elevated restart-(r+1) family has a nearby positive Hopf point with a nonzero a-component.

C.13. Persistence of the critical point and Hopf crossing

  • Elevated bounded evaluations converge in C2 to the unelevated data, and interpolation yields convergence of the H-component and coupling coefficients.In particular, T_R converges to T in C2(q, a), including the mixed derivatives used in the persistence argument.Source: §C.13 · p. 132
  • For every sufficiently large finite R, the elevated restart-(r+1) family has a nearby positive critical point with a transverse Hopf crossing and a Hopf eigenvector with nonzero a-component.Strict positivity margins persist at the crossing.Source: §C.13 · pp. 132–134
  • Invertibility of the unelevated critical Jacobian gives a unique nearby positive critical branch, with y_R and the barred matrix converging in C1 to their unelevated counterparts.The corresponding critical-point determinant is nonzero at the Hopf point.Source: §C.13 · p. 133
  • At the elevated Hopf point, the nonreal θ-pair yields eigenvalues ±iω_R and 1 ± iω_R, while no other eigenvalue lies on the imaginary axis.Elevation adds one further real eigenvalue +1; the universal θ = 2 gives λ = −1, 2.Source: §C.13 · p. 134

C.14. The two-block return map at arbitrary restart length … Appendix C. Exact certification of the configuration at restart length four

This section identifies the arbitrary-restart two-block map with the rescaled leading field used in the Hopf analysis, and establishes periodic-orbit selection and shadowing results. It then uses periodic profiles to construct nonterminating SPD restarted-CG examples with nonconvergent even residuals, extends the construction to every restart length s ≥ 4, and records the restart-four certification and an independent lift for lengths divisible by four.

C.14. The two-block return map at arbitrary restart length

  • The coefficient variables (a, C, H, U) form an analytic chart on the core simplex, with (C, H) tangent to the fixed-point family and U the independent normal direction.The chart follows from invertibility of the phase-coefficient and coefficient-to-weight differentials.Source: §C.14 · pp. 134–135
  • For every restart length r ≥ 4, analytic coordinates identify the rescaled exact two-block map’s leading field with the field containing the Hopf point.The weighted Taylor remainders are uniform in the C1 norm on compact subcharts.Source: §C.14 · pp. 135–137

C.15. Selection of a nonconstant periodic orbit

  • At a simple transverse Hopf point, every sufficiently small prescribed nonzero amplitude yields a nearby nonconstant periodic solution, independently of the first Lyapunov coefficient.For an elevated configuration, its nonzero a-component gives a nonzero first harmonic of a; sufficiently small amplitude keeps core weights and scaled external amplitudes positive.Source: §C.15 · pp. 137–138

C.16. Shadowing with harmonic time steps

  • A forward orbit of the perturbed maps shadows a periodic orbit with O(n^-ρ) error, even when the periodic orbit has unstable directions or neutral Jordan blocks.The shadowing theorem applies for any ρ below the smallest absolute stable Floquet decay rate, with βst = ∞ when there is no stable exponent.Source: §C.16 · p. 139
  • The harmonic-time shadowing theorem accommodates neutral Floquet directions from degree elevation in the finite-dimensional complementary subspace.Sections C.14–C.16 supply an orbit shadowing a nonconstant periodic profile at each elevated restart length.Source: §C.16 · p. 141, §C.17 · p. 141

C.17. Positivity, nontermination, and nonconvergence

  • For each elevated restart length, the construction yields a real SPD instance of dimension r + 4 that never terminates and has nonconvergent even residuals.Positive weight and block-factor margins ensure nontermination; distinct accumulation points of the even squared weights rule out convergence of the normalized residuals.Source: §C.17 · pp. 141–142

C.18. Induction and exact existence

  • For every prescribed s ≥ 4, degree elevation produces a positive transverse Hopf configuration with s + 4 nodes, which is converted into the required nonterminating SPD counterexample.The finite induction selects rational neighborhoods and sufficiently large integer scales while preserving strict root, weight, factor, and transversality inequalities.Source: §C.18 · p. 142

C.19. An exact lift for restart lengths divisible by four

  • For s = 4d, an exact Chebyshev lift transfers parity nonconvergence to an independent family of dimension 2s.The conjugacy keeps all 8d components active and the grade is 8d > 4d.Source: §C.19 · p. 143

Consequences and further questions

  • Universal convergence along even and odd subsequences holds precisely for s ∈ {1, 2, 3}; for s ≥ 4, error norms still decrease despite nonconvergent normalized spectral dynamics.The counterexamples have dimension s + 4; the smallest dimension permitting nonconvergence at each restart length remains an open question.Source: Consequences and further questions · p. 143

Appendix C. Exact certification of the configuration at restart length four

  • Exact rational interval arithmetic and Sturm counts certify the finite restart-four premises, while subsequent coordinate changes, contractions, reconstruction, and degree elevation are analytic arguments.The programs use exact rational inputs and verify root ordering, positivity margins, and the transverse Hopf crossing; supplementary all-s checks are finite regression tests, not arbitrary-degree proofs.Source: Appendix C · pp. 144–145
Loading 2609.04659v1…