Orbit finiteness vs. number of supported elements

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

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 {\cal P}_{\omega}\mathbb{A} 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 X, let \bar{X}(n) be the maximal number of elements of X supported by a set of n atoms.

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

Fact. A set X is orbit finite if and only if it is locally finite and \bar{X}(n) is bounded by a polynomial.

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

For arbitrary orbit-finite X, notice that a subset of X is a tuple of subsets of the orbits of X, 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 X. Being locally finite, it cannot have infinitely many orbits of the same dimension k (if it had then a set of k atoms would support infinitely many elements of X). This means that X must have orbits of arbitrarily high dimension. It is easy to see that in an orbit of dimension k, a set of n atoms supports at least {n}\choose{k} elements. As a consequence, the number of elements of X supported by n atoms is bounded from below by all {n}\choose{k}, hence it is not bounded from above by any polynomial in n.

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>