# P2664: Largest multiplicative Sidon subset of the first 200 integers

- ID: `P2664`
- Reference: `multiplicative-sidon-200`
- Page: https://theoremdb.org/statements/P2664
- Record maturity: Reviewed problem with recorded work

## 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.

### Problem setup

- **Convention.** Repetition allowed means squares a^2 are included.
- **Remark.** Equivalently, ab=cd with a<=b and c<=d in A forces (a,b)=(c,d).

### What counts as a solution

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

## Status

A displayed 71-set has 2,556 distinct unordered pair products; the complete collision-hypergraph LP gives the integer upper bound 145.

## Work

### Evidence for the current status

**Claim 1 (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.

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.

### Background and intake notes

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: 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}.

### Other known results

- **Computation 1** (reproduced): Exact enumeration confirms that every one of the set's 2,556 unordered pair products is different. [1](#reference-1)

### Prior approaches

- **Route 1** (supported): Primary and modern sources study the asymptotic extremal function, while the focused audit found no exact table for n=200. [1](#reference-1) [2](#reference-2) [3](#reference-3)

### Runnable artifacts

- **Artifact 1** (reproduced): Python enumerates every collision, verifies the 71-set, hash-binds the hypergraph, and solves its rational relaxation. [1](#reference-1)

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `multiplicative-sidon-200`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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] https://arxiv.org/abs/1808.06182
   - 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
   - preprint; reference source; arXiv:1808.06182, version checked 2026-07-25; checked 2026-07-25
   - Open copy: https://www.ibs.re.kr/ecopro/wp-content/uploads/2022/01/Sidon-0818.pdf
   - Source 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.
   - Source named by the research packet.
2. <a id="reference-2"></a>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 https://www.renyi.hu/~p_erdos/1938-07.pdf
   - journal_article; primary source; author-archive scan of the published paper; checked 2026-07-28
   - Source 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.
3. <a id="reference-3"></a>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 https://www.renyi.hu/~p_erdos/1968-09.pdf
   - journal_article; primary source; author-archive scan of the published paper; checked 2026-07-28
   - Source 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.