Minimum-sized generating sets of the direct powers of free distributive lattices: Dedicated to the memory of George F. McNulty

Gábor Czédli

doi:10.56754/0719-0646.2602.217

DOI:

https://doi.org/10.56754/0719-0646.2602.217

Abstract

For a finite lattice \(L\), let Gm(\(L\)) denote the least \(n\) such that \(L\) can be generated by \(n\) elements. For integers \(r>2\) and \(k>1\), denote by FD\((r)^k\) the \(k\)-th direct power of the free distributive lattice FD(\(r\)) on \(r\) generators. We determine Gm(FD\((r)^k\)) for many pairs \((r,k)\) either exactly or with good accuracy by giving a lower estimate that becomes an upper estimate if we increase it by 1. For example, for \((r,k)=(5,25\,000)\) and \((r,k)=(20,\ 1.489\cdot 10^{1789})\), Gm(FD\((r)^k\)) is \(22\) and \(6\,000\), respectively. To reach our goal, we give estimates for the maximum number of pairwise unrelated copies of some specific posets (called full segment posets) in the subset lattice of an \(n\)-element set. In addition to analogous earlier results in lattice theory, a connection with cryptology is also mentioned among the motivations.

Keywords

Free distributive lattice , minimum-sized generating set , small generating set , direct power , Sperner theorem , 3-crown poset , cryptography

Mathematics Subject Classification:

06D99 , 05D0

Gábor Czédli University of Szeged, Bolyai Institute. Szeged, Aradi vértanúk tere 1, Hungary. https://orcid.org/0000-0001-9990-3573

Pages: 217–237
Date Published: 2024-07-02
Vol. 26 No. 2 (2024)

D. Ahmed and G. Czédli, “(1 + 1 + 2)-generated lattices of quasiorders,” Acta Sci. Math. (Szeged), vol. 87, no. 3-4, pp. 415–427, 2021, doi: 10.14232/actasm-021-303-1.

I. Chajda and G. Czédli, “How to generate the involution lattice of quasiorders?” Studia Sci. Math. Hungar., vol. 32, no. 3-4, pp. 415–427, 1996.

G. Czédli, “Generating boolean lattices by few elements and exchanging session keys,” 2023, arXiv:2303.10790.

G. Czédli, “Sperner theorems for unrelated copies of some partially ordered sets in a powerset lattice and minimum generating sets of powers of distributive lattices,” 2023, arXiv:2308.15625.

G. Czédli, “Four-generated direct powers of partition lattices and authentication,” Publ. Math. Debrecen, vol. 99, no. 3-4, pp. 447–472, 2021, doi: 10.5486/pmd.2021.9024.

G. Czédli, “Generating some large filters of quasiorder lattices,” Acta Sci. Math. (Szeged), 2024, doi: 10.1007/s44146-024-00139-5.

G. Czédli and L. Oluoch, “Four-element generating sets of partition lattices and their direct products,” Acta Sci. Math. (Szeged), vol. 86, no. 3-4, pp. 405–448, 2020, doi: 10.14232/actasm-020-126-7.

A. P. Dove and J. R. Griggs, “Packing posets in the Boolean lattice,” Order, vol. 32, no. 3, pp. 429–438, 2015, doi: 10.1007/s11083-014-9343-7.

I. M. Gel’fand and V. A. Ponomarev, “Problems of linear algebra and classification of quadruples of subspaces in a finite-dimensional vector space,” in Hilbert space operators and operator algebras (Proc. Internat. Conf., Tihany, 1970), ser. Colloq. Math. Soc. János Bolyai. North- Holland, Amsterdam-London, 1972, vol. 5, pp. 163–237.

G. Grätzer, Lattice Theory: Foundation. Birkhäuser/Springer Basel AG, Basel, 2011, doi: 10.1007/978-3-0348-0018-1.

J. R. Griggs, J. Stahl, and W. T. Trotter, Jr., “A Sperner theorem on unrelated chains of subsets,” J. Combin. Theory Ser. A, vol. 36, no. 1, pp. 124–127, 1984, doi: 10.1016/0097- 3165(84)90085-2.

G. O. H. Katona and D. T. Nagy, “Incomparable copies of a poset in the Boolean lattice,” Order, vol. 32, no. 3, pp. 419–427, 2015, doi: 10.1007/s11083-014-9342-8.

J. Kulin, “Quasiorder lattices are five-generated,” Discuss. Math. Gen. Algebra Appl., vol. 36, no. 1, pp. 59–70, 2016, doi: 10.7151/dmgaa.1248.

D. Lubell, “A short proof of Sperner’s lemma,” J. Combinatorial Theory, vol. 1, p. 299, 1966.

N. J. A. Sloane, “The On-Line Encyclopedia of Integer Sequences,” https://oeis.org/, accessed: 2024-06-07.

E. Sperner, “Ein Satz über Untermengen einer endlichen Menge,” Math. Z., vol. 27, no. 1, pp. 544–548, 1928, doi: 10.1007/BF01171114.

H. Strietz, “Über Erzeugendenmengen endlicher Partitionverbände,” Studia Sci. Math. Hun- garica, vol. 12, pp. 1–17, 1977.

G. Takách, “Three-generated quasiorder lattices,” Discuss. Math. Algebra Stochastic Methods, vol. 16, no. 1, pp. 81–98, 1996.

L. Zádori, “Generation of finite partition lattices,” in Lectures in universal algebra (Szeged, 1983), ser. Colloq. Math. Soc. János Bolyai. North-Holland, Amsterdam, 1986, vol. 43, pp. 573–586.

L. Zádori, “Subspace lattices of finite vector spaces are 5-generated,” Acta Sci. Math. (Szeged), vol. 74, no. 3-4, pp. 493–499, 2008.