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.

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

3 Answers 3

Reset to default
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)|}$.

Improve this answer
$\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$.

Improve this answer
$\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
    Commented 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$
    – Dominic van der Zypen
    Commented Dec 28, 2016 at 9:43
  • 1
    $\begingroup$ @DominicvanderZypen The functions $g_A$ commute with each other. $\endgroup$
    – Goldstern
    Commented 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$
    – Dominic van der Zypen
    Commented 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)}|}$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Sorry - can you adapt this to infinity...? I forgot to write this in the question... $\endgroup$
    – Dominic van der Zypen
    Commented Dec 27, 2016 at 15:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .