Skip to content

Erdős problem 796

If g3(n)g_3(n) is the largest size of A⊆[1,n]A \subseteq [1,n] with fewer than three representations of every product a1a2a_1 a_2, does its conjectured second-order normalized term converge? The candidate proof gives an explicit limit constant.

Sources

The source's own material, retained exactly.

2 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

796.lean

Retained formal statement1 of 1

Let k≥2k\geq 2 and let gk(n)g_k(n) be the largest possible size of A⊆{1,…,n}A\subseteq \{1,\ldots,n\} such that every mm has <k<k solutions to m=a1a2m=a_1a_2 with a1<a2∈Aa_1<a_2\in A. Is it true that g3(n)=log⁡log⁡nlog⁡nn+(c+o(1))nlog⁡ng_3(n)=\frac{\log\log n}{\log n}n+(c+o(1))\frac{n}{\log n} for some constant cc?

The answer is yes: the rescaled error normalizedError converges.

FormalConjectures/ErdosProblems/796.leanErdos796.erdos_7961 lineExact file
True ↔ ∃ c, Filter.Tendsto Erdos796.normalizedError Filter.atTop (nhds c)
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.