google-deepmind / google-deepmind/alphaevolve_repository_of_problems

Problem 42 (sum-difference constant): a construction suggesting C = 2, and a note on prior art

Open
#5 1 comment 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.