Resolution of Erdős’ problems about unimodularity

Stijn Cambie · 2025

Read Resolution of Erdős’ problems about unimodularity by Stijn Cambie (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-10333.txt.

Introduction

Stijn Cambie settles two questions of Erdős about number densities in a 2025 paper. For a fixed lower bound, look at the density of integers having exactly one divisor inside an interval that stretches upward. Erdős wondered whether that density, as the interval's top end grows, always rises then falls just once: a single hump.

In general it does not. Cambie proves the sequence can wiggle with superpolynomially many local peaks and valleys. The single case where the hump truly occurs is the smallest lower bound, which he confirms. He also answers Erdős's companion question about the density of integers whose k-th prime factor equals a given prime. The paper closes both problems.

Catalog record

CREATORStijn Cambie
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE15 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-10333

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Resolution of Erdős’ problems about unimodularity Stijn Cambie Abstract Letting δ 1 ​ ( n , m ) \delta_{1}(n,m) be the density of the set of integers with exactly one divisor in ( n , m ) (n,m) , Erdős wondered if δ 1 ​ ( n , m ) \delta_{1}(n,m) is unimodular for fixed n n . We prove this is false in general, as the sequence ( δ 1 ​ ( n , m ) ) (\delta_{1}(n,m)) has superpolynomially many local extrema. However, we confirm unimodality in the single case for which it occurs; n = 1 n=1 . We also solve the question on unimodality of the density of integers whose k t ​ h k^{th} prime is p p . 1 Introduction In this note, we address the questions 690 and 692 from https://www.erdosproblems.com ( [ 3 , page. 75, 78] ), both in the negative. Let \delta_{1}(n,m) (resp. \delta_{r}(n,m) ) be the density of the set of integers with exactly one (resp. r ) divisor in (n,m)=\{n+1,n+2,\ldots,m-1\}. Erdős wondereded if \delta_{1}(n,m) is unimodular for fixed n , i.e., if (\delta_{1}(n,m)_{m\geq n+2} has at most one local maximum. With a computer program ( [ 2 , doc. Erdosproblem692_n_le20 ] ), one can check that (\delta_{1}(n,m))_{m\geq n+2} is not unimodular for small n ( 2\leq n\leq 20 ), answering the question. As an example, using the principle of inclusion-exclusion and a recursion, with \Pr(r\mid x) denoting the probality that a random integer x is a multiple of r , one can verify by hand that \displaystyle\delta_{1}(3,6) \displaystyle=\Pr(4\mid x)+\Pr(5\mid x)-2\cdot\Pr(4,5\mid x)=\frac{1}{4}+\frac{1}{5}-2\cdot\frac{1}{20} \displaystyle=\frac{7}{20}=0.35 \displaystyle\delta_{1}(3,7) \displaystyle=\frac{1}{4}+\frac{1}{5}+\frac{1}{6}-2\left(\frac{1}{20}+\frac{1}{12}+\frac{1}{30}\right)+3\cdot\frac{1}{60} \displaystyle=\frac{1}{3}\sim 0.33 \displaystyle\delta_{1}(3,8) \displaystyle=\frac{6}{7}\cdot\delta_{1}(3,7)+\frac{1}{7}\cdot\delta_{0}(3,7)=\frac{6}{7}\cdot\frac{1}{3}+\frac{1}{7}\cdot\frac{8}{15} \displaystyle=\frac{38}{105}\sim 0.36 Since \delta_{1}(3,7)<\min\{\delta_{1}(3,6),\delta(3,8)\} the sequence (\delta_{1}(3,m))_{m\geq 5} is not unimodal, from which one concludes. Inspired by communication with Thomas Bloom, we address the question more precisely. We prove that the sequence has superpolynomially many local maxima in general, and is thus very far from being unimodal. Nonetheless, there is still one case in which the possible intuition about nice behaviour is true. When n=1 , the sequence (\delta_{1}(1,m))_{m} of densities of the set of integers with exactly one non-trivial divisor bounded by m is unimodal, being non-increasing. The proofs can be found in Section 2 . As a second result, let d_{k}(p) be the density of integers whose k^{th} prime is p . Erdős could not disprove unimodularity of the sequence (d_{k}(p))_{p} . We show that unimodularity is true for k\leq 3 and give counterexamples for k>3. This is done in Section 3 . In the proofs, we will assume the reader is familiar with Landau notation O(),\omega(),\Theta() for functions that are bounded from above by a multiple of an other function, by below, and by both respectively. 2 Main proofs for problem 692 We first prove the one case for which Erdős’ question has a positive answer, since it is the more elementary result. Theorem 1 . The sequence \delta_{1}(1,m) is non-increasing (and thus unimodular) in m . Proof. For fixed m\in\mathbb{N} , let the small primes be 2\leq p_{1},p_{2},\ldots p_{r}\leq\sqrt{m-1} and the larger primes be \sqrt{m}\leq q_{1},q_{2},\ldots,q_{s}\leq m-1. Let L=\prod_{i=1}^{r}p_{i}^{2}\cdot\prod_{i=1}^{s}q_{i}. Let \varphi(L) and A be the number of integers in \{1,2,\ldots,L\} which have, respectively, zero or exactly one divisor in \{2,3,\ldots,m-1\}. Note that A and L are functions of m , but we won’t write m explicitly for ease of notation, and \varphi is the Euler totient function Now \delta_{1}(1,m)=\frac{A}{L}, since a number has exactly one divisor in \{2,3,\ldots,m-1\} if it is a multiple of exactly one prime in \{p_{1},\ldots,p_{r},q_{1},\ldots,q_{s}\} and not a multiple of p_{i}^{2} for any 1\leq i\leq r , and it is thus only dependent on its residue modulo L. Similarly \delta_{0}(n,m)=\frac{\varphi{(L)}}{L}. We will prove two properties in parallel; \frac{A}{L} is non-increasing in m and A\geq\varphi(L) for every m\geq 3. In the base case, where m=3 , we have L=2 and A=\varphi(L)=1 (half of the integers are a multiple of 2 and half of them are not). In the induction step, we only have to consider m-1 equal to a prime, or the square of a prime. Let L,A be the values for m-1 and A^{\prime},L^{\prime} the values for m. Case m-1=p : Compared with m-1 , for m we find that L^{\prime}=pL, \varphi(L^{\prime})=(p-1)\varphi(L) and A^{\prime}=A(p-1)+\varphi(L) . The latter since for every residue modulo L , there are p-1 possibilities modulo pL that are not a multiple of p, and one which is a multiple of p. Now \frac{A^{\prime}}{\varphi(L^{\prime})}=\frac{A}{\varphi(L)}+\frac{1}{p-1} (1) and \frac{A^{\prime}}{L^{\prime}}=\frac{A(p-1)+\varphi(L)}{pL}\leq\frac{A}{L} since \varphi(L)\leq A by the induction hypothesis. Case m-1=p^{2} : Compared with m-1 , for m we now find that L^{\prime}=pL, \varphi(L^{\prime})=p\varphi(L) and A^{\prime}=Ap-\frac{\varphi(L)}{p-1} , implying immediately that \frac{A^{\prime}}{L^{\prime}}<\frac{A}{L}. The latter since for every integer 0<x\leq L that is not a multiple of p that has one divisor among \{2,3,\ldots,m-2\}, each integer of the form iL+x with 0\leq i\leq p-1 has the same property. For an integer 0\leq x\leq L that only has the divisor p among \{2,3,\ldots,m-2\}, there are p-1 choices for 0\leq i\leq p-1 such that p^{2}\nmid iL+x. Here there are \varphi(L/p)=\frac{\varphi(L)}{p-1} choices for x , since x=px^{\prime} where x^{\prime}\leq\frac{L}{p} and x^{\prime} is relative prime with the other primes less than p^{2} and thus \frac{L}{p} . We further have that \frac{A^{\prime}}{\varphi(L^{\prime})}=\frac{A}{\varphi(L)}-\frac{1}{p(p-1)}. (2) Since \frac{1}{3-1}=\frac{1}{2(2-1)} and \frac{1}{5-1}>\frac{1}{3(3-1)}+\frac{1}{5(5-1)} , from Eq. 1 and Eq. 2 we deduce that \frac{A}{\varphi(L)}\geq 0 and the latter is strict once m\geq 6. We conclude that both statements are true by induction, and thus \delta_{1}(1,m) is indeed non-increasing. ∎ Remark 2 . The above recursions can also be implemented to compute \delta_{1}(n,m) efficiently for small n , leading to a linear time program as a function of m . This has been done for n\in\{2,3\} in [ 2 , doc. Recurs_n2 and Recurs_n3 ] Next, we prove there are superpolynomially many local maxima. Theorem 3 . For some fixed c>0 , the sequence (\delta_{1}(n,m))_{m\geq n+2} contains \omega(\exp(n^{c})) many local maxima. Proof. We start proving the following claim, which we will apply later. Claim 4 . There exists c>0 such that for every sufficiently large n and m=\Theta(\exp(3n^{c})), \delta_{0}(n,m+1)>\delta_{1}(n,m+1). Proof. Let L=\lcm\{n+1,n+2,\ldots,m\}=\lcm\{1,2,\ldots,m\}. By the definition of Euler’s totient function and by Mertens (third) theorem [ 5 ] \frac{\varphi(L)}{L}=\prod_{p\leq m}\frac{p-1}{p}\sim exp(-\gamma)\frac{1}{\log(m)} , where exp(\gamma)<2 is a constant. As a corollary, we have \frac{\varphi(L)}{L}>\frac{1}{2\log(m)}. A classical estimate of the harmonic numbers says H_{n}=\sum_{i=1}^{n}\frac{1}{i}>\log(n) . Using these two inequalities, we derive that \delta_{0}(n,m)=\frac{\sum_{i=1}^{n}\varphi\left(\frac{L}{i}\right)}{L}\geq\frac{\sum_{i=1}^{n}\frac{\varphi(L)}{i}}{L}\geq\frac{H_{n}\cdot\varphi(L)}{L}>\frac{\log(n)}{2\log(m)}. By [ 4 , Thm. 4] , \delta_{1}(n,m)=O\left(\frac{\log\log(m/n)}{\log(m/n)}\right). Assuming c is chosen sufficiently small, we conclude \delta_{1}(n,m)<\delta_{0}(n,m) . ∎ We will prove that \delta_{1}(n,p+1)>\delta_{1}(n,p) for the primes p with p=\Theta(\exp(3n^{c})) and \delta_{1}(n,2p+1)<\delta_{1}(n,2p) for every prime p>n. The result then follows from taking the longest sequences (p_{i})_{i} and (q_{i})_{i} of primes satisfying \exp(3n^{c})<p_{1}<2q_{1}<p_{2}<2q_{2}<p_{3}<\ldots<p_{r}<2q_{r}<2\exp(3n^{c}). By a result on prime gaps [ 1 ] , we know r=\omega(\exp(0.475\cdot 3n^{c}))) . To prove that \delta_{1}(n,p+1)>\delta_{1}(n,p) , note that \delta_{1}(n,p+1)=\frac{p-1}{p}\delta_{1}(n,p)+\frac{1}{p}\delta_{0}(n,p), and this is larger than \delta_{1}(n,p) by 4 for p=\Theta(\exp(3n^{c})) . The inequality \delta_{1}(n,2p+1)<\delta_{1}(n,2p) for a prime p>n is almost trivial. Since multiples of 2p are multiples of p , there are no numbers whose only divisor in (n,2p+1) is 2p. On the other hand, there are multiples of 2p (this only depends on the residue modulo \lcm\{n+1,\ldots,2p\} ) that have only one divisor in (n,2p), but with two divisors in (n,2p+1). ∎

Read the complete text