Erdoes #539 - working report - Erdős Problem a Day

Erdős problem 539 — wave9q

Date: 2026-07-28 (UTC)

Claim labels

(a) elementary-rigorous: proved from first principles below.
(b) rigorous-modulo-named-theorem: quoted from an identified primary source, with the exact source linked.
(c) plausible/structural-unverified: a conjecture, heuristic, or route not proved here.
(d) computational-only: established only in an explicitly finite search space by the standalone checker.

No claim below silently promotes (c) or (d) to a theorem. A label on a theorem or paragraph governs the mathematical claims in that theorem or paragraph.

Step 0: mandatory live-page gate

The first Bright Data request reached the origin but received “Site down for planned maintenance.” A retry through the same residential-browser route succeeded. On 2026-07-28 I then read both the complete live problem page, its LaTeX view, and the complete eight-comment thread, oldest first.

The exact live LaTeX statement is:

Let $h(n)$ be such that, for any set $A\subseteq \mathbb{N}$ of size $n$, the set\[\left\{ \frac{a}{(a,b)}: a,b\in A\right\}\]has size at least $h(n)$. Estimate $h(n)$.

The page cites #539: [Er73,p.125].

Live gate facts, all read directly on 2026-07-28:

The status is OPEN.
The page says “0 claimed proofs for this problem.”
“Currently working on this problem” is None.
“Interested in collaborating” is None.
The page was last edited 15 June 2026 and records eight comments.

Thus none of the mandatory stop conditions is present.

I also read all eight comments. In condensed form, they are:

Vjeko_Kovac (19 Aug 2025): identifies the Granville–Roesler and Holzman–Lev–Pinchasi bounds; the site says this was incorporated.
m-czech (22 May 2026, later edited): proposes the unproved fixed-dimension pattern $E_k=\binom{k}{\lfloor k/2\rfloor}/(2\binom{k}{\lfloor k/2\rfloor}-1)$, then explicitly withdraws the Sperner heuristic as empirically unsupported and stresses that it is only a three-point pattern fit.
m-czech (12 Jun 2026): discusses how the ProofCouncil suspension theorem refutes the uniform $2/3$ fixed-dimensional extrapolation for $k\geq5$, while leaving the pattern fit unproved.
TimG (10 Jun 2026): announces the ProofCouncil bound and links its repository.
StijnC (11 Jun 2026): asks where the self-contained proof is.
Nat Sothanaphan (11 Jun 2026): links the paper.
Nat Sothanaphan (11 Jun 2026): reports no issue in an informal screening, but correctly notes that Lean proves the exponent limit, not the sharper subexponential factor, and flags the unpublished Bollobás–Leader priority issue.
Thomas Bloom (15 Jun 2026): gives a simplified suspension sketch starting from $\{0\}$.

The live page’s explicit “0 claimed proofs” field governs the gate. The ProofCouncil contribution is an incorporated bound that determines the power exponent, not a claimed determination of the exact order.

Verified literature state

(b) Erdős’s source is P. Erdős, “Problems and Results on Combinatorial Number Theory,” A Survey of Combinatorial Theory (1973), pp. 117–138, DOI 10.1016/B978-0-7204-2262-7.50017-X. The live page points specifically to p. 125.
(b) Granville and Roesler, “The Set of Differences of a Given Set,” American Mathematical Monthly 106 (1999), 338–344, DOI 10.2307/2589556, gives the positive-projection reformulation and presents the Erdős–Szemerédi lower bound and Freiman–Lev $n^{2/3}$ construction. An author-hosted paper copy and the author’s publication page were checked.
(b) Holzman, Lev, and Pinchasi, “Projecting Difference Sets on the Positive Orthant,” Combinatorics, Probability and Computing 17 (2008), 681–688, DOI 10.1017/S0963548308009139, proves

\[ |D(F)|\geq (|F|/2)^{2/3}\quad(d=2),\qquad |D(F)|\geq |F|^{3/5}/6\quad(d=3), \] and \[ |D(F)|\geq c|F|^{6/11}/(\log |F|)^{2/11}\quad(d=4). \]

(b) Schmitt, Gehrunger, Dekoninck, Bérczi, Kreitner, Price, and Holmes, “ProofCouncil: An LLM Agent for Solving Open Mathematical Problems,” arXiv:2607.09474, Theorem A.1, proves

\[ \frac{1+\sqrt{8n-7}}2\leq h(n) \leq n^{1/2}\exp(C\sqrt{\log n}) \] for an absolute $C$, and consequently \[ \lim_{n\to\infty}\frac{\log h(n)}{\log n}=\frac12. \] Its §A.2 says precisely that Lean verifies the universal lower bound, fixed-depth upper bounds, and exponent limit; the displayed $n^{1/2}\exp(C\sqrt{\log n})$ bound remains informal (but self-contained) in that paper.

(b, documentary only) A 23 June 2009 Warwick seminar abstract says that joint work of Imre Leader and Béla Bollobás included “a negative answer to the $n^{2/3}$ question.” The 2012 Oxford abstract confirms the topic and joint work. No written proof or precise bound was found, so I do not use this announcement as a theorem.

The current proven power exponent is therefore $1/2$, but the exact order inside the subexponential gap remains open.

Targeted searches for an exact small-$n$ table (using the phrases “cofactor threshold,” “$a/\gcd(a,b)$,” and “positive difference set”) found the formal-conjectures entry and the papers above, but no primary source giving unrestricted exact values. This is a literature search miss, not a claim that the small values below are new.

Reformulation used below

For a finite $A\subset\mathbb Z_{>0}$, write

Q(A)=\{a/\gcd(a,b):a,b\in A\},\qquad h(n)=\min_{|A|=n}|Q(A)|.

For $x\in\mathbb Z^d$, let $x^+$ be its coordinatewise positive part, and for finite $F\subset\mathbb Z^d$ let

D(F)=\{(x-y)^+:x,y\in F\}.

(a) Exponent-vector bridge. One has

h(n)=\min_{\substack{d\geq1\\F\subset\mathbb Z^d,\ |F|=n}}|D(F)|.

Indeed, if $p_1,\ldots,p_d$ are the primes supporting $A$, unique factorization sends $a$ to its valuation vector $v(a)$ and gives

v(a/\gcd(a,b))=(v(a)-v(b))^+.

Conversely, translate any finite $F\subset\mathbb Z^d$ into $\mathbb Z_{\geq0}^d$ and encode $x$ as $\prod_i p_i^{x_i}$. Translation leaves $D(F)$ unchanged, and unique factorization gives the reverse equality.

Result 1: the exact unrestricted values $h(1),\ldots,h(4)$

Universal elementary lower bound

(a) If $F\subset\mathbb Z^d$ has $n$ elements, then

|F-F|\geq2n-1.

Choose an integer linear functional $L$ injective on $F$. If $L(F)=\{s_1<\cdots<s_n\}$, then $L(F-F)$ contains the $2n-1$ distinct values

s_1-s_n,\ldots,s_n-s_n,s_n-s_{n-1},\ldots,s_n-s_1.

Put $q=|D(F)|$. Since

\[ x-y=(x-y)^+-(y-x)^+, \]

we have $F-F\subseteq D(F)-D(F)$. A $q$-element set has at most $q(q-1)+1$ differences, so

q(q-1)\geq2n-2. \tag{1}

This is also Proposition A.4 of the ProofCouncil paper, but the argument above is complete.

For $n=1,2,3$, (1) gives $q\geq n$. The one-prime chain

A_n=\{2^0,2^1,\ldots,2^{n-1}\}

has $Q(A_n)=A_n$, proving $h(n)=n$ for $n=1,2,3$.

The exceptional $n=4$ argument

(a) Theorem.

h(1)=1,\qquad h(2)=2,\qquad h(3)=3,\qquad h(4)=4.

Only $h(4)\geq4$ remains. Suppose instead that $|F|=4$ and $q=|D(F)|\leq3$. Bound (1) forces $q=3$, and then

7\leq|F-F|\leq|D(F)-D(F)|\leq7.

All inequalities are equalities.

Choose an integer linear functional $L$ injective on the finite set $F-F$. Then $B=L(F)$ is a four-element integer set with $|B-B|=7$. A four-element subset of $\mathbb Z$ with only three positive differences is an arithmetic progression: after writing its successive gaps as $r,s,t>0$, the three strictly increasing differences from the least element already exhaust the three positive differences $r,r+s,r+s+t$. Hence $s=r$. Next $t$ is either $r$ or $r+s=2r$; the latter would make $s+t=3r$ a fourth positive difference. Thus $t=r$.

Order $F=\{x_0,x_1,x_2,x_3\}$ according to this progression. The three vectors $x_{i+1}-x_i$ have the same $L$-image; injectivity of $L$ on $F-F$ makes them equal. Thus

F=\{x,x+v,x+2v,x+3v\}

for some nonzero $v$.

Let $p=v^+$ and $m=(-v)^+$. Directly,

D(F)=\{0,p,2p,3p,m,2m,3m\}.

If one of $p,m$ is zero, this set has four elements. If both are nonzero, they have disjoint supports and the displayed set has seven elements. Either way $|D(F)|\geq4$, a contradiction. The chain $\{1,2,4,8\}$ gives the matching upper bound.

Result 2: a closed finite construction

(a) Theorem (deleted opposite corners). Let $d\geq1$, $m\geq2$, let $p_1,\ldots,p_d$ be distinct primes, and set

F_{d,m}=\{0,\ldots,m\}^d\setminus\{(0,\ldots,0),(m,\ldots,m)\},

A_{d,m}=\left\{\prod_{i=1}^d p_i^{x_i}:x\in F_{d,m}\right\}.

Then

|A_{d,m}|=(m+1)^d-2

and, exactly,

|Q(A_{d,m})|=(m+1)^d-(d+1)=|A_{d,m}|-d+1. \tag{2}

Consequently,

h\big((m+1)^d-2\big)\leq(m+1)^d-(d+1). \tag{3}

Proof. By the exponent-vector bridge it suffices to compute $D(F_{d,m})$. Put $M=(m,\ldots,m)$. Every positive difference lies in $C=\{0,\ldots,m\}^d$.

The $d+1$ vectors

M,\quad M-e_1,\ldots,M-e_d \tag{4}

are absent. The vector $M$ could only come from the deleted ordered pair $(M,0)$. Because $m\geq2$, every coordinate of $M-e_i$ is positive; its only two possible pairs $x-y=M-e_i$ have either $y=0$ or $x=M$, so one endpoint is deleted.

Conversely, fix $u\in C$ not listed in (4). The box

B_u=\{y\in C:y+u\in C\}

has

|B_u|=\prod_i(m-u_i+1).

This product is $1$ exactly for $u=M$, and $2$ exactly for one of the vectors $M-e_i$. Otherwise it is at least $3$, so choose $y\in B_u$ different from both $0$ and $M-u$. Then $y,y+u\in F_{d,m}$ and

\[ ((y+u)-y)^+=u. \]

Thus $D(F_{d,m})$ is exactly $C$ minus the $d+1$ vectors (4). Counting and applying the bridge proves (2)–(3). $\square$

The first nontrivial instance is $d=m=2$:

A=\{2,3,4,6,9,12,18\},\qquad Q(A)=\{1,2,3,4,6,9\}. \tag{5}

Hence (a) $h(7)\leq6$. This is an explicit, hand-checkable counterexample to the tempting inequality $|Q(A)|\geq|A|$. It is not claimed to improve the known asymptotic bounds.

Result 3: exact bounded-grid computation

(d) I exhaustively enumerated all $2^9-1=511$ nonempty subsets $F\subseteq\{0,1,2\}^2$. For each subset the code recomputed all ordered positive differences. If

g(n)=\min_{\substack{F\subseteq\{0,1,2\}^2\\|F|=n}}|D(F)|,

the exact finite table is

| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |---:|---:|---:|---:|---:|---:|---:|---:|---:|---:| | $g(n)$ | 1 | 2 | 3 | 4 | 5 | 6 | 6 | 8 | 9 |

The $n=7$ minimizer found by the fixed lexicographic enumeration is precisely $F_{2,2}$, giving (5).

This table is not a table of unrestricted $h(n)$. It is an exact table only for subsets of this nine-point exponent grid (equivalently, subsets of the divisors of $36$).

Reproduction and independent checks

The standalone checker is runs/erdos539_wave9q_verify.py. Run:

python runs/erdos539_wave9q_verify.py

It uses only the Python standard library and performs independent computations in both formulations:

ordered vector positive differences;
integer gcd/cofactor sets;
decoding cofactors back into prime valuations;
full pair enumeration for twelve $(d,m)$ instances of (2);
all 511 subsets for the bounded-grid table;
the one-prime witnesses and all sign cases in the $h(4)$ proof.

The observed output was:

PASS: all independent Erdős 539 checks completed
deleted-corners parameter pairs checked: [(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)]
A_7 = [2, 3, 4, 6, 9, 12, 18]
Q(A_7) = [1, 2, 3, 4, 6, 9]
universal lower-bound q for n=1..12: {1: 1, 2: 2, 3: 3, 4: 3, 5: 4, 6: 4, 7: 4, 8: 5, 9: 5, 10: 5, 11: 5, 12: 6}
exact minima over nonempty F subset {0,1,2}^2: {1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 6, 8: 8, 9: 9}
raw (n,q)=(7,5) label assignments and idealized core-hours: 227373675443232059478759765625, 6.316e+17
scope: the last table is bounded-grid computational evidence only

Clean reduction and exact remaining wall

(a) Dimension-reduction lemma. If some $n$-point $F\subset\mathbb Z^d$ has $|D(F)|=q$, then such an example exists in dimension at most

n+q-2. \tag{6}

To prove this, choose at most $n-1$ coordinates that separate the $n$ points of $F$: starting from the one-block partition, every new distinguishing coordinate increases the number of blocks. Choose similarly at most $q-1$ coordinates that separate the elements of $D(F)$, and project to the union of these coordinate sets. Coordinate projection commutes with positive part, so

D(\pi F)=\pi D(F).

Both $F$ and $D(F)$ retain their cardinalities, proving (6).

(a) Combining the proved lower bound, chains, and (5), the unrestricted small cases left by this report are only

4\leq h(5)\leq5,\qquad 4\leq h(6)\leq6,\qquad 4\leq h(7)\leq6. \tag{7}

The exact missing lemma for $h(7)=6$ would be:

Every finite $F\subset\mathbb Z^d$ with $|D(F)|\leq5$ has $|F|\leq6$.

By (6), a counterexample to that lemma need only be sought in dimension at most $10$, but its coordinates are still unbounded. Rank-compressing coordinates is invalid: replacing coordinate values by ranks can split equal differences and increase $|D(F)|$.

(c) A possible complete computational route would enumerate, up to symmetry, the labels of all ordered pairs by at most $q$ candidate vectors and certify feasibility of the resulting nonnegative linear cones, including the disjoint-support constraints for opposite differences.

(a) A naive label enumeration for $(n,q)=(7,5)$ has

5^{7\cdot6}=5^{42}\approx2.27\cdot10^{29}

raw assignments. Even at the unrealistically generous rate of $10^8$ assignments per second this is about $6.32\cdot10^{17}$ core-hours (about $7.21\cdot10^{13}$ core-years), so brute force is not an option. A canonical-signature or small-$q$ structure theorem is required before a certified computation becomes realistic. I did not run a large search.

Finally, (2) is only a finite exact family and is asymptotically much weaker than the ProofCouncil construction. It does not remove the $\exp(O(\sqrt{\log n}))$ factor or provide a stronger general lower bound. The exact asymptotic order of $h(n)$ therefore remains open.

PARTIAL: proved h(1)=1, h(2)=2, h(3)=3, h(4)=4; gave and independently checked an exact family with h((m+1)^d-2) <= (m+1)^d-(d+1), including h(7)<=6, plus the exact 3x3-grid table; the unrestricted asymptotic problem remains open.

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