gpt pro 5.2 attempt on Math-5386

Erdős Problem #38

FORMAL RESTATEMENT

Fix the convention $\mathbb N=\{1,2,3,\dots\}$ and $[1,N]=\{1,2,\dots,N\}$. For $A\subseteq\mathbb N$ define its Schnirelmann density \[ d_s(A):=\inf_{N\ge 1}\frac{|A\cap[1,N]|}{N}\in[0,1]. \] For $b\in\mathbb Z$ write $A+b:=\{a+b:a\in A\}$.

Call $B\subseteq\mathbb N$ an additive basis if there exists $k\in\mathbb N$ and $n_0$ such that every integer $n\ge n_0$ can be written as a sum of $k$ (not necessarily distinct) elements of $B$.

The question asks whether there exists a set $B\subseteq\mathbb N$ which is not an additive basis, but for which there exists a function $f:(0,1)\to(0,\infty)$ such that for every $\alpha\in(0,1)$, every $A\subseteq\mathbb N$ with $d_s(A)=\alpha$, and every $N\ge 1$, there exists $b\in B$ (allowed to depend on $A$ and $N$) such that \[ \left|(A\cup (A+b))\cap[1,N]\right|\ \ge\ (\alpha+f(\alpha))\,N. \] Edge cases: for $\alpha=0$ or $\alpha=1$ the requirement on $f(\alpha)$ is not imposed.

QUICK LITERATURE/CONTEXT CHECK

The problem statement itself records an Erdős inequality when $B$ is an additive basis of order $k$, and notes a random-set obstruction showing the coefficient for $B=\mathbb N$ cannot exceed $\alpha(1-\alpha)$. I do not rely on any additional literature beyond what is explicitly stated in the problem text.

ATTACK PLAN

Proof track: Try to deduce strong structural consequences of the displayed inequality for all Schnirelmann-dense sets $A$ (e.g. residue-class obstructions), and see whether these consequences force $B$ to be an additive basis.

Disproof track: Try to construct, for a given candidate $B$ which is not an additive basis, a Schnirelmann-dense set $A$ such that for some $N$ every $b\in B\cap[1,N]$ yields only a negligible increase in $|(A\cup(A+b))\cap[1,N]|$.

In this write-up I obtain only necessary conditions on $B$ and an explicit family of "hard" sets $A$ showing how bounded shifts give only $O(b/P)$ improvement on periodic examples.

WORK

Fast reality check (tiny examples).

• If $A=2\mathbb N$ (evens), then $d_s(A)=1/2$. For any odd $b$, $A$ and $A+b$ are disjoint and $(A\cup(A+b))\cap[1,N]=[1,N]$, so the union has size $N$ (gain $1/2$). For even $b$, $A+b=A$ so there is no gain.
• For a periodic block-set $A$ of density $\alpha=L/P$ with period $P$ and block length $L$ (defined precisely in Lemma 38.2 below), a direct computation for $(P,L)=(10,4)$ gives union densities $0.5,0.6,0.7,0.8$ for shifts $b=1,2,3,\ge4$ at $N=10,20,50,100$ (checked by a short local script). This matches the exact formula proved in Lemma 38.2.

Lemma 38.1 (gcd obstruction).

If there exists an integer $d\ge 2$ such that every $b\in B$ is divisible by $d$, then $B$ cannot satisfy the desired property for any function $f$ with $f(1/d)>0$.

Proof. Assume $B\subseteq d\mathbb N$. Let $A=d\mathbb N=\{d,2d,3d,\dots\}$. Then for every $N\ge 1$ we have \[ |A\cap[1,N]|=\left\lfloor\frac{N}{d}\right\rfloor\ge \frac{N}{d}-1, \] and in fact $d_s(A)=1/d$ because $|A\cap[1,N]|/N\to 1/d$ and the ratio is always $\ge 1/d$ (the worst case occurs at $N=d$).

For any $b\in B$ we have $b=dm$ for some $m$, hence $A+b=A$ (translation by a multiple of $d$ preserves the set of multiples of $d$). Therefore \[ (A\cup(A+b))\cap[1,N]=A\cap[1,N] \quad\text{and}\quad \left|(A\cup(A+b))\cap[1,N]\right|=|A\cap[1,N]|. \] In particular, for all large $N$, \[ \left|(A\cup(A+b))\cap[1,N]\right|\le \frac{N}{d}+1. \] If the desired property held with some $f$ satisfying $f(1/d)>0$, then for each large $N$ there would exist $b\in B$ with \[ \frac{N}{d}+1\ \ge\ \left|(A\cup(A+b))\cap[1,N]\right|\ \ge\ \left(\frac{1}{d}+f\left(\frac{1}{d}\right)\right)N. \] Dividing by $N$ and letting $N\to\infty$ forces $f(1/d)\le 0$, a contradiction. $\square$

Corollary 38.1.

Any $B$ satisfying the property for all $\alpha\in(0,1)$ must have $\gcd(B)=1$ (equivalently, $B$ is not contained in $d\mathbb N$ for any $d\ge2$).

Lemma 38.2 (periodic block sets: exact union count for small shifts).

Fix integers $P\ge 2$ and $1\le L\le P-1$, and define \[ A:=\bigcup_{k\ge 0}\{kP+1,kP+2,\dots,kP+L\} \subseteq \mathbb N. \] Then $d_s(A)=L/P$. Moreover, for any integer shift $b$ with $0\le b\le P-L$ and any integer $K\ge 1$ we have the exact formula \[ \left|(A\cup(A+b))\cap[1,KP]\right|\ =\ K\,(L+\min\{b,L\}). \] In particular, \[ \frac{\left|(A\cup(A+b))\cap[1,KP]\right|}{KP}\ \le\ \frac{L}{P}+\frac{b}{P}. \]

Proof. We first compute $d_s(A)$. For any $N\ge1$, write $N=kP+r$ with integers $k\ge0$ and $0\le r\le P-1$. Then in the first $k$ full periods we capture exactly $kL$ elements of $A$, and in the partial period we capture $\min\{r,L\}$ additional elements. Hence \[ |A\cap[1,N]|=kL+\min\{r,L\}. \] Therefore \[ \frac{|A\cap[1,N]|}{N}= \frac{kL+\min\{r,L\}}{kP+r}\ \ge\ \frac{kL+\min\{r,L\}}{kP+r}\cdot\frac{P}{P} \ge \frac{L}{P}, \] because $\min\{r,L\}\ge (L/P)\,r$ for $0\le r\le P$ (if $r\le L$ then $\min\{r,L\}=r\ge (L/P)r$; if $r\ge L$ then $\min\{r,L\}=L\ge (L/P)r$ since $r\le P$). Taking $N=KP$ gives equality $|A\cap[1,KP]|/(KP)=L/P$, so the infimum is exactly $L/P$.

Now assume $0\le b\le P-L$ and take $N=KP$. Decompose $[1,KP]$ into the disjoint union of periods $I_k:=\{kP+1,\dots,kP+P\}$ for $k=0,1,\dots,K-1$.

Inside a fixed period $I_k$, we have \[ A\cap I_k = \{kP+1,\dots,kP+L\} \quad\text{and}\quad (A+b)\cap I_k = \{kP+1+b,\dots,kP+L+b\}, \] where the latter inclusion holds because $b\le P-L$ ensures $kP+L+b\le kP+P$, i.e. the shifted block stays inside the same period.

Thus, within each $I_k$, the union $(A\cup(A+b))\cap I_k$ is the union of two intervals of length $L$ shifted by $b$. If $b\le L$, their overlap has length $L-b$, so the union has size $L+b$. If $b\ge L$, they are disjoint, so the union has size $2L=L+L=L+\min\{b,L\}$. In all cases, \[ |(A\cup(A+b))\cap I_k|=L+\min\{b,L\}. \] Summing over $k=0,\dots,K-1$ yields \[ \left|(A\cup(A+b))\cap[1,KP]\right|=\sum_{k=0}^{K-1}|(A\cup(A+b))\cap I_k| =K\,(L+\min\{b,L\}). \] Dividing by $KP$ gives the final inequality. $\square$

VERIFICATION

• Lemma 38.1: checked that $A=d\mathbb N$ indeed satisfies $d_s(A)=1/d$ by an explicit count and a direct inequality for all $N$.
• Lemma 38.2: boundary cases $b=0$ (union equals $A$) and $b=P-L$ (shift just reaches the end of the period) are covered; the proof uses that $b+L\le P$ so no wrap-around occurs when $N=KP$.
• Quantifiers: Lemma 38.2 only controls special $N$ (multiples of $P$) and shifts $b\le P-L$; it is intended as a construction for lower-bounding how much union-growth small shifts can force.

FINAL

UNRESOLVED

(i) Strongest proved partial result. Any $B$ satisfying the stated property for all $\alpha\in(0,1)$ must have $\gcd(B)=1$ (Corollary 38.1). Moreover, for rational $\alpha=L/P$ the periodic set $A$ of Lemma 38.2 has $d_s(A)=\alpha$ and for shifts $b\le P-L$ the gain on $[1,KP]$ is at most $b/P$.

(ii) First gap (crisp statement). I cannot prove or disprove: There exists a non-basis $B\subseteq\mathbb N$ with $\gcd(B)=1$ and a function $f(\alpha)>0$ such that for every $A$ with $d_s(A)=\alpha$ and every $N$ there exists $b\in B\cap[1,N]$ with $|(A\cup(A+b))\cap[1,N]|\ge (\alpha+f(\alpha))N$.

(iii) Top 3 next moves (concrete).

1. Try to strengthen Lemma 38.2 to handle all shifts $b\le N$ by controlling wrap-around when $b$ exceeds the gap size, aiming for a bound of the form $|(A\cup(A+b))\cap[1,N]|\le (\alpha+O(\min\{1,b/P\}))N$.
2. Given a sparse candidate $B$ (e.g. lacunary), attempt to choose a periodic $A$ whose period $P$ is tuned so that every $b\in B\cap[1,N]$ falls into a set of "bad" residues mod $P$ producing small union gain.
3. Conversely, attempt a positive construction: pick $B$ with strong equidistribution mod many moduli but still not an additive basis, and show that for any $A$ of Schnirelmann density $\alpha$ some $b\in B$ forces $|A\cap(A+b)\cap[1,N]|$ small enough to yield a fixed gain.

(iv) What a minimal counterexample would likely look like. A minimal failure for a given $B$ would be a set $A$ with $d_s(A)=\alpha$ that is highly structured (likely periodic or near-periodic) so that for many shifts $b\in B\cap[1,N]$ the translate $A+b$ overlaps $A$ on almost all of $[1,N]$, making the union gain $o(N)$. Lemma 38.2 exhibits a clean periodic template where the gain is controlled by $b/P$.