Erdős Problem #1109

Erdős Problem 1109 --- collection record

PROVENANCE AND STATUS

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

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/1109.tex.

REUSED SOURCE 1

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

FORMAL RESTATEMENT

For a positive integer $N$, let $f(N)$ be the maximum size of a set $A\subseteq\{1,2,\dots,N\}$ such that every element of the sumset \[A+A := \{a+b : a,b\in A\}\] is squarefree (i.e. not divisible by $p^2$ for any prime $p$). The problem asks for estimates on $f(N)$ as $N\to\infty$, and in particular whether one has \[f(N)\le N^{o(1)}\quad\text{or even}\quad f(N)\le (\log N)^{O(1)}. \]

QUICK LITERATURE/CONTEXT CHECK

The problem file states known bounds from the literature: \[\log N \ll f(N) \ll N^{3/4}\log N\] (Erdős--Sárközy), and an improved upper bound $f(N)\ll N^{11/15+o(1)}$ with a lower bound $\log\log N (\log N)^2\ll f(N)$ (Konyagin). I do not use any results not explicitly stated in the problem file.

ATTACK PLAN

Proof-track strategies.

• Derive strong modular restrictions: for each prime $p$, $A+A$ must avoid $0\bmod p^2$, so $A\bmod p^2$ must avoid pairs summing to $0$. Combine these constraints over many primes via a sieve/large-sieve style argument.
• Use additive combinatorics: if $|A|$ is large then $|A+A|$ is typically large; compare with the density of squarefree numbers and the distribution of squarefree numbers in residue classes.
• For lower bounds, attempt constructive sets using the Chinese remainder theorem to force $a+b$ away from $0\bmod p^2$ for many small primes simultaneously.

Disproof-track strategy. Try to build $A$ of size $N^{\delta}$ for some fixed $\delta>0$ by a structured choice of residues mod $\prod_{p\le y} p^2$, and test whether accidental divisibility by larger prime squares can be controlled.

WORK

FAST REALITY CHECK (computation).

I computed the exact value of $f(N)$ for $N\le 40$ by backtracking, using the necessary condition that every $2a\in A+A$ must be squarefree. The values for $N\le 40$ are:

Example maximizing sets found by the search include:

• $N=20$: $A=\{3,7,19\}$ (size $3$).
• $N=30$: $A=\{3,7,19,23\}$ (size $4$).
• $N=40$: $A=\{1,5,29,33,37\}$ (size $5$).

For some larger sample points the same code gave:

• $f(50)=6$ with example $A=\{1,5,29,33,37,41\}$.
• $f(60)=7$ with example $A=\{7,15,19,23,51,55,59\}$.
• $f(80)=7$ with example $A=\{1,5,21,37,41,65,73\}$.
• $f(100)=8$ with example $A=\{5,17,29,41,53,65,77,89\}$.

These values are small-$N$ data only and do not address the asymptotic questions.

Lemma 1109.1 (every element of $A$ is odd and squarefree).

Let $A\subseteq\{1,\dots,N\}$ satisfy that every element of $A+A$ is squarefree. Then every $a\in A$ is odd and squarefree.

Proof.

Fix $a\in A$. Since $a+a=2a\in A+A$, the integer $2a$ is squarefree by hypothesis.

If $a$ were even, then $2a$ would be divisible by $4=2^2$, contradicting squarefreeness. Hence $a$ is odd.

If $a$ were not squarefree, then there exists a prime $p$ such that $p^2\mid a$. Then $p^2\mid 2a$, so $2a$ would not be squarefree, again contradicting the hypothesis. Therefore $a$ is squarefree. $\square$

Lemma 1109.2 (residue-class restriction modulo $p^2$).

Let $A\subseteq\{1,\dots,N\}$ satisfy that every element of $A+A$ is squarefree. Fix a prime $p$. Then:

• No element of $A$ is $0\bmod p^2$.
• For any residue class $x\bmod p^2$, $A$ cannot contain simultaneously an element congruent to $x$ and an element congruent to $-x$ modulo $p^2$.

In particular, if $r$ is the number of residue classes modulo $p^2$ that $A$ meets, then $r\le (p^2-1)/2$, and hence \[|A|\le \frac{p^2-1}{2}\,\left\lceil \frac{N}{p^2}\right\rceil. \]

Proof.

If $a\in A$ satisfies $a\equiv 0\pmod{p^2}$, then $a+a=2a\equiv 0\pmod{p^2}$, so $2a$ is divisible by $p^2$ and therefore not squarefree, contradicting the hypothesis. This proves the first bullet.

For the second bullet, suppose $a,b\in A$ satisfy $a\equiv x\pmod{p^2}$ and $b\equiv -x\pmod{p^2}$. Then $a+b\equiv 0\pmod{p^2}$, so $p^2\mid (a+b)$, implying $a+b$ is not squarefree. But $a+b\in A+A$, contradiction.

Thus among the nonzero residue classes modulo $p^2$, $A$ can use at most one of each pair $\{x,-x\}$. There are $p^2-1$ nonzero classes, giving at most $(p^2-1)/2$ usable classes. Each residue class contributes at most $\lceil N/p^2\rceil$ elements from $\{1,\dots,N\}$, yielding the stated upper bound on $|A|$. $\square$

VERIFICATION

• Lemma 1109.1 uses only the necessary condition that $2a\in A+A$ is squarefree, so it is robust.
• Lemma 1109.2 correctly treats the diagonal case $a=b$: the first bullet excludes $a\equiv 0\pmod{p^2}$, which is exactly the condition needed to prevent $2a$ from being divisible by $p^2$ for odd $p$.
• The brute-force computations restricted candidates to odd squarefree numbers using Lemma 1109.1; this does not discard any feasible maximizing set.

FINAL

UNRESOLVED

(i) Strongest proved partial result. Lemma 1109.1 shows every feasible set $A$ consists of odd squarefree integers. Lemma 1109.2 gives a sharp modular restriction: for each prime $p$, $A\bmod p^2$ avoids pairs $x,-x$ and avoids $0$, yielding the explicit bound $|A|\le \frac{p^2-1}{2}\lceil N/p^2\rceil$.

(ii) First gap. Prove an asymptotic upper bound of the form $f(N)\le N^{o(1)}$ (or $f(N)\le (\log N)^{O(1)}$), or else construct sets $A$ of size $N^{\delta}$ for some fixed $\delta>0$.

(iii) Top 3 next moves. 1. Combine the constraints of Lemma 1109.2 over many primes $p\le y$ using a sieve/large-sieve framework to force $|A|$ to be small. 2. Study the distribution of $A+A$ and use lower bounds on $|A+A|$ (via additive energy or sumset growth) together with upper bounds on how many squarefree numbers can lie in a structured set. 3. Computationally search for extremal sets for larger $N$ (say $N\le 500$) to guess the true growth rate and to detect residue-class patterns mod $p^2$ that good constructions exploit.

(iv) What a minimal counterexample would likely look like. To contradict a polylogarithmic upper bound, a minimal counterexample would be a set $A$ of size $\gg N^{\delta}$ whose residues modulo many small $p^2$ occupy close to $(p^2-1)/2$ allowable classes (from Lemma 1109.2) while still avoiding accidental divisibility by squares of larger primes in all pairwise sums. Such a set would likely have a strong Chinese-remainder structure.

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.

FORMAL RESTATEMENT

For a positive integer $N$, let $f(N)$ be the maximum size of a set $A\subseteq\{1,2,\dots,N\}$ such that every element of the sumset \[A+A := \{a+b : a,b\in A\}\] is squarefree (i.e. not divisible by $p^2$ for any prime $p$). The problem asks for estimates on $f(N)$ as $N\to\infty$, and in particular whether one has \[f(N)\le N^{o(1)}\quad\text{or even}\quad f(N)\le (\log N)^{O(1)}. \]

QUICK LITERATURE/CONTEXT CHECK

The problem file states known bounds from the literature: \[\log N \ll f(N) \ll N^{3/4}\log N\] (Erdős--Sárközy), and an improved upper bound $f(N)\ll N^{11/15+o(1)}$ with a lower bound $\log\log N (\log N)^2\ll f(N)$ (Konyagin). I do not use any results not explicitly stated in the problem file.

ATTACK PLAN

Proof-track strategies.

• Derive strong modular restrictions: for each prime $p$, $A+A$ must avoid $0\bmod p^2$, so $A\bmod p^2$ must avoid pairs summing to $0$. Combine these constraints over many primes via a sieve/large-sieve style argument.
• Use additive combinatorics: if $|A|$ is large then $|A+A|$ is typically large; compare with the density of squarefree numbers and the distribution of squarefree numbers in residue classes.
• For lower bounds, attempt constructive sets using the Chinese remainder theorem to force $a+b$ away from $0\bmod p^2$ for many small primes simultaneously.

Disproof-track strategy. Try to build $A$ of size $N^{\delta}$ for some fixed $\delta>0$ by a structured choice of residues mod $\prod_{p\le y} p^2$, and test whether accidental divisibility by larger prime squares can be controlled.

WORK

FAST REALITY CHECK (computation).

I computed the exact value of $f(N)$ for $N\le 40$ by backtracking, using the necessary condition that every $2a\in A+A$ must be squarefree. The values for $N\le 40$ are:

Example maximizing sets found by the search include:

• $N=20$: $A=\{3,7,19\}$ (size $3$).
• $N=30$: $A=\{3,7,19,23\}$ (size $4$).
• $N=40$: $A=\{1,5,29,33,37\}$ (size $5$).

For some larger sample points the same code gave:

• $f(50)=6$ with example $A=\{1,5,29,33,37,41\}$.
• $f(60)=7$ with example $A=\{7,15,19,23,51,55,59\}$.
• $f(80)=7$ with example $A=\{1,5,21,37,41,65,73\}$.
• $f(100)=8$ with example $A=\{5,17,29,41,53,65,77,89\}$.

These values are small-$N$ data only and do not address the asymptotic questions.

Lemma 1109.1 (every element of $A$ is odd and squarefree).

Let $A\subseteq\{1,\dots,N\}$ satisfy that every element of $A+A$ is squarefree. Then every $a\in A$ is odd and squarefree.

Proof.

Fix $a\in A$. Since $a+a=2a\in A+A$, the integer $2a$ is squarefree by hypothesis.

If $a$ were even, then $2a$ would be divisible by $4=2^2$, contradicting squarefreeness. Hence $a$ is odd.

If $a$ were not squarefree, then there exists a prime $p$ such that $p^2\mid a$. Then $p^2\mid 2a$, so $2a$ would not be squarefree, again contradicting the hypothesis. Therefore $a$ is squarefree. $\square$

Lemma 1109.2 (residue-class restriction modulo $p^2$).

Let $A\subseteq\{1,\dots,N\}$ satisfy that every element of $A+A$ is squarefree. Fix a prime $p$. Then:

• No element of $A$ is $0\bmod p^2$.
• For any residue class $x\bmod p^2$, $A$ cannot contain simultaneously an element congruent to $x$ and an element congruent to $-x$ modulo $p^2$.

In particular, if $r$ is the number of residue classes modulo $p^2$ that $A$ meets, then $r\le (p^2-1)/2$, and hence \[|A|\le \frac{p^2-1}{2}\,\left\lceil \frac{N}{p^2}\right\rceil. \]

Proof.

If $a\in A$ satisfies $a\equiv 0\pmod{p^2}$, then $a+a=2a\equiv 0\pmod{p^2}$, so $2a$ is divisible by $p^2$ and therefore not squarefree, contradicting the hypothesis. This proves the first bullet.

For the second bullet, suppose $a,b\in A$ satisfy $a\equiv x\pmod{p^2}$ and $b\equiv -x\pmod{p^2}$. Then $a+b\equiv 0\pmod{p^2}$, so $p^2\mid (a+b)$, implying $a+b$ is not squarefree. But $a+b\in A+A$, contradiction.

Thus among the nonzero residue classes modulo $p^2$, $A$ can use at most one of each pair $\{x,-x\}$. There are $p^2-1$ nonzero classes, giving at most $(p^2-1)/2$ usable classes. Each residue class contributes at most $\lceil N/p^2\rceil$ elements from $\{1,\dots,N\}$, yielding the stated upper bound on $|A|$. $\square$

VERIFICATION

• Lemma 1109.1 uses only the necessary condition that $2a\in A+A$ is squarefree, so it is robust.
• Lemma 1109.2 correctly treats the diagonal case $a=b$: the first bullet excludes $a\equiv 0\pmod{p^2}$, which is exactly the condition needed to prevent $2a$ from being divisible by $p^2$ for odd $p$.
• The brute-force computations restricted candidates to odd squarefree numbers using Lemma 1109.1; this does not discard any feasible maximizing set.

FINAL

UNRESOLVED

(i) Strongest proved partial result. Lemma 1109.1 shows every feasible set $A$ consists of odd squarefree integers. Lemma 1109.2 gives a sharp modular restriction: for each prime $p$, $A\bmod p^2$ avoids pairs $x,-x$ and avoids $0$, yielding the explicit bound $|A|\le \frac{p^2-1}{2}\lceil N/p^2\rceil$.

(ii) First gap. Prove an asymptotic upper bound of the form $f(N)\le N^{o(1)}$ (or $f(N)\le (\log N)^{O(1)}$), or else construct sets $A$ of size $N^{\delta}$ for some fixed $\delta>0$.

(iii) Top 3 next moves. 1. Combine the constraints of Lemma 1109.2 over many primes $p\le y$ using a sieve/large-sieve framework to force $|A|$ to be small. 2. Study the distribution of $A+A$ and use lower bounds on $|A+A|$ (via additive energy or sumset growth) together with upper bounds on how many squarefree numbers can lie in a structured set. 3. Computationally search for extremal sets for larger $N$ (say $N\le 500$) to guess the true growth rate and to detect residue-class patterns mod $p^2$ that good constructions exploit.

(iv) What a minimal counterexample would likely look like. To contradict a polylogarithmic upper bound, a minimal counterexample would be a set $A$ of size $\gg N^{\delta}$ whose residues modulo many small $p^2$ occupy close to $(p^2-1)/2$ allowable classes (from Lemma 1109.2) while still avoiding accidental divisibility by squares of larger primes in all pairwise sums. Such a set would likely have a strong Chinese-remainder structure.