Find all integer coefficient polynomial $P(x)$ such that for all positive integer $x$, we have $$\tau(P(x))\geq\tau(x)$$Where $\tau(n)$ denotes the number of divisors of $n$. Define $\tau(0)=\infty$. Note: you can use this conclusion. For all $\epsilon\geq0$, there exists a positive constant $C_\epsilon$ such that for all positive integer $n$, the $n$th smallest prime is at most $C_\epsilon n^{1+\epsilon}$. Proposed by USJL
Problem
Source: 2022 IMOC N6
Tags: number theory, IMOC, function
Justanaccount
11.09.2022 06:58
Bump this, any hints other than the product of the n-th first primes? I tried to choose x to be the product of the n-th first primes, but it did not work.
chystudent1-_-
27.09.2022 18:06
bump......
dgrozev
01.10.2022 18:26
Justanaccount wrote: ...I tried to choose x to be the product of the n-th first primes, but it did not work. Why do you think this does not work? Suppose the polynomial $P$ has non zero constant term $c.$ Let $p_k>c$ be any prime number. Put $x=p_kp_{k+1}\cdots p_{k+n-1}$ where $p_1<p_2<\dots$ be the sequence of the prime numbers and $n$ is large enough. Then $\tau(x)=2^n.$ Note that $P(x)$ is not multiple of any $p_i,i=k,k+1,\dots,k+n-1$, so its prime factors are either small, among $p_1,p_2,\dots,p_{k-1},$ or greater or equal to $p_{k+n}$. Those, that are small has comparatively small exponent so their share into amount of $\tau(P(x))$ is small. There must be a lot of large prime factors (with their multiplicity) in order to attain $2^n$ divisors, so when $n$ is large enough the growth rate of their product will be faster than any polynomial.
Justanaccount
02.10.2022 04:35
@above, it might be possible for P(x) to have n prime factors too when $deg(P)$ is bigger than 1.
primesarespecial
02.10.2022 08:17
Sorry........
Justanaccount
02.10.2022 10:14
@above RHS is $4^{nlog(n)}$, not $4^n$, this is the product of the n first primes, NOT the product of all primes less than n.
hydo2332
07.10.2022 22:45
Bump on this?
Justanaccount
14.10.2022 16:44
I believe this work. Let $\Omega(N,a,b)$ denote the number of not necessary dinstinct prime factors of $N$ that lies in the interval $[a,b]$. Consider a large k, if we let $p_k$ to be the k-th prime number and $N=a_0p_1p_2...p_k$, then there is a constant C such that: $\displaystyle \sum_{i=1}^{N} \Omega(P(iN),2,N)=CNlog(log(N))+O(N)$. Thus we can choose an $i \leq N$ such that $\Omega(P(iN),2,N) \leq Clog(log(N))$. We also have $\Omega(P(iN),N,\infty) \leq$ $some$ $constant$. Finally, since we have $\tau(N) \leq 2^{\Omega(N)}$, the problem is solved.
primesarespecial
14.10.2022 21:42
Sorry....
Justanaccount
15.10.2022 02:57
@above, First, each prime has a summand $log(N)$ behind but there are $\pi(N)$ primes, therefore I don't see any reason it does not work here. Second, multiplicity does not really matter here, for example if $P=Q^4$ then $P(x) \equiv 0 \pmod{p^{4i}}$ is determined by $x \pmod{p^i}$
CrazyInMath
23.11.2022 11:17
Bump this problem. It had been unsolved for a while.
Justanaccount
23.11.2022 20:42
@above i believe I have sketched the solution above.
normalqher
25.11.2022 14:45
Justanaccount wrote: $\sum_{i=1}^{N} \Omega(P(iN),2,N)=CNlog(log(N))+O(N)$. We also have $\Omega(P(iN),N,\infty) \leq$ $some$ $constant$. How do you know these are true ?
egxa
30.04.2024 10:35
BUMPPPP!
EthanWYX2009
13.10.2024 16:49
If $P(0)=0$ then $x|P(x)$ so $\tau(P(x))>\tau(x)$. We prove by contradiction that every polynomial $P$ with $P(0)\neq 0$ isn't a solution. Assuming the contrary. Let $n=\deg P$ and $C$ is a positive constant such that $|P(x)|\leq C|x|^n$ holds for all $x\neq 0$. Let $d$ be a positive integer large enough with respect to $P$, and $N$ be a large enough positive integer with respect to $d$.
Let $p_1, p_2, p_3, \cdots$ be the prime sequence and $S$ be the set of the first $N$ primes. For any subset $I$ of $S$ with size at least $d$, consider\[x_I=\prod_{p\in S\backslash I}p.\]Then $\tau(P(x_I))\geq \tau(x_I)=2^{N-d}$. Then we use another method to estimate $\tau(P(x_I))$. Let $M$ be a positive integer yet to be determined. then
\[\tau(P(x_I))=\prod_{p\leq M, p|P(x_i)}(v_p(P(x_I))+1)\prod_{p> M, p|P(x_i)}(v_p(P(x_I))+1)\]\[\leq \left(\log_2 Cp_N^{n(N-d)}\right)^{\#\{p|p\leq M, p|P(x_I)\}}\cdot 2^{\log MCp_N^{n(N-d)}}.\]Now we take every subset $I$ with size at least $d$ of $S$, and multiply the respective inequalities we got above up. To estimate the first term, we neeed to know for all $p\leq M$, how many $I$ will cause $p|P(x_i)$ to hold.
Let $k$ be the number of distinct prime divisors of $P(0)$, then for a fixed $I$, all the $p$ that is at most $p_N$ contributes at most $k+d$.
For a $p$ that is larger that $p_N$, because $x^nP(p_1p_2\cdots p_N/x)$ has at most $n$ roots mod $p$, when $I$ runs through all subsets of $S$ with size at most $d$, the contribution of $p$ is at most $n\cdot (\lfloor p_1p_2\cdots p_N/p\rfloor+1)\leq n\max(2p_N^d/p, 1)$. As a result, when $2^tp_N\leq 2p_N^d$, the contribution of $p$ in the interval $(2^{t-1}p_N, 2^tp_N]$ is at most\[2^tp_N\cdot \frac{2p_N^d}{2^{t-1}p_N}=4p_N^d.\]Take $M=2^tp_N$, with $t$ be the largest integer satisfying $2^tp_N\leq 2p_N^d$, we have\[\prod_{I\in\binom{S}{d}}\tau(P(x_I))\leq \left(\log_2 Cp_N^{n(N-d)}\right)^{(k+d)\binom{N}{d}+4tp_N^d}\cdot 2^{\binom{N}{d}\log_{p_N^d}Cp_N^{n(N-d)}}.\]However,\[\prod_{I\in\binom{S}{d}}\tau(P(x_I))\geq 2^{(N-d)\binom{N}{d}}.\]Take log with base $2$, the latter is a polynomial about $N$ with degree $d+1$ and leading coefficient $1/d!$. But the former is at most a polynomial about $N$ with degree $d+1$ and leading coefficient $n/d\cdot d!$ adding some polynomials at most degree $d+\epsilon$. So we got a contradiction when $d>n$ and $N$ is large enough.