Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 863

claims/: The 1 claim page of Problem 863, one per claimant's result; the problem's standing derives from them.

Statement. Let $r\geq 2$ and let $A\subseteq \{1,\ldots,N\}$ be a set of maximal size such that there are at most $r$ solutions to $n=a+b$ with $a\leq b$ for any $n$ . (That is, $A$ is a $B_2[r]$ set.)

Similarly, let $B\subseteq \{1,\ldots,N\}$ be a set of maximal size such that there are at most $r$ solutions to $n=a-b$ for any $n\geq 1$ .

If $\lvert A\rvert\sim c_rN^{1/2}$ as $N\to \infty$ and $\lvert B\rvert \sim c_r'N^{1/2}$ as $N\to \infty$ then is it true that $c_r\neq c_r'$ for $r\geq 2$ ? Is it true that $c_r'<c_r$ ?

Status. Proved. The site credits Ho (with GPT-5.4 Pro) with observing that the separation $c_r'\leq\sqrt r<c_r$ follows from a window count and the Cilleruelo–Ruzsa–Trujillo construction; the accepted claim is Ho.

Source. erdosproblems.com/863, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #863, https://www.erdosproblems.com/863.

References.

[CRT02] Cilleruelo, Javier and Ruzsa, Imre Z. and Trujillo, Carlos, Upper and lower bounds for finite $B_h[g]$ sequences. J. Number Theory (2002), 26-34.
[Ho26] Ho, Boon Suan, On a problem of Erdős, Berend, and Freud concerning bounded sums and bounded differences. Write-up posted 2026-04-22, revised 2026-05-03, https://boonsuan.github.io/erdos863.pdf.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (21)

problems/additive_bases/E0863/claims Additive Bases and Sidon Sets An upper bound on the size of Sidon sets Theorem 6.1: the largest t-thin Sidon set in [n] has (1 + o(1)) sqrt(tn) elements additive_bases/cilleruelo_2002_upper_lower_bounds_finite_b_h Lemma 2.3 (p. 5): the set {0,...,g-1} ∪ {g-1+2k : 1 <= k <= [g/2]} satisfies the B*[g] condition Theorem 1.1 (p. 1): F_2(g,N) <= 1.864(gN)^(1/2) + 1, and a cosine-improved bound on F_h(g,N) for h > 2 Theorem 2.1 (p. 4): F_2(g,N) >= ((g + [g/2])/(g + 2[g/2])^(1/2)) N^(1/2) + o(N^(1/2))additive_bases/green_2001_number_squares_b_h_g_sets Theorem 24 (p. 21): alpha(2,g) is at most sqrt(7g/2 - 7/4)Theorem 25 (p. 21): B_2[g] sets in {1,...,N} have at most (17/5)^(1/2) g^(1/2) N^(1/2)(1+o(1)) elements additive_bases/kolountzakis_1996_density_b_h_g_sequences_minimum Theorem 3 (p. 8): B_2[2] subsets of [1, n] of size sqrt(2n)additive_bases/lindstrom_2000_b_h_g_sequences_b_h Corollary (p. 659): B_h[m^(h-1)] sets of size (gn)^(1/h)(1+o(1)) in [1,n]additive_bases/martin_2005_constructions_generalized_sidon_sets Theorem 3 (p. 5): lower bounds for sigma(g) for even g from 4 to 22 Theorem 4 (p. 5): a lower bound for sigma(2g) for every g additive_bases/plagne_nd_recent_progress_finite_b_h_g Problem 6: does c_{h,g} = lim F_{h,g}(N)/N^{1/h} exist?additive_bases/sarkozy_1997_additive_representation_functions

Graph