Collatzova domnienka - II. diel: Fraktálne štruktúry a všeobecné rovnice

Collatz Conjecture - Part II: Fractal Structures and General Equations

8. 8. 2022 Ing. Róbert Polák Matematika Mathematics

Fraktálne zobrazenie Collatzovej postupnosti

Úvod

Tento článok bude o ďalších nápadoch ku Collatzovej domnienke (Collatz conjecture). Tento problém je tiež známy pod názvami 3n + 1 problém, Ulamov problém (podľa Stanisława Ulama), Kakutanov problém (podľa Šizua Kakutaniho), Thwaitov problém (podľa sira Bryana Thwaitesa), Hassov algoritmus (podľa Helmuta Hasseho) alebo tiež ako Syrakuský problém.

Tento článok priamo nadväzuje na prvý diel o Collatzovej domnienke.

Hľadanie všeobecnej rovnice

V úvodnom článku sme dospeli k tomu, že dokážeme nájsť všeobecné riešenie pre ľubovoľný fraktál. Tie najzákladnejšie sú znázornené na obrázku 1.

Obr. 1: Základné fraktály pre sekvenciu 3n-1

Sekvencia 3n-1 je užitočná aj v tom, že celočíselné, záporné riešenie rovníc jednotlivých fraktálov je zároveň riešením Collatzovej hypotézy 3n+1. To je schematicky znázornené na obrázku 1.

Odvodenie rovníc pre fraktály

Všimnime si, že pre ľubovoľný n-fraktál takéhoto typu vznikne všeobecná rovnica:

Rovnice (1.8) až (1.11) dávajú jednoduché riešenie n-tého fraktálu v zmysle obr.1. To by sa dalo preveriť ľubovoľne ďaleko (s ohľadom na výpočtovú náročnosť). Možno rovnica (1.11) umožní vytvoriť dôkaz pre n-fraktál, pričom n smeruje k nekonečnu.

Bohužiaľ, ak urobíme miernu zmenu v type fraktálu, ako je znázornené na obrázku 2, zistíme, že rovnice pre túto zmenu sú síce podobné, ale nie identické.

Obr. 2: Porovnanie fraktálov a ich rovnice

Výpočet pre dve varianty

Tvrdenie (Statement)

To znamená, že rôzne variácie fraktálov vedú na kombinatorickú explóziu.

This means that different variations of fractals lead to a combinatorial explosion.

Rovnica (1.10) sa dá upraviť na jednoduchšiu rovnicu:

Riešenie môžete preveriť aj pomocou Wolfram Alpha:

Wolfram Alpha - riešenie rovnice

Intuitívne by sme povedali, že riešenie (1.14) je pre dva prípady skôr výnimka (s malými číslami) ako pravidlo. Začiatok a koniec na rovnakej úrovni dostaneme len pre tieto dva prípady (viď vyššie). Môžeme urobiť malú konštrukciu dôkazu.

Test závislosti

Na to, aby fraktál (obr. 2) mohol skončiť na rovnakej úrovni, existuje závislosť medzi "a" a "b". Táto závislosť je nasledovná:

Dostali sme rovnicu s jednou premennou. Pozrime sa na priebeh tejto rovnice.

Obr. 3: Priebeh rovnice 1.16

V tomto intervale nebola nájdená celočíselná hodnota pre n (iná ako sú uvedené riešenia). Počítač preveril 2 až 100-tisícový fraktál. Priebeh funkcie je prekvapivý. Priebeh je fraktálny, pričom pre zaujímavosť sa zmeny opakujú v rovnakých vzdialenostiach (pre rast), aj u poklesu sú rovnaké vzdialenosti, napr. perióda 665, perióda 15601 atď.

Priebeh zvyškov po delení (modulo) je znázornený na obrázku 4. Pre a>20 sú zvyšky >1 000 000 a čoraz viac sa zvyšujú. Na celom skúmanom intervale neklesne zvyšok ani raz pod 1 milión.

Obr. 4: Priebeh zvyškov je pre a>20 vždy väčší ako 1 milión. Skúmané na intervale 1-100 000.

Predpoklad je teda, že zvyšky už menšie nebudú až do nekonečna. To nie je prekvapivé.

Konštrukcia dôkazu

Záver

Na záver tohto článku malá rekapitulácia. Podarilo sa nájsť všeobecnú rovnicu pre fraktál z obr. 1, ktorý je n-rozmerný a ten najjednoduchší. Preveril sa fraktál pre n=1 až n=100 000 s programom v Pythone.

Bol vytvorený dôkaz, že okrem uvedených riešení už neexistuje iný fraktál, ktorý spĺňa rovnicu (1.17) a (1.18). Tento dôkaz možno poslúži aj pre hľadanie dôkazu všeobecného fraktálu s n vrcholmi (teda možnej opakujúcej sa sekvencie).

Zdroje

Collatz conjecture - Wikipedia

Fractal representation of Collatz sequence

Introduction

This article will be about further ideas regarding the Collatz conjecture (Collatz conjecture). This problem is also known by the names 3n + 1 problem, Ulam's problem (after Stanisław Ulam), Kakutani's problem (after Shizuo Kakutani), Thwaites' problem (after Sir Bryan Thwaites), Hasse's algorithm (after Helmut Hasse), or also as the Syracuse problem.

This article directly follows the first part about the Collatz conjecture.

Searching for General Equations

In the introductory article, we came to the conclusion that we can find a general solution for any fractal. The most basic ones are shown in Figure 1.

$Basic fractals for sequence 3n-1$

Fig. 1: Basic fractals for sequence 3n-1

The sequence 3n-1 is also useful in that the integer, negative solution of equations of individual fractals is simultaneously a solution to the Collatz hypothesis 3n+1. This is schematically shown in Figure 1.

Derivation of Equations for Fractals

$Derivation of equations for fractals$

Notice that for any n-fractal of this type, a general equation arises:

$General equation for n-fractal$

Equations (1.8) through (1.11) give a simple solution for the nth fractal in the sense of Fig. 1. This could be verified arbitrarily far (considering computational complexity). Perhaps equation (1.11) will allow creating a proof for the n-fractal, where n approaches infinity.

Unfortunately, if we make a slight change in the type of fractal, as shown in Figure 2, we find that equations for this change are similar but not identical.

$Comparison of fractals and their equations$

Fig. 2: Comparison of fractals and their equations

Calculation for Two Variants

Statement

This means that different variations of fractals lead to a combinatorial explosion.

Equation (1.10) can be modified to a simpler equation:

You can also verify the solution using Wolfram Alpha:

Wolfram Alpha - equation solution

Intuitively, we would say that the solution (1.14) is more of an exception (with small numbers) than a rule for two cases. We get the beginning and end at the same level only for these two cases (see above). We can make a small construction of proof.

Dependency Test

For the fractal (Fig. 2) to be able to end at the same level, there is a dependency between "a" and "b". This dependency is as follows:

We obtained an equation with one variable. Let's look at the course of this equation.

Fig. 3: Course of equation 1.16

In this interval, no integer value for n was found (other than the stated solutions). The computer verified fractals from 2 to 100,000. The function's course is surprising. The course is fractal, with changes repeating at the same distances (for growth), and the same distances for decreases, e.g., period 665, period 15,601, etc.

The course of remainders after division (modulo) is shown in Figure 4. For a>20, remainders are >1,000,000 and continue to increase. In the entire examined interval, the remainder never falls below 1 million.

Fig. 4: Course of remainders is always greater than 1 million for a>20. Examined on interval 1-100,000.

The assumption is therefore that remainders will not get smaller up to infinity. This is not surprising.

Proof Construction

Conclusion

To conclude this article, a brief recap. We managed to find a general equation for the fractal from Fig. 1, which is n-dimensional and the simplest one. The fractal was verified for n=1 to n=100,000 with a Python program.

A proof was created that besides the stated solutions, no other fractal exists that satisfies equations (1.17) and (1.18). This proof may also serve for finding a proof of the general fractal with n vertices (i.e., possible repeating sequence).

Sources

Collatz conjecture - Wikipedia