/-
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 FormalConjecturesUtilErdős Problem 192
References:
[ErGr79] Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory: van der Waerden's theorem and related topics. Enseign. Math. (1979), 325-344.
[ErGr80] Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).
[Ke92] Keränen, Veikko, Abelian squares are avoidable on $4$ letters. Automata, languages and programming (Vienna, 1992) (1992), 41-52.
[FiPu23] Fici, Gabriele and Puzynina, Svetlana, Abelian combinatorics on words: a survey. Comput. Sci. Rev. (2023), Paper No. 100532, 21.
@[expose] public sectionnamespace Erdos192A sequence $a_1, a_2, \ldots \in \mathbb{R}^d$ such that every difference $a_{i+1}-a_i$ is a positive unit vector $(0,\ldots,0,1,0,\ldots,0)$.
def IsPositiveUnitWalk {d : ℕ} (a : ℕ → Fin d → ℝ) : Prop :=
∀ n, ∃ i : Fin d, ∀ j, a (n + 1) j = a n j + if j = i then 1 else 0def erdos_192.answer : Set ℕ := Set.Iic 3Let $A={a_1,a_2,\ldots}\subset \mathbb{R}^d$ be an infinite sequence such that $a_{i+1}-a_i$ is a positive unit vector (i.e. is of the form $(0,0,\ldots,1,0,\ldots,0)$). For which $d$ must $A$ contain a three-term arithmetic progression?
This is true for $d\leq 3$ and false for $d\geq 4$.
This problem is equivalent to one on 'abelian squares' (see 231). In particular $A$ can be interpreted as an infinite string over an alphabet with $d$ letters (each letter describining which of the $d$ possible steps is taken at each point). An abelian square in a string $s$ is a pair of consecutive blocks $x$ and $y$ appearing in $s$ such that $y$ is a permutation of $x$. The connection comes from the observation that $p,q,r\in A\subset \mathbb{R}^d$ form a three-term arithmetic progression if and only if the string corresponding to the steps from $p$ to $q$ is a permutation of the string corresponding to the steps from $q$ to $r$.
This problem is therefore equivalent to asking for which $d$ there exists an infinite string over ${1,\ldots,d}$ with no abelian squares. An infinite string without abelian squares was constructed when $d=4$ by Keränen [Ke92]. We refer to a recent survey by Fici and Puzynina [FiPu23] for more background and related results.
@[category research solved, question value, AMS 5 11, formal_proof using lean4 at
"https://github.com/plby/lean-proofs/blob/8822f7ddef30fadbd92e1c6ab4ed897af356af5e/src/latest/ErdosProblems/Erdos192.lean#L39"]
theorem erdos_192 : {d : ℕ | ∀ a : ℕ → Fin d → ℝ, IsPositiveUnitWalk a →
∃ x ∈ Set.range a, ∃ y ∈ Set.range a, ∃ z ∈ Set.range a, x ≠ y ∧ ∀ j, x j + z j = 2 * y j} =
erdos_192.answer := ⊢ {d |
∀ (a : ℕ → Fin d → ℝ),
IsPositiveUnitWalk a →
∃ x ∈ Set.range a, ∃ y ∈ Set.range a, ∃ z ∈ Set.range a, x ≠ y ∧ ∀ (j : Fin d), x j + z j = 2 * y j} =
erdos_192.answer
All goals completed! 🐙end Erdos192