Source-linked AI summary
Mutually orthogonal anti-Latin squares
Eishiro Aoyama, So Hasegawa, Masahito Hayashi, Tomoki Sagara
TL;DR
The paper asks how large mutually orthogonal families of anti-Latin squares can be and how their extremal size relates to Latin squares. It uses balanced matrices, deterministic and probabilistic permutation constructions, and affine-geometric reformulations to show the exact relation and characterize saturated families. The result is NA(3) = NL(3) + 1 and NA(d) = NL(d) + 2 for d ≥4, with explicit treatment of orders through 9.
Problem
The paper studies the maximum size NA(d) of mutually orthogonal anti-Latin squares and its relation to the classical quantity NL(d), whose exact determination is generally difficult.
Method
The paper combines balanced-matrix bounds, deterministic and probabilistic cell-permutation constructions, and affine-plane reformulations of saturated families.
Results
NA(3) = NL(3) + 1, whereas NA(d) = NL(d) + 2 for every d ≥4.
Takeaways & Limitations
Saturated families correspond to affine planes with anti-coordinate grid decompositions, and the numerical value of NA(d) is obtained explicitly for every 3 ≤ d ≤9.
Takeaways & Limitations
The order-4 analysis does not classify all direction-complete partitions or all compatible pairs up to isomorphism.
Abstract
from arXiv · showhide
Anti-Latin squares were introduced in connection with non-linear secure network coding, and the extremal problem for large mutually orthogonal families is motivated by that setting. We study the maximum size $N_A(d)$ of a family of mutually orthogonal anti-Latin squares of order $d$. We prove that $N_L(d)+1\le N_A(d)\le N_L(d)+2$ for every $d\ge 3$, where $N_L(d)$ denotes the classical maximum size of a family of mutually orthogonal Latin squares of order $d$, and we show that in fact $N_A(3)=N_L(3)+1$ whereas $N_A(d)=N_L(d)+2$ for every $d\ge 4$. The upper bound is obtained by passing through balanced matrices, while the lower bound is given by a deterministic permutation argument. For all $d\ge 8$, and also for the exceptional order $d=6$, the upper bound is shown to be attainable by a general probabilistic construction. On the structural side, we show that a saturated family of size $d+1$ induces an affine plane of order $d$, and that the saturated case is characterized by the existence of an anti-coordinate grid decomposition; after transporting this condition to the fixed cell set $[d]^2$, it becomes a direction-completeness condition on the corresponding row-blocks and column-blocks. The remaining small orders are treated separately: $d=3$ is handled by direct analysis and classification of orthogonal triples, $d=4$ by an explicit saturated construction and an analysis of its finite-geometric structure, and $d=5$ and $d=7$ by explicit saturated examples arising from the random-grid framework. Thus $N_A(d)$ is determined in terms of $N_L(d)$ for every $d\ge3$, and its numerical value is obtained explicitly for every $3\le d\le9$.
1 Introduction
The paper determines the extremal size of mutually orthogonal anti-Latin squares relative to the classical Latin-square quantity and develops the geometric structure of saturated families. It also supplies probabilistic and explicit constructions, including the remaining small orders.
- Motivation: The unresolved Latin-square quantity NL(d) motivates studying the corresponding maximum NA(d) for mutually orthogonal anti-Latin squares.NL(d) is known to equal d−1 for prime-power orders, but its exact determination is generally difficult.
- Main extremal result: NA(3) = NL(3) + 1, while NA(d) = NL(d) + 2 for every d ≥4.Thus, except at d = 3, the anti-Latin extremal number is exactly two larger than the Latin-square extremal number.
- Geometric structure: Saturated families of size d + 1 are characterized by affine planes equipped with anti-coordinate grid decompositions.The additional structure consists of two orthogonal resolutions whose blocks are not transversals to any parallel class.
- Geometric structure: In the Desarguesian model, the saturated condition becomes a globally compatible system of direction-complete row-blocks and column-blocks.Both orthogonal partitions must consist of d-point sets determining all d + 1 directions.
- Proof strategy: A balanced-matrix upper-bound argument, deterministic cell permutation, and probabilistic constructions establish the general bounds and attain the upper bound for d ≥8 and d = 6.The low orders are handled separately: d = 3 by classification, d = 4 by explicit finite-geometric analysis, and d = 5,7 by explicit constructions.
2 Deterministic approach
The deterministic approach compares anti-Latin families with balanced matrices and transforms a maximal Latin family by a carefully chosen cell permutation. This permutation preserves orthogonality while forcing repeated symbols in every row and column.
- Upper bound: A maximal mutually orthogonal Latin family together with row- and column-coordinate matrices supplies NL(d) + 2 mutually orthogonal balanced matrices.The coordinate matrices are defined by R_k,j = k and C_k,j = j.
- Upper bound: Balanced matrices provide the upper-bound bridge: mutually orthogonal balanced families have maximum size NL(d) + 2, and anti-Latin families form a subclass.Orthogonality of two balanced matrices identifies rows and columns so that every remaining matrix becomes Latin.
- Lower bound: A cell permutation is constructed by cyclically shifting the cells on the zero-symbol transversal of one Latin square.The transversal meets every row and column exactly once, defining the permutation used in the lower-bound argument.
- Lower bound: For each remaining Latin square, the permutation creates a repeated symbol in every row and every column while preserving balance.Orthogonality with the selected Latin square makes the shifted values distinct before the row and column repetition argument is applied.
- Lower bound: The same permutation makes the row- and column-coordinate matrices anti-Latin, yielding NL(d) + 1 mutually orthogonal anti-Latin squares.The coordinate matrices acquire repetitions through the shifted cells and unchanged neighboring entries.
3 Probabilistic approach
The paper uses random cell permutations to turn balanced orthogonal matrices into anti-Latin squares, proving attainability in specified orders and providing a finite random-grid construction.
- Probabilistic attainability: d ≥8 and d = 6: a uniformly random cell permutation has positive probability of making every balanced matrix anti-Latin.Balance and pairwise orthogonality are preserved under common cell permutations.
- Bad-event analysis: A row is bad when it contains no repeated symbol, and a column is bad when it contains no repeated symbol.For a fixed row or column, the image under a random permutation is a uniformly distributed d-subset of the d^2 cells.
- Bad-event analysis: The probability that a selected d-subset contains no repeated symbol is d^d divided by the number of d-subsets of d^2 cells.This follows because balancedness gives d choices from each of the d symbol classes.
- Probabilistic attainability: A union-bound estimate shows the required success probability is positive for every d ≥8 and also for d = 6.For d ≥8, the numerical estimate is completed using a decreasing bound and the base case d = 8.
- Concrete algorithm: For prime-power q, random-grid sampling tests repeated values in every external row, column, and affine-plane direction before reconstructing the squares.If all tests succeed, the reconstructed line-membership arrays are anti-Latin and mutually orthogonal; displayed outputs can then be checked directly.
4 Geometric reformulation
Orthogonality and balance produce a net, while saturation identifies an affine plane; the anti-Latin requirement becomes an anti-coordinate condition on two orthogonal grid resolutions.
- From matrices to nets: Pairwise orthogonal balanced matrices determine a (d, K)-net whose partitions consist of d blocks of size d with singleton cross-intersections.This is the standard symbol-class construction on the d^2-cell set.
- Saturated families: K = d + 1: the resulting net is exactly an affine plane of order d, so a saturated anti-Latin family implies the existence of such a plane.This yields an immediate obstruction in orders without affine planes.
- Anti-coordinate grids: An anti-coordinate grid decomposition consists of orthogonal row-block and column-block partitions in which no block is a transversal of any parallel class.The row-blocks and column-blocks each have size d and intersect in one cell.
- Anti-coordinate grids: The saturated problem separates classical affine-plane incidence structure from the additional simultaneous resolution condition imposed by anti-Latin squares.The extra condition is carried by the external row and column partitions rather than by the square entries themselves.
- Transported formulation: After transport to [d]^2, directions are transported parallel classes, and the anti-coordinate condition becomes a concrete test on d-subsets.This reformulation does not assume field structure on [d]^2.
- Finite-field form: For prime-power q, a row-block or column-block is direction-complete exactly when every affine projection has a repeated value.Equivalently, each such block determines all q + 1 directions of AG(2, q).
5 Small-order cases and classifications
The small orders require separate treatment: order 3 is nonsaturated and classified directly, while order 4 is saturated and analyzed through finite geometry.
- Order 3: d = 3: extremal families are not saturated because NA(3) < d + 1, so the affine-plane framework does not directly govern them.The order-3 case is handled by direct analysis and classification of orthogonal triples.
- Order 4: d = 4: extremal families are saturated, so their row and column blocks can be analyzed as four-point sets in the associated affine plane.The analysis tracks symbol-multiplicity patterns across the five squares and constrains row and column double-repetition profiles.
- Order 3: Weak isomorphism preserves the grid while allowing family and symbol permutations; strong isomorphism additionally allows common row and column permutations.These equivalence notions formalize the square-side operations used in the order-3 classification.
5.2 Classification in the case d = 3
For d = 3, anti-Latin squares have a rigid row-column structure that bounds orthogonal families by three and permits a complete classification of extremal triples.
- Every row and column of an order-3 anti-Latin square is nonconstant and has pattern (x, x, y) up to permutation, with x ≠ y.
- After normalizing the top-left entry, six possible first-row patterns split into three incompatible pairs, with at most one pattern from each pair in an orthogonal family.
- NA(3) = 3, obtained from the lower bound NA(3) ≥ NL(3) + 1 with NL(3) = 2 and an upper bound of three.
- Every normalized order-3 square has unique parameters (ε, η) ∈ {±1}² and δ ∈ Z3, yielding 72 total anti-Latin squares.
- Orthogonality occurs exactly for squares sharing the same sign pair and having distinct δ parameters; consequently, triples form four weak-isomorphism classes but one strong-isomorphism class.
5.3 The case d = 4: extremal value and the geometry of saturated anti-Latin families
For d = 4, a saturated family has five squares and induces direction-complete row and column blocks in AG(2, 4), with additional doubled-direction and multiplicity constraints.
- NA(4) = 5, because an explicit saturated construction reaches five and the general upper bound gives NA(4) ≤ NL(4) + 2 = 5.
- Every row-block and column-block is a direction-complete four-point subset of AG(2, 4), determining all five directions.
- Each direction-complete four-point block has one doubled direction among its six pair-directions; no affine line contains three block points, and the doubled pairs are disjoint.
- For each row or column, exactly one square has multiplicity pattern (2, 2), while the other four have pattern (2, 1, 1).
- The four doubled directions have a restricted multiplicity profile: pattern (3, 1) is impossible, while exactly four admissible patterns occur.
- These profiles classify only doubled-direction multiplicities, not isomorphism classes or compatibility with a second partition.
5.4 Final synthesis
The final synthesis proves the exact relation between anti-Latin and Latin extremal numbers, with d = 3 exceptional and the upper bound attained in all d ≥ 4 cases.
- NA(3) = NL(3) + 1 because NA(3) = 3 and NL(3) = 2.
- NA(d) = NL(d) + 2 for d = 4, 5, and 7, using explicit constructions and NL(d) = d − 1 for these prime-power orders.
- The same upper-bound-attaining conclusion holds for d = 6 and every d ≥ 8.
6 Conclusion
The paper determines N_A(d) in terms of N_L(d), identifies the geometry of saturated families, and completes the cases through order 9.
- Extremal formula: The universal comparison N_L(d) + 1 ≤ N_A(d) ≤ N_L(d) + 2 is proved using balanced matrices for the upper bound and a deterministic permutation argument for the lower bound.
- Extremal formula: N_A(3) = N_L(3) + 1, while N_A(d) = N_L(d) + 2 for every d ≥4.Thus the anti-Latin extremal problem differs from the classical one by a fixed shift of two except at d = 3.
- Constructions: The upper bound is attained for all d ≥8 and also for d = 6 through a probabilistic construction.The remaining order-specific work concerns the small cases.
- Geometric structure: A saturated family of size d + 1 corresponds to an affine plane with an anti-coordinate grid decomposition, equivalently two orthogonal resolutions whose blocks are non-transversal to every parallel class.
- Geometric structure: After transport to [d]^2, the additional structure becomes direction-completeness for compatible row-blocks and column-blocks.This is a simultaneous decomposition problem for two compatible families of point sets, rather than the direction set of one point set.
- Small orders: For d = 3, N_A(3) = 3 and orthogonal triples fall into four weak classes and one strong class; d = 4 has an explicit saturated family with N_A(4) = 5.Explicit saturated constructions are also given for d = 5 and d = 7, and Table 1 records the determined values for 3 ≤ d ≤9.
Appendix A Explicit computational examples for d = 5 and d = 7
The appendix constructs saturated families for d = 5 and d = 7 using randomized grid decompositions and affine-plane line membership.
- Construction: A random bijection τ : [d]^2 → F_d^2 defines a grid decomposition by pulling back coordinate fibres.
- Construction: Every row-block and column-block is required to determine all d + 1 directions before reconstruction.Theorem 5 then reconstructs d + 1 arrays by line membership, producing a saturated family.
A.1 Provenance and reproducibility
The provenance record describes reproducible randomized-grid searches for d = 5 and d = 7 and verifies the resulting families.
- Search and verification: The supplementary script samples random bijections τ : [d]^2 → F_d^2 and tests direction-completeness of standard row- and column-blocks.
- Search and verification: Successful decompositions were found at trial 34 for d = 5 and trial 3 for d = 7 with seed 20260317.
- Search and verification: For d = 7, the construction yields eight arrays, equal to d + 1.
- Search and verification: The supplementary verifier checks the anti-Latin row/column property and pairwise orthogonality exactly as encoded in Theorem 5.
Availability of supporting data
Supporting data for the d = 5 and d = 7 constructions includes generation code, JSON outputs, and verification results.
- Artifacts: The script implements randomized-grid sampling, direction-completeness tests, and reconstruction of d + 1 arrays by Theorem 5’s line-membership rule.
- Artifacts: The JSON output records successful bijections, trial numbers, generated families, and verification results.