The shotgun assembly problem asks whether you can reconstruct a large structured object from many small, overlapping pieces, much like assembling a jigsaw puzzle when you are given all the local fragments but not told where they go. In this paper, the "object" is a grid of colored squares arranged in a d-dimensional lattice, where colors are assigned randomly to each position according to some probability distribution. The question is: if you are given every small sub-grid of size k, can you figure out how the colors are arranged across the entire large grid?
Previous research had solved this problem for the special case where all colors are equally likely, identifying a sharp threshold for the sub-grid size k below which reconstruction becomes impossible and above which it becomes possible. This paper tackles the harder, more realistic case where colors are not equally likely, meaning some colors appear more frequently than others. The authors focus specifically on proving when reconstruction is impossible, using tools from information theory to show that when k is too small, the fragments simply do not contain enough information to uniquely pin down the full coloring.
The main contribution is a sufficient condition, expressed in terms of the color distribution and the sub-grid size, that guarantees reconstruction is impossible. Importantly, when the distribution is plugged back into the uniform special case, this condition exactly matches the previously known impossibility threshold, confirming that the result is tight in that setting. The work extends the theoretical understanding of shotgun assembly to a broader and more realistic class of problems, though a matching positive result showing when reconstruction does succeed in the non-uniform case remains an open question.