/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
There is at most one $n$ with more than one representation $n = a + b$, where $a \leq b$ and
$a, b \in A$. That is, any two integers with more than one representation are equal.
Every Sidon set satisfies this condition, since then no $n$ has more than one representation.
Let $A\subseteq {1,\ldots,N}$ be a set such that there exists at most one $n$ with more than one
solution to $n=a+b$ (with $a\leq b\in A$). Estimate the maximal possible size of $|A|$. In
particular, is it true that
$$|A| \leq (1+o(1))\frac{2}{\sqrt{3}} N^{1/2}?$$
A problem of Erdős and Freud [ErFr91] [Er92c]. For the analogous question with $n=a-b$ they prove
that $\lvert A\rvert\sim N^{1/2}$. This is a weaker form of Erdős Problem 840.
The condition on $A$ is HasAtMostOneRepeatedSum. We state the question as follows: for every
$\varepsilon > 0$ and all large $N$, every such set $A$ satisfies
$|A| \leq (1+\varepsilon)\frac{2}{\sqrt{3}} N^{1/2}$.
Erdős and Freud [ErFr91] [Er92c] prove that
$$\lvert A\rvert \geq (1+o(1))\frac{2}{\sqrt{3}}N^{1/2}.$$
This is shown by taking a genuine Sidon set $B\subset [1,N/3]$ of size $\sim N^{1/2}/\sqrt{3}$
and taking the union with ${N-b : b\in B}$.
That is, for every $\varepsilon > 0$ and all large $N$ there is a set $A\subseteq {1,\ldots,N}$
with the property of Erdos864.erdos_864 and $|A| \geq (1-\varepsilon)\frac{2}{\sqrt{3}}N^{1/2}$.
So the constant $2/\sqrt{3}$ there cannot be replaced by a smaller one.
The set ${1,2,3}$ is not a Sidon set, but it satisfies the condition: only
$4 = 1 + 3 = 2 + 2$ has two representations.
All goals completed! 🐙
The set ${1,2,3,4}$ does not satisfy the condition: both $4 = 1 + 3 = 2 + 2$ and
$5 = 1 + 4 = 2 + 3$ have two representations. Without the case $a = b$, $4$ would have only one
representation and the set would satisfy the condition.