ACTA issues

Four-element generating sets of partition lattices and their direct products

Gábor Czédli, Lillian Oluoch

Acta Sci. Math. (Szeged) 86:3-4(2020), 405-448

Abstract. Let $n>3$ be a natural number. By a 1975 result of H. Strietz, the lattice Part$(n)$ of all partitions of an $n$-element set has a four-element generating set. In 1983, L. Zádori gave a new proof of this fact with a particularly elegant construction. Based on his construction from 1983, the present paper gives a lower bound on the number $\gnu n$ of four-element generating sets of Part$(n)$. We also present a computer-assisted statistical approach to $\gnu n$ for small values of $n$. In his 1983 paper, L. Zádori also proved that for $n\geq 7$, the lattice Part$(n)$ has a four-element generating set that is not an antichain. He left the problem whether such a generating set for $n\in \set {5,6}$ exists open. Here we solve this problem in negative for $n=5$ and in affirmative for $n=6$. Finally, the main theorem asserts that the direct product of some powers of partition lattices is four-generated. In particular, by the first part of this theorem, $\Part {n_1}\times \Part {n_2}$ is four-generated for any two distinct integers $n_1$ and $n_2$ that are at least 5. The second part of the theorem is technical but it has two corollaries that are easy to understand. Namely, the direct product $\Part {n}\times \Part {n+1}\times \dots \times \Part {3n-14}$ is four-generated for each integer $n\geq 9$. Also, for every positive integer $u$, the $u$-th the direct power of the direct product $\Part {n}\times \Part {n+1}\times \dots \times \Part {n+u-1}$ is four-generated for all but finitely many $n$. If we do not insist on too many direct factors, then the exponent can be quite large. For example, our theorem implies that the $ 10^{127}$-th direct power of $\Part {1011}\times \Part {1012}\times \dots \times \Part {2020}$ is four-generated.

DOI: 10.14232/actasm-020-126-7

AMS Subject Classification (1991): 06B99, 06C10

Keyword(s): equivalence lattice, partition lattice, four-element generating set, sublattice, statistics, computer algebra, computer program, direct product of lattices, generating partition lattices, semimodular lattice, geometric lattice

received 26.6.2020, revised 22.9.2020, accepted 27.9.2020. (Registered under 626/2020.)