Reused writeup on Math-843 (gpt pro 5.2)

Erdős Problem 536 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/536

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/536.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/536.tex.

FORMAL RESTATEMENT. Let $\epsilon>0$. Does there exist $N_0(\epsilon)$ such that for all integers $N\ge N_0(\epsilon)$ the following holds?

If $A\subseteq \{1,2,\dots,N\}$ and $|A|\ge \epsilon N$, then there exist distinct $a,b,c\in A$ such that \[ \operatorname{lcm}(a,b)=\operatorname{lcm}(b,c)=\operatorname{lcm}(a,c), \] where $\operatorname{lcm}(x,y)$ denotes the least common multiple.

QUICK LITERATURE/CONTEXT CHECK. The problem statement (in the provided source file) notes: (i) the analogous demand for four elements with all pairwise lcm equal is false (attributed there to Erdős), (ii) there are sketched constructions avoiding the triple-lcm property with $|A|\gg (\log\log N)^{f(N)}\,N/\log N$ for some $f(N)\to\infty$, and (iii) there is a sketched proof for very large densities ($\epsilon>221/225$). In this write-up, I do not use any external results beyond what is stated in the file, and I give self-contained arguments for the partial results below.

ATTACK PLAN. 1) Rephrase the condition $\operatorname{lcm}(a,b)=\operatorname{lcm}(a,c)=\operatorname{lcm}(b,c)$ in $p$-adic terms and obtain a clean structural parametrization. 2) Use the parametrization to search for forced small patterns inside dense $A$. 3) Do brute-force search for small $N$ to see how large a set can be while avoiding the configuration.

WORK. Fast reality check (small $N$). I brute-forced all subsets $A\subseteq\{1,\dots,N\}$ for $3\le N\le 20$ and computed the maximum size of a set avoiding any triple of distinct $a,b,c$ with equal pairwise lcm. The maximum sizes found were: \[ \begin{array}{c|cccccccccccccccccc} N&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\\hline \max|A|&3&4&5&5&6&7&8&9&10&10&11&12&12&13&14&15&16&16 \end{array} \] For example, for $N=20$ an extremal avoiding set of size $16$ is $\{1,4,5,7,8,9,10,11,12,13,14,15,16,17,18,19\}$.

Lemma 536.1 (prime-exponent characterization). Let $a,b,c\in\mathbb N$ be distinct. Write $v_p(x)$ for the $p$-adic valuation. Then \[ \operatorname{lcm}(a,b)=\operatorname{lcm}(a,c)=\operatorname{lcm}(b,c) \] holds if and only if for every prime $p$ the maximum of $\{v_p(a),v_p(b),v_p(c)\}$ is attained by at least two of the three numbers.

Proof. Let $L_{ab}=\operatorname{lcm}(a,b)$, etc. For a prime $p$, \[ v_p(L_{ab})=\max\{v_p(a),v_p(b)\},\quad v_p(L_{ac})=\max\{v_p(a),v_p(c)\},\quad v_p(L_{bc})=\max\{v_p(b),v_p(c)\}. \] Thus $L_{ab}=L_{ac}=L_{bc}$ if and only if for every prime $p$ the three maxima above are equal. Let $\alpha=v_p(a)$, $\beta=v_p(b)$, $\gamma=v_p(c)$, and let $M=\max\{\alpha,\beta,\gamma\}$. If $M$ is attained by only one of $\{\alpha,\beta,\gamma\}$, say $\alpha=M>\beta,\gamma$, then $\max\{\beta,\gamma\}<M$ and therefore $v_p(L_{bc})<v_p(L_{ab})$, so equality of lcms fails. Conversely, if $M$ is attained by at least two among $\alpha,\beta,\gamma$, then every pair has maximum exponent $M$ and hence $v_p(L_{ab})=v_p(L_{ac})=v_p(L_{bc})=M$. Since this holds for every prime $p$, the lemma follows. $\square$

Lemma 536.2 (structural parametrization). For $a,b,c\in\mathbb N$ distinct, the condition $\operatorname{lcm}(a,b)=\operatorname{lcm}(a,c)=\operatorname{lcm}(b,c)$ holds if and only if there exist integers $d,u,v,w\in\mathbb N$ with \[ \gcd(u,v)=\gcd(u,w)=\gcd(v,w)=1 \] (symmetric pairwise coprimality) such that, up to permuting $a,b,c$, \[ (a,b,c)=(d\,u v,\ d\,u w,\ d\,v w). \] In that case the common value of the three pairwise lcms is $d\,u v w$.

Proof. ($\Leftarrow$) Assume $a=d u v$, $b=d u w$, $c=d v w$ with pairwise coprime $u,v,w$. Then \[ \operatorname{lcm}(a,b)=\operatorname{lcm}(d u v, d u w)=d u\,\operatorname{lcm}(v,w). \] Because $\gcd(v,w)=1$, $\operatorname{lcm}(v,w)=vw$, so $\operatorname{lcm}(a,b)=d u v w$. Similarly, $\operatorname{lcm}(a,c)=d v\,\operatorname{lcm}(u,w)=d u v w$ and $\operatorname{lcm}(b,c)=d w\,\operatorname{lcm}(u,v)=d u v w$.

($\Rightarrow$) Assume the triple-lcm condition holds. Let $d=\gcd(a,b,c)$ and write $a=d a_1$, $b=d b_1$, $c=d c_1$ so that $\gcd(a_1,b_1,c_1)=1$. Using $\operatorname{lcm}(d x, d y)=d\,\operatorname{lcm}(x,y)$, the pairwise-lcm equality for $(a,b,c)$ is equivalent to the same equality for $(a_1,b_1,c_1)$.

Fix a prime $p$ and set $\alpha=v_p(a_1)$, $\beta=v_p(b_1)$, $\gamma=v_p(c_1)$. Since $\gcd(a_1,b_1,c_1)=1$, at least one of $\alpha,\beta,\gamma$ is $0$. By Lemma 536.1, the maximum of $\{\alpha,\beta,\gamma\}$ is attained at least twice. Therefore for each prime $p$ there are only two possibilities: (i) $\alpha=\beta=\gamma=0$ (so $p$ divides none of $a_1,b_1,c_1$), or (ii) exactly two of $\alpha,\beta,\gamma$ are equal and positive, and the third is $0$. In case (ii), $p$ divides exactly two of the numbers $a_1,b_1,c_1$ with the same exponent.

Define \begin{align*} u &= \prod_{p: v_p(a_1)>0,\ v_p(b_1)>0} p^{v_p(a_1)} ,\\ v &= \prod_{p: v_p(a_1)>0,\ v_p(c_1)>0} p^{v_p(a_1)} ,\\ w &= \prod_{p: v_p(b_1)>0,\ v_p(c_1)>0} p^{v_p(b_1)}. \end{align*} These products are over disjoint sets of primes because a prime cannot divide all three of $a_1,b_1,c_1$ (that would contradict $\gcd(a_1,b_1,c_1)=1$). Hence $u,v,w$ are pairwise coprime. Moreover, every prime dividing $a_1$ divides either $b_1$ or $c_1$ (again by the classification above), so $a_1$ factors exactly as the product of primes shared with $b_1$ (which contribute to $u$) and primes shared with $c_1$ (which contribute to $v$). Thus $a_1=uv$. Similarly $b_1=uw$ and $c_1=vw$. Therefore $(a,b,c)=(d u v, d u w, d v w)$. Finally, the lcm computation in the first direction gives the common lcm value $d u v w$. $\square$

Proposition 536.3 (a high-density sufficient condition). Let $A\subseteq\{1,\dots,N\}$ and set $M=\lfloor N/6\rfloor$. If \[ M>3\,(N-|A|), \] (equivalently, $N-|A|<M/3$), then there exist distinct $a,b,c\in A$ with equal pairwise lcm.

Proof. Consider the parametrized family of triples \[ (2d,3d,6d)\qquad (1\le d\le M). \] Each such triple satisfies $\operatorname{lcm}(2d,3d)=\operatorname{lcm}(2d,6d)=\operatorname{lcm}(3d,6d)=6d$. So it suffices to show that for some $d\le M$ all three numbers $2d,3d,6d$ lie in $A$.

Define the bad sets \[ B_2=\{d\in\{1,\dots,M\}:2d\notin A\},\quad B_3=\{d\in\{1,\dots,M\}:3d\notin A\},\quad B_6=\{d\in\{1,\dots,M\}:6d\notin A\}. \] If no $d$ works, then every $d\in\{1,\dots,M\}$ lies in $B_2\cup B_3\cup B_6$, hence \[ M\le |B_2|+|B_3|+|B_6|. \] For each $t\in\{2,3,6\}$, the map $d\mapsto td$ is injective on $\{1,\dots,M\}$ and takes values in $\{1,\dots,N\}$. Therefore $|B_t|$ is at most the number of missing elements $N-|A|$. Consequently, \[ M\le |B_2|+|B_3|+|B_6|\le 3(N-|A|), \] contradicting the hypothesis $M>3(N-|A|)$. Hence some $d\le M$ has $2d,3d,6d\in A$, giving the desired triple. $\square$

Remark. Since $M=\lfloor N/6\rfloor\sim N/6$, the condition $M>3(N-|A|)$ holds whenever $|A|>(17/18+o(1))N$. VERIFICATION. Checking Lemma 536.2 on examples. If $u,v,w$ are pairwise coprime and $a=d u v$, $b=d u w$, $c=d v w$, then for any prime $p$ dividing $u$ we have $v_p(a)=v_p(b)=v_p(d)+v_p(u)$ and $v_p(c)=v_p(d)$, so the maximum exponent is attained twice. The same holds for primes dividing $v$ or $w$, and primes dividing $d$ appear in all three. This is consistent with Lemma 536.1.

Sanity check for Proposition 536.3. The obstruction to finding some $(2d,3d,6d)$ fully inside $A$ is that too many of the multiples $2d,3d,6d$ are missing. The proof counts these missing-multiple obstructions and uses only injectivity of $d\mapsto td$.

FINAL.\;UNRESOLVED.

• (i) Strongest proved partial result. Writing $M=\lfloor N/6\rfloor$, if $M>3(N-|A|)$ (equivalently $N-|A|<M/3$; in particular this holds when $|A|>(17/18+o(1))N$), then $A$ contains a triple $\{2d,3d,6d\}$ and hence distinct $a,b,c\in A$ with equal pairwise lcm (Proposition 536.3). Also, Lemma 536.2 gives a complete structural characterization of all triples with pairwise-equal lcm.
• (ii) First gap (crisp statement). Prove (or disprove) that for every fixed $\epsilon>0$ there exists $N_0(\epsilon)$ such that for all $N\ge N_0(\epsilon)$ every $A\subseteq\{1,\dots,N\}$ with $|A|\ge\epsilon N$ contains some triple $(d u v, d u w, d v w)$ with $\gcd(u,v)=\gcd(u,w)=\gcd(v,w)=1$.
• (iii) Top 3 next moves.
  • Prove a density increment statement for the pattern $(2d,3d,6d)$ (or other small $(uv,uw,vw)$ patterns) that works for densities far below $17/18$ by using many patterns simultaneously and a refined counting of missing multiples.
  • Develop a hypergraph formulation: view each $d$ as defining a 3-uniform hyperedge $\{2d,3d,6d\}$ and attempt a removal/regularity argument to show that dense $A$ must hit some hyperedge completely.
  • Computationally: for larger $N$ (beyond brute force), implement a heuristic/ILP search for large avoiding sets to guess whether extremal size is $N-o(N)$ or $o(N)$.
• (iv) Minimal counterexample structure to look for. Any counterexample for a fixed $\epsilon>0$ would have to avoid all parametrized triples $(d u v, d u w, d v w)$ with pairwise coprime $u,v,w$, in particular avoiding the infinite family $(2d,3d,6d)$; thus it must delete at least one element from each triple $(2d,3d,6d)$ for $d\le N/6$, and similarly from each triple $(uvd,uwd,vwd)$ for many small coprime $(u,v,w)$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.