Is there an exact, workable description of sets of positive integers closed under the lcm or gcd operations? In other words, a set of ideals of Z which is closed under intersections or sums. My motivation for asking this is the fact that the order of the product of two elements in an abelian group is the lcm of their orders: thus, given a subset of integers A which is closed under lcm and contains 1, the set of all elements in a group whose orders are in A is a subgroup which may have some interesting properties. P-subgroups are an example of this.

In the absence of a general criterion, examples are also helpful.

  • $\begingroup$ Do you want sets to be closed under gcd and sets to be closed under lcm, or do you want sets that are closed under gcd and lcm? $\endgroup$ – Martin Brandenburg Jan 25 '16 at 17:39
  • $\begingroup$ Any one of those would be helpful. $\endgroup$ – Vik78 Jan 25 '16 at 17:41

Is there an exact, workable description of sets of positive integers closed under the lcm or gcd operations?

In short, I don't think so. Here's a description of uncountably many such sets: for every prime $p$, pick a subset $S_p \subseteq \mathbb{Z}_{\ge 0}$ of the nonnegative integers. Now consider the set of positive integers $n$ such that, if $\nu_p(n)$ denotes the power of $p$ dividing $n$,

$$\nu_p(n) \in S_p \forall p.$$

This set uniquely determines each $S_p$, and since there are uncountably many choices for each $S_p$, there are uncountably many such sets.

But this isn't even all of them! Right now there's no interaction between the different $\nu_p$, but we could also require, for example, that $\nu_2 = \nu_3$. More generally, for any equivalence relation $\sim$ on the natural numbers (and there are uncountably many of these too), we could require that if $p \sim q$, then $\nu_p = \nu_q$.

And this isn't even all of them. For simplicity, at this point I'm going to pretend that there are only two primes, say $2$ and $3$. Assign to every natural number $n$ the coordinates $(\nu_2(n), \nu_3(n))$ in $\mathbb{R}^2$, which is a certain lattice point in the first quadrant. Geometrically, taking the gcd of two natural numbers corresponds to making the two corresponding points two vertices of a right triangle and taking the third vertex. So there are lots more possibilities that aren't covered by the above construction, which you can visualize as sets of points closed under this operation.

For more look up the notion of order dimension.

  • 2
    $\begingroup$ Pretty sure there is more stuff we can do. Every finite lattice embeds into the lattice of natural numbers under divisibility, and not all of those have the nice structure as a product of linear orders that the ones described here do. $\endgroup$ – Henning Makholm Jan 25 '16 at 17:34
  • $\begingroup$ Right, I was about to edit to give some indication of this. $\endgroup$ – Qiaochu Yuan Jan 25 '16 at 17:37
  • $\begingroup$ This is a fascinating construction that you've come up with. Thanks for the answer! $\endgroup$ – Vik78 Jan 25 '16 at 17:51
  • $\begingroup$ One additional question: this construction is pretty general. Do you know whether or not this describes all the sets closed under lcm? $\endgroup$ – Vik78 Jan 25 '16 at 18:12
  • $\begingroup$ @Vik78: which construction? The second one? Definitely not. That's what the third construction (which isn't really a construction, just an indication of the possibilities) was supposed to indicate. $\endgroup$ – Qiaochu Yuan Jan 25 '16 at 18:32

The powers of any number of the form $a^k$, with $a,k$ natural satisfies this. You can stop at any power you want. You can also take the union of powers of $a^k$ and $b^m$ as long as $\gcd(a,b)=1$ and their products, stopping each at any power you want. This extends to as many pairwise coprime numbers as you want. You can include any subset of the primes, each to any power you like, so there are uncountably many such sets.

  • $\begingroup$ @QiaochuYuan: I have made it explicit that you can use an infinite set of primes, which makes the collection uncountable. I see you show there are more than this. $\endgroup$ – Ross Millikan Jan 25 '16 at 18:37
  • $\begingroup$ My bad, I misread the last bit. $\endgroup$ – Qiaochu Yuan Jan 25 '16 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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