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

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.

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Problem 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).

2What counts as a solution

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

1Status

Saved packet · July 25, 2026

What counts as a solution

Packet-reported 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.

This research-packet status has not passed editorial review.

1Packet records

Show recorded summaries

Record	Kind	Assessment
A displayed 71-set has 2,556 distinct unordered pair products; the complete collision-hypergraph LP gives the integer upper bound 145.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
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 replay is recorded for this computation. Inspect the replay record for its procedure and scope. 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 →
Exact enumeration confirms that every one of the set's 2,556 unordered pair products is different.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
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 replay is recorded for this computation. Inspect the replay record for its procedure and scope. 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 →
Primary and modern sources study the asymptotic extremal function, while the focused audit found no exact table for n=200.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
Python enumerates every collision, verifies the 71-set, hash-binds the hypergraph, and solves its rational relaxation.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
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 Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. 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 material

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

Original intake status. Status remains unverified. Multiplicative Sidon subsets of intervals are studied asymptotically, and the exact value at 200 may be tabulated.

Build the conflict hypergraph from nontrivial equalities ab=cd and solve maximum independent set. Prime-factor exponent vectors support fast equality checks.
Trap: pairwise coprimality is sufficient only for a much smaller family. Distinct ordinary differences or sums say nothing about repeated products.

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 connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemLargest multiplicative Sidon subset of the first 200 integers

1 record outside this overview

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

All 2 recorded relations between these records and the problem

2See also

Simultaneous additive and multiplicative Sidon sets in F_101multiplicative combinatorics
Existence of a fourteen-point two-fold difference packing modulo 100sidon type sets
Most lattice points with all pairwise slopes distinct in a ten by ten gridsidon type sets

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Largest multiplicative Sidon subset of the first 200 integers.” TheoremDB. P2664. Problem statement; statement text SHA-256 058dccc04c3766e4d0fc465e1d3b7c7775fa70aadc42b3efd6cf47a395ab7803. https://theoremdb.org/statement/?ref=P2664

BibTeX

@misc{theoremdb-problem-058dccc04c3766e4d0fc465e1d3b7c7775fa70aadc42b3efd6cf47a395ab7803,
  title = {{Largest multiplicative Sidon subset of the first 200 integers}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 058dccc04c3766e4d0fc465e1d3b7c7775fa70aadc42b3efd6cf47a395ab7803},
  url = {https://theoremdb.org/statement/?ref=P2664}
}

Plain text: Built Markdown snapshot

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

1Lean verification

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 · reference source · arXiv:1808.06182, version checked 2026-07-25 · checked 2026-07-25Source use: citation only.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.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.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. ↗journal article · primary source · author-archive scan of the published paper · checked 2026-07-28Source use: original summary.For Largest multiplicative Sidon subset of the first 200 integers: Introduces multiplicative Sidon sets and proves the original bounds above the prime-counting term.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. ↗journal article · primary source · author-archive scan of the published paper · checked 2026-07-28Source use: original summary.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.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

1Problem setup

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Problem setup

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance