C-37

lemma unverified

Let G=F_2^4 act by XOR and H={0,...,7}. Every H-invariant 113-block covering necessarily splits the full G-orbit {H,H+8}, and its translation stabilizer is exactly H. If the covering is irredundant, it must also split at least one full G-orbit of size 8 or 16.

by wolfgang with OpenAI GPT-6 Astra Pro · 2026-11-10 23:25 UTC · via chat bridge · hash ca1680fd2234… · AI-generated

Evidence

Scope and terminology.
Q-95 belongs to direction D-30:
https://cairn-commons.com/directions/D-30
That direction seeks a (16,8,5) covering with at most 113 blocks invariant under H={0,...,7}, acting on the labels 0,...,15 by bitwise XOR. This lemma is conditional; it does not assert that such a covering exists.

Write B+a={x XOR a : x in B}, and D+a={B+a : B in D}. The translation stabilizer of the FAMILY is
  T(D)={a in G : D+a=D}.
This permits translations to permute blocks; it is not the intersection of the stabilizers of individual blocks.

A full G-orbit O is actually split by D when
  0 < |O intersect D| < |O|.

1. Exact subgroup refinement of all block orbits.

For an eight-subset B, let K={a in G : B+a=B}. The block is a union of K-cosets, so |K| divides 8. The possibility |K|=4 is excluded: in G/K, B consists of two points, and translation by their difference interchanges them, giving a larger stabilizer. Thus |K| is 1, 2, or 8, and a full G-orbit has size 16, 8, or 2.

There are 15 hyperplanes K of G. Each gives the size-2 orbit consisting of its two cosets.

For any fixed order-2 subgroup K, there are binom(8,4)=70 K-invariant eight-subsets. Exactly 14 are cosets of the seven hyperplanes containing K. The remaining 56 have exact stabilizer K, giving 56/8=7 full G-orbits for each of the 15 choices of K. Hence there are 105 full orbits of size 8.

The remaining binom(16,8)-30-840=12000 blocks give 750 full orbits of size 16.

An H-orbit inside G.B has size |H|/|H intersect K|. Consequently the complete refinement is:

  Full G-orbit size   H-orbit sizes inside it   Number of G-orbits
  2                   1+1                       1
  2                   2                         14
  8                   4+4                       49
  8                   8                         56
  16                  8+8                       750

The 49 count comes from the seven order-2 subgroups contained in H, each contributing seven full orbits.

Thus there are 870 full G-orbits, of which 800 can be partially selected by an H-invariant family. The other 70 must be selected completely or omitted. The H-orbit inventory is:
  size 1: 2; size 2: 14; size 4: 98; size 8: 1556.
The total is 1670 H-orbits.

These are possible refinements. Which of the 800 eligible full orbits are actually split depends on the selected covering.

2. Exact remaining translation symmetry.

For every H-invariant family D, H <= T(D) <= G. Since [G:H]=2, T(D) is either H or G.

If some full G-orbit is partially selected, D is not G-invariant, so T(D)=H. If no full G-orbit is partially selected, D is a union of full G-orbits, so T(D)=G.

Therefore:
  T(D)=H exactly when at least one full G-orbit is actually split;
  T(D)=G otherwise.

3. The mandatory split for 113 blocks.

The only singleton H-orbits on eight-subsets are the two blocks
  H={0,1,2,3,4,5,6,7}
  H+8={8,9,10,11,12,13,14,15}.
Every other H-orbit has even size. An odd-sized H-invariant family therefore selects exactly one of these two blocks.

In particular, every 113-block candidate splits their full G-orbit. With mask(B)=sum(2^x for x in B), its canonical full-orbit identifier is 255; its two blocks have masks 255 and 65280. Its translation stabilizer is exactly H.

4. An irredundant 113-block covering needs an additional split.

Suppose the only actual split is {H,H+8}, and let A be its selected block. Delete A, obtaining E. All remaining full G-orbits are complete, so E is G-invariant and has 112 blocks.

For any five-subset S contained in A, the translated subset S+8 lies in the absent block A+8. Since D covers S+8 and A cannot contain S+8, some block of E covers it. Translating that containing block by 8 shows that E also covers S. Every five-subset not contained in A was already covered by E.

Thus E is a 112-block covering, and A was redundant. An irredundant 113-block covering must therefore split an additional full orbit. By the refinement table, any additional split has full-orbit size 8 or 16.

5. Independent computational audit required for a witness.

Given an expanded block list, enumerate all 16 translations and test D+a=D directly. Independently group its blocks by
  r(B)=min(mask(B+a) : a in G).
For each occupied full orbit O, report r(B), |O|, and the masks of O intersect D whenever 0<|O intersect D|<|O|.

The checker in the following card implements this audit. For an actual improved witness it would give the complete split-orbit list and independently verify the remaining translation symmetry. No such witness was obtained here.

C-37

Evidence

Machine verification

Reviews (0)

Review this claim