Orbit finiteness vs. number of supported elements

A set is orbit finite if and only if the number of its elements supported by atoms grows polynomially with .

Consider any atoms that admit the representation theorem.

Call a set with atoms locally finite if every finite set of atoms supports only finitely many elements in it. Every orbit finite set is locally finite. The converse is not true; for example, in the equality atoms, the set of finite sets of atoms is not orbit finite, but it is locally finite, since every set of atoms supports all its subsets and nothing more.

For a locally finite set , let be the maximal number of elements of supported by a set of atoms.

The following might look surprising at first sight, but is actually very easy to prove:

Fact. A set is orbit finite if and only if it is locally finite and is bounded by a polynomial.

Proof. For the left-to-right implication, consider a single-orbit first; let be the dimension of (i.e., every element of has the least support of size ).  From the representation theorem (every element of is an equivalence class of a -tuple of atoms) it is clear that atoms can support at most elements.

For arbitrary orbit-finite , notice that a subset of is a tuple of subsets of the orbits of , and it is supported by a set of atoms if and only if every subset in that tuple is.

For the right-to-left implication, assume an orbit-infinite, but locally finite set . Being locally finite, it cannot have infinitely many orbits of the same dimension (if it had then a set of atoms would support infinitely many elements of ). This means that must have orbits of arbitrarily high dimension. It is easy to see that in an orbit of dimension , a set of atoms supports at least elements. As a consequence, the number of elements of supported by atoms is bounded from below by all , hence it is not bounded from above by any polynomial in .

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>