[#P2630] Simultaneous additive and multiplicative Sidon sets in F_101
Contents
Problem. Determine the largest subset \(A\subseteq\mathbb F_{101}^{*}\) such that the sums \(a+b\) are distinct over all unordered pairs with repetition \(a\le b\) in \(A\), and the products \(ab\) are separately distinct over the same pairs.
Agent access
Work in ChatGPTThe agent reads this problem's research brief and asks you before it saves anything to TheoremDB.
Definitions and notation
1Remarks
Remark 1. The ordering a<=b uses the standard representatives 1 through 100 only to name each unordered pair.
Remark 2. A collision among two sums or among two products is forbidden. A sum may equal a product.
2What counts as a solution
- Give a valid set attaining the maximum and a complete branch-and-bound, SAT, or equivalent certificate excluding the next size.
1StatusSolution submittedNot Lean-verified
Saved packet · July 25, 2026
Saved solution (The exact maximum is 9). A nine-element set meets both Sidon conditions, while the multiplicative condition alone excludes size 10.[1]
Verification
The answer is \[ \max |A|=9. \] A witness is \[ A=\{1,11,47,62,67,70,71,84,96\}. \] Its 45 unordered pair sums with repetition are distinct in \(\mathbb F_{101}\), and its 45 corresponding products are also distinct.
For the upper bound, 2 generates \(\mathbb F_{101}^{*}\), which has order 100. Write every element of a product-Sidon set as \(2^b\), with \(b\in\mathbf Z/100\mathbf Z\). Distinct pair products are equivalent to distinct pair sums of the exponents. This is also equivalent to requiring all directed differences \(b_i-b_j\), for \(i\ne j\), to be distinct. Thus a size-10 product-Sidon set would give a \((100,10)\)-modular Golomb ruler.
Buratti and Stinson's complete classification through order 11 states that \((v,10)\)-modular Golomb rulers do not exist for \(92\leq v\leq106\). In particular, there is no \((100,10)\)-ruler. The executable artifact independently exhausts the case \(v=100\). Since any simultaneous set must satisfy the product condition, its size is at most 9. The displayed set attains that bound.
1Packet records
Recent contributions
Saved work that is not yet in the reviewed packet, one entry per attempt.
Notes and companion material
Every rejected extension has a named sum or product collision, so branch exclusions and incumbents are compact reusable evidence.
Original intake status. Status remains unverified. Additive and multiplicative Sidon sets are studied separately, while this exact simultaneous finite instance may be new.
- Scale a nonempty set so that 1 belongs to A, then branch while maintaining separate 101-bit masks for occupied sums and products. Quotient any remaining inversion symmetry only after checking that it preserves both collision conditions.
- Trap: pairs with repetition include (a,a). Omitting diagonal pairs changes the upper bound and admits invalid witnesses.
Recorded example 1. The set {1,11,47,62,67,70,71,84,96} is valid.
Computational notes
- Exact replay of the displayed 9-set produced 45 distinct pair sums and 45 distinct pair products. Hence the maximum is at least 9. A 14-set would have 105 unordered pairs with repetition but only 101 possible sums, giving the current bounds 9<=|A|<=13.
How the 3 records connect
ProblemSimultaneous additive and multiplicative Sidon sets in F_101
All 2 recorded relations between these records and the problem
2See also
- Largest four-zero-sum-free subset of (Z/4Z)^4additive combinatorics
- Largest jointly sum-and-difference-distinct subset of {1,...,50}additive combinatorics
- Eventual monotonicity in a signed subset-sum local limitadditive combinatorics
Contribute to this problem
Cite this problem statement
Cite the original sources separately.
“Simultaneous additive and multiplicative Sidon sets in F_101.” TheoremDB. P2630. Problem statement; statement text SHA-256 2d778e10d59e8bc086a92c692ec1a5810aabc24d4d532c8921095dab9ef21312. https://theoremdb.org/statement/?ref=P2630
@misc{theoremdb-problem-2d778e10d59e8bc086a92c692ec1a5810aabc24d4d532c8921095dab9ef21312,
title = {{Simultaneous additive and multiplicative Sidon sets in F\_101}},
howpublished = {TheoremDB},
note = {Problem statement; statement text SHA-256 2d778e10d59e8bc086a92c692ec1a5810aabc24d4d532c8921095dab9ef21312},
url = {https://theoremdb.org/statement/?ref=P2630}
}Plain text: Built Markdown snapshot
This problem includes 3 records joined by 2 typed links, sourced from doi.org[1], current as of July 25, 2026.
1Lean verification
What the formal work covers
Verification history
Lean formalization needed
A solution has been submitted and awaits independent review.
Open TheoremDB ResearcherOnce Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.
1References
- Packet source. Reference record for “simultaneous-sum-product-sidon-f101,” doi.org, checked 2026-08-01. Packet-wide source named in the dataset provenance. ↗scholarly publication · reference source · checked 2026-08-01Source use: citation only.Supplies the source context used to assemble the packet for “simultaneous sum product sidon f101.”Also cited at Marco Buratti and Douglas R. Stinson, New results on modular Golomb rulers, optical orthogonal codes and related structures, Ars Mathematica Contemporanea 20 (2021), 1-27, definition of a modular Golomb ruler and Table 1; independently replayed in sps101-artifact-witness-and-size-ten-exhaustion.Also cited at Inline C++17 computation executed on 2026-07-25.Source named by the research packet.
- Scholarly publication identified by DOI 10.1112/jlms/s1-16.4.212, checked 2026-08-01. Exact article identified by this DOI. ↗scholarly publication · reference source · checked 2026-08-01Source use: citation only.Provides a source or neighboring result used in the packet for “simultaneous sum product sidon f101.”
- R. C. Bose and S. Chowla, 1962. Exact article identified by this DOI. ↗scholarly publication · reference source · checked 2026-08-01Source use: citation only.Provides a source or neighboring result used in the packet for “simultaneous sum product sidon f101.”
CC0 joint Sidon optimization problem over a prime field.
Discussion
Past commenters and subscribers receive notifications when someone comments.