betaFeedback

WorksMathematics

On a problem due to Erdős concerning w1(n)w_1(n)

Abstract

Adopting notation from Erdős [Congress. Numer., 1980], we define w1(n)=w(n)w_1(n) = w(n) for positive integers nn so that w(1)=0w(1) = 0 and so that: If n>1n > 1 and n=∏pαpn = \prod p^{α_p}, then w(n)=∑pαp∥nnpαpw(n) = \sum_{p^{α_p} \parallel n} \frac{n}{p^{α_p}}. By then defining V(x)=∣{w(n):1≤n≤x}∣V(x)=\bigl|\{w(n):1\le n\le x\}\bigr| for x≥1x \geq 1, Erdős considered whether or not V(x)=o(x)V(x) = o(x) and left this as an open problem. This same problem was also given as an open problem in Guy's famous textbook on unsolved problems in number theory and seems to have remained open. We solve this problem by proving that V(x)≠o(x)V(x) \neq o(x), and, moreover, by proving the stronger result such that lim inf⁡x→∞V(x)x>0\liminf_{x \to \infty} \frac{V(x)}{x} > 0.

Introduction and background

Define the integer sequence (w(n):n∈N)(w(n):n\in\mathbb{N}) so that

w(n)={∑αppαp∥nnpαpif n>1 and n=∏pαp;0if n=1,(1)w(n)= \begin{cases} \sum_{\alpha_p p^{\alpha_p}\parallel n}\frac{n}{p^{\alpha_p}} & \text{if } n>1\text{ and }n=\prod p^{\alpha_p};\\ 0 & \text{if } n=1, \end{cases} \tag*{(1)}

and define V(x)={w(n):1≤n≤x}V(x)=\{w(n):1\le n\le x\}. For n>1n>1, the function in (1) is the function denoted by w1(n)w_1(n) by Erdős [3], who also considered its iterates. Such iterates will not be considered in this paper, so we write w(n)=w1(n)w(n)=w_1(n). We also adopt the empty-sum convention such that w(1)=0w(1)=0. A problem introduced by Erdős in 1980 [3] is given by whether or not V(x)=o(x)V(x)=o(x), and Erdős described this problem by stating it “perhaps is not hopeless.” This same problem is also given as an unsolved problem in Guy’s famous text on unsolved problems in number theory [4 p. 64], and it seems that this same problem has remained open, in view of the extant references citing Erdős’s work [3], and in view of the extant material in the entries in the Online Encyclopedia of Integer Sequences1 that agree (up to initial terms) with the integer sequence defined in (1), namely, the OEIS entries A028236 and A066504. We succeed, based on our extensive interactions with GPT-6 Astra Pro, in solving Erdős’s problem, by proving that V(x)≠o(x)V(x)\ne o(x). Furthermore, we prove the stronger result such that lim inf⁡x→∞V(x)x>0\liminf_{x\to\infty}\frac{V(x)}{x}>0.

2020 Mathematics Subject Classification. Primary 11N64; Secondary 11N36.

Key words and phrases. arithmetic function, Brun–Titchmarsh inequality, asymptotic estimate, sieve method, prime factorization.

Brief outline

Our proof uses integers of the form n=etrp≤xn=etrp\le x, where e≡2(mod4)e\equiv2\pmod{4} and tt, rr, and pp are primes in suitably separated ranges. We construct a set of such integers whose cardinality is bounded below by a fixed positive multiple of xx, and we bound the number of ordered pairs of its elements having the same value under ww by a fixed multiple of xx. The desired lower bound for V(x)V(x) then follows from the Cauchy–Schwarz inequality. Writing a=etra=etr, the identity w(ap)=p w(a)+aw(ap)=p\,w(a)+a reduces the equality w(ap)=w(bq)w(ap)=w(bq) to a linear equation in the primes pp and qq, to which we apply a uniform sieve estimate.

The two smaller prime factors have different roles in estimating the resulting weights. For fixed distinct cc and dd in this construction, writing a=cra=cr and b=dsb=ds, every positive common divisor of w(cr)w(cr), w(ds)w(ds), and cr−dscr-ds divides the nonzero integer c2w(d)−d2w(c)c^{2}w(d)-d^{2}w(c). The chosen ranges ensure that this integer is smaller in absolute value than the primes rr and ss, allowing an average over rr and ss through the Brun–Titchmarsh inequality. Writing c=etc=et and d=fud=fu, we then average over tt: For fixed ee, ff, and uu, the same integer is the value of a quadratic polynomial in tt whose content is gcd⁡(e,f)2\gcd(e,f)^2. A uniform estimate for polynomial values at primes, followed by a harmonic gcd estimate, controls the remaining weight. Related polynomial averages control the prime-factor weights contributed by the sieve. The case c=dc=d is treated separately.

Preliminaries

Let D⊆[0,∞)D\subseteq[0,\infty) be unbounded, and let F,G:D→RF,G:D\to\mathbb{R} be functions that may depend on parameters ρ1,ρ2,…,ρn\rho_1,\rho_2,\ldots,\rho_n. Assume that: For each fixed admissible choice of these parameters, the relation G(x)≥0G(x)\ge0 holds for all sufficiently large x∈Dx\in D. We then write F≪ρ1,ρ2,…,ρnGF\ll_{\rho_1,\rho_2,\ldots,\rho_n}G as x→∞x\to\infty through DD to indicate that: For each fixed and admissible choice of ρ1,ρ2,…,ρn\rho_1,\rho_2,\ldots,\rho_n, there are constants C=C(ρ1,ρ2,…,ρn)>0C=C(\rho_1,\rho_2,\ldots,\rho_n)>0 and x0=x0(ρ1,ρ2,…,ρn)≥0x_0=x_0(\rho_1,\rho_2,\ldots,\rho_n)\ge0 (possibly depending on the given parameters) such that ∣F(x)∣≤CG(x)\lvert F(x)\rvert\le CG(x) holds for all x∈Dx\in D such that x≥x0x\ge x_0. Observe that CC and x0x_0 are independent of xx. Also observe that no uniformity with respect to the given parameters is asserted. We may then define ≪\ll accordingly, via an empty set of parameters.

We require the use of a number of familiar and fundamental arithmetic functions. In this direction, we let ω(n)\omega(n) denote the number of distinct prime divisors of n≥2n\ge2, with the convention such that ω(1)=0\omega(1)=0. We recall the usual notation π(x)\pi(x) for the prime-counting function giving the number of primes not exceeding xx, and we recall one of the most fundamental results in all of number theory, namely, the prime number theorem asserting that π(x)∼xlog⁡x\pi(x)\sim\frac{x}{\log x}. We also make use of the usual notation for the counting function for primes in arithmetic progressions, writing

π(x;d,a)=∣{p:p is prime, p≤x, p≡a(modd)}∣(2)\pi(x;d,a)=\lvert\{p:p\text{ is prime},\ p\le x,\ p\equiv a\pmod d\}\rvert \tag*{(2)}

for x∈R≥0x\in\mathbb{R}_{\ge0}, d∈Z≥1d\in\mathbb{Z}_{\ge1}, and a∈Za\in\mathbb{Z}. Recalling that Euler’s totient function is defined so that φ(n)=∣{a∈Z:1≤a≤n,gcd⁡(a,n)=1}∣\varphi(n)=\lvert\{a\in\mathbb{Z}:1\le a\le n,\gcd(a,n)=1\}\rvert, a well known generalization of the prime number theorem is such that π(x;d,a)∼xφ(d)log⁡x\pi(x;d,a) \sim\frac{x}{\varphi(d)\log x} (i.e., for fixed dd and aa satisfying gcd⁡(a,d)=1\gcd(a,d)=1 and as x→∞x \to\infty), but we require an explicit bound for π(x;d,a)\pi(x;d,a) given below.

A fundamental property concerning the arithmetic function defined in (2) is the Brun–Titchmarsh inequality. A formulation of this result attributed to Montgomery and Vaughan [5] gives us that: If dd and aa are positive integers that are relatively prime, then

π(x;d,a)<2xφ(d)log⁡(xd)(3)\pi(x;d,a) < \frac{2x}{\varphi(d)\log\left(\frac{x}{d}\right)} \tag*{(3)}

holds for all x>dx>d, referring to Crandall and Pomerance’s text for background [2 p. 43]. We require the relation in (3) for our main construction.

We henceforth adopt the convention whereby variables denoted with pp in indexing sets for sums and products are prime, and we recall Euler’s product formula for the totient function giving that

φ(n)=n∏p∣n(1−1p)(4)\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right) \tag*{(4)}

for each positive integer nn (with the empty product being interpreted as being equal to 1). We also recall Bézout’s identity giving us that: For integers AA and BB that are not both equal to 0, there exist integers uu and vv such that Au+Bv=gcd⁡(A,B)Au+Bv=\gcd(A,B).

We require some fundamental inequalities often applied in analysis and number theory, including a formulation of Hölder’s inequality giving us that: For real numbers p,q>1p,q>1 such that 1p+1q=1\frac{1}{p}+\frac{1}{q}=1, and for a positive integer NN, and for complex numbers a1,a2,…,aNa_1,a_2,\ldots,a_N and b1,b2,…,bNb_1,b_2,\ldots,b_N, the inequality

∑i=1N∣aibi∣≤(∑i=1N∣ai∣p)1p(∑i=1N∣bi∣q)1q(5)\sum_{i=1}^{N}|a_i b_i|\leq\left(\sum_{i=1}^{N}|a_i|^p\right)^{\frac{1}{p}}\left(\sum_{i=1}^{N}|b_i|^q\right)^{\frac{1}{q}} \tag*{(5)}

holds.

We also make use of some familiar terminology arising in the number-theoretic study of polynomials. For a nonzero polynomial PP with integer coefficients, the content of PP, denoted by cont⁡(P)\operatorname{cont}(P), refers to the positive greatest common divisor of its coefficients. A primitive polynomial is a nonzero polynomial with integer coefficients whose coefficients have greatest common divisor 1.

Main construction

We begin by briefly establishing some basic and required properties concerning the integer sequence in (1).

Lemma 1. For each positive integer nn, the equality gcd⁡(n,w(n))=1\gcd(n,w(n))=1 holds.

Proof. This is immediate for n=1n=1. If pα∥n>1p^\alpha\parallel n>1, then all terms in the expansion of w(n)w(n) displayed in (1) apart from npα\frac{n}{p^\alpha} are divisible by pp, whereas the exceptional term is not. Thus no prime divisor of nn divides w(n)w(n), proving the claim. □\square

Lemma 2. Suppose that aa is a positive integer and pp is a prime such that p∤ap \nmid a. Then the relation w(ap)=p w(a)+aw(ap)=p\,w(a)+a holds.

Proof. This is a special case of the relation such that: If aa and bb are positive and relatively prime integers, then w(ab)=a w(b)+b w(a)w(ab)=a\,w(b)+b\,w(a), and, in turn, this follows in a direct way from the definition in (1). □\square

References

  1. [1]Alina Carmen Cojocaru and M. Ram Murty. An Introduction to Sieve Methods and Their Applications, volume 66 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 2005.DOI
  2. [2]Richard Crandall and Carl Pomerance. Prime numbers. Springer, New York, second edition, 2005. A computational perspective.
  3. [3]Paul Erdős. Problems and results in number theory and graph theory. In Proceedings of the Ninth Manitoba Conference on Numerical Mathematics and Computing (Univ. Manitoba, Winnipeg, Man., 1979), volume XXVII of Congress. Numer., pages 3–21. Utilitas Math., Winnipeg, MB, 1980.
  4. [4]Richard K. Guy. Unsolved problems in number theory. Problem Books in Mathematics. Springer-Verlag, New York, second edition, 1994. Unsolved Problems in Intuitive Mathematics, I.
  5. [5]H. L. Montgomery and R. C. Vaughan. The large sieve. Mathematika, 20:119–134, 1973.

Paper details

vlnc:W_4tszz6un
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 16

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents