Skip to content

Erdős problem 401

Is there some function f(r)f(r) such that f(r)→∞f(r)\to \infty as r→∞r\to\infty, such that, for infinitely many nn, there exist a1,a2a_1,a_2 with a1+a2>n+f(r)log⁡na_1+a_2> n+f(r)\log n such that a1!a2!∣n!2n3n⋯prna_1!a_2! \mid n!2^n3^n\cdots p_r^n?

Sources

The source's own material, retained exactly.

1 retained statement36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

401.lean

Retained formal statement1 of 1

Is there some function f(r)f(r) such that f(r)→∞f(r)\to \infty as r→∞r\to\infty, such that, for infinitely many nn, there exist a1,a2a_1,a_2 with a1+a2>n+f(r)log⁡na_1+a_2> n+f(r)\log n such that a1!a2!∣n!2n3n⋯prna_1!a_2! \mid n!2^n3^n\cdots p_r^n?

It is ambiguous in [ErGr80] what the intended quantifiers are on the variables (they write 'is it true that we can find a1+a2>n+f(r)log⁡na_1+a_2>n+f(r)\log n...'). Comparing to previous problems such as [728] and [729] it seems most likely that they intended to ask the formulation in the problem statement.

The answer is yes: Barreto and Leeham have used ChatGPT to provide a proof of the stated problem (in fact essentially the same construction as their solution to [729]).

FormalConjectures/ErdosProblems/401.leanErdos401.erdos_40112 linesExact file
True ↔  ∃ f,    Filter.Tendsto f Filter.atTop Filter.atTop ∧      ∀ (r : ℕ),        1 ≤ r →          {n |              ∃ a₁ a₂,                0 < a₁ ∧                  0 < a₂ ∧                    ↑a₁ + ↑a₂ > ↑n + f r * Real.log ↑n ∧                      a₁.factorial * a₂.factorial ∣                        n.factorial * (∏ i ∈ Finset.range r, Nat.nth Nat.Prime i) ^ n}.Infinite
SolvedProof has a holelean4external proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.