Problem 786

../

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

---

Statement. Let $\epsilon>0$. Is there some set $A\subset \mathbb{N}$ of density $>1-\epsilon$ such that $a_1\cdots a_r=b_1\cdots b_s$ with $a_i,b_j\in A$ can only hold when $r=s$?

Similarly, can one always find a set $A\subset\{1,\ldots,N\}$ with this property of size $\geq (1-o(1))N$?

Statement (precise). Let $\epsilon>0$. Is there some set $A\subset \mathbb{N}$ of density $>1-\epsilon$ such that $a_1\cdots a_r=b_1\cdots b_s$ with $a_i,b_j\in A$ (where each product runs over a subset of $A$) can only hold when $r=s$?

Similarly, can one always find a set $A\subset\{1,\ldots,N\}$ with this property of size $\geq (1-o(1))N$?

Notes. The site's wording does not say whether a factor may repeat within a product, and the two readings have different answers on the record: when repetitions are allowed the condition on $A$ is stronger, and [ERS73] answers both questions no (see Formulation); when the factors of each product are distinct the condition is weaker, and the site's commentary calls both questions open. The site's commentary itself calls the original sources ambiguous on this point. The change inserts "(where each product runs over a subset of $A$)" after "$a_i,b_j\in A$", in the words of Erdős's definition of property $P$ in [Er80], printed p. 114: "(where each product runs over a subset of the $a$'s)". That is the poser's own statement of both questions, and it fixes the distinct-factor reading; the two subsets may overlap, since no disjointness is required there. The poser's other texts are silent but agree with it: [Er65], printed p. 182, introduces the condition (4), $\prod_{r=1}^{l_1}a_{i_r}=\prod_{r=1}^{l_2}a_{j_r}$ only if $l_1=l_2$, as the alternative to the distinct-products condition (3), whose products are over subsets ($\epsilon_i=0$ or $1$), [Er69], printed p. 81, display (12), writes $\prod_{r=1}^{q_1}a_{i_r}=\prod_{r=1}^{q_2}a_{j_r}$ only if $q_1=q_2$, and [Er73], printed p. 132, writes the products as $a_{i_1}\cdots a_{i_r}=a_{j_1}\cdots a_{j_s}$, neither saying whether the indices repeat. The silence is therefore already in the poser's earlier texts, and no text of his fixes the repetitions-allowed reading. The results about that reading are credited, not counted: Theorems 2 and 6 of Erdős, Ruzsa and Sárközy [ERS73], with the transfer to product sets that the site's commentary gives, and Tao's sharp constant from Granville and Soundararajan [GrSo01] in forum post 4061 (2 February 2026), all recorded under Formulation and Known Results.

Formulation. The site's wording as of the snapshot accessed 2026-09-04 (page last edited 11 April 2026); its full commentary distinguishes the two conventions. The two subsets in the Statement (precise) may overlap, and the Lean definition quoted in forum post 4031 likewise has no disjointness hypothesis. The reading not adopted, with repetitions allowed, has the answer no to both questions. With repetitions allowed, the number of factors of a product of members of $A$ is well defined; it extends to the group generated by $A$ and from there to a completely additive real function $f$ with $f(a)=1$ for every $a\in A$, so $A$ lies in the level set $\{f=1\}$. Theorem 2 of [ERS73], p. 2, bounds the density of such a level set by $1/2$ for each fixed real additive $f$, and Theorem 6, p. 2, gives an absolute $C>0$ with $\lvert A\cap[1,N]\rvert<(1-C)N$ for large $N$ even when $f$ varies with $N$. The site's commentary gives this transfer and names Theorem 2; the paper itself never mentions the product question, and the deduction carries no independent review. The site's curator agrees that [ERS73] answers both questions no in this reading and keeps the problem OPEN until the distinct-factor reading is settled (forum post 4060, 2 February 2026).

Status. The site labels the problem OPEN (page last edited 11 April 2026; proof-claim tab accessed 2026-10-06), a label that describes the distinct-factor reading as unsettled. The standing derives from the claim pages and judges the Statement (precise). The full claim Li 2026, submitted to the site's proof-claim tab on 28 September 2026 and declared as produced with GPT-6 Astra and GPT-5.6 Sol (OpenAI) and Claude (Anthropic), asserts negative answers to both questions under the distinct-factor reading; the partial claim Gessel 2026 of 6 September 2026 asserts the density bound $7/8$ for the first question under the same reading. The site has not acted on either, neither has a referee or named reviewer, and no Lean development of either has been built or audited in this corpus, so the full claim is claimed and the problem's standing is claimed, disproved. Ruzsa's negative answers to both questions under the distinct-factor reading, which [Er80] reports without a proof or a proof citation and which the site's commentary suspects came from a confusion of the two conventions, are a report of an unpublished result rather than a posted claim, so they have no claim page; Progress below records the report. The negative answers under the repetitions-allowed reading concern the reading not adopted and are recorded under Formulation.

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

References.

• [ERS73] Erdős, P. and Ruzsa, Jr., I. and Sárközi, A., On the number of solutions of $f(n)=a$ for additive functions. Acta Arith. 24 (1973), 1--9. Source digest.
• [Er69] Erdős, Paul, Some applications of graph theory to number theory. The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) (1969), 77-82. Source digest.
• [Er65] Erdős, P., Extremal problems in number theory. Proc. Sympos. Pure Math., Vol. VIII (1965), 181-189. Source digest and later Additions.
• [Er73] Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138. Source digest.
• [Er80] Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. Source digest.
• [GrSo01] Granville, Andrew and Soundararajan, K., The spectrum of multiplicative functions. Ann. of Math. (2) 153 (2001), no. 2, 407-470, DOI 10.2307/2661346. Source digest; arXiv version 1, 8 September 1999.

Formalization. Statement in formal-conjectures.

Current assessment

Scope: the site's full commentary (accessed 2026-09-04), the discussion thread (accessed 2026-09-06) and the proof-claim tab (accessed 2026-10-06), with the statements in [Er65], [Er73], [Er80], [ERS73] and [GrSo01]. No literature search beyond these sources, check of the linked Lean developments or proof review is recorded. The Statement (precise) takes the distinct-factor reading from [Er80], under which the site's commentary treats both questions as open; the negative answers under the repetitions-allowed reading come from [ERS73] through the transfer the commentary gives and are recorded under Formulation.

Proof claims on the site. The site's proof-claim tab carries two claims, both for the distinct-factor reading, each declared as produced with AI systems (Gessel's with GPT-6 Astra (Codex); Li's with GPT-6 Astra, GPT-5.6 Sol and Claude) and each with a manuscript and a Lean development linked from its claim page. The partial claim Gessel 2026 (6 September 2026) bounds the natural density of an admissible set by $7/8$ and leaves the finite question open. The full claim Li 2026 (28 September 2026) asserts an absolute deficit, $\lvert A\rvert<(1-\eta)N$ for every admissible $A\subseteq\{1,\ldots,N\}$ and large $N$, and a logarithmic density at most $1/2$ for an admissible infinite set. Gessel's note says that Erdős's 1980 survey reports a stronger unpublished negative result of Ruzsa in this setting, and Li's note says that the survey reports Ruzsa as having shown both answers negative there, with no proof published; neither claims priority. The site's label is OPEN, no comment has been posted on either claim, and neither manuscript nor either Lean development has been reviewed in this corpus.

Progress

Er80, printed p. 114, defines property $P$ using a subset on each side of the product equality. It reports that Ruzsa answered both the infinite-density and finite-size questions negatively, with upper density $<1/e$ in the infinite case and an absolute finite deficit. It also calls the infinite bound best possible. No proof or specific proof citation accompanies that paragraph, and no proof of Ruzsa's results has been published. The site's suggestion that Erdős confused the two conventions is conjectural.

Er65, printed p. 182, equation (3), explicitly uses exponents in $\{0,1\}$, and the adjacent equal-product-length question (4), posed as its alternative, writes the products with indices whose repetition it does not address. The later Additions printed with [Er65], p. 189, report Ruzsa's bound $Z<n(1-\epsilon)$ while printing $\epsilon<0$ and saying the proof is not yet published. The sign is defective for a nontrivial deficit and is not silently corrected here. These Additions include later references and are not evidence that this report appeared in the original 1965 text.

Known Results

ERS73 studies real additive functions and the largest nonzero level set $G_0(x)=\max_{c\ne0}\#\{n\leq x:f(n)=c\}$. Its Theorem 2, p. 2, gives an existing limiting proportion at most $1/2$ for each fixed function. Theorem 3 makes the bound strict for a totally additive function, where $f(ab)=f(a)+f(b)$ for every $a,b$, without coprimality. Theorem 6, p. 2, gives an absolute $C>0$ with $\limsup_{x\to\infty}\max_f G_0(x)/x<1-C$, allowing $f$ to vary with $x$. The site's full commentary names Theorem 2; Theorem 6 is the statement that gives the finite bound. The source's suggestion of $G_0(x)<9x/10$, p. 5, is not proved there.

These level-set theorems reach the product-length condition only through a transfer, which the site's full commentary gives for the repetitions-allowed reading: an upper bound needs only $A\subseteq\{n:f(n)=1\}$, and the commentary's equality with that level set is stronger than needed. The transfer does not reach the distinct-factor reading of the Statement (precise), whose condition on $A$ is weaker.

Granville-Soundararajan's arXiv:math/9909190v1, pp. 2-3, concerns real completely multiplicative functions $g:\mathbb N\to[-1,1]$. Corollary 1 gives $\sum_{n\leq x}g(n)\geq(\delta_1+o(1))x$, where $\delta_1=-0.656999\ldots$. Tao's forum post 4061, 2 February 2026, proposes $g(n)=(-1)^{f(n)}$ and the sharp finite constant $0.1715\ldots$; that notation is in the forum post, not the site's full commentary (accessed 2026-09-04). For a merely real additive $f$, the real-valued hypothesis on $g$ requires justification. Neither that bridge nor a sharp $0.8285\ldots$ density bound for either convention has been verified in this corpus; the source cards record the exact source bounds and omitted-proof qualifications.

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.

• erdos_1965_extremal_problems_number_theory
• erdos_1973_number_solutions_additive_functions
• granville_2001_spectrum_multiplicative_functions
• granville_2001_spectrum_multiplicative_functions / corollary_1
• granville_2001_spectrum_multiplicative_functions / theorem_1
• erdos_1980_survey_problems_combinatorial_number_theory