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.