# Comptes Rendus
Mathématique

Jared Duker Lichtman

Translated sums of primitive sets

Volume 360 (2022), p. 409-414

Published online: 26 April 2022

https://doi.org/10.5802/crmath.285

<figure><img src="image_1.png" /></figure>

This article is licensed under the
CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.
http://creativecommons.org/licenses/by/4.0/

<figure><img src="image_2.png" /></figure>
Combinatorics, Number theory / Combinatoire, Théorie des nombres

# Translated sums of primitive sets

Jared Duker Lichtman*, a

<sup>a</sup> Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK

E-mail: jared.d.lichtman@gmail.com

**Abstract.** The Erdős primitive set conjecture states that the sum $f(A) = \sum_{a \in A} \frac{1}{a \log a}$, ranging over any primitive set A of positive integers, is maximized by the set of prime numbers. Recently Laib, Derbal, and Mechik proved that the translated Erdős conjecture for the sum $f(A, h) = \sum_{a \in A} \frac{1}{a[\log a + h]}$ is false starting at $h = 81$, by comparison with semiprimes. In this note we prove that such falsehood occurs already at $h = 1.04\dots$, and show this translate is best possible for semiprimes. We also obtain results for translated sums of k-almost primes with larger k.

**Mathematical subject classification** (2010). 11N25, 11Y60, 11A05, 11M32.

**Funding.** The author is supported by a Clarendon Scholarship at the University of Oxford.

Manuscript received 30th August 2021, revised 14th October 2021, accepted 19th October 2021.

## 1. Introduction

A set $A \subset \mathbb{Z}_{>1}$ of positive integers is called *primitive* if no member divides another (we trivially exclude the singleton $\{1\}$). An important family of examples is the set $\mathbb{N}_k$ of *k-almost primes*, that is, numbers with exactly *k* prime factors counted with multiplicity. For example, $k=1,2$ correspond to the sets of primes and semiprimes, respectively.

In 1935 Erdős [3] proved that $f(A) = \sum_{a \in A} \frac{1}{a \log a}$ converges uniformly for any primitive A. In 1988 he further conjectured that the maximum of $f(A)$ is attained by the primes $A = \mathbb{N}_1$. One may directly compute $f(\mathbb{N}_1) = 1.636\dots$, whereas the best known bound is $f(A) < e^\gamma = 1.781\dots$ for any primitive A [8]. As a special case, Zhang [9] proved that the primes maximize $f(\mathbb{N}_k)$, that is, $f(\mathbb{N}_1) > f(\mathbb{N}_k)$ for all $k > 1$.

One may pose a translated analogue of the Erdős conjecture, namely, the maximum of $f(A, h) = \sum_{a \in A} \frac{1}{a(\log a + h)}$ is attained by the primes $A = \mathbb{N}_1$. Recently Laib, Derbal, and Mechik [5] proved that this translated conjecture is false, by showing $f(\mathbb{N}_1, h) < f(\mathbb{N}_2, h)$ for all $h \ge 81$. Their proof method is direct, by studying partial sum truncations of $f(A, h)$. (Laib [4] very recently announced a bound $h \ge 60$, as a refinement of the same method.)

By different methods, we extend the range of such falsehood down to $h > 1.04\dots$, and show this translate is best possible for semiprimes.

<footnote>* Corresponding author.</footnote>
**Theorem 1.** Let $P(s) = \sum_p p^{-s}$ denote the prime zeta function. We have $f(\mathbb{N}_1, h) < f(\mathbb{N}_2, h)$ if and only if $h > h_2$, where $t = h_2 = 1.04\dots$ is the unique real solution to

$$ \int_{1}^{\infty} \left[ P(s) - \frac{1}{2} (P(s)^2 + P(2s)) \right] e^{(1-s)t} ds = 0, $$

Moreover $f(\mathbb{N}_1, h) < f(\mathbb{N}_k, h)$ for all $k$ sufficiently large, if and only if $h > 0.277\dots$.

This suggests that the Erdős conjecture, if true, is only barely so. Moreover, for the same value $h = h_2 = 1.04\dots$ we show the primes minimize $f(\mathbb{N}_k, h)$, which may be viewed as the inverse analogue of Zhang's maximization result.

**Theorem 2.** For $h_2 = 1.04\dots$, we have $f(\mathbb{N}_1, h_2) < f(\mathbb{N}_k, h_2)$ for all $k > 1$.

## 2. Proof of Theorem 1

We introduce the zeta function for $k$-almost primes $P_k(s) = \sum_{n \in \mathbb{N}_k} n^{-s}$, whose relevance to us arises from the identity,

$$ \begin{aligned} f(\mathbb{N}_k, h) &= \sum_{n \in \mathbb{N}_k} \frac{1}{n(\log n + h)} = \sum_{n \in \mathbb{N}_k} \frac{1}{n \log(ne^h)} \\ &= \sum_{n \in \mathbb{N}_k} e^h \int_1^{\infty} (ne^h)^{-s} ds = \int_1^{\infty} P_k(s) e^{(1-s)h} ds. \end{aligned} \quad (1) $$

Here the interchange of sum and integral holds by Tonelli's theorem, since $f(\mathbb{N}_k, h) \le f(\mathbb{N}_k)$ converges uniformly after Erdős. The significance of the identity (1) was first observed when $k = 1$, $h = 0$ by H. Cohen [2, p. 6], who rapidly computed $f(\mathbb{N}_1) = 1.636616\dots$ to 50 digits accuracy. By comparison, the direct approach by partial sums $\sum_{p \le x} 1/(p \log p)$ converge too slowly, i.e. $O(1/\log x)$. Similarly for $k > 1$, we shall see (1) leads to sharper results.

Note one has $P_1(s) = P(s)$ and $P_2(s) = \frac{1}{2}P(s)^2 + \frac{1}{2}P(2s)$, as well as

$$ P_3(s) = \frac{1}{6}P(s)^3 + \frac{1}{2}P(s)P(2s) + \frac{1}{3}P(3s), $$

$$ P_4(s) = \frac{1}{24}P(s)^4 + \frac{1}{4}P(s)^2P(2s) + \frac{1}{8}P(2s)^2 + \frac{1}{3}P(s)P(3s) + \frac{1}{4}P(4s). $$

In general for $k \ge 1$, [6, Proposition 3.1] gives an explicit formula for $P_k$ in terms of $P$,

$$ P_k(s) = \sum_{n_1+2n_2+\dots=k} \prod_{j \ge 1} \frac{1}{n_j!} \left( \frac{P(js)}{j} \right)^{n_j}. \quad (2) $$

Here the above sum ranges over all partitions of $k$. Also see [7, Proposition 2.1].

In practice, we may rapidly compute $P_k$ (and $P'_k$) using recursion relations.

**Lemma 3.** For $k \ge 1$ let $P_k(s) = \sum_{\Omega(n)=k} n^{-s}$ and $P_1(s) = P(s) = \sum_p p^{-s}$. We have

$$ P_k(s) = \frac{1}{k} \sum_{j=1}^{k} P_{k-j}(s)P(js) \quad \text{and} \quad P'_k(s) = \sum_{j=1}^{k} P_{k-j}(s)P'(js). \quad (3) $$

**Proof.** The recursion (3) for $P_k$ is given in [6, Proposition 3.1], and is equivalent to (2).

The recursion (3) for $P'_k$ is obtained by differentiating (2),

$$ \begin{aligned} P'_{k}(s) &= \sum_{n_1+2n_2+\cdots=k} \sum_{i \le k} P'(is) \frac{(P(is)/i)^{n_i-1}}{(n_i-1)!} \prod_{j \ne i} \frac{1}{n_j!} (P(js)/j)^{n_j} \\ &= \sum_{i \le k} P'(is) \sum_{n_1+2n_2+\cdots=k-i} \prod_{j \ge 1} \frac{1}{n_j!} (P(js)/j)^{n_j} = \sum_{i \le k} P'(is) P_{k-i}(s). \end{aligned} $$

□
As observed empirically in [1], the Dirichlet series $P_2(s) - P(s) = \frac{1}{2}[P(s)^2 + P(2s)] - P(s)$ has a unique root at $s = \sigma = 1.1403...$, through which it passes from positive to negative. We prove this more generally for $k \le 20$.

**Lemma 4.** For $2 \le k \le 20$, the Dirichlet series $P_k(s) - P(s)$ has a unique root at $s = \sigma_k > 1$, through which it passes from positive to negative.

**Proof.** For each $k \ge 1$, $P_k(s)$ is monotonically decreasing in $s > 1$. As such there is a unique $s_k > 1$ for which $P(s)$ passes through $(k!)^{1/(k-1)}$ from above. Using the main term in (2), $P_k(s) > P(s)^k/k!$ which is larger than $P(s)$ iff $P(s)^{k-1} > k!$ iff $s < s_k$ by definition. That is,

$$P_k(s) > P(s) > 0 \quad \text{for } s \in (1, s_k). \qquad (4)$$

Also there is a unique $s'_k > 1$ for which $P_{k-1}(s)$ passes through 1 from above. Using the first term in the recursion (3), $-P'_k(s) > -P'(s)P_{k-1}(s)$ which is larger than $-P'(s) > 0$ iff $P_{k-1}(s) > 1$ iff $s < s'_k$ by definition. That is,

$$P'_k(s) < P'(s) < 0 \quad \text{for } s \in (1, s'_k). \qquad (5)$$

For $c < 2^k$, $P_k(s)c^s$ is monotonically decreasing in $s > 1$, and so is $P_k(s)/(2^{-s} + 3^{-s}) = \{1/[P_k(s)2^s] + 1/[P_k(s)3^s]\}^{-1}$. Thus there is a unique $t_k > 1$ for which $P_k(s)/(2^{-s} + 3^{-s})$ passes through 1 from above. Now by definition $P(s)/(2^{-s} + 3^{-s}) > 1 = P_k(t_k)/(2^{-t_k} + 3^{-t_k})$, which is larger than $P_k(s)/(2^{-s} + 3^{-s})$ iff $s > t_k$ by monotonicity. That is,

$$0 < P_k(s) < P(s) \quad \text{for } s \in (t_k, \infty). \qquad (6)$$

In summary $P_k - P$ has at most one root in $(1, s'_k)$, and no roots in $(1, s_k) \cup (t_k, \infty)$. We directly compute that $s_k < t_k < s'_k$ for $2 \le k \le 20$, and so $P_k(s) - P(s)$ has a unique root $\sigma_k \in (s_k, t_k)$ as claimed. $\square$

We deduce the following corollary, which gives (the first part of) Theorem 1 when $k = 2$.

**Corollary 5.** For $2 \le k \le 20$, $f(\mathbb{N}_k, h) - f(\mathbb{N}_1, h)$ has a unique root at $h_k > 0$, through which it passes from negative to positive.

**Proof.** For $h \ge 0$, recall $f(\mathbb{N}_k, h) = \int_1^\infty P_k(s)e^{(1-s)h} \, ds$ by (1). Now by Lemma 4, $P_k(s) - P(s)$ passes from positive to negative at $s = \sigma_k > 1$. Thus

$$ \begin{aligned} [f(\mathbb{N}_k, h) - f(\mathbb{N}_1, h)] e^{(\sigma_k - 1)h} &= \int_1^\infty [P_k(s) - P(s)] e^{(\sigma_k - s)h} \, ds \\ &= \int_1^{\sigma_k} [P_k(s) - P(s)] e^{(\sigma_k - s)h} \, ds - \int_{\sigma_k}^\infty [P(s) - P_k(s)] e^{(\sigma_k - s)h} \, ds \end{aligned} $$

is difference of two integrals with positive integrands, which are monotonically increasing and decreasing in $h \ge 0$, respectively. Hence the difference is monotonically increasing in $h \ge 0$. And $f(\mathbb{N}_k, 0) - f(\mathbb{N}_1, 0) < 0$ by Zhang [9], so the result follows. $\square$

For the second part of Theorem 1, note for any fixed $h \ge 0$ we have $\log n + h \sim \log n$ for $n \in \mathbb{N}_k$ as $k \to \infty$, since $n \ge 2^k$. Thus $f(\mathbb{N}_k, h) \sim f(\mathbb{N}_k, 0)$ as $k \to \infty$. Hence by [6, Theorem 2.2],

$$\lim_{k \to \infty} f(\mathbb{N}_k, h) = \lim_{k \to \infty} f(\mathbb{N}_k) = 1.$$

Note 1 – $f(\mathbb{N}_1, h)$ passes from negative to positive at a unique root $h_\infty = 0.277...$. So for each $h > h_\infty$, we have $f(\mathbb{N}_k, h) - f(\mathbb{N}_1, h) > 0$ for $k$ sufficiently large (and similarly for the converse). This completes the proof of Theorem 1.
<table><thead><tr><th>k</th><th>s<sub>k</sub></th><th>t<sub>k</sub></th><th>s'<sub>k</sub></th><th>σ<sub>k</sub></th><th>h<sub>k</sub></th></tr></thead><tbody><tr><td>2</td><td>1.11313</td><td>1.40678</td><td>1.39943</td><td>1.14037</td><td>1.04466</td></tr><tr><td>3</td><td>1.06861</td><td>1.23367</td><td>1.25922</td><td>1.09224</td><td>0.98213</td></tr><tr><td>4</td><td>1.04306</td><td>1.15231</td><td>1.17696</td><td>1.06206</td><td>0.93018</td></tr><tr><td>5</td><td>1.02761</td><td>1.104</td><td>1.12386</td><td>1.04231</td><td>0.89038</td></tr><tr><td>6</td><td>1.01795</td><td>1.07259</td><td>1.08784</td><td>1.02907</td><td>0.86146</td></tr><tr><td>7</td><td>1.01179</td><td>1.05125</td><td>1.06272</td><td>1.02007</td><td>0.84126</td></tr><tr><td>8</td><td>1.00779</td><td>1.0364</td><td>1.04493</td><td>1.0139</td><td>0.8276</td></tr><tr><td>9</td><td>1.00518</td><td>1.02594</td><td>1.03223</td><td>1.00964</td><td>0.8186</td></tr><tr><td>10</td><td>1.00346</td><td>1.0185</td><td>1.02312</td><td>1.0067</td><td>0.8128</td></tr><tr><td>11</td><td>1.00231</td><td>1.0132</td><td>1.01658</td><td>1.00466</td><td>0.80915</td></tr><tr><td>12</td><td>1.00155</td><td>1.00942</td><td>1.01187</td><td>1.00325</td><td>0.80689</td></tr><tr><td>13</td><td>1.00105</td><td>1.00672</td><td>1.00849</td><td>1.00226</td><td>0.80551</td></tr><tr><td>14</td><td>1.0007</td><td>1.00479</td><td>1.00607</td><td>1.00158</td><td>0.8047</td></tr><tr><td>15</td><td>1.00048</td><td>1.00341</td><td>1.00433</td><td>1.0011</td><td>0.8042</td></tr><tr><td>16</td><td>1.00032</td><td>1.00243</td><td>1.00309</td><td>1.00077</td><td>0.80391</td></tr><tr><td>17</td><td>1.00022</td><td>1.00173</td><td>1.0022</td><td>1.00053</td><td>0.80374</td></tr><tr><td>18</td><td>1.00015</td><td>1.00123</td><td>1.00157</td><td>1.00037</td><td>0.80365</td></tr><tr><td>19</td><td>1.0001</td><td>1.00087</td><td>1.00112</td><td>1.00026</td><td>0.80359</td></tr><tr><td>20</td><td>1.00007</td><td>1.00062</td><td>1.00079</td><td>1.00018</td><td>0.80356</td></tr></tbody></table>

## 2.1. Computations

For $k \le 20$, we compute the unique roots $\sigma_k$ and $h_k$ of $P_k(s) - P(s)$ and $f(\mathbb{N}_k, h) - f(\mathbb{N}_1, h)$, respectively, as well as verify that the auxiliary parameters (as defined in Lemma 4) satisfy $s_k < \sigma_k < t_k < s'_k$. We similarly compute the root of $1 - f(\mathbb{N}_1, h)$ as $h_\infty = 0.277 \cdots$.

In our computations, we express $P_k$ in terms of $P$ using the recursion in (3). In turn by Möbius inversion $P(s) = \sum_{m \ge 1} (\mu(m)/m) \log \zeta(ms)$, so $P$ is obtained via well-known rapid computation of $\zeta$. Finally, we compute $f(\mathbb{N}_k, h)$ from its integral form (1). The data are displayed in the table below, obtained using Mathematica (for technical convenience, we first compute $y_k = \log h_k)^1$.

We believe a unique of root $h_k$ exists as in Corollary 5 for all $k > 20$ as well. This would enable a strengthening of Theorem 2 to $f(\mathbb{N}_k, h) > f(\mathbb{N}_1, h)$ for all values of $k > 1$, $h \ge h_2$ (so far we only establish this for $\{1 < k \le 20, h \ge h_2\}$ or $\{k > 1, h = h_2\}$). Uniqueness of $h_k$ would follow if $\sigma_k$ is unique, as in Lemma 4, for all $k$. In turn it would suffice to show $t_k < s'_k$ for all $k$ (note $s_k < t_k$ holds automatically by (4), (6)), though it is not clear how to establish such an inequality in general.

Moreover, it appears both $h_k$ and $\sigma_k$ are monotonically decreasing in $k$. This may be related to some empirical trends for $f(\mathbb{N}_k)$, found in a recent disproof of a conjecture of Banks–Martin, see [1, 6].

<footnote n="1">¹P[k_Integer,s_]= If[k==1,PrimeZetaP[s],
Expand[(Sum[P[1,j*s]*P[k-j,s],j,1,k-1]+P[1,k*s])/k]]
FindRoot[P[1, s] == (k!)^1/(k-1)), s, 1 + 1/k^3]
FindRoot[P[k, t]/(2^(-t) + 3^(-t)) == 1, t, 1 + 1/k^3]
FindRoot[P[k - 1, s1] == 1, s1, 1 + 1/k^3]
FindRoot[P[k, sigma] == P[1, sigma], sigma, 1 + 1/k^3]]
FindRoot[NIntegrate[(P[1, s] - P[k, s])/y^s, s, 1, Infinity, WorkingPrecision->30,
AccuracyGoal->13, PrecisionGoal->13], y, 1 + 1/k^3]</footnote>
### 3. Proof of Theorem 2

**Proof.** We have already verified the claim directly for $k \le 20$, since in this case $h_k \le h_2 = 1.04...$.

For $k > 20$, the proof strategy is similar to that of [6, Theorem 5.5]. That is, the integral $f(\mathbb{N}_k, h) = \int_1^\infty P_k(s)e^{(1-s)h} ds$ has its mass concentrated near 1 as $k \to \infty$, so it suffices to truncate the integration to $[1, 1.01]$ say, as a lower bound. Thus by (1),

$$f(\mathbb{N}_k, h_2) = \int_1^\infty P_k(s) e^{(1-s)h_2} ds > e^{-.01h_2} \int_1^{1.01} P_k(s) ds. \quad (7)$$

Next, we may lower bound $P_k(s)$ by $P(s)^k/k!$, which constitutes the first of the terms in the identity (2), one per partition of $k$. Note the terms of partitions built from small parts contribute the most mass. So by also including the terms for the partitions $k = 1, (k-j)+j$ and $k = 1, (k-j-2)+2+j$ for $j \le 6$, we shall obtain a sufficiently tight lower bound to deduce the result. Indeed, we have

$$\int_1^{1.01} P_k(s) ds > \frac{1}{k!} \int_1^{1.01} P(s)^k ds + \sum_{j=2}^6 \frac{\int_1^{1.01} P(s)^{k-j} P(js) ds}{j(k-j)!} + \frac{\int_1^{1.01} P(s)^{k-4} P(2s)^2 ds}{2!2^2(k-4)!} + \sum_{j=3}^6 \frac{\int_1^{1.01} P(s)^{k-j-2} P(2s) P(js) ds}{2j(k-j-2)!} \quad (8)$$

From [6, (5.10)], we have

$$0 < P(s) - \log\left(\frac{\alpha}{s-1}\right) < 1.4(s-1), \quad \text{for } s \in [1, 2], \quad (9)$$

where $\alpha = \exp(-\sum_{m \ge 2} P(m)/m) = .7292...$. Thus for every $k \ge 1$, since $\log(\alpha/0.01) > 4$,

$$\int_1^{1.01} P(s)^k ds > \int_0^{0.01} \log\left(\frac{\alpha}{s}\right)^k ds = \alpha \int_{\log(\alpha/0.01)}^{\infty} u^k e^{-u} du > \alpha \Gamma(k+1, 4) > .729 k!, \quad (10)$$

where $\Gamma(k+1, 4)$ the incomplete Gamma function, and noting $\Gamma(k+1, 4)/k!$ is monotonically increasing in $k$. Also note

$$\int_0^1 s \log\left(\frac{\alpha}{s}\right)^k ds = \alpha^2 \int_0^\infty u^k e^{-2u} du = \frac{\alpha^2}{2^{k+1}} k!$$

Using the first order Taylor approximation $P(js) > P(j) + P'(j)(s-1)$ for $j \ge 2$,

$$\int_1^{1.01} P(s)^{k-j} P(js) ds > P(j) \int_0^{0.01} \log\left(\frac{\alpha}{s}\right)^{k-j} ds + P'(j) \int_0^1 s \log\left(\frac{\alpha}{s}\right)^{k-j} ds \\ > .729 (k-j)! \left(P(j) + \frac{\alpha P'(j)}{2^{k-j}}\right)$$

by (10). Similarly,

$$\int_1^{1.01} P(s)^{k-j-2} P(2s) P(js) ds \\ > P(2)P(j) \int_0^{0.01} \log\left(\frac{\alpha}{s}\right)^{k-j-2} ds + \left[P'(2)P(j) + P(2)P'(j)\right] \int_0^1 s \log\left(\frac{\alpha}{s}\right)^{k-j-2} ds \\ > .729 (k-j-2)! \left(P(2)P(j) + \frac{\alpha}{2^{k-j-1}} \left[P'(2)P(j) + P(2)P'(j)\right]\right).$$

Hence plugging back into (8),

$$f(\mathbb{N}_k, h_2) e^{.01h_2} > \int_1^{1.01} P(s)^k ds > \ell_k,$$
for the explicit lower bound

$$ \ell_k := .729 \left[ 1 + \sum_{j=2}^{6} \frac{P(j) + \alpha P'(j) / 2^{k-j}}{j} + \frac{1}{8} \left( P(2)^2 + \frac{\alpha P(2) P'(2)}{2^{k-4}} \right) \right. \\ \left. + \sum_{j=3}^{6} \frac{1}{2j} \left( P(2)P(j) + \frac{\alpha}{2^{k-j-1}} \left[ P'(2)P(j) + P(2)P'(j) \right] \right) \right] $$

Note $\ell_k$ is clearly increasing in $k$ (recall $P'(s) < 0$). Hence for $k > 20$ we have

$$ f(\mathbb{N}_k, h_2) > e^{-0.01h_2} \ell_k > e^{-0.01h_2} \ell_{20} > .98 > 0.91 > f(\mathbb{N}_1, h_2). \quad (11) $$

Here we compute $\ell_{20} = 0.99069 \dots$ and $f(\mathbb{N}_1, h_2) = 0.908599 \dots$. This completes the proof of Theorem 2. $\square$

## Acknowledgments

The author thanks Paul Kinlaw and Carl Pomerance for helpful discussions.

## References

[1] W. D. Banks, G. Martin, "Optimal primitive sets with restricted primes", *Integers* **13** (2013), article no. A69 (10 pages).

[2] H. Cohen, "High precision computation of Hardy-Littlewood constants", https://www.math.u-bordeaux.fr/~hecohen/.

[3] P. Erdős, "Note on sequences of integers no one of which is divisible by any other", *J. Lond. Math. Soc.* **10** (1935), p. 126-128.

[4] I. Laib, "Note on translated sum on primitive sequences", *Notes Number Theory Discrete Math.* **27** (2021), no. 3, p. 39-43.

[5] I. Laib, A. Derbal, R. Mechik, "Somme translatée sur des suites primitives et la conjecture d'Erdős", *C. R. Math. Acad. Sci. Paris* **357** (2019), no. 5, p. 413-417.

[6] J. D. Lichtman, "Almost primes and the Banks-Martin conjecture", *J. Number Theory* **211** (2020), p. 513-529.

[7] ——, "Mertens' prime product formula, dissected", *Integers* **21A** (2021), article no. A17 (15 pages).

[8] J. D. Lichtman, C. Pomerance, "The Erdős conjecture for primitive sets", *Proc. Am. Math. Soc.* **6** (2019), p. 1-14.

[9] Z. Zhang, "On a problem of Erdős concerning primitive sequences", *Math. Comput.* **60** (1993), no. 202, p. 827-834.