Multiplication tables with all entries distinct

Question

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.

Answer 1

Here are some numerical results:

$$ \begin{array}{c|ccccc} & 1 & 2 & 3 & 4 & 5 \\\hline 1 & 1 & 2 & 3 & 4 & 5 \\ 2 & 2 & 6 & 8 & 10 & 14 \\ 3 & 3 & 8 & 15 & 21 & 24 \\ 4 & 4 & 10 & 21 & 28 & 36 \\ 5 & 5 & 14 & 24 & 36 & 54 \end{array} $$ The diagonal sequence eludes the OEIS.

Gerry's heuristic fails for $(5,3)$ and $(5,4)$, though in these cases there are optima where the smaller set is equal to his: $$ \begin{gather*} \{1,2,3\}, \{1,5,6,7,8\} \\ \{1,2,3,4\}, \{1,5,7,8,9\} \end{gather*} $$ Gerry's heuristic only gives $27$ and $44$ (instead of $24$ and $36$): $$ \begin{gather*} \{1,2,3\}, \{1,4,5,7,9\} \\ \{1,2,3,4\}, \{1,5,6,7,11\} \end{gather*} $$ Worse, for $\{5,5\}$, the best solution is obtained on a pair not including $\{1,2,3,4,5\}$: $$ \{1,2,3,4,6\},\{1,5,7,8,9\} $$ The best solution containing $\{1,2,3,4,5\}$ has value $55$ (compared to $54$): $$ \{1,2,3,4,5\}, \{1,7,8,9,11\} $$ This is always the case when $x \nmid M(x,y)$.

Let $M^*(x)$ denote $M(x,x)$ under the constraint that one of the sets is $\{1,\ldots,x\}$. For $x \leq 7$, $M^*(x)$ agrees with A033286 and A026102, but the next entry in these sequences is 152, while $M^*(8) = 160$.

Answer 2

I will use this post to catalog results and miscellaneous thoughts about the problem.

The optimal solution for the $(6,6)$ case is very simple; it has $A=\{1,\ldots ,6\}, B=\{a, 7,\ldots,11\}$ (where $a$ is some element of $A$, say 1), and $M=66$. Clearly no solution can reduce the largest element of $A$. Any solution that reduces the largest element of $B$ will create a second overlap with $A$ that must be addressed by increasing the largest element of $A$. But 66 is too small to be improved in this way: $7×9$ is out of reach and $8×8$ is forbidden. Nothing else can work since each set must contain an element of 6 or more.

The solution seems to be simple in this case because there is a good home for the problem child 6, which is best housed with 2 and 3. [Add reason later.] In the 5×5 case the partial solution $A=\{1,\ldots,5\}, B=\{a, 6,\ldots\}$ is dominated by $A=\{1,2,3,4,6\}, B=\{a, 5, \ldots\}$ for the same reason.

---

A choice of $A$ induces a graph on ${\Bbb N}\setminus A$ where there is an edge between $n$ and $n'$ whenever there exist $a, a'\in A$ with $a/a' = n/n'$. Legal choices of $B$ then correspond to independent sets in this graph, and it is usually easy to pick out the optimal $B$ for a given $A$.