4
$\begingroup$

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.

  • 0
    Ah, excellent, sometimes you just need to know the right words. Thanks!2012-07-30

1 Answers 1

2

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$.

  • 0
    Thanks, the last part in the parentheses is what I was unsure of.2012-08-02