The Ψ₁ 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 G₀ be a subset of G and g an element of G. We say that the Ψ₁ condition is satisfied for G, G₀, and g if each atom and zero-sumfree sequence made of elements of G₀ with sum -g has the same cross number. Please note that G₀ is half-factorial if and only if the Ψ₁ condition is satisfied for G, G₀, and the neutral element e. We say that G satisfies the Ψ₁ condition if there exists at least one half-factorial G₀ of maximum cardinality in G and at least one g in G \ G₀ such that the Ψ₁ condition is satisfied for G, G₀, 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 Ψ₁ 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 Ψ₁(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:

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, C₄ × C₂, are represented as [0, 0], [1, 0], …, [3,1]. The batch file vect.bat invokes it to create the files h-f_vectorized.txt and psi1_vectorized.txt — the vectorized versions of h-f.txt and psi1.txt.

A short “revision history”:

• 2001, December — a program for determining the structure of the sets of elements with factorizations of at most k distinct lengths in a Krull monoid with a given class group. This program was limited to class groups of at most 8 elements and small k. The number of computations increased very fast with the group order.
• 2002, February — a specific program for checking the conjecture allowed all groups of order up to 24 to be covered.
• 2004, June — the present version, written from scratch, with many speedups.

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

© 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)