pith. sign in

arxiv: 2605.18875 · v1 · pith:WLRYE5CFnew · submitted 2026-05-15 · 💻 cs.FL · math.CO

On the transversals of Latin squares generated by nonlinear bipermutive cellular automata

Alberto Dennunzio , Maximilien Gadouleau , Luca Mariot This is my paper

Pith reviewed 2026-05-20 16:26 UTC · model grok-4.3

classification 💻 cs.FL math.CO
keywords cellular automataLatin squarestransversalsbipermutive rulesorthogonal matesnonlinear cellular automatainvertible automata
0
0 comments X

The pith

The main diagonal of Latin squares from bipermutive cellular automata forms a transversal exactly when the local rule induces an invertible periodic automaton on d-1 cells.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper characterizes when bipermutive cellular automata without boundary conditions produce Latin squares of order 2 to the power of d minus 1 that have a transversal along the main diagonal. The existence of such transversals is a prerequisite for partitioning the square into disjoint transversals, which in turn determines whether an orthogonal mate exists. The authors prove an if-and-only-if link between the transversal property and the invertibility of a related cellular automaton with periodic boundaries on a smaller grid of size d minus 1. Exhaustive experiments then locate the smallest diameter where nonlinear rules satisfy the condition.

Core claim

The main diagonal forms a transversal if and only if the generating function of the bipermutive local rule induces an invertible CA with periodic boundary conditions on a configuration of size d-1.

What carries the argument

The algebraic reduction that equates the no-boundary transversal property of the Latin square to the invertibility of a smaller periodic cellular automaton generated by the same local rule.

If this is right

  • No nonlinear bipermutive rules yield main-diagonal transversals for diameters 3 through 5.
  • At diameter 6, nonlinear rules exist that satisfy the transversal condition, as shown by exhaustive enumeration.
  • The equivalence provides a decidable test for the main-diagonal transversal property without constructing the full Latin square.
  • Rules meeting the invertibility condition become candidates for further checks on the existence of a complete set of disjoint transversals.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction technique might identify rules whose Latin squares admit multiple disjoint transversals rather than just one.
  • Extending the diameter beyond 6 could expose families of nonlinear generating functions that systematically produce orthogonal mates.
  • The invertibility criterion may generalize to other local-rule-generated combinatorial objects such as orthogonal arrays.

Load-bearing premise

The specific algebraic structure of bipermutive rules and the chosen representation of Latin square entries allow the transversal property to reduce directly to invertibility of the smaller periodic CA.

What would settle it

A bipermutive rule that induces an invertible periodic CA on d-1 cells yet whose generated Latin square has no main-diagonal transversal, or the converse case.

Figures

Figures reproduced from arXiv: 2605.18875 by Alberto Dennunzio, Luca Mariot, Maximilien Gadouleau.

Figure 1
Figure 1. Figure 1: Application of the global rule F to the symmetric configuration x||x, with x ∈ F d−1 2 . This is equivalent to computing T(x). associated polynomial always admits a coprime pair. Therefore, in this paper we focus on the generic case where the BCA rule can also be nonlinear, which is the most interesting one. Let us now take a closer look at the mapping T. This corresponds to the application of the CA globa… view at source ↗
Figure 2
Figure 2. Figure 2: Depiction of the map T as a PBCA of size d − 1, with local rule corre￾sponding to the generating function g : F d−2 2 → F2. actually defined by a CA with periodic boundary conditions having d − 1 cells, and equipped with the generating function g : F d−2 2 → F2 as a local rule [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The 32 × 32 Latin square generated by the BCA of diameter 6 with generating function g(x1, x2, x3, x4) = x1 ⊕ x3 ⊕ x1x4. Background shading follows the viridis colormap (symbol 1: dark purple, symbol 32: yellow). Cells outlined in black form the main diagonal transversal [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
read the original abstract

In this short paper, we begin to investigate the conditions under which a generic Bipermutive Cellular Automaton (BCA) with no-boundary conditions of diameter $d$ generates a Latin square of order $N=2^{d-1}$ admitting an orthogonal mate, without relying on the linearity of the local rule. Since an orthogonal mate exists if and only if the Latin square can be partitioned into $N$ disjoint \emph{transversals}, we start by characterizing the subclass of BCA whose Latin squares have a transversal on the main diagonal. In particular, we prove that the main diagonal forms a transversal if and only if the generating function of the bipermutive local rule induces an invertible CA with periodic boundary conditions on a configuration of size $d-1$. We then perform exhaustive search experiments, showing that $d=6$ is the smallest diameter for which there exist nonlinear bipermutive CA that generate Latin squares with a transversal on the main diagonal.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript characterizes transversals in Latin squares generated by bipermutive cellular automata (BCA) of diameter d with no-boundary conditions, where the squares have order N=2^{d-1}. It proves that the main diagonal forms a transversal if and only if the generating function of the bipermutive local rule induces an invertible CA with periodic boundary conditions on configurations of size d-1. Exhaustive search experiments are reported to establish that d=6 is the smallest diameter admitting nonlinear bipermutive rules with this property.

Significance. If the central iff characterization holds, the result extends prior work on linear rules to the nonlinear setting and supplies a concrete algebraic criterion for the existence of at least one transversal (hence an orthogonal mate) in these CA-generated Latin squares. The exhaustive enumeration for small d provides independent, falsifiable confirmation and identifies the threshold diameter for nonlinear examples.

minor comments (2)
  1. [Proof of Theorem 1] The reduction from the no-boundary transversal condition to invertibility of the induced periodic CA on d-1 cells is the load-bearing step; while the abstract and introduction state that it holds for both linear and nonlinear rules, a brief remark on why the bipermutive algebraic structure guarantees the mapping would improve clarity for readers unfamiliar with the representation.
  2. [Section 4] The exhaustive-search section reports completeness for d=6 but does not specify the enumeration strategy (e.g., whether all 2^{2^{d-1}} possible generating functions were checked or a smarter enumeration over nonlinear rules was used); adding this detail would strengthen reproducibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and for recommending acceptance. The characterization of the main diagonal as a transversal and the identification of d=6 as the smallest diameter admitting nonlinear examples appear to have been found clear and of interest.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper's central result is a direct mathematical characterization: the main diagonal is a transversal iff the bipermutive local rule's generating function induces an invertible periodic CA on d-1 cells. This equivalence follows from the algebraic definitions of bipermutive rules, Latin square construction from the CA, and the chosen entry representation, without any fitted parameters, self-referential equations, or load-bearing self-citations. The exhaustive search for d=6 supplies independent computational verification that nonlinear examples exist, confirming the characterization holds outside any definitional loop. No step reduces the claimed iff to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard definitions of bipermutive cellular automata, Latin squares, and transversals; no new free parameters or invented entities are introduced. The invertibility check is a standard property of one-dimensional CA.

axioms (1)
  • domain assumption Bipermutive local rules admit a generating function representation that allows reduction of the no-boundary transversal condition to periodic invertibility on d-1 cells.
    Invoked in the proof that equates the main-diagonal transversal to invertibility of the induced CA.

pith-pipeline@v0.9.0 · 5707 in / 1304 out tokens · 39216 ms · 2026-05-20T16:26:58.265921+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · 1 internal anchor

  1. [1]

    Wiley-Interscience series in discrete mathematics and optimization, Wiley (2005)

    Bruen, A.A., Forcinito, M.A.: Cryptography, information theory, and error- correction - a handbook for the 21st century. Wiley-Interscience series in discrete mathematics and optimization, Wiley (2005)

    work page 2005

  2. [2]

    Daemen, J.: Cipher and hash function design strategies based on linear and differ- ential cryptanalysis. Ph.D. thesis, KU Leuven (1995)

    work page 1995

  3. [3]

    Applied Mathematics and Computation62(2), 259 – 277 (1994)

    Daemen, J., Govaerts, R., Vandewalle, J.: Invertible shift-invariant transformations on binary arrays. Applied Mathematics and Computation62(2), 259 – 277 (1994)

    work page 1994

  4. [4]

    D´ enes, J., Keedwell, A.D.: Latin squares: New developments in the theory and applications, vol. 46. Elsevier (1991)

    work page 1991

  5. [5]

    Nonlinearity6(6), 1009–1023 (1993)

    Eloranta, K.: Partially permutive cellular automata. Nonlinearity6(6), 1009–1023 (1993)

    work page 1993

  6. [6]

    Gadouleau, M., Mariot, L., Picek, S.: Bent functions in the partial spread class generated by linear recurring sequences. Des. Codes Cryptogr.91(1), 63–82 (2023)

    work page 2023

  7. [7]

    Hammer, J.M., Lorch, J.: Diagonal cellular factor pair latin squares. Des. Codes Cryptogr.91(6), 2309–2322 (2023)

    work page 2023

  8. [8]

    CoRR abs/2411.00721(2024)

    Haugland, J.K., Omland, T.: New classes of reversible cellular automata. CoRR abs/2411.00721(2024). https://doi.org/10.48550/ARXIV.2411.00721, https:// doi.org/10.48550/arXiv.2411.00721

    work page doi:10.48550/arxiv.2411.00721 2024

  9. [9]

    Sankhy¯ a: The Indian Journal of Statistics, Series A pp

    Hedayat, A., Shrikhande, S.: Experimental designs and combinatorial systems associated with latin squares and sets of mutually orthogonal latin squares. Sankhy¯ a: The Indian Journal of Statistics, Series A pp. 423–432 (1971)

    work page 1971

  10. [10]

    Elsevier (2015)

    Keedwell, A.D., D´ enes, J.: Latin squares and their applications. Elsevier (2015)

    work page 2015

  11. [11]

    Leporati, A., Mariot, L.: Cryptographic properties of bipermutive cellular automata rules. J. Cell. Autom.9(5-6), 437–475 (2014)

    work page 2014

  12. [12]

    Manzoni, L., Mariot, L., Menara, G.: Combinatorial designs and cellular automata: A survey. Discret. Appl. Math.379, 656–674 (2026)

    work page 2026

  13. [13]

    Mariot, L.: Enumeration of maximal cycles generated by orthogonal cellular au- tomata. Nat. Comput.22(3), 477–491 (2023)

    work page 2023

  14. [14]

    Constructing Orthogonal Latin Squares from Linear Cellular Automata

    Mariot, L., Formenti, E., Leporati, A.: Constructing orthogonal latin squares from linear cellular automata. CoRRabs/1610.00139(2016), http://arxiv.org/abs/ 1610.00139

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  15. [15]

    In: Dennunzio, A., Formenti, E., Manzoni, L., Porreca, A.E

    Mariot, L., Formenti, E., Leporati, A.: Enumerating orthogonal latin squares generated by bipermutive cellular automata. In: Dennunzio, A., Formenti, E., Manzoni, L., Porreca, A.E. (eds.) Cellular Automata and Discrete Complex Systems - 23rd IFIP WG 1.5 International Workshop, AUTOMATA 2017, Milan, Italy, June 7-9, 2017, Proceedings. Lecture Notes in Comp...

    work page 2017

  16. [16]

    Mariot, L., Gadouleau, M., Formenti, E., Leporati, A.: Mutually orthogonal latin squares based on cellular automata. Des. Codes Cryptogr.88(2), 391–411 (2020)

    work page 2020

  17. [17]

    In: International Workshop on Cellular Automata and Discrete Complex Systems

    Mariot, L., Manzoni, L.: Building correlation immune functions from sets of mutually orthogonal cellular automata. In: International Workshop on Cellular Automata and Discrete Complex Systems. pp. 153–164. Springer (2023)

    work page 2023

  18. [18]

    In: Proceedings of the Genetic and Evolutionary Computation Conference

    Mariot, L., Picek, S., Jakobovic, D., Leporati, A.: Evolutionary algorithms for the design of orthogonal latin squares based on cellular automata. In: Proceedings of the Genetic and Evolutionary Computation Conference. pp. 306–313 (2017)

    work page 2017

  19. [19]

    Cryptogr

    Mariot, L., Picek, S., Leporati, A., Jakobovic, D.: Cellular automata based s-boxes. Cryptogr. Commun.11(1), 41–62 (2019)

    work page 2019

  20. [20]

    Springer (2004)

    Stinson, D.R.: Combinatorial designs - constructions and analysis. Springer (2004)

    work page 2004

  21. [21]

    Wolfram, S.: Statistical mechanics of cellular automata. Reviews of modern physics 55(3), 601 (1983) 9 Appendix: Example of nonlinear BCA-based Latin square 1 22 11 32 21 2 31 12 9 14 3 8 29 26 23 20 17 6 27 16 5 18 15 28 25 30 19 24 13 10 7 4 2 21 12 31 22 1 32 11 10 13 4 7 30 25 24 19 18 5 28 15 6 17 16 27 26 29 20 23 14 9 8 3 4 23 10 29 24 3 30 9 12 15...

    work page 1983