2025/03/30 by Limbach, Anna Margarethe, Scheidweiler, Robert, Triesch, Eberhard
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2503.23578
Let P(k,n) be the set of products of k factors from the set \1,… , 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(n2 ) for n →∞. In 2015, Darda and Hujdurović asked whether, for each fixed n, |P (k, n)| is a polynomial in k of degree π(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 qn of degree π(n) such that |P (k, n)|=qn(k) for each k≥ n2⋅(∏m=1π(n) logpm(n))-n+1. Moreover, we give an upper estimate of the leading coefficient of qn.