Putnam 2008, Problem A-3

Start with a finite sequence $a_1, a_2, \ldots, a_n$ of positive integers. If possible, choose two indices $j < k$ such that $a_j$ does not divide $a_k$, and replace $a_j$ and $a_k$ by $\gcd(a_j, a_k)$ and $\operatorname{lcm}(a_j, a_k)$, respectively. Prove that if this process is repeated, it must eventually stop and the final sequence does not depend on the choices made. (Note: $\gcd$ means greatest common divisor and $\operatorname{lcm}$ means least common multiple.)

Solution:
We first prove that the process stops. Note first that the product $a_1 \cdots a_n$ remains constant, because $a_j a_k = \gcd(a_j,a_k) \operatorname{lcm}(a_j,a_k)$. Moreover, the last number in the sequence can never decrease, because it is always replaced by its least common multiple with another number. Since it is bounded above (by the product of all of the numbers), the last number must eventually reach its maximum value, after which it remains constant throughout. After this happens, the next-to-last number will never decrease, so it eventually becomes constant, and so on. After finitely many steps, all of the numbers will achieve their final values, so no more steps will be possible. This only happens when $a_j$ divides $a_k$ for all pairs $j < k$.

We next check that there is only one possible final sequence. For $p$ a prime and $m$ a nonnegative integer, we claim that the number of integers in the list divisible by $p^m$ never changes. To see this, suppose we replace $a_j, a_k$ by $\gcd(a_j,a_k), \operatorname{lcm}(a_j,a_k)$. If neither of $a_j, a_k$ is divisible by $p^m$, then neither of $\gcd(a_j,a_k), \operatorname{lcm}(a_j,a_k)$ is either. If exactly one $a_j, a_k$ is divisible by $p^m$, then $\operatorname{lcm}(a_j,a_k)$ is divisible by $p^m$ but $\gcd(a_j,a_k)$ is not. $\gcd(a_j,a_k), \operatorname{lcm}(a_j,a_k)$ are as well.

If we started out with exactly $h$ numbers not divisible by $p^m$, then in the final sequence $a_1', \ldots, a_n'$, the numbers $a_{h+1}', \ldots, a_n'$ are divisible by $p^m$ while the numbers $a_1', \ldots, a_h'$ are not. Repeating this argument for each pair $(p,m)$ such that $p^m$ divides the initial product $a_1, \ldots, a_n$, we can determine the exact prime factorization of each of $a_1', \ldots, a_n'$. This proves that the final sequence is unique.

**Remark:** (by David Savitt and Noam Elkies) Here are two other ways to prove the termination. One is to observe that $\prod_j a_j^j$ is strictly increasing at each step, and bounded above by $(a_1 \cdots a_n)^n$. The other is to notice that $a_1$ is nonincreasing but always positive, so eventually becomes constant; then $a_2$ is nonincreasing but always positive, and so on.

**Reinterpretation:** For each $p$, consider the sequence consisting of the exponents of $p$ in the prime factorizations of $a_1, \ldots, a_n$. At each step, we pick two positions $i$ and $j$ such that the exponents of some prime $p$ are in the wrong order at positions $i$ and $j$. We then sort these two position into the correct order for every prime $p$ simultaneously.

It is clear that this can only terminate with all sequences being sorted into the correct order. We must still check that the process terminates; however, since all but finitely many of the exponent sequences consist of all zeroes, and each step makes a nontrivial switch in at least one of the other exponent sequences, it is enough to check the case of a single exponent sequence. This can be done as in the first solution.

**Remark:** Abhinav Kumar suggests the following proof that the process always terminates in at most $\binom{n}{2}$ steps. (This is a variant of the worst-case analysis of the bubble sort algorithm.)

Consider the number of pairs $(k,l)$ with $1 \leq k < l \leq n$ such that $a_k$ does not divide $a_l$ (call these bad pairs). At each step, we find one bad pair $(i,j)$ and eliminate it, and we do not touch any pairs that do not involve either $i$ or $j$. If $i < k < j$, then neither of the pairs $(i,k)$ and $(k,j)$ can become bad, because $a_i$ is replaced by a divisor of itself, while $a_j$ is replaced by a multiple of itself. If $k < i$, then $(k,i)$ can only become a bad pair if $a_k$ divided $a_i$ but not $a_j$, in which case $(k,j)$ stops being bad. Similarly, if $k > j$, then $(i,k)$ and $(j,k)$ either stay the same or switch status. Hence the number of bad pairs goes down by at least 1 each time; since it is at most $\binom{n}{2}$ to begin with, this is an upper bound for the number of steps.

**Remark:** This problem is closely related to the classification theorem for finite abelian groups. Namely, if $a_1, \ldots, a_n$ and $a_1', \ldots, a_n'$ are the sequences obtained at two different steps in the process, then the abelian groups $\mathbb{Z}/a_1\mathbb{Z} \times \cdots \times \mathbb{Z}/a_n\mathbb{Z}$ and $\mathbb{Z}/a_1'\mathbb{Z} \times \cdots \times \mathbb{Z}/a_n'\mathbb{Z}$ are isomorphic. The final sequence gives a canonical presentation of this group; the terms of this sequence are called the elementary divisors or invariant factors of the group.

**Remark:** (by Tom Belulovich) A lattice is a partially ordered set $L$ in which for any two $x,y \in L$, there is a unique minimal element $z$ with $z \geq x$ and $z \geq y$, called the join and denoted $x \vee y$, and there is a unique maximal element $z$ with $z \leq x$ and $z \leq y$, called the meet and denoted $x \wedge y$. In terms of a lattice $L$, one can pose the following generalization of the given problem. Start with $a_1, \ldots, a_n \in L$. If $i < j$ but $a_i \not\leq a_j$, it is permitted to replace $a_i, a_j$ by $a_i \vee a_j, a_i \wedge a_j$, respectively. The same argument as above shows that this always terminates in at most $\binom{n}{2}$ steps. The question is, under what conditions on the lattice $L$ is the final sequence uniquely determined by the initial sequence?

It turns out that this holds if and only if $L$ is distributive, i.e., for any $x,y,z \in L$,
$$x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z).$$

(This is equivalent to the same axiom with the operations interchanged.) For example, if $L$ is a Boolean algebra, i.e., the set of subsets of a given set $S$ under inclusion, then $\wedge$ is union, $\vee$ is intersection, and the distributive law holds. Conversely, any finite distributive lattice is contained in a Boolean algebra by a theorem of Birkhoff. The correspondence takes each $x \in L$ to the set of $y \in L$ such that $x \geq y$ and $y$ cannot be written as a join of two elements of $L \setminus \{y\}$. (See for instance Birkhoff, Lattice Theory, Amer. Math. Soc., 1967.)

On one hand, if $L$ is distributive, it can be shown that the $j$-th term of the final sequence is equal to the meet of $a_{i_1} \wedge \cdots \wedge a_{i_j}$ over all sequences $1 \leq i_1 < \cdots < i_j \leq n$. For instance, this can be checked by forming the smallest subset $L'$ of $L$ containing $a_1, \ldots, a_n$ and closed under meet and join, then embedding $L'$ into a Boolean algebra using Birkhoff's theorem, then checking the claim for all Boolean algebras. It can also be checked directly (as suggested by Nghi Nguyen) by showing that for $j = 1, \ldots, n$, the meet of all joins of $j$-element subsets of $a_1, \ldots, a_n$ is invariant at each step.

On the other hand, a lattice fails to be distributive if and only if it contains five elements $a,b,c,0,1$ such that either the only relations among them are implied by
$$1 \geq a,b,c \geq 0$$

(this lattice is sometimes called the diamond), or the only relations among them are implied by
$$1 \geq a \geq b \geq 0, \quad 1 \geq c \geq 0$$

(this lattice is sometimes called the pentagon). (For a proof, see the Birkhoff reference given above.) For each of these examples, the initial sequence $a,b,c$ fails to determine the final sequence; for the diamond, we can end up with $0,*,1$ for any of $* = a,b,c$, whereas for the pentagon we can end up with $0,*,1$ for any of $* = a,b$.

Consequently, the final sequence is determined by the initial sequence if and only if $L$ is distributive.