17
$\begingroup$

Let positive integers $\alpha$ and $\beta$ be given. It is easy to find sets $A$ and $B$ of positive integers such that:

  • $|A|=\alpha$ and $|B|=\beta$
  • The set $P = \{ab : a\in A, b\in B\}$ contains exactly $\alpha\beta$ members. That is, if $a_1,a_2\in A$ and $b_1,b_2\in B$, and $a_1b_1 = a_2b_2$, then $a_1=a_2$ and $b_1=b_2$. Or put another way, multiplication is injective when restricted to $A\times B$. Or another way: if we compute the multiplication table of members of $A$ multiplied by members of $B$, no entry appears more than once in the table.

I want to find $A$ and $B$ such that the largest entry in the multiplication table, $M = \max P = \max A\cdot\max B$, is as small as possible.

My questions are: What are good asymptotic bounds on the minimum $M$ as a function of $\alpha$ and $\beta$? What is a good algorithm for finding sets $A$ and $B$ with small $M$, given $\alpha$ and $\beta$? What else can be said about this problem that is interesting? Has it been studied before, and if so, what is already known?

Example: $(\alpha, \beta) = (2,4)$

For example, let's say that $\alpha=2$, $\beta=4$. Then taking $A = \{1, 2\}$ and $B=\{1,3,4,5\}$ we make $M=10$, since the products are $\{1,3,4,5,2,6,8,10\}$.

$$\begin{array}{r|rrrr} \times & 1 & 3 & 4 & 5 \\ \hline\\ 1 & 1 & 3 & 4 & 5 \\ 2 & 2 & 6 & 8 & 10 \end{array}$$

It is not possible to get a smaller $M$ for this case. If it were possible, the 8 elements of $P$ would have to be chosen from $\{1,\ldots 9\}$. But $P$ cannot contain 7, since then either $A$ or $B$ must contain 7, and then $P$ would have to contain a second distinct multiple of 7, so $M=\max P \ge 14$. Similarly if $P$ contained 5, it would have to contain a second multiple of 5, and so $M\ge 10$. So $M\le 9$ implies $P\subset \{1,2,3,4,6,8,9\}$ and this is impossible, since $P$ has 8 elements. This $M=10$ is optimal.

Example: $(\alpha, \beta) = (3,4)$

Now let's consider $\alpha=3$, $\beta=4$.Taking $A=\{1,5,6\}$ and $B=\{1,2,3,4\}$ works and makes $M=24$, so this is an upper bound for $M$:

$$\begin{array}{r|rrrr} \times & 1 & 2 & 3 & 4 \\ \hline \\ 1 & 1 & 2 & 3 & 4 \\ 5 & 5 & 10 & 15 & 20 \\ 6 & 6 & 12 & 18 & 24 \end{array}$$

$|A|=3$, so $\max A\ge 3$, and $|B|=4$, so $\max B\ge 4$. It is easily seen that $|A\cap B|\le 1$, since if $|A\cap B| \ge 2$ we can find distinct $p$ and $q$ in $A\cap B$ and then $(p, q)$ and $(q, p)$ fail to have distinct products. So $|A\cup B| \ge 6$, and we know that at least one set must have an element that is at least 6.

$M$ is equal to $\max A\cdot\max B$. $M=23$ is impossible, since then $M=1\cdot 23$ and so one of $A$ or $B$ would have a max of 1; similarly $M=22 = 2\cdot 11$ is impossible, since then one of $A$ or $B$ would have a max of 1 or 2.

So to find sets that make $M<24$, we must have $M\le 21$. $M=20$ is impossible since then one of $A$ and $B$ would have a a max of 4 and one has a max of 5 and we said at least one has a max of at least 6. (Obviously, $20=2\cdot10$ and $20 = 1\cdot20$ also fail.) $M=19$ is impossible by the same argument that ruled out $M=23$. Each $M<18$ can be similarly ruled out. The only remaining possibilities are $(\max A, \max B) = (3, 6)$ or $(3, 7)$. Then $A=\{1,2,3\}$. Taking $\max B = 6$ we get $\{4,5,6\}\subset B$ since $|A\cap B|\le 1$. But then $\{2,3\}\subset A$ and $\{4,6\}\subset B$, so the products are not all distinct since $2\cdot6 = 3\cdot 4$. This rules out $\max B = 6$.

But $\max B=7$ does work:

$$\begin{array}{r|rrrr} \times & 1 & 4 & 5 & 7 \\ \hline \\ 1 & 1 & 4 & 5 & 7 \\ 2 & 2 & 8 & 10 & 14 \\ 3 & 3 & 12 & 15 & 21 \end{array}$$

And the foregoing arguments show that this is the best possible.

  • 1
    If $\alpha\le\beta$, then I think you want to take $A=\{{1,2,\dots,\alpha\}}$, and fill $B$ greedily, that is, one element at a time, always adjoining the smallest number that doesn't make a duplication.2012-07-24
  • 5
    I just discovered that you and I discussed this problem before - 14 years ago! - on the sci.math newsgroup, under the subject, "Multiplication table with all products distinct". You even found the same $(3,5)$ reply to my heuristic that Yuval gives in his answer. 14 years, and I haven't learned anything. Sad, really.2012-07-24
  • 2
    @Gerry: It seems I've learned even less! I had completely forgotten that [I asked that before](https://groups.google.com/forum/?fromgroups#!searchin/sci.math/multiplication$20table/sci.math/zmdrXK_tduc/tBMNz9fWWhUJ). I see that Google also has a record of a snotty reply that I sent, I thought better of, and tried to replace. I apologize for being rude to you 14 years ago, or today, whenever you saw it first.2012-07-25
  • 2
    Not to worry, no offense taken. By the standards of sci.math, you were a model of civility.2012-07-25

2 Answers 2