# P3040: Maximal Number of Distinct Prime Factors in Pairwise Sums Products

- ID: `P3040`
- Reference: `erdos-problem-126`
- Page: https://theoremdb.org/statements/P3040
- Record maturity: Reviewed problem with recorded work

## Problem

Erdős Problem 126: For each positive integer $n$, let $f(n)$ denote the maximum integer $m$ such that for every subset $A \subseteq \mathbb{N}$ with $|A| = n$, the product $\prod_{\substack{a,b \in A \\ a \neq b}} (a + b)$ has at least $m$ distinct prime factors. Is it true that $\displaystyle\frac{f(n)}{\log n} \to \infty$ as $n \to \infty$?

### Context

This problem concerns the growth rate of a function defined through extremal combinatorial number theory. Erdős and Turán established in their first joint paper that $\log n \ll f(n) \ll \frac{n}{\log n}$, and it remains open whether the lower bound can be strengthened to $f(n)/\log n \to \infty$.

### Problem setup

- **Definition (For a finite set $A \subseteq \mathbb{N}$, the off-diagonal product $\prod_{\substack{a,b \in A \\ a \neq b}} (a + b)$).** For a finite set $A \subseteq \mathbb{N}$, the off-diagonal product $\prod_{\substack{a,b \in A \\ a \neq b}} (a + b)$ is the product of all sums $a + b$ where $a$ and $b$ are distinct elements of $A$.
- **Definition (For a positive integer $k$, we write $\omega(k)$ for the number of distinct prime factors of $k$).** For a positive integer $k$, we write $\omega(k)$ for the number of distinct prime factors of $k$.
- **Definition (For functions $g, h: \mathbb{N} \to \mathbb{R}$, we say $g(n) = O(h(n))$ if there exists $C > 0$ and $N \in \mathbb{N}$ such that $|g(n)| \leq C|h(n)|$ for all $n \geq N$).** For functions $g, h: \mathbb{N} \to \mathbb{R}$, we say $g(n) = O(h(n))$ if there exists $C > 0$ and $N \in \mathbb{N}$ such that $|g(n)| \leq C|h(n)|$ for all $n \geq N$.
- **Definition (For functions $g, h: \mathbb{N} \to \mathbb{R}$, we say $g(n) = o(h(n))$ if $\lim_{n \to \infty} g(n)/h(n) = 0$).** For functions $g, h: \mathbb{N} \to \mathbb{R}$, we say $g(n) = o(h(n))$ if $\lim_{n \to \infty} g(n)/h(n) = 0$.
- **Definition (We say $g(n) \ll h(n)$ if $g(n) = O(h(n))$).** We say $g(n) \ll h(n)$ if $g(n) = O(h(n))$.
- **Remark.** This problem concerns the growth rate of a function defined through extremal combinatorial number theory. Erdős and Turán established in their first joint paper that $\log n \ll f(n) \ll \frac{n}{\log n}$, and it remains open whether the lower bound can be strengthened to $f(n)/\log n \to \infty$.

### What counts as a solution

- Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 126: For each positive integer $n$, let $f(n)$ denote the maximum integer $m$ such that for every subset $A \subseteq \mathbb{N}$ with $|A| = n$, the product $\prod_{\substack{a,b \in A \\ a \neq b}} (a + b)$ has at least $m$ distinct prime factors. Is it true that $\displaystyle\frac{f(n)}{\log n} \to \infty$ as $n \to \infty$?

## Status

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 126 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 126: For each positive integer $n$, let $f(n)$ denote the maximum integer $m$ such that for every subset $A \subseteq \mathbb{N}$ with $|A| = n$, the product $\prod_{\substack{a,b \in A \\ a \neq b}} (a + b)$ has at least $m$ distinct prime factors. Is it true that $\displaystyle\frac{f(n)}{\log n} \to \infty$ as $n \to \infty$? [1](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (Current status and unresolved remainder).** OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 126 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 126: For each positive integer $n$, let $f(n)$ denote the maximum integer $m$ such that for every subset $A \subseteq \mathbb{N}$ with $|A| = n$, the product $\prod_{\substack{a,b \in A \\ a \neq b}} (a + b)$ has at least $m$ distinct prime factors. Is it true that $\displaystyle\frac{f(n)}{\log n} \to \infty$ as $n \to \infty$?

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 126 as open. The unresolved remainder is the full displayed statement.

A complete resolution must satisfy this condition: Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 126: For each positive integer $n$, let $f(n)$ denote the maximum integer $m$ such that for every subset $A \subseteq \mathbb{N}$ with $|A| = n$, the product $\prod_{\substack{a,b \in A \\ a \neq b}} (a + b)$ has at least $m$ distinct prime factors. Is it true that $\displaystyle\frac{f(n)}{\log n} \to \infty$ as $n \to \infty$?

### Background and intake notes

- Original intake status: OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 126 as open. The unresolved remainder is the full displayed statement.
- The maintained database entry for Erdős Problem 126 was open at commit 8138974387d9030542daabe67faaa33eff9356f8.
- The pinned Formal Conjectures declaration was matched by problem number and source locator.
- The controlled TheoremDB source corpus was checked for an already published record with the same slug.

### Open directions

- **Route 1** (reported): Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 126: For each positive integer $n$, let $f(n)$ denote the maximum integer $m$ such that for every subset $A \subseteq \mathbb{N}$ with $|A| = n$, the product $\prod_{\substack{a,b \in A \\ a \neq b}} (a + b)$ has at least $m$ distinct prime factors. Is it true that $\displaystyle\frac{f(n)}{\log n} \to \infty$ as $n \to \infty$? [1](#reference-1)

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `erdos-problem-126`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Erdős Problems database, Problem 126, maintained status record. Erdős Problems record 126, checked 2026-08-01. Problem 126; status field and linked bibliography https://www.erdosproblems.com/126
   - Also cited at Problem 126; status snapshot 8138974387d9030542daabe67faaa33eff9356f8
   - Also cited at See dataset.references[0] for the exact external source and locator.
   - Also cited at Editorial research route recorded 2026-07-31
   - reference_database; reference source; commit 8138974387d9030542daabe67faaa33eff9356f8; checked 2026-07-31
   - Source use: original_summary
   - Records the current open status and links the literature attached to this exact numbered problem.
   - Source used to formulate or check the problem record.
   - Source used to assess the problem's recorded status.
   - For Maximal Number of Distinct Prime Factors in Pairwise Sums Products: Records the current open status and links the literature attached to this exact numbered problem.
   - Source named by the research packet.
2. <a id="reference-2"></a>Erdős problem database, data/problems.yaml, commit 8138974387d9030542daabe67faaa33eff9356f8. Problem 126 entry in data/problems.yaml https://github.com/teorth/erdosproblems/blob/8138974387d9030542daabe67faaa33eff9356f8/data/problems.yaml
   - reference_database; reference source; commit 8138974387d9030542daabe67faaa33eff9356f8; checked 2026-07-31
   - Source use: original_summary
   - Pins the maintained database snapshot used for this release's dated status decision.
   - Source used to assess the problem's recorded status.
   - For Maximal Number of Distinct Prime Factors in Pairwise Sums Products: Pins the maintained database snapshot used for this release's dated status decision.
3. <a id="reference-3"></a>Google DeepMind, Formal Conjectures, formal statement for Erdős Problem 126. GitHub commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1. FormalConjectures/ErdosProblems/126.lean:L41; theorem erdos_126; commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1 https://github.com/google-deepmind/formal-conjectures/blob/bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1/FormalConjectures/ErdosProblems/126.lean#L41
   - reference_database; primary source; commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1; checked 2026-07-31
   - Source use: original_summary
   - Supplies the pinned formal declaration whose human-readable editorial statement is published here.
   - Source used to assess the problem's recorded status.
   - For Maximal Number of Distinct Prime Factors in Pairwise Sums Products: Supplies the pinned formal declaration whose human-readable editorial statement is published here.