Erdős problem 538 — wave9p report

Date: 2026-07-28 UTC

Artifacts:

• Standalone verifier: runs/erdos538_wave9p_reverify.py
• This report: runs/erdos538_wave9p.md

Claim labels used below:

• (a) elementary-rigorous: a complete proof is given here, using only

elementary algebra, counting, unique factorisation, or finite averaging.

• (b) rigorous-modulo-named-theorem: the proof is complete after the

explicitly named standard theorem or cited published theorem.

• (c) plausible/structural-unverified: a claim not promoted to a theorem.
• (d) computational-only: established only by the indicated exact

computation.

No mathematical conclusion below is labelled (c).

0. Mandatory page/status gate

Live-origin warning

(d) NOT LIVE-ORIGIN-VERIFIED BECAUSE THE SITE ITSELF WAS DOWN. Before doing any mathematics I used the required Bright Data browser route, with CAPTCHA solving, on https://www.erdosproblems.com/538. It returned only

Site down for planned maintenance... We'll be back soon!

with title Site down for planned maintenance. I retried after the mathematical work and obtained exactly the same result. The browser was available; the authoritative origin content was not.

I therefore used the newest accessible first-party indexed copy, not memory or the stale task YAML. The Er73 open bibliography page was crawled about three weeks before this run and gives the recommended access date 2026-07-02 for problem 538. I cross-checked it against the indexed problem page, discussion thread, the indexed open number-theory listing, and the site's public database at commit 2e7e7a630f9814f3df562bc1b207d9ad41451a55 (2026-07-28 07:39:21 UTC). The database is corroborative only because its entry for 538 was last updated in 2025.

(d) The newest accessible first-party state says:

• OPEN This is open, and cannot be resolved with a finite computation.
• Comment activity that has not yet been incorporated into the remarks:

None Partial Solution.

• There are no solutions, partial or complete, claimed in the comments.
• 0 comments on this problem.
• Likes this problem | Alfaiz.
• Interested in collaborating | None.
• Currently working on this problem | None.
• This problem looks difficult | Prasannam.
• This problem looks tractable | None.
• both formalisation markers: None.

The indexed forum landing page's “Solution Claims” list also does not contain

1. Thus no stop condition was visible in the newest accessible first-party

state. There is an unavoidable narrow caveat: an origin-only change after the last index crawl cannot be excluded while the site is under maintenance.

Verbatim statement from the newest accessible page copy

Let \(r\geq 2\) and suppose that \(A\subseteq\{1,\ldots,N\}\) is such that, for any \(m\), there are at most \(r\) solutions to \(m=pa\) where \(p\) is prime and \(a\in A\). Give the best possible upper bound for \[ > \sum_{n\in A}\frac{1}{n}. > \]

Verbatim listed result

Erdős observed that \[ > \sum_{n\in A}\frac{1}{n}\sum_{p\leq N}\frac{1}{p} > \leq r\sum_{m\leq N^2}\frac{1}{m}\ll r\log N, > \] and hence \[ > \sum_{n\in A}\frac{1}{n} > \ll r\frac{\log N}{\log\log N}. > \] See also [536] and [537].

The page cites only [Er73] for problem 538.

1. Outcome

Put

The principal result of this report is the uniform order

for all integers \(r\ge2\) and all sufficiently large \(N\), with absolute implicit constants. This is (b) rigorous modulo Bertrand's postulate and Mertens' theorem

For fixed \(r\), (1) is \(M_r(N)=\Theta_r(\log N/\log\log N)\), matching Erdős's listed upper bound. Uniformity in \(r\) matters: the answer saturates at the trivial harmonic scale once \(r\) is of order \(\log\log N\).

The proof below gives the stronger finite sandwich. Write

and

Then, for every \(r,N\ge2\),

The lower bound in (2) is harmless but vacuous when \(H_N/4-1<0\). The upper half is (a); the lower half is (b) only because its palette uses Bertrand's postulate.

The constants in (2) are deliberately conservative and are not claimed optimal. Thus this report determines the best possible order, including the dependence on \(r\); it does not determine the exact finite value of \(M_r(N)\) or the leading asymptotic constant.

2. Primary-source and literature audit

Original source

(d) Primary-source verified. I opened P. Erdős, “Problems and Results on Combinatorial Number Theory,” Chapter 12 of J. N. Srivastava et al., eds., A Survey of Combinatorial Theory, North-Holland, 1973, pp. 117–138:

• primary PDF.

On printed page 124 Erdős asks for many \(a_i<n\) for which \(pa_i=m\) has at most two solutions, records Ruzsa's positive-density construction inside \((n/2,n)\), states the incidence inequality numbered (4.5), and writes, “I do not know whether (4.5) can be improved.” Ruzsa's interval construction is not by itself a reciprocal-mass lower construction over all of \([1,N]\).

The hypergraph obstruction in published work

On the squarefree \(k\)-prime-factor layer, the cap-two problem is the \(H_3^k\) Turán problem: an \(H_3^k\)-free \(k\)-graph has at most two facets inside every \((k+1)\)-set.

The following papers were opened and their identifiers and quoted bounds were checked:

1. (b) Alexander Sidorenko, [“Turán numbers of \(r\)-graphs on \(r+1\)

vertices,” arXiv:2205.02006](https://arxiv.org/abs/2205.02006), published in J. Combin. Theory Ser. B 169 (2024), 150–160, DOI 10.1016/j.jctb.2024.06.004. It proves \(\pi(H_3^r)\ge r^{-2}\) for every \(r\), and \(\pi(H_3^r)\ge(1.7215-o(1))r^{-2}\), while recording the general upper bound \(\pi(H_3^r)\le1/r\).

1. (b) Felix Christian Clemen, [“Applications of Sparse Hypergraph

Colorings,” arXiv:2406.01499](https://arxiv.org/abs/2406.01499), improves the lower bound to \(\pi(H_3^r)=\Omega(r^{-2}\sqrt{\log r})\).

Consequently the elementary \(\Omega(1/k)\) palette proved below closes a substantial published order gap for this Turán problem. Exact-title, exact formula, citation, and problem-wording searches found no primary paper that already gives this palette or directly resolves problem 538. That is a search miss, not a novelty certification.

A third-party claimed proof found after the status gate

(d) Provenance and machine audit. A broader web search found a recent third-party page, “Erdős Problem #538: the matching-order bound”, claiming the fixed-\(r\) result and providing a Lean bundle. This claim is not present in the newest indexed first-party tracker state, so it did not trigger the page-defined stop rule. It is nevertheless essential provenance: the safe-isotropic-kernel construction in Sections 4–6 below comes from that artifact and is not claimed as original here.

I downloaded https://www.starfleetmath.com/downloads/verify/erdos-538/erdos-538-solution.zip. Its SHA-256 was

f8af3e5c118ebb6fb9bbaba6845b0d4a9f7f46d554c555eacdf66ad1fcbf367b

I then performed a cold build, rather than trusting the website transcript:

• Lean 4.31.0;
• mathlib commit

fabf563a7c95a166b8d7b6efca11c8b4dc9d911f;

• lake build: success, 8,597 jobs;
• `lake env lean

../../../../verified_math/F-080_final-matching-order/Proof.lean`: success;

• source scan: no sorry, admit, or local axiom declaration (the words

occur only in comments);

• #print axioms Erdos538.erdos538_matching_order:

[propext, Classical.choice, Quot.sound].

The bundle's definitions quantify over exactly the pairs \((p,a)\) in the page statement and use the rational mass \(\sum1/a\). Its checked theorem gives, for all \(r,N\ge2\),

for every admissible \(A\), and a cap-two (hence cap-\(r\)) witness with

in the precise floor-valued Lean formulation. This rigorously certifies the fixed-\(r\) order.

The uniform-in-\(r\) packing lemma in Section 7 is an additional argument in this report; it is not part of that final Lean theorem. Its proof is elementary, and its arithmetic is independently exercised by the standalone Python checker.

3. The finite upper bound

For an admissible \(A\), let

The original condition gives \(R_A(m)\le r\). Therefore

Also \(\sum_{a\in A}1/a\le H_N\). This proves the upper half of (2) and is (a) elementary-rigorous. Mertens' theorem then gives the upper half of (1), (b).

4. A dense cap-two palette

Palette lemma

Lemma (b, using Bertrand only for the choice of field). For every \(k\ge2\), there is a family \(\mathcal F_k\) of \(k\)-subsets of a set of

colors such that

and every \((k+1)\)-set has at most two facets in \(\mathcal F_k\).

Everything after the choice of a prime is (a). By Bertrand's postulate choose an odd prime

Put \(d=k-1\), and independently label each of the \(M\) color vertices \(v\) by

For a \(k\)-set \(S\), define

Select \(S\) when all of the following hold:

1. \(R_S:\mathbb F_q^S\to\mathbb F_q^d\) is onto, so its kernel is a line.
2. A generator \(\lambda\) of that line has all coordinates nonzero.
3. \(B_S(\lambda,\lambda)=0\), and \((c_v)_{v\in S}\ne0\).
4. For every outside vertex \(y\), the restriction of the diagonal form

\(B_{S\cup\{y\}}\) to \(\ker R_{S\cup\{y\}}\) is not identically zero.

These conditions are independent of the scalar chosen for \(\lambda\).

Why the cap is two

This is (a) elementary-rigorous. Suppose a parent \(T\), \(|T|=k+1\), had three selected facets, omitting distinct \(x,y,z\). Since one selected facet already spans \(\mathbb F_q^d\), the parent relation space \(\ker R_T\) is two-dimensional. Each selected facet supplies an isotropic line in this plane whose unique zero coordinate is its omitted vertex. The three lines are distinct.

Let \(u,v\) generate two of them and write a generator of the third as \(w=au+bv\). The unique-zero property gives \(a,b\ne0\). Since the form is symmetric and the characteristic is odd,

Thus \(B(u,v)=0\), so \(B\) vanishes on the entire parent relation plane. This contradicts the safety condition of any selected facet. Hence at most two facets are selected.

Exact density count

This is (a) elementary-rigorous. Fix an ordering of a prospective child and distinguish one coordinate. The following parameters generate distinct favorable child labelings:

• choose a normalized full-support relation

\(\lambda=(1,\lambda_1,\ldots,\lambda_d)\): \((q-1)^d\) choices;

• choose an ordered basis \(b_1,\ldots,b_d\) of \(\mathbb F_q^d\):

\(\prod_{i=0}^{d-1}(q^d-q^i)\) choices;

• put \(x_0=-\sum_i\lambda_i b_i\), \(x_i=b_i\);
• choose a nonzero coefficient vector \(c\) satisfying

\(c_0+\sum_{i=1}^d c_i\lambda_i^2=0\): \(q^d-1\) choices.

The generated rows reveal the basis, linear independence then recovers \(\lambda\), and the labels reveal \(c\), so this parameterisation is injective. Among the \(q^{(d+1)^2}\) child labelings, the favorable proportion is at least

Indeed, the three displayed factors are respectively at least \(1/2,1/2,\) and \(1/(2q)\), using \(q\ge2(d+1)\) and \(\prod(1-u_i)\ge1-\sum u_i\).

For a fixed favorable child, express an outside row uniquely as \(x_y=\sum_i a_i b_i\), and call its coefficient \(\gamma\). The parent relation plane is spanned by the child relation and the relation having outside coordinate \(1\) and basis coordinates \(-a_i\). Total isotropy requires

The first functional is nonzero: otherwise every \(c_i\) with \(i\ge1\) vanishes, and child isotropy forces \(c_0=0\), contrary to \(c\ne0\). Thus (5) has exactly \(q^{d-1}\) solutions among the \(q^{d+1}\) outside labels—a dangerous fraction exactly \(q^{-2}\). The basis-coordinate map \((a_1,\ldots,a_d)\mapsto\sum_i a_ib_i\) is bijective, so this is a count of actual outside labels rather than an overcount by coordinate choices.

There are \(M-k\) outside vertices, and

A union bound retains at least half the outside assignments. Combining this with (4), every fixed child is selected with probability at least \(1/(16q)\). Averaging over global labelings yields a labeling with family density at least \(1/(16q)\ge1/(64k)\), proving (3).

5. Weighted extraction on an arbitrary layer

Weighted palette lemma (a). Let \(\mathcal L\) be any finite weighted family of \(k\)-subsets, \(k\ge2\), with nonnegative weight \(w\). It has a subfamily \(\mathcal B\) such that every \((k+1)\)-set contains at most two members of \(\mathcal B\), and

Color the ground vertices independently and uniformly with the \(M=2k^2\) palette colors. A fixed \(k\)-set is rainbow with probability

Conditional on being rainbow, its color set is uniform among the \(\binom Mk\) color \(k\)-sets. Select it if that color set lies in \(\mathcal F_k\). By (3), its selection probability is at least \(1/(128k)\); expectation gives a coloring attaining (6).

The cap remains two even when the parent is not rainbow. If deleting one point from a color multiset makes it rainbow, the parent multiset has exactly one repeated pair, and only the two members of that pair can be deleted. Thus there are at most two potentially selected facets.

6. Transfer to squarefree integers

Let

weighted by \(1/a\). Identify \(a\) with its set of prime divisors. Applying (6) gives a subfamily \(B_k\subseteq\mathcal L_k(N)\) of at least a \(1/(128k)\) share of that layer's reciprocal mass and with representation cap two.

This transfer is (a) elementary-rigorous:

• If \(m=pa\) is squarefree, its representations by squarefree \(a\) are

exactly the selected facets of the prime support of \(m\).

• If \(m\) is not squarefree, at most one prime can be removed to leave a

squarefree quotient; otherwise no such representation exists.

• All squarefree quotients \(a\) of a fixed \(m\) have the same

\(\omega(a)\). Therefore unions over distinct \(k\)-layers do not add their representation caps.

7. The uniform cap-\(r\) packing lemma

The third-party artifact takes one cap-two family and hence proves a lower bound independent of \(r\). The following repetition recovers the correct linear dependence until saturation.

Layer packing lemma (a). From any weighted squarefree \(k\)-layer one can retain a fraction at least

while imposing representation cap \(r\).

If \(k<r\), take the entire layer. A squarefree parent has only \(k+1\le r\) facets, and a nonsquarefree product has at most one representation.

If \(k\ge r\), put \(t=\lfloor r/2\rfloor\). Apply (6) successively to the remaining elements, obtaining pairwise disjoint cap-two families \(B_1,\ldots,B_t\). Their union has cap at most \(2t\le r\). With \(x=1/(128k)\), its retained fraction is at least

Bernoulli's inequality applied to \((1-x)^{-t}\) gives

Here \(tx\le1\), and \(t\ge r/3\) for \(r\ge2\), so

proving (7).

For all layers \(1\le k\le K\), (7) consequently retains at least

of their total mass. The union is still cap \(r\), because representations of any fixed product occur in only one squarefree layer.

8. Squarefree harmonic truncation

This section is (a) elementary-rigorous. Let

Writing every \(n\) uniquely as \(n=ab^2\) with \(a\) squarefree gives

The first prime-factor moment satisfies

With \(K=K_N=\lceil4P_N\rceil\), Markov's inequality applied to (10) gives

Removing \(a=1\), (9)–(11) show that the layers \(1\le\omega(a)\le K\) have total mass at least

Apply (8) to (12). This proves the lower half of the finite sandwich (2). Finally, \(H_N=\log N+O(1)\) and Mertens' \(P_N=\log\log N+O(1)\) imply (1). This last asymptotic passage is (b); all preceding truncation inequalities are (a).

9. Exact small cases for \(r=2\)

The standalone checker exhausts all \(2^N\) subsets in Gray-code order, using an exact integer-scaled reciprocal objective. It constructs every product constraint from scratch.

It is enough to enumerate primes \(p\le N\). Indeed, if

are distinct representations and \(g=(a,b)\), unique factorisation gives

after noting that distinct representations force \(p\ne q\). Thus \(p,q\le N\). Hence every collision, and therefore every violation of a cap \(r\ge2\), is present in the finite constraint list. This completeness argument is (a).

The resulting table is (d) computational-only, although each optimum is certified by complete enumeration and each displayed witness is rechecked against all product counts. The optimizer shown need not be unique.

| \(N\) | exact \(M_2(N)\) | one optimizing \(A\) | |---:|---:|:---| | 2 | \(3/2\) | \(1,2\) | | 3 | \(11/6\) | \(1,\ldots,3\) | | 4 | \(25/12\) | \(1,\ldots,4\) | | 5 | \(137/60\) | \(1,\ldots,5\) | | 6 | \(49/20\) | \(1,\ldots,6\) | | 7 | \(363/140\) | \(1,\ldots,7\) | | 8 | \(761/280\) | \(1,\ldots,8\) | | 9 | \(7129/2520\) | \(1,\ldots,9\) | | 10 | \(7381/2520\) | \(1,\ldots,10\) | | 11 | \(83711/27720\) | \(1,\ldots,11\) | | 12 | \(86021/27720\) | \(1,\ldots,12\) | | 13 | \(1145993/360360\) | \(1,\ldots,13\) | | 14 | \(1171733/360360\) | \(1,\ldots,14\) | | 15 | \(1171733/360360\) | \(1,\ldots,14\) | | 16 | \(2388511/720720\) | \(1,\ldots,14,16\) | | 17 | \(41325407/12252240\) | \(1,\ldots,14,16,17\) | | 18 | \(4667343/1361360\) | \(1,\ldots,14,16,17,18\) |

(a) The first obstruction to taking all of \([N]\) occurs at \(N=15\): \(30=2\cdot15=3\cdot10=5\cdot6\). Indeed, three distinct representations require three distinct prime divisors, and the least possible product uses \(2,3,5\); its largest prime quotient is already \(30/2=15\).

10. Independent finite-field certificate

The checker contains 18 raw labels in \(\mathbb F_7^2\times\mathbb F_7\). From those labels alone it:

1. computes relation kernels by modular row reduction;
2. tests the favorable and outside-safety conditions for all

\(\binom{18}{3}=816\) triples;

1. obtains 76 selected triples;
2. checks all \(\binom{18}{4}=3060\) parents; and
3. finds maximum parent multiplicity exactly 2.

This is a concrete (d) certificate for the palette mechanism, much denser than the guaranteed threshold \(\lceil\binom{18}{3}/(64\cdot3)\rceil=5\). It is independent of Lean and of the web artifact: the code implements finite-field linear algebra directly with Python integers.

The checker also verifies exactly, for every \(2\le k\le300\),

• the favorable-count inequality in (4);
• \(2(2k^2-k)\le q^2\) for the first prime \(q>2k\);
• the conversion \(1/(16q)\ge1/(64k)\);

and, for every \(2\le r\le k\le300\), the iteration inequality in (7). It separately recomputes (9)–(12), with exact rational arithmetic, for every \(2\le N\le200\). These range checks are (d) sanity tests, not substitutes for the uniform elementary proofs above.

11. Reproduction

Run:

python3 runs/erdos538_wave9p_reverify.py --max-n 18

The verifier uses only the Python standard library. On this VM it completed in 35.22 seconds (15,092 KB peak RSS) and ended with:

palette k=3 q=7 m=18: selected=76/816, max_parent_facets=2
palette density arithmetic: PASS for 2 <= k <= 300
cap-2 iteration arithmetic: PASS for 2 <= r <= k <= 300
squarefree truncation arithmetic: PASS for 2 <= N <= 200
...
r=2 N=18 optimum=4667343/1361360 witness=(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18)
ALL CHECKS PASS

To search independently for another \(k=3\) palette instead of using the embedded certificate:

python3 runs/erdos538_wave9p_reverify.py --search-palette

(a) The general proof is effective by finite search, but naive exhaustive construction is expensive: enumerating all palette labelings costs \(q^{2k^3}\), and enumerating all colorings of the prime ground set costs \((2k^2)^{\pi(N)}\). No such heavy computation is needed for the existence theorem, and none was run here.

12. Scope and remaining work

• (b) The best possible asymptotic order, with uniform \(r\)-dependence,

is (1).

• (b) The finite quantitative sandwich is (2), with Bertrand's postulate

its only non-elementary input; its upper half is (a).

• (d) Exact finite values are supplied only for \(r=2,\ N\le18\), and one

palette is exhaustively certified at \(k=3\).

• (c) No claim is made about the optimal absolute constants, the exact

pointwise value for general \(r,N\), or historical novelty.

• (d) The official same-day tracker status remains unverifiable until its

planned-maintenance page is removed. The newest first-party indexed state showed no collision; the later third-party fixed-\(r\) artifact was fully credited and independently kernel-checked.

PROVED: modulo Bertrand's postulate and Mertens' prime-reciprocal theorem, \(M_r(N)\asymp\log N\min\{1,r/\log\log N\}\) uniformly for \(r\ge2\); exact finite bounds, a cap-two construction, a cold Lean audit, and a standalone checker are supplied, with the live-tracker maintenance caveat explicit.