Problem 126 — Visual explainer (undergrad)
==========================================

Problem statement
---------------
Let $f(n)$ be maximal such that if $A\subseteq\mathbb{N}$ has $\lvert A\rvert=n$ then $\prod_{a\neq b\in A}(a+b)$ has at least $f(n)$ distinct prime factors. Is it true that $f(n)/\log n\to\infty$?

Picture
-------
Target integer N as "prime + offset":

N  =  p  +  a
     ^     ^
   prime  pick a from A

Think: A is a small "menu of offsets" that helps you hit all large N.

Question: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Context
-------
Area hint: additive number theory (primes) / sieve methods.

Notation (if it appears above)
-----------------------------
- `o(g(n))` means "grows strictly smaller than g(n)" (ratio → 0 as n→∞).

Benchmarks / known results (from comments)
----------------------------------------
- Investigated by Erd\H{o}s and Tur\'{a}n (prompted by a question of
  L\'{a}z\'{a}r and Gr\"{u}nwald) in their first joint paper, where they
  proved that\[\log n \ll f(n) \ll n/\log n\](the upper bound is trivial,
  taking $A=\{1,\ldots,n\}$).
- Erd\H{o}s says that $f(n)=o(n/\log n)$ has never been proved, but perhaps
  never seriously attacked.
- This problem has been formalised in Lean as part of the Google DeepMind
  Formal Conjectures project.