Maximal pattern complexity, dual system and pattern recognition

For a family ΩΩ of sets in R2R2 and a finite subset SS of R2R2, let pΩ(S)pΩ(S) be the number of distinct sets of the form S∩ωS∩ω for all ω∈Ωω∈Ω. The maximum pattern complexity pΩ∗(k) is the maximum of pΩ(S)pΩ(S) among SS with #S=k#S=k. The SS attaining the maximum is considered as the most effective sampling to distinguish the sets in ΩΩ. We obtain the exact values or at least the order of pΩ∗(k) in kk for various classes ΩΩ. We also discuss the dual problem in the case that #Ω=∞#Ω=∞, that is, consider the partition of R2R2 generated by a finite family T⊂ΩT⊂Ω. The number of elements in the partition is written as pR2(T)pR2(T) and pR2∗(k) is the maximum of pR2(T)pR2(T) among TT with #T=k#T=k. Here, pΩ∗(k)=pR2∗(k) does not hold in general.For the general setting that ΩΩ is an infinite subset of AΣAΣ, where AA is a finite alphabet, ΣΣ is an arbitrary infinite set, and pΩ∗(k)=max#S=k#Ω∣S, it is known that the entropy h(Ω):=limk→∞logpΩ∗(k)/k exists and takes value in {log1,log2,…,log#A}. In this paper, we prove that the entropy h(Σ)h(Σ) of the dual system coincides with h(Ω)h(Ω).