Erdős Problem #1103

Erdős Problem 1103 --- collection record

PROVENANCE AND STATUS

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

REUSED SOURCE 1

FORMAL RESTATEMENT. Let $A\subset\mathbb Z$ be an infinite set. Interpreting growth as in the problem text, we take the minimal correction that $A\subset\mathbb N$ is infinite and write it in increasing order as $A=\{a_1<a_2<\cdots\}$. Assume that every sum $a_i+a_j$ (allowing $i=j$) is squarefree, i.e. for every prime $p$ one has $p^2\nmid (a_i+a_j)$. Question: how small can $a_j$ be as a function of $j$? Equivalently, how large can $|A\cap[1,X]|$ be as a function of $X$?

QUICK LITERATURE/CONTEXT CHECK (from the problem file only). The text states that Erdős produced an exponentially growing example, expected no polynomial-growth example, and that van Doorn--Tao $2025$ prove a lower bound $a_j>0.24j^{4/3}$ and an upper construction $a_j<\exp(5j/\log j)$ for large $j$. I do not reprove these claims here.

ATTACK PLAN.

• Extract immediate necessary congruence conditions from the squarefree constraint, especially modulo $p^2$.
• Use these congruence restrictions to get any unconditional growth lower bound.
• Reality check: brute force compute the maximum size of a subset of $\{1,\dots,N\}$ with squarefree pairwise sums for small $N$.

WORK.

Lemma 1 (each element is odd and squarefree). If $A+A$ consists entirely of squarefree integers, then every $a\in A$ is odd and squarefree.

Proof. Take any $a\in A$. Then $2a=a+a\in A+A$, hence $2a$ is squarefree. If $a$ were even, then $2a$ would be divisible by $4$, contradicting squarefreeness. So $a$ is odd. If $p$ is an odd prime with $p^2\mid a$, then $p^2\mid 2a$, again contradicting squarefreeness of $2a$. Thus no odd prime square divides $a$. Together with oddness, this means $a$ is squarefree. $\square$

Lemma 2 (no opposite residues modulo $p^2$). Let $p$ be an odd prime and let $S_p\subset\mathbb Z/p^2\mathbb Z$ be the set of residues attained by $A$ modulo $p^2$: \[S_p:=\{a\bmod p^2: a\in A\}. \] Then $S_p\cap(-S_p)=\varnothing$. In particular, \[|S_p|\le \frac{p^2-1}{2}. \]

Proof. If $r\in S_p\cap(-S_p)$, then there exist $a,b\in A$ with $a\equiv r\pmod{p^2}$ and $b\equiv -r\pmod{p^2}$. Then $a+b\equiv 0\pmod{p^2}$, so $p^2\mid(a+b)$, contradicting the assumption that $a+b$ is squarefree. Thus $S_p\cap(-S_p)=\varnothing$. The map $x\mapsto -x$ is a bijection of $\mathbb Z/p^2\mathbb Z$, so $|S_p|=|-S_p|$. Because $S_p$ and $-S_p$ are disjoint subsets of a set of size $p^2$, we have $2|S_p|\le p^2$. Since $p^2$ is odd this implies $|S_p|\le (p^2-1)/2$. $\square$

Lemma 3 (mod $4$ rigidity). All elements of $A$ lie in the same odd residue class modulo $4$; i.e. either $A\subseteq\{n: n\equiv 1\pmod 4\}$ or $A\subseteq\{n: n\equiv 3\pmod 4\}$.

Proof. By Lemma 1, all $a\in A$ are odd, so $a\equiv 1$ or $3\pmod 4$. If there exist $a,b\in A$ with $a\equiv 1\pmod 4$ and $b\equiv 3\pmod 4$, then $a+b\equiv 0\pmod 4$. Thus $4\mid(a+b)$, so $a+b$ is not squarefree, contradicting the hypothesis. Therefore all elements are congruent to $1\pmod 4$ or all are congruent to $3\pmod 4$. $\square$

FAST REALITY CHECK (finite search). For each $N$ I computed (by backtracking search) the maximum possible size of a subset $A\subseteq\{1,2,\dots,N\}$ such that every $a+b$ with $a,b\in A$ is squarefree. The exact maxima found were: \[ \begin{array}{c|c|l} N & \max|A| & \text{one maximiser }A\\\hline 10 & 2 & \{3,7\}\\ 20 & 3 & \{11,15,19\}\\ 30 & 4 & \{11,15,19,23\}\\ 50 & 6 & \{1,5,29,33,37,41\}\\ 60 & 7 & \{11,15,19,23,51,55,59\}\\ 100 & 8 & \{23,35,51,59,71,83,87,95\}\\ 150 & 12 & \{5,17,29,41,53,65,77,89,105,113,141,149\}\\ 200 & 16 & \{7,15,23,51,59,71,87,95,107,115,123,131,151,159,167,195\} \end{array} \] These are small-$N$ sanity checks only; they do not determine asymptotics.

VERIFICATION.

• Lemma 1: used only that $a+a\in A+A$ and that squarefree means not divisible by $4$ and not divisible by $p^2$ for odd primes.
• Lemma 2: checked that the conclusion uses $p$ odd so that $p^2$ is odd (no nontrivial element equals its own negative).
• Lemma 3: verified that mixing residues $1$ and $3$ mod $4$ forces a sum divisible by $4$.
• Finite search: I verified the reported witness sets by directly checking the squarefree condition for all pairs.

FINAL: UNRESOLVED. (i) Strongest proved partial result here. Any such $A$ must consist of odd squarefree integers all in a single residue class mod $4$ (Lemmas 1 and 3), and for each odd prime $p$ the residue set $A\bmod p^2$ avoids opposite residues, hence has size at most $(p^2-1)/2$ (Lemma 2).

(ii) First gap (crisp). I do not have an unconditional argument proving any superlinear lower bound $a_j\gg j^{1+\eta}$ for some fixed $\eta>0$ (or ruling out polynomial growth) from only the squarefree-sum condition.

(iii) Top 3 next moves. 1. Combine the "no opposite residues" condition for many primes $p\le P$ simultaneously via CRT to obtain a strong restriction on the additive energy of $A\cap[1,X]$. 2. Attempt a sieve-type upper bound on $|A\cap[1,X]|$ by counting pairs $(a,b)$ and estimating how often $a+b$ must fall into the set of nonsquarefree integers. 3. Extend the finite search to larger $N$ with heuristic/greedy constructions to guess the correct exponent from data (e.g. log--log slope of $\max|A\cap[1,N]|$).

(iv) Minimal counterexample structure. A hypothetically "slow-growing" infinite $A$ would need to place its elements into a carefully chosen sparse set of residue classes modulo many squares $p^2$ so that no pair of residues ever sums to $0$ mod $p^2$ for any $p$, while still leaving enough freedom to keep adding new elements without violating earlier congruence constraints.

COMPLETION ESTIMATE

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. Let $A\subset\mathbb Z$ be an infinite set. Interpreting growth as in the problem text, we take the minimal correction that $A\subset\mathbb N$ is infinite and write it in increasing order as $A=\{a_1<a_2<\cdots\}$. Assume that every sum $a_i+a_j$ (allowing $i=j$) is squarefree, i.e. for every prime $p$ one has $p^2\nmid (a_i+a_j)$. Question: how small can $a_j$ be as a function of $j$? Equivalently, how large can $|A\cap[1,X]|$ be as a function of $X$?

QUICK LITERATURE/CONTEXT CHECK (from the problem file only). The text states that Erdős produced an exponentially growing example, expected no polynomial-growth example, and that van Doorn--Tao $2025$ prove a lower bound $a_j>0.24j^{4/3}$ and an upper construction $a_j<\exp(5j/\log j)$ for large $j$. I do not reprove these claims here.

ATTACK PLAN.

• Extract immediate necessary congruence conditions from the squarefree constraint, especially modulo $p^2$.
• Use these congruence restrictions to get any unconditional growth lower bound.
• Reality check: brute force compute the maximum size of a subset of $\{1,\dots,N\}$ with squarefree pairwise sums for small $N$.

WORK.

Lemma 1 (each element is odd and squarefree). If $A+A$ consists entirely of squarefree integers, then every $a\in A$ is odd and squarefree.

Proof. Take any $a\in A$. Then $2a=a+a\in A+A$, hence $2a$ is squarefree. If $a$ were even, then $2a$ would be divisible by $4$, contradicting squarefreeness. So $a$ is odd. If $p$ is an odd prime with $p^2\mid a$, then $p^2\mid 2a$, again contradicting squarefreeness of $2a$. Thus no odd prime square divides $a$. Together with oddness, this means $a$ is squarefree. $\square$

Lemma 2 (no opposite residues modulo $p^2$). Let $p$ be an odd prime and let $S_p\subset\mathbb Z/p^2\mathbb Z$ be the set of residues attained by $A$ modulo $p^2$: \[S_p:=\{a\bmod p^2: a\in A\}. \] Then $S_p\cap(-S_p)=\varnothing$. In particular, \[|S_p|\le \frac{p^2-1}{2}. \]

Proof. If $r\in S_p\cap(-S_p)$, then there exist $a,b\in A$ with $a\equiv r\pmod{p^2}$ and $b\equiv -r\pmod{p^2}$. Then $a+b\equiv 0\pmod{p^2}$, so $p^2\mid(a+b)$, contradicting the assumption that $a+b$ is squarefree. Thus $S_p\cap(-S_p)=\varnothing$. The map $x\mapsto -x$ is a bijection of $\mathbb Z/p^2\mathbb Z$, so $|S_p|=|-S_p|$. Because $S_p$ and $-S_p$ are disjoint subsets of a set of size $p^2$, we have $2|S_p|\le p^2$. Since $p^2$ is odd this implies $|S_p|\le (p^2-1)/2$. $\square$

Lemma 3 (mod $4$ rigidity). All elements of $A$ lie in the same odd residue class modulo $4$; i.e. either $A\subseteq\{n: n\equiv 1\pmod 4\}$ or $A\subseteq\{n: n\equiv 3\pmod 4\}$.

Proof. By Lemma 1, all $a\in A$ are odd, so $a\equiv 1$ or $3\pmod 4$. If there exist $a,b\in A$ with $a\equiv 1\pmod 4$ and $b\equiv 3\pmod 4$, then $a+b\equiv 0\pmod 4$. Thus $4\mid(a+b)$, so $a+b$ is not squarefree, contradicting the hypothesis. Therefore all elements are congruent to $1\pmod 4$ or all are congruent to $3\pmod 4$. $\square$

FAST REALITY CHECK (finite search). For each $N$ I computed (by backtracking search) the maximum possible size of a subset $A\subseteq\{1,2,\dots,N\}$ such that every $a+b$ with $a,b\in A$ is squarefree. The exact maxima found were: \[ \begin{array}{c|c|l} N & \max|A| & \text{one maximiser }A\\\hline 10 & 2 & \{3,7\}\\ 20 & 3 & \{11,15,19\}\\ 30 & 4 & \{11,15,19,23\}\\ 50 & 6 & \{1,5,29,33,37,41\}\\ 60 & 7 & \{11,15,19,23,51,55,59\}\\ 100 & 8 & \{23,35,51,59,71,83,87,95\}\\ 150 & 12 & \{5,17,29,41,53,65,77,89,105,113,141,149\}\\ 200 & 16 & \{7,15,23,51,59,71,87,95,107,115,123,131,151,159,167,195\} \end{array} \] These are small-$N$ sanity checks only; they do not determine asymptotics.

VERIFICATION.

• Lemma 1: used only that $a+a\in A+A$ and that squarefree means not divisible by $4$ and not divisible by $p^2$ for odd primes.
• Lemma 2: checked that the conclusion uses $p$ odd so that $p^2$ is odd (no nontrivial element equals its own negative).
• Lemma 3: verified that mixing residues $1$ and $3$ mod $4$ forces a sum divisible by $4$.
• Finite search: I verified the reported witness sets by directly checking the squarefree condition for all pairs.

FINAL: UNRESOLVED. (i) Strongest proved partial result here. Any such $A$ must consist of odd squarefree integers all in a single residue class mod $4$ (Lemmas 1 and 3), and for each odd prime $p$ the residue set $A\bmod p^2$ avoids opposite residues, hence has size at most $(p^2-1)/2$ (Lemma 2).

(ii) First gap (crisp). I do not have an unconditional argument proving any superlinear lower bound $a_j\gg j^{1+\eta}$ for some fixed $\eta>0$ (or ruling out polynomial growth) from only the squarefree-sum condition.

(iii) Top 3 next moves. 1. Combine the "no opposite residues" condition for many primes $p\le P$ simultaneously via CRT to obtain a strong restriction on the additive energy of $A\cap[1,X]$. 2. Attempt a sieve-type upper bound on $|A\cap[1,X]|$ by counting pairs $(a,b)$ and estimating how often $a+b$ must fall into the set of nonsquarefree integers. 3. Extend the finite search to larger $N$ with heuristic/greedy constructions to guess the correct exponent from data (e.g. log--log slope of $\max|A\cap[1,N]|$).

(iv) Minimal counterexample structure. A hypothetically "slow-growing" infinite $A$ would need to place its elements into a carefully chosen sparse set of residue classes modulo many squares $p^2$ so that no pair of residues ever sums to $0$ mod $p^2$ for any $p$, while still leaving enough freedom to keep adding new elements without violating earlier congruence constraints.