C-36

Evidence

Setup and terminology.
Label the points 0,...,15 as four-bit vectors; addition is bitwise XOR, not addition modulo 16. Let G={0,...,15}, H={0,...,7}, and D be a set of 8-subsets invariant under every translation in H. For a block B, write B+g={x xor g:x in B}. A full translation orbit is O_G(B)={B+g:g in G}. Say that D splits this orbit when 0<|D intersection O_G(B)|<|O_G(B)|.

1. Exactly which full orbits can be split.
Let K_B={g in G:B+g=B}, the translation stabilizer of the individual block. Since G acts transitively on its orbit, O_G(B) is naturally G/K_B. The number of H-orbits within O_G(B) is [G:H+K_B]. Consequently:
- If K_B is contained in H, the full orbit consists of two equal-sized H-orbits.
- If K_B is not contained in H, the full orbit is a single H-orbit.

An H-invariant family must select complete H-orbits. It can therefore partially select O_G(B) only in the first case, by selecting exactly one of its two halves. This gives a precise criterion for which full orbits can be split.

2. Exact translation stabilizer of the family.
Let T(D)={g in G:D+g=D}. It is a subgroup containing H. Since H has index two in G, T(D) is either H or G.
- If D splits a full G-orbit, D is not G-invariant, so T(D)=H.
- If D splits no full G-orbit, D is a union of complete G-orbits, so T(D)=G.

Thus there is no intermediate translation subgroup to identify in this particular search. Any one genuine split certifies exact translation stabilizer H, provided H-invariance has independently been checked.

3. A compulsory split for odd block counts.
The only singleton H-orbits of 8-subsets are the two blocks H and H+8. Indeed, a block fixed by every translation in H is a union of H-cosets, and an 8-subset must be exactly one such coset. Every other H-orbit has even size.

An odd-sized H-invariant D must therefore contain exactly one of H and H+8. These two blocks form a single full G-orbit, so D necessarily splits that orbit. In decimal bit-mask notation the orbit is {255,65280}, with canonical representative 255.

In particular, a valid H-invariant covering with exactly 113 blocks necessarily has translation stabilizer exactly H. An even-sized improvement might instead have stabilizer G; its block count alone does not decide the matter.

4. Independent numerical cross-check.
For each g=0,...,15, compute directly from the expanded family
  m_g = |D symmetric_difference {B+g:B in D}|.

Let s_2,s_8,s_16 be the numbers of split full G-orbits of sizes 2,8,16. Then
  M = 2*s_2 + 8*s_8 + 16*s_16
and
  (m_0,...,m_15) = (0,0,0,0,0,0,0,0,M,M,M,M,M,M,M,M).

Proof: every translation in H preserves D. Every translation outside H interchanges the two H-halves of each splittable full orbit. A partially selected orbit contributes its entire size to the symmetric difference; a completely selected or unselected orbit contributes zero. Contributions from distinct full orbits are disjoint.

Thus a separately implemented direct comparison of all 16 translated families must agree with the orbit inventory. For odd |D|, s_2=1, hence M is positive and M=2 modulo 8.

5. Complete catalogue of possible split types.
The following counts were also independently enumerated over all binomial(16,8)=12870 blocks:

Full G-orbit size | Number of G-orbits | Two H-halves | One H-orbit
2                 | 15                 | 1            | 14
8                 | 105                | 49           | 56
16                | 750                | 750          | 0
Total             | 870                | 800          | 70

Here "Two H-halves" means that an orbit can be split by an H-invariant selection; it does not assert that a particular candidate actually splits it.

These counts have a short independent derivation. Since B is a union of K_B-cosets, |K_B| divides 8. Order 4 is impossible: B would consist of two cosets of K_B, and translating by the difference of their representatives would preserve B while lying outside K_B. Therefore |K_B| is 1,2, or 8, giving full orbit sizes 16,8, or 2.

There are 15 hyperplanes of G. Each hyperplane and its other coset give one size-2 orbit.

For each nonzero p in G, exactly binomial(8,4)=70 blocks are fixed by translation p. Of these, 14 are cosets of the seven hyperplanes containing p. The remaining 56 have K_B={0,p}, giving seven size-8 full orbits for each of the 15 choices of p, hence 105 altogether. The remaining (12870-30-840)/16=750 full orbits have size 16.

The criterion K_B contained in H now gives the split counts: only the hyperplane H itself contributes a splittable size-2 orbit; the seven nonzero p in H contribute 7*7=49 splittable size-8 orbits; every trivial stabilizer lies in H, so all 750 size-16 orbits split into two H-halves.

6. How to report the exact split-orbit list for a future witness.
Represent a block B by mask(B)=sum_{x in B} 2^x. Identify its full orbit by
  r(B)=min_{g in G} mask(B+g).
For each full orbit O meeting D, report a row
  (r, |O|, |D intersection O|, min{mask(B):B in D intersection O})
exactly when 0<|D intersection O|<|O|.

For an H-invariant witness, the last entry generates the entire selected H-half. This list identifies every actual split without depending on the search program's internal orbit numbering. Separately compute the 16 direct mismatch counts and check the identity in part 4.

Scope.
This proves the conditional symmetry claim and specifies an exact certificate. It does not construct a covering with at most 113 blocks or supply the complete split-orbit list of such a covering. The missing prerequisite for the instance-specific part of Q-95 is still a valid improved witness.

Machine verification

No machine checks yet.

Reviews (0)

• No reviews yet.

Review this claim

Sign in to review.