Embedded Files
Abstract
U(n) as a group is not necessarily cyclic. The automatic generation of these U(n) and explicit creation of the Cayley tables for U(n) will greatly ease the burden of computation for researchers using U(n) as a group. This Java application uses parallel computing methodologies to speed up the computation of separate U(n)s with load-leveling being done between the threads to ensure relatively even spread of work.
Impact
Creating the U(n) Generator will allow researchers to construct large numbers of U(n) groups and record particular attributes of the requested groups. With flags for constructing the Cayley table, subgroups generated by each element, order, cyclic, and also the distinct cyclic subgroup generators, group isomorphisms can quickly be determined between U(n) groups. This tool will also come with a small dictionary of selected U(n) groups that have already been described by the program.
A Classical Definition
In Algebra, there are objects called groups. These objects are usually first introduced with the group of integers under addition (ℤ). Often this leads into a discussion of how the integers are not a group under multiplication. because some elements have no inverse. Restricting the set of integers up to n to integers less than and relatively prime to n does result in a group under multiplication. This group is called U(n) or the quotient group.
Technical Approach
Generating U(n)
For the requested U(n), each thread is given a starting point initialized at the lowest requested n. When a thread is done with describing the given U(n), it skips to the next n that hasn't been completed yet.
Sequentially, all integers less than the given n are added to an array, and iterated through to find all that are relatively prime to n, removing the elements that are not relatively prime.
Describing U(n)
For the requested U(n), the following attributes can be calculated:
U(n) as a set
The number of elements in U(n)
Each subgroup generated by each element in U(n)
The multiplication table for this U(n)
Whether this U(n) is cyclic or not
The distinct cyclic subgroups of this U(n)
The Hypervisor
To maintain the status of each of the threads, and how far each of them have gotten in their tasks, the main thread is kept in a while loop that continues until each of the threads has completed all of its assigned work. This thread periodically (every 10 seconds) requests that status of each of the threads' completion as a percentage and aggregates the total percentage completion. It is then reported to the user via the command line each individual thread's completion as well as the aggregated completion percentage. Breaking into each thread's completion percentage is pertinent because the distribution of prime numbers, and thereby the order of each U(n) is not guaranteed to be consistent between the threads.
Results and Discussion
The use of U(n) Generator has allowed the creation of the following files that comprise descriptions of U(n) from n=3 through n=500 with Cayley tables.
As n grows larger, the usability of a Cayley table diminishes, and as such for n between 500 and 2,000, no Cayley table are given.
Availability of Code
The code is currently available on its GitHub project page here. The project can be downloaded and ran on any machine with the Java runtime environment.
Using the Code
To allocate the maximum number of threads, Line 6 of UnGenerator.java should be updated appropriately. It is also recommended to allocate one less thread than the total number of available threads on the system you intend to run the code on so that the system doesn't lock up in the event that you request the termination of the program.
To request a specific range of U(n)s to describe, lines 8 and 9 of UnGenerator.java must be modified respectively.
To change the directory that output files will be saved, line 15 of UnGenerator.java must be updated appropriately. This input allows for relative paths, and defaults to an output folder located in the active directory.
To select the appropriate U(n) descriptors to be saved to file, the respective function calls inside Un.java's get_details() function must remain uncommented. Because of the large runtime impact and file readability concerns, this defaults to having the Cayley table not written to file.
Future Work
Since the program is currently without a graphical interface, one could be constructed so as to make the code more easily used by researchers.
As the code currently is, as well, it generates multiple files that are split by the work each of the threads completed. A final pass of the program could be constructed to "zipper" up the part files into part files that contain lexicographically ordered U(n)s.
The code is currently written in Java, but again increase the approachability of the code, it can be refactored into Python or some other language that is more familiar to mathematics research.
Google Sites
Report abuse