2
$\begingroup$

I stumbled upon a funny fact:

Let $\mathbf{Bool} = \{0, 1 \}$. For all functions $f: \mathbf{Bool} \to \mathbf{Bool}$ it is the case that $f^3 = f$.

This got me excited and I was wondering whether there's anything similar for endofunctions on finite sets, but I quickly realised it does not generalise (at least in the straightforward way) to any larger cases.

So, I have two questions:

  1. Does this generalise in some way to endomorphisms on larger finite sets?
  2. Is there any "deeper" reason why the fact holds for boolean endomorphisms?

Thanks!

$\endgroup$
3
  • $\begingroup$ I edited to say "for all functions", I hope it makes it clearer. $\endgroup$ – yfyf Nov 25 '13 at 0:29
  • 1
    $\begingroup$ There's nothing deeper going on than "two is very small." An endomorphism of a two-element set is either a bijection or an idempotent, and this is very far from true for larger sets. $\endgroup$ – Qiaochu Yuan Nov 25 '13 at 0:59
  • $\begingroup$ Well, I was actually thinking along the same lines, but still wanted to get a confirmation. $\endgroup$ – yfyf Nov 25 '13 at 19:52
3
$\begingroup$

If we restrict our attention to bijections $f: S\rightarrow S$ of a set $S$ of size $n$, then elementary group theory tells us that $f^{n!+1} = f$.

While it is not true that for every function $f:S\rightarrow S$ there is some $m$ such that $f^m = f$, it is true that for every such function there are some $m \neq k$ and $k < n$ so that $f^m = f^k$. The reason for this is that $f^k$ must be a bijection on $f^k(S)$ for some $k < n$ (because $f^{p+1}(S) \subseteq f^p(S)$, and this can only be decreasing for so long before it is constant). Then apply the above observation to $f^k$.

$\endgroup$
2
  • $\begingroup$ Presumably you don't actually mean "for some $m\neq k$ and $k<n$". Maybe $k<n!$? Is there a tighter bound that works? $\endgroup$ – mjqxxxx Nov 25 '13 at 1:28
  • $\begingroup$ I do mean $k<n$, but you are correct that one could place a bound ($n!+1$ should work) on $m$ as well. $\endgroup$ – universalset Nov 25 '13 at 1:37
1
$\begingroup$

For this answer, let $X$ be a set with $n$ elements. A little bit of group theory shows us that, for any bijection $f: X\mapsto X$, $f^{n!+1} = f$ (because $f^{n!} = \operatorname{id}_X$). However, for $n>2$, this does not hold for arbitrary functions. We can see why by considering the restriction of $f$ onto its image.

If the restriction $f|_{\operatorname{im}f}$ is bijective, then we have that, if $m=|\operatorname{im}f|$, $(f|_{\operatorname{im}f})^{m!} = \operatorname{id}_{\operatorname{im} f}$. Since $m!|n!$, and, for any $a$, $f(a) \in \operatorname{im} f$, we then have that $f^{n!+1} = f$.

The reason that this holds for any $f: \mathbf{Bool} \mapsto \mathbf{Bool}$, then, is that $\mathbf{Bool}$ has only two elements, and so any such $f$ is either a bijection, or has an image of size one, and so the restriction onto the image must be a bijection.

Interestingly, for any $f$ that is not bijective on its image, there can be no $k$ such that $f^{k} = f$. This is because, if $f|_{\operatorname{im}f}$ is not bijective, then $\operatorname{im}f^k \subset \operatorname{im}f$ for all $k$, so those functions cannot be equal. Therefore, we have the following result:

If, for a given $f: X\mapsto X$, there exists a $k$ such that $f^k = f$, then $f^{|X|!+1}=f$.

$\endgroup$
0
$\begingroup$

Actually, a slightly more precise result holds: every function $f$ from $\{0,1\}$ into itself satisfies either $f^2 = Id$ or $f^2 = f$. This property is actually a combination of two properties of functions from $\{0, ..., n-1\}$ into itself:

  1. If $f$ is a bijection, then $f^{n!} = Id$ and hence $f^{n! + 1} = f$.
  2. If $f$ is a constant map, then $f^2 = f$.

Related result: given a finite semigroup $S$, there exists an integer $n$ such that for all $x \in S$, $(x^n)^2 = x^n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.