Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.23578 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908290538012672 |
|---|---|
| author | Limbach, Anna Margarethe Scheidweiler, Robert Triesch, Eberhard |
| author_facet | Limbach, Anna Margarethe Scheidweiler, Robert Triesch, Eberhard |
| contents | Let $P(k,n)$ be the set of products of $k$ factors from the set $\{1,\ldots , 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 $π(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 $π(n)$ such that $|P (k, n)|=q_n(k)$ for each $k\geq n^2\cdot\left(\prod_{m=1}^{π(n)} \log_{p_m}(n)\right)-n+1.$ Moreover, we give an upper estimate of the leading coefficient of $q_n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_23578 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Effective Khovanskii, Ehrhart Polytopes, and the Erdős Multiplication Table Problem Limbach, Anna Margarethe Scheidweiler, Robert Triesch, Eberhard Combinatorics Let $P(k,n)$ be the set of products of $k$ factors from the set $\{1,\ldots , 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 $π(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 $π(n)$ such that $|P (k, n)|=q_n(k)$ for each $k\geq n^2\cdot\left(\prod_{m=1}^{π(n)} \log_{p_m}(n)\right)-n+1.$ Moreover, we give an upper estimate of the leading coefficient of $q_n$. |
| title | Effective Khovanskii, Ehrhart Polytopes, and the Erdős Multiplication Table Problem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.23578 |