Erdoes #786 - working report - Erdős Problem a Day

Erdős problem 786, wave 7l

Access date: 2026-07-27 UTC.

Claim labels used below:

(a) elementary-rigorous: a proof is included and uses no unproved

external input.

(b) rigorous-modulo-named-theorem: the deduction is rigorous assuming

the cited published theorem.

(c) plausible/structural-unverified: a conjecture, comment, search miss,

or proposed route, not a theorem.

(d) computational-only: an exact finite computation with reproducible

code, not an asymptotic theorem.

0. Mandatory live-page audit

I fetched the rendered live page through the Bright Data browser path, then

opened its discussion thread and read the full rendered text. The direct page

was not inferred from stale YAML.

Live-page facts:

Status: OPEN.
Last edited: 11 April 2026.
Claimed proofs: 0.
“Currently working on this problem”: None.
“Interested in collaborating”: None.
“Likes this problem”: Alfaiz, ebarschkis, Dogmachine, ibex.
Comments: 10.

Thus the mandatory stop condition did not fire.

Verbatim live 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$?

Source: live problem 786 and its

live discussion thread.

Results and qualifications listed on the live page

The following is a faithful audit of what the page says, not a claim that

every historical attribution has independently available proof.

1. (a) The integers congruent to $2\bmod 4$ have the property and

density $1/4$: the 2-adic valuation of a product of $r$ such integers

is exactly $r$.

2. (a) The page gives Selfridge's construction with density

$1/e-\epsilon$: choose large consecutive primes \(p_1<\cdots

$\sum_{i\leq k}1/p_i<1<\sum_{i\leq k+1}1/p_i$, and take integers

divisible by exactly one selected prime. The selected-prime valuation

count is a totally additive function equal to $1$ on the construction,

so equal products have equal numbers of factors.

3. (b) For the finite problem, the page records the elementary

$(\log 2)N$ construction using a prime factor $>N^{1/2}$, and the

improved $0.8285\ldots N$ construction from the comments: integers with

exactly one prime factor

$>N^{1/(1+\sqrt e)}$. The asymptotic count is an analytic-number-theory

input; the product property again follows from an additive prime-factor

count.

4. (b) If repetitions are allowed, the page reduces the property to a

level set $\{n:f(n)=1\}$ of a totally additive function. It cites

Erdős--Ruzsa--Sárközy for a uniform finite upper gap and density at most

$1/2$, and Granville--Soundararajan for the sharp completely

multiplicative finite constant $1-0.1715\ldots$.

5. The page explicitly warns that item 4 assumes repetitions. If every

product must use distinct elements, that reduction is not justified and

the page leaves both questions open.

6. The page also records a historical conflict: Erdős's 1980 formulation

explicitly says that each product runs over a subset and reports that

Ruzsa answered both questions negatively, with upper density $<1/e$ in

the infinite case and a fixed finite gap. No proof is supplied there.

The page says Erdős may have conflated this with the repetitions-allowed

result.

7. The page points to related problems [421] and [795]. Problem 795 concerns

full dissociativity of subset products and is now solved, but it does not

impose or resolve the unequal-cardinality-only condition here.

All ten comments read

The site warns that comments are user-supplied and unverified. Accordingly,

claims in this digest are (c) unless separately proved elsewhere.

1. ebarschkis, 2026-02-01 10:47: asks whether repetitions are allowed,

links the 1965 Erdős paper and the 1973 Erdős--Ruzsa--Sárközy paper, and

notes that the interpretation matters.

2. ebarschkis, 2026-02-01 12:49: quotes the Google DeepMind Lean

formalisation using Finset, hence distinct factors; later notes that an

earlier Tao comment used repetitions. The site says it was updated in

response.

3. Terence Tao, 2026-02-01 16:22: says sampling with and without

replacement should be contiguous when $r,s\ll N$; after checking the

original sources, he leans toward the distinct-elements interpretation

because neighbouring questions use that language.

4. ebarschkis, 2026-02-01 16:34: explains the valuation-vector

linear-algebra reduction for repetitions and observes that it does not

directly handle the distinct-elements variant.

5. Thomas Bloom, 2026-02-02 06:57: agrees that the repetitions-allowed

variant is answered negatively by the 1973 additive-function paper, but

keeps the page open for the no-repetition variant.

6. Terence Tao, 2026-02-02 07:34: derives the Hall--Montgomery finite

constant for the repetitions variant and tentatively conjectures the same

upper bound for the no-repetition problem.

7. Thomas Bloom, 2026-02-02 08:37: asks whether the first, density,

repetitions-allowed question can be sharpened beyond the listed

$1/e$ lower and $1/2$ upper bounds.

8. Terence Tao, 2026-02-02 16:24: reports no better bound; he notes that

Wirsing's theorem bounds a related parity level set, but that level set is

only an upper envelope for $\{f=1\}$.

9. Terence Tao, 2025-10-18 16:39: gives the $0.828499\ldots$ finite

construction, relates it to the Hall--Montgomery constant, and proposes a

robust-contiguous-probability approach to forcing a collision after

deleting $o(N)$ elements.

10. Terence Tao, 2025-10-18 14:59: reports that two AI-assisted

literature reviews found no Ruzsa proof or relevant literature beyond

what the tracker already listed.

1. Primary-source literature audit

I searched by the exact problem phrases, Selfridge's $1/e$ construction,

Ruzsa's claimed upper-density statement, and the titles and bibliographic

data on the tracker. I checked the following primary sources.

1. [Erdős, Extremal Problems in Number Theory

(1965)](https://users.renyi.hu/~p_erdos/1965-02.pdf), pp. 181--189.

Page 182 asks the product-length question and gives the $2\bmod4$ and

Selfridge constructions. An additions section reports an unpublished

Ruzsa finite negative result. The displayed indexed products do not say

whether indices may repeat.

2. [Erdős, Some Applications of Graph Theory to Number Theory

(1969)](https://users.renyi.hu/~p_erdos/1969-14.pdf), pp. 77--82.

Page 81 asks the infinite question and gives Selfridge's construction;

page 82 asks whether the finite maximum is $n+o(n)$ and records the

$(\log2-o(1))n$ lower bound. It supplies no upper bound and again does

not explicitly specify distinct indices.

3. [Erdős, Problems and Results on Combinatorial Number Theory

(1973)](https://users.renyi.hu/~p_erdos/1973-21.pdf), pp. 117--138.

Page 132 repeats both questions and the lower bounds, without reporting a

resolution.

4. [Erdős, Ruzsa, and Sárközy, *On the number of solutions of

$f(n)=a$ for additive functions*

(1973)](https://users.renyi.hu/~p_erdos/1973-16.pdf),

DOI 10.4064/aa-24-1-1-9.

The paper exists in Acta Arithmetica 24 (1973), 1--9. Its theorems bound

level sets of additive and totally additive functions. **It does not

prove that the distinct-subset hypothesis produces such a function.**

5. [Erdős, A survey of problems in combinatorial number theory

(1980)](https://users.renyi.hu/~p_erdos/1980-03.pdf), pp. 89--115.

Page 114 explicitly defines property $P$ using products “over a subset

of the $a$'s,” then says Ruzsa proved the infinite upper density

$<1/e$ (best possible) and a finite bound $(1-c)x$. There is no proof

or bibliographic pointer for this claim.

6. [Granville and Soundararajan, *The spectrum of multiplicative

functions*](https://annals.math.princeton.edu/2001/153-2/p04),

Annals of Mathematics 153 (2001), 407--470, DOI

10.2307/2661346, is the real-valued multiplicative-spectrum source cited

in the tracker comments. It supports the repetitions/level-set discussion,

not the missing distinct-subset reduction.

7. [Tao, On product representations of squares,

arXiv:2405.11610](https://arxiv.org/abs/2405.11610) exists and proves a

fixed density gap for a related problem about $k$ distinct elements

whose product is a square. That condition does not itself give two

subsets of $A$ with equal products and unequal cardinalities, so it does

not close problem 786.

Search miss (c). I found no published version of the specific Ruzsa

argument reported on page 114 of the 1980 survey, and no later primary source

directly resolving the distinct-elements version. This is a report of the

search result, not proof that no such source exists. In particular, the live

page's OPEN status and its warning about unknown literature remain the

appropriate authority.

2. Exact finite formulation

Let

\[ M(N)=\max\{|A|:A\subseteq[1,N]\text{ has the distinct-elements property}\}. \]

The empty product convention only affects the singleton case $N=1$. For

every $N\ge2$, the same maximum results if products are required to be

nonempty: a set containing $1$ and another element $t$ has the collision

$\{1,t\}$ versus $\{t\}$.

For $n\le N$, let $\nu(n)$ be its vector of prime valuations, and let

\[ V_N=(\nu(1)\ \nu(2)\ \cdots\ \nu(N)). \]

Signed-relation lemma (a). A set $A\subseteq[1,N]$ is bad if and only

if there is a vector

\[ z\in\{-1,0,1\}^N,\qquad \operatorname{supp}z\subseteq A,\qquad V_Nz=0,\qquad {\bf1}^{T}z\ne0. \]

Proof. Given equal subset products, cancel their intersection. Put $z_n=1$

on the remaining left subset, $-1$ on the remaining right subset, and zero

elsewhere. Equality of all prime valuations is $V_Nz=0$, and the difference

of subset sizes is ${\bf1}^{T}z$. The converse reverses this construction.

Define the obstruction hypergraph $\mathcal H_N$ on $[1,N]$ whose edges

are the supports of these bad signed relations. Then

\[ \boxed{M(N)=N-\tau(\mathcal H_N)}, \tag{1} \]

where $\tau$ is the minimum transversal (hitting-set) number. This is an

exact reduction, not a relaxation.

Private-prime lemma (a). A prime $p>N/2$ is an isolated vertex of

$\mathcal H_N$. Indeed, $p$ is the only integer at most $N$ divisible

by $p$, so it cannot occur on either side of a cancelled disjoint product

identity. Such a prime may always be added to a valid set.

3. Exact computation

Exact table through $N=25$

The standalone checker gives the following table. Every entry in this

subsection is (d).

| $N$ | $M(N)$ | one maximum set |

|---:|---:|:---|

| 2 | 1 | $[2,2]$ |

| 3 | 2 | $[2,3]$ |

| 4 | 3 | $[2,4]$ |

| 5 | 4 | $[2,5]$ |

| 6 | 4 | $[3,6]$ |

| 7 | 5 | $[3,7]$ |

| 8 | 6 | $[3,8]$ |

| 9 | 6 | $[4,9]$ |

| 10 | 7 | $[4,10]$ |

| 11 | 8 | $[4,11]$ |

| 12 | 8 | $[5,12]$ |

| 13 | 9 | $[5,13]$ |

| 14 | 9 | $[6,14]$ |

| 15 | 10 | $[6,15]$ |

| 16 | 10 | $[7,16]$ |

| 17 | 11 | $[7,17]$ |

| 18 | 11 | $[8,18]$ |

| 19 | 12 | $[8,19]$ |

| 20 | 13 | $[8,20]$ |

| 21 | 13 | $[9,21]$ |

| 22 | 13 | $[10,22]$ |

| 23 | 14 | $[10,23]$ |

| 24 | 15 | $[10,24]$ |

| 25 | 15 | $[11,25]$ |

Here $[u,v]$ means every integer from $u$ through $v$. The fact that a

maximum set happens to be a terminal interval throughout this range is only

a computed observation; I do not extrapolate it.

Compact certificate for $M(20)=13$

The lower bound is the set

\[ A_{20}=\{8,9,\ldots,20\}. \]

The checker enumerates its $2^{13}=8192$ subsets and confirms that each

exact product occurs at only one cardinality.

For the upper bound, the following 25 unequal-cardinality identities form a

covering certificate. A 14-subset of $[1,20]$ cannot contain the union of

the two sides of any line.

empty product = 1
3·4 = 12                    2·6 = 12
2·7 = 14                    3·5 = 15
2·8 = 16                    3·6 = 18
2·9 = 18                    4·5 = 20
3·7·8 = 12·14               5·6·7 = 14·15
4·7·8 = 14·16               4·6·10 = 15·16
4·7·9 = 14·18               5·6·9 = 15·18
4·8·9 = 16·18               3·6·10 = 9·20
3·10·12 = 18·20             5·7·9·12 = 14·15·18
6·7·8·12 = 14·16·18         6·7·8·10 = 12·14·20
5·8·10·12 = 15·16·20        6·8·9·10 = 12·18·20
7·8·9·10 = 14·18·20         6·7·10·12 = 14·18·20

For the first line, under the nonempty-products convention, any other

$t$ in the candidate supplies $\{1,t\}$ versus $\{t\}$.

The verifier checks each identity with exact integer arithmetic, then

enumerates all

\[ \binom{20}{14}=38{,}760 \]

candidate 14-subsets and confirms that every candidate contains at least one

listed support. Consequently $M(20)\le13$, while $A_{20}$ gives equality.

The compact certificate was discovered with a set-cover CP-SAT pass, but its

verification uses no solver.

How the full table is recomputed

The checker does not trust the displayed table.

1. It removes the private primes $13,17,19,23$ from $[1,25]$, leaving a

21-element core.

2. It enumerates all $2^{21}=2{,}097{,}152$ core subsets and groups them by

their exact integer product.

3. Whenever two masks in a group have different cardinalities, it cancels

their intersection by taking the XOR of the masks.

4. It retains all 823 inclusion-minimal obstruction supports.

5. For each $2\le N\le25$, it solves the exact minimum hitting-set problem

by branching on a shortest uncovered edge. Every hitting set must choose

some vertex of that edge, so these branches are exhaustive.

6. It directly re-enumerates subset products of the resulting maximum

witness.

On this VM the final run used exact Python integers, no third-party package,

and reported:

explicit N=20 certificate: PASS
full exact table: PASS (823 minimal obstructions at N=25)
certificate and signed-lattice time: 0.163 s
full-table time: 45.946 s
total time: 46.109 s
maximum resident memory: 203,352 KB

Standalone verifier:

erdos786_wave7l_verify.py.

4. Exact obstruction to the standard additive-function reduction

For $A=\{a_1,\ldots,a_m\}$, write

\[ L(A)=\ker_{\mathbb Z}V_A \]

for all integer relations among the valuation columns, and

\[ L_{\pm}(A)= \left\langle L(A)\cap\{-1,0,1\}^{m}\right\rangle_{\mathbb Z} \]

for the lattice generated by distinct-subset relations. Let

$\sigma(z)=\sum_i z_i$.

Extension criterion (a). If $A$ has the distinct-elements property and

\[ \operatorname{rank}L_{\pm}(A)=\operatorname{rank}L(A), \tag{2} \]

then there is a totally additive rational-valued function $f$ with

$f(a)=1$ for every $a\in A$.

Proof. The distinct-elements property says that $\sigma$ vanishes on every

generator of $L_{\pm}(A)$. Under (2), $L_{\pm}(A)$ has finite index in

$L(A)$. Hence for every $z\in L(A)$, some positive multiple $qz$ lies

in $L_{\pm}(A)$, so $q\sigma(z)=0$ and $\sigma(z)=0$. Therefore

\[ F(V_Ax)=\sigma(x) \]

is a well-defined homomorphism on the lattice generated by the columns.

Extend $F$ linearly over the rational prime-valuation space and put

$f(n)=F(\nu(n))$. Then $f(xy)=f(x)+f(y)$ and $f(a_i)=1$.

Conditional consequence (b). If one could prove (2) for every

sufficiently dense candidate $A$, the published

Erdős--Ruzsa--Sárközy level-set theorems would give a fixed finite density

gap (and the corresponding infinite density bound). Thus (2), or an adequate

dense-set substitute for it, precisely identifies what the familiar

additive-function route still needs.

The criterion cannot hold automatically:

(a) $A=\{2,4\}$ has no unequal-cardinality collision between

distinct subsets, but $2\cdot2=4$. A totally additive $f$ with

$f(2)=f(4)=1$ would give $1=f(4)=2f(2)=2$, impossible.

(d) For the exact optimum $A_{20}=\{8,\ldots,20\}$, the verifier

computes

\[ \operatorname{rank}V_A=8,\qquad \dim_{\mathbb Q}\ker V_A=5,\qquad \operatorname{rank}_{\mathbb Q}\langle L(A)\cap\{-1,0,1\}^{13}\rangle=4. \]

It generates 2,688 signed subset relations; all are balanced. The missing

kernel direction is witnessed by the unbalanced repeated relation

$8^4=16^3$.

This rank-one defect is a concrete explanation of why replacing “distinct

subsets” by “repetitions allowed” loses essential information even in the

small exact optimum.

5. What remains and cost of pushing the computation

The asymptotic problem remains open.

The exact finite target is now the transversal problem (1). To answer the

finite question negatively one needs a uniform theorem

\[ \tau(\mathcal H_N)\ge cN \]

for some fixed $c>0$; to answer it affirmatively one needs transversals of

size $o(N)$. The additive-function machinery would obtain a gap after an

extension result such as (2), but the examples above show that no

unconditional extension lemma is possible.

Tao's comment suggests another precise sufficient route (c): construct a

probability measure contiguous with uniform measure on $[1,N]$ under which

an unequal-length distinct-factor collision occurs with positive probability

and remains positive after conditioning away any $o(N)$ exceptional set.

No such robust collision lemma is presently supplied by the cited papers.

The current exact enumerator scales as $2^{|C_N|}$, where $C_N$ is the

non-private core. At $N=25$, $|C_N|=21$. At $N=30$, merely removing

private primes leaves 26 vertices, a factor $2^5=32$ increase before the

superlinear collision-pair and hitting-set work. Extrapolating the measured

run gives roughly 0.5--2 single-core hours and 8--16 GB RAM for $N=30$;

at a typical \$0.05--\$0.15 per core-hour the CPU charge is only

\$0.03--\$0.30, but memory is the practical constraint. I did not run this

because it exceeds the requested few-CPU-minute budget and cannot settle the

uniform asymptotic step.

PARTIAL: For the distinct-elements problem, proved computationally that $M(20)=13$, recomputed the exact table $M(N)$ for $2\le N\le25$, and isolated the one-rank signed-relation defect that blocks the published additive-function machinery; the uniform density question remains open.

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