Source-linked AI summary
Three Quadratic Recurrences Modulo 3: What We Can Prove and What We Can Guess
Steven Finch
TL;DR
The paper asks how three similar modulo-3 recurrences behave, noting that swapping the lags in two rules can produce completely different behavior. It analyzes them through linear recurrence and state-space methods, proving exact period and structural results while leaving some patterns conjectural.
Problem
The paper examines how three modulo-3 recurrences behave, including why rules with the same ingredients but swapped lags can behave differently.
Source: §1 · p. 2Method
Results
Takeaways & Limitations
The proposed random behavior of NB(k)/3^k remains a conjecture, and recurrence (A) also has observed patterns that the paper does not establish as a theorem.
Source: §3 · p. 4, §4 · p. 6For recurrence (A), no simple sufficient condition on k is established for the observed period behavior, which remains a guess rather than a theorem.
Source: §4 · p. 6
Abstract
from arXiv · showhide
We study three innocent-looking recurrences modulo $3$, each built from squares of two earlier terms. One of them turns out to be secretly $\textit{linear}$, and we can compute its periods exactly. One is a $\textit{permutation}$ hiding a small, perfectly orderly piece inside a large, random-looking one. The third looks thoroughly random, but it still has a few provable features. Along the way we meet open problems that need nothing beyond a first course in abstract algebra to state. This paper is a starting point, not the final word in any sense.
1 The setup
The paper sets up three recurrences modulo 3 from a common initial block and notes that swapping the lags in rules (A) and (B) produces different behavior. Since each term depends on only the previous k terms, every sequence is eventually periodic.
1 The setup
- Each sequence starts with x1 through xk−1 equal to 0 and xk equal to 1, then follows one of three rules modulo 3.The rules use squares of earlier terms.Source: §1 · pp. 1–2
- Because there are only 3^k possible blocks of k terms, every sequence is eventually periodic, with a least period and pre-period.The paper denotes these by N and µ for each rule.Source: §1 · p. 1
- For c in Z/3, c^2 indicates whether c is nonzero, and 2(c^2+c) indicates whether c equals 1.Source: §1 · p. 1
- Rule (C) can be written as the sum of indicators that x_n−1 and x_n−k equal 1.Source: §1 · p. 2
- Rules (A) and (B) use the same two ingredients with the lags swapped, yet behave completely differently.Source: §1 · p. 2
2 Recurrence (C): secretly linear
Recurrence (C) becomes linear after tracking whether each term equals 1, which gives an exact polynomial-order description of its period. The section also establishes bounds and divisibility results while distinguishing proved period formulas from the missing step in a related argument.
2 Recurrence (C): secretly linear
- For k ≥ 2, µC(k)=1 and NC(k)=ord(x^k+x+1)≤2^k−1, with equality exactly when x^k+x+1 is primitive.The sequence y_n=[x_n=1] follows a linear recurrence over F2; its period matches the order of the reversed polynomial, and x becomes periodic from n=2.Source: §2 · p. 2
- The polynomial x^k+x+1 has no repeated factors, so NC(k) is the least common multiple of the orders of its irreducible factors; for k=5, NC(5)=21.Here x^5+x+1 factors into polynomials of orders 3 and 7.Source: §2 · p. 3
- For q=2^j, the section proves 3 divides NC(k) when k≡2 (mod 3), and gives NC(q) divides q^2−1 and NC(q+1) divides q^2+q+1.The divisibility arguments use polynomial orders over F2 and the characteristic-2 identity (a+b)^q=a^q+b^q.Source: §2 · p. 3
- The divisibility bounds are equalities: NC(2^j)=2^(2j)−1 and NC(2^j+1)=2^(2j)+2^j+1, as proved in [1] and proposed in.Bartholdi verified cases through j≤16 by computer and proved half of the conjecture [1].Source: §2 · p. 3
- The argument for one direction shows ord(x^(2^M−1)+x+1) divides 2^M−1, but the missing step is ruling out a smaller order.The construction uses the squaring map in the quotient ring over F2.Source: §2 · p. 3
3 Recurrence (B): a permutation with an orderly corner
Recurrence (B) is a permutation of the state space, so every orbit is a cycle, but its starting state is not in the orderly set of short cycles. The paper characterizes states fixed by the 4k-th iterate and contrasts this orderly region with a large, random-looking remainder.
3 Recurrence (B): a permutation with an orderly corner
- For k≥2, the state map T is a bijection of (Z/3)^k, so every orbit is a cycle and µB(k)=0; its only fixed point is 0.Source: §3 · p. 4
- For k≤20, computer decompositions find thousands of cycles of length 4k and a handful of huge cycles; the short cycles can be described exactly.The count follows by choosing a starting zero and counting step sequences that return to it.Source: §3 · p. 4
- States fixed by T^4k correspond to two-sided sequences of period dividing 4k, arranged as a 4×k array whose columns each have either one or four zeros.If any column is all zero, the recurrence forces every column to be all zero, giving the fixed point 0.Source: §3 · p. 4
- In nonzero states fixed by T^4k, successive column zeros differ by k+1 or 2k+1 positions, and any such choices that close around the array give a solution.Source: §3 · p. 4
- For k≥3, NB(k) does not divide 4k, and the starting block’s adjacent zeros exclude it from the solutions described by the theorem.Source: §3 · p. 4
- The orderly corner contains about 2k of the 3^k states, while the remaining states resemble a random permutation; for k≤20, the largest cycle averages about 0.63·3^k.The reported average is close to the 0.6243… Golomb-Dickman constant for random permutations.Source: §3 · p. 4
- The conjecture is that NB(k)/3^k behaves like independent uniform random numbers in (0,1) as k→∞.Source: §3 · p. 4
4 Recurrence (A): looks random, but not entirely
Recurrence A has eventual periods of at least four, and its period-four cycles occur only for specified values of k modulo 4. A precise capture criterion identifies when those cycles occur, while broader patterns remain conjectural.
4 Recurrence (A): looks random, but not entirely
- The pre-period can be enormous: µA(403) ≈1.0×10^11 and µA(487) ≈4.8×10^12.The section defines b_n = [x_n ≠ 0] and d_n = x_n − x_(n−1) = b_(n−k) for n ≥ k + 1.Source: §4 · p. 5
- Every eventual period is at least 4.A period of 3 would force every term to be nonzero, contradicting that the period contains all three residues.Source: §4 · p. 5
- When NA(k) = 4, the eventual cycle is (0, 1, 1, 2) for k ≡2 (mod 4), or (0, 1, 2, 2) for k ≡3 (mod 4).For each such k, the corresponding 4-periodic sequence satisfies the recurrence.Source: §4 · p. 5
- The residue condition is necessary but not sufficient: NA(18) = 213 and NA(23) = 412.The paper gives an exact test that can be applied on a computer.Source: §4 · p. 5
- For k ≡2 or 3 (mod 4), NA(k) = 4 exactly when, beyond index k, the zeros contain G = ⌈(k −1)/4⌉ consecutive gaps of exactly 4.Once such a run occurs, the recurrence follows the matching 4-periodic solution from its final zero onward.Source: §4 · p. 5
- The conjectured families NA(4m^2 + 3) = 4 and NA(32j+1) = 4 have only modest computational checks so far.The first was checked for m ≤11 (up to k = 487), and the second only for k = 3, 27, 243.Source: §4 · p. 5
- About three quarters of tested k ≡2, 3 (mod 4) up to 411 have NA(k) = 4, but the paper suspects no simple sufficient condition exists.That suspicion is explicitly presented as a guess; statistics gathered before capture do not seem to distinguish the outcomes.Source: §4 · p. 6
6 Addendum: short runs of zeros in recurrence (A)
For k ≡0 or 1 (mod 4), runs of zeros spaced four apart have a strict length bound, unlike the persistent 4-cycles possible for k ≡2 or 3 (mod 4).
The setting
- After index k, each step is 0 or 1 modulo 3, so the sequence can only stay put or increase by 1.The addendum contrasts the bounded-run cases with k ≡2 or 3 (mod 4), where zeros spaced four apart can persist.Source: The setting · p. 6
What we mean by a run
- A run has g gaps when zeros occur at r, r + 4, …, r + 4g with no intervening zeros; it need not be maximal.The definition requires r ≥ k + 1 and makes no assumptions about terms before r or after r + 4g.Source: What we mean by a run · pp. 6–7
The result
- For k ≡0 or 1 (mod 4), every run of zeros spaced exactly four apart has at most ⌊(k −1)/4⌋ gaps.The bound follows by considering the step k positions after a run begins: the recurrence forces it to be 0, while the run’s block pattern forces it to be 1.Source: The result · pp. 7–8
- Within each four-step block between run zeros, the terms read 0, 1, ∗, 2, 0, and steps at positions congruent to r or r + 1 modulo 4 equal 1.The middle entry ∗ is either 1 or 2.Source: The result · p. 7
An example and some remarks
- For k = 4, no gap of four occurs beyond index 4; for k = 5, one such gap is allowed, but two consecutive ones are not.The k = 4 example has gaps between consecutive ones only of lengths 1, 3, or 5.Source: An example and some remarks · p. 8
- For k ≡2 or 3 (mod 4), the 4-cycles (0, 1, 1, 2) and (0, 1, 2, 2) persist indefinitely.In these residue classes the relevant step can be into or out of the middle entry, which may be zero.Source: An example and some remarks · p. 8
- Empirical examples attain ⌊(k−1)/4⌋ gaps for k = 245, 297, 333 and k = 288, 320, 340; proving such maximal runs always occur remains a theoretical challenge.Source: An example and some remarks · p. 8
The setting
This setting fixes the recurrence’s initial values and focuses on k ≡2 or 3 (mod 4) when the eventual period is 4. It defines the zero runs and the indices used to describe capture and pre-period.
The setting
- The sequence starts with x1 through xk−1 equal to 0 and xk equal to 1; the discussion assumes k ≡2 or 3 (mod 4) and eventual period 4.Source: The setting · p. 9
- A run is a stretch of zeros spaced exactly four apart, and the capture point is the earliest endpoint of such a run with G gaps.The first zero in that run is s = z − 4G.Source: The setting · p. 9
- The pre-period µ is the least index after which xn+4 = xn always holds; equivalently, µ + 4 is the last index where xn differs from xn−4.Source: The setting · p. 9
The guess
The conjecture predicts that qualifying sequences enter the 4-cycle through a fixed pattern: their last disagreement is exactly two steps before capture, with terms thereafter in step with the cycle.
The guess
- For every k ≡ 2, 3 (mod 4) with NA(k) = 4, the conjecture says the last disagreement with the 4-cycle occurs exactly two steps before capture.After position z −2, xn = xn−4 for all n > z −2; the final run of length G is completed at capture.Source: The guess · p. 9
- The conjectured capture pattern means the sequence never reaches the cycle earlier or has a later mismatch.Capture “clicks in” as the final run of length G is completed.Source: The guess · p. 9
- For k ≡ 3 (mod 4), the conjecture reduces to the condition bs−5 = 0 and bs−1 = 1 just before the capturing run starts.The run’s middle entries are determined by values of b exactly k places back.Source: The guess · p. 9
The evidence
Reported examples span both residue classes; the pre-period ranges from 5 at k = 3 to 104,321,125,322 at k = 403, whose capture point is 104,321,125,328.
The evidence
- The pre-period ranges from 5 at k = 3 to 104,321,125,322 at k = 403, where the capture point is 104,321,125,328.The examples include k = 6, 10, 14, and 294 in the class 2 mod 4, and the remaining cited values in the class 3 mod 4; the passage proposes testing more k and investigating why capture follows the same narrow pattern.Source: The evidence · p. 10