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
    See [arithmetic combinatorics](http://en.wikipedia.org/wiki/Arithmetic_combinatorics).2012-07-30
  • 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
    What do you mean by "minimum" and "maximum"? Are you taking this over all possible subsets of $\mathbb{Z}$?2012-07-31
  • 0
    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$.2012-07-31
  • 0
    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.2012-07-31
  • 0
    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.2012-07-31
  • 0
    @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.2012-08-01
  • 0
    I'm not the OP. I was just asking what you meant by minimum and maximum. Typically in mathematics, one takes the minimum (or maximum) of some collection of things. So my question is what are you comparing your minimum (and maximum) to. Or another way to ask the same question: $2n - 2$ is the minimum *of what*?2012-08-02
  • 0
    @Code, from context, it is the minimum number of distinct products you can get (when you start with a set with $n$ numbers in it).2012-08-02
  • 0
    Thanks, the last part in the parentheses is what I was unsure of.2012-08-02