pith. sign in

arxiv: 2506.00360 · v3 · submitted 2025-05-31 · 🧮 math.CO · math.RT

Tiling the symmetric group by transpositions

Teng Fang , Binzhou Xia This is my paper

Pith reviewed 2026-05-19 12:18 UTC · model grok-4.3

classification 🧮 math.CO math.RT
keywords tilingsymmetric grouptranspositionspartition-transitivitygroup factorizationpermutation group
0
0 comments X

The pith

Any set Y that tiles the symmetric group with identity plus transpositions must be partition-transitive on certain partitions of n.

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

The paper establishes a new necessary condition for the existence of a tiling (T_n, Y) of the symmetric group S_n, where T_n contains the identity and every transposition. The condition requires that Y must be partition-transitive with respect to certain partitions of the set [n]. This requirement arises from the unique factorization property combined with the way transpositions move points. The condition generalizes the earlier non-existence results based on divisibility by large primes and the work of Nomura. If the condition holds, it imposes strong symmetry requirements on Y that many candidate sets will fail to meet.

Core claim

If (T_n, Y) forms a tiling of S_n, then Y is partition-transitive with respect to certain partitions of n. The proof derives this by examining the orbits and blocks created when transpositions act on [n] and showing that the uniqueness of each group element as a product xy forces Y to map blocks to blocks transitively.

What carries the argument

Partition-transitivity of Y, the requirement that Y acts transitively on the blocks of specific partitions of [n] induced by the transposition action.

If this is right

  • The new condition rules out more potential tilings than the earlier divisibility test alone.
  • The same condition generalizes Nomura's earlier obstruction for these tilings.
  • Analysis of the related set of all transpositions without the identity leads to the conjecture that neither set tiles S_n for any n at least 4.

Where Pith is reading between the lines

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

  • The condition supplies a practical test that could be applied by computer to search for or rule out tilings on small values of n.
  • Analogous block-transitivity requirements may appear when studying factorizations of other permutation groups or Coxeter groups.
  • If the conjecture holds, it would mean the symmetric group admits no such factorization into a small set of transpositions and a complementary set for all n at least 4.

Load-bearing premise

The natural action of transpositions on the points [n] produces block constraints that any valid Y must respect by being partition-transitive.

What would settle it

An explicit construction of a set Y that is not partition-transitive for the relevant partitions yet still completes (T_n, Y) to a tiling of S_n for some n at least 4.

read the original abstract

For nonempty subsets $X$ and $Y$ of a group $G$, we say that $(X,Y)$ is a tiling of $G$ if every element of $G$ can be uniquely expressed as $xy$ for some $x\in X$ and $y\in Y$. In 1966, Rothaus and Thompson studied whether the symmetric group $S_n$ with $n\geq3$ admits a tiling $(T_n,Y)$, where $T_n$ consists of the identity and all the transpositions in $S_n$. They showed that no such tiling exists if $1+n(n-1)/2$ is divisible by a prime number at least $\sqrt{n}+2$. In this paper, we establish a new necessary condition for the existence of such a tiling: the subset $Y$ must be partition-transitive with respect to certain partitions of $n$. This generalizes the result of Rothaus and Thompson, as well as a result of Nomura in 1985. We also study whether $S_n$ can be tiled by the set $T_n^*$ of all the transpositions, which finally leads us to conjecture that neither $T_n$ nor $T_n^*$ tiles $S_n$ for any $n\geq4$.

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

1 major / 2 minor

Summary. The paper defines a tiling (X,Y) of a group G and focuses on tilings (T_n, Y) of the symmetric group S_n, where T_n consists of the identity and all transpositions. It establishes a new necessary condition that any such Y must be partition-transitive with respect to certain partitions of [n]. This generalizes non-existence results of Rothaus-Thompson and Nomura. The paper further examines tilings by the full set of transpositions T_n* and conjectures that neither T_n nor T_n* tiles S_n for any n ≥ 4.

Significance. If the partition-transitivity condition is correctly derived from the unique-product property and the transposition action, the result strengthens existing obstructions to tilings and provides a new invariant for studying factorizations in S_n. The conjecture supplies a concrete, falsifiable prediction that could guide computational checks or further theoretical work. The generalization over prior results is a clear incremental advance in this area of combinatorial group theory.

major comments (1)
  1. [Main theorem and its proof] The central derivation of the partition-transitivity requirement (stated in the abstract and proved in the main theorem) rests on the claim that the natural action of transpositions on [n] forces any completing Y to preserve transitivity on the blocks of certain partitions. This step appears load-bearing for the necessity result and its claimed generalization of Rothaus-Thompson and Nomura. A concrete walk-through is needed showing how xy = g (with x in T_n) implies the required invariance when a transposition fixes a block setwise but Y maps elements across blocks inconsistently; without this, the constraint may not hold for all partitions used in the argument.
minor comments (2)
  1. [Introduction] The introduction would benefit from a short explicit comparison (one paragraph) of the new partition-transitivity condition with the divisibility criterion of Rothaus-Thompson and the earlier result of Nomura, to make the precise improvement transparent.
  2. [Final section] For the conjecture on T_n and T_n*, stating the range of n for which exhaustive or computational checks were performed would help readers assess the supporting evidence.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough review and for highlighting the need for greater clarity in the proof of our main theorem. We address the major comment below and have revised the manuscript to incorporate a detailed walkthrough as requested. This strengthens the exposition without altering the core results.

read point-by-point responses

  1. Referee: [Main theorem and its proof] The central derivation of the partition-transitivity requirement (stated in the abstract and proved in the main theorem) rests on the claim that the natural action of transpositions on [n] forces any completing Y to preserve transitivity on the blocks of certain partitions. This step appears load-bearing for the necessity result and its claimed generalization of Rothaus-Thompson and Nomura. A concrete walk-through is needed showing how xy = g (with x in T_n) implies the required invariance when a transposition fixes a block setwise but Y maps elements across blocks inconsistently; without this, the constraint may not hold for all partitions used in the argument.

    Authors: We agree that an explicit walkthrough improves accessibility and have added it to the revised proof of Theorem 3.1. Consider a partition π of [n] into blocks B1, ..., Bk that are preserved setwise by a transposition τ in T_n (so τ either fixes a block pointwise or swaps two elements inside one block). For g = x y with x ∈ T_n and y ∈ Y, the unique-product property implies that if y maps an element of Bi to Bj (i ≠ j), then composing with τ would produce a second factorization g' = x' y' for some g' in the same coset, contradicting uniqueness. We now include a concrete case for n=4 and π = {{1,2},{3,4}}: assume Y sends 1 to an element in the second block while preserving the first; taking x = (1 2) yields two distinct representations of the same group element, violating the tiling condition. This argument extends directly to the partitions used in generalizing Rothaus-Thompson and Nomura by tracking orbits under the transposition action. revision: yes

Circularity Check

0 steps flagged

Derivation of partition-transitivity condition follows directly from tiling definition without reduction to inputs

full rationale

The paper defines a tiling (T_n, Y) via unique factorization g = x y with x in T_n (identity plus transpositions). It then derives that any such Y must be partition-transitive on certain partitions of [n] by examining how transpositions act on blocks and how the unique-product property constrains Y's action across those blocks. This step uses only the group action and the uniqueness axiom; it does not invoke fitted parameters, rename prior empirical patterns, or rest on a self-citation chain. The result generalizes Rothaus-Thompson and Nomura by extending the same definitional argument rather than assuming their conclusions. No equation or claim reduces to its own input by construction, and external citations are to independent prior work. The derivation is therefore self-contained against the stated axioms.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard group axioms and the combinatorial definition of tiling; no free parameters are fitted to data and no new entities are postulated.

axioms (2)
  • standard math Standard axioms of finite groups and the symmetric group S_n.
    The entire development takes place inside established group theory.
  • domain assumption Every element of G is uniquely expressed as xy with x in X and y in Y.
    This is the definition of tiling used throughout.

pith-pipeline@v0.9.0 · 5748 in / 1416 out tokens · 60610 ms · 2026-05-19T12:18:25.982552+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

33 extracted references · 33 canonical work pages · 2 internal anchors

  1. [1]

    N. L. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B , 15 (1973), 289–296

    work page 1973

  2. [2]

    Corteel, A

    S. Corteel, A. Goupil and G. Schaeffer, Content evaluation and class symmetric functions, Adv. Math., 188 (2004) 315–336. 13

    work page 2004

  3. [3]

    C. W. Curtis and I. Reiner, Representation theory of finite groups and associative algebras, Interscience, New York, 1962

    work page 1962

  4. [4]

    I. J. Dejter and O. Serra, Efficient dominating sets in Cayley graphs, Discrete Appl. Math., 129 (2003) 319–328

    work page 2003

  5. [5]

    Diaconis and M

    P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete , 57 (1981), no. 2, 159–179

    work page 1981

  6. [6]

    Diaconis, Group representations in probability and statistics , Institute of Mathe- matical Statistics, Hayward, CA, 1989

    P. Diaconis, Group representations in probability and statistics , Institute of Mathe- matical Statistics, Hayward, CA, 1989

    work page 1989

  7. [7]

    P. H. Edelman and D. White, Codes, transforms and the spectrum of the symmetric group, Pacific J. Math. , 143 (1990), no. 1, 47–67

    work page 1990

  8. [8]

    Ellis, E

    D. Ellis, E. Friedgut and H. Pilpel, Intersecting families of permutations, J. Amer. Math. Soc. , 24 (2011), no. 3, 649–682

    work page 2011

  9. [9]

    Intersecting Families of Permutations

    D. Ellis, E. Friedgut and H. Pilpel, Intersecting families of permutations, ArXiv, https://arxiv.org/abs/1011.3342v2

    work page internal anchor Pith review Pith/arXiv arXiv

  10. [10]

    Ellis and N

    D. Ellis and N. Lifshitz, Approximation by juntas in the symmetric group, and for- bidden intersection problems, Duke Math. J. , 171 (2022), no. 7, 1417–1467

    work page 2022

  11. [11]

    Etienne Perfect codes and regular partitions in graphs and groups, European J

    G. Etienne Perfect codes and regular partitions in graphs and groups, European J. Combin., 8 (1987), no. 2, 139–144

    work page 1987

  12. [12]

    Fang, On a conjecture of Green and Liebeck concerning codes in symmetric groups, Arxiv, https://arxiv.org/abs/2502.10744

    T. Fang, On a conjecture of Green and Liebeck concerning codes in symmetric groups, Arxiv, https://arxiv.org/abs/2502.10744

    work page arXiv

  13. [13]

    T. Feng, W. Li and J. Zhou, On codes in the projective linear group PGL(2, q), Finite Fields Appl., 75 (2021), Paper No. 101812, 11 pp

    work page 2021

  14. [14]

    A comment on Intersecting Families of Permutations

    Y. Filmus, A comment on intersecting families of permutations, Arxiv, https:// arxiv.org/abs/1706.10146

    work page internal anchor Pith review Pith/arXiv arXiv

  15. [15]

    Frobenius, ¨Uber die Charaktere der symmetrischen Gruppe , Berliner Berichte, 1901

    G. Frobenius, ¨Uber die Charaktere der symmetrischen Gruppe , Berliner Berichte, 1901

    work page 1901

  16. [16]

    H. M. Green and M. W. Liebeck, Some codes in symmetric and linear groups,Discrete Math., 343 (2020), no. 8, 111719, 5 pp

    work page 2020

  17. [17]

    Haj´ os,¨Uber einfache und mehrfache Bedeckung des n-dimensionalen Raumes mit einem Wfelgitter, Math

    G. Haj´ os,¨Uber einfache und mehrfache Bedeckung des n-dimensionalen Raumes mit einem Wfelgitter, Math. Z., 47 (1941), 427–467

    work page 1941

  18. [18]

    T. W. Haynes, S. T. Hedetniemi and P. Slater,Fundamentals of domination in graphs, Marcel Dekker, Inc., New York, 1998

    work page 1998

  19. [19]

    R. E. Ingram, Some characters of the symmetric group, Proc. Amer. Math. Soc. , 1 (1950), 358–369

    work page 1950

  20. [20]

    G. D. James and A. Kerber, The representation theory of the symmetric group , En- cyclopedia Math. Appl., 16, Addison-Wesley Publishing Co., Reading, MA, 1981. 14

    work page 1981

  21. [21]

    Katriel, Explicit expressions for the central characters of the symmetric group, Discrete Appl

    J. Katriel, Explicit expressions for the central characters of the symmetric group, Discrete Appl. Math. , 67 (1996), no. 1-3, 149–156

    work page 1996

  22. [22]

    Keevash and E

    P. Keevash and E. Long, Frankl-R¨ odl-type theorems for codes and permutations, Trans. Amer. Math. Soc., 369 (2017), no. 2, 1147–1162

    work page 2017

  23. [23]

    Kupavskii and D

    A. Kupavskii and D. Zakharov, Spread approximations for forbidden intersections problems, Adv. Math., 445 (2024), Paper No. 109653, 29 pp

    work page 2024

  24. [24]

    Lee, Independent perfect domination sets in Cayley graphs, J

    J. Lee, Independent perfect domination sets in Cayley graphs, J. Graph Theory , 37 (2001), no. 4, 213–219

    work page 2001

  25. [25]

    W. J. Martin and B. E. Sagan, A new notion of transitivity for groups and sets of permutations, J. London Math. Soc. (2) , 73 (2006), no. 1, 1–13

    work page 2006

  26. [26]

    Nomura, Multiple transitivity of perfect 1-codes in symmetric groups, Osaka J

    K. Nomura, Multiple transitivity of perfect 1-codes in symmetric groups, Osaka J. Math., 22 (1985), no. 4, 767–771

    work page 1985

  27. [27]

    Rothaus and J

    O. Rothaus and J. G. Thompson, A combinatorial problem in the symmetric group, Pacific J. Math. , 18 (1966), 175–178

    work page 1966

  28. [28]

    B. E. Sagan, The symmetric group , Second edition, Grad. Texts in Math., 203, Springer-Verlag, New York, 2001

    work page 2001

  29. [29]

    Schmidt, Integer partitions and binary trees, Adv

    F. Schmidt, Integer partitions and binary trees, Adv. in Appl. Math. , 28 (2002), no. 3-4, 592–601

    work page 2002

  30. [30]

    Szab´ o and A

    S. Szab´ o and A. D. Sands, Factoring groups into subsets , Lect. Notes Pure Appl. Math., 257, CRC Press, Boca Raton, FL, 2009

    work page 2009

  31. [31]

    Terada, Perfect codes in SL(2 , 2f), European J

    S. Terada, Perfect codes in SL(2 , 2f), European J. Combin., 25 (2004), no. 7, 1077– 1085

    work page 2004

  32. [32]

    Zieschang, Cayley graphs of finite groups, J

    P.-H. Zieschang, Cayley graphs of finite groups, J. Algebra, 118 (1988), no. 2, 447– 454

    work page 1988

  33. [33]

    Zhou, Total perfect codes in Cayley graphs, Des

    S. Zhou, Total perfect codes in Cayley graphs, Des. Codes Cryptogr., 81 (2016), no. 3, 489–504. 15

    work page 2016