Independent adversarial review — iteration 03
Date: 2026-11-04
Scope: finite, deterministic, one-shot, exact recovery; encoder knows g but not q in nonempty H; decoder knows z(g) and y=gq. This is an independent AI review, not external peer review.

VERDICT
The general graph equivalence and the proposed cyclic-interval optimum are correct under the stated assumptions. All independent exact checks passed. These are applications of established characteristic-graph coding and cycle-power coloring, not new general information-theoretic or graph-theoretic results.

GENERAL GRAPH
Put an edge between distinct g and k exactly when some q != r in H satisfy gq=kr. If adjacent transformations share a record, the same decoder input requires two outputs, impossible. Conversely, in any color class, a given output y has at most one originating q in H, so assigning that q defines a valid decoder on feasible inputs. The decoder can be defined arbitrarily on infeasible inputs because H is nonempty. Hence minimum record alphabet cardinality is exactly the chromatic number, and minimum fixed-length binary record length is ceil(log2 chi).

Do not replace this graph by the graph of all overlaps gH intersect kH. For nonregular actions a shared y can originate from the same q, and causes no decoding conflict. The problem is generally recovery of the function q=g^{-1}y, not recovery of g. For example, in the natural S3 action on {0,1,2}, H={0,1}, the identity and (1 2) overlap only at output 0 with origin 0; they may share a record. Ordinary recovery-of-g side-information coding would separate them. In a regular action, distinct g and k cannot map the same q to the same y, and the two notions coincide.

If G is an abstract group whose action is nonfaithful, elements with identical induced permutations need not be distinguished. Full H=Q forces the complete graph only after quotienting by the action kernel (equivalently, using the image permutation group). The generic graph theorem itself remains correct without faithfulness. Restricting the allowed transformations to a subset is valid via the corresponding induced graph; the interval formula below assumes every cyclic shift is allowed.

CYCLIC INTERVAL PROOF
Let n>=1, 1<=h<=n, Q=G=Z_n and H={0,...,h-1}. Two shifts conflict exactly when their nonzero difference lies in {+/-1,...,+/-(h-1)} modulo n.

An independent set with m>=2 members has clockwise gaps all at least h, so mh<=n. For a singleton the same bound follows from h<=n. With k=floor(n/h), the k points 0,h,...,(k-1)h attain the bound, including the wrap gap n-(k-1)h>=h. Thus alpha=k and chi>=ceil(n/k).

Set c=ceil(n/k), d=kc-n, so 0<=d<k. Divide 0,...,n-1 into k consecutive rows: d rows of length c-1 and k-d rows of length c. Color a vertex by its zero-based column in its row. Every row length is at least h: c>=h; if c=h, n=kh and d=0, while c>h gives c-1>=h. For any fixed column, consecutive occurrences around the circle have clockwise separation equal to the sum of the lengths of the intervening rows, at least h. Every color class is therefore independent. A row of length c exists since d<k, so exactly c colors are used. This proves chi=ceil(n/floor(n/h)) for every allowed n,h.

Do not use the superficially similar coloring shift modulo c without justification. At n=10,h=3,c=4 the color class {0,4,8} has a wrap gap 2 and is invalid. The balanced-row code is (0,1,2,0,1,2,0,1,2,3), valid with four colors. Its two-bit fixed record is strictly shorter than the four bits needed to distinguish ten transformations. This is compression enabled by the restricted prior H, not a contradiction of the unrestricted-state lower bound.

INDEPENDENT COMPUTATION
reviewer_checks.py uses only Python's standard library. Edges are built directly from conflicting decoder histories, without relying on the interval difference-set simplification. A separate exact backtracking coloring search determines chi. A direct decoder-table test checks each constructive encoding.
Results, reproduced in reviewer_checks.json:
- 78 interval cases (every 1<=h<=n<=12): exact chi equals formula and balanced-row records decode correctly.
- 247 arbitrary nonempty subsets H of Z_n (every n<=7): exact optimal colorings decode correctly.
- 8,967 ternary encoders over every nonempty H for n<=5: direct decoder consistency agrees exactly with proper coloring.
- Script exited successfully; status PASS. Enumeration is corroboration, not the proof of the infinite family. General nonregular actions were reviewed analytically, not exhaustively enumerated by this script.

LITERATURE AND NOVELTY
1. Martin F. Jimenez and Mario Valencia-Pabon, A note on coloring powers of cycles, author-hosted manuscript:
https://www-lipn.univ-paris13.fr/~valenciapabon/papers/colpow2.pdf
Theorem 1 states chi(C(n,a))=a+1+ceil(r/q), n=q(a+1)+r, and attributes this result to A. Prowse and D. R. Woodall, Choosability of powers of circuits, Graphs and Combinatorics 19(1), 137-144 (2003). Substitution a=h-1 gives precisely the claimed formula in the nontrivial cycle-power range. Remaining complete-graph and degenerate cases follow directly. The manuscript also gives an optimal linear-time coloring algorithm. The present row proof is self-contained; no originality is claimed for that construction.

2. Side Information Design in Zero-Error Coding for Computing, primary research article (2024), Section 3.1, Definition 4 and Theorem 1:
https://pmc.ncbi.nlm.nih.gov/articles/PMC11049120/
This article defines characteristic graphs by common feasible side information with different demanded function outputs, and proves the correspondence of zero-error encoders with proper colorings. Its probabilistic/asymptotic rate results must not be substituted for this task's one-shot worst-case alphabet objective.

3. P. Koulgi, E. Tuncel, S. L. Regunathan, and K. Rose, On Zero-Error Source Coding With Decoder Side Information, IEEE Transactions on Information Theory 49(1), 99-111 (2003):
https://web.ece.ucsb.edu/publications/rose/pubs/pub40-T-IT1-03.pdf
Useful established source-coding context. For the general action, retain the functional-output distinction above.

4. H. S. Witsenhausen, The zero-error side information problem and chromatic numbers, IEEE Transactions on Information Theory 22(5), 592-593 (1976):
https://doi.org/10.1109/TIT.1976.1055607
Foundational pointer; original full text was not obtained in this review. No claim to having checked that original proof.

REQUIRED PRESENTATION LIMITS
State that H is known to both parties, q is unknown to the encoder, all pairs (g,q) in G x H are possible, and records are trusted. The theorem is not about verifying a malicious or falsified record. The result is finite and exact, and does not establish a physically realizable identity criterion or a new theorem about personal identity. Keep any philosophical interpretation separate from the formal coding result. No additional mathematical repair is required under these limitations.
