/- Copyright 2026 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 FormalConjecturesUtil

Balanced walks on a 4-dimensional cubic lattice with neighbor steps

The sequence $a(n)$ counts the words over a $4$-ary alphabet (either empty or starting with the first letter) in which each letter occurs $n$ times and adjacent letters are equal or adjacent in the alphabet. Equivalently, $$a(n) = \sum_{k=0}^{n-1} \binom{n}{k} \binom{n-1}{k} \binom{n+k-1}{k}^2$$ for $n \ge 1$ and $a(0) = 1$.

References:

@[expose] public sectionnamespace OeisA212334

Number of words over a $4$-ary alphabet where each letter occurs $n$ times and adjacent letters are equal or neighbors, given by $a(n) = \sum_{k=0}^{n-1} \binom{n}{k} \binom{n-1}{k} \binom{n+k-1}{k}^2$ for $n \ge 1$ and $a(0) = 1$.

def a (n : ℕ) : ℕ := if n = 0 then 1 else ∑ k ∈ Finset.range n, n.choose k * (n - 1).choose k * (n + k - 1).choose k ^ 2@[category test, AMS 11] theorem a_0 : a 0 = 1 := ⊢ a 0 = 1 All goals completed! 🐙@[category test, AMS 11] theorem a_1 : a 1 = 1 := ⊢ a 1 = 1 All goals completed! 🐙@[category test, AMS 11] theorem a_2 : a 2 = 9 := ⊢ a 2 = 9 All goals completed! 🐙@[category test, AMS 11] theorem a_3 : a 3 = 163 := ⊢ a 3 = 163 All goals completed! 🐙@[category test, AMS 11] theorem a_4 : a 4 = 3593 := ⊢ a 4 = 3593 All goals completed! 🐙

"It appears that for primes $p \ge 5$, $a(p) \equiv 1 \pmod{p^5}$."

    Peter Bala, Dec 12 2021

@[category research open, AMS 11] theorem conjecture_1 (p : ℕ) (hp : p.Prime) (hp5 : 5 ≤ p) : a p % (p ^ 5) = 1 := p:ℕhp:Nat.Prime php5:5 ≤ p⊢ a p % p ^ 5 = 1 All goals completed! 🐙

"Conjecture: for $r \ge 2$, and all primes $p \ge 5$, $a(p^r) \equiv a(p^{r-1}) \pmod{p^{3r+3}}$."

    Peter Bala, Oct 13 2022

@[category research open, AMS 11] theorem conjecture_2 (p r : ℕ) (hp : p.Prime) (hp5 : 5 ≤ p) (hr2 : 2 ≤ r) : a (p ^ r) % (p ^ (3 * r + 3)) = a (p ^ (r - 1)) % (p ^ (3 * r + 3)) := p:ℕr:ℕhp:Nat.Prime php5:5 ≤ phr2:2 ≤ r⊢ a (p ^ r) % p ^ (3 * r + 3) = a (p ^ (r - 1)) % p ^ (3 * r + 3) All goals completed! 🐙end OeisA212334