The Ψ1 conjecture computations

Maciej Radziejewski (a part of joint work with Wolfgang A. Schmid)

We describe computations related to the problem considered in the paper “On the Asymptotic Behavior of some Counting Functions” (Maciej Radziejewski and Wolfgang A. Schmid, in preparation). We assume the reader is familiar with the notions of half-factoriality, sequences and block monoids, atoms, zero-sumfree sequences, and the cross number. Some background information can be found in our paper and in many other papers.

Let G be a finite abelian group with at least three elements. Let G0 be a subset of G and g an element of G. We say that the Ψ1 condition is satisfied for G, G0, and g if each atom and zero-sumfree sequence made of elements of G0 with sum -g has the same cross number. Please note that G0 is half-factorial if and only if the Ψ1 condition is satisfied for G, G0, and the neutral element e. We say that G satisfies the Ψ1 condition if there exists at least one half-factorial G0 of maximum cardinality in G and at least one g in G \ G0 such that the Ψ1 condition is satisfied for G, G0, and g.

In our paper and in an earlier paper by the first author it was conjectured (in other terms) that every finite abelian group with at least three elements satisfies the Ψ1 condition. However, the conjecture could only be settled in the affirmative in some special cases. It seems quite intriguing, as the formulation of the problem is quite simple.

The study of this problem was motivated by the investigations of the structure of elements with factorizations of at most k distinct lengths in algebraic number fields and in Krull monoids. A constant that naturally arises in the description of such elements was called Ψk(G) in the paper, where G is the (ideal) class group. The conjecture, as stated here, is equivalent to the statement that Ψ1(G) > 0 for all G with at least three elements. Please refer to the paper for detailed motivation and results. Here we describe the computations showing that the conjecture is true for all G of order less than or equal to 95.

The calculations were performed in the following order (the programs performing the different tasks are named on the left):

parameters_C0 For a given n we find all the groups of order 3 ≤ |G| ≤ n, other than cyclic p-groups and cyclic groups of order pq (where we know the conjecture holds and we know the half-factorial subsets). For each group we compute the list of inclusion-maximal subsets satisfying the C0 condition of J. Sliwa — all up to group automorphy. These serve as parameters for further steps.
max_h-f_within We compute all the inclusion-maximal half-factorial subsets contained in the C0-subsets computed before. That gives us the list of all inclusion-maximal half-factorial subsets (for each group) up to group automorphy (although there still may be multiple half-factorial subsets equivalent by group automorphy).
select_max_card For each group we pick one half-factorial subset of maximum cardinality. It seems that the condition given in the conjecture holds for all half-factorial sets in each group (at least for |G| ≤ 50), while the conjecture only requires it “for at least one half-factorial subset of maximum cardinality”. If the condition is satisfied for the subset we picked, the conjecture is verified for the given group, otherwise we'll have to pick another subset.
psi1 For each group G and the half-factorial subset G0 selected for this group we find the set G0' of elements g in G such that all atoms and zero-sumfree sequences made of elements of G0 with sum -g have the same cross number. Then we output G0' and G0'' = G0' \ G0. If G0'' is nonempty, the conjecture is verified for the given group.

Each program name above provides a link to an executable program file that you are welcome to download and try out (for use under MS Windows 95® or later, tested only under MS Windows XP®). Please note that these programs are command line tools with very little explanation. They can be run using the batch file calc_psi1.bat and the parameter file n.txt (which contains just one number: the maximum group order).

You may also like to browse the C++ source code if you are into programming and would like to study the method in detail.

The results and partial results are given below:

C0.txt Groups and C0 subsets. The neutral element is ommitted from the C0 subsets in order to make the subsequent calculations slightly faster — it is treated in a special way.
h-f.txt (compressed, 1.56 MB) Groups and half-factorial subsets. Again, the neutral element is always ommitted. Here is an uncompressed version with C26 and C25×C4 ommitted (597 KB).
h-f_mu.txt Groups and half-factorial subsets of maximum cardinality (one subset for each group).
psi1.txt Final results: for each group G the subsets G0, G0', and G0'' are given.

The format of the results requires some explanation. Groups are specified as vectors of dimensions in the cyclic p-group decomposition. Subsets are given as vectors of element numbers — the elements within a group of order n are numbered from 0 to n-1. The neutral element always has the number 0. The subsets in C0.txt and h-f.txt are specified as vectors of vectors, because we have lists of subsets there. The same format is used in h-f_mu.txt and psi1.txt, although we only have one subset of each kind. The program vectorize converts element numbers to coordinate vectors, so that the elements of, say, C4 × C2, are represented as [0, 0], [1, 0], …, [3,1]. The batch file vect.bat invokes it to create the files h-f_vectorized.txt (compressed, 2.47 MB) and psi1_vectorized.txt — the vectorized versions of h-f.txt and psi1.txt. There is also an uncompressed version of h-f_vectorized.txt with C26 and C25×C4 ommitted (2.18 MB).

A short “revision history”:

The complete package (all the files referred to on this page as well as the page itself) can be found here (4.5 MB).

© 2004 Maciej Radziejewski. The programs and scripts available from this page come WITHOUT ANY WARRANTY WHATSOEVER. You can use them at your own risk. If you copy any of the programs or scripts, please keep them together with this web page file.

(Back to the main page)

To send me an e-mail, you can click on my name (please modify the spam-protected address): Maciej Radziejewski.