Effective Khovanskii, Ehrhart Polytopes, and the Erdős Multiplication Table Problem

Abstract

Let $P(k,n)$ be the set of products of $k$ factors from the set $\{1,\dots ,n\}.$ In 1955, Erdős posed the problem of determining the order of magnitude of $|P(2,n)|$ and proved that $|P(2,n)|=o(n^2)$ for $n\to \infty$. In 2015, Darda and Hujdurović asked whether, for each fixed $n$, $|P(k,n)|$ is a polynomial in $k$ of degree $\ddot{I}€(n)$ - the number of primes not larger than $n$. Recently, Granville, Smith and Walker published an effective version of Khovanskii's Theorem. We apply this new result to show, that for each integer $n$, there is a polynomial $q_n$ of degree $\ddot{I}€(n)$ such that $|P(k,n)|=q_n(k)$ for each $k\ge n^2\cdot \left({\prod }_{m=1}^{\ddot{I}€(n)}{\log }_{p_m}(n)\right)-n+1.$ Moreover, we give an upper estimate of the leading coefficient of $q_n$.