[#P2664] Largest multiplicative Sidon subset of the first 200 integers

A neutral schematic of the objects and relations in the statement.

Problem. Determine the maximum size of \(A\subseteq\{1,\ldots,200\}\) such that the products \(ab\), indexed by unordered pairs \(a,b\in A\) with repetition allowed, are all distinct.

1Context

Every multiplicative collision has a canonical four-term factorization, making branch conflicts easy to record.

2Problem setup

Convention 1. Repetition allowed means squares a^2 are included.

Remark 1. Equivalently, ab=cd with a<=b and c<=d in A forces (a,b)=(c,d).

3What counts as a solution

Give a maximum subset and a complete upper-bound certificate for all subsets of the 200-element ground set.

1Status

Current status (The certified interval is 71 through 145). A displayed 71-set has 2,556 distinct unordered pair products; the complete collision-hypergraph LP gives the integer upper bound 145.

1Packet records

Record	Kind	Assessment
	Result	Reproduced
claim · Claim 1 A displayed 71-set has 2,556 distinct unordered pair products; the complete collision-hypergraph LP gives the integer upper bound 145. Relevance to this problem For Largest multiplicative Sidon subset of the first 200 integers, record ms200-claim-certified-interval-71-145 (“The certified interval is 71 through 145”) records a bound, answer, status fact, or structural consequence. The record states: A displayed 71-set has 2,556 distinct unordered pair products; the complete collision-hypergraph LP gives the integer upper bound 145. Evidence ReproducedA computation someone reran from the artifact on this page. Record state reported Scope multiplicative Sidon subsets of the positive integers 1 through 200, with squares included among the unordered pair products Details Write \(M(200)\) for the largest size in the question. The present computation certifies \[ 71\le M(200)\le145. \] The lower bound is attained by the displayed set in `ms200-claim-verified-71-set`. Its \(\binom{71+1}{2}=2556\) unordered products, including all squares, are distinct. For the upper bound, generate one forbidden hyperedge for every two distinct unordered pairs \(\{a,b\}\) and \(\{c,d\}\) with \(ab=cd\). After duplicate removal, the complete hypergraph has 20,111 edges: 248 triples and 19,863 four-sets. Every valid set is an independent set of this hypergraph. Relaxing its incidence vector to \(0\le x_i\le1\) and imposing \[ \sum_{i\in E}x_i\le \|E\|-1 \] for every collision edge \(E\) gives the exact rational optimum \(291/2\). An integral solution therefore has size at most 145. This leaves a gap of 74. The exact finite value remains unresolved in this record. The upper calculation is a relaxation certificate, rather than a completed integer branch-and-bound proof. Open full record →
	Result	Reproduced
claim · Computation 1 Exact enumeration confirms that every one of the set's 2,556 unordered pair products is different.^[1] Relevance to this problem For Largest multiplicative Sidon subset of the first 200 integers, record ms200-claim-verified-71-set (“A 71-element multiplicative Sidon set”) records a bound, answer, status fact, or structural consequence. The record states: Exact enumeration confirms that every one of the set's 2,556 unordered pair products is different. Evidence ReproducedA computation someone reran from the artifact on this page. Record state established Scope all unordered pairs with repetition from the displayed 71-element subset of 1 through 200 Sources Reference 1 Details The set \[ \begin{split} A=\{&1,12,17,31,35,40,41,43,49,52,54,55,58,71,73,81,83,86,89,96,\\ &101,103,107,109,113,114,117,118,119,121,125,127,131,133,134,137,\\ &138,139,143,145,148,149,151,153,157,158,159,163,164,167,168,170,\\ &173,174,176,179,181,182,183,184,185,186,188,191,193,194,195,197,\\ &198,199,200\} \end{split} \] has 71 elements. Direct integer enumeration of all pairs \(a\le b\) in \(A\) produces 2,556 products and 2,556 distinct values. Thus \(A\) is multiplicative Sidon under the question's convention, which includes squares. The canonical space-separated set has SHA-256 digest `87c37bb973034570880b4c3a868eaf2a20ab69d25872f48a545fe2e9a0716db3`. The sorted product list has digest `2c893b6f16e7f5b02675d9d78bf06467300d5437d6729334d35473e816cc5c20`. Related: Claim 1 Open full record →
	Trace	Supported
attempt · Route 1 Primary and modern sources study the asymptotic extremal function, while the focused audit found no exact table for n=200.^[1][2][3] Relevance to this problem For Largest multiplicative Sidon subset of the first 200 integers, record ms200-attempt-literature-and-exact-search-audit (“The literature gives asymptotics; the finite exact search remains incomplete”) documents a concrete method, search boundary, or failed route. The record states: Primary and modern sources study the asymptotic extremal function, while the focused audit found no exact table for n=200. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2, Reference 3 What happened Erdős introduced this extremal problem in 1938. His original paper gave a construction above \(\pi(n)\) by a lower-order term and an upper bound \(\pi(n)+O(n^{3/4})\). His 1969 paper sharpened the order, proving \[ s(n)=\pi(n)+\Theta\!\left(\frac{n^{3/4}}{(\log n)^{3/2}}\right). \] Liu and Pach restate this history in their 2018 paper and study the number of multiplicative Sidon subsets. Their introduction and bibliography identify the two primary Erdős papers. None of these sources tabulates \(s(200)\). A focused search for exact finite tables, the phrase `multiplicative Sidon`, and \(s(200)\) found asymptotic and generalized results. It found no published exact value at 200. A direct Boolean model of the 20,111 forbidden edges was also tried locally. It reproduced the 71 lower bound, while an attempted proof at the neighboring upper threshold did not finish within the allotted run. The retained LP computation gives a rigorous upper bound and records the remaining gap without claiming an exact solution. Open full record →
	Artifact	Reproduced
artifact · Artifact 1 Python enumerates every collision, verifies the 71-set, hash-binds the hypergraph, and solves its rational relaxation.^[1] Relevance to this problem For Largest multiplicative Sidon subset of the first 200 integers, record ms200-artifact-construction-and-lp (“Construction verifier and exact rational LP replay”) supplies evidence or a replay used to check the packet. The record states: Python enumerates every collision, verifies the 71-set, hash-binds the hypergraph, and solves its rational relaxation. Evidence ReproducedA computation someone reran from the artifact on this page. Record state available Scope all 20,100 unordered pairs in the ground set 1 through 200, every resulting product collision, and the full 200-variable collision-hypergraph LP Sources Reference 1 Entry point `join source_lines with newline and run with python3` Runtime CPython 3 with z3-solver 5.0.0 Details The program first checks the lower-bound set using integer multiplication. It then groups all \(20,100\) ground-set pairs by product. Every pair of distinct representations yields a three- or four-vertex forbidden edge. Sorting and hashing all 20,111 distinct edges fixes the exact hypergraph used by the upper calculation. The final block asks Z3's exact rational optimizer to maximize the sum of 200 real variables under the box and hyperedge constraints. It asserts the optimum \(291/2\), then emits a canonical JSON report. On the audited installation, Z3 5.0.0 completed this relaxation in about 28 seconds. The report has SHA-256 digest `68e7d07943110a09a301151769f2d3d750b42f35402796bd36204588ddc487a0`. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. UNKNOWN as of 2026-07-25. A displayed 71-set has 2,556 distinct unordered pair products; the complete collision-hypergraph LP gives the integer upper bound 145. The checked sources do not settle the full acceptance condition.

The dated packet audit checked the exact title, parameter, and the terminology used by the cited primary literature.
The strongest recorded neighboring result is: A displayed 71-set has 2,556 distinct unordered pair products; the complete collision-hypergraph LP gives the integer upper bound 145.
The controlled TheoremDB corpus was checked for equivalent formulations and contains no duplicate published target.

Recorded example 1. A verified 71-set is {1,12,17,31,35,40,41,43,49,52,54,55,58,71,73,81,83,86,89,96,101,103,107,109,113,114,117,118,119,121,125,127,131,133,134,137,138,139,143,145,148,149,151,153,157,158,159,163,164,167,168,170,173,174,176,179,181,182,183,184,185,186,188,191,193,194,195,197,198,199,200}.

Computational notes

Fifty thousand seeded random greedy orders were attempted before the run was stopped after reaching size 71. Exact reconstruction formed all 2556 unordered products, including squares, and confirmed that they were distinct.

How the 4 records connectTyped relations and evidence flow

ProblemLargest multiplicative Sidon subset of the first 200 integers

Claim 1The certified interval is 71 through 145in this packetReproduced
Computation 1A 71-element multiplicative Sidon setsupportsReproduced
Artifact 1Construction verifier and exact rational LP replayverifiesReproduced

1 record with no typed link to the problem

Route 1The literature gives asymptotics; the finite exact search remains incomplete

2See also

Most lattice points with all pairwise slopes distinct in a ten by ten gridsidon type sets
Existence of a fourteen-point two-fold difference packing modulo 100sidon type sets
Union-closed sets conjectureextremal set theory

How to cite

TheoremDB contributors, “Largest multiplicative Sidon subset of the first 200 integers,” TheoremDB research memory, snapshot of July 25, 2026. https://theoremdb.org/statements/multiplicative-sidon-200

This page as plain text: multiplicative-sidon-200.md

This problem includes 4 records joined by 4 typed links, sourced from arxiv.org^[1], current as of July 25, 2026.

1References

Packet source. Hong Liu and Péter Pál Pach, “The number of multiplicative Sidon sets of integers”. arXiv:1808.06182 (2018). Hong Liu and Péter Pál Pach, The number of multiplicative Sidon sets of integers, introduction, equation (1.1), and references [8] and [9]; Introduction, definition of s(n), equation (1.1), and references [8] and [9]. ↗ open copy ↗preprint · primary source · arXiv:1808.06182, version checked 2026-07-25 · checked 2026-07-25Source use: original summary.The literature gives asymptotics; the finite exact search remains incomplete. Primary and modern sources study the asymptotic extremal function, while the focused audit found no exact table for n=200.Also cited at Pages 1 and 19, including the full citations of the 1938 and 1969 Erdős papers.Also cited at Introduction, definition of s(n), equation (1.1), and references [8] and [9]; open-copy locator: Pages 1 and 19, including the full citations of the 1938 and 1969 Erdős papers.Also cited at Candidate construction exhaustively replayed in ms200-artifact-construction-and-lp.Also cited at Hong Liu and Péter Pál Pach, The number of multiplicative Sidon sets of integers, introduction, equation (1.1), and references [8] and [9].Also cited at Inline Python exhaustive verifier with Z3 exact rational optimization, executed 2026-07-25.For Largest multiplicative Sidon subset of the first 200 integers: The literature gives asymptotics; the finite exact search remains incomplete. Primary and modern sources study the asymptotic extremal function, while the focused audit found no exact table for n=200.Source named by the research packet.
Paul Erdős, On sequences of integers no one of which divides the product of two others and some related problems, Mitt. Forsch.-Inst. Math. Mech. Univ. Tomsk 2 (1938), 74-82. Section 2, especially the upper and lower estimates for B-sequences. ↗preprint · primary source · PDF checked 2026-07-25 · checked 2026-07-25Source use: original summary.Introduces multiplicative Sidon sets and proves the original bounds above the prime-counting term.For Largest multiplicative Sidon subset of the first 200 integers: Introduces multiplicative Sidon sets and proves the original bounds above the prime-counting term.
Paul Erdős, On some applications of graph theory to number theoretic problems, Publications of the Ramanujan Institute 1 (1969), 131-136. Opening theorem and equation (2) on pp. 131-132. ↗preprint · primary source · PDF checked 2026-07-25 · checked 2026-07-25Source use: original summary.Sharpens the multiplicative Sidon extremal function to the stated order of its lower-order term.For Largest multiplicative Sidon subset of the first 200 integers: Sharpens the multiplicative Sidon extremal function to the stated order of its lower-order term.

CC0 finite multiplicative-packing target.

[#P2664] Largest multiplicative Sidon subset of the first 200 integers

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance