Erdős Problem #888

Erdős Problem 888: a checked attempt

GPT_6_Astra_Ultra

24 September 2026

Statement and provenance

Let $F(n)$ be the largest size of $A\subseteq[1,n]$ such that, whenever $a\le b\le c\le d$ belong to $A$ and $abcd$ is a square, one has $ad=bc$. Repetitions are permitted. We reconstruct the current order-of-magnitude resolution \[ F(n)\asymp\frac{n\log\log n}{\log n} \] from the April 2026 draft A square-product rigidity problem of Erdős, Sárközy and Sós, linked by the problem page, https://www.ulam.ai/research/erdos888.pdf. The graph and summation arguments are proved below; the standard prime estimates used are stated explicitly.

The lower bound and the repetition convention

Take all primes and all squarefree semiprimes $pq$ with $p<q$, up to $n$. Four primes with square product occur in equal pairs, giving the required identity. For two primes and two semiprimes, either both pairs are repeated, or the numbers are $p,q,pr,qr$; their smallest and largest have the same product as the middle pair. Four semiprimes correspond to four loopless edges on prime vertices. Square product means every vertex has even degree. The multigraph is either a union of doubled edges or a four-cycle. In the latter case the values are $ux,uy,vx,vy$, and again the extreme product equals the middle product. An odd number of prime entries is impossible because the total number of prime factors counted with multiplicity would be odd. This proves rigidity, including repeated entries.

Prime squares must not be included indiscriminately: for example $4,4,4,9$ have square product but $4\cdot9\ne4\cdot4$. The word squarefree above is essential.

For the size lower bound, take $p\le n^{1/3}$ prime and $n/(2p)<q\le n/p$ prime. The prime number theorem gives $\gg n/(p\log n)$ choices for $q$, uniformly in this range, and $q>p$ for large $n$. Distinct pairs give distinct semiprimes. The prime reciprocal estimate $\sum_{p\le x}1/p=\log\log x+O(1)$ therefore gives $\gg n\log\log n/\log n$ elements.

Reduction and an elementary colored-graph estimate

Write $G(n)$ for the maximum restricted to squarefree integers. Every integer is uniquely $k^2s$ with $s$ squarefree. For fixed $k$, dividing the elements of $A$ having this square part by $k^2$ preserves both ordering and the rigidity property. Hence \[ F(n)\le\sum_{k\le\sqrt n}G(\lfloor n/k^2\rfloor).\tag{1} \] If $G(x)\ll x\log\log x/\log x$, the range $k\le n^{1/3}$ in $1$ is bounded by $O(n\log\log n/\log n)\sum k^{-2}$, and the remaining range is at most $n\sum_{k>n^{1/3}}k^{-2}=O(n^{2/3})$. It suffices to prove the squarefree estimate.

A bipartite graph with sides $M\le N$, $e$ edges, and $c_4$ unlabelled rectangles satisfies \[ e\ll N+M\sqrt N+(MN)^{1/2}c_4^{1/4}.\tag{2} \] If $e$ exceeds a sufficiently large constant times $N+M\sqrt N$, convexity first gives at least $\gg e^2/N$ two-edge paths with endpoints on the $M$ side. Distributing these paths among its $\binom M2$ pairs and applying convexity again gives $c_4\gg e^4/(M^2N^2)$. Otherwise the first terms of $2$ suffice.

If $T$ such graphs share the same sides and no rectangle is complete in two colors, their rectangle counts sum to at most $\binom M2\binom N2$. Summing $2$ and applying Hölder yields \[ \sum e\ll T(N+M\sqrt N)+T^{3/4}MN.\tag{3} \]

Encoding integers by two largest primes

For squarefree $a$ with at least two prime factors, write $a=cpq$, where $p<q$ are its largest two primes. Fix dyadic intervals $X<p\le2X$, $Y<q\le2Y$, $X\le Y$. Color edge $pq$ by $c$. The possible squarefree cores satisfy \[ cXY\le n,\qquad P^+(c)<2X; \] put $T(X,Y)$ for their number. For $X=Y$, a random bipartition of the prime interval retains half the colored edges on average; choose a partition retaining at least this many. Thus we can use bipartite graphs throughout at only a constant loss.

No rectangle is complete in two distinct core colors $c,d$. Otherwise, for four distinct endpoint primes $p,q,r,s$, the set contains $cpr,cqs,dps,dqr$. The endpoints divide neither core: they are all larger than every prime factor of both cores, because each color contains the whole rectangle. These four integers are distinct, their product is a square, and their three possible equal-product pairings would respectively imply $c=d$, $p=q$, or $r=s$. All are impossible. This contradicts rigidity.

Let $L(x)=\log(2+x)$. The standard prime estimate $\pi(x)\ll x/L(x)$ bounds side sizes by $O(X/L(X))$, $O(Y/L(Y))$; swapping sides if necessary preserves these ordered bounds up to absolute constants. Therefore $3$ bounds the block by \[ E(X,Y)\ll T\left(\frac Y{L(Y)}+\frac{X\sqrt Y}{L(X)\sqrt{L(Y)}}\right) +T^{3/4}\frac{XY}{L(X)L(Y)}.\tag{4} \] We now sum all three terms, supplying the smooth-core estimates rather than leaving their uniformity implicit.

The rectangle term

Since $T\le n/(XY)$, this term sums to at most \[ n^{3/4}\sum_{X\le Y,XY\le n}\frac{(XY)^{1/4}}{L(X)L(Y)} \ll n\sum_{X\le\sqrt n}\frac1{L(X)L(n/X)} \ll\frac{n\log\log n}{\log n}.\tag{5} \] All sums here and below are dyadic. The inner $Y$ sum is geometrically dominated by its final scale. For the last inequality put $X=2^j$: its denominator is comparable to $(j+1)(1+\log n-j\log2)$, and $j\le\frac12\log_2n$ gives a harmonic sum divided by $\log n$.

The term linear in the larger side

Interchange the sum over cores and put $\rho(c)=\max(2,P^+(c))$. For fixed $c,X$, summing $Y/L(Y)$ up to $n/(cX)$ gives $\ll n/(cXL(n/(cX)))$. Since $X>P^+(c)/2$ and $X^2\le n/c$, the remaining geometric sum over $X$ is at most \[ \frac{C}{\rho(c)L(n/(c\rho(c)))}. \] Indeed write $X\asymp2^j\rho$; nonemptiness forces $2^j\ll\sqrt{n/(c\rho^2)}$, so the logarithmic denominator stays comparable to its value at the first scale, and $2^{-j}$ is summable. It remains to show \[ \sum_{c\rho(c)^2\le4n}\frac1{c\rho(c)L(n/(c\rho(c)))}\ll\frac1{\log n}.\tag{6} \] The core $1$ is immediate. For $c>1$ write $c=rd$, with $r$ prime and $d$ squarefree having all prime factors below $r$. The summand is $1/(dr^2L(n/(dr^2)))$ and $dr^3\le4n$.

We use the standard consequences of prime estimates \[ \prod_{p<x}(1+1/p)\ll L(x),\qquad \prod_{p<x}p\le e^{C_0x}.\tag{7} \] For $r\le\eta\log n$, with $\eta$ sufficiently small, $d\le e^{C_0r}\le n^{1/3}$, so $L(n/(dr^2))\gg\log n$. Summing $1/d$ using $7$ bounds these terms by $O(1/\log n)\sum_rL(r)/r^2=O(1/\log n)$. For $r>\eta\log n$, the cutoff gives $n/(dr^2)\ge r/4$, hence the denominator is $\gg L(r)$. Equation $7$ cancels that factor, leaving $O(\sum_{r>\eta\log n}r^{-2})=O(1/\log n)$. This proves $6$ and bounds this portion of $4$ by $O(n/\log n)$.

The remaining graph term

Discard $\sqrt{L(Y)}$ from its denominator and put \[ T_0(X)=|\{c\le n/X^2:c\text{ squarefree},\ P^+(c)<2X\}|. \] Since $T(X,Y)\le\min(T_0(X),n/(XY))$, splitting the dyadic $Y$ sum at $n/(XT_0(X))$ gives \[ \sum_Y\min(T_0(X),n/(XY))\sqrt Y\ll\sqrt{nT_0(X)/X}. \] Thus the whole term is at most \[ \sqrt n\sum_{X\le\sqrt n}\frac{\sqrt{XT_0(X)}}{L(X)}.\tag{8} \] For $X\ge(\log n)^4$, use $T_0(X)\le n/X^2$; the resulting geometric tail is $O(n/(\log n)^2)$. For smaller $X$, Rankin's elementary inequality $1_{c\le U}\le(U/c)^{3/4}$ gives \[ T_0(X)\le(n/X^2)^{3/4}\prod_{p<2X}(1+p^{-3/4}) \le n^{3/4+o(1)}X^{-3/2}. \] Here the standard partial-summation estimate $\sum_{p<x}p^{-3/4}\ll x^{1/4}/L(x)$ makes the product at most $\exp(O(\log n/\log\log n))=n^{o(1)}$, uniformly for $X<(\log n)^4$. Substitution in $8$ gives $n^{7/8+o(1)}\sum_X X^{-1/4}/L(X)=o(n/\log n)$, because this dyadic series converges. Thus this final term is also $O(n/\log n)$.

The squarefree element $1$ and the primes contribute only $O(n/\log n)$ additionally. Equations $4$--$8$ prove $G(n)\ll n\log\log n/\log n$, and $1$ completes the upper bound for arbitrary integers.

Assessment

Both bounds and the full colored-rectangle reduction are proved relative only to the stated classical prime-number estimates (prime number theorem, reciprocal-prime estimate, and their elementary consequences). This reconstructs the cited recent resolution; the square-part reduction, repeated entries and uniform smooth-core cutoff are all included explicitly.

Completion rate estimate: 100%.

1) FORMAL RESTATEMENT

For each $n\ge 1$, let $f(n)$ be the maximum size of a set $A\subseteq\{1,2,\dots,n\}$ with the property:

For all $a,b,c,d\in A$ with $a\le b\le c\le d$, if $abcd$ is a perfect square, then $ad=bc$.

Ambiguity note. Because $A$ is a set, elements of $A$ are distinct, but the statement does not explicitly say whether the quadruple $(a,b,c,d)$ is required to consist of four distinct elements of $A$ or whether repetitions are allowed (e.g. $(a,b,b,c)$). The condition as written quantifies over $a,b,c,d\in A$ and allows equality in $a\le b\le c\le d$, so the literal reading allows repetitions. In what follows, I adopt this literal (stronger) reading; any set satisfying it also satisfies the "distinct quadruples only" variant.

The question asks for the asymptotic order of $f(n)$ (e.g. is $f(n)=o(n)$?).

2) QUICK LITERATURE/CONTEXT CHECK

The problem text attributes the question to Erdős--Sárközy--Sós and reports (without proof here) that Erdős claimed Sárközy proved $f(n)=o(n)$. The problem text also notes a lower bound $f(n)\gg n/\log n$ coming from taking $A$ to be the primes.

3) ATTACK PLAN

Proof-direction (upper bounds).

• Convert the condition "$abcd$ square" into parity constraints on prime exponents (squarefree kernels), turning the problem into forbidding certain 4-term relations; try to show this forces sparseness.
• Search for a combinatorial reformulation (hypergraph of forbidden 4-tuples) and apply container-style counting or energy bounds.

Disproof-direction (large constructions).

• Look for multiplicative constructions beyond primes (e.g. numbers with restricted squarefree part) that still avoid nontrivial square quadruples.
• Use computation for moderate $n$ to guess the true growth of $f(n)$ under the intended interpretation.

4) WORK

Lemma 888.1 (Primes give a valid set). Let $A$ be the set of primes $\le n$. Then $A$ satisfies the stated property (both in the "repetitions allowed" and "distinct only" interpretations). Consequently $f(n)\ge \pi(n)$.

Proof. Take $a\le b\le c\le d$ in $A$ (so each is prime) and assume $abcd$ is a perfect square. Write the prime factorization of $abcd$: since $a,b,c,d$ are primes, each of these primes occurs with exponent equal to its multiplicity among $\{a,b,c,d\}$. For $abcd$ to be a square, every prime exponent must be even. Hence every prime appearing among $a,b,c,d$ must appear an even number of times. Because there are four primes total, the multiset $\{a,b,c,d\}$ must be either:

• $\{p,p,p,p\}$ for some prime $p$, or
• $\{p,p,q,q\}$ for two distinct primes $p<q$.

Under the imposed ordering $a\le b\le c\le d$, the second case forces $a=b=p$ and $c=d=q$. In either case we have $ad=bc$ (both sides equal $p^2$ in the first case, and both equal $pq$ in the second). Thus the property holds for all such quadruples, and $|A|=\pi(n)$ gives $f(n)\ge \pi(n)$. $\square$

Lemma 888.2 (Square-product pairs force a geometric mean). Assume $A\subseteq\{1,\dots,n\}$ satisfies the stated property (with repetitions allowed). Let $a,c\in A$ with $a<c$ and suppose $ac$ is a perfect square. Then there is at most one element $b\in A$ with $a<b<c$. Moreover, if such a $b$ exists, then $b^2=ac$ (hence $b=\sqrt{ac}\in\mathbb{N}$).

Proof. Assume $a<c$ are in $A$ and $ac$ is a square. Let $b\in A$ satisfy $a<b<c$. Consider the nondecreasing quadruple $(a,b,b,c)$; it is allowed because repetitions are permitted and $a\le b\le b\le c$. Its product is \[ a\cdot b\cdot b\cdot c = b^2\,(ac). \] Because $b^2$ is a perfect square and $ac$ is assumed to be a perfect square, their product $b^2(ac)$ is a perfect square. Therefore the defining property of $A$ applies and yields \[ a\,c = b\,b = b^2. \] So any such $b$ must equal $\sqrt{ac}$. In particular, there is at most one element of $A$ strictly between $a$ and $c$. $\square$

Fast reality check (computation, literal "repetitions allowed" version). I brute-forced the maximum size $f(n)$ for $n\le 15$ by enumerating all subsets $A\subseteq\{1,\dots,n\}$ and checking the condition for all nondecreasing quadruples $a\le b\le c\le d$ with entries in $A$ (allowing repetitions). The exact maxima found were: \[ \begin{array}{c|ccccccccccccccc} n & 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline f(n) & 1&2&3&3&4&5&6&6&6&7&8&8&9&10&10 \end{array} \] One maximizing example for $n=15$ is \[ A=\{1,2,3,5,6,7,10,11,13,14\},\qquad |A|=10, \] and it was verified directly (by exhaustive quadruple checking) that this $A$ has no violating quadruple.

5) VERIFICATION

Lemma 888.1: the proof uses only unique factorization and the characterization of square integers by even prime exponents.

Lemma 888.2: the key step is that $b^2(ac)$ is a square if and only if $ac$ is a square, because $b^2$ is always a square. Then the defining implication gives $ac=b^2$.

Computation: the brute check tested exactly the implication "if $abcd$ is a square then $ad=bc$" over all nondecreasing quadruples with repetition; this matches the literal interpretation.

6) FINAL

UNRESOLVED

1. (i) Strongest proved partial result here. The set of primes gives a valid construction of size $\pi(n)$ (Lemma 888.1), so $f(n)\ge \pi(n)\gg n/\log n$. Also, if $a,c\in A$ have $ac$ square, then any $b\in A$ with $a<b<c$ is forced to equal $\sqrt{ac}$ (Lemma 888.2).
2. (ii) First gap (crisp). Prove a nontrivial upper bound on $f(n)$ (ideally $f(n)=o(n)$, or any explicit $f(n)\le n/(\log n)^{\delta}$) from the square-quadruple implication.
3. (iii) Top 3 next moves.
   • Reformulate the constraint in terms of squarefree kernels: write each $x\in A$ as $x=s(x)\,t(x)^2$ with $s(x)$ squarefree, and analyze which 4-tuples of $s(x)$ can yield a square product without forcing $ad=bc$.
   • Push the computation to larger $n$ under both interpretations (repetitions allowed vs. distinct quadruples only) to guess the true growth rate and to detect structure in extremal sets.
   • Try to prove that many elements sharing the same squarefree kernel create many square quadruples; quantify this to obtain an upper bound by double counting.
4. (iv) Minimal counterexample structure. To refute $f(n)=o(n)$ one would need a sequence $n_t\to\infty$ and sets $A_t\subseteq\{1,\dots,n_t\}$ with $|A_t|\ge \delta n_t$ for some fixed $\delta>0$ such that every nondecreasing quadruple from $A_t$ with square product satisfies $ad=bc$. Such a construction would have to prevent the "parity cancellations" of prime exponents that normally generate many square products among dense sets.