Uniform sets and complexity

AbstractFor a nonempty closed subset Ω of {0,1}Σ, where Σ is a countably infinite set, let pΩ(S)≔#πSΩ be the complexity function depending on the nonempty finite sets S⊂Σ, where # denotes the number of elements in a set and πS:{0,1}Σ→{0,1}S is the projection. Define the maximal pattern complexity function pΩ∗(k)≔supS;#S=kpΩ(S) as a function of k=1,2,….We call Ω a uniform set if pΩ(S) depends only on #S=k, and the complexity function pΩ(k)≔pΩ(S) as a function of k=1,2,… is called the uniform complexity function of Ω. Of course, we have pΩ(k)=pΩ∗(k) in this case.Such uniform sets appear, for example, as the partitions generated by congruent sets in a space with optimal positionings, or they appear as the restrictions of a symbolic system to optimal windows.Let Ω′ be the derived set (i.e. the set of accumulating points) of Ω and degΩ≔inf{d;Ω(d+1)=0̸} with Ω(1)=Ω′,Ω(2)=(Ω′)′,….We prove that for any nonempty closed subset Ω of {0,1}N, where N={0,1,2,…}, such that deg(Ω∘ρ)<∞ for some injection ρ:N→N, there exists an increasing injection ϕ:N→N such that Ω∘ϕ∘ψ=Ω∘ϕ for any increasing injection ψ:N→N. Such a set Ω∘ϕ is called a super-stationary set. Moreover, if deg(Ω∘ρ)=∞ for any injection ρ:N→N, then pΩ∗(k)=2k(k=1,2,…) holds.A uniform set Ω⊂{0,1}Σ is said to have a primitive factor [Ω∘ϕ] if there exists an injection ϕ:N→Σ such that Ω∘ϕ is a super-stationary set, where [Ω∘ϕ] is the isomorphic class containing Ω∘ϕ. Then, any uniform set has at least one primitive factor, and hence, any uniform complexity function is realized by the uniform complexity function of a super-stationary set. It follows that the uniform complexity function pΩ(k) is either 2k for any k or a polynomial function of k for large k