Math 3500-101 Instructor: Dr. V. Rykov End of Class Report VARSHAMOV-GILBERT BOUNDS FOR PARTITION CODES Jaime Lopez University of Nebraska at Omaha Undergraduate Program E-mail: [email protected] Adviser : Dr. Vyacheslav Rykov Professor of Mathematics University of Nebraska at Omaha E-mail: [email protected] 1. Abstract Partition codes characterize the partitioning of n elements into q partitions, with 2≤q<n. The space generated by such codes is nonhomogeneous, resulting in the inability to define a closed formula for determining the volume of a sphere for various n and q. With the use of a Java program developed by the team, we calculate the Varshamov-Gilbert bounds as generated from the average sphere volume for various values of n and q. 2. Statement of the Problem Partition codes have the potential to be applicable for many societal needs, most notably the diagnosis of mental impairments in youth. One method for diagnosing autism involves having the child divide a finite set of objects into partitions of their choosing. The psychiatrist administering the test compares the results against those from other children that have been deemed autistic. By using some type of distance measure between the child’s results and the mean for autistic children, the psychiatrist can make a guess as to if the child also has autism. Clearly, this method contains several areas that could result in a misdiagnosis. First, the method for evaluating the distance from one child’s results to another’s is, by enlarge, subjective, resulting in variant diagnosis among psychiatrists. Secondly,the distance away from the autistic mean that still constitutes a positive diagnosis is not as quantifiably sound as it could be. Developing the theory of partition codes would provide a way to quantifiably support a diagnosis that is neither haphazard nor subjective. By defining a distance metric and calculating the lower bound properties of various q-ary sequences of length n, we hope to help in the accurate and quantifiable diagnosis of such mental illnesses. 3. Definitions and Theorems Definition 1: Let n > q ≥ 2 be fixed integers, Aq = {0,1,…q-1} be the standard q-ary alphabet, and Mq={µ}, µ=µ(x), be the set of all q! one-to-one permutations of Aq, i.e. y= µ(x), x= µ-1(y), x,yεAq={0,1,…,q-1}, µ, µ-1εMq. [1] Definition 2: Let x=(x1,x2,…xn) ε AqXXXXX be an arbitrary q-ary n-sequence which identifies an unordered q-partition x={E0(x),E1(x),…,Eq-1(x)} of the set [n]=E0(x)+E1(x)+…+Eq-1(x), where Ex(x)={i:xi=x}, xεAq. [1] Given these definitions, a distance metric between two arbitrary q-ary n-sequences, x and y, can be defined as follows: Definition 3: The minimum distance between two arbitrary q-ary n-sequences x` and y` is described as: d(x,y`)=min(H(µ(x), y)), where µ(x) denotes any permutation of x on Aq and H(x,y) denotes the standard Hamming distance between two q-ary numerical sequences of length n. Example 1: Let x=(1,1,2,1,2,3,3,2,2,1) and y=(1,2,3,1,1,2,2,3,1,3). The distance between x and y would be 4 because by permuting y, we can get y=(1,2,3,1,1,2,2,3,1,3)=(1,3,2,1,1,3,3,2,1,2), whose Hamming distance to x is 4. Definition 4: The Stirling number of the second kind, S(n,k), is defined as the number of ways to partition a set of n elements into k nonempty subsets, and can be shown as: nniiiqiqqqnS )()1(!1),(0−⎟⎟⎠⎞⎜⎜⎝⎛−=∑= Definition 5: The Bell number, Bn, is defined as the number of partitions of a setof n elements, and can be shown as the sum of Stirling numbers, in that: ∑==nininSB0),( The Bell number provides a method to calculate the sphere size of distance d around the origin, or in our case, the partition code with only one partition (i.e. 111111…1), via the following relationship: ∑∑∑−==−=⎟⎟⎠⎞⎜⎜⎝⎛+=⎟⎟⎠⎞⎜⎜⎝⎛+=11111),(11),,(qidkqdkikSknBkndqnV 4. Methodology Given the aforementioned distance metric, the task quickly became that of finding the total number of partitions of each distance, d, for all codewords in Aq, for various n and q. To accomplish this, we wrote a Java program that cycles over all representative partitions, calculates the distance between it and all other representative partitions, and maintains a count for all distance. We define a representative codeword to be one that can be represented in multiple ways. For example, 11112 and 11113 are the same partition, and, thus, should not both be used in calculations. In an attempt to make speed a priority, an open source implementation of Hungarian Algorithm was integrated into the program for use with calculating the distance. Using this algorithm, most commonly used for solving assignment problems in an attempt to minimize “cost,” we used it to maximize the cost of permuting a partition. Subtracting the sum of the “costs” chosen by the algorithm from the length of either codeword (they should be equal) results in the minimum distance value. Example 2: Given the same x` and y` as Example 1, a matrix containing the frequency of mapping each partition in x` to each partition in y` was generated. x`/y` 1 2 3 1 2 1 1 2 2 0 2 3 0 2 0 The Hungarian Algorithm then takes this matrix and chooses the three assignments that maximize the “cost,” such that only one is chosen from each row and column, namely, 1→1, 3→2, and 2→3, resulting in the permutation of y =(1,3,2,1,1,3,3,2,1,2). By subtracting the sum of the frequencies chosen (i.e. 2+2+2=6) for the permutation of x from the length of x (or subsequently y ), we get the resulting value of 10-6=4. As mentioned, the distance value is calculated for every x`-y` pair in Aq, and the frequency of each is collected. Upon the completion of the distance calculations, the average sphere size for each distance value is calculated as shown: ),,()(dqnVdqdfVavgq⎟⎟⎠⎞⎜⎜⎝⎛= (1)where )(df denotes the frequency of occurrence for distance d and ),,( dqnV denotes the sphere size derived from the Bell number for a given n, q, and d. Dividing by ⎟⎟⎠⎞⎜⎜⎝⎛dq is necessary because there exist ⎟⎟⎠⎞⎜⎜⎝⎛dq code words that are the d positions away from the origin (i.e. 111…11). The results are shown in Table 1. Table 1: The Average Sphere Sizes for Various n and q Values n 4 4 46668 8 9 10 q 2 3 42342 4 3 2 d Average Sphere