Counting the decimation classes of binary vectors with relatively prime length and density
- PDF / 476,523 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 81 Downloads / 160 Views
Counting the decimation classes of binary vectors with relatively prime length and density Jonathan S. Turner1 · Dursun A. Bulutoglu1 · Daniel Baczkowski2 · Andrew J. Geyer1 Received: 14 February 2020 / Accepted: 30 October 2020 © This is a U.S. Government work and not under copyright protection in the US; foreign copyright protection may apply 2020
Abstract We present a method for determining the number of decimation classes of density δ binary vectors indexed by a finite abelian group G of size and exponent ∗ such that δ is relatively prime to ∗ . This method is the first which is not based on exhaustive vector generation and exploits the subgroup lattice of Z× ∗ . Instead, our method is based on our newly developed theory of multipliers for arbitrary subsets of finite abelian groups, our results on orbits under the action of the multiplier group, and finding the number of solutions of a potentially highly symmetric subset sum problem. Implementing our method on vectors indexed by Z of odd length and density ( + 1)/2 greatly increased the number of for which the number of decimation classes of such vectors is known. Additionally, our newly developed theory provides information on the number of distinct translates fixed by each member of the multiplier group as well as sufficient conditions for each member of the multiplier group to be translate fixing. Keywords Bracelet · Lattice of subgroups · Legendre pair · Multiplier group · Necklace · Recursion Mathematics Subject Classification 90C10 · 05B10 · 05B20 · 05C25 · 20B05 · 20B25
B
Dursun A. Bulutoglu [email protected] Jonathan S. Turner [email protected] Daniel Baczkowski [email protected] Andrew J. Geyer [email protected]
1
Department of Mathematics and Statistics, Air Force Institute of Technology, Wright-Patterson Air Force Base, OH 45433, USA
2
Department of Mathematics, University of Findlay, Findlay, OH 45840, USA
123
Journal of Algebraic Combinatorics
1 Introduction In this paper, we present a method for determining the number of decimation classes of fixed density vectors indexed by a finite abeliangroup G of order , where the density of a vector v ∈ {0, 1}G is defined to be δ = g∈G vg . A block circulant shift of a vector v by g ∈ G, denoted by cg (v), is defined to be cg (v) h = vh−g for each h ∈ G [11]. Block circulant shifts are also known as translates [7]. Throughout, we use | · | to denote the order of a group or the cardinality of a set. For an isomorphism, : G 1 → G 2 , and a set I ⊆ G 1 , (I ) = {(i) | i ∈ I }. We assume that G is a finite abelian group that has the operation + unless specified otherwise. It is well known that such a group is isomorphic to Z1 × · · · × Zr for some 1 , 2 , . . . , r ∈ Z≥1 . Throughout the paper, Z× = { j ∈ Z | gcd( j, ) = 1} and ∗ denotes the exponent of the group G ∼ = Z1 × · · · × Zr , i.e., the smallest positive integer n such that ng = 0 for all g ∈ G. Any subgroup H or K of Z× ∗ is always written multiplicatively with its identity element
Data Loading...
