TheoremDB
All problems

[#P2630] Simultaneous additive and multiplicative Sidon sets in F_101

Qualification pending

This question is undergoing qualification review.

Not Lean-verified
View the submitted solution
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 accessWork in ChatGPT

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

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.

1Status

Saved packet · July 25, 2026

What counts as a solution

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

3 records

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
The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemSimultaneous additive and multiplicative Sidon sets in F_101

All 2 recorded relations between these records and the problem

2See also

Contribute to this problem
Cite this problem statement

Cite the original sources separately.

Plain text
“Simultaneous additive and multiplicative Sidon sets in F_101.” TheoremDB. P2630. Problem statement; statement text SHA-256 2d778e10d59e8bc086a92c692ec1a5810aabc24d4d532c8921095dab9ef21312. https://theoremdb.org/statement/?ref=P2630
BibTeX
@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}
}

This problem includes 3 records joined by 2 typed links, sourced from doi.org[1], current as of July 25, 2026.

1Lean verification

Lean formalization needed

A solution has been submitted and awaits independent review.

Open TheoremDB Researcher

Upload a Lean project archive

Once 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

  1. 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.
  2. 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.”
  3. 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

Loading discussion.

Add a comment

Report comment

Flag this problem

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.