Erdős #411: finite-certificate equivalence, parity constraints, and an exhaustive catalogue of eventual-multiplier orbits of n+φ(n) to 10^7

Certificate equivalence theorem: for integers n,r≥1, c≥2, the eventual relation g_{k+r}(n)=c·g_k(n) (all large k) holds iff some orbit point x=g_K(n) satisfies the finite certificate g_r(x)=c·x and rad(c)|g_j(x) for 0≤j<r; moreover the relation then holds for every k≥K and the set of certificate indices is upward closed (so the least certificate index is the sharp onset). Proof: two-line φ-scaling lemma φ(cm)=cφ(m) ⟺ rad(c)|m plus a well-founded double induction; both directions complete in proof_structural_lemmas.md.

Parity theorem: for m≥3, g(m)≡m (mod 2), so orbit parity is constant once the orbit is ≥3; consequently any eventual relation with even multiplier c (in particular the literal Erdős–Graham c=2) forces n even (n≥4) with an all-even orbit, and odd n≥3 admit only odd multipliers. All odd witnesses in the catalogue (6075, 9009, 11739, 13857, 31851, 74829, 965505) have odd c ∈ {729, 6561}, as forced.

Exhaustive catalogue at x<=10^8, r<=40 (COMPLETE and fully verified; extends the initially reported 10^7 box): 25513 raw hits g_r(x)=c*x, 16832 certificates (each independently re-verified by direct orbit iteration, 0 failures), collapsing under orbit/scaling/power reductions to exactly 20 primitive families. Exactly ONE new primitive family appears beyond 10^7: a second orbit-independent (r=25, c=729) witness at x=71912934, independent of Weintraub's 3114 orbit. OEIS A383044 cross-check passes on the (r,c)=(2,2) certificate points.

New primitive witness orbits (each with a verified finite certificate proving its eventual relation unconditionally): (r=4,c=3) at x=11202, 13890, 42498 — pairwise independent of Cambie's 738 and of each other up to all scalings s=2^a·3^b≤2000 within 200 steps (values to 10^18); (r=9,c=9) root 28002 whose 2^a·3-scaled orbits absorb all five recorded Steinerberger starts (130,170,234,266 funnel to 8892342 on 3·orbit(28002); 260=2·130 runs exactly 2× that orbit, first certificate point 17784684 on 6·orbit(28002)); (r=25,c=729) root 15702 (2·orbit meets 1702's orbit; commensurable with Weintraub's 3114 and Steinerberger's 1570); odd (r=20,c=6561) orbits 6075=3^5·5^2 and 965505 (27·orbit(6075) and orbit(965505) meet 385's orbit and its 9-scaling respectively); odd (r=14,c=729) entry branches 11739 and 31851 merging downstream with the recorded outlier class.

Sharp onset indices for all recorded empirical examples, upgrading them from observations to theorems: Weintraub's g_{k+25}(3114)=729·g_k(3114) holds for all k≥5 and fails at k=4 (the record says k≥6); Steinerberger's five r=9 starts have onsets 37–39 with common first certificate point 8892342; 385 has onset 13 (certificate 251505), 1570 onset 28 (18755712), 1702 onset 15 (218700), and the r=14 outliers 3393/6175/6969 onsets 2/7/2. Cambie's 738, 148646, 4325798 carry certificates at k=0 (recorded as k≥1).

Caveats on novelty: Steinerberger's r=9 list carries an ellipsis and he writes 'Many more such solutions exist', and the original Selfridge–Weintraub r=9 solution values are not listed in any accessible source (ErGr80 p.81 gives none; Steinerberger reports only 'all n found were even'), so the (9,9), (20,6561), (25,729) and (14,729) novelty claims are relative to the explicitly recorded examples; Stijn Cambie is active on this problem (page edited 2025-10-28) and may hold unpublished sweeps covering the (4,3) orbits.