Erdős Problem #538: the matching-order bound

The problem and why it is hard

For fixed $r\ge 2$, let $A\subseteq\{1,\dots,N\}$ satisfy the condition that every integer $m$ has at most $r$ representations

$$m=pa,$$

with $p$ prime and $a\in A$. The problem asks for the best possible upper bound on

$$S(A)=\sum_{a\in A}\frac1a.$$

A weighted incidence count gives the natural upper scale

$$S(A)=O_r\!\left(\frac{\log N}{\log\log N}\right).$$

The difficulty was proving that this scale is attainable. On a squarefree layer with exactly $k$ prime factors, write an integer as its $k$-element set of prime divisors. The representation condition becomes a hypergraph condition: among the $k+1$ facets of every $(k+1)$-set, at most $r$ may be selected. For $r=2$, this is the $H_3^k$ daisy problem.

The elementary upper density is of order $1/k$, but previously available general constructions were only around $1/k^2$, up to logarithmic improvements. That missing factor of $k$ became exactly the missing factor of $\log\log N$ in the number-theoretic problem.

Where the standard approaches stalled

Many natural constructions impose a checksum, coloring, or deletion code on each $k$-set. They generally need two independent rare events:

• enough distinct colors to identify a deleted coordinate; and
• a checksum or syndrome condition to limit the number of accepted facets.

Each event costs roughly $1/k$, leaving density $1/k^2$. We verified this obstruction for the balanced rainbow-checksum template and saw the same scale recur in extensive experiments with rooted trees, tries, permutations, cyclic orders, tournaments, Pfaffians, ordered words, and singular matrices.

The broader issue is that generic hypergraph coloring treats forbidden triples as unrelated local constraints. It throws away the decisive geometry: all facets of one parent live in a single two-dimensional relation space. The successful construction had to control that entire parent space at once rather than attach an almost-independent syndrome to each child.

Arithmetic detours did not remove the obstruction. Prime reciprocal weights, the product cutoff $a\le N$, and nonsquarefree exponent cores all reduce back to the same daisy coefficient under weighted blow-ups or square-kernel decomposition. The real bottleneck was genuinely combinatorial.

The key insight: safe isotropic kernels

Fix $k=d+1$ and an odd finite field $K=\mathbb F_q$, with $q$ comparable to $k$. Label each ground vertex $v$ by

$$(\phi_v,c_v)\in K^d\times K.$$

For a $k$-set $S$, define

$$\Psi_S(\lambda)=\sum_{v\in S}\lambda_v\phi_v, \qquad B_S(\lambda,\mu)=\sum_{v\in S}c_v\lambda_v\mu_v.$$

Call $S$ favorable when:

• $\Psi_S$ is surjective, so its relation space is a line;
• a generator $\lambda$ of that line has full support;
• $B_S(\lambda,\lambda)=0$; and
• the coefficient vector $(c_v)_{v\in S}$ is nonzero.

A favorable child is called safe if no outside vertex extends it to a parent whose two-dimensional relation space is totally isotropic for the same diagonal bilinear form.

Why the family has cap two

Consider a $(k+1)$-set $T$. A selected facet missing $x$ contributes an isotropic relation in the parent relation space whose unique zero coordinate is $x$. Full support makes the relation lines from distinct selected facets distinct.

One selected facet already forces the parent relation space to be two-dimensional. If three facets were selected, that plane would contain three distinct isotropic lines. For a symmetric bilinear form in odd characteristic, three such lines force the form to vanish identically: if $u,v$ are two isotropic generators and $w=au+bv$ is a third distinct isotropic line, then $a,b\ne0$ and

$$0=B(w,w)=2abB(u,v),$$

so $B(u,v)=0$ as well. The whole plane is therefore totally isotropic, contradicting the safety condition. Thus every parent contains at most two selected facets.

Why the density is $\Omega(1/k)$

The favorable samples admit an injective finite-field parameterization. Its exact cardinality is

$$(q-1)^d \left(\prod_{i=0}^{d-1}(q^d-q^i)\right) (q^d-1).$$

When $q\ge 2k$, this gives favorable density at least $1/(8q)$.

After a favorable child is fixed, one outside label makes its parent relation plane totally isotropic only when two equations hold: one nonzero linear equation and one uniquely determined scalar equation. The dangerous fraction is exactly

$$\frac1{q^2}.$$

On a ground set with $2(m-k)\le q^2$, a union bound leaves at least half of the outside assignments safe. Averaging over all global labelings therefore yields a cap-two family of density at least $1/(16q)$.

Bertrand's postulate supplies an odd prime $2k<p\le4k$. Taking $q=p$ and $m=2k^2$ gives, for every $k\ge2$, a cap-two $k$-uniform family of density at least

$$\frac1{64k}.$$

This closes the daisy density gap at the order needed here.

Returning to the integers

A weighted coloring argument transfers the palette to any exact squarefree $k$-prime-factor layer. First, color prime supports into $2k^2$ colors so that at least half of the reciprocal weight is rainbow. Then average over permutations of the colors so that at least a $1/(64k)$ fraction of that rainbow weight lands in the safe-kernel palette.

The resulting integer subfamily retains at least

$$\frac1{128k}$$

of the reciprocal mass of that layer and satisfies the original representation cap two. Repeated colors do not create a hidden multiplicity problem: in a non-rainbow parent, at most the two occurrences in the unique repeated pair can yield rainbow facets.

Exact prime-factor layers can be united without adding their representation caps, because all representations of a fixed $m$ come from one $\Omega$-layer. Truncating at $K\asymp\log\log N$, and using the squarefree harmonic-mass and first-moment estimates, gives an admissible cap-two family satisfying the explicit inequality

$$\log(N+1) \le 4+8192\bigl(1+\lfloor\log_2\lfloor\log_2N\rfloor\rfloor\bigr)S(A).$$

Thus

$$S(A)=\Omega\!\left(\frac{\log N}{\log\log N}\right).$$

Together with the incidence upper bound, the best possible order for every fixed $r\ge2$ is

$$\boxed{\Theta_r\!\left(\frac{\log N}{\log\log N}\right)}.$$

Verification

The entire argument was formalized in Lean 4 with Mathlib. The final theorem uses the exact audited definitions of:

• a finite set $A\subseteq[1,N]$;
• every solution pair $(p,a)$ to $m=pa$;
• the universal cap over every $m$; and
• the rational reciprocal mass $\sum_{a\in A}1/a$.

The verified chain includes the finite-field counts, injectivity of the favorable parameterization, the exact $1/q^2$ danger fraction, the parent cap, weighted relabeling, multiplicity-aware pattern transfer, integer-layer retention, harmonic truncation, and the final upper/lower theorem. The complete Lean project builds successfully, and the copied final artifact verified_math/F-080_final-matching-order/Proof.lean kernel-checks without sorry, admit, or additional axioms.