Uniform sets and complexity

For a nonempty closed subset ΩΩ of {0,1}Σ{0,1}Σ, where ΣΣ is a countably infinite set, let pΩ(S)≔#πSΩpΩ(S)≔#πSΩ be the complexity function depending on the nonempty finite sets S⊂ΣS⊂Σ, where ## denotes the number of elements in a set and πS:{0,1}Σ→{0,1}Sπ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,…k=1,2,….We call ΩΩ a uniform set if pΩ(S)pΩ(S) depends only on #S=k#S=k, and the complexity function pΩ(k)≔pΩ(S)pΩ(k)≔pΩ(S) as a function of k=1,2,…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̸}degΩ≔inf{d;Ω(d+1)=0̸} with Ω(1)=Ω′,Ω(2)=(Ω′)′,…Ω(1)=Ω′,Ω(2)=(Ω′)′,….We prove that for any nonempty closed subset ΩΩ of {0,1}N{0,1}N, where N={0,1,2,…}N={0,1,2,…}, such that deg(Ω∘ρ)<∞deg(Ω∘ρ)<∞ for some injection ρ:N→Nρ:N→N, there exists an increasing injection ϕ:N→Nϕ:N→N such that Ω∘ϕ∘ψ=Ω∘ϕΩ∘ϕ∘ψ=Ω∘ϕ for any increasing injection ψ:N→Nψ:N→N. Such a set Ω∘ϕΩ∘ϕ is called a super-stationary set. Moreover, if deg(Ω∘ρ)=∞deg(Ω∘ρ)=∞ for any injection ρ:N→Nρ:N→N, then pΩ∗(k)=2k(k=1,2,…) holds.A uniform set Ω⊂{0,1}ΣΩ⊂{0,1}Σ is said to have a primitive factor [Ω∘ϕ][Ω∘ϕ] if there exists an injection ϕ:N→Σϕ: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)pΩ(k) is either 2k2k for any kk or a polynomial function of kk for large kk.