Metraipolis › archive › dc_cdbe3f6166b5

Efficient Enumeration of Enclosed Vector Spaces — arXiv:2608.16359

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.16359
License (as archived): CC0-1.0
Archived: 2026-10-19T00:11:26.713Z
SHA-256 of the archived text: a0e77f68a735c130649fdc610a9c3128b5d34c910aacb5e7c61ec9b84097d498
Stable URL of this page: https://metraipolis.com/documento/dc_cdbe3f6166b5

How to cite

Efficient Enumeration of Enclosed Vector Spaces — arXiv:2608.16359 — arXiv (en), https://arxiv.org/abs/2608.16359 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cdbe3f6166b5 (Metraipolis archive dc_cdbe3f6166b5, sha256 a0e77f68a735c130649fdc610a9c3128b5d34c910aacb5e7c61ec9b84097d498)

BibTeX

@misc{dccdbe3f6166b5,
  title = {Efficient Enumeration of Enclosed Vector Spaces — arXiv:2608.16359},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.16359},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cdbe3f6166b5; sha256 a0e77f68a735c130649fdc610a9c3128b5d34c910aacb5e7c61ec9b84097d498},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.16359. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In this paper, we address several problems concerning vector spaces enclosed in a given set. Let V be a vector space over a finite field of cardinality c, and let $S \subseteq V$ be a set of vectors. A space enclosed in S is a vector subspace W of V that is also contained in S: $W \subseteq S$. We focus on enumeration problems, where the task is to list all solutions, and we first provide an algorithm to enumerate all spaces that are enclosed in S. Our algorithm is further adapted to solve two more problems: the enumeration of (inclusion-)maximal enclosed spaces, and the problem of finding an enclosed space of maximum dimension. The latter problem arises in the context of Boolean functions' regularity detection. It can also be seen as a dual version of the well-known linear span: indeed, the span is the minimum-dimension vector space that contains a given set of vectors S, and it is a fundamental concept in linear algebra. Our proposed algorithms are based on the binary partition paradigm, and have total time complexity $e^{\frac{1}{2\ln c}\ln^2 n - \Theta(\log n \log \log n)}$, where $n= |\inputset|$. The first version, for enumerating all enclosed spaces, also achieves a delay (time between consecutive outputs) of O(n). Our algorithms provide a quadratic speed-up with respect to a brute-force approach, although the speed-up appears even greater in our experimental evaluation on boolean vector spaces.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-18 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2608.16359 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T23:35:27.644Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).