ERDŐS/DAILY ▸

← back to the ledger

ERDőS #12 · PARTIAL

Erdős problem #12, wave 6z

Date of live check and computation: 2026-07-27 UTC.

Claim labels used below:

0. Mandatory live-page gate

I fetched both the problem page and its discussion thread through the Bright Data

browser, not by datacenter curl:

The live state was:

Thus the mandatory skip condition did not fire. The page has incorporated proofs of

the first and second subquestions, but explicitly leaves the third subquestion open.

I therefore did not duplicate the first/second constructions and worked only on the

reciprocal-sum question.

Verbatim live-page statement

The following is copied from the live LaTeX view:

> Let $A$ be an infinite set such that there are no distinct $a,b,c\in A$ such that $a\mid (b+c)$ and $b,c>a$. Is there such an $A$ with\[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}>0?\]Does there exist some absolute constant $c>0$ such that there are always infinitely many $N$ with\[\lvert A\cap\{1,\ldots,N\}\rvert

Here and throughout this report, “distinct” means that the forbidden configuration is

$a<b<c$ after interchanging $b,c$ if necessary. In particular, the live problem does

not forbid the repeated choice $b=c$. The checker uses exactly this live-page

condition.

Known results incorporated in the page

The page records the following.

1. Erdős and Sárközy proved that every such infinite $A$ has density zero. They also

gave examples whose counting function is larger than $N/f(N)$ at infinitely many

$N$, for any prescribed $f(N)\to\infty$.

2. The prime-square example $A=\{p^2:p\equiv3\pmod4\}$ has counting function of

order $\sqrt N/\log N$ and has the required divisibility property.

3. Elsholtz--Planitzer improved the construction to

\[ |A\cap[1,N]|\gg \frac{N^{1/2}} {(\log N)^{1/2}(\log\log N)^2(\log\log\log N)^2}. \]

4. The page gives Schoen's and Baier's upper estimates under the additional

pairwise-coprime hypothesis.

5. The 2026 DeepMind construction answers the first question yes and the second

question no. The comment simplifications improve this to a construction with

\[ |A\cap[1,N]|\ge \frac{N}{(\log N)^{O(\log\log\log N)}} \quad\text{for all sufficiently large }N. \]

6. The page's present unresolved statement is: it is unknown whether there is an

admissible $A$ with $\sum_{a\in A}1/a=\infty$.

What the 13 comments say

The comments were checked in full. Their mathematical content is as follows.

(i) and (ii). Thomas Bloom and Terence Tao then extracted the block/CRT mechanism

and observed that the within-block 3-AP-free ingredient is unnecessary for the

live distinct-$b,c$ formulation.

its links readable and separating the informal proof from the Lean proof. Nat

Sothanaphan linked a further simplified set of notes.

identifiers into constant-weight binary codes, with the examples $B_1,B_2$ and

$B_3,\ldots,B_8$ displayed on the page. Bloom observed the equivalent binary-digit

description and enlarged a “1” residue from one class to an oriented half of the

residue classes.

divergent reciprocal sum.

condition per block is already close to the harmonic budget, while the side

congruence conditions consume an additional factor. He says that either a

construction must go beyond congruence conditions on blocks, or a positive answer

likely needs an inverse theorem saying such congruence constructions are close to

optimal.

No comment claims to settle the third question.

1. Primary-source literature check

I searched exact titles, exact phrases from the conjecture, arXiv, DOI/publisher

records, and the papers cited by the live page. The following primary sources were

opened and checked.

1. P. Erdős and A. Sárközy, *On the divisibility properties of sequences of

integers*, Proc. London Math. Soc. 21 (1970), 97--101,

DOI <https://doi.org/10.1112/plms/s3-21.1.97>;

archival PDF <https://users.renyi.hu/~p_erdos/1970-13.pdf>.

The paper proves density zero and explicitly conjectures both convergence of the

reciprocal sum (indeed, a uniform absolute bound) and the then-open power saving.

2. P. Erdős, Problems and results in combinatorial number theory,

Astérisque 24--25 (1975),

<https://www.renyi.hu/~p_erdos/1975-30.pdf>, and

Problems and results on combinatorial number theory III (1977),

<https://www.renyi.hu/~p_erdos/1977-27.pdf>. Both repeat the reciprocal-sum

problem; the 1977 source says the available methods were far from it.

3. C. Elsholtz and S. Planitzer, On Erdős and Sárközy's sequences with Property P,

arXiv:1609.07935, <https://arxiv.org/abs/1609.07935>. This is the stated

counting-function construction and does not settle the reciprocal sum.

4. T. Schoen, On a Problem of Erdős and Sárközy,

DOI <https://doi.org/10.1006/JCTA.2000.3142>, and S. Baier,

A Note on P-Sets, <https://math.colgate.edu/~integers/e13/e13.pdf>.

These are the pairwise-coprime counting-function papers, not reciprocal-sum

resolutions.

5. B. Bedert, *On a problem of Erdős and Sárközy about sequences with no term

dividing the sum of two larger terms*, arXiv:2301.07065,

<https://arxiv.org/abs/2301.07065>. This resolves a finite cardinality problem.

Its displayed definition permits the two larger summands to coincide, so it is

important not to silently substitute that stronger convention for the current

live-page statement.

6. G. Tsoukalas et al., *Advancing Mathematics Research with AI-Driven Formal Proof

Search*, arXiv:2605.22763v2,

<https://arxiv.org/abs/2605.22763>. Section B.4 presents the first two solutions

and explicitly says that the third reciprocal-sum question remains open and

difficult. This June 2026 source postdates the April page edit and corroborates

the live status.

7. The current Formal Conjectures source

<https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/12.lean>

marks parts (i),(ii) solved and part (iii) research-open. Its IsGood definition

also confirms that equal $b=c$ is allowed and only distinct $b,c$ are forbidden.

The exact-phrase searches found no primary source claiming a resolution of part

(iii). This is a documented search miss, not a proof that no unindexed result exists.

2. Elementary structural facts

2.1 Tail residues are oriented

Lemma 1 [a]. Fix $a\in A$, and let $T=A\cap(a,\infty)$. For every pair of

different residue classes $\{r,-r\}$ modulo $a$, at most one of the two classes can

meet $T$. Each self-opposite class ($0$, and also $a/2$ when $a$ is even) contains

at most one member of $T$.

Proof. Elements $b,c$ in opposite classes satisfy $a\mid b+c$. If the classes

are different then $b\ne c$. In a self-opposite class, any two different elements

also have sum $0\bmod a$. Both alternatives are forbidden. $\square$

Consequently, a finite tail occupies at most

\[ \left\lfloor\frac a2\right\rfloor+1 \]

residue classes modulo $a$, with the one or two self-opposite classes having

multiplicity at most one. This elementary orientation is the local input behind all

the CRT constructions.

2.2 An infinite admissible set cannot contain 1 or 2

Lemma 2 [a]. If $A$ is infinite and admissible, then $1,2\notin A$.

Proof. If $1\in A$, any two distinct later elements violate the condition. If

$2\in A$, infinitely many later elements contain two of the same parity; their sum

is divisible by $2$. $\square$

This makes the computation over $\{3,\ldots,N\}$ below more relevant than the

unrestricted finite optimum.

3. A rigorous obstruction for the oriented-CRT block strategy

This section turns the heuristic barrier in Tao's final comment into a precise theorem

for a broad, explicitly delimited construction class.

3.1 The template

Let $q_1,q_2,\ldots$ be pairwise coprime odd moduli. For every $i$, fix a set

\[ U_i\subseteq\mathbb Z/q_i\mathbb Z,\qquad U_i\cap(-U_i)=\varnothing. \]

Thus $0\notin U_i$ and $u+v\ne0\bmod q_i$ for all $u,v\in U_i$.

A block pattern is a pair of disjoint finite coordinate sets $(D_k,S_k)$. Its

permitted integers satisfy

\[ n\equiv0\pmod{q_i}\quad(i\in D_k),\qquad n\bmod q_i\in U_i\quad(i\in S_k). \]

Coordinates in $D_k$ are “divisibility digits”; coordinates in $S_k$ are “safe

digits”. Put

\[ Q_k=\prod_{i\in D_k\cup S_k}q_i,\qquad \delta_k= \prod_{i\in D_k}\frac1{q_i} \prod_{i\in S_k}\frac{|U_i|}{q_i}. \]

Assume:

1. the active coordinate sets are nested:

$D_k\cup S_k\subseteq D_\ell\cup S_\ell$ for $k<\ell$;

2. the ordered-separation condition holds:

\[ D_k\cap S_\ell\ne\varnothing\qquad(k<\ell); \]

3. $B_k$ is the permitted set (or a subset of it) inside

\[ I_k=[X_k,\lambda X_k),\qquad 1<\lambda\le\frac32, \]

the intervals are ordered and disjoint, and $Q_k\le X_k$ except perhaps for

finitely many $k$.

3.2 Cylinder inequality

Theorem 3 [a]. Under assumptions 1--3,

\[ \sum_k\delta_k\le1 \quad\text{and}\quad \sum_k\sum_{n\in B_k}\frac1n<\infty. \]

After discarding the finitely many exceptional blocks with $Q_k>X_k$, the latter

sum is at most $\lambda$.

Proof.

For each coordinate $i$, make a three-symbol probability space with symbol

probabilities

\[ \Pr(D)=\frac1{q_i},\qquad \Pr(S)=\frac{|U_i|}{q_i},\qquad \Pr(*)=1-\frac{1+|U_i|}{q_i}. \]

The last quantity is nonnegative because $0\notin U_i$.

The cylinder $C_k$ that fixes symbol $D$ on $D_k$ and $S$ on $S_k$ has measure

$\delta_k$. If $k<\ell$, a coordinate in $D_k\cap S_\ell$ would have to be both

$D$ and $S$, so $C_k\cap C_\ell=\varnothing$. For any finite collection of blocks,

ordinary finite product probability therefore gives

\[ \sum_{k\le K}\delta_k\le1. \]

Letting $K\to\infty$ proves the first assertion without invoking any infinite-product

measure theorem.

By the Chinese remainder theorem, the permitted set for block $k$ occupies exactly

$R_k=\delta_kQ_k$ residue classes modulo $Q_k$. Every residue class contributes at

most $(\lambda-1)X_k/Q_k+1$ integers to $I_k$. Hence, when $Q_k\le X_k$,

\[ |B_k| \le R_k\left(\frac{(\lambda-1)X_k}{Q_k}+1\right) =\delta_k\bigl((\lambda-1)X_k+Q_k\bigr) \le\lambda\delta_kX_k. \]

Since every $n\in B_k$ is at least $X_k$,

\[ \sum_{n\in B_k}\frac1n\le\lambda\delta_k. \]

Summing and using $\sum\delta_k\le1$ proves convergence. $\square$

3.3 Why these blocks are admissible

Lemma 4 [a]. The union of the blocks in the template has the live-page

divisibility property.

Proof.

\[ 2a

No multiple of $a$ lies strictly between $2a$ and $3a$.

Pick $i\in D_k\cap S_\ell$. The later element has residue in $U_i$. By nested

activity, the other element is either $0\bmod q_i$ or has residue in $U_i$.

In the first case the sum is a nonzero member of $U_i$; in the second it is

nonzero because $U_i\cap(-U_i)=\varnothing$. But $q_i\mid a$, so $a\nmid b+c$.

$\square$

3.4 Consequence for the live-comment constructions

The binary/constant-weight construction in the comments takes $q_i$ to be successive

odd primes, uses digit $D$ for residue $0$, and uses either residue $1$ or the fixed

oriented half

\[ U_i=\{1,\ldots,(q_i-1)/2\} \]

for digit $S$. Earlier active coordinates remain active, and the code was designed

precisely so that $D_k\cap S_\ell\ne\varnothing$ for $k<\ell$.

There are $O(\log k)$ active primes in block $k$. Bertrand's postulate gives the

crude bound

\[ Q_k\le \exp(O((\log k)^2))=o(2^k), \]

so $Q_k\le X_k=2^k$ eventually. Therefore Theorem 3 applies to these regular

oriented-CRT implementations and proves that their reciprocal sums converge

**[b, modulo Bertrand's postulate and the parameter count stated in the live

comment]**.

The important point is not merely that one displayed construction is too sparse:

within this entire fixed-coordinate, equidistributed template, changing or optimizing

the binary code cannot produce a divergent reciprocal sum. The cylinder budget is

at most one.

4. Exact finite computation

Define

\[ M(N)=\max_{\substack{F\subseteq[1,N]\\F\text{ admissible}}} \sum_{n\in F}\frac1n \]

and, using Lemma 2, the necessary infinite-set relaxation

\[ M_{\ge3}(N)= \max_{\substack{F\subseteq\{3,\ldots,N\}\\F\text{ admissible}}} \sum_{n\in F}\frac1n. \]

The standalone checker proves:

\[ \boxed{M(1)=1,\qquad M(N)=\frac32\quad(2\le N\le300)} \tag{5} \]

with witness $\{1,2\}$, and

\[ \boxed{ M_{\ge3}(200)= \frac{7706174493}{7012827052} =1.098868464295\ldots } \tag{6} \]

with witness

\[ \{3,5,6,8,11,20,23,26,56,71,143,146,191\}. \]

Both (5) and (6) are [d]. Equation (6) is sharp for the displayed finite

relaxation. I do not claim that its maximizing witness extends to an infinite

admissible set.

Exact algorithm and certification logic

The forbidden triples form a 3-uniform hypergraph with edges

\[ (a,b,c),\qquad 1\le aLet $L=\operatorname{lcm}(1,\ldots,N)$ and give vertex $n$ the integer weight $L/n$.

Maximizing the integer total is exactly the harmonic optimization, with no

floating-point rounding.

The recursion processes vertices increasingly. If $n$ is selected, then for every

already selected $a<n$ it marks all future $c>n$ satisfying $a\mid n+c$ as forbidden.

Thus every legal subset is visited once. At every node,

> current integer weight + total weight of all unprocessed non-forbidden vertices

is a rigorous upper bound on every completion. A branch is discarded only when

this exact integer upper bound cannot beat the incumbent. The optimized solver

visited 1,903,537 nodes for (5) and 5,874,365 nodes for (6).

As an implementation-independent sanity check, the script also literally enumerates

all $2^{18}$ subsets at $N=18$ and gets the same optimum as the branch-and-bound

solver. It separately checks every generated forbidden-bit entry against

$a\mid b+c$ by a cubic loop for $N\le35$.

The finite result cannot settle the infinite question. The unrestricted optimum is

even attained by $\{1,2\}$, which Lemma 2 shows cannot occur in an infinite example.

Equation (6) removes that immediate artefact, but a cutoff of 200 supplies no

uniform-in-$N$ argument.

5. Reproducible checker

Complete standard-library source:

runs/erdos12_wave6z_verify.py

SHA-256:

60b291ae9dfe3605b9abd0d9626dce621aa37bc44cfd3c0b56606501e5c122b8

Run:

python runs/erdos12_wave6z_verify.py

The exact run performed for this report printed:

independent exhaustive check N=18:
  optimum=3/2, witness=[1, 2]
optimized exact solver cross-check N=18:
  optimum=3/2, witness=[1, 2], nodes=49, seconds=0.000
exact forbidden-triple optimization N=300:
  optimum=3/2, witness=[1, 2], nodes=1903537, seconds=9.001
exact optimization with 1,2 excluded, N=200:
  optimum=7706174493/7012827052 (1.098868464295), witness=[3, 5, 6, 8, 11, 20, 23, 26, 56, 71, 143, 146, 191], nodes=5874365, seconds=19.062
ordered oriented-CRT code check:
  patterns=78
  exact cylinder-weight sum=61910546628955511/307444891294245705
  decimal cylinder-weight sum=0.201371199789
  exact four-coordinate toy sum=41/1155
ALL CHECKS PASSED

The code also builds the first three code epochs of sizes $2,4,8$ (78 patterns),

checks every ordered-separation relation, checks the two-later-block modular

certificate, recomputes all cylinder weights as Fractions, and enumerates every

residue in a four-prime CRT toy instance.

6. Exact remaining wall

Theorem 3 says precisely where the current construction machinery stops. To obtain a

negative answer (a divergent reciprocal sum), a construction must evade at least one

of the following:

1. fixed, scale-independent oriented residue sets $U_i$;

2. coordinatewise zero/safe certificates with ordered separation;

3. nested activation of coprime coordinates;

4. CRT-regular blocks whose period is no longer than their scale.

Possible escape routes are scale-dependent orientations, genuinely composite and

non-coordinatewise correlations, blocks shorter than their joint CRT period, or a

non-block construction. None was found here.

For a positive answer, Lemma 1 alone is insufficient. It orients residues modulo

each entire $a\in A$, but those moduli overlap heavily and their orientations can

change with $a$ and with scale. The exact missing result is an **inverse/entropy

lemma** converting these arbitrary, overlapping tail orientations into disjoint

cylinders (or another summable budget) whose mass dominates

\[ \sum_{n\in A\cap[X,2X]}\frac1n. \]

Ordinary CRT multiplication gives that comparison only in the regular template.

Ordinary larger-sieve arguments also lose the required information when the moduli

$a\in A$ are not pairwise coprime. Establishing such a self-sieving inverse lemma,

or constructing a counterexample that violates it, is the remaining uniform step;

finite computation cannot supply it.

No proof or counterexample to part (iii) is claimed.

PARTIAL: Proved an elementary cylinder-budget theorem forcing convergence for the regular oriented-CRT block template used in the live comments, and exactly computed the finite harmonic optima M(N)=3/2 through N=300 and M_{\ge3}(200)=7706174493/7012827052; the unrestricted reciprocal-sum question remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger