|
Prikladnaya Diskretnaya Matematika. Supplement, 2024, Issue 17, Pages 34–37 DOI: https://doi.org/10.17223/2226308X/17/8
(Mi pdma638)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Discrete Functions
On the number of functions that break subspaces of dimension $3$ and higher
N. A. Kolomeets Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
DOI:
https://doi.org/10.17223/2226308X/17/8
Abstract:
We consider the sets $\mathcal{P}_{n}^{k}$ consisting of invertible functions $F: \mathbb{F}_2^{n} \to \mathbb{F}_2^{n}$ such that any $U \subseteq \mathbb{F}_2^{n}$ and its image $F(U)$ are not simultaneously $k$-dimensional affine subspaces of $\mathbb{F}_2^{n}$, where $3 \leq k \leq n - 1$. We present lower bounds for the cardinalities of all such $\mathcal{P}_{n}^{k}$ and $\mathcal{P}_{n}^{k} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}$ that improve the result of W. E. Clark et al., 2007 providing that these sets are not empty. We prove that almost all permutations of $\mathbb{F}_2^{n}$ belong to $\mathcal{P}_{n}^{4} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}$. Asymptotic lower and upper bounds of $|\mathcal{P}_{n}^{3}|$ and $|\mathcal{P}_{n}^{3} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}|$ up to $o(2^n!)$ are obtained as well. The number of functions from $\mathcal{P}_{n}^{4} \cap \ldots \cap \mathcal{P}_{n}^{n - 1}$ that map exactly one $3$-dimensional affine subspace of $\mathbb{F}_2^{n}$ to an affine subspace is estimated.
Keywords:
affine subspaces, invariant subspaces, permutations, asymptotic bounds.
Citation:
N. A. Kolomeets, “On the number of functions that break subspaces of dimension $3$ and higher”, Prikl. Diskr. Mat. Suppl., 2024, no. 17, 34–37
Linking options:
https://www.mathnet.ru/eng/pdma638 https://www.mathnet.ru/eng/pdma/y2024/i17/p34
|
|