/-
Copyright 2025 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilThe Curling Number Conjecture
Reference: arxiv/0912.2382 The Curling Number Conjecture by Benjamin Chaffin and N. J. A. Sloane
@[expose] public sectionnamespace Arxiv.«0912.2382»The curling number
Let $S$ be a finite nonempty sequence of integers. By grouping adjacent terms, it is always possible to write it as $S = X Y Y . . . Y = X Y^k$, where $X$ and $Y$ are sequences of integers and $Y$ is nonempty ($X$ is allowed to be the empty sequence $∅$). There may be several ways to do this: choose the one that maximizes the value of $k$: this $k$ is the curling number of $S$, denoted by $k S$.
noncomputable def k (S : List ℤ) : ℕ :=
sSup {k : ℕ | ∃ X Y : List ℤ, Y ≠ [] ∧ S = X ++ (List.replicate k Y).flatten}A nonempty suffix repeated $r$ times uses at least $r$ entries.
@[category API, AMS 11]
theorem exponent_le_length {L X Y : List ℤ} {r : ℕ} (hY : Y ≠ [])
(hL : L = X ++ (List.replicate r Y).flatten) : r ≤ L.length := L:List ℤX:List ℤY:List ℤr:ℕhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flatten⊢ r ≤ L.length
L:List ℤX:List ℤY:List ℤr:ℕhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flattenhlen:L.length = (X ++ (List.replicate r Y).flatten).length⊢ r ≤ L.length
L:List ℤX:List ℤY:List ℤr:ℕhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flattenhlen:L.length = X.length + r * Y.length⊢ r ≤ L.length
L:List ℤX:List ℤY:List ℤr:ℕhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flattenhlen:L.length = X.length + r * Y.lengthhpos:1 ≤ Y.length⊢ r ≤ L.length
L:List ℤX:List ℤY:List ℤr:ℕhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flattenhlen:L.length = X.length + r * Y.lengthhpos:1 ≤ Y.lengthhmul:r * 1 ≤ r * Y.length⊢ r ≤ L.length
L:List ℤX:List ℤY:List ℤr:ℕhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flattenhlen:L.length = X.length + r * Y.lengthhpos:1 ≤ Y.lengthhmul:r ≤ r * Y.length⊢ r ≤ L.length
All goals completed! 🐙The admissible repetition counts in the definition of $k(L)$ are bounded.
@[category API, AMS 11]
theorem bddAbove_exponents (L : List ℤ) :
BddAbove {r : ℕ | ∃ X Y : List ℤ, Y ≠ [] ∧ L = X ++ (List.replicate r Y).flatten} := L:List ℤ⊢ BddAbove {r | ∃ X Y, Y ≠ [] ∧ L = X ++ (List.replicate r Y).flatten}
L:List ℤ⊢ L.length ∈ upperBounds {r | ∃ X Y, Y ≠ [] ∧ L = X ++ (List.replicate r Y).flatten}
L:List ℤr:ℕX:List ℤY:List ℤhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flatten⊢ r ≤ L.length
All goals completed! 🐙The curling number cannot exceed the length of the sequence, including the empty case.
@[category API, AMS 11]
theorem k_le_length (L : List ℤ) : k L ≤ L.length := L:List ℤ⊢ k L ≤ L.length
apply csSup_le (show ∃ r : ℕ, ∃ X Y : List ℤ,
Y ≠ [] ∧ L = X ++ (List.replicate r Y).flatten from ⟨0, L, [0], L:List ℤ⊢ [0] ≠ [] All goals completed! 🐙, L:List ℤ⊢ L = L ++ (List.replicate 0 [0]).flatten All goals completed! 🐙⟩)
L:List ℤr:ℕX:List ℤY:List ℤhY:Y ≠ []hL:L = X ++ (List.replicate r Y).flatten⊢ r ≤ L.length
All goals completed! 🐙Every nonempty sequence has curling number at least $1$.
@[category API, AMS 11]
theorem one_le_k {L : List ℤ} (hL : L ≠ []) : 1 ≤ k L := L:List ℤhL:L ≠ []⊢ 1 ≤ k L
exact le_csSup (bddAbove_exponents L) ⟨[], L, hL, L:List ℤhL:L ≠ []⊢ L = [] ++ (List.replicate 1 L).flatten All goals completed! 🐙⟩A nonempty sequence has a suffix repeated exactly its curling number of times.
L:List ℤhL:L ≠ []hne:{r | ∃ X Y, Y ≠ [] ∧ L = X ++ (List.replicate r Y).flatten}.Nonempty⊢ ∃ X Y, Y ≠ [] ∧ L = X ++ (List.replicate (k L) Y).flatten
exact Nat.sSup_mem hne (bddAbove_exponents L) All goals completed! 🐙One starts with any initial sequence of integers $S₀$, and extends it by repeatedly appending the curling number of the current sequence.
noncomputable def S (S₀ : List ℤ) (n : ℕ) : List ℤ :=
match n with
| 0 => S₀
| n + 1 => (S S₀ n) ++ [Int.ofNat (k (S S₀ n))]Each extension step appends exactly one integer.
@[category API, AMS 11]
theorem S_length (L : List ℤ) (n : ℕ) : (S L n).length = L.length + n := by L:List ℤn:ℕ⊢ (S L n).length = L.length + n
induction n with
| zero => zero L:List ℤ⊢ (S L 0).length = L.length + 0 simp [S] All goals completed! 🐙
| succ n ih => succ L:List ℤn:ℕih:(S L n).length = L.length + n⊢ (S L (n + 1)).length = L.length + (n + 1) simp [S, ih, Nat.add_assoc] All goals completed! 🐙Extending a nonempty initial sequence preserves nonemptiness.
@[category API, AMS 11]
theorem S_ne_nil {L : List ℤ} (hL : L ≠ []) (n : ℕ) : S L n ≠ [] := by L:List ℤhL:L ≠ []n:ℕ⊢ S L n ≠ []
have hpos := List.length_pos_iff.mpr hL L:List ℤhL:L ≠ []n:ℕhpos:0 < L.length⊢ S L n ≠ []
have hlen := S_length L n L:List ℤhL:L ≠ []n:ℕhpos:0 < L.lengthhlen:(S L n).length = L.length + n⊢ S L n ≠ []
intro h L:List ℤhL:L ≠ []n:ℕhpos:0 < L.lengthhlen:(S L n).length = L.length + nh:S L n = []⊢ False
simp only [h, List.length_nil] at hlen L:List ℤhL:L ≠ []n:ℕhpos:0 < L.lengthh:S L n = []hlen:0 = L.length + n⊢ False
omega All goals completed! 🐙A one-term sequence has curling number $1$, regardless of the integer in it.
@[category test, AMS 11]
theorem k_singleton (a : ℤ) : k [a] = 1 := by a:ℤ⊢ k [a] = 1
have hle := k_le_length [a] a:ℤhle:k [a] ≤ [a].length⊢ k [a] = 1
have hge := one_le_k (by a:ℤhle:k [a] ≤ [a].length⊢ [a] ≠ [] a:ℤhle:k [a] ≤ [a].lengthhge:1 ≤ k [a]⊢ k [a] = 1 simp All goals completed! 🐙 a:ℤhle:k [a] ≤ [a].lengthhge:1 ≤ k [a]⊢ k [a] = 1 : [a] ≠ []) a:ℤhle:k [a] ≤ [a].lengthhge:1 ≤ k [a]⊢ k [a] = 1
simp only [List.length_singleton] at hle a:ℤhle:k [a] ≤ 1hge:1 ≤ k [a]⊢ k [a] = 1
omega All goals completed! 🐙The conjecture holds immediately for every one-term starting sequence.
@[category test, AMS 11]
theorem curling_number_conjecture_singleton (a : ℤ) : ∃ m, k (S [a] m) = 1 := by a:ℤ⊢ ∃ m, k (S [a] m) = 1
exact ⟨0, k_singleton a⟩ All goals completed! 🐙Starting from any nonempty finite integer sequence, repeatedly appending its curling number eventually gives a sequence with curling number $1$ [Chaffin and Sloane, Conjecture 1].
@[category research open, AMS 11]
theorem curling_number_conjecture (S₀ : List ℤ) (h : S₀ ≠ []) : ∃ m, k (S S₀ m) = 1 := by S₀:List ℤh:S₀ ≠ []⊢ ∃ m, k (S S₀ m) = 1
sorry All goals completed! 🐙end Arxiv.«0912.2382»