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

Updated Oct 7

Problem 1109

claims/: The 3 claim pages of Problem 1109, one per claimant's result; the problem's standing derives from them.

Statement. Let $f(N)$ be the size of the largest subset $A\subseteq {1,\ldots,N}$ such that every $n\in A+A$ is squarefree. Estimate $f(N)$ . In particular, is it true that $f(N)\leq N^{o(1)}$ , or even $f(N) \leq (\log N)^{O(1)}$?

Status. Open. The site labels the problem OPEN (page last edited 3 December 2025). Its commentary credits three sets of bounds, each recorded on a claim page: Erdős and Sárközy's $\log N\ll f(N)\ll N^{3/4}\log N$ , Erdős and Sárközy 1987; Gyarmati's second proof of $f(N)\gg\log N$ , Gyarmati 2001; and Konyagin's $\log^2N\log\log N\ll f(N)\ll N^{11/15+o(1)}$ , the best known, Konyagin 2004. None answers either question. G. N. Sárközy [Sa92c] extends the problem to sums $A+B$ and to $k$ -power-free sums and, as Konyagin records (p. 494), improves the upper bound to $f(N)\ll N^{3/4}$ ; that bound is superseded by Konyagin's and the site does not credit it, so it has no claim page.

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

References.

[ErSa87] Erdős, P. and Sárközy, A., On divisibility properties of integers of the form $a+a'$ . Acta Math. Hungar. (1987), 117-122.
[Gy01] Gyarmati, Katalin, On divisibility properties of integers of the form $ab+1$ . Period. Math. Hungar. (2001), 71-79.
[Ko04] Konyagin, S. V., Problems of the set of square-free numbers. Izv. Ross. Akad. Nauk Ser. Mat. (2004), 63-90.
[Sa92c] Sárközy, G. N., On a problem of P. Erdős. Acta Math. Hungar. (1992), 271-282.

Formalization. Statement in formal-conjectures.

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 (13)

Erdős and Sárközy's first bounds for squarefree pairwise sums Gyarmati's graph-theoretic proof of the logarithmic lower bound Konyagin's bounds for squarefree pairwise sums problems/integer_sequences/E1109/claims Sequences and Densities of Integers integer_sequences/doorn_2025_growth_rates_sequences_governed_squarefree_properties Unnumbered bound (p. 4): a sequence with squarefree sums has a_j >> j^{15/11} exp(-O(log j/sqrt(log log j)))integer_sequences/erdos_1987_divisibility_properties_integers_form Conjecture (p. 117): the bound 3N^{3/4} log N can be replaced by N^eps, perhaps by (log N)^c Remark (pp. 117--118): two sequences with all cross sums squarefree have kl < N^{3/2+eps}Theorem 1 (p. 117): a subset of {1,...,N} of more than (1/248) log N elements with all pairwise sums squarefree Theorem 2 (p. 117): a subset of {1,...,N} with all pairwise sums squarefree has fewer than 3N^{3/4} log N elements integer_sequences/konyagin_2004_problems_set_square_free_numbers

Graph