Prescribed-Difference Matchings with Four and Eight Holes: Fourier Filters for Compatible Boundaries

Source abstract

Let $s\geq 2$ and let $v_1,\ldots,v_{2^{s-1}}\in F_2^s\setminus\{0\}$ have sum zero. The prescribed-difference matching problem asks whether $F_2^s$ can be partitioned into pairs whose differences, counted with multiplicity, are exactly these vectors. Fix a hyperplane $H\leq F_2^s$. An $h$-hole instance is one in which exactly $h$ prescribed differences lie in $H$, counted with multiplicity. We prove that every four-hole instance has a solution for $s\geq 3$ and every eight-hole instance has a solution for $s\geq 4$. Thus no restriction on the multiplicities or on the sum of the holes is needed beyond the global zero-sum condition. After the internal pairs are placed, their endpoints are deleted from the two affine halves determined by $H$, and the remaining vectors must be paired with the prescribed crossing differences. A locally valid placement of the internal pairs need not admit such a completion. We encode the possible completions by coefficients of signed determinants and use the Walsh transform to sum over all disjoint legal placements while keeping the crossing profile fixed. Nonvanishing of this sum guarantees that at least one placement extends to a full matching. The four-hole and zero-sum eight-hole theorems are proved theoretically. The general eight-hole proof uses three finite exact verifications, independent of the crossing profile: a local filter calculation, a classification of the remaining eight-hole configurations, and integer certificates for those configurations. The verification software, exact inputs, and recorded outputs are archived in a versioned Zenodo record.