Parity positions in the Sobolewski–Ulas meta-Fibonacci sequence

Abstract

Both parity-position sequences of h(1,1) have finitely generated binary-kernel spans.

Definition 1.1 (The nested recurrence).

$$\begin{array}{r}h\left(0\right)=1\\ h\left(1\right)=1\\ \forall n\in \mathrm{Nat},h\left(n+2\right)=h\left(\min \left(n+2-h\left(n+1\right),n+1\right)\right)+h\left(n\right)\end{array}$$

Formalization. D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.h (✓ std3).

Citation. Bartosz Sobolewski and Maciej Ulas (2022). Solutions of certain meta-Fibonacci recurrences. DOI: 10.4064/aa220613-19-1. URL: https://arxiv.org/abs/2204.04011v1.

Commentary.

Page 4: “We write h(n) = h_{1,1}(n) and in the sequel, we consider the sequence h = (h(n)){n∈ℕ}.” Page 3 defines h{a,b}; taking a=b=1 gives h(n)=1 for n≤1 and h(n)=h(n−h(n−1))+h(n−2) for n>1. Natural subtraction sends a negative argument to zero, where h is one. Positivity makes the minimum in the recursive definition select its first argument.

Definition 1.2 (Parity).

$$\forall n\in \mathrm{Nat},r\left(n\right)=Nat.mod\left(h\left(n\right),2\right)$$

Formalization. D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.r (✓ std3).

Citation. Bartosz Sobolewski and Maciej Ulas (2022). Solutions of certain meta-Fibonacci recurrences. DOI: 10.4064/aa220613-19-1. URL: https://arxiv.org/abs/2204.04011v1.

Commentary.

Page 8: “Let us write r(n) = h(n) (mod 2).” Values are natural numbers zero and one.

Definition 1.3 (Increasing occurrence enumerations).

$$\forall i\in \mathrm{Nat},\forall n\in \mathrm{Nat},u\left(i,n\right)=Nat.nth\left(\mathrm{fun}m:\mathrm{Nat}\mapsto (r\left(m\right)=i),n\right)$$

Formalization. D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.u (✓ std3).

Citation. Bartosz Sobolewski and Maciej Ulas (2022). Solutions of certain meta-Fibonacci recurrences. DOI: 10.4064/aa220613-19-1. URL: https://arxiv.org/abs/2204.04011v1.

Commentary.

Page 16, Question 7.5: “Let u_i = (u_i(n)) for i = 0, 1 be the increasing sequence of nonnegative integers such that r(u_i(n)) = i. Is the sequence u_i is k-regular for some k?” Nat.nth lists the nonnegative positions in increasing order, starting with index zero. Each aligned block of sixteen positions contains eight positions of each parity, so both enumerations are infinite.

Definition 1.4 (The k-kernel).

$$\forall k\in \mathrm{Nat},\forall a\in \mathrm{Nat}\to \mathbb{Z},\mathrm{kKernel}\left(k,a\right)=\{f:\mathrm{Nat}\to \mathbb{Z}\mid \exists j\in \mathrm{Nat},\exists i\in \mathrm{Nat},i<k^j\wedge f=\mathrm{fun}n:\mathrm{Nat}\mapsto (a\left(k^j\cdot n+i\right))\}$$

Formalization. D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.kKernel (✓ std3).

Citation. Bartosz Sobolewski and Maciej Ulas (2022). Solutions of certain meta-Fibonacci recurrences. DOI: 10.4064/aa220613-19-1. URL: https://arxiv.org/abs/2204.04011v1.

Commentary.

Section 2, page 4: “Let k ≥ 2 be a fixed integer.” The k-kernel is “K_k(a) = {(a_{k^j n+i})_{n∈ℕ} : j ∈ ℕ, 0 ≤ i < k^j}”. The carrier here is the space of integer-valued sequences.

Definition 1.5 (Finite generation of the kernel span).

$$\forall k\in \mathrm{Nat},\forall a\in \mathrm{Nat}\to \mathbb{Z},\mathrm{IsKRegular}\left(k,a\right)\iff (Submodule.span\left(\mathbb{Z},\mathrm{kKernel}\left(k,a\right)\right)).FG$$

Formalization. D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.IsKRegular (✓ std3).

Citation. Bartosz Sobolewski and Maciej Ulas (2022). Solutions of certain meta-Fibonacci recurrences. DOI: 10.4064/aa220613-19-1. URL: https://arxiv.org/abs/2204.04011v1.

Commentary.

Section 2, page 4: “In other words, the ℤ-submodule generated by K_k(a) is finitely generated.” Submodule.FG expresses finite generation over ℤ.

Definition 1.6 (Question 7.5).

$$claim\iff \left(\forall i\in \mathrm{Nat},i<2\Rightarrow \left(\exists k\in \mathrm{Nat},2\le k\wedge \mathrm{IsKRegular}\left(k,\mathrm{fun}n:\mathrm{Nat}\mapsto ((u\left(i,n\right):\mathbb{Z}))\right)\right)\right)$$

Formalization. D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.claim (✓ std3).

Citation. Bartosz Sobolewski and Maciej Ulas (2022). Solutions of certain meta-Fibonacci recurrences. DOI: 10.4064/aa220613-19-1. URL: https://arxiv.org/abs/2204.04011v1.

Commentary.

Page 16, Question 7.5: “Let u_i = (u_i(n)) for i = 0, 1 be the increasing sequence of nonnegative integers such that r(u_i(n)) = i. Is the sequence u_i is k-regular for some k?” The variable i ranges over zero and one; the base k is at least two, as required in Section 2. Natural positions are cast to ℤ.

Theorem 1.7 (Both occurrence enumerations are regular).

$$\forall i\in \mathrm{Nat},i<2\Rightarrow \left(\exists k\in \mathrm{Nat},2\le k\wedge \mathrm{IsKRegular}\left(k,\mathrm{fun}n:\mathrm{Nat}\mapsto ((u\left(i,n\right):\mathbb{Z}))\right)\right)$$

Proof. Machine-checked in Lean as D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.result (✓ std3). ∎

Resolves. Problems/sobolewski-ulas-2022-meta-fibonacci-parity-positions-question-7-5 (proved) by D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.result.

Source. Repository-derived.

Acknowledgement. Bartosz Sobolewski and Maciej Ulas (2022). Solutions of certain meta-Fibonacci recurrences. DOI: 10.4064/aa220613-19-1. URL: https://arxiv.org/abs/2204.04011v1.

Commentary.

The proof chooses k=2 for both parities. Odd-index and even-index identities for h yield an exact parity table for each block of length sixteen. Every block contains eight zeros and eight ones. Thus the nth position is twice n plus an integer correction obtained by selecting within a block. The correction is the output of a finite state space stable under n↦2n and n↦2n+1, so its binary kernel is finite. Every binary-kernel sequence of the position enumeration lies in the ℤ-span of this finite kernel, the constant sequence one, and the sequence n↦n. A submodule of this finitely generated ℤ-module is finitely generated. This concerns h_{1,1} and its two parity classes; it asserts nothing about other parameters or moduli.

References

• Truth anchor: D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.IsKRegular
• Truth anchor: D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.claim
• Truth anchor: D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.h
• Truth anchor: D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.kKernel
• Truth anchor: D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.r
• Truth anchor: D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.result
• Truth anchor: D5/S1/Recurrence/MetaFibonacci/SobolewskiUlasParityPositions.u
• Dependency: D5/S1/Words/Palindromes/PeriodDoubling/SparseKernelRank