De gedachte achter dit artikel is wel mooi: het Collatz vermoeden inductief bewijzen via modulaire equivalentieklassen.
Hieronder tot hoe ver ik kom met "Proof 1" van Farzali Izadi.
Definieer:
f(n) = de Collatz functie (f(n) = 3n+1 als n oneven, f(n) = n/2 als n even)
m, n, a, b, c ∈ N = {0, 1, 2, 3, ... }
i, j, k, k' ∈ I = {1, 3, 5, 7, ... }
R(k) = de gereduceerde Collatz functie van I naar I met
\(\small R(k) = k' = \frac{3k+1}{2^r}\)
waarbij r zo groot mogelijk, zodat alle factoren 2 uit 3k+1 worden weggedeeld(zie bv https://oeis.org/A075677)
en veronderstel voor k:
\(\small j \overset{R}{\rightarrow} k \overset{R}{\rightarrow} k'\)
(voor zover er zo'n j < k bestaat)Inductief bewijs:
Basis: R(1) = 1
Inductie:
Stel het Collatz vermoeden geldt voor alle i < k, toon aan dat het dan ook voor k geldt.
Farzali Izadi doet dit in zijn "Proof 1" via equivalentieklassen mod 6.
Hier een aangepaste versie daarvan:
Part I: k%6 ≡ 1
Part Ia: k%12 ≡ 1
k = 12m+1 → f(k) = 3k+1 = 36m+4 = 4(9m+1) → k' = R(k) ≤ 9m+1 < 12m+1 = k (voor m>0)
Omdat k' < k geldt het vermoeden voor k' (volgens de inductie-hypothese) en dus ook voor k.
Part Ib: k%12 ≡ 7
k = 12m+7 → f(k) = 3k+1 = 36m+22 = 2(18m+11) → k' = R(k) = 18m+11 > 12m+1 = k
Omdat k' > k schieten we hier niet mee op.
Probeer dan een j < k te vinden zodat R(j) = k (dan zit k in het Collatz-pad van j naar 1):
zoek a, b en c, zodanig dat
j = am+b en f(j) = 3am+3b+1 = 2c(12m+7)
c=0 → 3a = 12 en 3b+1 = 7 → a=4 en b=2 → j = 4am+2 = even, en dat mag niet
c=1 → 3b+1 = 14, heeft geen geheeltallige oplossing
c=2 → 3a = 48 en 3b+1 = 28 → a=16 en b=9 → j = 16m+9 > 12m+7 = k, kan niet: j is groter dan k
Voor hogere waarden van c wordt j alleen nog maar groter.
Conclusie: (nog) geen oplossing voor dit geval
Part II: k%6 ≡ 5 (ofwel: k%12 ≡ 5 of k%12 ≡ 11)
k = 6m+5, kies j = 4m+3 (zodat j < k):
j = 4m+3 → f(j) = 12m+10 = 2(6m+5) → R(j) = 6m+5 = k, dus geldt het vermoeden ook voor k
Part III: k%6 ≡ 3
Part IIIa: k%12 ≡ 3
k = 12m+3 → f(k) = 36m+10 = 2(18m+5) → k' = R(k) = 18m+5 > 12m+3 = k, dus k' > k = geen bewijs
dan via R(j) = k voor een j < k:
j = am+b en f(j) = 3am+3b+1 = 2c(12m+3)
dan moet 3b+1 = 3*2c → b = 2c - (1/3) en dit heeft geen geheeltallige oplossing.
Conclusie: (nog) geen oplossing voor dit geval
Part IIIb: k%12 ≡ 9
k = 12m+9 → f(k) = 36m+28 = 4(9m+7) → k' = R(k) ≤ 9m+7 < 12m+3 = k
Omdat k' < k geldt het vermoeden voor k' en dus ook voor k.
In zijn Remark 2 stelt Farzali Izadi: neem in Part I j=2m, dan is j ∉ I gaat j wel naar 1, ook al is deze even.
Maar dit gebeurt via deling door 2, en niet via 3j+1 naar k
Eveneens stelt hij daar voor Part III: "sometimes we need to apply the Syracuse function a couple of times",
maar dit is vergelijkbaar met de brute-kracht methode voor het testen van een Collatz getal,
en dit sluit bovendien een hoge cykel niet uit (hoger dan 1-4-2-1) noch mogelijke divergentie naar oneindigheid van de keten (ofwel: geen garantie dat de keten terugkomt naar een getal kleiner dan k).
Met bovenstaande kunnen we het zoeken naar Collatz-uitzonderingen nu wel beperken tot alle oneven getallen
3 mod 12 en 7 mod 12.
De vraag die overblijft is: hoe kunnen we de zoekruimte nog verder verkleinen?
