betaFeedback

WorksMathematics

A solution to the Erdős-Sárközy product-density problem

Abstract

Color each positive integer red or blue, and call an integer a same-color product if it is the product of two red numbers or of two blue numbers. Does there exist a universal constant c>0c > 0 such that: For each fixed coloring, and for all sufficiently large MM (where "sufficiently large" may depend on the coloring), at least cMcM of the integers among 11, 22, …\ldots, MM are same-colored products (allowing for equal factors, and where each distinct product is counted once)? This problem was given (in an equivalent way) in Guy's famous text on unsolved problems in number theory, and was posed (in equivalent ways) by Erdős and Sárközy in 1990, in the proceedings of the 1988 Banff number theory conference, and 1993 [Colloq. Math.], and this problem seems to have remained open. We succeed in solving this problem, by proving that no such universal constant exists.

Introduction

Multiplicative Ramsey theory is a deep and challenging area in combinatorial number theory. A foundational reference in multiplicative Ramsey theory is due to Hindman [9], who introduced and proved a result that gives that each finite coloring of N\mathbb{N} admits a strictly increasing infinite sequence such that each nonempty finite product of distinct terms has the same color. Some similarly notable works are due to Bergelson et al. [2, 3], Green and Sanders [7], and Moreira [10]. We solve, building on our extensive interactions with GPT-6 Astra Pro, a problem in the field of multiplicative Ramsey theory that is given in Guy’s classic textbook on unsolved problems in number theory [8 p. 204] and that was repeatedly posed by Erdős and Sárközy [5, 6]. It appears that this problem has, prior to our work, remained open.

Erdős and Sárközy [5, 6] pose the following question: For each ε>0\varepsilon> 0, is it true that there is a partition {A1,A2}\{A_1, A_2\} of N\mathbb{N} such that the lower asymptotic density of the sequence consisting of the distinct monochromatic products aa′aa' is less than ε\varepsilon? In this context, a positive integer nn is said to be a monochromatic product if it admits at least one factorization of the form n=aa′n = aa' such that the two factors aa and a′a' are either both in A1A_1 or are both in A2A_2. In this paper, we answer Erdős and Sárközy’s question in the

2020 Mathematics Subject Classification. Primary 11B05; Secondary 05D10.

Key words and phrases. lower asymptotic density, multiplicative Ramsey theory, combinatorial number theory, monochromatic products. affirmative. The problem given by determining whether or not this question holds is equivalent to a problem in Guy’s classic text on unsolved problems in number theory [8 p. 204], in the sense that a solution to one problem gives a solution to the other problem. More specifically, a negative solution to Guy’s problem is equivalent to a solution in the affirmative to the Erdős–Sárközy problem. For every fixed finite partition, the lower density of the monochromatic products is positive [5], but what is at issue is whether that positive lower bound can be chosen independently of the partition.

For a 2-coloring C\mathcal{C} of N\mathbb{N}, write

rC(N)=# distinct monochromatic products among 1, 2, …, NN(1)r_{\mathcal{C}}(N)=\frac{\#\text{ distinct monochromatic products among }1,\,2,\,\ldots,\,N}{N} \tag*{(1)}

and

dC=lim inf⁡N→∞rC(N).(2)d_{\mathcal{C}}=\liminf_{N\to\infty}r_{\mathcal{C}}(N). \tag*{(2)}

Thus the Erdős–Sárközy problem above is given by whether or not it is the case that

∀ε>0 ∃C dC<ε.(3)\forall\varepsilon>0\ \exists\mathcal{C}\ d_{\mathcal{C}}<\varepsilon. \tag*{(3)}

As suggested in the above abstract, the problem given by whether or not (3) holds is equivalent to the problem as to whether or not the negation

∃ε>0 ∀C dC≥ε(4)\exists\varepsilon>0\ \forall\mathcal{C}\ d_{\mathcal{C}}\geq\varepsilon \tag*{(4)}

holds. More precisely, and in view of (2), we find that (4) is equivalent (as clarified below) to

∃c>0 ∀C ∃NC ∀M≥NC#(distinct monochromatic products among 1, 2, …, M)≥cM,\exists c>0\ \forall\mathcal{C}\ \exists N_{\mathcal{C}}\ \forall M\geq N_{\mathcal{C}}\quad\#\text{(distinct monochromatic products among }1,\,2,\,\ldots,\,M)\geq cM,

i.e., for a universal constant c>0c>0. To justify this equivalence, if, for fixed ε>0\varepsilon>0 and for each coloring C\mathcal{C}, we have that lim inf⁡ℓ→∞rC(ℓ)≥ε>0\liminf_{\ell\to\infty}r_{\mathcal{C}}(\ell)\geq\varepsilon>0, then, for every coloring C\mathcal{C}, we have that rC(M)≥ε2r_{\mathcal{C}}(M)\geq\frac{\varepsilon}{2} for sufficiently large MM. Conversely, if, for fixed c>0c>0 and for every coloring C\mathcal{C}, we have that rC(M)≥c>0r_{\mathcal{C}}(M)\geq c>0 for sufficiently large MM, then lim inf⁡ℓ→∞rC(ℓ)≥c>0\liminf_{\ell\to\infty}r_{\mathcal{C}}(\ell)\geq c>0. As indicated above, we prove that no universal constant of the form c>0c>0 indicated above can exist, thus proving (3) in the affirmative.

Example 1. Let each odd and positive integer be colored red. Let each even and positive integer be colored blue. According to this coloring, for a positive integer MM, let a(M)a(M) denote the number of distinct monochromatic products among 1, 2, …, M1,\,2,\,\ldots,\,M. For example, we see that a(9)=7a(9)=7, since the associated monochromatic products are as shown below.

1=1⋅1,3=1⋅3,4=2⋅2,5=1⋅5,7=1⋅7,8=2⋅4,9=1⋅9=3⋅3.1=1\cdot1,\quad3=1\cdot3,\quad4=2\cdot2,\quad5=1\cdot5,\quad7=1\cdot7,\quad8=2\cdot4,\quad9=1\cdot9=3\cdot3.

Observe that 2=1⋅22 = 1 \cdot2 does not qualify, and observe that 6=1⋅6=2⋅36 = 1 \cdot6 = 2 \cdot3 also does not qualify. It is easily seen (omitting details) that the integer sequence (a(n):n∈N)(a(n) : n \in\mathbb{N}), as defined above, may be explicitly evaluated so that

a(n)=⌊3n+14⌋.(5)a(n) = \left\lfloor\frac{3n+1}{4} \right\rfloor. \tag*{(5)}

This agrees with the sequence indexed in the On-line Encyclopedia of Integer Sequences1 as A037915, but there is not currently any equivalent definition of a(n)a(n), as defined above, given. From the evaluation in (5), we find that, according to the specified coloring CC, and with respect to the notation in (1), the evaluation lim⁡N→∞rC(N)=34\lim_{N \to\infty} r_C(N) = \frac{3}{4} holds.

The problem indicated above may be seen in relation to subsequent work related to the given Erdős–Sárközy references [5, 6]. Csikvári et al. [4 Theorem 7] use the logarithmic-density theorem for monochromatic products from Erdős and Sárközy [5] to establish positive lower logarithmic density for integers admitting both monochromatic sum and product representations, with the two representations allowed to use different colours. However, this result does not settle the two-class lower-asymptotic-density problem studied here. The Erdős–Sárközy problem above may also be seen in contrast to a related problem on colorings of sums of integers, as opposed to products of integers, with reference to the so-called Erdős Problem #48422.

Main construction

We begin by covering some basic preliminaries. In this direction, for a subset SS of the set N\mathbb{N} of positive integers, we write SSSS in place of {st:s,t∈S}\{st : s,t \in S\} (where repeated factor are permitted). For subsets SS and TT contained in N\mathbb{N}, we write

P(S,T)=SS∪TT.(6)P(S,T) = SS \cup TT. \tag*{(6)}

We require some familiar arithmetic functions, and, in this direction, we recall the prime-counting function π(x)\pi(x) giving the number primes pp less than or equal to a given real value xx, and we let vp(n)v_p(n) denote the exponent of pp in the prime factorization of the positive integer nn. Throughout, sums indexed by pp are understood as being over primes.

We also require some basic properties of the special function known as the digamma function, which may be defined so that ψ(x)=Γ′(x)Γ(x)\psi(x) = \frac{\Gamma'(x)}{\Gamma(x)} for x>0x > 0 and for the familiar Γ\Gamma-function, referring to Rainville’s classic text for background [11 §2]. For the Euler–Mascheroni constant γ=lim⁡n→∞(1+12+⋯+1n−\gamma= \lim_{n \to\infty} (1 + \frac{1}{2} + \cdots+ \frac{1}{n} - log⁡n\log n), a fundamental property of the digamma function is such that

ψ(z)=−γ−1z+∑n=1∞zn(z+n)(7)\psi(z)=-\gamma-\frac{1}{z}+\sum_{n=1}^{\infty}\frac{z}{n(z+n)} \tag*{(7)}

for real z>0z>0. A consequence of a result due to Alzer and Berg [1, Theorem 4.2(i)] is such that

ψ(b+1)−ψ(a+1)≤log⁡(ba)(8)\psi(b+1)-\psi(a+1)\le\log\left(\frac{b}{a}\right) \tag*{(8)}

for 0<a≤b0<a\le b, which follows from the mapping x↦ψ(x+1)−log⁡xx\mapsto\psi(x+1)-\log x being nonincreasing on (0,∞)(0,\infty).

We require, for the purposes of the proof below, a well known consequence of Markov’s inequality. This may be seen as a “non-probabilistic” version of Markov’s inequality, and this may be formulated as follows. Suppose that EE is a finite set. Then, for a mapping F:E→[0,∞)F:E\to[0,\infty) and for a positive value η\eta, the relation

η∣{u∈E:F(u)≥η}∣≤∑u∈EF(u)(9)\eta\left|\{u\in E:F(u)\ge\eta\}\right|\le\sum_{u\in E}F(u) \tag*{(9)}

holds.

Some further notation local to our construction is given as follows. By letting q≥2q\ge2 be real, we write

L(q)=∑p≤q1p,(10)L(q)=\sum_{p\le q}\frac{1}{p}, \tag*{(10)}

noting that the condition q≥2q\ge2 guarantees that L(q)>0L(q)>0. Recall that a fundamental result in number theory (attributed to Euler) is such that L(q)→∞L(q)\to\infty as q→∞q\to\infty. Now, for a real value θ∈(0,1)\theta\in(0,1), define

Hθ(N,q)=∣{n∈N:n≤N, ∃d∣n θq≤d≤q}∣.(11)H_\theta(N,q)=\left|\{n\in\mathbb{N}:n\le N,\ \exists d\mid n\ \theta q\le d\le q\}\right|. \tag*{(11)}

The definition in (11) leads us toward Lemma 1 below.

Lemma 1. Let θ∈(0,1)\theta\in(0,1). Suppose that

q≥max⁡{2,θ−1},(12)q\ge\max\{2,\theta^{-1}\}, \tag*{(12)}

and suppose that

N≥q2,(13)N\ge q^2, \tag*{(13)}

for real values qq and NN. Then

Hθ(N,q)≤KθNL(q),H_\theta(N,q)\le K_\theta\frac{N}{L(q)},

for Kθ=48θ+100+48log⁡1θK_\theta=\frac{48}{\theta}+100+48\log\frac{1}{\theta} (noting that L(q)>0L(q)>0 since q≥2q\ge2).

Proof. Write L=L(q)L=L(q) for brevity (again noting that L>0L>0 from the hypothesis in (12)). We then define

F(n)=∑p≤q1p∣n,(14)F(n)=\sum_{p\le q}\mathbf{1}_{p\mid n}, \tag*{(14)}

letting indicator functions be denoted as per usual. We also define

R(n)=∑p≤qmax⁡{νp(n)−1,0}.(15)R(n)=\sum_{p\le q}\max\{\nu_p(n)-1,0\}. \tag*{(15)}

For a real value M≥qM\ge q, we find that

∑n≤M(F(n)−L)2=∑p≤q⌊Mp⌋+2∑p≤q∑p<r≤qr prime⌊Mpr⌋−2L∑p≤q⌊Mp⌋+L2⌊M⌋.\begin{aligned} \sum_{n\le M}(F(n)-L)^2 &=\sum_{p\le q}\left\lfloor\frac{M}{p}\right\rfloor +2\sum_{p\le q}\sum_{\substack{p<r\le q\\r\ \mathrm{prime}}}\left\lfloor\frac{M}{pr}\right\rfloor -2L\sum_{p\le q}\left\lfloor\frac{M}{p}\right\rfloor +L^2\lfloor M\rfloor. \end{aligned}

Applying the relation ⌊x⌋≤x\lfloor x\rfloor\le x to the positive terms, and applying the relation ⌊x⌋≥x−1\lfloor x\rfloor\ge x-1 in the negative terms, we find that

∑n≤M(F(n)−L)2≤M(L−∑p≤q1p2)+2Lπ(q).(16)\sum_{n\le M}(F(n)-L)^2\le M\left(L-\sum_{p\le q}\frac{1}{p^2}\right)+2L\pi(q). \tag*{(16)}

Since

π(q)≤q≤M,(17)\pi(q)\le q\le M, \tag*{(17)}

the relation in (16) gives us that

∑n≤M(F(n)−L)2≤3ML.(18)\sum_{n\le M}(F(n)-L)^2\le3ML. \tag*{(18)}

Now, consider the families among

{n≤M:F(n)<3L4}and{n≤M:F(n)≥5L4}.(19)\left\{n\le M:F(n)<\frac{3L}{4}\right\}\quad\text{and}\quad\left\{n\le M:F(n)\ge\frac{5L}{4}\right\}. \tag*{(19)}

Since F(n)<3L4⇒∣F(n)−L∣>L4F(n)<\frac{3L}{4}\Rightarrow|F(n)-L|>\frac{L}{4} and since F(n)≥5L4⇒∣F(n)−L∣≥L4F(n)\ge\frac{5L}{4}\Rightarrow|F(n)-L|\ge\frac{L}{4}, either case gives us that (F(n)−L)2≥L216(F(n)-L)^2\ge\frac{L^2}{16}. This and (18) together give us that each of the families indicated in (19) has at most 48ML\frac{48M}{L} members. Also, by using the evaluation ∑m≥21m(m−1)=1\sum_{m\ge2}\frac{1}{m(m-1)}=1, we find that

∑n≤MR(n)=∑p≤q∑k≥2⌊Mpk⌋≤M∑p≤q1p(p−1)≤M.(20)\sum_{n\le M}R(n)=\sum_{p\le q}\sum_{k\ge2}\left\lfloor\frac{M}{p^k}\right\rfloor\le M\sum_{p\le q}\frac{1}{p(p-1)}\le M. \tag*{(20)}

Now, since R(n)≥0R(n)\ge0 (recalling (15)) and since L>0L>0 (recalling (10)), by applying the consequence of Markov’s inequality on display in (9) to the function RR, with E={1,2,…,[M]}E=\{1,2,\ldots,[M]\} and with η=L4\eta=\frac{L}{4}, we find that

∣{n≤M:R(n)>L4}∣≤∣{n≤M:R(n)≥L4}∣(21)\left|\left\{n\le M:R(n)>\frac{L}{4}\right\}\right|\le\left|\left\{n\le M:R(n)\ge\frac{L}{4}\right\}\right| \tag*{(21)}
≤4L∑n≤MR(n),(22)\le\frac{4}{L}\sum_{n\le M}R(n), \tag*{(22)}

so that a joint application of (20) and (21) gives us that

∣{n≤M:R(n)>L4}∣≤4ML.(23)\left|\left\{n\le M:R(n)>\frac{L}{4}\right\}\right|\le\frac{4M}{L}. \tag*{(23)}

This leads us toward the following case analysis, where the cases below correspond to the conditions associated with the sets of the forms DiD_i and Sd(i)S_d^{(i)} defined below.

Case 1. Define

D1={d∈N:θq≤d≤q, F(d)<3L4},(24)D_1=\left\{d\in\mathbb{N}:\theta q\le d\le q,\ F(d)<\frac{3L}{4}\right\}, \tag*{(24)}

and, for each d∈D1d\in D_1, define

Sd(1)={dk:k∈N, dk≤N}.S_d^{(1)}=\{dk:k\in\mathbb{N},\ dk\le N\}.

Taking M=qM=q in the established bound for the first set in (19), we obtain

∣D1∣≤∣{m∈N:m≤q, F(m)<3L4}∣≤48qL.(25)|D_1|\le\left|\left\{m\in\mathbb{N}:m\le q,\ F(m)<\frac{3L}{4}\right\}\right|\le\frac{48q}{L}. \tag*{(25)}

Again for dd in the family defined in (23), since d≥θqd\ge\theta q, we find that

∣Sd(1)∣=⌊Nd⌋≤Nd≤Nθq.(26)\left|S_d^{(1)}\right|=\left\lfloor\frac{N}{d}\right\rfloor\le\frac{N}{d}\le\frac{N}{\theta q}. \tag*{(26)}

The union ⋃d∈D1Sd(1)\bigcup_{d\in D_1}S_d^{(1)} is exactly the set of positive integers n≤Nn\le N having at least one divisor in D1D_1. Consequently, an application of the inclusion–exclusion principle gives us that ∣⋃d∈D1Sd(1)∣≤∑d∈D1∣Sd(1)∣\left|\bigcup_{d\in D_1}S_d^{(1)}\right|\le\sum_{d\in D_1}\left|S_d^{(1)}\right|. This and (24) and (25) together give us that

∣⋃d∈D1Sd(1)∣≤∣D1∣Nθq≤48NθL.(27)\begin{aligned} \left|\bigcup_{d\in D_1}S_d^{(1)}\right|\le|D_1|\frac{N}{\theta q} \\ &\le\frac{48N}{\theta L}. \tag*{(27)} \end{aligned}

Case 2. Define

D2={d∈N:θq≤d≤q, F(d)≥3L4},(28)D_2=\left\{d\in\mathbb{N}:\theta q\le d\le q,\ F(d)\ge\frac{3L}{4}\right\}, \tag*{(28)}

and, for each element d∈D2d \in D_2, define

Sd(2)={dk:k∈N, dk≤N, F(k)<3L4}.(29)S_d^{(2)}=\left\{dk:k\in\mathbb{N},\,dk\leq N,\,F(k)<\frac{3L}{4}\right\}. \tag*{(29)}

For a fixed integer dd in D2D_2, we find that

Nd≥Nq.(30)\frac{N}{d}\geq\frac{N}{q}. \tag*{(30)}

From the hypothesis indicated in (13), we find that (30) implies that

Nd≥q.(31)\frac{N}{d}\geq q. \tag*{(31)}

The relation in (31) allows us to let M=NdM=\frac{N}{d}, recalling that M≥qM\geq q. So, from the established upper bound for the first family on display in (19), we find that

∣{n≤Nd:F(n)<3L4}∣≤48NdL.(32)\left|\left\{n\leq\frac{N}{d}:F(n)<\frac{3L}{4}\right\}\right|\leq\frac{48N}{dL}. \tag*{(32)}

We rewrite (32) so that ∣{n≤Nd:F(n)<3L4}∣≤48NdL\left|\left\{n\leq\frac{N}{d}:F(n)<\frac{3L}{4}\right\}\right|\leq\frac{48N}{dL}, and this then gives us that

∣{k∈N:kd≤N,F(k)<3L4}∣≤48NdL.(33)\left|\left\{k\in\mathbb{N}:kd\leq N,F(k)<\frac{3L}{4}\right\}\right|\leq\frac{48N}{dL}. \tag*{(33)}

For each member kk in the family whose cardinality is given as the left-hand side of the inequality in (33), we obtain a different value of n=dk≤Nn=dk\leq N. So, again for a given fixed value of dd, there are (according to (33)) at most 48NdL\frac{48N}{dL} integers n≤Nn\leq N admitting a factorization of the form n=dkn=dk such that F(k)<3L4F(k)<\frac{3L}{4}.

It is immediate that the right-hand side of (28) has the same cardinality as {k∈N:kd≤N,F(k)<3L4}\left\{k\in\mathbb{N}:kd\leq N,F(k)<\frac{3L}{4}\right\}. So, from the relation in (32), we find that ∣Sd(2)∣≤48NdL\left|S_d^{(2)}\right|\leq\frac{48N}{dL}. This and an application of the inclusion–exclusion principle give us that

∣⋃d∈D2Sd(2)∣≤∑d∈D2∣Sd(2)∣≤48NL∑d∈D21d≤48NL∑d∈Nθq≤d≤q1d.\left|\bigcup_{d\in D_2}S_d^{(2)}\right| \leq\sum_{d\in D_2}\left|S_d^{(2)}\right| \leq\frac{48N}{L}\sum_{d\in D_2}\frac{1}{d} \leq\frac{48N}{L}\sum_{\substack{d\in\mathbb{N}\\ \theta q\leq d\leq q}}\frac{1}{d}.

Since ψ\psi is increasing on (0,∞)(0,\infty) (and this may be seen via the series expansion shown in (7)), and since the recurrence ψ(x+1)−ψ(x)=1x\psi(x+1)-\psi(x)=\frac{1}{x} holds, a telescoping argument and the Alzer–Berg inequality in (8) (applied with a=θqa=\theta q and b=qb=q) give us that

∑d∈Nθq≤d≤q1d=∑d∈Nθq≤d≤q(ψ(d+1)−ψ(d))≤ψ(q+1)−ψ(θq)=1θq+ψ(q+1)−ψ(θq+1)≤1θq+log⁡(1θ)≤1+log⁡(1θ).\begin{aligned} \sum_{\substack{d\in\mathbb{N}\\ \theta q\le d\le q}}\frac{1}{d} &=\sum_{\substack{d\in\mathbb{N}\\ \theta q\le d\le q}}\left(\psi(d+1)-\psi(d)\right)\\ &\le\psi(q+1)-\psi(\theta q)\\ &=\frac{1}{\theta q}+\psi(q+1)-\psi(\theta q+1)\\ &\le\frac{1}{\theta q}+\log\left(\frac{1}{\theta}\right)\\ &\le1+\log\left(\frac{1}{\theta}\right). \end{aligned}

noting that this last inequality holds since q≥θ−1q\ge\theta^{-1}, i.e., from the hypothesis displayed in (12). A combined application of the given bounds for ∣⋃d∈D2Sd(2)∣\left|\bigcup_{d\in D_2}S_d^{(2)}\right| and ∑d∈Nθq≤d≤q1d\sum_{\substack{d\in\mathbb{N}\\ \theta q\le d\le q}}\frac{1}{d} gives us that

∣⋃d∈D2Sd(2)∣≤48NL(1+log⁡(1θ)).(34)\left|\bigcup_{d\in D_2}S_d^{(2)}\right|\le\frac{48N}{L}\left(1+\log\left(\frac{1}{\theta}\right)\right). \tag*{(34)}

Case 3. Let D2D_2 be as in (28), and, for each member dd in D2D_2, define

Sd(3)={dk:k∈N, dk≤N, F(k)≥3L4}.(35)S_d^{(3)}=\left\{dk:k\in\mathbb{N},\ dk\le N,\ F(k)\ge\frac{3L}{4}\right\}. \tag*{(35)}

Let n∈Sd(3)n\in S_d^{(3)}, and write k=ndk=\frac{n}{d}. From the definition in (14), we find that

F(d)+F(k)−F(n)=∑p≤qp∣d, p∣k1.(36)F(d)+F(k)-F(n)=\sum_{\substack{p\le q\\ p\mid d,\ p\mid k}}1. \tag*{(36)}

Now, observe that a given prime p≤qp\le q dividing both dd and kk is such that vp(n)≥2v_p(n)\ge2 and thus contributes at least 1 as a term on the right-hand side of (15). From (36), we thus have that

F(d)+F(k)−F(n)≤R(n).(37)F(d)+F(k)-F(n)\le R(n). \tag*{(37)}

From (37) and the assumptions that F(d)≥3L4F(d)\ge\frac{3L}{4} and that F(k)≥3L4F(k)\ge\frac{3L}{4}, we find that

F(n)≥F(d)+F(k)−R(n)≥3L2−R(n).(38)\begin{aligned} F(n)&\ge F(d)+F(k)-R(n)\\ &\ge\frac{3L}{2}-R(n). \tag*{(38)} \end{aligned}

From (38), we obtain the implication R(n)≤L4⇒F(n)≥5L4R(n)\le\frac{L}{4}\Rightarrow F(n)\ge\frac{5L}{4}. So, each member nn in Sd(3)S_d^{(3)} is such that R(n)>L4R(n)>\frac{L}{4} or F(n)≥5L4F(n)\ge\frac{5L}{4}. Since this holds for an arbitrary member dd of D2D_2, and since the definition in (35) gives us that each member in Sd(3)S_d^{(3)} is ≤N\leq N, we find that the inclusion

⋃d∈D2Sd(3)⊆{n∈N:n≤N, R(n)>L4}∪{n∈N:n≤N, F(n)≥5L4}\bigcup_{d\in D_2} S_d^{(3)} \subseteq \left\{n\in\mathbb{N}: n\leq N,\ R(n)>\frac{L}{4}\right\} \cup \left\{n\in\mathbb{N}: n\leq N,\ F(n)\geq\frac{5L}{4}\right\}

holds, and we thus obtain that

∣⋃d∈D2Sd(3)∣≤∣{n∈N:n≤N, R(n)>L4}∣+∣{n∈N:n≤N, F(n)≥5L4}∣.\left|\bigcup_{d\in D_2} S_d^{(3)}\right| \leq \left|\left\{n\in\mathbb{N}: n\leq N,\ R(n)>\frac{L}{4}\right\}\right| + \left|\left\{n\in\mathbb{N}: n\leq N,\ F(n)\geq\frac{5L}{4}\right\}\right|.

From (12) and (13) together, we find that N≥qN\geq q. This allows us (recalling that M≥qM\geq q, as in (17)) to set M=NM=N, i.e., in the established bounds for the latter family in (19) and in the bound on display in (23). Using these established bounds, the above bound for ∣⋃d∈D2Sd(3)∣\left|\bigcup_{d\in D_2} S_d^{(3)}\right| gives us that

∣⋃d∈D2Sd(3)∣≤4NL+48NL=52NL.(39)\left|\bigcup_{d\in D_2} S_d^{(3)}\right| \leq\frac{4N}{L}+\frac{48N}{L} = \frac{52N}{L}. \tag*{(39)}

Now, recall the definition of Hθ(N,q)H_\theta(N,q) on display in (11), giving a family of positive integers n≤Nn\leq N admitting a factorization n=kdn=kd for positive integers kk and dd, with θq≤d≤q\theta q\leq d\leq q. Each such factorization satisfies one of the conditions used to define Cases 1–3, so that

Hθ(N,q)≤∣⋃d∈D1Sd(1)∣+∣⋃d∈D2Sd(2)∣+∣⋃d∈D2Sd(3)∣.(40)H_\theta(N,q)\leq \left|\bigcup_{d\in D_1} S_d^{(1)}\right| + \left|\bigcup_{d\in D_2} S_d^{(2)}\right| + \left|\bigcup_{d\in D_2} S_d^{(3)}\right|. \tag*{(40)}

So, a combined application of the inequalities among (27), (34), (39), and (40) gives us that

Hθ(N,q)≤48NθL+48NL(1+log⁡1θ)+52NL=KθNL(q),H_\theta(N,q)\leq\frac{48N}{\theta L}+\frac{48N}{L}\left(1+\log\frac{1}{\theta}\right)+\frac{52N}{L} =K_\theta\frac{N}{L(q)},

as desired. □

Lemma 2. Let θ∈(0,1)\theta\in(0,1) and let δ>0\delta>0. Then there exist a strictly increasing sequence (Nj:j∈N)(N_j:j\in\mathbb{N}) of positive integers and a set

S⊆(max⁡{2,θ−1},∞)∖Q(41)S\subseteq\left(\max\{2,\theta^{-1}\},\infty\right)\setminus\mathbb{Q} \tag*{(41)}

such that:

  • (a) Each bounded interval contains only finitely many elements of SS;

  • (b) For each positive integer jj, the value Nj\sqrt{N_j} is in SS;

  • (c) The elements in SS are such that

∑s∈S1L(s)≤δ;\sum_{s\in S}\frac{1}{L(s)}\le\delta;

and

  • (d) The function

χ(x)=(−1)∣S∩(1,x)∣(42)\chi(x)=(-1)^{|S\cap(1,x)|} \tag*{(42)}

defined for x∈Qx\in\mathbb{Q} and x≥1x\ge1 is such that

χ(x)=−χ(Njx)(43)\chi(x)=-\chi\left(\frac{N_j}{x}\right) \tag*{(43)}

for j≥1j\ge1 and

x∈[1,Nj]∩Q.(44)x\in[1,N_j]\cap\mathbb{Q}. \tag*{(44)}

Proof. Our strategy is to construct the terms of the desired sequence (Nj:j∈N)(N_j:j\in\mathbb{N}) recursively, starting with N0=1N_0=1. Similarly, we recursively construct a sequence (Sj:j∈N)(S_j:j\in\mathbb{N}) of finite sets to define SS, with

S=⋃j≥1Sj.(45)S=\bigcup_{j\ge1}S_j. \tag*{(45)}

Also, define S0=∅S_0=\varnothing. Now, for an index j≥1j\ge1, with the assumption that Nj−1N_{j-1} and Sj−1S_{j-1} have already been determined, we proceed to choose a positive integer MjM_j satisfying both

Mj>max⁡{Nj−1,2,θ−1}(46)M_j>\max\{N_{j-1},2,\theta^{-1}\} \tag*{(46)}

and

L(Mj)≥4j2δ,(47)L(M_j)\ge\frac{4^j}{2\delta}, \tag*{(47)}

noting that such a selection is permitted by the classical result giving that the right-hand side of (10) approaches ∞\infty as q→∞q\to\infty. Having chosen MjM_j (subject to the given conditions), we proceed to define

Nj=Mj2+1(48)N_j=M_j^2+1 \tag*{(48)}

and

Sj=Sj−1∪{Nj}∪{Njs:s∈Sj−1}.(49)S_j=S_{j-1}\cup\{\sqrt{N_j}\}\cup\left\{\frac{N_j}{s}:s\in S_{j-1}\right\}. \tag*{(49)}

From (45) and (47) together, we obtain that

Nj=Mj2+1>Mj>Nj−1(50)N_j=M_j^2+1>M_j>N_{j-1} \tag*{(50)}

for j≥1j\ge1, thus giving us that (Nj:j∈N)(N_j:j\in\mathbb{N}) is strictly increasing and consists of positive integers. Now, since MjM_j is a positive integer, and since Mj2<Nj=Mj2+1<(Mj+1)2M_j^2 < N_j = M_j^2 + 1 < (M_j+1)^2, we find that NjN_j is not a perfect square, so that Nj\sqrt{N_j} is irrational for each index j≥1j \ge1. Since S0=∅S_0 = \varnothing, the recursion in (49) gives us that S1={N1}S_1 = \{\sqrt{N_1}\}. Since N1\sqrt{N_1} is positive and irrational (as established), we find that S1S_1 is a finite set of positive irrational numbers. Also observe that Njs\frac{N_j}{s} is positive and irrational whenever ss is positive and irrational. So, the recursive definition for SjS_j and the irrationality of Nj\sqrt{N_j} together show that SjS_j is necessarily a finite set consisting of positive and irrational numbers, for each index j≥1j \ge1. We proceed to prove, via induction, that

Sj⊂(max⁡{2,θ−1},Nj)(51)S_j \subset\left(\max\{2,\theta^{-1}\},N_j\right) \tag*{(51)}

for each index j≥1j \ge1.

For the base case, with j=1j = 1, we find that S1={N1}S_1 = \{\sqrt{N_1}\} and that max⁡{2,θ−1}<M1\max\{2,\theta^{-1}\} < M_1, directly from the definition in (46). Similarly, from (48), we find that M1<N1<N1M_1 < \sqrt{N_1} < N_1. So, since max⁡{2,θ−1}<N1<N1\max\{2,\theta^{-1}\} < \sqrt{N_1} < N_1, the inclusion in (51) holds for the current base case. Now, for an index j≥2j \ge2, we (inductively) assume that

Sj−1⊂(max⁡{2,θ−1},Nj−1).(52)S_{j-1} \subset\left(\max\{2,\theta^{-1}\},N_{j-1}\right). \tag*{(52)}

Now, for each element s∈Sj−1s \in S_{j-1}, the inductive hypothesis in (52) gives us that max⁡{2,θ−1}<s<Nj−1\max\{2,\theta^{-1}\} < s < N_{j-1}. Also, from (46), we find that

Nj−1<Mj.(53)N_{j-1} < M_j. \tag*{(53)}

Also, from (48), we find that

Mj<Nj<Nj,(54)M_j < \sqrt{N_j} < N_j, \tag*{(54)}

i.e., so that

max⁡{2,θ−1}<s<Nj.(55)\max\{2,\theta^{-1}\} < s < N_j. \tag*{(55)}

Again letting s∈Sj−1s \in S_{j-1}, from the induction hypothesis shown in (52), we find that s<Nj−1s < N_{j-1}. Moreover, from (53) and (54), we find that

s<Nj−1<Mj<Nj.(56)s < N_{j-1} < M_j < \sqrt{N_j}. \tag*{(56)}

From (56), we see that 1<max⁡{2,θ−1}<s<Nj1 < \max\{2,\theta^{-1}\} < s < \sqrt{N_j}, which, in turn, implies

max⁡{2,θ−1}<Nj<Njs<Nj.(57)\max\{2,\theta^{-1}\} < \sqrt{N_j} < \frac{N_j}{s} < N_j. \tag*{(57)}

From (55) and (57), we obtain the inclusion

Sj=Sj−1∪{Nj}∪{Njs:s∈Sj−1}⊂(max⁡{2,θ−1},Nj),(58)\begin{aligned} S_j &= S_{j-1} \cup\left\{\sqrt{N_j}\right\} \cup\left\{\frac{N_j}{s}:s \in S_{j-1}\right\}\\ &\subset\left(\max\{2,\theta^{-1}\},N_j\right), \tag*{(58)} \end{aligned}

thus completing our induction.

Now, recall that we previously established that SjS_j consists of irrational numbers. From this and (57) together, we find that

S=⋃j≥1Sj⊆(max⁡{2,θ−1},∞)∖Q.S = \bigcup_{j\ge1} S_j \subseteq\left(\max\{2,\theta^{-1}\},\infty\right) \setminus\mathbb{Q}.

To prove the first assertion listed above, we begin by proving that

Sj∖Sj−1⊆(Nj−1,∞)(59)S_j \setminus S_{j-1} \subseteq(N_{j-1},\infty) \tag*{(59)}

for each j≥1j \ge1. Now, recall the relations among Nj−1N_{j-1}, MjM_j, and Nj\sqrt{N_j} shown in (55). By letting s∈Sj−1s \in S_{j-1}, we find, again with reference to (55) (recalling that (55) holds for s∈Sj−1s \in S_{j-1}), that 0<s<Nj0 < s < \sqrt{N_j}. So, the relations in (55) give us that

Njs>NjNj=Nj>Nj−1.(60)\frac{N_j}{s} > \frac{N_j}{\sqrt{N_j}} = \sqrt{N_j} > N_{j-1}. \tag*{(60)}

Now, from the recursion on display in (48), if tt is any element in Sj∖Sj−1S_j \setminus S_{j-1}, then either t=Njt = \sqrt{N_j} or t=Njst = \frac{N_j}{s} for some s∈Sj−1s \in S_{j-1}.

In the former case, the definitions of NjN_j and MjM_j give us that

t=Nj=Mj2+1>Mj>Nj−1.t = \sqrt{N_j} = \sqrt{M_j^2+1} > M_j > N_{j-1}.

In the latter case, we have t=Njst = \frac{N_j}{s} for some s∈Sj−1s \in S_{j-1}, and the previously established inequality s<Njs < \sqrt{N_j} gives us that

t=Njs>Nj>Nj−1.t = \frac{N_j}{s} > \sqrt{N_j} > N_{j-1}.

So, for every j≥1j \ge1, the inclusion

Sj∖Sj−1⊆(Nj−1,∞)S_j \setminus S_{j-1} \subseteq(N_{j-1},\infty)

holds.

We proceed to let I⊆RI \subseteq\mathbb{R} be an arbitrary bounded interval, and we then let TT be a real value such that I⊆(−∞,T]I \subseteq(-\infty,T]. As established previously (recalling (49)), the sequence (Nj)j≥1(N_j)_{j\ge1} is strictly increasing, and we also recall that it consists of positive integers. So, since Nj→∞N_j \to\infty, we are permitted to choose an index J≥1J \ge1 such that NJ>TN_J > T. For each j>Jj > J, every member tt in Sj∖Sj−1S_j \setminus S_{j-1} is such that

t>Nj−1≥NJ>T,t > N_{j-1} \ge N_J > T,

and we thus find that

(Sj∖Sj−1)∩I=∅(61)(S_j \setminus S_{j-1}) \cap I = \varnothing \tag*{(61)}

since I⊆(−∞,T]I \subseteq(-\infty,T]. The recursion in (48) gives us that Sj−1⊆SjS_{j-1} \subseteq S_j, and thus, for j>Jj > J, we proceed to write

Sj∩I=(Sj−1∩I)∪((Sj∖Sj−1)∩I),(62)S_j \cap I = (S_{j-1} \cap I) \cup((S_j \setminus S_{j-1}) \cap I), \tag*{(62)}

so that a combined application of (60) and (61) yields

Sj∩I=Sj−1∩I.(63)S_j \cap I = S_{j-1} \cap I. \tag*{(63)}

A repeated application of the equality in (63) then gives us that

Sj∩I=SJ∩I(64)S_j \cap I = S_J \cap I \tag*{(64)}

for each j≥Jj \ge J. Since

Sj⊆SJfor j∈{1,2,…,J−1},(65)S_j \subseteq S_J \quad\text{for } j \in\{1,2,\ldots,J-1\}, \tag*{(65)}

we find, by appealing to the equality in (64) that

S∩I=⋃j≥1(Sj∩I)=SJ∩I.\begin{aligned} S \cap I &= \bigcup_{j\ge1}(S_j \cap I)\\ &= S_J \cap I. \end{aligned}

Also observe that SJ∩IS_J \cap I is finite, as a consequence of SJS_J being finite. This proves the first listed assertion above.

The second listed assertion follows immediately from the recursion in (49) in conjunction with the definition in (45).

We now proceed to establishing the third assertion listed above. In this direction, we begin by observing that Sj−1S_{j-1}, {Nj}\{\sqrt{N_j}\}, and {Njs:s∈Sj−1}\left\{\frac{N_j}{s}:s\in S_{j-1}\right\} are pairwise disjoint for an arbitrary element jj in N\mathbb{N}, since: For each s∈Sj−1s\in S_{j-1}, we have that s<Nj<Njss<\sqrt{N_j}<\frac{N_j}{s}, recalling (56) and (60). For a fixed and positive integer jj, we find that the mapping on Sj−1S_{j-1} such that s↦Njss\mapsto\frac{N_j}{s} is injective, and we thus find that the recursion shown in (49) yields the recurrence such that

∣Sj∣=2∣Sj−1∣+1.(66)|S_j|=2|S_{j-1}|+1. \tag*{(66)}

Since S0=∅S_0=\varnothing, this and the recurrence in (66) together give us that

∣Sj∣=2j−1(67)|S_j|=2^j-1 \tag*{(67)}

for each nonnegative integer jj. Since Sj−1⊆SjS_{j-1}\subseteq S_j (again recalling the recursion in (49)), this and the evaluation in (67) together give us that

∣Sj∖Sj−1∣=∣Sj∣−∣Sj−1∣=2j−1(68)|S_j\setminus S_{j-1}|=|S_j|-|S_{j-1}|=2^{j-1} \tag*{(68)}

for each positive integer jj. From the recursion in (49), a given element tt in Sj∖Sj−1S_j\setminus S_{j-1} (letting j≥1j\ge1 be fixed) is either equal to Nj\sqrt{N_j} or is equal to Njs\frac{N_j}{s} for some s∈Sj−1s\in S_{j-1}. In the latter case, the relations in (60) (which hold, as above, for s∈Sj−1s\in S_{j-1}) give us that t=Njs>Njt=\frac{N_j}{s}>\sqrt{N_j}, so, in either case, we see that t≥Njt\ge\sqrt{N_j}. Now, since t≥Nj>Mjt\ge\sqrt{N_j}>M_j (recalling (54)), and since the mapping on R≥2\mathbb{R}_{\ge2} such that q↦L(q)q\mapsto L(q) is nondecreasing (recalling (10)), the defining condition in (47) gives us that

1L(t)≤1L(Mj)≤2δ4j.(69)\frac{1}{L(t)}\le\frac{1}{L(M_j)}\le\frac{2\delta}{4^j}. \tag*{(69)}

From (67) and (68) together, we find that

∑t∈Sj∖Sj−11L(t)≤2j−12δ4j=δ2j.(70)\sum_{t\in S_j\setminus S_{j-1}} \frac{1}{L(t)} \le2^{j-1}\frac{2\delta}{4^j} = \frac{\delta}{2^j}. \tag*{(70)}

Since S=⋃j≥1SjS = \bigcup_{j\ge1} S_j, S0=∅S_0 = \varnothing, and Sj−1⊆SjS_{j-1} \subseteq S_j for each j≥1j \ge1, sets of the form Sj∖Sj−1S_j \setminus S_{j-1} are pairwise disjoint with union SS, an application of (70) gives us that

∑s∈S1L(s)=∑j=1∞∑t∈Sj∖Sj−11L(t)≤∑j=1∞δ2j=δ,\sum_{s\in S} \frac{1}{L(s)} = \sum_{j=1}^{\infty}\sum_{t\in S_j\setminus S_{j-1}} \frac{1}{L(t)} \le\sum_{j=1}^{\infty}\frac{\delta}{2^j} = \delta,

thus proving the third listed assertion as desired.

We proceed to prove the final listed assertion. In this direction, we begin by fixing a positive integer jj, and observing that (50) gives us that

Sj⊆(1,Nj).(71)S_j \subseteq(1,N_j). \tag*{(71)}

Consequently, the relation

S∩(1,Nj)=Sj(72)S \cap(1,N_j) = S_j \tag*{(72)}

holds. From the chain of sets indicated in (64) together with the inclusion in (58) together with the NN-sequence being nondecreasing, we find that

S∖Sj=⋃k=j+1∞(Sk∖Sk−1)⊆(Nj,∞).S \setminus S_j = \bigcup_{k=j+1}^{\infty}(S_k\setminus S_{k-1}) \subseteq(N_j,\infty).

Now, observe that the mapping on SjS_j such that t↦Njtt\mapsto\frac{N_j}{t} is a bijection, since, in view of the recursion in (48), the given mapping interchanges Sj−1S_{j-1} and {Njs:s∈Sj−1}\left\{\frac{N_j}{s}:s\in S_{j-1}\right\} and fixes Nj\sqrt{N_j}. Now, let

x∈[1,Nj]∩Q(73)x\in[1,N_j]\cap\mathbb{Q} \tag*{(73)}

be fixed. Since xx and Njx\frac{N_j}{x} are rational and since each element in SjS_j is irrational, we find that neither xx nor Njx\frac{N_j}{x} is in SjS_j. Now, since the given bijection maps SjS_j onto itself, we see that this same bijection maps Sj∩(1,x)S_j\cap(1,x) onto Sj∩(Njx,Nj)S_j\cap\left(\frac{N_j}{x},N_j\right), and we thus obtain the equality

∣Sj∩(1,x)∣=∣Sj∩(Njx,Nj)∣.(74)\left|S_j\cap(1,x)\right| = \left|S_j\cap\left(\frac{N_j}{x},N_j\right)\right|. \tag*{(74)}

Recalling the inclusion in (71), since Njx∉Sj\frac{N_j}{x} \notin S_j, we find that Sj∩(1,Njx)S_j \cap(1,\frac{N_j}{x}) and Sj∩(Njx,Nj)S_j \cap(\frac{N_j}{x},N_j) form a partition of SjS_j. This partition gives us that

∣Sj∣=∣Sj∩(1,Njx)∣+∣Sj∩(Njx,Nj)∣.(75)|S_j|=\left|S_j\cap\left(1,\frac{N_j}{x}\right)\right|+\left|S_j\cap\left(\frac{N_j}{x},N_j\right)\right|. \tag*{(75)}

A combined application of (67), (74), and (75) then gives us that

∣Sj∩(1,x)∣+∣Sj∩(1,Njx)∣=∣Sj∣=2j−1.(76)\begin{aligned} \left|S_j\cap(1,x)\right|+\left|S_j\cap\left(1,\frac{N_j}{x}\right)\right|=|S_j| \\ &=2^j-1. \tag*{(76)} \end{aligned}

Recalling (73), we have that x≤Njx\leq N_j, with (1,x)⊆(1,Nj)(1,x)\subseteq(1,N_j), so that

S∩(1,x)=(S∩(1,Nj))∩(1,x)=Sj∩(1,x),(77)\begin{aligned} S\cap(1,x)=(S\cap(1,N_j))\cap(1,x) \\ &=S_j\cap(1,x), \tag*{(77)} \end{aligned}

where the last equality in (77) follows from (72). From (73), we find that 1≤Njx≤Nj1\leq\frac{N_j}{x}\leq N_j, i.e., so that (1,Njx)⊆(1,Nj)(1,\frac{N_j}{x})\subseteq(1,N_j). By analogy with (77), we have that

S∩(1,Njx)=(S∩(1,Nj))∩(1,Njx)=Sj∩(1,Njx),(78)\begin{aligned} S\cap\left(1,\frac{N_j}{x}\right)=(S\cap(1,N_j))\cap\left(1,\frac{N_j}{x}\right) \\ &=S_j\cap\left(1,\frac{N_j}{x}\right), \tag*{(78)} \end{aligned}

where we have again exploited (72). So, a combined application of (76), (77), and (78) yields

∣S∩(1,x)∣+∣S∩(1,Njx)∣=∣Sj∩(1,x)∣+∣Sj∩(1,Njx)∣=2j−1.(79)\begin{aligned} |S\cap(1,x)|+\left|S\cap\left(1,\frac{N_j}{x}\right)\right|=|S_j\cap(1,x)|+\left|S_j\cap\left(1,\frac{N_j}{x}\right)\right| \\ &=2^j-1. \tag*{(79)} \end{aligned}

So, in view of the parity of 2j−12^j-1, the definition of χ\chi shown in (42) and the equalities in (79) together give us that

χ(x)χ(Njx)=(−1)∣S∩(1,x)∣+∣S∩(1,Njx)∣=(−1)2j−1=−1.\begin{aligned} \chi(x)\chi\left(\frac{N_j}{x}\right)=(-1)^{|S\cap(1,x)|+|S\cap(1,\frac{N_j}{x})|} \\ &=(-1)^{2^j-1} \\ &=-1. \end{aligned}

Since the possible values for χ\chi are in {−1,1}\{-1,1\}, the preceding equalities give us that χ(x)=−χ(Njx)\chi(x)=-\chi\left(\frac{N_j}{x}\right), and this proves the final listed assertion. □

We are now in a position to prove our main result and to provide an affirmative solution to the Erdős–Sárközy problem given in Section 1.

Theorem 1. For each ε>0\varepsilon>0, there exists a partition {A1,A2}\{A_1,A_2\} of N\mathbb{N} such that

lim inf⁡N→∞∣P(A1,A2)∩{1,2,…,N}∣N<ε.\liminf_{N\to\infty}\frac{|\mathcal{P}(A_1,A_2)\cap\{1,2,\ldots,N\}|}{N}<\varepsilon.

Proof. It suffices to prove the desired result for ε∈(0,1)\varepsilon\in(0,1) (since, once such a result is established for ε∈(0,1)\varepsilon\in(0,1), it would immediately hold for larger values). So, let ε∈(0,1)\varepsilon\in(0,1) be fixed. Also, set θ=ε2\theta= \frac{\varepsilon}{2} and δ=ε4Kε\delta= \frac{\varepsilon}{4K_{\varepsilon}}. Since θ∈(0,1)\theta\in(0,1) and δ>0\delta> 0, Lemma 2 gives us a strictly increasing sequence (Nj:j∈N)(N_j : j \in\mathbb{N}) of positive integers and a set SS satisfying the desired conditions in Lemma 2, along with the associated function χ(x)=(−1)∣S∩(1,x]∣\chi(x) = (-1)^{|S \cap(1,x]|} for x∈Q≥1x \in\mathbb{Q}_{\geq1}. We then define two color classes so that A1={n∈N:χ(n)=1}\mathcal{A}_1 = \{n \in\mathbb{N} : \chi(n) = 1\} and A2={n∈N:χ(n)=−1}\mathcal{A}_2 = \{n \in\mathbb{N} : \chi(n) = -1\}. Since χ(n)∈{−1,1}\chi(n) \in\{-1,1\} for each positive integer nn, we find that A1\mathcal{A}_1 and A2\mathcal{A}_2 form a partition of N\mathbb{N}, defining a 2-coloring that we denote with C\mathcal{C}.

Now, let jj be a fixed and positive integer, and write NN in place of NjN_j. For any n∈P(A1,A2)n \in P(\mathcal{A}_1,\mathcal{A}_2) such that

θN<n≤N,(80)\theta N < n \leq N, \tag*{(80)}

there exists (recalling (6)) at least one factorization n=abn = ab such that a,b∈Na,b \in\mathbb{N} and a≤ba \leq b and

χ(a)=χ(b).(81)\chi(a) = \chi(b). \tag*{(81)}

We fix one such factorization n=abn = ab. This leads us to two cases covered below.

Case 1. Suppose that b≤Nb \leq\sqrt{N}. Then, by taking s=N∈Ss = \sqrt{N} \in S, as permitted by the second listed assertion in Lemma 2, we find that θs=θN≤θNb\theta s = \theta\sqrt{N} \leq\frac{\theta N}{b}. From (79), we find that θNb<nb=a≤b≤N=s\frac{\theta N}{b} < \frac{n}{b} = a \leq b \leq\sqrt{N} = s.

Case 2. Suppose that b>Nb > \sqrt{N}. Define

u=Nb∈Q.(82)u = \frac{N}{b} \in\mathbb{Q}. \tag*{(82)}

Since θN<n=ab≤N\theta N < n = ab \leq N and since b>Nb > \sqrt{N}, we find that

1≤a=nb≤Nb=u<N,(83)1 \leq a = \frac{n}{b} \leq\frac{N}{b} = u < \sqrt{N}, \tag*{(83)}

and

a=nb>θNb=θu.(84)a = \frac{n}{b} > \frac{\theta N}{b} = \theta u. \tag*{(84)}

From (82), we find that u∈[1,N]u \in[1,N], and this and (81) together give us that u∈[1,N]∩Qu \in[1,N] \cap\mathbb{Q}, recalling the condition in (43) associated with the reflection identity in (42) for the χ\chi-function. This same reflection identity, applied with u∈[1,N]∩Qu \in[1,N] \cap\mathbb{Q}, gives us that

χ(u)=−χ(Nu)=−χ(b),=−χ(a).\begin{aligned} \chi(u) &= -\chi\left(\frac{N}{u}\right) \\ &= -\chi(b), \\ &= -\chi(a). \end{aligned}

where we have exploited both (80) and (81). This gives us that

χ(a)≠χ(u).(85)\chi(a) \ne\chi(u). \tag*{(85)}

Now, since n=ab≤Nn=ab\le N and b>0b>0, we have that

a=nb≤Nb=u.(86)a=\frac{n}{b}\le\frac{N}{b}=u. \tag*{(86)}

Also, observe that (84) and (85) together give us that a<ua<u. Each member of SS is irrational, recalling (40), but aa is an integer and uu is rational. This leads us to the implications such that

S∩(a,u)=∅⟹S∩(1,a)=S∩(1,u)⟹χ(a)=χ(u),(87)\begin{aligned} S\cap(a,u)=\varnothing&\Longrightarrow S\cap(1,a)=S\cap(1,u)\\ &\Longrightarrow\chi(a)=\chi(u), \tag*{(87)} \end{aligned}

thus contradicting (84), noting that we have exploited (to obtain the final implication in (86)) the definition of χ\chi on display in (41). So, in view of the implications shown in (86), it cannot be the case that S∩(a,u)S\cap(a,u) is empty. So, we have shown that there exists an element s∈Ss\in S (noting that SS is nonempty by construction, with, for example, the value Nℓ\sqrt{N_\ell} being in SS for all ℓ≥1\ell\ge1) such that a<s<ua<s<u. For the given choice of ss, the inequality u<Nu<\sqrt{N} (recalling (82)) and the inequality a>θua>\theta u (recalling (83)) give us that s<u<Ns<u<\sqrt{N} and that θs<θu<a<s\theta s<\theta u<a<s.

So, in either of the above cases, we have that s≤Ns\le\sqrt{N} and that θs≤a≤s\theta s\le a\le s. Now, let m∈P(A1,A2)∩[1,N]m\in P(A_1,A_2)\cap[1,N]. So, in other words, the integer mm is a monochromatic product such that 1≤m≤N1\le m\le N. We proceed to consider two separate cases.

Case 1. Suppose that m≤θNm\le\theta N. Then it is immediate that m∈{k∈N:k≤θN}m\in\{k\in\mathbb{N}: k\le\theta N\}.

Case 2. Suppose that θN<m≤N\theta N<m\le N. From the preceding case analysis, we deduce that there exists a positive integer divisor a∣ma\mid m and an element s∈Ss\in S such that s≤Ns\le\sqrt{N} and θs≤a≤s\theta s\le a\le s.

We thus obtain the inclusion

P(A1,A2)∩[1,N]⊆{m∈N:m≤θN}∪⋃t∈St≤N{m∈N:m≤N, ∃d∈N (d∣m and θt≤d≤t)}.\begin{aligned} P(A_1,A_2)\cap[1,N] &\subseteq\{m\in\mathbb{N}:m\le\theta N\}\\ &\quad\cup\bigcup_{\substack{t\in S\\t\le\sqrt{N}}} \{m\in\mathbb{N}:m\le N,\ \exists d\in\mathbb{N}\ (d\mid m\text{ and }\theta t\le d\le t)\}. \end{aligned}

Since S⊂(1,∞)S\subset(1,\infty) (recalling (40)), we find that indexing sets associated with the latter union above consist of elements tt in S∩[1,N]S\cap[1,\sqrt{N}]. As established in Lemma 2, every bounded interval contains only finitely many elements of SS, and hence the finitude of S∩[1,N]S\cap[1,\sqrt{N}]. From this finitude, the above inclusion, and the definition in (11), we find that

∣P(A1,A2)∩[1,N]∣≤⌊θN⌋+∑t∈St≤NHθ(N,t).(88)|P(\mathcal{A}_1,\mathcal{A}_2)\cap[1,N]|\le\lfloor\theta N\rfloor+\sum_{\substack{t\in S\\t\le\sqrt{N}}}H_\theta(N,t). \tag*{(88)}

Now, for t∈St\in S such that t≤Nt\le\sqrt{N}, since a given element in SS is strictly greater than max⁡{2,θ−1}\max\{2,\theta^{-1}\} according to (40), we find that t>max⁡{2,θ−1}t>\max\{2,\theta^{-1}\}. Since t≤Nt\le\sqrt{N}, this yields N≥t2N\ge t^2. So, the required conditions of Lemma 1 hold for q=tq=t, writing

Hθ(N,t)≤KθNL(t).(89)H_\theta(N,t)\le K_\theta\frac{N}{L(t)}. \tag*{(89)}

From (87) and (88), we find that

∣P(A1,A2)∩[1,N]∣N≤⌊θN⌋N+Kθ∑t∈St≤N1L(t)≤θ+Kθ∑t∈St≤N1L(t).(90)\begin{aligned} \frac{|P(\mathcal{A}_1,\mathcal{A}_2)\cap[1,N]|}{N}\le\frac{\lfloor\theta N\rfloor}{N}+K_\theta\sum_{\substack{t\in S\\t\le\sqrt{N}}}\frac{1}{L(t)} \\ &\le\theta+K_\theta\sum_{\substack{t\in S\\t\le\sqrt{N}}}\frac{1}{L(t)}. \tag*{(90)} \end{aligned}

Since L(t)>0L(t)>0 for each member tt in SS, this and the third listed assertion in Lemma 2 give us that

∑t∈St≤N1L(t)≤∑t∈S1L(t)≤δ.(91)\begin{aligned} \sum_{\substack{t\in S\\t\le\sqrt{N}}}\frac{1}{L(t)}\le\sum_{t\in S}\frac{1}{L(t)} \\ &\le\delta. \tag*{(91)} \end{aligned}

Now, recall that j≥1j\ge1 was arbitrary and that N=NjN=N_j. Also recall that θ=ε2\theta=\frac{\varepsilon}{2} and that δ=ε4Kθ\delta=\frac{\varepsilon}{4K_\theta}. A combined application of the relations among (89) and (90) gives us that

rC(Nj)=∣P(A1,A2)∩[1,Nj]∣Nj≤θ+Kθδ=ε2+ε4=3ε4<ε.\begin{aligned} r_C(N_j)=\frac{|P(\mathcal{A}_1,\mathcal{A}_2)\cap[1,N_j]|}{N_j} \\ &\le\theta+K_\theta\delta\\ &=\frac{\varepsilon}{2}+\frac{\varepsilon}{4}=\frac{3\varepsilon}{4}<\varepsilon. \end{aligned}

Since (Nj)j≥1(N_j)_{j\ge1} is a strictly increasing sequence of positive integers, we find that Nj→∞N_j\to\infty, and we thus find that

dC=lim inf⁡M→∞rC(M)≤lim inf⁡j→∞rC(Nj)≤3ε4<ε,d_C=\liminf_{M\to\infty}r_C(M)\le\liminf_{j\to\infty}r_C(N_j)\le\frac{3\varepsilon}{4}<\varepsilon,

as desired. □

Example 2. For each ε>0\varepsilon>0, our construction, as above, gives us at least one coloring CC of N\mathbb{N} such that dC<εd_C<\varepsilon. There are many such 2-colorings possible according to our construction, and this depends on how values of the form

MjM_j, as in (45), are chosen. Adopting the convention that 1 is colored with red, our construction necessarily assigns colorings so that

1,2,…,M1⏟red,M1+1,M1+2,…,M12+1⏟blue.\underbrace{1,2,\ldots,M_1}_{\text{red}},\quad\underbrace{M_1+1,M_1+2,\ldots,M_1^2+1}_{\text{blue}}.

For example, let ε=110\varepsilon=\frac{1}{10}. In this case, the associated parameters are θ=120\theta=\frac{1}{20}, Kθ=1060+48log⁡20K_\theta=1060+48\log20, and δ=140Kθ\delta=\frac{1}{40K_\theta}. By then writing T=84 800+3840log⁡20T=84\,800+3840\log20, we define

Mmin⁡=min⁡{m∈N:m>20, ∑p≤m1p≥T}.M_{\min}=\min\left\{m\in\mathbb{N}:m>20,\ \sum_{p\le m}\frac{1}{p}\ge T\right\}.

The admissible choices for M1M_1 are thus Mmin⁡M_{\min}, Mmin⁡+1M_{\min}+1, etc. Using classical bounds for sums of reciprocals of consecutive primes due to Rosser and Schoenfeld [12 Theorem 5, Eq. (3.17)–(3.18)], it can be shown that

exp⁡(exp⁡(96 303.3504))<Mmin⁡≤exp⁡(exp⁡(96 303.3505)).\exp(\exp(96\,303.3504))<M_{\min}\le\exp(\exp(96\,303.3505)).

So, in any case, the first

exp⁡(exp⁡(96 303.3504))>101041 823\exp(\exp(96\,303.3504))>10^{10^{41\,823}}

integers would necessarily be colored red for the ε=110\varepsilon=\frac{1}{10} case.

Conclusion

Our solution to the Erdős–Sárközy product-density problem indicated above and the techniques introduced and employed above raise questions in regard to further areas of study related to the given problem and to our techniques. For example, instead of coloring each positive integer (red or blue) and then considering lower limits as in (2), we could instead color each prime (red or blue) and then enumerate integers up to a given integer NN that admit a monochromatic prime factorization. This is decidedly inequivalent to the enumeration suggested in (1), and we encourage a full exploration of monochromatic prime factorizations in relation to the work of Erdős and Sárközy [5, 6].

For a given value α∈[12,1]\alpha\in\left[\frac{1}{2},1\right], how can we characterize 2-colorings C\mathcal{C} of N\mathbb{N} such that the limit lim⁡N→∞rC(N)\lim_{N\to\infty}r_{\mathcal{C}}(N) exists and, moreover, is equal to α\alpha (being consistent with the definition of rC(N)r_{\mathcal{C}}(N) in (1))?

How can we characterize 2-colorings C\mathcal{C} of N\mathbb{N} such that lim⁡N→∞rC(N)\lim_{N\to\infty}r_{\mathcal{C}}(N) does not exist?

AI disclosure. The following AI disclosure is based on AI disclosures used and written by the author previously (with numerous parts taken verbatim from previous AI disclosures used and written by the author).

Our solution above to Guy’s problem is, as indicated above, based on our extensive interactions with GPT-6 Astra Pro, and this is described in more detail below. All AI-generated suggestions were substantially revised, corrected, and independently verified by the author, who assumes full responsibility for the mathematical content. The author’s use of AI is fully in accordance with editorial standards on the responsible, ethical, and transparent use of AI.

On 2026-10-18, the author inputted a prompt into GPT-6 Astra Pro containing an equivalent version of the problem from Guy’s text solved above (with an explicit attribution to Guy’s text on unsolved problems in number theory), concluding with an explicit request that GPT-6 Astra Pro solve the given problem. After 13m 53s of thinking, GPT-6 Astra Pro provided a response beginning with

“I obtain a negative answer to the exact formulation you gave: no such absolute constant c>0c > 0 exists. The construction below produces, for every ε>0\varepsilon> 0, one fixed partition and an infinite sequence of cutoffs at which the proportion of distinct monochromatic products is at most ε\varepsilon.”

After extensive clarifications, corrections, revisions, suggestions, verifications, calculations, etc., through extensive discussions between the author and GPT-6 Astra Pro, and after extensive and careful reviews of such discussions on the part of the author, this provided a basis for the above solution, written by the author, to Guy’s problem.

For example, it was through the author’s enquiries, investigations, revisions, reviews, reflections, considerations, etc., that the “non-probabilistic” version of Markov’s inequality given above was employed to prove Lemma 1. Similar commentary applies to the case analysis in the proof of Lemma 1, the use of the Alzer–Berg inequality in (8), the expansion of ∑n≤M(F(n)−L)2\sum_{n \le M}(F(n)-L)^2 involved in the proof of Lemma 1, the equivalent formulations of the Erdős–Sárközy problem discussed in § 1, the evaluation in (5), etc.

Department of Mathematics and Statistics, Dalhousie University, Halifax, NS B3H 4R2, Canada

Email address: [email protected]

References

  1. [2]Mathias Beiglböck, Vitaly Bergelson, Neil Hindman, and Dona Strauss. Some new results in multiplicative and additive Ramsey theory. Trans. Amer. Math. Soc., 360(2):819–847, 2008.DOI
  2. [3]Vitaly Bergelson. Multiplicatively large sets and ergodic Ramsey theory. volume 148, pages 23–40. 2005. Probability in mathematics.DOI
  3. [4]Péter Csikvári, Katalin Gyarmati, and András Sárközy. Density and Ramsey type results on algebraic equations with restricted solution sets. Combinatorica, 32(4):425–449, 2012.DOI
  4. [5]P. Erdős and A. Sárközy. On a conjecture of Roth and some related problems. II. In Number theory (Banff, AB, 1988), pages 125–138. de Gruyter, Berlin, 1990.
  5. [6]P. Erdős and A. Sárközy. Some solved and unsolved problems in combinatorial number theory. II. Colloq. Math., 65(2):201–211, 1993.DOI
  6. [7]Ben Green and Tom Sanders. Monochromatic sums and products. Discrete Anal., pages Paper No. 5, 48, 2016.DOI
  7. [8]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.
  8. [9]Neil Hindman. Partitions and sums and products of integers. Trans. Amer. Math. Soc., 247:227–245, 1979.DOI
  9. [10]Joel Moreira. Monochromatic sums and products in N. Ann. of Math. (2), 185(3):1069–1090, 2017.arxiv.org/abs/1605.01469
  10. [11]Earl D. Rainville. Special functions. The Macmillan Company, New York, 1960.
  11. [12]J. Barkley Rosser and Lowell Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois J. Math., 6:64–94, 1962.

Paper details

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

views · 0

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