Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  Gerry Myerson Jul 24 '12 at 13:44
3  
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. –  Gerry Myerson Jul 24 '12 at 23:38
2  
@Gerry: It seems I've learned even less! I had completely forgotten that I asked that before. 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. –  MJD Jul 25 '12 at 2:14
2  
Not to worry, no offense taken. By the standards of sci.math, you were a model of civility. –  Gerry Myerson Jul 25 '12 at 6:38

2 Answers 2

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

share|improve this answer
    
Thanks for doing this. I suspected that Gerry's heuristic would be suboptimal but I was not sure. –  MJD Jul 24 '12 at 15:55
    
It could be that my heuristic, even though suboptimal, gives good asymptotic bounds. I'm not betting on it, but it's possible. –  Gerry Myerson Jul 24 '12 at 23:30
    
The $(5,5)\to54$ solution turns out to be fairly easy to find and easy to prove optimal with pencil and paper. –  MJD Jul 30 '12 at 12:54

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.