leanprover-community / leanprover-community/mathlib4
API development for `LanguageOn` in symbolic dynamics
Nobody has claimed this yet.
- Dominant language
- Lean
- Stars
- 4.1k
- Forks
- 1.7k
- PR merge metrics
- No merged PRs in 30d
Description
This issue collects planned basic properties of the language of a subshift. The goal is to gradually build a small, reusable API for symbolic dynamics in the ambient full shift setting, consistent with the current design philosophy of avoiding subshift-relative definitions.
1. Basic monotonicity and functoriality
For subsets of configurations:
- Monotonicity
$X \subseteq Y \Rightarrow \mathcal{L}_U(X) \subseteq \mathcal{L}_U(Y)$
This will be the object of the first PR.
- Union compatibility
$\mathcal{L}_U(X \cup Y) = \mathcal{L}_U(X) \cup \mathcal{L}_U(Y)$
- Intersection inclusion
$\mathcal{L}_U(X \cap Y) \subseteq \mathcal{L}_U(X) \cap \mathcal{L}_U(Y)$
(equality is not expected in general)
2. Interaction with restriction in the shape
For finite shapes U ⊆ V, we have compatibility with restriction of patterns:
- Natural restriction map:
$\mathcal{L}_V(X) \to \mathcal{L}_U(X)$
induced by restricting patterns from V to U.
This should make the family (𝓛_U(X))_U functorial in the finite set U.
3. Interaction with subshifts
For a subshift Y : Subshift A G:
𝓛_U(Y)is defined via the carrierY.carrier, hence inherits ambient properties.
Potential lemmas include:
- compatibility of language with shift invariance (at the level of induced patterns),
- stability under inclusion of subshifts:
$Y_1 \subseteq Y_2 \Rightarrow \mathcal{L}_U(Y_1) \subseteq \mathcal{L}_U(Y_2)$
This is expected to become relevant for later development of subshift classification and entropy.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by locating the existing LanguageOn definition and the Subshift A G carrier used in the issue. Implement and verify the first planned property, monotonicity for subsets, before addressing the later union, restriction, or subshift lemmas.
Written by the indexing model from the issue text.
Assessment
- Domain
- backend-api-design
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100