Prescribed-Difference Matchings with Four and Eight Holes: Fourier Filters for Compatible Boundaries
Abstract
Let s≥ 2 and let v1,…,v2s−1∈ F2s∖{0} have sum zero. The prescribed-difference matching problem asks whether F2s can be partitioned into pairs whose differences, counted with multiplicity, are exactly these vectors. Fix a hyperplane H≤ F2s. 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≥ 3 and every eight-hole instance has a solution for s≥ 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.
Related
- Prescribed and simultaneous failures of log-concavity in trees with perfect matchings
- Dense Sets with Prescribed Difference Representation Functions
- Finite difference methods for three kinds of reaction-diffusion equations with free boundaries
- Simultaneous Residue-Class Selection in Prescribed-Difference Packings
- A nonlocal nonlinear Schrödinger model: well-posedness, local limit, and structure-preserving asymptotically compatible Fourier approximations
BibTeX
@misc{kreindel2026prescribeddifference,
title = {{Prescribed-Difference Matchings with Four and Eight Holes: Fourier Filters for Compatible Boundaries}},
author = {Avraham Kreindel and Aryeh Lev Zabokritskiy},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.27547},
eprint = {2608.27547},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.27547},
}
RIS
TY - UNPB
TI - Prescribed-Difference Matchings with Four and Eight Holes: Fourier Filters for Compatible Boundaries
AU - Avraham Kreindel
AU - Aryeh Lev Zabokritskiy
PY - 2026
DA - 2026/08/27
PB - arXiv
DO - 10.48550/arxiv.2608.27547
UR - https://arxiv.org/abs/2608.27547
AB - Let s≥ 2 and let v_1,…,v_2^s−1∈ F_2^s∖{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≤ 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≥ 3 and every eight-hole instance has a solution for s≥ 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.
ER -