Orbits, fixed points and periodic points: classifying all six states of T(x)=(2x+1) mod 6

Goal and scope

On the state space X={0,1,2,3,4,5} take the self-map T(x)=(2x+1) mod 6. Find all fixed points and all periodic points of least period 2; prove that for a point of least period p, T^n(x)=x exactly when p divides n, and use this to explain why T^4(1)=1 does not make 4 the least period of 1; finally prove that 0, 2 and 4 are not periodic, although their orbits enter a cycle after one step.

Works inside the MKO's scope: complete finite residue-class states and an affine self-map, with the classification valid only for this specified finite model (assumptions a1, a2). Fixed points and period 2 are decided by congruence algebra and cross-checked by finite checks that cover all six states. Attraction, stability, parameter bifurcation and infinite systems are not treated; the canonical MKO and its English edition are not changed.

Givens and symbols

• division_algorithm
• divides_def
• nat_induction
• composition_def
• image_preimage_def
• case_analysis
• contradiction

• G1 — X={0,1,2,3,4,5}, the least nonnegative representatives of the six residue classes modulo 6 (complete finite residue-class states, MKO assumption a1).
• G2 — T:X→X, T(x)=(2x+1) mod 6, where m mod 6 is the remainder of the integer m on division by 6.
• G3 — Iterates: T^0 is the identity map of X and T^(n+1)=T∘T^n. The forward orbit of x is x, T(x), T²(x), and so on.
• G4 — Definitions (MKO): x is a fixed point if T(x)=x; x is periodic if T^n(x)=x for some positive integer n, and the least such n is the least period p(x). Here x is called preperiodic if x is not periodic but some T^k(x) with k≥1 is periodic.

• X — the state space {0,1,2,3,4,5}
• T — the self-map T(x)=(2x+1) mod 6
• T^n — the n-th iterate of T, with T^0 the identity
• p(x) — the least period of x
• T(X) — the image of T
• u\equiv v\pmod 6 — congruence modulo 6

Rules and sources

• division_algorithm · prerequisite — Division algorithm: for an integer a and a positive integer b there are unique integers q, r with a=bq+r and 0≤r<b.
• divides_def · prerequisite — Divisibility: for integers a, b, a∣b means there is an integer k with b=ak.
• nat_induction · prerequisite — Principle of induction: for a family P(n) starting at n₀, if P(n₀) holds and P(n)⇒P(n+1) for every n≥n₀, then P(n) holds for every n≥n₀.
• composition_def · prerequisite — Composition: for f:A→B and g:B→C, g∘f:A→C is defined by (g∘f)(a)=g(f(a)).
• image_preimage_def · prerequisite — Image and preimage: f(S)={f(a) ∣ a∈S}; f⁻¹(T)={a∈A ∣ f(a)∈T}. The preimage notation does not presuppose that f has an inverse.
• case_analysis · prerequisite — Proof by cases: if P∨Q holds and both P⇒R and Q⇒R are proved, then R holds. The cases must cover every possibility.
• contradiction · prerequisite — Proof by contradiction: if assuming ¬P leads to a contradiction (a statement and its negation both hold), then P holds.
• def_intro · prerequisite — Introducing a definition: a statement, expression or object may be given a name, after which the name and what it stands for are interchangeable.
• numeric_evaluation · prerequisite — Exact evaluation of an explicit integer or rational expression; independently recomputable.
• set_extensionality · prerequisite — Set equality: A=B if and only if A⊆B and B⊆A, i.e. they have the same elements.
• add_inverse · prerequisite — Additive inverse: every u has −u with u+(−u)=0; u−v means u+(−v).
• distributive · prerequisite — Distributivity: u(v+w)=uv+uw; with commutativity also (v+w)u=vu+wu.
• mul_inverse_nonzero · prerequisite — Inverse of a nonzero number: in ℚ, ℝ or ℂ, if u≠0 there is 1/u with u·(1/u)=1, and v/u means v·(1/u). 0 has no inverse, so v/0 is undefined.
• eq_congruence · prerequisite — Congruence of equality: if u=v, applying the same defined operation f to both sides gives f(u)=f(v). Operating on one side only is not an instance of this rule.
• def_unfold · prerequisite — Unfolding a definition: replacing a defined term by its definition (or folding it back) does not change whether a statement is true.
• eq_replace · prerequisite — Replacement of equals: an expression inside a statement may be replaced by an equal expression without changing whether the statement is true.
• and_intro_elim · prerequisite — Conjunction: from P and Q infer P∧Q; from P∧Q infer P and infer Q.
• set_operations_def · prerequisite — Set operations: x∈A∪B ⇔ x∈A or x∈B; x∈A∩B ⇔ x∈A and x∈B; x∈A∖B ⇔ x∈A and x∉B; in a universe U, Aᶜ=U∖A.
• mko_orbit_defs · cited — For a self-map T:X→X, the forward orbit of x is x, T(x), T²(x) and so on. A point is fixed when T(x)=x. If there is a least positive integer p such that T^p(x)=x, it is periodic with least period p. Eventually entering a cycle does not make the starting point itself periodic. · mko-orbit-fixed-periodic
• mod6_arith · prerequisite — Congruence modulo 6: u≡v (mod 6) means 6∣(u−v); congruence is compatible with addition and multiplication; m mod 6 is the unique r∈X with m≡r (mod 6); two elements of X are equal ⇔ they are congruent modulo 6.
• iterate_law · prerequisite — For a self-map T and all natural numbers a, b: T^(a+b)=T^a∘T^b (it follows from T^0=id and T^(n+1)=T∘T^n by induction on a).
• L_return · lemma — If x has least period p, then for every positive integer n: T^n(x)=x ⇔ p∣n.
• L_image · lemma — For every x∈X and every positive integer n: T^n(x)∈T(X).

Main derivation

\text{self-map and its iterates}

T:X\to X,\ T^0=\mathrm{id}_X,\ T^{n+1}=T\circ T^n

x\in X

T(x)=(2x+1)\bmod 6\in X

T(0),T(1),T(2),T(3),T(4),T(5)

1,\ 3,\ 5,\ 1,\ 3,\ 5

T(X)=\{T(x)\mid x\in X\}

T(X)=\{1,3,5\}

T(x)=x,\ x\in X

x=5

T^2(x)=T(T(x))

T^2(x)=(4x+3)\bmod 6

T^2(x)=x,\ x\in X

x\in\{1,3,5\}

x\in\{1,3,5\}

p(5)=1,\ p(1)=2,\ p(3)=2

p=\min\{n\geq 1\mid T^n(x)=x\}

\forall n\geq 1:\ T^n(x)=x\iff p\mid n

x=1,\ p(1)=2

T^n(1)=1\iff 2\mid n;\ T^4(1)=1,\ T^3(1)=3

n\geq 1

T^n(x)\in T(X)=\{1,3,5\}

x\in\{0,2,4\}

\forall n\geq 1:\ T^n(x)\neq x

T(0)=1,\ T(2)=5,\ T(4)=3

0,2,4\ \text{preperiodic, not periodic}

X=\{0,1,2,3,4,5\}

\mathrm{Fix}(T)=\{5\},\ \{x\mid p(x)=2\}=\{1,3\},\ \text{preperiodic}=\{0,2,4\}

Substeps and lemmas

2x+1\ \text{for}\ x=0,1,2,3,4,5

1,\ 3,\ 5,\ 7,\ 9,\ 11

1,3,5,7,9,11\ \bmod 6

1,\ 3,\ 5,\ 1,\ 3,\ 5

T(x)=x

2x+1\equiv x\pmod 6

2x+1\equiv x\pmod 6

6\mid x+1

6\mid x+1,\ x\in X

x=5

4x+3\equiv x\pmod 6

6\mid 3(x+1)

6\mid 3(x+1)

2\mid x+1

2\mid x+1,\ x\in X

x\in\{1,3,5\}

q=0

T^{0\cdot p}(x)=T^0(x)=x

T^{qp}(x)=x

T^{(q+1)p}(x)=x

n=qp+r,\ 0\le r<p

T^n(x)=T^r(x)

T^n(x)=x

r=0,\ p\mid n

T^n(x),\ n\geq 1

T^n(x)=T(T^{n-1}(x))\in T(X)

Reverse audits

• S14 · sufficient_goal_reduction · S05, S08, S12, S13 — Goal G: the complete classification of X. Sufficient condition H: the four conclusions S05, S08, S12, S13, plus the fact that the union of the three sets is X; H⇒G by conjunction. H is proved forwards from the definitions and congruence algebra; G is never used as a premise.
• S13 · premise_audit · S08, S12, G4 — Preperiodic needs two parts: not periodic (S12) and some T^k(x) periodic (here k=1, by S03 and S08).
• S12 · premise_audit · S11, S04, contradiction — It needs x outside the image (S04) and L_image; no converse is claimed: lying outside the image is sufficient for non-periodicity, not necessary.
• S11.1 · premise_audit · G3, composition_def, image_preimage_def — Only the recursive definition of iterates and the definition of the image are used; the argument holds uniformly for every n≥1 and is not a finite check.
• S11 · premise_audit · L_image, S04 — It needs n≥1; for n=0, T^0(x)=x may lie outside the image, which is exactly the case of 0, 2 and 4.
• S10 · premise_audit · S08, L_return — It needs p(1)=2 (S08) and the lemma; N9 and N10 cross-check T^4(1) and T^3(1) by direct computation.
• S09.4 · premise_audit · S09.2, S09.3, contradiction, G4 — The contradiction uses only the minimality of p and 0≤r<p; both directions are handled.
• S09.3 · premise_audit · division_algorithm, iterate_law, S09.2 — It needs p≥1 for division with remainder, and the induction result of S09.2.
• S09.2 · premise_audit · iterate_law, nat_induction, G4 — It needs the induction hypothesis, the iterate law and T^p(x)=x; it does not claim that there are no return times other than multiples of p (that is S09.4's job).
• S09.1 · premise_audit · G3, nat_induction — Only the definition of T^0 is used.
• S09 · premise_audit · L_return, iterate_law, G4 — The lemma needs only that p is the least positive return time and the iterate law; it does not depend on X being finite or on the formula for T.
• S08 · premise_audit · S03, S05, S07, G4 — Two things are needed: T^p(x)=x (S05, S07), and T^n(x)≠x for every 1≤n<p (from the table S03). The first alone does not determine the least period.
• S07.3 · inverse_equivalence · case_analysis — The six cases cover all of X and each is decided, so both directions are checked.
• S07.2 · inverse_equivalence · divides_def, mul_inverse_nonzero — Multiplying by 3 and dividing by 3 undo each other given 3≠0; the same k works in both directions.
• S07.1 · inverse_equivalence · divides_def, distributive — Unfolding congruence and the identity 4x+3−x=3(x+1) (N7) are both two-way.
• S07 · inverse_equivalence · mod6_arith, divides_def — All three sub-steps are equivalences; backwards one checks directly T²(1)=1, T²(3)=3 and T²(5)=5.
• S06 · inverse_equivalence · mod6_arith, composition_def — Both sides name the same element of X (the unique representative of one residue class), so the equation holds both ways; N6 cross-checks all six states.
• S05.3 · inverse_equivalence · case_analysis, divides_def — The six cases cover every element of X and each is decided, so both directions are checked.
• S05.2 · inverse_equivalence · divides_def, mod6_arith — This unfolds the definition of congruence and uses one identity, so it holds both ways.
• S05.1 · inverse_equivalence · mod6_arith — 'Equal in X ⇔ congruent' is itself two-way.
• S05 · inverse_equivalence · mod6_arith, divides_def — All three sub-steps are two-way equivalences, so T(x)=x and x=5 are true together; backwards, T(5)=5 is checked directly.
• S04 · inverse_equivalence · S03, image_preimage_def, set_extensionality — Both inclusions hold: every T(x) belongs to {1,3,5}, and each of 1, 3, 5 has a preimage; by extensionality the two descriptions name the same set.
• S03.2 · inverse_equivalence · division_algorithm — Backward: 6·1+1=7 and so on restore the original numbers; uniqueness in the division algorithm makes each remainder unique.
• S03.1 · inverse_equivalence · numeric_evaluation — Integer arithmetic has unique values, so both sides agree.
• S03 · inverse_equivalence · numeric_evaluation, division_algorithm — Each value is the same number written two ways and can be recomputed one by one (N1 to N4).
• S02 · premise_audit · G2, division_algorithm — It needs only that the divisor 6 is a positive integer; it is not claimed that T is a bijection (S04 shows it is not).
• S01 · premise_audit · G1, G2, G3, G4, mko_orbit_defs — This step only states the model and definitions and derives no new fact; every conclusion holds in this finite model only.

Error controls and negative controls

A return time need not be the least period

One mistake named by the MKO is calling any return time the least period. T^4(1)=1, but already T²(1)=1, so the least period of 1 is 2 (S08, S10); T²(5)=5, but T(5)=5, so the least period of 5 is 1. L_return shows every return time is a multiple of p, and deciding the least period requires excluding every smaller positive integer.

Eventually entering a cycle does not make the starting point periodic

The orbit 0, 1, 3, 1, 3 of 0 cycles from step 1 on, but the cycle does not contain the start 0. S12 proves 0 never comes back: every T^n(0) with n≥1 lies in {1,3,5}. Calling a point periodic because its orbit eventually cycles is the other mistake the MKO names.

What the finite checks cover

N4, N5, N6, N8 and N11 are finite checks over all six states of X; X has exactly these six states, so they cover the whole state space of this system, and the conclusions of S05, S07 and S12 also have algebraic proofs. The checks say nothing about other moduli, other maps or infinite systems (MKO assumption a2).

• T^4(1)=1, so the least period of 1 is 4 → reject — T²(1)=T(3)=1, so 2 is a smaller positive return time.
• The orbit of 0 ends up cycling between 1 and 3, so 0 is periodic → reject — 0∉T(X)={1,3,5}, so T^n(0)≠0 for every n≥1 (S12).
• T²(5)=5, so 5 is a periodic point of least period 2 → reject — T(5)=11 mod 6=5, so the least period is 1.
• In a system on ℤ, the orbit of a point does not return in its first 200 steps, so the point is not periodic → reject — Take T(x)=x+1 for 0≤x<200, T(200)=0 and T(x)=x otherwise: 0 does not return in the first 200 steps, but T^201(0)=0. A finite prefix proves no non-periodicity (MKO assumption a2).

Result and limitations

For T(x)=(2x+1) mod 6: the only fixed point is 5; 1 and 3 form a cycle of least period 2; 0, 2 and 4 are not in the image of T, so they never return to themselves and are preperiodic (after one step they move to 1, 5 and 3). For a point of least period p, T^n(x)=x exactly when p∣n; so T^4(1)=1 is only a return time, and the least period of 1 is still 2.

• The iterate law T^(a+b)=T^a∘T^b is used as a prerequisite here and is not re-proved by induction.
• Attracting cycles, stability and parameter bifurcation belong to the MKO's formal next step and are not treated; the classification here is not extended to other affine maps (ax+b) mod m.

Verification and source binding

12 declared checks for this guide; only the listed expressions are covered.

• source commit: b28a5edbd46279b1db2a3f3f48bb3f447e18899f
• adopted source SHA-256: 790a36d058c22ecf3ef889f75d6af706cd0f9c467bc505d2f3267262dbba5620
• original source SHA-256: 790a36d058c22ecf3ef889f75d6af706cd0f9c467bc505d2f3267262dbba5620
• Lean: NOT_RUN · independent AI: NOT_MEASURED

Same-source full JSON (formulas, ASTs, controls and revision log)