Exhaustion of the x ↦ 26x and x ↦ 41x invariant spaces for R(3,20) on 111 vertices

# Result

The published lower bound for the Ramsey cell R(3,20), recorded in DS1 rev#18 dated 2026-04-24, is

R(3,20) >= 112.

It is witnessed by a graph on 111 vertices. We searched two precisely defined spaces of Cayley graphs on Z_111. Neither search produced a (3,20)-free graph, and therefore this computation does not improve the published Ramsey bound.

In the first space, connection sets were required to be invariant under the multiplier map x ↦ 26x. This map partitions the 55 inverse-pair representatives into 13 orbits. The non-empty unions of these orbits give 8191 candidates. All 8191 candidates were tested to completion across 3 independent shards. All 8191 were reached, none remained unresolved, and none was (3,20)-free. The best candidate had 33 violations.

In the second space, connection sets were required to be invariant under x ↦ 41x. Here the 55 inverse-pair representatives split into 7 orbits, giving 127 non-empty unions. All 127 candidates were tested to completion across 3 independent shards. All 127 were reached, none remained unresolved, and none was (3,20)-free. The best candidate had 72 violations.

A violation means either a copy of K_3 or an independent set of size 20. The reported result is negative but exhaustive within each stated candidate space.

# Method

For a group G and an inverse-closed connection set S, the Cayley graph Cay(G,S) has vertex set G, with vertices joined when their difference lies in S. In the present computation G is Z_111. Nonzero elements are handled through the 55 inverse pairs represented by x and -x, ensuring that the resulting circulant graph is undirected.

A multiplier acts on these inverse-pair representatives. Requiring S to be invariant under that multiplier means that S must be a union of complete multiplier orbits. Thus, after the orbit partition is computed, the candidate space is finite and explicit: every non-empty union of the orbit collection is enumerated. For x ↦ 26x this construction gives the stated 13 orbits and 8191 candidates; for x ↦ 41x it gives the stated 7 orbits and 127 candidates.

The graphs are vertex-transitive. In any Cayley graph, a clique can be translated so that one of its vertices is the identity. Consequently, determining whether Cay(G,S) contains K_s reduces to determining whether the neighbourhood of the identity contains K_{s-1}. For the present cell, this makes triangle detection a local computation in the identity neighbourhood and is the principal reduction that makes complete enumeration of these spaces affordable.

Each candidate was also tested for an independent set of size 20. A candidate was conclusively rejected as soon as any violation was found. A candidate was classified as unresolved only if its violation count returned as zero without the search completing. The unresolved count was 0 in each space. Thus the negative conclusion is not the result of stopping an unfinished search: every enumerated candidate received a conclusive outcome.

The enumeration was deterministic. No language model, randomness, or heuristic search produced the candidate counts, completion counts, unresolved counts, or violation figures. Re-running the same enumeration yields the same result.

# Why this space

Multiplier-invariant circulants form a mathematically natural restricted family. They replace arbitrary choices among inverse pairs by choices among multiplier orbits, imposing algebraic symmetry while leaving a finite family that can be enumerated exactly.

This restriction also has precedent in published Ramsey work. Paley graphs are exactly the graphs whose connection sets are the quadratic residues, and those sets are invariant under multiplication by any square. More generally, multiplier invariance is a standard source of structured, vertex-transitive candidates. It is therefore reasonable to ask whether the known 111-vertex scale for R(3,20) contains a witness with either of the specified multiplier symmetries.

The computation answers that limited question completely. No non-empty union of the x ↦ 26x orbits works, and no non-empty union of the x ↦ 41x orbits works.

# What this does not show

The multiplier-invariant spaces considered here are thin slices of the full connection-set space on Z_111. Exhausting them does not exhaust all circulant graphs on 111 vertices. In particular, a connection set that is not a union of the specified multiplier orbits is outside the enumeration and is not constrained by this result.

The computation also says nothing about non-circulant graphs on 111 vertices. The published witness establishing R(3,20) >= 112 need not have either multiplier symmetry and need not belong to either searched family. Its existence is fully compatible with the negative findings reported here.

Likewise, the result does not establish an upper bound for R(3,20), does not alter the lower bound, and does not show that multiplier-invariant searches using other multipliers must fail. It rules out exactly the two stated candidate spaces and no larger class. The counts of 33 and 72 describe the best candidates under the reported violation measure; they do not turn near misses into Ramsey witnesses.

# Reproduction

To reproduce the first enumeration, begin with Z_111 and form the 55 inverse-pair representatives of its nonzero elements. Apply multiplication by 26 modulo 111, identifying an image with its inverse-pair representative, and compute the resulting orbit partition. The partition must contain 13 orbits. Enumerate every non-empty union of those orbits, giving 8191 connection sets. For each connection set, construct Cay(Z_111,S), test for a K_3 using the identity-neighbourhood reduction, and test for an independent set of size 20. Record a conclusive rejection when either type of violation is found, and distinguish any incomplete zero result as unresolved. The expected totals are 8191 candidates reached and 0 unresolved, with no (3,20)-free candidate. The best reported violation count is 33.

Repeat the same procedure with multiplication by 41. The induced action on the 55 inverse-pair representatives must produce 7 orbits and hence 127 non-empty unions. The expected totals are 127 candidates reached and 0 unresolved, again with no (3,20)-free candidate. The best reported violation count is 72.

Each candidate list may be distributed across 3 independent shards, as in the reported computation, provided that every candidate is assigned and the completed shard outputs cover the entire deterministic enumeration. Reproduction is verified by matching the orbit counts, candidate counts, reached counts, unresolved counts, negative outcomes, and best violation figures stated above.

Machine-readable coverage record

Appended verbatim by the harness, not written by the drafting model. Re-run the enumeration to check it.

{
  "cell": [
    3,
    20
  ],
  "n": 111,
  "source_revision": "DS1 rev#18, 2026-04-24 (Radziszowski, Small Ramsey Numbers)",
  "improved": false,
  "spaces": [
    {
      "group": "Z_111",
      "invariant_under": "x -> 26x",
      "orbits": 13,
      "total_candidates": 8191,
      "reached": 8191,
      "unresolved": 0,
      "exhausted": true,
      "best_violations": 33,
      "best_set": [
        2,
        6,
        9,
        12,
        17,
        20,
        21,
        22,
        35,
        45,
        51,
        52
      ]
    },
    {
      "group": "Z_111",
      "invariant_under": "x -> 41x",
      "orbits": 7,
      "total_candidates": 127,
      "reached": 127,
      "unresolved": 0,
      "exhausted": true,
      "best_violations": 72,
      "best_set": [
        3,
        9,
        12,
        21,
        27,
        30,
        33,
        36,
        48
      ]
    }
  ]
}