Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does anyone know if the following question has been solved in general or has any insight in the question.

Let us take for example the sets {0,1} and {1,2} and function multiplication (*) over the sets shall be denoted as *(0,1)=0*1=0.

We now want to know the size of the set that can be derived from multiplication over all combinations of such sets. For example:

{*(0,0), *(0,1), *(1,0), *(1,1)} = {0,1}

where as

{*(1,1), *(1,2), *(2,1), *(2,2)} = {1,2,4}

This is a simple example but generalisations to combinations of the alphabet larger than two should be progressively more difficult to keep track of.

share|cite|improve this question
See arithmetic combinatorics. – sai Jul 30 '12 at 15:11
Ah, excellent, sometimes you just need to know the right words. Thanks! – user1170304 Jul 30 '12 at 20:27
up vote 2 down vote accepted

I'm going to take the question to be this: given a set $S$ of $n$ non-negative integers, how many distinct numbers are there of the form $ab$ with $a,b$ in $S$?

As OP is aware, the answer depends on $S$, not just on $n$. So here are some extreme cases.

  1. If $S=\{{0,1,2,4,8,\dots,2^{n-2}\}}$ then you get $2n-2$ distinct products. This is the minimum; you can't get fewer.

  2. If $S=\{{2,3,5,7,11,\dots,p_n\}}$, where $p_n$ is the $n$th prime, you get $(n^2+n)/2$ distinct products. This is the maximum; you can't get more.

If you want a better answer, you have to make some assumptions about $S$.

share|cite|improve this answer
What do you mean by "minimum" and "maximum"? Are you taking this over all possible subsets of $\mathbb{Z}$? – Code-Guru Jul 31 '12 at 0:50
Minimum means minimum, and maximum means maximum. With $n$ non-negative integers (or even $n$ complex numbers), you can't have fewer than $2n-2$ distinct products, and you can't have more than $(n^2+n)/2$. – Gerry Myerson Jul 31 '12 at 2:16
Oops, I take back part of that comment. It's fine for non-negative integers, but with $n$ complex numbers you might have only $n$ products, if your $n$ complex numbers are the $n$th roots of unity. The $(n^2+n)/2$ part is OK for the complex numbers. – Gerry Myerson Jul 31 '12 at 2:54
Simply repeating a word doesn't define it. However, your additional comments do clarify to some extent what you are measuring the minimum and maximum of. – Code-Guru Jul 31 '12 at 17:48
@Code, I'm sorry, I'd be happy to clarify further, but I just don't know what needs clarification. Clarification is a two-way street - you have to make your needs clearer, too. – Gerry Myerson Aug 1 '12 at 3:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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