2017/01/09 by MLJ van de Vel, Van de Vel, M.
Computer Science · Engineering · #00A08 #05A05 #05A17 #05B15 #05C21 (secondary) #11R18 (primary) #Cellular Automata and Applications #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1701.02325
openalex publication_date 2017/01/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A formal n-square is the set of positions in an square matrix of size n. A shuffle of a formal n-square consists of independent rotations of each row and of each column. A key result turns out to be valid at least for n <= 34 and n = 37: Each set of n positions can be mapped with one shuffle onto a transversal of the columns. We consider two applications to equi-n-squares (i.e., n-matrices filled with digits 0, .., n - 1 in equal amounts). First, a shuffled equi-n-square can be seen as a torus with n colors and two orthogonal layers of n rings that can be rotated. Unlike Rubik's cube, each permutation of colored cells can be implemented with shuffles. An upper bound of 3*(-1)n-1 + 6n shuffles is derived from the key result. Our second application invokes column transversals and a process of indirection to produce theoretically unpredictable sequences of integers in shuffled equi-n-squares. Our proof of the key result involves optimizing position sets, averaging, computations based on number partitions, rotating subsets of a regular n-gon apart, and the use of cyclotomic polynomials. A few intermediate results need computer assistence. These efforts also generated a variety of (partially) unsolved problems. We selected eight of these for a brief discussion based on the available theoretical and computer evidence.