4
$\begingroup$

Let $X$ be an infinite set and let $\text{End}(X)$ be the set of all functions $f:X\to X$. For $f\in\text{End}(X)$ let $$\text{fix}(f) = \{x\in X: x = f(x)\},$$ and $$\text{Com}(f) = \{g\in\text{End}(X): g\circ f = f \circ g\}.$$ It is not hard to prove that if $2^{|\text{fix}(f)|} > |X|$ then $|\text{Com}(f)|> |X|$. Does the converse hold?

EDIT: I forgot to include the condtion that $X$ is an infinite set - apologies.

$\endgroup$
1
  • 1
    $\begingroup$ Your last claim fails for $|X|=1$. $\endgroup$
    – Wojowu
    Dec 27, 2016 at 15:04

3 Answers 3

2
$\begingroup$

Let $X=\mathbf{N}$, $f:X\rightarrow X$ defined by $f(n)=0$ if $n$ even and $f(n)=1$ if $n$ odd. Then $f$ commutes with all elements of the set \begin{multline} G:=\{g:X\rightarrow X\colon g(0)=0, g(1)=1, g(2k+1)=2m+1, g(2l)=2n, \\k,l,m,n\in X, k,l>0\}. \end{multline} Obviously, $|G|=2^{|X|}$, thus $|\text{Com}(f)|\geq |G|=2^{|X|}>|X|>2^{|\text{fix}(f)|}$.

$\endgroup$
7
$\begingroup$

The answer is no, even if you consider only injective functions.

Consider any infinite cardinal $\kappa$, and let $X=\omega\times\kappa$ be the disjoint union of $\kappa$ many copies of $\omega$. Let $f:X\to X$ be the function that shifts within each copy separately. So $f$ has no fixed points. But meanwhile, for any subset $A$ of the copies of $\omega$, let $g_A$ be the function that shifts within the copies of $A$, but is the identity on the copies of $\omega$ not in $A$. So every $g_A$ commutes with $f$, and there are $2^\kappa$ many such $g_{A}$. So this is a counterexample to the converse implication, since $|\text{Com}(f)|=2^{\kappa}>\kappa$ but $2^{|\text{fix}(f)|}=1<\kappa$.

$\endgroup$
4
  • 2
    $\begingroup$ The following adapts Joel's answer for people not familiar with ordinals and cardinals: Let $f:\mathbf{N}\rightarrow\mathbf{N}$ permute $2n$ and $2n+1$. Let $A$ be any subset of the even numbers and $g_A:\mathbf{N}\rightarrow\mathbf{N}$ permute $2n$ and $2n+1$ for $n\in A$ and be the identity elsewhere. Then $f$ commutes with every $g_A$, the set of $g_A$'s being uncountable. $\endgroup$
    – Joel Adler
    Dec 28, 2016 at 9:13
  • $\begingroup$ Interesting! Can this example be used to find an uncountable family of functions from $\mathbb{N}$ to itself such that every member of that family commutes with every other member? $\endgroup$ Dec 28, 2016 at 9:43
  • 1
    $\begingroup$ @DominicvanderZypen The functions $g_A$ commute with each other. $\endgroup$
    – Goldstern
    Jan 1, 2017 at 11:46
  • $\begingroup$ Oh ok! So I guess we have a partial answer to this question: mathoverflow.net/questions/254049/… . It will be interesting to see whether all maximal commuting subsets have the same cardinality. Maybe you can shed some light on this? $\endgroup$ Jan 1, 2017 at 12:31
5
$\begingroup$

Let $n\ge4 $ and suppose that $|X|=n!-1 >2^n$, and that $f$ is a permutation of $X$ with exactly $n$ fixed points. Any permutation $g$ that permutes the fixed points of $f$ and fixes the non-fixed points of $f$ certainly commutes with $f$. Thus $|\mathrm{Com}(f)|\ge n!> |X| >2^{|\mathrm{fix(f)}|}$.

$\endgroup$
1
  • $\begingroup$ Sorry - can you adapt this to infinity...? I forgot to write this in the question... $\endgroup$ Dec 27, 2016 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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