No Improvement for R(3,16): A Budget-Limited Nonabelian Search Stalled at 81

Abstract

No improvement to the published lower bound for \(R(3,16)\) was obtained. A nonabelian program search made 42 model calls and evaluated 22 programs before stopping at the budget. The best proven order remained 81, establishing \(R(3,16) \ge 82\), equal to the bound in DS1 revision 18. The run rules out improvement only for the evaluated outputs, not for the nonabelian family as a whole.

Problem

A lower-bound construction for \(R(3,16)\) is a triangle-free graph with no independent set of size 16. The published bound is

\[ R(3,16) \ge 82, \]

reported in DS1 revision 18, dated 2026-04-24, Table IIa. Its proven construction order is 81. The computational objective was to exceed this published bound. No such improvement was obtained.

Method

The attempt used program search in the methodological line of AlphaEvolve and FunSearch. The evaluated strategy family was nonabelian Cayley-graph search.

The key idea of the best search program was as follows:

• filter the supplied group specifications to nonabelian groups;
• select a group deterministically from the seed;
• pair each possible connection with its inverse;
• seek a proper cyclic subgroup \(H=\langle h\rangle\) of index two;
• represent subgroup connections by an inverse-symmetric set \(A\) and the other coset by a set \(B\);
• enforce a sum-free condition on \(A\) and difference-compatibility between \(A\) and \(B\);
• use seeded shuffling and greedy additions to enlarge the candidate.

Representative fragments of the supplied program are:

const choices = (groups || []).filter(x => !x.abelian);

const choice = choices[(seed >>> 0) % choices.length];
const G = groupFromSpec(choice.spec);
const reps = pairRepresentatives(choice.spec);

if (h < 0 || p < 5 || n !== 2 * p) return null;

const ok = sumFree(A) && compatible(A, B);

Thus the program exploited a tightly structured connection-set representation rather than searching arbitrary graphs.

Results

The attempt stalled at the already proven order 81. None of the 22 evaluated programs produced a verified improvement. The negative result applies only to those evaluated outputs from the nonabelian strategy family; it is not an exhaustive exclusion of that family.

Verification

The measured verification endpoint was a best proven order of 81. A valid order-81 construction for this Ramsey cell establishes \(R(3,16) \ge 82\). This matches, but does not improve, DS1 revision 18.

The supplied best-program excerpt imports cayleyViolations, groupFromSpec, and pairRepresentatives, and explicitly enforces nonabelian selection, inverse pairing, and structural compatibility tests. The listing supplied for this report is truncated inside makeCandidate; therefore, this report does not claim an independent end-to-end rerun or verification beyond the recorded outcome.

Limitations

This computation searched one strategy family on one cell. It stopped because of the budget, so failure to find an improvement is not a proof that no improvement exists within the nonabelian family.

A vertex-transitive (circulant) construction is a restriction, not a general search. The nonabelian Cayley specialization used here is likewise restricted and does not range over arbitrary graphs. The structural requirement involving a cyclic subgroup of index two narrows the search further.

The supplied execution record does not contain the exact command or seed, and the supplied best-program listing is incomplete. Full reproduction from this report alone is therefore not possible.

Reproducibility

• Cell: R(3,16)
• Exact command: not recorded in the supplied execution data
• Seed: not recorded in the supplied execution data
• Model calls: 42
• Programs evaluated: 22
• Stop reason: budget
• Cost: $1.5667 of model tokens, 1171s wall clock

An exact command or seed cannot be supplied without fabrication. Reproduction requires recovering those missing values and the remainder of the truncated program from the original run artifacts.

References

[
  {
    "id": "10.37236/21",
    "title": "Small Ramsey Numbers, DS1 revision 18",
    "authors": "Stanisław P. Radziszowski",
    "year": 2026
  },
  {
    "id": "10.48550/arXiv.2603.09172",
    "title": "AlphaEvolve on Ramsey numbers",
    "authors": "Authors listed in the arXiv record",
    "year": 2026
  },
  {
    "id": "10.1038/s41586-023-06924-6",
    "title": "Mathematical discoveries from program search with large language models",
    "authors": "Bernardino Romera-Paredes et al.",
    "year": 2024
  }
]