Erdős Problem #126

FORMAL RESTATEMENT

QUICK LITERATURE AND CONTEXT CHECK

WORK

A finite kernel lemma

Each $M_p$ is positive semidefinite because its quadratic form is $\sum_Bw_p(B)(\sum_{i\in B}x_i)^2$. Hence so are $Q_p=(\sigma_p(i)\sigma_p(j)M_p(i,j))$ and $Q=\sum_pQ_p=R-C$. Write $T=\operatorname{tr}Q$ and $\Sigma=\sum_{i,j}C(i,j)>0$. For every sign vector $s$, negative off-diagonal entries of $Q$ imply \[ s^TQs+\mathbf1^TQ\mathbf1\le2T. \] Taking $s=\sigma_p$ and discarding nonnegative quadratic forms gives $\sum_{i,j}M_p(i,j)\le2T$. Also $\mathbf1^TQ\mathbf1\ge0$, so $\sum R\ge\sum C=\Sigma$. Consequently \[ 2\Sigma\le\sum_p\sum_{i,j}M_p(i,j)\le2rT, \qquad\Sigma\le rT. \tag{1} \]

Fix $p$. For each $i$, choose the smallest support $A_i$ containing it; if none exists put $A_i=V$. There is a map $h$ with $h(i)\in A_i\setminus\{i\}$ such that each value is used at most twice. To justify this application of Hall's theorem, for $X\subseteq V$ put $N(X)=\bigcup_{i\in X}(A_i\setminus\{i\})$. The supports indexed by $X\setminus N(X)$ are pairwise disjoint: if two were nested, one of their distinct indexing vertices would belong to $N(X)$. Choosing one point in each punctured support injects $X\setminus N(X)$ into $N(X)$. Thus $|X|\le2|N(X)|$, which is Hall's condition for two copies of $V$. Laminarity and minimality now give \[ M_p(i,i)=M_p(i,h(i))\le C(i,h(i)). \tag{2} \] The inequality holds because a term is either counted in $C$ or is bounded by $R<C$. It also holds when $M_p(i,i)=0$.

Let $c_i=\sum_j C(i,j)$ and $d_i=2nc_i-\Sigma$. Testing conditional negative semidefiniteness on $ne_i-\mathbf1$ and $n(e_i+e_j)-2\mathbf1$, using $C(i,i)=0$, gives \[ d_i\ge0,\qquad n^2 C(i,j)\le d_i+d_j,\qquad \sum_i d_i=n\Sigma. \] Sum $2$, observing that each $h(i)$ is used at most twice: \[ n^2\sum_iM_p(i,i)\le3n\Sigma. \] After summing over $p$, $nT\le3r\Sigma$. Combine with $1$, and cancel $\Sigma>0$, to obtain $n\le3r^2$.

The arithmetic kernels

Define a further kernel $B$ by summing $\log p$ over all self-opposite classes modulo $p^\ell$ containing both indices. It is positive semidefinite, being a nonnegative sum of kernels $\mathbf1_D(i)\mathbf1_D(j)$. Unique factorization gives, for $i\ne j$, \[ C(i,j)+B(i,j)=\log(a_i+a_j),\qquad R(i,j)+B(i,j)\le\log|a_i-a_j|. \tag{3} \] The second inequality follows because equal-residue and self-opposite contributions each divide the difference. Therefore $R(i,j)<C(i,j)$.

Finally $L(i,j)=\log(a_i+a_j)$ is conditionally negative semidefinite. Indeed set $\rho_i=(a_i-1)/(a_i+1)$, so $0\le\rho_i<1$. Apart from terms depending on a single index and a constant, \[ L(i,j)=\log(1-\rho_i\rho_j) =-\sum_{m\ge1}\frac{\rho_i^m\rho_j^m}{m}. \] For a zero-sum vector its quadratic form is $-\sum_{m\ge1}(\sum_i x_i\rho_i^m)^2/m\le0$. Off the diagonal $C+B=L$ by $3$. On the diagonal $C(i,i)=0$ and $B(i,i)\le\log(2a_i)=L(i,i)$. Thus $L-C-B$ is a nonnegative diagonal matrix. Subtracting it and the positive semidefinite $B$ shows that $C$ has the required conditional property. The finite lemma applies: \[ f(n)\ge\sqrt{n/3},\qquad \frac{f(n)}{\log n}\longrightarrow\infty. \] $\square$

VERIFICATION

FINAL STATUS

SOURCES

COMPLETION ESTIMATE

1) FORMAL RESTATEMENT

For a finite set $A\subset \mathbb{N}$ with $|A|=n$, define \[ P(A):=\prod_{\substack{a,b\in A\\ a\neq b}} (a+b). \] Let $\omega(m)$ denote the number of distinct prime factors of $m$. Define \[ f(n):=\min_{\substack{A\subset\mathbb{N}\\ |A|=n}} \omega(P(A)). \] (Equivalently, $f(n)$ is the maximal integer such that every $n$-element set $A$ makes $P(A)$ have at least $f(n)$ distinct prime factors.)

Given the bounds quoted in the text, one knows $\log n \ll f(n) \ll n/\log n$.

Question. Is it true that \[ \lim_{n\to\infty} \frac{f(n)}{\log n} = \infty\ ? \]

2) QUICK LITERATURE/CONTEXT CHECK

(Restricted to statements explicitly present in 123-137.tex.) - Erdos and Turan $1934$ proved $\log n\ll f(n)\ll n/\log n$. - The problem asks whether $f(n)/\log n\to\infty$.

3) ATTACK PLAN

- Prove structural properties of $f(n)$ (monotonicity, small-$n$ exact values). - Attempt to force many primes by considering congruence constraints on sums $a+b$. - Use small computational experiments to guess behavior.

4) WORK

Lemma 4.1 (Monotonicity). The function $f(n)$ is nondecreasing: $f(n+1)\ge f(n)$ for all $n\ge 1$.

Proof. Let $A$ be any set of size $n+1$ and let $B\subset A$ be any $n$-element subset. Then $P(B)$ divides $P(A)$ because $P(B)$ is the subproduct of $P(A)$ over pairs inside $B$. Therefore $\omega(P(A))\ge \omega(P(B))$. Since this holds for every $B$ of size $n$, and by definition every $n$-element set satisfies $\omega(P(B))\ge f(n)$, we obtain $\omega(P(A))\ge f(n)$ for every $A$ of size $n+1$. Taking the minimum over $A$ shows $f(n+1)\ge f(n)$. $\square$

Lemma 4.2 (Exact value $f(3)=2$). For every set $A=\{a,b,c\}$ of three distinct positive integers, $\omega(P(A))\ge 2$. Moreover, equality occurs (e.g. for $A=\{1,3,5\}$), so $f(3)=2$.

Proof. Write the three pairwise sums as \[x=a+b,\quad y=a+c,\quad z=b+c,\] so $P(A)$ is (up to squares) the product $xyz$. Suppose for contradiction that $\omega(xyz)=1$, i.e. $x,y,z$ are all powers of a single prime $p$. Then $p$ divides each of $x,y,z$, hence $x\equiv y\equiv z\equiv 0\pmod p$. Subtracting gives $b-c=x-y\equiv 0\pmod p$, and similarly $a-c\equiv 0\pmod p$; thus $a\equiv b\equiv c\pmod p$. Then $x=a+b\equiv 2a\pmod p$, so $2a\equiv 0\pmod p$. If $p$ is odd, then $a\equiv 0\pmod p$, hence $p\mid a,b,c$. Dividing $a,b,c$ by $p$ yields a smaller triple with the same property; iterating gives an impossible infinite descent in positive integers. Therefore $p=2$. But if $x,y,z$ are powers of 2, then in particular they are all even, so $a,b,c$ must all have the same parity. If all are odd, then each sum is congruent to $2\pmod 4$, so each of $x,y,z$ has 2-adic valuation exactly 1, forcing $x=y=z=2$, which would imply $a=b=c=1$, contradicting distinctness. Hence all of $a,b,c$ are even, so dividing by 2 gives a smaller triple with the same property, again yielding infinite descent. Thus $\omega(xyz)\ge 2$ always. The example $A=\{1,3,5\}$ has sums $4,6,8$ with prime set $\{2,3\}$, so $\omega(P(A))=2$ and $f(3)=2$. $\square$

Corollary 4.3. $f(4)=2$.

Proof. By Lemma 4.1 and Lemma 4.2, $f(4)\ge f(3)=2$. On the other hand, the explicit set $A=\{1,5,7,11\}$ has all pairwise sums in $\{6,8,12,16,18\}$, hence every pairwise sum has prime factors only from $\{2,3\}$. Therefore $\omega(P(A))\le 2$, so $f(4)\le 2$. $\square$

Lemma 4.4 (A simple upper bound). For all $n\ge 2$, \[ f(n) \le \pi(2n), \] where $\pi(x)$ is the number of primes $\le x$.

Proof. Take $A=\{1,2,\dots,n\}$. Then every factor $(a+b)$ lies in $[3,2n]$, so every prime divisor of $P(A)$ is $\le 2n$. Hence $\omega(P(A))\le \pi(2n)$ for this particular $A$, and therefore the minimum $f(n)$ is also $\le \pi(2n)$. $\square$

FAST REALITY CHECK (computation, heuristic only). Searching over sets $A\subset\{1,\dots,30\}$ found: - For $n=2$, minimum $\omega(P(A))$ is 1, achieved by $\{1,2\}$. - For $n=3$, minimum is 2, achieved by $\{1,2,7\}$. - For $n=4$, minimum is 2, achieved by $\{1,5,7,11\}$. - For $n=5$, the minimum within this search window was 3 (example $\{1,2,7,11,25\}$). This does not determine $f(5)$ globally, but is consistent with growth beyond 2.

5) VERIFICATION

- Lemma 4.1 is a clean divisibility argument: restricting to an $n$-subset only removes factors, so primes cannot be lost when passing from subset to superset. - Lemma 4.2 carefully rules out the "single prime" case by congruences and infinite descent. - Corollary 4.3 uses both the monotonicity and an explicit example, so it is rigorous.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result: - $f(n)$ is nondecreasing (Lemma 4.1). - Exact small values: $f(2)=1$, $f(3)=2$ (Lemma 4.2), and $f(4)=2$ (Corollary 4.3). - A simple universal upper bound $f(n)\le \pi(2n)$ (Lemma 4.4).

(ii) Exact first gap: - Prove a super-logarithmic lower bound: show that for every $n$-element set $A$, the product of pairwise sums must contain more than $C\log n$ distinct primes for any fixed $C$ as $n\to\infty$.

(iii) Top 3 next moves: 1. Develop a structural theorem for sets $A$ whose pairwise sums have prime factors restricted to a small set $P$; show such $A$ must be small. 2. Use sieve/graph methods: color edges of $K_n$ by a prime divisor of $a_i+a_j$ and bound the number of colors needed. 3. Attempt a "many moduli" argument: for many primes $p$, show there must exist at least one pair sum divisible by $p$ with a new prime, forcing $\omega(P(A))$ large.

(iv) What a minimal counterexample would likely look like: - A large set $A$ for which all pairwise sums $a+b$ are composed only of primes from a set $P$ with $|P|\asymp \log n$, implying strong congruence alignment of $A$ modulo many primes simultaneously.