Erdős Problem 291

References:

• erdosproblems.com/291
• [ErGr80, p.34] Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).
• [Sh16] P. Shiu, The denominators of harmonic numbers. arXiv:1607.02863 (2016).
• [WuYa22] Wu, Bing-Ling and Yan, Xiao-Hui, On the denominators of harmonic numbers. {IV}. C. R. Math. Acad. Sci. Paris (2022), 53--57.

def Erdos291.L (n : ℕ) : ℕ

$L_n$ is the least common multiple of $\{1,\ldots,n\}$.

Equations

• Erdos291.L n = (Finset.Icc 1 n).lcm fun (x : ℕ) => x

theorem Erdos291.L_eval : L 1 = 1 ∧ L 2 = 2 ∧ L 3 = 6 ∧ L 4 = 12

def Erdos291.a (n : ℕ) : ℕ

$a_n$ is defined by $\sum_{1\leq k\leq n}\frac{1}{k}=\frac{a_n}{L_n}$.

Equations

• Erdos291.a n = ∑ k ∈ Finset.Icc 1 n, Erdos291.L n / k

theorem Erdos291.a_eval : a 1 = 1 ∧ a 2 = 3 ∧ a 3 = 11 ∧ a 4 = 25

theorem Erdos291.erdos_291.parts.i : sorry ↔ {n : ℕ | (a n).gcd (L n) = 1}.Infinite

Let $n\geq 1$ and define $L_n$ to be the least common multiple of $\{1,\ldots,n\}$ and $a_n$ by $\sum_{1\leq k\leq n}\frac{1}{k}=\frac{a_n}{L_n}$.

Is it true that $(a_n,L_n)=1$ occurs for infinitely many $n$?

theorem Erdos291.erdos_291.parts.ii : True ↔ {n : ℕ | (a n).gcd (L n) > 1}.Infinite

Is it true that $(a_n,L_n)>1$ occurs for infinitely many $n$?

Steinerberger has observed that the answer to the second question is trivially yes: for example, any $n$ which begins with a $2$ in base $3$ has $3\mid (a_n,L_n)$.

theorem Erdos291.erdos_291.variants.steinerberger_generalization (n p : ℕ) (hp : Nat.Prime p) (hpn : p ≤ n) : have k := n / p ^ Nat.log p n; p ∣ (a n).gcd (L n) ↔ ↑p ∣ (∑ i ∈ Finset.Icc 1 k, 1 / ↑i).num

More generally, if the leading digit of $n$ in base $p$ is $p-1$ then $p\mid (a_n,L_n)$. There is in fact a necessary and sufficient condition: a prime $p\leq n$ divides $(a_n,L_n)$ if and only if $p$ divides the numerator of $1+\cdots+\frac{1}{k}$, where $k$ is the leading digit of $n$ in base $p$. This can be seen by writing $a_n = \frac{L_n}{1}+\cdots+\frac{L_n}{n}$ and observing that the right-hand side is congruent to $1+\cdots+1/k$ modulo $p$. (The previous claim about $p-1$ follows immediately from Wolstenholme's theorem.)

theorem Erdos291.erdos_291.variants.shiu_heuristic_asymptotic : (fun (x : ℕ) => ↑{n ∈ Finset.Icc 1 x | (a n).gcd (L n) = 1}.card) =Θ[Filter.atTop] fun (x : ℕ) => ↑x / Real.log ↑x

This leads to a heuristic prediction (see for example a preprint of Shiu [Sh16]) of $\asymp\frac{x}{\log x}$ for the number of $n\in [1,x]$ such that $(a_n,L_n)=1$.

theorem Erdos291.erdos_291.variants.shiu_heuristic_density_zero : Filter.Tendsto (fun (N : ℕ) => ↑{n ∈ Finset.Icc 1 N | (a n).gcd (L n) = 1}.card / ↑N) Filter.atTop (nhds 0)

In particular, there should be infinitely many $n$, but the set of such $n$ should have density zero. Unfortunately this heuristic is difficult to turn into a proof.

theorem Erdos291.erdos_291.variants.wu_yan (h_indep : LinearIndependent ℚ fun (p : { p : ℕ // Nat.Prime p }) => 1 / Real.log ↑↑p) : Filter.limsup (fun (N : ℕ) => ↑↑{n ∈ Finset.Icc 1 N | (a n).gcd (L n) > 1}.card / ↑↑N) Filter.atTop = 1

Wu and Yan [WuYa22] have proved, conditional on $\frac{1}{\log p}$ being linearly independent over $\mathbb{Q}$ for any finite collection of primes $p$ (itself a consequence of Schanuel's conjecture), that the set of $n$ for which $(a_n,L_n)>1$ has upper density $1$.