ERDŐS/DAILY ▸

← back to the ledger

ERDőS #840 · PARTIAL

Erdős problem 840 — wave w018

Accessed and computed on 2026-07-28 (UTC).

Outcome

This run does not solve problem 840. It gives two verifiable pieces of progress.

  1. (d, computational-only) The finite extremal function introduced by

Pikhurko, \[ s(k,n):=\max_{\substack{A\subseteq[1,n]\\|A|=k}}|A+A|, \] is determined exactly for every \(n\leq 27\). In particular, \[ (s(k,27))_{k=1}^{27}= (1,3,6,10,15,21,28,34,41,47,51,53,\ldots,53). \] The exhaustive checker visits exactly \(2^{26}=67,108,864\) translated subsets, independently recomputes the witnesses, and cross-checks a second brute-force implementation through \(n=13\).

  1. **(a, elementary-rigorous; upper attainment uses the standard Fourier

uniqueness theorem, hence (b))** Pikhurko's trigonometric certificate is optimal in the whole class of arguments which bound each Fourier mode separately and then apply the triangle inequality. More precisely, if \[ q(x)=\sum_{t=1}^T(a_t\cos tx+b_t\sin tx)\geq 1 \quad(0\leq x\leq\pi), \] and \[ C(q):=\sum_{t=1}^T\sqrt{a_t^2+b_t^2}, \] then \[ C(q)\geq 1+\frac{\pi}{2}. \] The infimum is \(1+\pi/2\), exactly the value in Pikhurko's proof. Therefore reweighting, adding modes, or choosing different phases cannot improve his \(1.863949\ldots\) upper constant by that proof architecture. A better upper bound needs a genuinely joint inequality between Fourier modes (or a different method).

The exact finite table is useful data, but no finite computation supplies the uniform \(N\to\infty\) step required by the question.

Step 0: live-page gate

I used the Bright Data browser path, not datacenter curl, to load both https://www.erdosproblems.com/840 and its /latex/840 view.

(a, direct page transcript) At access time the live page said:

None;

Thus none of the mandatory stop conditions applied.

Verbatim live statement

Let \(f(N)\) be the size of the largest quasi-Sidon subset \(A\subset\{1,\ldots,N\}\), where we say that \(A\) is quasi-Sidon if \[ > \lvert A+A\rvert=(1+o(1))\binom{\lvert A\rvert}{2}. > \] How does \(f(N)\) grow?

The page labels this #840: [Er81h,p.175][ErFr91][Er92c].

Known results displayed on the live page

The following are page claims, and the cited theorem statements were checked in the primary sources.

\[ \left(\frac{2}{\sqrt3}+o(1)\right)N^{1/2} \leq f(N)\leq(2+o(1))N^{1/2}. \] The page says both bounds were already in Erdős's 1981 paper.

Sidon set \(B\subset[1,N/3]\), \(|B|\sim N^{1/2}/\sqrt3\), and uses \(B\cup\{N-b:b\in B\}\).

\[ f(N)\leq \left(\left(\frac14+\frac1{(\pi+2)^2}\right)^{-1/2}+o(1)\right)N^{1/2}, \] whose constant is \[ 1.863949116923613\ldots. \]

size is \((1+o(1))N^{1/2}\).

live LaTeX for 864. (a, direct page transcript) Problem 864 asks about sets having at most one repeated sum value and conjectures the same \(2/\sqrt3\) upper constant; its page explicitly calls it a weaker form of

  1. Thus that cross-reference does not contain a stronger known lower

construction.

The notation \(o(1)\) makes “largest” an asymptotic-family notion rather than a literal property of one finite set. (a) The function \(s(k,n)\) avoids that minor formal ambiguity and is the exact finite proxy used by Pikhurko.

Literature verification

Primary sources actually opened:

  1. P. Erdős, *Some problems and results on additive and multiplicative number

theory*, LNM 899 (1981), 171--182, especially p. 175: <https://renyi.hu/~p_erdos/1981-33.pdf>. The paper states the question, the reflected construction, and the trivial constant \(2\) upper bound.

  1. P. Erdős and R. Freud, On sums of a Sidon-sequence, J. Number Theory 38

(1991), 196--205, DOI <https://doi.org/10.1016/0022-314X(91)90083-N>. The journal record and paper metadata agree on volume, pages, and DOI.

  1. P. Erdős, Some of my forgotten problems in number theory,

Hardy--Ramanujan Journal 15 (1992): <https://hrj.episciences.org/125/pdf>.

  1. O. Pikhurko, Dense Edge-Magic Graphs and Thin Additive Bases,

arXiv:math/0309029 and Discrete Math. 306 (2006), 2097--2107, DOI <https://doi.org/10.1016/j.disc.2006.05.003>. Primary copies: <https://arxiv.org/abs/math/0309029> and <https://opikhurko.warwick.ac.uk/E/Pikhurko06dm.pdf>. Theorem 2 gives \[ s(k,n)\leq n+k^2\left(\frac14-\frac1{(\pi+2)^2}+o(1)\right), \] and Theorem 3 gives the displayed quasi-Sidon bound.

  1. J. Cilleruelo, Quasi Sidon Sets (author-hosted manuscript):

<https://matematicas.uam.es/~franciscojavier.cilleruelo/Papers/quasi-Sidon%20-%20greedy%20-%20solo%20A-A.pdf>. Its finite inequality implies the difference analogue quoted by the page.

(c, search result rather than a theorem) Exact-phrase searches for “quasi-Sidon”, “maximum size of quasi-Sidon sets”, Pikhurko's title, and the distinctive constant \(1/(\pi+2)^2\), together with forward-citation scans of the Erdős--Freud and Pikhurko DOIs, found no later primary paper claiming an improvement for this sumset question. The Pikhurko citations found after 2006 concern differences, edge-magic labellings, or finite additive bases. This is an honest search miss, not a proof that no uncatalogued result exists.

Pikhurko also records that Erdős and Freud had promised an unpublished \((1.98+o(1))N^{1/2}\) upper bound; Pikhurko's published theorem supersedes it.

1. Exact form of the standard lower construction

The live page gives the asymptotic construction. The following exact count is useful for checking collision bookkeeping.

Lemma (a, elementary-rigorous). Let \(B\subseteq[1,M]\) be a Sidon set of size \(m\), let \(N\geq3M\), and put

\[ X=B\cup(N-B). \]

Then

\[ |X|=2m,\qquad |X+X|=2m^2+1. \]

Proof. The three types of sums are

\[ B+B,\qquad N+(B-B),\qquad 2N-(B+B). \]

They lie respectively in

\[ [2,2M],\quad [N-M+1,N+M-1],\quad[2N-2M,2N-2], \]

which are disjoint when \(N\geq3M\). The first and third sets each have \(\binom{m+1}{2}\) elements. The Sidon property also makes all nonzero ordered differences distinct, so

\[ |B-B|=m(m-1)+1. \]

Adding the three cardinalities gives \(2m^2+1\). Also \([1,M]\) and \(N-[1,M]\) are disjoint. \(\square\)

Consequently,

\[ \frac{|X+X|}{\binom{|X|}{2}} =\frac{2m^2+1}{2m^2-m}=1+O(m^{-1}). \]

Using a family of asymptotically maximum Sidon sets \(|B|=(1+o(1))\sqrt M\) (Singer/Bose--Chowla) and \(M=\lfloor N/3\rfloor\) recovers \(2/\sqrt3\). This last existence input is (b, rigorous-modulo the named Sidon-set theorem). The verifier checks the exact formula for all 224 Sidon subsets of intervals of length at most 8.

2. Exact finite computation

Definition and exhaustive reduction

Let

\[ s(k,n)=\max\{|A+A|:A\subseteq[1,n],\ |A|=k\}. \]

(a) Translation preserves \(|A+A|\). Every nonempty \(A\subseteq[1,n]\) can therefore be translated so that its minimum is 0 and its diameter remains at most \(n-1\). It is enough to enumerate the \(2^{n-1}\) subsets of \([0,n-1]\) which contain 0.

Represent both \(A\) and its sumset \(\Sigma(A)=A+A\) as integer bit masks. When a new largest element \(x\) is adjoined,

\[ \Sigma(A\cup\{x\})=\Sigma(A)\cup(x+A)\cup\{2x\}. \]

Thus the complete search kernel is:

def visit(next_x, element_mask, sumset_mask, cardinality, diameter):
    score = sumset_mask.bit_count()
    best[diameter][cardinality] = max(
        best[diameter][cardinality], score
    )
    for x in range(next_x, max_n):
        visit(
            x + 1,
            element_mask | (1 << x),
            sumset_mask | (element_mask << x) | (1 << (2 * x)),
            cardinality + 1,
            x,
        )

visit(1, 1, 1, 1, 0)

(a) Each translated subset occurs exactly once, at the node whose selected positive elements are its DFS choices. (d) The run counted exactly \(2^{26}=67,108,864\) nodes. At 68 deterministically spaced nodes it threw away the recurrence and rebuilt the entire sumset mask directly. A separate itertools.combinations implementation exhaustively checked all 8,191 translated candidates arising for \(n\leq13\).

Exact row at \(n=27\)

(d, computational-only)

| \(k\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12--27 | |---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:| | \(s(k,27)\) | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 34 | 41 | 47 | 51 | 53 |

The nontrivial transition witnesses, independently checked by ordinary set comprehensions, are:

| \(k\) | witness \(A\subseteq[1,27]\) | \(|A+A|\) | |---:|:---|---:| | 7 | \(\{1,2,5,11,19,24,26\}\) | 28 | | 8 | \(\{1,2,5,15,18,19,24,26\}\) | 34 | | 9 | \(\{1,2,4,8,13,18,22,24,25\}\) | 41 | | 10 | \(\{1,2,4,9,13,15,19,24,26,27\}\) | 47 | | 11 | \(\{1,3,4,6,10,14,18,22,24,25,27\}\) | 51 | | 12 | \(\{1,2,3,4,8,12,16,20,22,25,26,27\}\) | 53 |

It follows computationally that the largest Sidon subset of \([1,27]\) has size 7, and the smallest \(A\subseteq[1,27]\) with \(A+A=[2,54]\) has size 12. The \(k=12\) witness makes the latter lower bound for every \(k\geq12\) elementary by adding arbitrary missing elements; the nonexistence claims at smaller \(k\) remain (d).

This finite row does not improve either asymptotic constant. It is exact data for the same \(s(k,n)\) whose asymptotics would settle the quasi-Sidon question.

3. A sharp barrier for Pikhurko's Fourier-certificate method

Abstract certificate problem

For a real trigonometric polynomial with no constant term,

\[ q(x)=\sum_{t=1}^T(a_t\cos tx+b_t\sin tx), \]

define its amplitude cost

\[ \|q\|_{\mathrm{amp}}=\sum_{t=1}^T\sqrt{a_t^2+b_t^2}. \]

Theorem (a, elementary lower bound). If \(q(x)\geq1\) on \([0,\pi]\), then

\[ \|q\|_{\mathrm{amp}}\geq1+\frac{\pi}{2}. \]

Proof. Symmetrise:

\[ \widetilde q(x)=\frac{q(x)+q(\pi-x)}2. \]

This keeps only the even cosine coefficients \(a_{2j}\) and the odd sine coefficients \(b_{2j+1}\), while never increasing amplitude cost. Since \(\widetilde q(0)\geq1\),

\[ 1\leq\sum_j a_{2j}\leq\sum_j|a_{2j}|. \]

Also,

\[ \pi\leq\int_0^\pi\widetilde q(x)\,dx =\sum_j\frac{2b_{2j+1}}{2j+1} \leq2\sum_j|b_{2j+1}|. \]

The retained cosine cost is therefore at least 1 and the retained sine cost at least \(\pi/2\). \(\square\)

Sharpness (b, using the standard Fourier uniqueness theorem). Pikhurko uses

\[ q_\infty(x)=\frac{\pi}{2}\sin x+ \sum_{j\geq1}\frac{2}{(2j)^2-1}\cos(2jx). \]

This is the Fourier series of the continuous \(2\pi\)-periodic function

\[ r(x)= \begin{cases} 1,&0\leq x\leq\pi,\\ 1+\pi\sin x,&\pi\leq x\leq2\pi. \end{cases} \]

Its coefficient cost is exactly

\[ \frac{\pi}{2}+\sum_{j\geq1}\frac{2}{4j^2-1} =\frac{\pi}{2}+\sum_{j\geq1} \left(\frac1{2j-1}-\frac1{2j+1}\right) =1+\frac{\pi}{2}. \]

The coefficients are absolutely summable, so the partial sums converge uniformly. Scaling a sufficiently long partial sum by its minimum on \([0,\pi]\) gives finite feasible polynomials whose costs tend to \(1+\pi/2\). Hence the infimum is exactly this value.

Why this is exactly the relevant obstruction

(b, rigorous modulo Pikhurko's displayed generating-function inequality) For \(F(\theta)=\sum_{a\in A}e^{ia\theta}\), Pikhurko obtains a common asymptotic bound \(Z\) for the sampled nonzero Fourier modes, with

\[ Z^2=k^2+4n-4|A+A|+o(n) \quad\text{when }k=O(\sqrt n). \]

Choosing an arbitrary phase at each mode and combining the separate inequalities produces precisely a polynomial \(q\) as above:

\[ k+o(\sqrt n)\leq \sum_{a\in A}q(\pi a/n) \leq \|q\|_{\mathrm{amp}}\,Z. \]

If a certificate of cost \(C\) exists, this yields

\[ |A+A|\leq n+k^2\left(\frac14-\frac1{4C^2}\right)+o(n). \]

The theorem forces \(C\geq1+\pi/2=(\pi+2)/2\), giving exactly

\[ \frac14-\frac1{4C^2} =\frac14-\frac1{(\pi+2)^2}. \]

For a quasi-Sidon family, the resulting constant is

\[ \frac{2}{\sqrt{1+C^{-2}}} =\left(\frac14+\frac1{(\pi+2)^2}\right)^{-1/2} =1.863949116923613\ldots. \]

Thus (a) no alteration consisting only of more modes, different phases, or different nonnegative mode weights can improve the Pikhurko constant. This does not prove that his bound is globally optimal.

4. What remains, precisely

Upper-bound route

(a, consequence of the certificate theorem) A strict improvement over \(1.863949\ldots\) cannot come from another mode-by-mode trigonometric minorant followed by the triangle inequality. The missing analytic input is a joint-mode inequality for the vector \((F(\pi t/n))_t\), using correlations imposed by the common set \(A\) and by the representation polynomial. Parseval by itself is too weak because it does not encode the missing-sum signs that drive Pikhurko's pointwise bound.

Lower-bound route

(a) To beat \(2/\sqrt3\), one must exhibit a family \(A_N\subseteq[1,N]\) with

\[ |A_N|\geq(c+o(1))\sqrt N,\qquad c>\frac2{\sqrt3}, \]

and

\[ \binom{|A_N|+1}{2}-|A_N+A_N|=o(N). \]

The reflected construction obtains the required \(o(N)\) defect by placing the three sum types in disjoint intervals, which forces its micro-Sidon set into length \(N/3\). A better construction must allow those ranges to overlap while proving only \(o(N)\) actual collisions, or use a genuinely different multi-block/algebraic design. No such uniform family emerged here.

Why extending the brute force is not the missing step

At the measured Python rate, the same full enumeration would cost approximately:

These are realistic extrapolations from 40.2 seconds for \(2^{26}\) nodes, not jobs run on this box. Better branch-and-bound or SAT encodings could push the exact table farther, but no fixed \(n\) closes the required uniformity step.

Reproduction

Standalone checker:

runs/erdos840_wavew018_verify.py

Run:

python runs/erdos840_wavew018_verify.py

Environment and audited result:

Python 3.12.3
Linux 6.12.93 x86_64
enumerated translated subsets: 67,108,864
incremental enumeration seconds: 40.219
sampled direct recurrence checks: 68
independent small-search candidates: 8,191
small reflected Sidon sets checked: 224
s(k,27), k=1..27:
1 3 6 10 15 21 28 34 41 47 51 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53
largest Sidon cardinality in [27]: 7
smallest k with A+A=[2,54]: 12
Fourier certificate infimum cost: 1+pi/2 = 2.570796326794897
Pikhurko upper constant: 1.863949116923613
reflected-Sidon lower constant: 1.154700538379252
ALL CHECKS PASSED

Checker SHA-256:

158c7d2ab2a59f4f3056eca7e75f89fdbc48e9cce37f99beaf28edf464a2bf7c

PARTIAL: exact s(k,n) for all n<=27 plus a proof that Pikhurko's 1.863949... bound is optimal within every mode-by-mode Fourier/triangle-inequality certificate; the asymptotic problem remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger