Problem 1643

For any function $g: \mathbb{Z}_{>0} \rightarrow \mathbb{Z}_{>0}$ and any subset $X \subset \mathbb{Z}_{>0}$, we define $g(X) = \{g(x): x \in X\}$. We have that the image of $f_{X}$ is $f_{X}(\mathbb{Z}_{>0}) = \mathbb{Z}_{>0} \backslash X$. We now show a general lemma about the operation *, with the goal of showing that * is associative. Lemma 1. Let $X$ and $Y$ be finite sets of positive integers. The functions $f_{X * Y}$ and $f_{X} \circ f_{Y}$ are equal. Proof. We have $f_{X * Y}(\mathbb{Z}_{>0}) = \mathbb{Z}_{>0} \backslash (X * Y) = (\mathbb{Z}_{>0} \backslash X) \backslash f_{X}(Y) = f_{X}(\mathbb{Z}_{>0}) \backslash f_{X}(Y) = f_{X}(\mathbb{Z}_{>0} \backslash Y) = f_{X}(f_{Y}(\mathbb{Z}_{>0}))$. Thus, the functions $f_{X * Y}$ and $f_{X} \circ f_{Y}$ are strictly increasing functions with the same range. Because a strictly increasing function is uniquely defined by its range, we have $f_{X * Y} = f_{X} \circ f_{Y}$. Lemma 1 implies that * is associative, in the sense that $(A * B) * C = A * (B * C)$ for any finite sets $A, B$, and $C$ of positive integers. We prove the associativity by noting
$$\begin{gathered} \mathbb{Z}_{>0} \backslash ((A * B) * C) = f_{(A * B) * C}(\mathbb{Z}_{>0}) = f_{A * B}(f_{C}(\mathbb{Z}_{>0})) = f_{A}(f_{B}(f_{C}(\mathbb{Z}_{>0}))) \\ = f_{A}(f_{B * C}(\mathbb{Z}_{>0})) = f_{A * (B * C)}(\mathbb{Z}_{>0}) = \mathbb{Z}_{>0} \backslash (A * (B * C)) \end{gathered}$$
In light of the associativity of *, we may drop the parentheses when we write expressions like $A * (B * C)$. We also introduce the notation
$$X^{* k} = \underbrace{X * (X * \cdots * (X * (X * X)) \ldots)}_{X \text{ appears } k \text{ times}}$$
Our goal is then to show that $A * B = B * A$ implies $A^{* b} = B^{* a}$. We will do so via the following general lemma. Lemma 2. Suppose that $X$ and $Y$ are finite sets of positive integers satisfying $X * Y = Y * X$ and $|X| = |Y|$. Then, we must have $X = Y$. Proof. Assume that $X$ and $Y$ are not equal. Let $s$ be the largest number in exactly one of $X$ and $Y$. Without loss of generality, say that $s \in X \backslash Y$. The number $f_{X}(s)$ counts the $s^{\text{th}}$ number not in $X$, which implies that
$$f_{X}(s) = s + |X \cap \{1, 2, \ldots, f_{X}(s)\}|$$
Since $f_{X}(s) \geq s$, we have that
$$\{f_{X}(s) + 1, f_{X}(s) + 2, \ldots\} \cap X = \{f_{X}(s) + 1, f_{X}(s) + 2, \ldots\} \cap Y$$
which, together with the assumption that $|X| = |Y|$, gives
$$|X \cap \{1, 2, \ldots, f_{X}(s)\}| = |Y \cap \{1, 2, \ldots, f_{X}(s)\}|$$
Now consider the equation
$$t - |Y \cap \{1, 2, \ldots, t\}| = s$$
This equation is satisfied only when $t \in [f_{Y}(s), f_{Y}(s+1))$, because the left hand side counts the number of elements up to $t$ that are not in $Y$. We have that the value $t = f_{X}(s)$ satisfies the above equation because of (1) and (2). Furthermore, since $f_{X}(s) \notin X$ and $f_{X}(s) \geq s$, we have that $f_{X}(s) \notin Y$ due to the maximality of $s$. Thus, by the above discussion, we must have $f_{X}(s) = f_{Y}(s)$.

Finally, we arrive at a contradiction. The value $f_{X}(s)$ is neither in $X$ nor in $f_{X}(Y)$, because $s$ is not in $Y$ by assumption. Thus, $f_{X}(s) \notin X * Y$. However, since $s \in X$, we have $f_{Y}(s) \in Y * X$, a contradiction.

We are now ready to finish the proof. Note first of all that $|A^{* b}| = ab = |B^{* a}|$. Moreover, since $A * B = B * A$, and * is associative, it follows that $A^{* b} * B^{* a} = B^{* a} * A^{* b}$. Thus, by Lemma 2, we have $A^{* b} = B^{* a}$, as desired.

Comment 1. Taking $A = X^{* k}$ and $B = X^{* l}$ generates many non-trivial examples where $A * B = B * A$. There are also other examples not of this form. For example, if $A = \{1, 2, 4\}$ and $B = \{1, 3\}$, then $A * B = \{1, 2, 3, 4, 6\} = B * A$.