О существовании разбиений, примитивных по Агиевичу

О существовании разбиений, примитивных по Агиевичу

Таранников Ю. В.
Дискретный анализ и исследование операций, 29, 4, 104-123 (2022)
Скачать статью

УДК 519.115.5 
DOI: 10.33048/daio.2022.29.747

Аннотация:

Доказано, что для любого натурального $m$ существует наименьшее натуральное $N = N_{q}(m)$ такое, что при $n > N$ не существует $А$-примитивных разбиений пространства $F_q^n$ на $q^m$ аффинных подпространств размерности $n - m$. Получены нижние и верхние оценки на величину $N_{q}(m)$. Доказано, что $N_{q}(2) = q + 1$. Результаты того же типа установлены для разбиений на грани. 
Библиогр. 16.

Литература:
  1. Heden O. A survey of the different types of vector space partitions // Discrete Math. Algorithms Appl. 2012. V. 4, No. 1. P. 1–14. 
     
  2. Akman F., Sissokho P. A. Reconfiguration of subspace partitions // J. Comb. Des. 2022. V. 30, No. 1. P. 5–18. 
     
  3. Августинович С. В., Соловьёва Ф. И., Хеден У. О разбиениях $n$-куба на неэквивалентные совершенные коды // Пробл. передачи информ. 2007. Т. 43, № 4. С. 45–50. 
     
  4. Agievich S. V. Bent rectangles // Boolean functions in cryptology and information security. Amsterdam: IOS Press, 2008. P. 3–22. (NATO Sci. Peace Secur. Ser. D: Inf. Commun. Secur.; V. 18).
     
  5. Баксова И. П., Таранников Ю. В. Об одной конструкции бент-функций // Обозрение прикл. и промышл. математики. 2020. Т. 27, № 1. С. 64–66. 
     
  6. Баксова И. П., Таранников Ю. В. Оценки числа разбиений пространства $F_2^m$ на аффинные подпространства размерности $k$ // Вестн. Моск. ун-та. Сер. 1. Математика, механика. 2022. № 3. С. 21–25. 
     
  7. Potapov V. N., Taranenko A. A., Tarannikov Yu. V. Asymptotic bounds on numbers of bent functions and partitions of the Boolean hypercube into linear and affine subspaces. Ithaca, NY: Cornell Univ., 2021. (Cornell Univ. Libr. e-Print Archive; arXiv:2108.00232). 
     
  8. Логачёв О. А., Сальников А. А., Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: Ленард, 2021. 576 с. 
     
  9. Heden O., Solov’eva F. Partitions of $F^n$ into non-parallel Hamming codes // Adv. Math. Commun. 2009. V. 3, No. 4. P. 385–397. 
     
  10. Krotov D. S. A partition of the hypercube into maximally nonparallel Hamming codes // J. Comb. Des. 2014. V. 22, No. 4. P. 179–187. 
     
  11. Rivest R. L. On hash-coding algorithms for partial-match retrieval // Proc. 15th Annu. Symp. Switching Automata Theory (New Orleans, USA, Oct. 14–16, 1974). Piscataway: IEEE, 1974. P. 95–103. 
     
  12. Brouwer A. E. On associative block designs // Combinatorics. Amsterdam: North-Holland, 1978. P. 173–184. (Colloq. Math. Soc. J. Bolyai; V. 18). 
     
  13. Van Lint J. H. {$0, 1, \ast$}-Distance problems in combinatorics // Surveys in Combinatorics. Inv. Pap. 10th British Comb. Conf. (Glasgow, UK, July 22–26, 1985). Cambridge: Camb. Univ. Press, 1985. P. 113–135. (Lond. Math. Soc. Lect. Notes Ser.; V. 103). 
     
  14. Potapov V. N. DP-colorings of uniform hypergraphs and splittings of Boolean hypercube into faces // Electron. J. Comb. 2022. V. 29, No. 3, ID P3.37. 7 p. 
     
  15. Van Lint J. H., Wilson R. M. A course in combinatorics. Cambridge: Camb. Univ. Press, 2001. 620 p. 
     
  16. La Poutré J. A. A theorem on associative block designs //Discrete Math. 1986. V. 58, No. 2. P. 205–208.

Исследование выполнено при финансовой поддержке Министерства науки и высшего образования России в рамках программы Московского центра фундаментальной и прикладной математики (соглашение № 075–15–2022–284).

Таранников Юрий Валерьевич
  1. Московский государственный университет им. М. В. Ломоносова,
    Ленинские горы, 1, 119991 Москва, Россия
  2. Московский центр фундаментальной и прикладной математики,
    Ленинские горы, 1, 119991 Москва, Россия

E-mail: yutarann@gmail.com

Статья поступила 11 июля 2022 г. 
После доработки — 28 июля 2022 г. 
Принята к публикации 28 июля 2022 г.

Abstract:

We prove that for any positive integer $m$ there exists the smallest positive integer $N = N_{q}(m)$ such that for $n > N$ there are no Agievich-primitive partitions of the space $F_q^n$ into $q^m$ affine subspaces of dimension $n - m$. We give lower and upper bounds on the value $N_{q}(m)$ and prove that $N_{q}(2) = q + 1$. Results of the same type for partitions into coordinate subspaces are established.
Bibliogr. 16.

References:
  1. O. Heden, A survey of the different types of vector space partitions, Discrete Math. Algorithms Appl. 4 (1), 1–14 (2012).
     
  2. F. Akman and P. A. Sissokho, Reconfiguration of subspace partitions, J. Comb. Des. 30 (1), 5–18 (2022).
     
  3. S. V. Avgustinovich, F. I. Solov’eva, and O. Heden, Partitions of an $n$-cube into nonequivalent perfect codes, Probl. Peredachi Inf. 43 (4), 45–50 (2007) [Russian] [Probl. Inf. Transm. 43 (4), 310–315 (2007)].
     
  4. S. V. Agievich, Bent rectangles, in Boolean Functions in Cryptology and Information Security (IOS Press, Amsterdam, 2008), pp. 3–22 (NATO Sci. Peace Secur. Ser. D: Inf. Commun. Secur., Vol. 18).
     
  5. I. P. Baksova and Yu. V. Tarannikov, On a construction of bent functions, Obozr. Prikl. Prom. Mat. 27 (1), 64–66 (2020) [Russian].
     
  6. I. P. Baksova and Yu. V. Tarannikov, The bounds on the number of partitions of the space $F_2^m$ into $k$-dimensional affine subspaces, Vestn. Mosk. Univ., Ser. 1. Mat. Mekh., No. 3, 21–25 (2022) [Russian] [Mosc. Univ. Math. Bull. 77 (3), 131–135 (2022)].
     
  7. V. N. Potapov, A. A. Taranenko, and Yu. V. Tarannikov, Asymptotic bounds on numbers of bent functions and partitions of the Boolean hypercube into linear and affine subspaces (Cornell Univ., Ithaca, NY, 2021) (Cornell Univ. Libr. e-Print Archive, arXiv:2108.00232).
     
  8. O. A. Logachev, A. A. Salnikov, S. V. Smyshlyaev, and V. V. Yashchenko, Boolean Functions in Coding Theory and Cryptography (Lenard, Moscow, 2021) [Russian].
     
  9. O. Heden and F. I. Solov’eva, Partitions of $F^n$ into non-parallel Hamming codes, Adv. Math. Commun. 3 (4), 385–397 (2009).
     
  10. D. S. Krotov, A partition of the hypercube into maximally nonparallel Hamming codes, J. Comb. Des. 22 (4), 179–187 (2014).
     
  11. R. L. Rivest, On hash-coding algorithms for partial match retrieval, in Proc. 15th Annu. Symp. Switching Automata Theory, New Orleans, USA, Oct. 14–16, 1974 (IEEE, Piscataway, 1974), pp. 95–103.
     
  12. A. E. Brouwer, On associative block designs, in Combinatorics (North-Holland, Amsterdam, 1978), pp. 173–184 (Colloq. Math. Soc. J. Bolyai, Vol. 18).
     
  13. J. H. van Lint, {$0, 1, \ast$}-distance problems in combinatorics, in Surveys in Combinatorics (Inv. Pap. 10th British Comb. Conf., Glasgow, UK, July 22–26, 1985) (Camb. Univ. Press, Cambridge, 1985), pp. 113–135 (Lond. Math. Soc. Lect. Notes Ser., Vol. 103).
     
  14. V. N. Potapov, DP-colorings of uniform hypergraphs and splittings of Boolean hypercube into faces, Electron. J. Comb. 29 (3), ID P3.37, 7 p. (2022).
     
  15. J. H. van Lint and R. M. Wilson, A Course in Combinatorics (Camb. Univ. Press, Cambridge, 2001), 620 p.
     
  16. J. A. La Poutré, A theorem on associative block designs, Discrete Math. 58 (2), 205–208 (1986).