Nested Perfect Arrays

Abstract

We introduce two-dimensional periodic arrays that are a variant of the de Bruijn tori. We call them nested perfect arrays. Instead of asking that every array of a given size has exactly one occurrence, we partition the positions in congruence classes and we ask exactly one occurrence in each congruence class. We also ask that this property applies recursively to each of the subarrays. We give a method to construct nested perfect arrays based on Pascal triangle matrix modulo 2. For the two-symbol alphabet, and for n being a power of 2, we partition the positions of the arrays in n2 many congruence classes by taking the row number modulo n and the column number modulo n. We construct arrays where each possible n×n array occurs n2 times, once in each congruence class. Our method yields exponentially many (in n2 ) different nested perfect arrays.