Partially Ordered Sets question

Question

For $m\in\mathbb{N}$, which integers are covered by $m$? I've been playing with the prime factors of $m$ and I can't seem to see any pattern. Can anyone help?

Answer 1

Look at the prime factorization of the integer. Say $x = p_1^{a_1}\cdots p_n^{a_n}$ and $y = p_1^{b_1}\cdots p_n^{b_n}$ and $x$ divides $y$. Then $a_i \leq b_i$ for all $i$. There is a path from $x$ to $y$ in the ordering by multiplying by prime numbers to raise the $a_i$ up to the $b_i$. It should then be clear that $y$ covers $x$ if and only if there exists a prime $p$ such that $y = xp$.

Answer 2

Here’s a rather different way to look at it. It’s not needed to solve the problem, but the idea of transferring the problem to a possibly more transparent setting is a useful one, and this instance of it is a fairly simple introduction to the idea.

Each integer $n>1$ can be written uniquely as a product of positive powers of distinct primes. If we allow $0$ as an exponent, we can write every positive integer $n$ uniquely as

$$n=\prod_{k\ge 1}p_k^{a_k}\;,$$

where $p_k$ is the $k$-th prime. Conversely, if $a=\langle a_k:k\in\Bbb Z^+\rangle$ is any sequence of non-negative integers having only finitely many non-zero terms, there is a unique integer

$$n(a)=\prod_{k\ge 1}p_k^{a_k}\;.$$

Let $\Sigma_0$ be the set of all sequences of non-negative integers having only finitely many non-zero terms. Then the map $n:\Sigma_0\to\Bbb Z^+:a\mapsto n(a)$ is a bijection.

If $a=\langle a_k:k\in\Bbb Z^+\rangle,b=\langle b_k:k\in\Bbb Z^+\rangle\in\Sigma_0$, define $a\preceq b$ if and only if $a_k\le b_k$ for all $\in\Bbb Z^+$; it’s easy to check that $\preceq$ is a partial order on $\Sigma_0$ and that the map $n$ is actually an order-isomorphism of the partial orders $\langle\Sigma_0,\preceq\rangle$ and $\Bbb Z^+,\mid\rangle$: $a\preceq b$ if and only if $n(a)\mid n(b)$. Thus, $b$ covers $a$ if and only if $n(b)$ covers $n(a)$.

Now moving ‘up’ (with respect to $\preceq$) from some $a\in\Sigma_0$ means increasing one or more terms of the sequence. What’s a minimal step up? Clearly it must be increasing exactly one term by just $1$. Thus, $b$ covers $a$ if and only if there is an $i\in\Bbb Z^+$ such that

$$b_k=\begin{cases} a_k,&\text{if }k\ne i\\ a_k+1,&\text{if }k=i\;. \end{cases}$$

Now just translate this back to $\Bbb Z^+$ via the isomorphism $n$, and you have Jim’s answer.