Simultaneous Residue-Class Selection in Prescribed-Difference Packings
Abstract
A family ℱ of finite subsets of ℤ is packed into [N] if suitable integer translates of its members are pairwise disjoint subsets of [N]. We study two prescribed-difference packing problems of Alon, Dębski, Grytczuk and Przybyło for the arithmetic progressions Ad={d,2d,…,⌊ n/d⌋ d} and Bd={d,2d,…,nd}. Let m(n) and M(n) denote the corresponding minimum packing lengths, with subscripts indicating restrictions on the admissible differences, and let 𝒫(x) denote the set of primes at most x. The key ingredient is a residue-class selection scheme that encodes pairwise intersection constraints by cyclic intervals. A lattice-covering argument yields a simultaneous admissible choice, permitting substantial overlap of the containing intervals and providing the sharp upper bounds needed for the bounded-diameter family and the prime-difference equal-cardinality family. For the bounded-diameter family, we prove m(n)∼ m𝒫(√n)(n)∼ 4n3/2/(3log n). For the equal-cardinality family with prime differences, we prove M𝒫(n)(n)∼ n3/(6log n). For the full equal-cardinality family, we show M(n)≥ (19/108−o(1))n3/log n. Together with corresponding estimates for restricted ranges of differences, these results prove several conjectures of Alon--Dębski--Grytczuk--Przybyło and disprove others.
Related
- Prescribed digit sums in residue classes and a conjecture of Murthy (OEIS A077754)
- Dense Sets with Prescribed Difference Representation Functions
- Prescribed and simultaneous failures of log-concavity in trees with perfect matchings
- Prescribed-Difference Matchings with Four and Eight Holes: Fourier Filters for Compatible Boundaries
- A cyclotomic gluing construction for lattice sphere packings
BibTeX
@misc{hou2026simultaneous,
title = {{Simultaneous Residue-Class Selection in Prescribed-Difference Packings}},
author = {Jianfeng Hou and Siyue Liu and Hongbin Zhao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07487},
eprint = {2609.07487},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07487},
}
RIS
TY - UNPB
TI - Simultaneous Residue-Class Selection in Prescribed-Difference Packings
AU - Jianfeng Hou
AU - Siyue Liu
AU - Hongbin Zhao
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.07487
UR - https://arxiv.org/abs/2609.07487
AB - A family ℱ of finite subsets of ℤ is packed into [N] if suitable integer translates of its members are pairwise disjoint subsets of [N]. We study two prescribed-difference packing problems of Alon, Dębski, Grytczuk and Przybyło for the arithmetic progressions A_d={d,2d,…,⌊ n/d⌋ d} and B_d={d,2d,…,nd}. Let m(n) and M(n) denote the corresponding minimum packing lengths, with subscripts indicating restrictions on the admissible differences, and let 𝒫(x) denote the set of primes at most x. The key ingredient is a residue-class selection scheme that encodes pairwise intersection constraints by cyclic intervals. A lattice-covering argument yields a simultaneous admissible choice, permitting substantial overlap of the containing intervals and providing the sharp upper bounds needed for the bounded-diameter family and the prime-difference equal-cardinality family. For the bounded-diameter family, we prove m(n)∼ m_𝒫(√n)(n)∼ 4n^3/2/(3log n). For the equal-cardinality family with prime differences, we prove M_𝒫(n)(n)∼ n^3/(6log n). For the full equal-cardinality family, we show M(n)≥ (19/108−o(1))n^3/log n. Together with corresponding estimates for restricted ranges of differences, these results prove several conjectures of Alon--Dębski--Grytczuk--Przybyło and disprove others.
ER -