Institution: Stanford University, Department of Computer Science

Title: On multiplicative representations of integers.

Author: Erdoes, Paul

Author: Szemeredi, Endre

Date: March 1975

Abstract: In 1969 it was shown by P. Erdoes that if 0 < $a_1$ < $a_2$ < ... < $a_k \leq x$ is a sequence of integers for which the products $a_i a_j$ are all distinct then the maximum possible value of k satisfies $\pi$(x) + $c_2$ $x^{3/4}$/${(log x)}^{3/2}$ < max k < $\pi$(x) + $c_1$ $x^{3/4}$/$(log x)^{3/2}$ where $\pi$(x) denotes the number of primes not exceeding x and $c_1$ and $c_2$ are absolute constants. In this paper we will be concerned with similar results of the following type. Suppose 0 < $a_1$ < ... < $a_k \leq x$, 0 < $b_1$ < ... < $b_{\ell} \leq x$ are sequences of integers. Let g(n) denote the number of representations of n in the form $a_i b_j$. Then we prove: (i) If g(n) $\leq$ 1 for all n then for some constant $c_3$, k$\ell$ < $c_3 x^2$/log x. (ii) For every c there is an f(c) so that if g(n) $\leq$ c for all n then for some constant $c_4$, k$\ell$ < $c_4 x^2$/log x ${(log log x)}^{f(c)}.

http://i.stanford.edu/pub/cstr/reports/cs/tr/75/485/CS-TR-75-485.pdf