12
$\begingroup$

Let $S$ be a subset of the integers which is closed under multiplication. There are many possible choices of $S$:

  1. $S = \{-1, 1\}$.
  2. $S$ is the set of integers of the form $a^k$, where $a$ is fixed and $k \geq 0$ varies. For example, $S$ is the set of powers of 2.
  3. $S$ is the set of integers of the form $a^k$, where $a$ is varied and $k \geq 0$ is fixed. For example, $S$ is the set of all squares.
  4. $S$ is the set of integers divisible by some set of primes and not divisible by some other set of primes. For example, $S$ is the set of $B$-smooth integers, i.e. integers not divisible by any primes larger than $B$, or $S$ is the set of multiples of 13, or $S$ is the set of even numbers.
  5. Here is a more exotic choice: $S$ is the set of all integers which can be written as a sum of two squares (number theorists will recognize this as a special case of #4).

I have two questions: first, is there a simple reason why the collection of subsets of the integers which is closed under multiplication is so much richer than the collection of subsets of the integers which is closed under addition? Second, are there any other interesting choices of $S$ which aren't on my list?

Improve this question
$\endgroup$
6
  • 12
    $\begingroup$ The premise is not quite right: the positive integers are also closed under addition, and there are more exotic examples such as all Summer Olympic Games' years (using the official designation of the 32nd games as Tokyo 2020, and assuming no further cancellations beyond 1916, 1940, 1944). But such "additive semigroups" are still more tractable than multiplicative ones because the integers can be generated additively by just $\{1,-1\}$ but require infinitely many multiplicative generators. $\endgroup$
    – Noam D. Elkies
    Commented Aug 9, 2021 at 21:01
  • 3
    $\begingroup$ How about this one? let $f$ be any convex increasing function from the reals to itself with the property that $f(0)=0$. Let $S=\{2^a3^b\colon b\le f(a)\}$. $\endgroup$
    – Anthony Quas
    Commented Aug 9, 2021 at 23:18
  • 1
    $\begingroup$ For any real $k>1$ the set $S_k=\{n\;|\;n\ge \text{rad}(n)^k\}$. $\endgroup$
    – Yaakov Baruch
    Commented Aug 9, 2021 at 23:47
  • 2
    $\begingroup$ I suspect it's partly because integers have a unique prime factorisation, but there's many ways to write each integer as a sum of other integers. So there's no useful analogue to the OP's example 3 (you can't say "written as a sum of $k$ equal numbers" because that's the same as example 2). $\endgroup$
    – user7868
    Commented Aug 10, 2021 at 5:41
  • 3
    $\begingroup$ The set of integers that are not square-free. The set of integers $n=1\mod 13$. $\endgroup$
    – Pietro Majer
    Commented Aug 10, 2021 at 7:36

2 Answers 2

Reset to default
15
$\begingroup$

That is because the semigroup $({\mathbb Z},\times)$ contains the semigroup $({\mathbb N},+)^\infty$ as an isomorphic copy. In contrast, most of the subsemigroups of $({\mathbb Z},+)$ are isomorphic to subsemigroups of $({\mathbb N},+)$.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ I mostly agree, but I think it's better to say that $(\mathbf Z,\cdot)$ isomorphic to the product of the free abelian monoid and the cyclic group of order $2$ (as opposed to the vague statement that it contains the monoid). And also, by the Chinese remainder theorem, it follows that subsemigroups of $(\mathbf Z, +)$ are all either isomorphic to $(\mathbf Z,+)$ itself (if they contain both negative and positive elements) or, in the latter case you mentioned, have a cofinite subsemigroup isomorphic to $(\mathbf N,+)$. $\endgroup$
    – tomasz
    Commented Aug 10, 2021 at 17:01
  • 3
    $\begingroup$ In other words, subsemigroups of $(\mathbf Z, +)$ are of the form $k\mathbf Z$ or $(a+k\mathbf N)\cup F$, for $a,k\in \mathbf Z, F\subseteq \mathbf Z$ finite (all of the same sign or zero, among other restrictions). So there are only countably many of them, as opposed to continuum many multiplicative subsemigroups. On the other hand, the isomorphism types are much more interesting for the additive than multiplicative, IMO. $\endgroup$
    – tomasz
    Commented Aug 10, 2021 at 17:03
  • $\begingroup$ A minor correction: $(\mathbf Z,\cdot)$ is isomorphic to $F\times C_2\cup \{0\}$, where $F$ is the free abelian monoid (I neglected to mention $0$ in my comment above). $\endgroup$
    – tomasz
    Commented Aug 11, 2021 at 17:45
1
$\begingroup$

To make Mark Sapir's answer more explicit, we can take the direct product of sets obtained from your second example. For instance, we can take $S = \{ x: \exists a \in A, b \in B: x =ab\}$ where $A = \{x:\exists k: x=3^k\}$ and $B = \{x:\exists k: x=5^k\}$.

If we consider just the cases where each component set is built around a power of a prime, and we only have one component set for each prime, then we can represent what power is associated with each prime by some function $f$ from the prime numbers to the non-negative integers, and we can define $S_p=\{x: \exists k : x = p^{kf(p)}\}$. This means that for every such $f$, there is some set constructed from the direct product of all $S_p$, so this gives a family of cardinality $\mathbb N ^ {\mathbb N}$.

If we take $f(p)$ to be a constant function $f(p) \equiv c$, then we get your third example of numbers of a fixed power. I believe that some of your other examples are outside this family, but as far as the cardinality is concerned, adding those examples doesn't change the number of sets.

Improve this answer
$\endgroup$

You must log in to answer this question.

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