Reused writeup on Math-5720 (gpt pro 5.2)
mathematicsErdős problemscontributionManuscript
Contents
Erdős Problem 535 --- collection record
PROVENANCE AND STATUS
Official problem: https://www.erdosproblems.com/535Saved 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/535.tex.
REUSED SOURCE 1
Original attribution:gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/535.tex.Let $r\geq 3$, and let $f_r(N)$ denote the size of the largest subset of $\{1,\ldots,N\}$ such that no subset of size $r$ has the same pairwise greatest common divisor between all elements. Estimate $f_r(N)$. Erdős [Er64] proved that\[f_r(N) \leq N^{\frac{3}{4}+o(1)},\]and Abbott and Hanson [AbHa70] improved this exponent to $1/2$. Erdős [Er64] proved the lower bound\[f_3(N) > N^{\frac{c}{\log\log N}}\]for some constant $c>0$, and conjectured this should also be an upper bound. Erdős writes this is 'intimately connected' with the sunflower problem [20] . Indeed, the conjectured upper bound would follow from the following stronger version of the sunflower problem: estimate the size of the largest set of integers $A$ such that $\omega(n)=k$ for all $n\in A$ and there does not exist $a_1,\ldots,a_r\in A$ and an integer $d$ such that $(a_i,a_j)=d$ for all $i\neq j$ and $(a_i/d,d)=1$ for all $i$. The conjectured upper bound for $f_r(N)$ would follow if the size of such an $A$ must be at most $c_r^k$. The original sunflower proof of Erdős and Rado gives the upper bound $c_r^kk!$. See also [536] . References [AbHa70] Abbott, H. L. and Hanson, D., An extremal problem in number theory . Bull. London Math. Soc. $1970$, 324-326. [Er64] Erdős, P., On a problem in elementary number theory and a combinatorial problem . Math. Comp. $1964$, 644-646.
FORMAL RESTATEMENT
Fix an integer $r\ge 3$ and $N\ge 1$. For a set $A\subseteq [N]:=\{1,2,\dots,N\}$, say that an $r$-tuple of distinct elements $\{a_1,\dots,a_r\}\subseteq A$ is pairwise-gcd-constant if there exists an integer $d\ge 1$ such that \[ \gcd(a_i,a_j)=d\qquad\text{for all }1\le i<j\le r. \] Define $f_r(N)$ to be the maximum size of a subset $A\subseteq [N]$ that contains no pairwise-gcd-constant $r$-subset. The problem asks for the asymptotic order of $f_r(N)$ as $N\to\infty$ (for fixed $r$).QUICK LITERATURE/CONTEXT CHECK
The statement records upper bounds from [Er64,AbHa70] and a lower bound for $r=3$ from [Er64], plus a connection to sunflower-type configurations. Per the integrity rule I do not use any additional external results.ATTACK PLAN
Proof-track ideas. Characterize forbidden configurations in terms of multiplicative structure: if all pairwise gcds equal $d$, then dividing by $d$ should produce pairwise coprime numbers. Use this to connect the condition to sunflower-like patterns in prime supports.Disproof-track ideas. Construct large sets avoiding the forbidden pattern, e.g. by forcing strong divisibility chains (so different pairs have different gcds), or by restricting prime factor patterns.
WORK
- There exists $d\ge 1$ such that $\gcd(a_i,a_j)=d$ for all $i\ne j$.
- There exists $d\ge 1$ and integers $b_1,\dots,b_r\ge 1$ such that $a_i=db_i$ for all $i$, the $b_i$ are pairwise coprime (i.e. $\gcd(b_i,b_j)=1$ for $i\ne j$), and additionally $\gcd(b_i,d)=1$ for all $i$.
Now fix $i$ and suppose (for contradiction) that some prime $p$ divides both $b_i$ and $d$. Then $p$ divides $a_i=db_i$ and also $d$. Since $d=\gcd(a_i,a_j)$ for any $j\ne i$, $p$ divides $a_j$ for all $j\ne i$. In particular $p$ divides $a_j/d=b_j$ for all $j\ne i$, contradicting $\gcd(b_i,b_j)=1$. Hence $\gcd(b_i,d)=1$ for all $i$.
$(2)\Rightarrow(1)$: Assume $2$. For $i\ne j$, \[ \gcd(a_i,a_j)=\gcd(db_i,db_j)=d\cdot \gcd(b_i,b_j)=d, \] since $\gcd(b_i,b_j)=1$. ∎
FAST REALITY CHECK (exact computation for $r=3$ and small $N$).
For $r=3$ I computed $f_3(N)$ exactly for all $N\le 50$ by branch-and-bound search over subsets of $[N]$ (the search checks that for every triple $\{a,b,c\}$ in the chosen set, the three values $\gcd(a,b),\gcd(a,c),\gcd(b,c)$ are not all equal). The exact values are:| $N$ | $f_3(N)$ (exact for $N\le 50$) |
| 1 | 1 |
| 2 | 2 |
| 3 | 2 |
| 4 | 3 |
| 5 | 3 |
| 6 | 3 |
| 7 | 3 |
| 8 | 4 |
| 9 | 5 |
| 10 | 5 |
| 11 | 5 |
| 12 | 5 |
| 13 | 5 |
| 14 | 5 |
| 15 | 5 |
| 16 | 6 |
| 17 | 6 |
| 18 | 7 |
| 19 | 7 |
| 20 | 7 |
| 21 | 7 |
| 22 | 7 |
| 23 | 7 |
| 24 | 7 |
| 25 | 7 |
| 26 | 7 |
| 27 | 8 |
| 28 | 8 |
| 29 | 8 |
| 30 | 8 |
| 31 | 8 |
| 32 | 9 |
| 33 | 9 |
| 34 | 9 |
| 35 | 9 |
| 36 | 9 |
| 37 | 9 |
| 38 | 9 |
| 39 | 9 |
| 40 | 9 |
| 41 | 9 |
| 42 | 9 |
| 43 | 9 |
| 44 | 9 |
| 45 | 10 |
| 46 | 10 |
| 47 | 10 |
| 48 | 10 |
| 49 | 11 |
| 50 | 11 |
Example maximum-size sets produced by the search include:
- $N=8$: $A=\{1,2,4,8\}$ (size $4$).
- $N=32$: $A=\{4,8,9,10,15,16,27,30,32\}$ (size $9$).
- $N=50$: $A=\{6,7,10,12,15,20,24,40,45,48,49\}$ (size $11$).
VERIFICATION
- Lemma Lemma (Exact characterization of a forbidden configuration): checked both directions carefully, including the condition $\gcd(b_i,d)=1$ which is necessary (otherwise the pairwise gcd would exceed $d$).
- Lemma Lemma (Divisibility chains give valid sets): verified that any $r\ge 3$ subset contains a triple, so forbidding triples suffices.
- Computation: the search explicitly checks every triple in the candidate set, and the output sets were re-verified by an independent triple-check.
FINAL
UNRESOLVED(i) Strongest proved partial result. Forbidden configurations are exactly those of Lemma Lemma (Exact characterization of a forbidden configuration) (a common factor $d$ times pairwise-coprime quotients also coprime to $d$). This yields an explicit general lower bound $f_r(N)\ge \lfloor \log_2 N\rfloor+1$ via divisibility chains (Lemma Lemma (Divisibility chains give valid sets)). Additionally, $f_3(N)$ was computed exactly for all $N\le 50$.
(ii) First gap (crisp statement). Determine the correct order of magnitude of $f_r(N)$ (for fixed $r$), even up to $N^{o(1)}$ factors, without invoking unproved sunflower-type hypotheses.
(iii) Top 3 next moves. 1. Translate Lemma Lemma (Exact characterization of a forbidden configuration) into a set-system statement about prime supports and attempt to apply sunflower-style arguments directly to these supports. 2. Search for constructions significantly larger than $\log N$ by constraining prime factors in a way that forbids both $d=1$ (pairwise coprime $r$-tuples) and $d>1$ patterns. 3. Extend exact computations for $f_3(N)$ and for $r=4$ to larger $N$ via integer programming to guess growth and identify extremal structure.
(iv) Minimal counterexample structure. A minimal counterexample to Erdős' conjectured upper bound (as stated in the problem text) would be a set $A$ of integers with uniform prime-factor counts and no configuration of the form $a_i=db_i$ with $b_i$ pairwise coprime and $\gcd(b_i,d)=1$ (Lemma Lemma (Exact characterization of a forbidden configuration)); i.e., $A$ behaves like a large family of "almost-disjoint" prime supports without containing an $r$-sunflower.
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.