4
$\begingroup$

The number of groups of order $n$ (gnu(n)) can be calculated by a closed formula, if $n$ is squarefree. I could calculate the values with GAP, additionally, I programmed a version in PARI/GP, working fine. I found

$$gnu(8{,}574{,}796{,}230)=1{,}243{,}776$$

and I wonder, whether this is the smallest example $n$ with $gnu(n)>10^6$.

I am looking for a faster way because it takes long (also with GAP) to simply apply brute-force.

It is clear that two prime factors are not enough because $gnu(n)$ is at most $2$ in this case.

If $n$ has $3$ prime factors, of which the smallest is $p$, then $gnu(n)$ is at most $p+4$.

I worked out an upper bound for $4$ prime factors, which I cannot remember, but I am pretty sure, that $4$ factors is not enough either.

Is there an efficient way to calculate the smallest example ?

$\endgroup$
  • $\begingroup$ Just to reiterate my warning (see README.txt in your new mini GAP installation) - it has limited functionality because in particular it has only 4 packages. For example, FactInt speeds up integer factorisation, and it's missing. You may add packages one after another downloading individual archives from their overview pages listed at gap-system.org/Packages/packages.html $\endgroup$ – Alexander Konovalov Dec 17 '15 at 0:25
  • $\begingroup$ But yes, even with a full GAP installation a sequential computation will take a while. Nothing with $gnu(n) > 10^6$ found overnight for $n \le 246464745$. $\endgroup$ – Alexander Konovalov Dec 17 '15 at 9:54
  • $\begingroup$ I have checked that the smallest solution must have at least $5$ prime factors. Maybe, this speeds up the search :) $\endgroup$ – Peter Dec 17 '15 at 12:15
  • $\begingroup$ Thanks, I think so - now at 365295805. Still a long way to go. $\endgroup$ – Alexander Konovalov Dec 17 '15 at 21:27
  • $\begingroup$ For numbers with more than $5$ prime factors, I checked that the smallest example must be greater than $1.7\times 10^9$. Probably the smallest example must have more than $5$ prime factors, but I did not prove that yet. $\endgroup$ – Peter Dec 20 '15 at 19:55
2
$\begingroup$

Yes, $n=8574796230$ is the smallest square-free number $n$ such that the number of groups of order $n$ is greater than $10^6$.

The number of groups of this order can be calculated in GAP as follows:

gap> NrSmallGroups(8574796230);
1243776

I did not have a chance to try anything better than a brute force approach, or even parallelising the check, so I was patient enough to run the following script to check that there are no smaller numbers with this property:

IsWorthTrying:=function(n) 
local d,x; 
d :=Factors(n); 
if Length(d)>4 and ForAll(Collected(d),x -> x[2]=1) then 
  return true; 
else 
  return false; 
fi;
end;

k:=1;
repeat 
  k:=k+1; 
  if IsWorthTrying(k) then 
    nr:=NrSmallGroups(k); 
    Print(k, " : ", nr, "                 \r");  
  else 
    nr:=0; 
  fi; 
until nr > 10^6; 
Print("\n\n");

As @Peter said, "the smallest solution must have at least $5$ prime factors", so it was checking only those with 5 or more prime factors. It was running from December 16th till February 6th, except maybe several days when it was stopped and then restarted from the point where it was at the time of the shutdown.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.