Distribution of Squares and Hypothesis Verification in Odd Integer Partitions
DOI:
https://doi.org/10.14529/cmse240102Keywords:
integer partition, asymptotic formula, parallel computing, OpenMPAbstract
The article considers partitions of a natural number n whose parts are distinct, odd and their product is not a square. Such partitions are applicable for determining the rank of the group of central units of an integral group ring of an alternating group. The number of partitions grows exponentially, hence the enumeration task is computationally expensive. The article proposes a parallel algorithm in shared memory for finding the number of partitions of the n with additional conditions. The algorithm is based on the concept of data parallelism and the use of nested parallelism. A set of lengths K of the partition of the n is obtained, the elements of which are processed in parallel. During the processing of the length k of the partition of the n, the set of levels L is obtained, the elements of which are processed in parallel as well. Acceptable values of speedup and parallel efficiency of the proposed algorithm are obtained by using two threads per parallel length region and two threads per parallel level region. Thus, the speedup for distinct n increases to 2.1, and the parallel efficiency does not decrease below 50 %. The results obtained were used to check Kargapolov’s hypotheses and analyze the distribution of the number of odd partition in certain ranges. An algorithm for finding the optimal coefficient c is proposed. Using this algorithm, an asymptotic formula for the number of partitions of the n is obtained, in which the parts are distinct, odd and their product is a square. This formula is based on experimental data and formulated as a conjecture.References
Ferraz R.A. Simple components and central units in group algebras. Journal of Algebra. 2004. Vol. 279, no. 1. P. 191–203. DOI: 10.1016/j.jalgebra.2004.05.005.
Aleev R.Z., Kargapolov A.V., Sokolov V.V. The ranks of central unit groups of integral group rings of alternating groups. Fundamental and Applied Mathematics. 2008. Vol. 14, no. 7. P. 15–21. (in Russian).
Kargapolov A.V. Central units of integral group rings of alternating groups: PhD thesis / Kargapolov Andrey Valerievich. South Ural State University, Russia, 2012. (in Russian).
Sagan B.E. The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions. New York: Springer New York, 2001. XVI, 240 p. DOI: 10.1007/978-1-4757-6804-6.
Doliskani J.N., Malekian E., Zakerolhosseini A. A Cryptosystem Based on the Symmetric Group Sn. IJCSNS International Journal of Computer Science and Network Security. 2008. Vol. 8, no. 2. P. 226–234.
Andrews G. The Theory of Partitions. Moscow: Nauka, 1982. 256 p. (in Russian).
Postnikov A.G. Introduction to Analytic Number Theory. Moscow: Nauka, 1971. 416 p. (in Russian).
Lipsky V. Combinatorics for Programmers. Moscow: Mir, 1988. 200 p. (in Russian).
Anderson J.A. Discrete Mathematics with Combinatorics. Moscow: Williams, 2004. 960 p. (in Russian).
Kelley C.T. Iterative Methods for Optimization. University City, Philadelphia: Society for Industrial аnd Applied Mathematics, 1999. 196 p. DOI: 10.1137/1.9781611970920.
Samoilov A.A. Study of partitions with additional conditions. URL: https://github.com/SashaSamoilov/qop-partitions (accessed: 25.09.2023).
