google-deepmind / google-deepmind/alphaevolve_repository_of_problems
Problem 42 (sum-difference constant): a construction suggesting C = 2, and a note on prior art
- Dominant language
- Jupyter Notebook
- Stars
- 236
- Forks
- 15
- PR merge metrics
- No merged PRs in 30d
Description
Two notes on Problem 42, offered for scrutiny. The first is a large claim
and we would genuinely welcome having it torn apart.
1. We believe the constant is 2. Combining a construction with Kravitz's
recent Prop. 2.1 (arXiv:2606.27087: for every ε > 0 there exist q and
S ⊆ ℤ_q with S + S = ℤ_q and |S − S| ≤ εq), we obtain sets with g(A) → 2,
matching Ruzsa's upper bound. In brief: take a thin additive basis B of
[0, m²] blown up by width 2q; keep only elements whose residue mod q lies
in S (a sparse "ghost" that still carries every sum); add one interval of
4q consecutive integers in a gap. Then |A+A|/|A| ≳ m² while
|A−A|/|A| ≲ 9m, so g(A) → 2. A concrete instance independent of Prop. 2.1
certifies C ≥ 1.6269.
We also record: (i) an elementary theorem that any set whose missing
differences all exceed half its diameter has |A−A| ≥ diam(A) + |A|,
capping all such "single-scale" constructions at
sup_κ ln(2+4κ)/ln(2+2κ) = 1.2938…, which appears to explain why known
methods converge there; and (ii) a related conjecture (that sets with
*every* sum present are capped at that same 1.2938) proven in the dense
case and the top-deletion case and verified by exact search through
diameter 59, but not closed in the sparse-interior case.
2. Separately, the stated baseline appears to predate the best known
result: Penman & Wells, "On sets with more restricted sums than
differences" (INTEGERS 13 (2013), A57, Thm 21), give an explicit family
with g → ln(32/5)/ln(26/5) ≈ 1.12594 in exactly this normalization,
above both the stated 1.0598 and the AlphaEvolve value 1.1219 (Staps,
INTEGERS 15 (2015) A42, records it as best known).
On provenance and reliability: this was produced with heavy use of AI
systems (Anthropic's Claude, cross-checked by an independent OpenAI
model), including the constructions themselves. Every count and lemma
was independently re-derived and rebuilt by adversarial verification
passes across the two, but no human mathematician has reviewed it, and
we may well be wrong. Attached (materials.zip): the full write-up, a
self-contained review packet with the exact data needed to check the
claims, an enumerable counterexample to the natural strong form (23,646
integers, four independent counters), and a small script anyone can run
in a second that certifies g > 1.163.
Grateful for any error, gap, or missed reference (particularly anyone
who can say whether C = 2, or these constructions, are already in the
literature under different language).
[materials.zip](https://github.com/user-attachments/files/30597718/materials.zip)
Contributor guide
Research direction
Download materials.zip and begin with the self-contained review packet and the runnable certification script. Check the proposed construction, the cited Penman & Wells and Staps results, and the enumerable counterexample; the work is done only when the claims and baseline can be independently verified or a specific gap is documented.
Written by the indexing model from the issue text.
Assessment
- Domain
- content
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 20/100